Алгоритм 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 позволяет снизить размерность данных - не нужно хранить всю матрицу слово-документ, достаточно только сравнительно небольшого набора числовых значений для описания каждого слова и документа.
- Получаем семантическое представление слов и документов - это позволяет находить неочевидные связи между словами и документами.
- Из минусов - очень большая вычислительная сложность метода.
Комментарии:
Идеи для интернет-маркетологов, как получить дополнительные каналы трафика и сделать заметным сниппет в поисковой выдаче....
19 03 2023 5:35:14
Новый тип рекламных кампаний, который помогает расширить целевую аудиторию. Потенциальных покупателей можно найти среди людей не знакомых с вашим брендом....
18 03 2023 8:18:38
Цели у личных сайтов могут быть разные, но в первую очередь они помогают рассказать историю о специалисте...
17 03 2023 21:14:58
Как вернуть клиентов с помощью реактивационных email-рассылок. Внутри идеи таких брендов: Bershka, Wildberries, LinguaLeo, Facebook, Mail.ru, Coub, BlaBlaCar, Repka.ua и другие. Узнайте принципы красивой реактивации!...
16 03 2023 22:41:25
Глоссарий глупых ошибок в аудите от топовых SEO-агентств...
15 03 2023 15:19:22
Нам удалось увеличить количество органических показов на 63% и установок на 25%....
14 03 2023 23:40:47
Офис Netpeak в Харькове официально открыт! В этом посте, вместо игры на фанфарах, мы на собственном примере рассмотрим, что нужно для создания регионального отделения в разгар кризиса....
13 03 2023 1:33:44
Итоги одной из наших первых онлайн рекламных кампаний в Play...
12 03 2023 20:14:25
Интервью с основателем школы английского языка Progress...
11 03 2023 11:47:39
История свидания двух ботов как иллюстрация развития искусственного интеллекта...
10 03 2023 5:39:51
О том, как работают, празднуют, танцуют и в какой корпоративной культуре живут сотрудники корпорации Google. Этот пост развеет кое-какие мифы....
09 03 2023 8:28:26
Как METRO Cash & Carry Украина нашла индивидуальный подход к 1 000 000 клиентов....
08 03 2023 18:38:57
История Affise от фаундера компании, рассказанная на SaaS Nation....
07 03 2023 19:20:29
Хасан Исламов о развитии Chocofamily, крупнейшего интернет-холдинга Казахстана....
06 03 2023 17:52:41
Какие фишки влияют на видимость сайтов? Советы по юзабилити от SEO-специалиста....
05 03 2023 2:35:37
Как увеличить количество транзакциий, сохранив прибыльность кампании в РСЯ?...
04 03 2023 16:31:46
Лучшие маркетинговые и бизнес-фишки от Давида Брауна (Weblium), Владислава Флакса (OWOX), Александра Галкина (Competera), Люси Литерадо (Reply.io), Вадима Нехая (Depositphotos), Валерия Грабко (PromoRepublic), Игоря Дебатура (Uploadcare), Руслана Савчишин...
03 03 2023 15:11:17
Предложение для крупных и средних бизнес-проектов по эффективному использованию больших бюджетов при запуске на новых рынках...
02 03 2023 2:28:41
Обычно SaaS-бизнесы начинают привлечение лидов с запуска рекламы на Facebook. Но наш опыт говорит о том, что это не самые подходящие каналы. Более высокие результаты можно получить на LinkedIn....
01 03 2023 1:37:55
Как найти индивидуальный подход к аудитории на каждом этапе воронки продаж? В этом вам поможет правильно составленная стратегия контекстной рекламы....
28 02 2023 2:32:23
Как владельцу стартапа пробиться сквозь сотни ежедневных сообщений, которые получает инвестор, создать эффективную цепочку писем и быть замеченным...
27 02 2023 15:35:30
Что нужно сделать, чтобы превью веб-страниц в социальных сетях стало магнитом для пользователей?...
26 02 2023 14:25:59
Как найти сетку сайтов конкурентов — рассказываем о популярных методах и секретных фишках. Бонус — инструкция по выявлению PBN конкурентов. Читать дальше!...
25 02 2023 17:35:34
Решение для поискового продвижения крупных проектов (от 300 000 страниц)....
24 02 2023 12:43:44
Я исследовал 23 миллиона кликов из Украины в Google Ads, Facebook, Директ и структурировал данные по 19 тематикам...
23 02 2023 14:34:59
Игровой формат отлично работает в email-рассылке. Но какой вид гeймификации интересен любой целевой аудитории? Давайте рассмотрим примеры....
22 02 2023 8:31:23
Отслеживаем пропущенные, анализируем входящие и делаем выводы о том, как организовать работу менеджеров....
21 02 2023 21:53:49
Подробно об оплате аккаунтов и налогообложении рекламы в Украине, России, Казахстане....
20 02 2023 4:40:37
Миллионы решили купить книгу гении и аутсайдеры на Amazon: удивительное исследование канадского журналиста...
19 02 2023 20:26:12
Делимся советами по оптимизации рассылок. Важны новые форматы писем, предварительное тестирование, смена тем письма, ярче CTA. Все это в сочетании с понятностью и искренностью не заставит ждать хороший CTR...
18 02 2023 0:59:43
На что обращает внимание система и менеджеры Google при проверке сайта и аккаунта....
17 02 2023 23:50:19
Почему встречаются низкие показатели переходов на сайты по всем источникам трафика? Нет рекламодателей, которые могут предложить пользователям те или иные товары и услуги....
16 02 2023 18:24:20
Как надолго завоевать доверие покупателя с помощью грамотного email-маркетинга? Примеры обращений к клиенту в рассылках, текст писем для привлечения и благодарности за покупку....
15 02 2023 15:12:31
Рассказываем в подробностях, что полезного сделал Netpeak для своих клиентов с января по апрель 2017 года...
14 02 2023 7:35:43
Что же такое эти authority и чем они лучше и полезнее, к примеру, чем Page Rank?...
13 02 2023 20:34:24
Как помешать фейковым 404 страницам испортить статистику вашего сайта?...
12 02 2023 9:28:42
11 02 2023 14:58:53
Изучаем на примере тестирования товарных кампаний в момент смены логотипа и ренейминга...
10 02 2023 14:19:25
Что делать, если денег нет, но трафик очень нужен: советы по раскрутке бренда в фейсбуке. В бесплатном продвижении главный ресурс — время: часы, дни, недели, месяцы, проведенные на площадке. Как их применить? Читайте!...
09 02 2023 4:51:36
Опыт стартапа Paperform для стартаперов, которые боятся начать из-за ограниченного бюджета и/или отсутствия знаний в маркетинге. Надеемся, эта история вдохновит предпринимателей и поможет меньше сомневаться на счет запуска без бюджета....
08 02 2023 17:10:46
Как настроить Google ***ytics и как открыть вход другому пользователю: подробный урок....
07 02 2023 11:42:54
Где найти лидера для своей инхаус-комaнды маркетологов...
06 02 2023 2:18:10
Полезные советы для тех, кто делает контекст своими ручками :)...
05 02 2023 3:45:40
5 важных навыков для новичков в PPC: как учиться, чтобы стать экспертом; секреты тайм-менеджмента, мотивации; тонкости оптимизации рабочего процесса. Узнать больше!...
04 02 2023 6:12:40
Чтобы и клиенту не стыдно было показать и свои ожидания не обмануть....
03 02 2023 8:21:49
Эта книга рекомендована к прочтению решительно всем :)...
02 02 2023 14:58:38
Читайте простой мануал о том, как перейти на Universal ***ytics и не поломать весь сбор данных...
01 02 2023 22:26:31
Сначала учитесь, а потом идите в бизнес и предпринимательство. Бизнес — это игра, в которую играют пару тысяч лет, и здесь не нужно придумывать велосипеды. Научитесь сначала просто ездить, потом уже будете думать про кастомы....
31 01 2023 23:55:53
Примеры странной, классной и непонятной рекламы в соцсетях из моей ленты за февраль 2021 года...
30 01 2023 19:33:34
Бета-версия помогает записывать действия пользователей на сайте и благодаря этому улучшать удобство использования сайта и в перспективе растить продажи. Узнать больше!...
29 01 2023 9:51:16
Еще:
понять и запомнить -1 :: понять и запомнить -2 :: понять и запомнить -3 :: понять и запомнить -4 :: понять и запомнить -5 :: понять и запомнить -6 :: понять и запомнить -7 ::