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



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

Как не платить за клики без конверсий?

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

28 11 2022 7:19:33

Контекстная реклама для интернет-магазина принтов на одежде в Украине — увеличение дохода на 130%

Контекстная реклама для интернет-магазина принтов на одежде в Украине — увеличение дохода на 130% История для заказчиков, которые самостоятельно запускают рекламу...

27 11 2022 1:34:52

Восемь советов успешного запуска рекламной кампании в myTarget

Восемь советов успешного запуска рекламной кампании в myTarget Делимся фишками, которые облегчат работу как новичкам, так и специалистам....

26 11 2022 3:12:17

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

Как арбитражник использует редирект в контекстной рекламе Чтобы перенаправить рекламу не на свой домен, арбитражники используют редирект в Яндексе при работе с партнерскими ссылками...

25 11 2022 2:52:40

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

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

24 11 2022 3:16:54

Отчеты Google ***ytics — подробное руководство с объяснениями

Отчеты Google ***ytics — подробное руководство с объяснениями То, чего нет в справке — подробный обзор отчетов Google ***ytics: в режиме реального времени, по аудитории, источникам трафика, поведению, конверсии. Узнать больше!...

23 11 2022 13:10:32

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

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

22 11 2022 0:29:31

Google Apps Script: полезные функции и фишки для SEO (часть первая)

Google Apps Script: полезные функции и фишки для SEO (часть первая) Как автоматизировать рутину в Google Таблицах с помощью Google Apps Script...

21 11 2022 4:27:27

Как связать Twitter, Google Buzz, Facebook и Vkontakte.ru

Как связать Twitter, Google Buzz, Facebook и Vkontakte.ru Как сделать так, чтобы статусы автоматически трaнcлировались в Twitter...

20 11 2022 23:13:50

Линкбилдинг для элитной клиники в США: плюс 528% к количеству звонков за два года

Линкбилдинг для элитной клиники в США: плюс 528% к количеству звонков за два года Адаптивный линкбилдинг: будьте полезны людям, а не поисковикам....

18 11 2022 17:42:57

Как связать Microsoft Power BI и Google BigQuery

Как связать Microsoft Power BI и Google BigQuery Как визуализировать данные Google BigQuery в Power BI? Пошаговая инструкция от руководителя отдела веб-аналитики Netpeak Алексея Селезнева...

17 11 2022 17:17:25

Как B2B-стартап с помощью партнерской программы увеличил доход на 1983% за 6 месяцев

Как B2B-стартап с помощью партнерской программы увеличил доход на 1983% за 6 месяцев Создание успешного стартапа в нише телемедицины. Без дополнительных трат увеличил за 6 месяцев доход на 1983%, а клиентскую базу — более чем на 1000%....

16 11 2022 23:36:10

Нестандартные форматы баннеров в Google Marketing Platform

Нестандартные форматы баннеров в Google Marketing Platform Краткий обзор динамических мультимедийных объявлений...

15 11 2022 18:39:18

Как редизайн повысил доход от SEO — кейс по юзабилити

Как редизайн повысил доход от SEO — кейс по юзабилити Считаем SEO-эффект от нового дизайна сайта и работы над usability...

14 11 2022 1:47:35

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

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

13 11 2022 2:52:50

Как динамическая подмена заголовка влияет на конверсии

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

12 11 2022 13:33:59

Почему пользователи удаляют ваше приложение — обзор инструментов для анализа Uninstall Rate

Почему пользователи удаляют ваше приложение — обзор инструментов для анализа Uninstall Rate Иногда удержать пользователя сложнее, чем мотивировать загрузить приложение. Семь инструментов для анализа Uninstall Rate....

11 11 2022 19:19:49

ТОП-11 бесплатных курсов от Netpeak

ТОП-11 бесплатных курсов от Netpeak Уроки, написанные понятным и доступным языком экспертами по контекстной рекламе, поисковому продвижению, SMM....

10 11 2022 3:30:21

Как руководителю построить сильную комaнду и не сойти с ума

Как руководителю построить сильную комaнду и не сойти с ума Есть 3 качества грамотного руководителя: самоорганизованность, скорость. четкость. А еще — уйма фишек организации рабочих процессов, которые применяют в Netpeak. Узнать!...

09 11 2022 4:43:10

Как получить контакты клиентов в Facebook с помощью чат-бота ManyChat

Инструкция по интеграции рекламной кампании с чат-ботом...

08 11 2022 23:58:23

Email-маркетинг для интернет-магазина — как настроить, чтобы получить от 7 до 15% общего дохода

Email-маркетинг для интернет-магазина — как настроить, чтобы получить от 7 до 15% общего дохода Email-маркетинг увеличивает частоту транзакций. Показываем как это происходит и за счет чего. Делимся кейсом email-маркетинга для книжного интернет-магазина. Читать дальше....

07 11 2022 3:14:11

Как настроить динамические объявления в Яндекс.Директ

Объясняем по пунктам, как создать и правильно настроить DSA c таргетингом на фид и содержание сайта...

06 11 2022 17:50:15

Визуализация данных с помощью DataDeck

Визуализация данных с помощью DataDeck Краш-тест сервиса визуализации данных: выбираем задачу, источники, создаём отчет с помощью DataDeck. Бонус в конце — лаконичные списки преимуществ и недостатков этого инструмента и приятный подарок для дочитавших...

05 11 2022 9:35:13

Инсталлы по цене пирожка — кейс Apple Search Ads для приложения OLX Украина

Инсталлы по цене пирожка — кейс Apple Search Ads для приложения OLX Украина Как с помощью рекламы в Apple Search Ads получить дешевые установки и привлечь релевантных пользователей среди владельцев айфонов...

04 11 2022 10:35:21

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

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

02 11 2022 21:51:29

Влияние ссылок из социалок на ранжирование в поисковиках

Влияние ссылок из социалок на ранжирование в поисковиках Выдержка из интервью Дэнни Салливаном с представителями компаний Google и Bing...

01 11 2022 16:23:44

Реклама медицинских услуг: требования и ограничения для контекстной рекламы

Реклама медицинских услуг: требования и ограничения для контекстной рекламы Если ваша фирма работает на предоставление услуг в медицине, следует учесть требования рекламных систем в интернете, чтобы объявления в с первого раза прошли модерацию...

31 10 2022 6:23:11

О рекламе в Telegram — что пошло не так

О рекламе в Telegram — что пошло не так Если вы автор телеграм-канала, то стоит задуматься об альтернативных контент-платформах. Мнение...

30 10 2022 12:40:25

Как определить ключевую метрику LTV перед запуском Apple Search Ads

Как определить ключевую метрику LTV перед запуском Apple Search Ads Расчет прогноза по LTV позволит более точно задать параметры рекламной кампании в Apple Search Ads на начальном этапе. Как это делают в RadASO, читайте в статье....

29 10 2022 16:56:29

13 фишек маркетинга и продвижения проектов за рубежом — круглый стол 8P 2017

13 фишек маркетинга и продвижения проектов за рубежом — круглый стол 8P 2017 «Нет, нам нужна раскрутка и точка!» Список маркетинговых пpaктически применимых фишек....

28 10 2022 20:23:34

Сколько стоил клик в Google Ads в первом квартале 2017

Сколько стоил клик в Google Ads в первом квартале 2017 Анализ цены за клик в 25 тематиках и 852 городах Украины, России, Казахстана, Болгарии...

27 10 2022 23:19:21

10 идей продвижения медицинских услуг — инсайты конференции MeDiConf

10 идей продвижения медицинских услуг — инсайты конференции MeDiConf Кейсы, фишки и советы, опыт крупных брендов, маркетологов....

26 10 2022 12:20:55

RFM-анализ: три параметра для сверхточной сегментации базы email-рассылок

RFM-анализ: три параметра для сверхточной сегментации базы email-рассылок RFM — это аббревиатура слов Recency, Frequency, Money — новизна, частота, деньги. То есть считаем, как давно клиент купил товар в последний раз, сколько всего покупок он сделал и сколько денег принес нам за все время заказов....

25 10 2022 23:53:52

15 фишек контекстной рекламы — итоги круглого стола 8P 2019

Работающие способы повысить эффективность рекламных кампаний...

24 10 2022 18:16:57

Деcять неочевидных и пpaктически применимых PPC-фишек — круглый стол 8P 2018

Деcять неочевидных и пpaктически применимых PPC-фишек — круглый стол 8P 2018 Проверенные лайфхаки по платному трафику от спикеров и участников конференции 8P 2018...

23 10 2022 3:47:26

8 секретов крутых заголовков для 1000 репостов в соцсетях

8 секретов крутых заголовков для 1000 репостов в соцсетях Придумать цепляющие заголовки для 1000 репостов в соцсетях — что можно узнать в результате анализа миллиона заголовков в блогах....

22 10 2022 16:40:29

Прогнозируем поисковую активность в Яндексе с помощью Wordstat и Google Таблиц

Прогнозируем поисковую активность в Яндексе с помощью Wordstat и Google Таблиц Аналитик Алексей Селезнев описал простой алогритм прогнозирования поисковой активности пользователей в Яндексе....

21 10 2022 22:23:55

Как отслеживать клики по телефонным номерам

Как отслеживать клики по телефонным номерам Быстрый и бесплатный способ настройки целей через Google Tag Manager....

20 10 2022 10:34:41

Сeкc и эpoтика, магия, тренер-олень, и даже ребус! Апрельская реклама с блоком 18+

Чем шокировала, радовала и удивляла реклама в социальных сетях и контекстная в Google в апреле 2021 года...

19 10 2022 8:57:30

За авторку замолвите слово. Как и зачем использовать феминитивы

За авторку замолвите слово. Как и зачем использовать феминитивы Прежде чем использовать феминитивы в коммуникации со своими клиентами и сотрудниками, убедитесь, что им это нужно и важно. Впрочем, ждите негатива при любом раскладе. Что с ним делать? Рассказываем....

18 10 2022 6:20:43

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

Клубная культура Netpeak: что такое Netpeak Cluster и как он поможет развивать малый и средний бизнес Участники бизнес-клуба netpeak получают бесплатные консультации по вопросам ведения контекстной рекламы в Google Ads...

17 10 2022 17:54:36

SEO для магазина лакокрасочных и строительных материалов — как мы увеличили объем бесплатного трафика на 463%

SEO для магазина лакокрасочных и строительных материалов — как мы увеличили объем бесплатного трафика на 463% Эта история о том, как за два года комплексный подход к поисковому продвижению (SEO на этапе разработке сайта и дальнейшие действия по оптимизации) помог увеличить рост бесплатного трафика на 463% или Что делать, если SEO не приносит результаты сразу...

16 10 2022 15:35:51

Как показать пользователю статистику Google ***ytics, не открывая доступ? Мануал

Как показать пользователю статистику Google ***ytics, не открывая доступ? Мануал Вам тоже нужно предоставлять отчеты о работе рекламной кампании, посещение сайтов? Держите три примера работы с Google ***ytics и понятных отчета по ним, которые можно продемонстрировать, не открывая доступ к аккаунту....

15 10 2022 1:59:46

Работа с автоматическими типами кампаний на Facebook

Работа с автоматическими типами кампаний на Facebook Как вести рекламные кампании и что делать на разных этапах настройки. Делимся опытом: примерами, кейсами и рекомендациями. Узнать больше и настроить свои РК, как боженька!...

14 10 2022 0:22:47

Как создать рекламную видеозаставку с помощью Bumper Machine

Как создать рекламную видеозаставку с помощью Bumper Machine Создание даже короткого ролика может стоить дорого. Поэтому можно использовать бесплатный инструмент Bumper Machine от Google....

13 10 2022 21:50:32

Функции вычисляемых полей Google Data Studio

Всё, что вы хотели знать о функциях вычисляемых полей, но боялись спросить....

12 10 2022 8:39:48

Как быстро проверить индексацию сайта в Google и Яндекс

Как быстро проверить индексацию сайта в Google и Яндекс Быстрая индексация: как оперативно узнать, попала ли важная для вас страница в поисковые системы Google и Яндекс....

11 10 2022 12:54:36

Сколько стоил клик в Google Ads в Казахстане во втором квартале 2020 года — исследование Netpeak

Сколько стоил клик в Google Ads в Казахстане во втором квартале 2020 года — исследование Netpeak Зная стоимость клика в вашей тематике или регионе, коэффициент конверсии на сайте, вы можете оценить объем необходимых в рекламу инвестиций и прогнозировать стоимость конверсии. Узнать больше!...

10 10 2022 7:24:14

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