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



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

Бизнес и экология. В компании Herman Miller наняли на работу пчёл

Бизнес и экология. В компании Herman Miller наняли на работу пчёл Сортировка мусора, использование велосипедов вместо автомобилей, озеленение города... В Украине, как правило, так представляют экофрендли бизнес. Зарубежные компании идут дальше....

27 02 2024 5:34:56

Как улучшить оценку качества целевой страницы в Google Ads — эксперимент Netpeak

Как улучшить оценку качества целевой страницы в Google Ads — эксперимент Netpeak Можно ли повысить оценку качества целевой страницы , если проставить конечные URL на уровне ключевого слова? Результаты исследования....

26 02 2024 0:43:16

Как и когда выходить на рынки других стран — советы Google

Как и когда выходить на рынки других стран — советы Google Менеджер экспортного направления Гугл Украина — об особенностях выхода на рынки разных стран мира....

25 02 2024 7:22:21

Зачем нужны целевые страницы и что такое лидогенерация

Всё, что важно узнать о лидогенерации и работе с целевой аудиторией....

24 02 2024 2:13:13

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

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

23 02 2024 19:26:59

Как мы продвигали приложение в Instagram и получили CPI в два раза ниже, чем в Facebook

Как мы продвигали приложение в Instagram и получили CPI в два раза ниже, чем в Facebook Case по продвижению в Instagram. В любой непонятной ситуации — масштабируйте рекламные инструменты...

22 02 2024 1:40:56

Отчет «Статистика аукционов» в Google Рекламе

Отчет «Статистика аукционов» в Google Рекламе Пpaктика в режиме «рейтинг онлайн». Новинка Google Рекламы — отчет «Статистика аукционов»....

21 02 2024 5:13:46

Удаленка и низкая продуктивность — когда пора выходить в офис

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

20 02 2024 17:56:44

Как работать с аудиториями Google Ads в наблюдении

Давайте больше не будем сливать бюджет, выбирая неправильный параметр....

19 02 2024 11:44:24

Продвижение мобильного приложения — шпаргалка для строителей воронок продаж

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

18 02 2024 15:15:28

Как с помощью контекстной рекламы мы добились роста брендового трафика на 268% за два года — опыт Kentavar.bg

Как с помощью контекстной рекламы мы добились роста брендового трафика на 268% за два года — опыт Kentavar.bg Повышаем узнаваемость бренда с помощью медийной кампании, а затем отслеживаем результат по запуску поисковой кампании с брендовыми запросами...

17 02 2024 21:11:42

Кейс по SEO для тематики «осветительные приборы, мебель и декор», регион Болгария: рост органического трафика на 108,96%

Кейс по SEO для тематики «осветительные приборы, мебель и декор», регион Болгария: рост органического трафика на 108,96% Кейс по росту органического трафика на сайте интернет-магазина на платформе Summer Cart....

16 02 2024 11:18:12

Исследование о влиянии отзывов в интернете на решение о покупке

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

15 02 2024 9:41:21

Как быстро найти ошибки на сайте — проверка важных тегов с помощью Google Tag Manager и таблиц Google

Как быстро найти ошибки на сайте — проверка важных тегов с помощью Google Tag Manager и таблиц Google Тестирования наличия важных тегов на целевых страница — бесплатный скрипт и алгоритм...

14 02 2024 22:55:50

Какие ошибки возникают при работе с Google ***ytics и как с ними бороться

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

13 02 2024 4:41:37

Кейс: крауд-маркетинг для увеличения продаж интернет-магазина

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

12 02 2024 20:14:17

Сколько стоил клик Google Ads и Facebook в Украине во втором квартале 2018 года

Сколько стоил клик Google Ads и Facebook в Украине во втором квартале 2018 года Ежеквартальное исследование Netpeak по стоимости клика...

11 02 2024 14:23:30

Кейс: учим поисковый движок распознавать грамматические ошибки

Кейс: учим поисковый движок распознавать грамматические ошибки Что поможет написать объявление без грамматических ошибок? В недрах агентства Netpeak рождается новый полезный сервис...

10 02 2024 1:21:14

Что такое гонзо-копирайтинг и как его определить?

Что такое гонзо-копирайтинг и как его определить? Примеры креативного авторского стиля копирайтеров, которые старались обыграть УТП продукта, услуги, стремились необычно подать обычное. Узнать больше!...

09 02 2024 7:20:17

Дополнение Google Ads для Google Taблиц — руководство пользователя

Дополнение Google Ads для Google Taблиц — руководство пользователя Как сократить время на создание собственных отчетов, если вы работаете с большими рекламными аккаунтами...

08 02 2024 9:53:15

Какие фишки я беру у конкурентов — дневник оптимизатора

Какие фишки я беру у конкурентов — дневник оптимизатора Заимствуете лучшее, коллекционируйте идеи и не откладывайте тестирование фишек в долгий ящик...

07 02 2024 10:12:26

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

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

06 02 2024 18:32:25

Кейс по продвижению интернет-магазина велосипедов и велозапчастей: ROMI 58%

Проделанные шаги и полученные результаты при раскрутке магазина великов в интернете...

05 02 2024 12:14:17

Дизайн email-рассылки: как мотивировать подписчиков

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

04 02 2024 11:43:15

Как составить и анализировать KPI для PR-менеджера

Как составить и анализировать KPI для PR-менеджера PR должен решать задачи бизнеса и для этого мало мониторить упоминания компании или бренда, нужно анализировать. С появлением соцсетей пиар изменился. Узнать больше!...

02 02 2024 21:12:17

Партиционирование таблиц в Google BigQuery — понятная инструкция

Партиционирование таблиц в Google BigQuery — понятная инструкция Как упростить работу с данными и сэкономить на оплате сервиса...

01 02 2024 12:55:25

10 SEO-требований к сайту

Советы и даже требования SEO-специалистов к разработчикам сайтов....

31 01 2024 15:45:40

Как сделать разработчикам приятно — опыт Netpeak

Как сделать разработчикам приятно — опыт Netpeak Отличный способ мотивации, который мы попробовали и вам рекомендуем....

30 01 2024 22:52:15

Почему мертвецы ставят «лайки» в Facebook?

Почему мертвецы ставят «лайки» в Facebook? Темная сторона лайков или правда о продвижении постов в Facebook...

29 01 2024 23:40:37

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

Кейс по привлечению платного трафика в тематике «оптовая торговля одеждой»: ROMI 345% О том как растут доходы при оптовой торговле женской одеждой и обувью, а траты на рекламу остаются на прежнем уровне...

28 01 2024 13:43:18

SEO-среда: Основные инструменты веб-мастера

SEO-среда: Основные инструменты веб-мастера Пройдем вместе путь вебмастера от первых шагов и до вершины ТОПа :)...

27 01 2024 6:52:20

Как рекламировать в гугл игры мужчинам и женщинам гeймерам

Как рекламировать в гугл игры мужчинам и женщинам гeймерам Что нужно учесть при создании баннеров для разных аудиторий...

26 01 2024 1:48:20

Как получить 184% прироста трафика и увеличить долю поискового трафика в три раза в gaming-тематике — кейс Wowcarry

Как получить 184% прироста трафика и увеличить долю поискового трафика в три раза в gaming-тематике — кейс Wowcarry Доля органического трафика увеличилась с 14% до 44%, а небрендового — на 184%....

25 01 2024 19:22:17

Изменение поведения: факторы влияния

Изменение поведения: факторы влияния Формула изменения поведения Фогга и два красочных примера инсайде....

24 01 2024 0:21:24

Как приводить трафик на молодой сайт: результаты обсуждения темы на Quora

Как приводить трафик на молодой сайт: результаты обсуждения темы на Quora Повышение посещаемости на сайте: контент, seo, ppc и многое другое...

23 01 2024 15:18:19

Как удалить себя из социальных сетей

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

22 01 2024 10:37:24

Как создать графическое объявление в Google Рекламе

Как создать графическое объявление в Google Рекламе Многие не догадываются о том, что в КМС Google можно разместить и редактировать графические объявления онлайн...

21 01 2024 1:40:50

Как составить техзадание по крауд-маркетингу для сайтов услуг

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

20 01 2024 17:20:59

Кто такой аккаунт-менеджер Netpeak

Кто такой аккаунт-менеджер Netpeak Аккаунт менеджеры это... Быть лицом компании, проводником между заказчиком и комaндой агентства, ментором для коллег и суперменом, готовым прийти на помощь клиенту в любой час дня и ночи… Эти задачи по плечу аккаунт-менеджерам Netpeak...

19 01 2024 12:35:36

10 онлайн способов улучшить контент

10 онлайн способов улучшить контент Как преодолеть онлайн писательский ступор, разобраться с рутиной и освободить время для экспериментов...

18 01 2024 4:19:19

Динамический ремаркетинг в myTarget: подробный мануал и кейс

Динамический ремаркетинг в myTarget: подробный мануал и кейс Как настроить динамический ремаркетинг в myTarget и эффективно ли работают такие объявления — делимся собственным опытом....

17 01 2024 1:39:38

Внутренние факторы ранжирования — как сделать сайт понятным для поисковых систем

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

16 01 2024 23:24:48

Как настроить языковую версию сайта

Если выполнить настройку не корректно, поисковик воспримет материалы как дубли контента....

15 01 2024 7:53:45

Итоги Всемирного дня шопинга: рост продаж в 11 раз в Украине и самые популярные товары

Итоги Всемирного дня шопинга: рост продаж в 11 раз в Украине и самые популярные товары Впереди ещё черная пятница и новогодние праздники. И успех массовых распродаж можно повторить....

14 01 2024 3:28:10

AMP Google: что нужно знать об ускоренных мобильных страницах

Обновление от Google, запущенный в октябре 2015 года. Это просто веб-страницы, но в их основе находится AMP HTML, формат для максимального ускорения загрузки на телефонах...

13 01 2024 8:24:17

7 фобий SMM-специалиста

Осторожно: очень страшно. Про теневой бан, гифки, цену клика, рекламный бюджет, ответы подписчикам, ошибки, наличие интернета подробно и в драматических деталях. Читайте в статье!...

12 01 2024 12:18:30

Как Netpeak продвигает бизнес-страницы на OLX — вторая часть

Как Netpeak продвигает бизнес-страницы на OLX — вторая часть Как мы продвигали бизнес-страницы OLX с помощью рекламы в Facebook, TikTok и Viber....

11 01 2024 1:12:31

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

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

10 01 2024 0:51:54

Форма подписки на сайте: виды и примеры форм сбора email-адресов

Форма подписки на сайте: виды и примеры форм сбора email-адресов Какими бывают формы подписки и как их используют бренды...

09 01 2024 18:29:59

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