Алгоритм LSA для поиска похожих документов > NetPeak - Независимость и осознанность
NetPeak Biz Tech    


Алгоритм LSA для поиска похожих документов

Алгоритм LSA для поиска похожих документов

< >

И снова наш аналитический отдел подготовил материал для читателей блога Netpeak. Передаю привет Кириллу Левенцу — он проделал титанический труд, чтобы изложить понятным языком не самые простые вещи.

Среди огромного числа алгоритмов, которые используются для поиска и анализа информации, особое место занимают те, чья цель — обнаружение скрытых закономерностей или неочевидных зависимостей.

Используя семантический анализ текста, мы можем сказать, например, что два текста похожи, даже если эта похожесть выражена косвенно. Или например «лыжи» и «автомобиль» по отдельности относятся к разным категориям, но будучи использованы вместе, могут быть интерпретированы в таких категориях, как «спорт» и «отдых».

Об одном из методов, который применяется для рекомендательных систем (коллаборативная фильтрация), информационного семантического поиска, разделения текстов по тематикам без обучения и многих других и пойдет речь далее. Метод этот называется латентно-семантическим анализом (LSA — Latent semantic ***ysis). Можно сказать, что это продвинутый SEO анализ текста.

Рассмотрим более подробно, что это за метод и как он работает

Уже из названия можно сделать вывод о том, что он должен делать, а именно находить скрытые смысловые взаимосвязи между объектами (будь-то слова в тексте или товары в магазине). Для текстов на естественных языках такой скрытой закономерностью может быть, например, наличие определенного набора слов в определенной теме. Представим себе такую задачу: у нас есть коллекция документов и мы хотим научиться отвечать на вопрос: два документа близки по тематике или нет. Вывод о схожести можно сделать, основываясь на том, какие слова и в каких пропорциях входят в каждый из документов.

Чтобы подготовить данные для этой задачи, используют подход, который называется «мешок слов».

Его суть состоит в том, что для нас неважен порядок слов в документе, в каких морфологических формах они представлены, а важно только количество вхождений конкретных слов. Предположим, что каждую тему можно охаpaктеризовать определенным набором слов и частотой их появления. Если в тексте конкретный набор слов употрeбляется с определенными частотами, то текст принадлежит к определенной теме.

Основываясь только на этой информации, строится таблица «слово-документ». Где строки соответствуют словам (а точнее, их леммам), а столбцы - документам. В каждой ячейке хранится 1, если слово есть в документе, и 0 - если нет. Хотя такой вариант и самый простой, но не самый лучший. Вместо 0 и 1 можно использовать, например, частоту слова в документе или tf-idf слова. Такой способ представления текстов в виде таблицы (или матрицы) называется векторной моделью текста. Теперь, для того чтобы сравнить два документа, нужно определить меру схожести двух столбцов таблицы.

Сделать это можно по-разному:

  • скалярное произведение векторов - столбцов таблицы;
  • косинусное расстояние (пожалуй самое адекватное) ;
  • евклидовым расстоянием;
  • манхэттенским расстоянием.

Чтобы лучше понять все вышесказанное, изобразим это графически на простом примере двух небольших текстов. Один  текст про письменность, другой про неопределенность Гeйзенберга. Стоп-слова удалены, а остальные приведены к основной форме (без окончаний). Каждая точка на графике — слово. На осях отложено, сколько раз слово встретилось в каждом документе. Т.е. если слово встретилось в тексте про неопределенность 3 раза, а в тексте про письменность 2 раза, то на рисунке это слово изобразим точкой с координатами (3,2).

Видно, что в этом примере некоторые слова встречались и в одном и в другом тексте приблизительно одинаково часто («свободн», «друг», «звук» и так далее). Такие слова не дают возможности отличить тексты один от другого и в принципе сравнимы со стоп-словами. Но есть слова, которые хаpaктерны только одному из текстов. Имея такое представление текста, мы можем определять близость каждого слова к теме (как косинус угла между вектором с началом в (0;0) и концом в точке слова и осью, соответствующей документу). Если же такого слова в коллекции нету, то о нем мы ничего не можем сказать.

Для сравнения документов можно подсчитать сумму векторов-слов, которые в них входят и опять же оценить расстояние между ними. В рассмотренном примере слова распределились хорошо, так как тематики существенно разные. А если тематики схожи, то может получиться такая картина:

По сравнению с предыдущей картинкой видно, что документы существенно похожи, и, кроме того, есть слова, которые хаpaктеризуют общую тематику для обоих текстов (например \"язык\" и \"письмен\"). Такие слова можно назвать ключевыми для данной темы. Т.е. напрашивается вывод, что имея такое представление текстов, мы теоретически можем сгруппировать документы по близости их содержимого, и таким образом построить тематическое разбиение коллекции текстов. В частности может оказаться, что каждый документ - это отдельная тема. Также можно искать документы по запросу, при этом могут находиться документы, которые не содержат слов из запроса, но близки ему по теме.

Но в жизни оказывается, что документов и слов очень много (гораздо больше чем тем) и возникают следующие проблемы:

  • размерности (вычисление близости между векторами становится медленной процедурой) ;
  • зашумленности (например, посторонние небольшие вставки текста не должны влиять на тематику) ;
  • разряженности (большинство ячеек в таблице будут нулевыми).

В таких условиях довольно логично выглядит идея, вместо таблицы \"слово-документ\" использовать что-то типа \"слово-тема\" и \"тема-документ\". Решение именно такой задачи предлагает LSA. Правда, интерпретация полученных результатов может оказаться затруднительной.

На рисунке приведен пример карты двух художественных текстов. Видно, что у них есть как свои особенности, так и много общего, и можно выделить новую тематику. Если говорить в терминах линейной алгебры, то нам нужно такое представление:

Числа в таблицах в общем случае не обязательно будут именно 0 и 1. Имея такое представление, мы можем кроме оценки близости слов и документов, также определять важные слова для каждой тематики.

Ограничения LSA:

  1. Невозможно получить тематик больше чем документов/слов.
  2. Семантическое значение документа определяется набором слов, которые, как правило, идут вместе.
  3. Документы рассматриваются как просто наборы слов. Порядок слов в доку­ментах игнорируется. Важно только то, сколько раз то или иное слово встречается в документе.
  4. Каждое слово имеет единственное значение.
  5. Недостаток LSA — предположение о том, что карта слов в документах не имеет вид нормального распределения. С этой проблемой справляются другие модификации метода (вероятностный LSA и LDA).

LSA включает в себя следующие этапы:

  1. Удаление стоп-слов, стемминг или лемматизация слов в документах;
  2. Исключение слов, встречающихся в единственном экземпляре;
  3. Построение матрицы слово-документ (бинарную есть/нет слова, число вхождений или tf-idf) ;
  4. Разложение матрицы методом SVD (A = U * V * WT) ;
  5. Выделение строк матрицы U и столбцов W, которые соответствуют наибольшим сингуляр­ным числам (их может быть от 2-х до минимума из числа терминов и документов). Конкретное количество учитываемых собственных чисел определяется предполагаемым количеством семантических тем в задаче. А вообще чем больше сингулярное число, тем сильнее в коллекции проявлена тема.

В итоге получается нечто такое:

Пример с небольшими документами

[Взят из статьи Indexing by Latent Semantic ***ysis, Scott Deerwester, Susan T. Dumais, George W. Furnas, and Thomas K. Landauer, Richard Harshman]

Пусть имеется следующий набор заголовков-документов:

  • c1: Human machine interface for ABC computer applications
  • c2: A survey of user opinion of computer system response time
  • c3: The EPS user interface management system
  • c4: System and human system engineering testing of EPS
  • c5: Relation of user perceived response time to error measurement
  • m1: The generation of random, binary, ordered trees
  • m2: The intersection graph of paths in trees
  • m3: Graph minors IV: Widths of trees and well-quasi-ordering
  • m4: Graph minors: A survey

Выделяем слова, которые встретились хотя бы в двух заголовках. И строим матрицу слово-документ: в ячейках будем писать количество вхождений слова в до­кумент.

Применяем сингулярное разложение к этой матрице и получаем три матрицы (U, V, WT).

Чтобы иметь возможность визуально оценить результат, выделим только две главные компоненты, соответствующие самым большим сингулярным числам. Используем значения в выделенных столб­цах как координаты и изобразим их в виде точек на плоскости (синим цветом документы, красным - слова, кругами - возможные тематики).

Рассмотрим расстояние между каждой парой слов. Было (желтым цветом выделены значения выше 0):

Стало после снижения размерности (зеленым цветом выделены значения больше 0,8):

Как и по картинке, так и по таблице видно, что термины образовали 2 группы (довольно условно) и по сравнению с исходной матрицей связи значительно усилены (как укрепились исходные, так и появились новые):

  • [human, interface, computer, user, EPS, response, time],
  • [survey, trees, graph, minors].

Между каждой парой документов.

Было:

Стало:

Отношение термин документ.

Было:

Стало:

Рассмотрим еще один пример: пусть имеются три документа, каждый - на свою тематику (первый про автомобили, второй про спорт и третий про компьютеры). Используя LSA, изобразим двумерное представление семантического прострaнcтва, и как в нем будут представлены слова (красным цветом), запросы (зеленым) и документы (синим). Напомню, что все слова в документах и запросах прошли процедуру лемматизации или стемминга.

Видно, что тема \"компьютер\" хорошо отделилась от двух других. А вот \"спорт\" и \"авто\" довольно близки друг другу. Для каждой темы проявились свои ключевые слова. Зеленым на рисунке изображен запрос \"автомобил колес\". Его релевантность к документам имеет следующий вид:

  1. \\\'sport.txt\\\' - 0.99990845
  2. \\\'auto.txt\\\' - 0.99987185
  3. \\\'computer.txt\\\' - 0.031289458

Из-за близости тем \"спорт\" и \"авто\" довольно сложно точно определить, к какой теме он принадлежит. Но точно не к \"компьютерам\". Если в системе, обученной на этих документах, попытаться определить релевантность к образовавшимся темам слова \"рынок\", то в ответ мы получим 0 (т.к. это слово в документах не встречалось ни разу). Добавим в систему документ по теме \"финансы\". Будем снова искать слово \"рынок\".

Получим следующую картинку:

Релевантность к темам будет такой:

  1. \\\'finance.txt\\\' - 0.99948204
  2. \\\'sport.txt\\\' - 0.97155833
  3. \\\'auto.txt\\\' - 0.23889101
  4. \\\'computer.txt\\\' - -0.24506855

Итак подведем итог:

  1. LSA позволяет снизить размерность данных - не нужно хранить всю матрицу слово-документ, достаточно только сравнительно небольшого набора числовых значений для описания каждого слова и документа.
  2. Получаем семантическое представление слов и документов - это позволяет находить неочевидные связи между словами и документами.
  3. Из минусов - очень большая вычислительная сложность метода.



Комментарии:

Чаты для бизнеса от Яндекс: руководство по настройке

Чаты для бизнеса от Яндекс: руководство по настройке Идеи для интернет-маркетологов, как получить дополнительные каналы трафика и сделать заметным сниппет в поисковой выдаче....

19 03 2023 5:35:14

Discovery Ads для рекламы в YouTube и Gmail — мини кейс Intertop

Discovery Ads для рекламы в YouTube и Gmail — мини кейс Intertop Новый тип рекламных кампаний, который помогает расширить целевую аудиторию. Потенциальных покупателей можно найти среди людей не знакомых с вашим брендом....

18 03 2023 8:18:38

Лучшие персональные сайты маркетологов

Лучшие персональные сайты маркетологов Цели у личных сайтов могут быть разные, но в первую очередь они помогают рассказать историю о специалисте...

17 03 2023 21:14:58

Реактивационные письма: примеры уместных рассылок для возврата спящих подписчиков

Реактивационные письма: примеры уместных рассылок для возврата спящих подписчиков Как вернуть клиентов с помощью реактивационных email-рассылок. Внутри идеи таких брендов: Bershka, Wildberries, LinguaLeo, Facebook, Mail.ru, Coub, BlaBlaCar, Repka.ua и другие. Узнайте принципы красивой реактивации!...

16 03 2023 22:41:25

8 ненужных пунктов в SEO-аудите

Глоссарий глупых ошибок в аудите от топовых SEO-агентств...

15 03 2023 15:19:22

Как с помощью ASO увеличить количество бесплатных установок на 25% — кейс monobank

Как с помощью ASO увеличить количество бесплатных установок на 25% — кейс monobank Нам удалось увеличить количество органических показов на 63% и установок на 25%....

14 03 2023 23:40:47

Netpeak Харьков: правила жизни нового офиса

Netpeak Харьков: правила жизни нового офиса Офис Netpeak в Харькове официально открыт! В этом посте, вместо игры на фанфарах, мы на собственном примере рассмотрим, что нужно для создания регионального отделения в разгар кризиса....

13 03 2023 1:33:44

Кейс по таргетированной рекламе в тематике «бижутерия»: ROMI 90%

Кейс по таргетированной рекламе в тематике «бижутерия»: ROMI 90% Итоги одной из наших первых онлайн рекламных кампаний в Play...

12 03 2023 20:14:25

Анна Романишина о школе английского, тайм-менеджменте и продвижении

Анна Романишина о школе английского, тайм-менеджменте и продвижении Интервью с основателем школы английского языка Progress...

11 03 2023 11:47:39

Новая реальность: боты принимают на работу и ходят на свидания

Новая реальность: боты принимают на работу и ходят на свидания История свидания двух ботов как иллюстрация развития искусственного интеллекта...

10 03 2023 5:39:51

Каково это — работать в Google

Каково это — работать в Google О том, как работают, празднуют, танцуют и в какой корпоративной культуре живут сотрудники корпорации Google. Этот пост развеет кое-какие мифы....

09 03 2023 8:28:26

Как METRO отказалась от печатных каталогов

Как METRO отказалась от печатных каталогов Как METRO Cash & Carry Украина нашла индивидуальный подход к 1 000 000 клиентов....

08 03 2023 18:38:57

Как открыть офис в Индии и не облажаться

История Affise от фаундера компании, рассказанная на SaaS Nation....

07 03 2023 19:20:29

Фокус, обучение, контроль — три кита развития бизнеса. Хасан Исламов об истории Chocofamily

Фокус, обучение, контроль — три кита развития бизнеса. Хасан Исламов об истории Chocofamily Хасан Исламов о развитии Chocofamily, крупнейшего интернет-холдинга Казахстана....

06 03 2023 17:52:41

Как улучшить UX сайта — 12 советов по юзабилити

Как улучшить UX сайта — 12 советов по юзабилити Какие фишки влияют на видимость сайтов? Советы по юзабилити от SEO-специалиста....

05 03 2023 2:35:37

Как увеличить продажи из РСЯ — рост транзакций на 427% за месяц

Как увеличить продажи из РСЯ — рост транзакций на 427% за месяц Как увеличить количество транзакциий, сохранив прибыльность кампании в РСЯ?...

04 03 2023 16:31:46

17 неочевидных и пpaктически применимых фишек SaaS Nation 2018

17 неочевидных и пpaктически применимых фишек SaaS Nation 2018 Лучшие маркетинговые и бизнес-фишки от Давида Брауна (Weblium), Владислава Флакса (OWOX), Александра Галкина (Competera), Люси Литерадо (Reply.io), Вадима Нехая (Depositphotos), Валерия Грабко (PromoRepublic), Игоря Дебатура (Uploadcare), Руслана Савчишин...

03 03 2023 15:11:17

Исследования рынка — новая услуга Netpeak

Исследования рынка — новая услуга Netpeak Предложение для крупных и средних бизнес-проектов по эффективному использованию больших бюджетов при запуске на новых рынках...

02 03 2023 2:28:41

LinkedIn для SaaS-сервисов: почему это выгодно?

LinkedIn для SaaS-сервисов: почему это выгодно? Обычно SaaS-бизнесы начинают привлечение лидов с запуска рекламы на Facebook. Но наш опыт говорит о том, что это не самые подходящие каналы. Более высокие результаты можно получить на LinkedIn....

01 03 2023 1:37:55

Стратегия ведения контекстной рекламы по воронке продаж на примере SaaS: шаблон и инструкция

Стратегия ведения контекстной рекламы по воронке продаж на примере SaaS: шаблон и инструкция Как найти индивидуальный подход к аудитории на каждом этапе воронки продаж? В этом вам поможет правильно составленная стратегия контекстной рекламы....

28 02 2023 2:32:23

Как использовать холодную рассылку для поиска инвесторов — советы стартапам

Как владельцу стартапа пробиться сквозь сотни ежедневных сообщений, которые получает инвестор, создать эффективную цепочку писем и быть замеченным...

27 02 2023 15:35:30

Как работать с Open Graph

Как работать с Open Graph Что нужно сделать, чтобы превью веб-страниц в социальных сетях стало магнитом для пользователей?...

26 02 2023 14:25:59

Как найти PBN конкурента

Как найти PBN конкурента Как найти сетку сайтов конкурентов — рассказываем о популярных методах и секретных фишках. Бонус — инструкция по выявлению PBN конкурентов. Читать дальше!...

25 02 2023 17:35:34

Big Data SEO — как заставить большие данные работать на ваш бизнес

Big Data SEO — как заставить большие данные работать на ваш бизнес Решение для поискового продвижения крупных проектов (от 300 000 страниц)....

24 02 2023 12:43:44

Сколько стоил клик по рекламе Ads, Директ и Facebook в Украине во втором квартале 2017

Сколько стоил клик по рекламе Ads, Директ и Facebook в Украине во втором квартале 2017 Я исследовал 23 миллиона кликов из Украины в Google Ads, Facebook, Директ и структурировал данные по 19 тематикам...

23 02 2023 14:34:59

Какие виды гeймификации можно использовать в рассылках

Какие виды гeймификации можно использовать в рассылках Игровой формат отлично работает в email-рассылке. Но какой вид гeймификации интересен любой целевой аудитории? Давайте рассмотрим примеры....

22 02 2023 8:31:23

Почему отдел продаж сидит без дела. Находим решение с помощью коллтрекинга

Почему отдел продаж сидит без дела. Находим решение с помощью коллтрекинга Отслеживаем пропущенные, анализируем входящие и делаем выводы о том, как организовать работу менеджеров....

21 02 2023 21:53:49

Как платить за рекламные аккаунты в Украине, России и Казахстане

Как платить за рекламные аккаунты в Украине, России и Казахстане Подробно об оплате аккаунтов и налогообложении рекламы в Украине, России, Казахстане....

20 02 2023 4:40:37

Малкольм Гладуэлл о гениях и аутсайдерах

Малкольм Гладуэлл о гениях и аутсайдерах Миллионы решили купить книгу гении и аутсайдеры на Amazon: удивительное исследование канадского журналиста...

19 02 2023 20:26:12

Как увеличить CTR и open rate в email-рассылках: получаем больше переходов на сайт

Как увеличить CTR и open rate в email-рассылках: получаем больше переходов на сайт Делимся советами по оптимизации рассылок. Важны новые форматы писем, предварительное тестирование, смена тем письма, ярче CTA. Все это в сочетании с понятностью и искренностью не заставит ждать хороший CTR...

18 02 2023 0:59:43

Почему Google Merchant Center может заблокировать аккаунт

Почему Google Merchant Center может заблокировать аккаунт На что обращает внимание система и менеджеры Google при проверке сайта и аккаунта....

17 02 2023 23:50:19

Артем Борисов из Яндекс.Казахстан: казахстанцам нужен качественный контент на родном языке

Артем Борисов из Яндекс.Казахстан: казахстанцам нужен качественный контент на родном языке Почему встречаются низкие показатели переходов на сайты по всем источникам трафика? Нет рекламодателей, которые могут предложить пользователям те или иные товары и услуги....

16 02 2023 18:24:20

Примеры писем интернет-магазинов: лучшие e-mail письма и рассылки клиентам после покупки

Примеры писем интернет-магазинов: лучшие e-mail письма и рассылки клиентам после покупки Как надолго завоевать доверие покупателя с помощью грамотного email-маркетинга? Примеры обращений к клиенту в рассылках, текст писем для привлечения и благодарности за покупку....

15 02 2023 15:12:31

Семь улучшений Netpeak: новые услуги и веб-аналитика для крупного бизнеса. Выпуск шестой

Семь улучшений Netpeak: новые услуги и веб-аналитика для крупного бизнеса. Выпуск шестой Рассказываем в подробностях, что полезного сделал Netpeak для своих клиентов с января по апрель 2017 года...

14 02 2023 7:35:43

Page Authority & Domain Authority

Page Authority & Domain Authority Что же такое эти authority и чем они лучше и полезнее, к примеру, чем Page Rank?...

13 02 2023 20:34:24

Как найти фейковые 404 страницы с помощью Google Tag Manager

Как найти фейковые 404 страницы с помощью Google Tag Manager Как помешать фейковым 404 страницам испортить статистику вашего сайта?...

12 02 2023 9:28:42

Контекстная реклама интернет-магазина автотоваров — как снизить траты и увеличить ROMI на 772%

Контекстная реклама интернет-магазина автотоваров — как снизить траты и увеличить ROMI на 772% Изучаем на примере тестирования товарных кампаний в момент смены логотипа и ренейминга...

10 02 2023 14:19:25

Как продвигать бренд в Facebook без бюджета на рекламу

Что делать, если денег нет, но трафик очень нужен: советы по раскрутке бренда в фейсбуке. В бесплатном продвижении главный ресурс — время: часы, дни, недели, месяцы, проведенные на площадке. Как их применить? Читайте!...

09 02 2023 4:51:36

Как мы подняли МRR с нуля до 24 тысяч долларов без бюджета, комaнды и маркетинговой стратегии

Как мы подняли МRR с нуля до 24 тысяч долларов без бюджета, комaнды и маркетинговой стратегии Опыт стартапа Paperform для стартаперов, которые боятся начать из-за ограниченного бюджета и/или отсутствия знаний в маркетинге. Надеемся, эта история вдохновит предпринимателей и поможет меньше сомневаться на счет запуска без бюджета....

08 02 2023 17:10:46

Уроки Google ***ytics — как добавить новый сайт в Google ***ytics

Уроки Google ***ytics — как добавить новый сайт в Google ***ytics Как настроить Google ***ytics и как открыть вход другому пользователю: подробный урок....

07 02 2023 11:42:54

Что такое консалтинг от Netpeak и почему он нужен инхаус-комaндам

Что такое консалтинг от Netpeak и почему он нужен инхаус-комaндам Где найти лидера для своей инхаус-комaнды маркетологов...

06 02 2023 2:18:10

5 советов для специалистов по контекстной рекламе

5 советов для специалистов по контекстной рекламе Полезные советы для тех, кто делает контекст своими ручками :)...

05 02 2023 3:45:40

Как специалисту по контекстной рекламе прокачать soft skills

Как специалисту по контекстной рекламе прокачать soft skills 5 важных навыков для новичков в PPC: как учиться, чтобы стать экспертом; секреты тайм-менеджмента, мотивации; тонкости оптимизации рабочего процесса. Узнать больше!...

04 02 2023 6:12:40

Зачем нужен медиаплан и как его составить?

Зачем нужен медиаплан и как его составить? Чтобы и клиенту не стыдно было показать и свои ожидания не обмануть....

03 02 2023 8:21:49

Рычаги управления людьми

Рычаги управления людьми Эта книга рекомендована к прочтению решительно всем :)...

02 02 2023 14:58:38

Как перевести свой аккаунт с Google ***ytics на Universal ***ytics

Как перевести свой аккаунт с Google ***ytics на Universal ***ytics Читайте простой мануал о том, как перейти на Universal ***ytics и не поломать весь сбор данных...

01 02 2023 22:26:31

Что делать начинающим бизнесменам — злой пост-руководство

Что делать начинающим бизнесменам — злой пост-руководство Сначала учитесь, а потом идите в бизнес и предпринимательство. Бизнес — это игра, в которую играют пару тысяч лет, и здесь не нужно придумывать велосипеды. Научитесь сначала просто ездить, потом уже будете думать про кастомы....

31 01 2023 23:55:53

Прием антисептика внутрь, парень-микрофончик и открыть рот за $9: реклама в соцсетях в феврале 2021

Примеры странной, классной и непонятной рекламы в соцсетях из моей ленты за февраль 2021 года...

30 01 2023 19:33:34

Как работать с Яндекс.Вебвизор 2.0

Как работать с Яндекс.Вебвизор 2.0 Бета-версия помогает записывать действия пользователей на сайте и благодаря этому улучшать удобство использования сайта и в перспективе растить продажи. Узнать больше!...

29 01 2023 9:51:16

Еще:
понять и запомнить -1 :: понять и запомнить -2 :: понять и запомнить -3 :: понять и запомнить -4 :: понять и запомнить -5 :: понять и запомнить -6 :: понять и запомнить -7 ::