Алгоритм 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. Из минусов - очень большая вычислительная сложность метода.



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

Что такое robots.txt и зачем вообще нужен индексный файл

У каждого сайта в топе есть страница, о существовании которой знают только роботы и... SEO-специалисты. Это robots.txt или индексный файл....

19 07 2025 16:14:42

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

SEOmoz создал систему, которая определяет релевантность страницы поисковому запросу....

18 07 2025 9:35:15

Как обойти блокировку API запрещенных сервисов с помощью скриптов R

Как обойти блокировку API запрещенных сервисов с помощью скриптов R Как отключить блокировку API запрещенных сервисов в скриптах R и продолжать использовать пакеты ryandexdirect, rvkstat, rmytarget, Google Sheets и BigQuery...

17 07 2025 19:52:53

Как автоматизировать PPC-отчетность с помощью языка R, Google Таблиц и Data Studio

Как автоматизировать PPC-отчетность с помощью языка R, Google Таблиц и Data Studio Новый способ автоматизации процессов при настройке аналитики больших объемов данных....

16 07 2025 15:41:59

Язык R в веб-аналитике и интернет-маркетинге — интервью с Алексеем Селезневым

Зачем маркетологи и аналитики обращаются к языку программирования R в повседневной работе нужно и какая польза от программирования на R в интернет-маркетинге в интервью Алексея Селезнева...

15 07 2025 6:21:47

Внутренняя кухня SEO: считаем рентабельность блога и возвращаем трафик на сайт UniSender

Внутренняя кухня SEO: считаем рентабельность блога и возвращаем трафик на сайт UniSender Очередной красивый пост о продвижении платформы email и sms-рассылок — UniSender...

14 07 2025 14:19:43

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

Кейс по таргетированной рекламе в тематике «женская одежда»: ROMI 76% Насколько классно продается женская одежда в интернете....

13 07 2025 10:59:36

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

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

12 07 2025 22:59:50

Продвижение мобильного приложения: как вовлечь пользователей с помощью рекламы в Facebook?

Реклама Facebook для вовлечения пользователей помогает привлечь внимание к приложению и удержать пользователей в условиях перенасыщенного рынка....

11 07 2025 19:42:37

Массовые изменения в Google Ads Editor

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

10 07 2025 6:28:54

Какие товары загружать на маркетплейсы — аналитика Hubber

Какие товары загружать на маркетплейсы — аналитика Hubber Специалисты дропшиппинг-платформы делятся данными по самым продаваемым товарам на крупных онлайн-площадках. Информация для масштабирования бизнеса. Читать!...

09 07 2025 19:29:39

Как настроить Facebook Business Manager для продвижения мобильного приложения

Как настроить Facebook Business Manager для продвижения мобильного приложения Как зарегистрироваться в приложении Facebook Business Manager и грамотно сделать и настроить аккаунт...

08 07 2025 14:33:31

Как исключить спам в Google ***ytics, или Кто портит ваши данные

Как исключить спам в Google ***ytics, или Кто портит ваши данные Что делать, если вы столкнулись со спамом в отчетах Google ***ytics? Значит ли это, что кто-то имеет доступ к вашему аккаунту, или что кто-то специально влияет на данные сайта в GA? Как они это делают? И как исключить подобные данные из отчетов?...

07 07 2025 0:40:44

Эксцентричный и скромный Дарвин Смит

Эксцентричный и скромный Дарвин Смит Короткая история про одного из руководителей корпорации «Kimberly Clark». Альтернативная Википедия для тех, кто любит сторителлинг. Читать дальше!...

06 07 2025 23:25:52

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

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

05 07 2025 13:23:33

17 шагов к эффективному бренду, или Крутая зеленая ворона. Рецензия на книгу «Zag»

17 шагов к эффективному бренду, или Крутая зеленая ворона. Рецензия на книгу «Zag» Семнадцать крутых шагов к эффективному бренду Заг — это авторский неологизм от слова зигзаг (англ. zigzag). Он подразумевает движение в другом направлении....

04 07 2025 21:22:21

Синтаксис, виды и параметры UTM-меток — как правильно отследить трафик

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

03 07 2025 1:11:34

Контекстная реклама для строительной компании в Украине — рост конверсий в 5 раз

Контекстная реклама для строительной компании в Украине — рост конверсий в 5 раз Почему в рекламе недвижимости стоит запускать динамический ремаркетинг...

02 07 2025 9:32:25

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

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

01 07 2025 1:36:11

Google показывает не все результаты поиска

Google показывает не все результаты поиска Сколько страниц на самом деле показывает и может перевести поисковик Google?...

30 06 2025 5:47:23

Как отслеживать ускоренные мобильные страницы (AMP) в Google ***ytics

Что такое ускоренные мобильные страницы и как их посмотреть в Google ***ytics...

29 06 2025 1:16:28

Google Penguin: как защитить свои позиции в выдаче

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

28 06 2025 13:50:32

Обзор Netpeak Checker 2.1 — мультифункционального инструмента для массового анализа и сравнения сайтов

Обзор Netpeak Checker 2.1 — мультифункционального инструмента для массового анализа и сравнения сайтов Netpeak Checker – это мультифункциональный инструмент для массового анализа и сравнения сайтов, который помогает выполнять самые разнообразные задачи в области интернет-маркетинга....

27 06 2025 21:11:28

«Лучший питч — продукт, клиенты и доходы». Интервью с Виталием Гончаруком о маркетинге Augmented Pixels

«Лучший питч — продукт, клиенты и доходы». Интервью с Виталием Гончаруком о маркетинге Augmented Pixels СЕО of Augmented Pixels рассказал нам о принципах ведения бизнеса в Украине и США, о ненужности бизнес-планов и креативных питчей, а также о способе стать лучшим программистом...

26 06 2025 10:38:20

Гайд по форматам видеокампаний YouTube

Гайд по форматам видеокампаний YouTube Рекламные кампании для брендинга, роста вовлечения пользователей, продаж, лояльности. Какой формат выбрать, чтобы получить необходимое целевое действие. Узнать!...

25 06 2025 12:48:56

Как загрузить данные из API Google ***ytics в R: часть 2

Пример использования пакета google***yticsR от Марка Эдмондса...

24 06 2025 10:44:59

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

Как запустить рекламу на Reddit — руководство для новичка 330 миллионов активных пользователей и 14 миллиардов просмотров в месяц. Хорошо бы там запускать рекламные кампании....

23 06 2025 20:51:23

10 трендов email-маркетинга в 2022 году

10 трендов email-маркетинга в 2022 году All about internet mail. Примеры того, что стоит внедрить в рассылках почты онлайн....

22 06 2025 18:12:44

Три уровня оптимизации рекламной кампании в Google Ads

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

21 06 2025 8:47:55

Какие бывают движки для блогов

Какие бывают движки для блогов Бесплатные CMS помогают решить много задач без привлечения программиста или самостоятельного изучения кодов. Но у таких движков есть свои недостатки. Узнать больше!...

20 06 2025 14:14:36

Pitch perfect: как получить публикации в топовых медиа

Pitch perfect: как получить публикации в топовых медиа Если у вас есть продукт, о котором миру стоит узнать, книга Pitch perfect придется вам очень кстати....

19 06 2025 13:42:20

Как подобрать низкочастотные запросы и для чего это нужно

Низкочастотные, низкоконкурентные, Long Tail и другие термины, которые нужно знать и понимать....

18 06 2025 2:41:13

12 функций таблиц Google для работы с семантикой

12 функций таблиц Google для работы с семантикой + таблица с примерами использования каждой функции....

17 06 2025 18:19:37

Как молодому IP-адресу пробиться в мир больших email-рассылок — греем новичка

Как молодому IP-адресу пробиться в мир больших email-рассылок — греем новичка Алгоритм технической подготовки IP-адреса к массовым рассылкам...

16 06 2025 19:49:36

Списки исключенных мест размещения в Google Рекламе

Списки исключенных мест размещения в Google Рекламе О списках исключенных мест размещения будет интересно узнать тем, кто хочет облегчить себе работу с контекстно-медийными сетями....

15 06 2025 18:30:51

Семь улучшений Netpeak: построение репутации для нового бренда, продвижение в TikTok и PR-статьи в журнале

Семь улучшений Netpeak: построение репутации для нового бренда, продвижение в TikTok и PR-статьи в журнале Еще организовали новую онлайн-конференцию, запустили опрос онлайн-покупателей, создали SEO-услугу для крупного бизнеса, рассказали, как вести В2С и В2В аккаунты в Instagram и ввели консультации SMM-специалистов....

14 06 2025 7:18:26

Как за месяц получить 60 тысяч подписчиков для мобильной аудитории сайта: сотрудничество Gravitec.net и F.ua

Как за месяц получить 60 тысяч подписчиков для мобильной аудитории сайта: сотрудничество Gravitec.net и F.ua «Случайный» посетитель потому, что может уйти (не сделав покупку) и не вернуться, не стать клиентом. Пуш-уведомления позволяют посетителю сразу стать подписчиком: ему предлагают подписаться на рассылку. Как это использовать? Читайте!...

13 06 2025 19:57:51

Как быстро увеличить продажи — мнения руководителей отделов продаж

Как быстро увеличить продажи — мнения руководителей отделов продаж Как повысить результаты продаж в режиме цейтнота. Советы новому руководителю от специалистов Netpeak Group. Больше подробностей — в посте...

12 06 2025 10:26:41

Почему мы так говорим — из истории устойчивых выражений

Почему мы так говорим — из истории устойчивых выражений Об истории и значении поговорок и других фразеологических оборотов...

11 06 2025 20:25:53

Как выбрать платформу для вебинаров

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

10 06 2025 22:16:25

Выбираем оффер правильно: инструкция для начинающего арбитражника

От того, что такое оффер до лучших стратегий и избежания ошибок...

09 06 2025 17:45:29

Интервью с Юлией Куриловой

Интервью с Юлией Куриловой Увлекательные истории от специалиста по контекстной рекламе....

08 06 2025 8:51:33

Core Web Vitals: что это такое и как работает

Core Web Vitals: что это такое и как работает В мае прошлого года Google анонсировал выход нового Core Web Vitals. Что это и как будет работать рассмотрим в статье...

07 06 2025 0:46:17

Как добавить видео на Youtube с телефона. Пошаговая инструкция

Как добавить видео на Youtube с телефона. Пошаговая инструкция Будь мобильным — заливай видео на Youtube с телефона...

06 06 2025 6:19:25

Семь массовых сбоев, оставивших миллионы людей без привычных сервисов

Семь массовых сбоев, оставивших миллионы людей без привычных сервисов Пожар в дата-центре, неудачные обновления и то самое падение Facebook....

05 06 2025 19:35:27

Netpeak Spider — помощник при составлении технического аудита сайта

Netpeak Spider — помощник при составлении технического аудита сайта Мы запустили еще один полезный инструмент: Netpeak Spider....

04 06 2025 17:23:49

Как узнать сколько стоит ваш сайт

Как узнать сколько стоит ваш сайт На что обратить внимание при покупке интернет-ресурса, какие факторы влияют на цену и что помогает определить качество сайта? Ответы на все эти вопросы в статье. Читать!...

03 06 2025 18:40:44

10 творческих задач на собеседовании Wieden+Kennedy в интернете

10 творческих задач на собеседовании Wieden+Kennedy в интернете 10 заданий, которые заставят пошевелить мозгами и придумать нестандартные решения. Используйте их (видоизмените, адаптируйте) под свой продукт или услугу. Создайте крутую кампанию, креатив или предложите это своей комaнде....

02 06 2025 16:43:47

Обязательные элементы email-рассылки: проверьте свои письма на привлекательность

Четкая структура полноценного письма с примерами из рассылок крупных компаний: Aviasales, LinguaLeo, Rozetka, Yves Rocher, Pich Shop, Эльдорадо и другие....

01 06 2025 8:32:11

Что делать с бизнесом, когда нужен взрывной рост и позиция лидера ниши

Что делать с бизнесом, когда нужен взрывной рост и позиция лидера ниши Как стать лидером ниши не на словах, а на деле. Пошаговый алгоритм....

31 05 2025 3:30:49

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