Алгоритм 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:
- Невозможно получить тематик больше чем документов/слов.
- Семантическое значение документа определяется набором слов, которые, как правило, идут вместе.
- Документы рассматриваются как просто наборы слов. Порядок слов в документах игнорируется. Важно только то, сколько раз то или иное слово встречается в документе.
- Каждое слово имеет единственное значение.
- Недостаток LSA — предположение о том, что карта слов в документах не имеет вид нормального распределения. С этой проблемой справляются другие модификации метода (вероятностный LSA и LDA).
LSA включает в себя следующие этапы:
- Удаление стоп-слов, стемминг или лемматизация слов в документах;
- Исключение слов, встречающихся в единственном экземпляре;
- Построение матрицы слово-документ (бинарную есть/нет слова, число вхождений или tf-idf) ;
- Разложение матрицы методом SVD (A = U * V * WT) ;
- Выделение строк матрицы 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тва, и как в нем будут представлены слова (красным цветом), запросы (зеленым) и документы (синим). Напомню, что все слова в документах и запросах прошли процедуру лемматизации или стемминга.
Видно, что тема \"компьютер\" хорошо отделилась от двух других. А вот \"спорт\" и \"авто\" довольно близки друг другу. Для каждой темы проявились свои ключевые слова. Зеленым на рисунке изображен запрос \"автомобил колес\". Его релевантность к документам имеет следующий вид:
- \\\'sport.txt\\\' - 0.99990845
- \\\'auto.txt\\\' - 0.99987185
- \\\'computer.txt\\\' - 0.031289458
Из-за близости тем \"спорт\" и \"авто\" довольно сложно точно определить, к какой теме он принадлежит. Но точно не к \"компьютерам\". Если в системе, обученной на этих документах, попытаться определить релевантность к образовавшимся темам слова \"рынок\", то в ответ мы получим 0 (т.к. это слово в документах не встречалось ни разу). Добавим в систему документ по теме \"финансы\". Будем снова искать слово \"рынок\".
Получим следующую картинку:
Релевантность к темам будет такой:
- \\\'finance.txt\\\' - 0.99948204
- \\\'sport.txt\\\' - 0.97155833
- \\\'auto.txt\\\' - 0.23889101
- \\\'computer.txt\\\' - -0.24506855
Итак подведем итог:
- LSA позволяет снизить размерность данных - не нужно хранить всю матрицу слово-документ, достаточно только сравнительно небольшого набора числовых значений для описания каждого слова и документа.
- Получаем семантическое представление слов и документов - это позволяет находить неочевидные связи между словами и документами.
- Из минусов - очень большая вычислительная сложность метода.
Комментарии:
У каждого сайта в топе есть страница, о существовании которой знают только роботы и... SEO-специалисты. Это robots.txt или индексный файл....
19 07 2025 16:14:42
SEOmoz создал систему, которая определяет релевантность страницы поисковому запросу....
18 07 2025 9:35:15
Как отключить блокировку API запрещенных сервисов в скриптах R и продолжать использовать пакеты ryandexdirect, rvkstat, rmytarget, Google Sheets и BigQuery...
17 07 2025 19:52:53
Новый способ автоматизации процессов при настройке аналитики больших объемов данных....
16 07 2025 15:41:59
Зачем маркетологи и аналитики обращаются к языку программирования R в повседневной работе нужно и какая польза от программирования на R в интернет-маркетинге в интервью Алексея Селезнева...
15 07 2025 6:21:47
Очередной красивый пост о продвижении платформы email и sms-рассылок — UniSender...
14 07 2025 14:19:43
Насколько классно продается женская одежда в интернете....
13 07 2025 10:59:36
Подкаст — это аудиозапись в повествовательном, музыкальном, юмористическом формате. Создается с целью рекламы, увеличения потока посетителей на сайт и роста почитателей определенного продукта...
12 07 2025 22:59:50
Реклама Facebook для вовлечения пользователей помогает привлечь внимание к приложению и удержать пользователей в условиях перенасыщенного рынка....
11 07 2025 19:42:37
При работе с рекламным аккаунтом приходится вносить много однотипных изменений. Рассказываем, как сделать это быстро....
10 07 2025 6:28:54
Специалисты дропшиппинг-платформы делятся данными по самым продаваемым товарам на крупных онлайн-площадках. Информация для масштабирования бизнеса. Читать!...
09 07 2025 19:29:39
Как зарегистрироваться в приложении Facebook Business Manager и грамотно сделать и настроить аккаунт...
08 07 2025 14:33:31
Что делать, если вы столкнулись со спамом в отчетах Google ***ytics? Значит ли это, что кто-то имеет доступ к вашему аккаунту, или что кто-то специально влияет на данные сайта в GA? Как они это делают? И как исключить подобные данные из отчетов?...
07 07 2025 0:40:44
Короткая история про одного из руководителей корпорации «Kimberly Clark». Альтернативная Википедия для тех, кто любит сторителлинг. Читать дальше!...
06 07 2025 23:25:52
Полезные советы для тех, кто делает контекст своими ручками :)...
05 07 2025 13:23:33
Семнадцать крутых шагов к эффективному бренду Заг — это авторский неологизм от слова зигзаг (англ. zigzag). Он подразумевает движение в другом направлении....
04 07 2025 21:22:21
UTM-метки позволяют эффективно отслеживать источники трафика. Но составлять их нужно правильно. Как именно, давайте разбираться....
03 07 2025 1:11:34
Почему в рекламе недвижимости стоит запускать динамический ремаркетинг...
02 07 2025 9:32:25
В третьем квартале Netpeak внедрил множество крутых улучшений. Мы подробно расскажем о семи самых интересных новостях....
01 07 2025 1:36:11
Сколько страниц на самом деле показывает и может перевести поисковик Google?...
30 06 2025 5:47:23
Что такое ускоренные мобильные страницы и как их посмотреть в Google ***ytics...
29 06 2025 1:16:28
Google Penguin официально стал частью основного алгоритма поисковика. Как обезопасить свой бизнес и встретить апдейт алгоритма Google во всеоружии? О трафике, анкорах, бэклинках, ссылках и ссылочной массе, трастовости и постоянном мониторинге, с комментариями специалистов...
28 06 2025 13:50:32
Netpeak Checker – это мультифункциональный инструмент для массового анализа и сравнения сайтов, который помогает выполнять самые разнообразные задачи в области интернет-маркетинга....
27 06 2025 21:11:28
СЕО of Augmented Pixels рассказал нам о принципах ведения бизнеса в Украине и США, о ненужности бизнес-планов и креативных питчей, а также о способе стать лучшим программистом...
26 06 2025 10:38:20
Рекламные кампании для брендинга, роста вовлечения пользователей, продаж, лояльности. Какой формат выбрать, чтобы получить необходимое целевое действие. Узнать!...
25 06 2025 12:48:56
Пример использования пакета google***yticsR от Марка Эдмондса...
24 06 2025 10:44:59
330 миллионов активных пользователей и 14 миллиардов просмотров в месяц. Хорошо бы там запускать рекламные кампании....
23 06 2025 20:51:23
All about internet mail. Примеры того, что стоит внедрить в рассылках почты онлайн....
22 06 2025 18:12:44
Предположим, что оптимизация в аккаунте похожа на реальный мир и рассмотрим несколько примеров :)...
21 06 2025 8:47:55
Бесплатные CMS помогают решить много задач без привлечения программиста или самостоятельного изучения кодов. Но у таких движков есть свои недостатки. Узнать больше!...
20 06 2025 14:14:36
Если у вас есть продукт, о котором миру стоит узнать, книга Pitch perfect придется вам очень кстати....
19 06 2025 13:42:20
Низкочастотные, низкоконкурентные, Long Tail и другие термины, которые нужно знать и понимать....
18 06 2025 2:41:13
+ таблица с примерами использования каждой функции....
17 06 2025 18:19:37
Алгоритм технической подготовки IP-адреса к массовым рассылкам...
16 06 2025 19:49:36
О списках исключенных мест размещения будет интересно узнать тем, кто хочет облегчить себе работу с контекстно-медийными сетями....
15 06 2025 18:30:51
Еще организовали новую онлайн-конференцию, запустили опрос онлайн-покупателей, создали SEO-услугу для крупного бизнеса, рассказали, как вести В2С и В2В аккаунты в Instagram и ввели консультации SMM-специалистов....
14 06 2025 7:18:26
«Случайный» посетитель потому, что может уйти (не сделав покупку) и не вернуться, не стать клиентом. Пуш-уведомления позволяют посетителю сразу стать подписчиком: ему предлагают подписаться на рассылку. Как это использовать? Читайте!...
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
В мае прошлого года Google анонсировал выход нового Core Web Vitals. Что это и как будет работать рассмотрим в статье...
07 06 2025 0:46:17
Будь мобильным — заливай видео на Youtube с телефона...
06 06 2025 6:19:25
Пожар в дата-центре, неудачные обновления и то самое падение Facebook....
05 06 2025 19:35:27
Мы запустили еще один полезный инструмент: Netpeak Spider....
04 06 2025 17:23:49
На что обратить внимание при покупке интернет-ресурса, какие факторы влияют на цену и что помогает определить качество сайта? Ответы на все эти вопросы в статье. Читать!...
03 06 2025 18:40:44
10 заданий, которые заставят пошевелить мозгами и придумать нестандартные решения. Используйте их (видоизмените, адаптируйте) под свой продукт или услугу. Создайте крутую кампанию, креатив или предложите это своей комaнде....
02 06 2025 16:43:47
Четкая структура полноценного письма с примерами из рассылок крупных компаний: 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 ::