Алгоритм 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 позволяет снизить размерность данных - не нужно хранить всю матрицу слово-документ, достаточно только сравнительно небольшого набора числовых значений для описания каждого слова и документа.
- Получаем семантическое представление слов и документов - это позволяет находить неочевидные связи между словами и документами.
- Из минусов - очень большая вычислительная сложность метода.
Комментарии:
Регулярный мониторинг позиций необходим для отслеживания истории их изменений после внедрения новых ключевых слов и других работ над сайтом...
26 04 2024 5:37:46
Гайд по рекламе для SMM-, PPC-специалистов, блогеров и владельцев бизнеса...
25 04 2024 4:37:17
Автор книги о вирусном маркетинге «Заразительный. Психология сарафанного радио» Йона Бергер пришел к выводу, что у виральности всего шесть принципов....
24 04 2024 4:51:18
Изначально необходимо планировать продолжительное сотрудничество с агентством для достижения поставленных целей. В своей стратегии мы использовали сезонность, чтобы достичь максимальных результатов для клиента...
23 04 2024 0:20:40
Опыт сотрудника отдела маркетинга Netpeak. Дочке Маше — 10 лет, сыну Егору — почти 4 года. Мы по-прежнему не очень продуктивны в таких условиях, но все же накопили больше опыта, чем те люди, которые сейчас внезапно столкнулись с удаленной работой...
22 04 2024 20:40:38
Как рекламировать смартфоны в YouTube — советы крупному бизнесу по настройке и запуску эффективной рекламы. Важно: корректный анализ результатов. Узнайте как его сделать!...
21 04 2024 18:46:41
Сакральные знания о контекстной рекламе для экспертов и тех, кто с ними сотрудничает....
20 04 2024 17:47:40
Обновление от Google, запущенный в октябре 2015 года. Это просто веб-страницы, но в их основе находится AMP HTML, формат для максимального ускорения загрузки на телефонах...
19 04 2024 19:17:42
Как настроить работу удаленной комaнды сотрудников и успевать выполнить все задачи...
18 04 2024 12:14:44
Как понять, что проект нуждается в новых текстах и сделать читателя счастливым...
17 04 2024 21:19:53
Рекомендации и мнения экспертов по одной из самых противоречивых тем украинского интернет-прострaнcтва....
16 04 2024 10:58:38
Что же такое эти authority и чем они лучше и полезнее, к примеру, чем Page Rank?...
15 04 2024 21:36:11
Обзор новой версии краулера Netpeak Spider 3.0, которая включает в себя около 300 изменений: от супер-фич до небольших фиксов в юзабилити....
14 04 2024 8:37:12
Дэн Гридин, ненавистник холодных звонков и эксперт в области системного B2B маркетинга для сложных рынков, рассказал читателям блога о принципах работы на рынке во время шторма....
13 04 2024 10:21:47
Инструкция по интеграции рекламной кампании с чат-ботом...
12 04 2024 20:21:56
Если у интернет-магазина, форума да и любого другого сайта нет мобильной версии, почти 40 процентов пользователей будут искать другой ресурс. Как удержать их? Узнать!...
11 04 2024 20:45:55
Дмитрий Шахов, Алексей Чекушин и другие эксперты поделились своим опытом решения сложных вопросов SEO на примере больших проектов....
10 04 2024 1:19:31
Как заинтересовать инвесторов, сколько времени это займет, а также стратегии поиска....
09 04 2024 16:29:40
Шпаргалка по размерам креативов для всех, кто запускает рекламу в соцсетях...
08 04 2024 19:41:16
В семье Leo Burnett - 7750 человек из 84-х стран мира. В Украине всего - 90 творческих единиц....
07 04 2024 5:50:16
Продвижение казахстанского онлайн-издания, новостника informburo.kz....
06 04 2024 9:39:16
Информация для бизнесменов, интернет-маркетологов и всех, кто интересуется продвижением бизнеса в интернете....
05 04 2024 5:16:52
Руководство для всех, кто продает через Instagram: когда стоит воспользоваться рекламным кабинетом Facebook для настройки кампании в Instagram и как правильно запустить рекламу в Instagram через кабинет Facebook. Читайте дальше!...
04 04 2024 13:24:17
На что обращает внимание система и менеджеры Google при проверке сайта и аккаунта....
03 04 2024 5:33:59
Google внедрил новую возможность выделить объявление — автоматическое добавление часов работы. Давайте разберемся, как добавить эту полезную информацию в расширения объявлений...
02 04 2024 18:40:28
в поисках нового источника трафика расскажем о Pinterest — современной поисковой сети c акцентом на визуальном контенте...
01 04 2024 2:13:51
В этом году часть пользователей предпочла вернуться к привычным покупкам в оффлайн-магазинах....
31 03 2024 16:36:33
Услуга уровня элит-класса в конкурентной нише и не в самом простом для продвижения регионе. Рассказываем, как привели целевой трафик по минимальной цене. Узнать!...
30 03 2024 11:33:32
Инструкция по созданию изображений для сториз, email-рассылок и объявлений в соцсетях...
29 03 2024 18:31:55
Более строгие требования к таким ресурсам обуславливают свои подходы....
28 03 2024 6:12:50
Какие регионы и тематики наиболее выгодно продвигать в каждом из представленных рекламных сервисов, где наибольшая доля мобильного трафика, и другая полезная статистика....
27 03 2024 13:17:18
Идеи, кейсы и советы от экспертов. Читайте и находите что-то для продвижения своего бизнеса. Нетривиальные идеи от признанных экспертов-пpaктиков! Рекомендуем каждому, что развивает или планирует свой бизнес в интернете!...
26 03 2024 9:34:26
Несколько фишек Google Tag Manager, чтобы сделать продвинутые списки ремаркетинга....
25 03 2024 5:57:17
Пример пользовательских отчетов в Google ***ytics, созданных за 15 минут...
24 03 2024 2:55:23
2013, 2014, 2015 — годы, когда конференция 8p радовала все сео-сообщество СНГ. Прошла она и в 2016 году. Мы собрали лучшие советы интернет-магазинам от экспертов и участников круглого стола на конференции 8P 2016....
23 03 2024 2:32:37
Попасть в топ 3 — ваш предел мечтаний? Почему и когда это не принесет ожидаемых результатов, плюс другие не актуальные убеждения о PPC. Узнать больше!...
22 03 2024 10:13:11
Гифка — это зациклиненное видеоизображение, рисунок-ролик, крохотный фильм, без которого трудно представить современный сайт. Как быстро создавать гифки и получать профит....
21 03 2024 4:22:13
Полезный и интересный контент — это лучший крючок, который помогает привлечь новых клиентов на аграрном рынке и удержать их внимание....
20 03 2024 4:57:47
Если выполнить настройку не корректно, поисковик воспримет материалы как дубли контента....
19 03 2024 5:26:16
Четыре важных шага для новичка...
18 03 2024 22:28:35
Узнайте зарплату интернет-маркетологов с новым рейтингом от Serpstat....
17 03 2024 0:56:29
Алгоритм ссылочного ранжирования, который показывает ее значимость, в частности, для поисковиков. Важность показателя PageRank оспаривают, но до сих пор считают. Читать!...
16 03 2024 20:26:19
Идеи, достойные распространения. Какие доклады TED Talks повлияли на нетпиковцев....
15 03 2024 7:24:50
Пpaктическая информация о том, что и куда нужно постить....
14 03 2024 4:18:52
Продолжаем разговор о том, почему функция «Совмещение данных» в Google Data Studio может работать не так, как вы ожидаете....
13 03 2024 0:24:42
Экспорт/импорт с помощью Excel-файла или таблиц Google позволит скопировать и перенести кампании, группы объявлений и объявления в Facebook вместе с креативами, текстами, ссылками и utm-метками...
12 03 2024 20:56:16
Низкочастотные, низкоконкурентные, Long Tail и другие термины, которые нужно знать и понимать....
11 03 2024 1:18:12
Новости, доработки и обновления в услугах, блоге, Академии блога и Кластере....
10 03 2024 7:10:29
Об истории и значении поговорок и других фразеологических оборотов...
09 03 2024 9:35:51
Как быстро настроить DSA с помощью Netpeak Spider. Рассмотрим подробнее «Только URL из фида страниц». Этот таргетинг помогает точнее определить целевую аудиторию и привести ее на максимально релевантные страницы сайта (к примеру, на карточку товара)....
08 03 2024 10:18:12
Еще:
понять и запомнить -1 :: понять и запомнить -2 :: понять и запомнить -3 :: понять и запомнить -4 :: понять и запомнить -5 :: понять и запомнить -6 :: понять и запомнить -7 ::