Как находить тексты похожие по смыслу? Какие есть алгоритмы для поиска текстов одной тематики? – Вопросы регулярно возникающие на различных программистских форумах. Сегодня я расскажу об одном из подходов, которым активно пользуются поисковые гиганты и который звучит чем-то вроде мантры для SEO aka поисковых оптимизаторов. Этот подход называет латентно-семантический анализ (LSA), он же латентно-семантическое индексирование (LSI)
Предположим, перед вами стоит задача написать алгоритм, который сможет отличать новости о звездах эстрады от новостей по экономике. Первое, что приходит в голову, это выбрать слова которые встречаются исключительно в статьях каждого вида и использовать их для классификации. Очевидная проблема такого подхода: как перечислить все возможные слова и что делать в случае когда в статье есть слова из нескольких классов. Дополнительную сложность представляют омонимы. Т.е. слова имеющие множество значений. Например, слово «банки» в одном контексте может означать стеклянные сосуды а в другом контексте это могут быть финансовые институты.
Латентно-семантический анализ отображает документы и отдельные слова в так называемое «семантическое пространство», в котором и производятся все дальнейшие сравнения. При этом делаются следующие предположения:
- Документы это просто набор слов. Порядок слов в документах игнорируется. Важно только то, сколько раз то или иное слово встречается в документе.
- Семантическое значение документа определяется набором слов, которые как правило идут вместе. Например, в биржевых сводках, часто встречаются слова: «фонд», «акция», «доллар»
- Каждое слово имеет единственное значение. Это, безусловно, сильное упрощение, но именно оно делает проблему разрешимой.
Пример
Для примера я выбрал несколько заголовков с различных новостей. Они выбраны не совсем случайно, дело в том, что для случайной выборки потребовался бы очень большой объем данных, что сильно затруднило бы дальнейшее изложение. Итак, было выбрано несколько заголовков.
Далее была произведена операция стемминга. Она не является обязательной, некоторые источники утверждают, что хорошие результаты получаются и без нее. И действительно, если набор текстов достаточно большой, то этот шаг можно опустить. Если тексты на английском языке, то этот шаг тоже можно проигнорировать, в силу того, что количество вариаций той или иной словоформы в английском языке существенно меньше чем в русском. В нашем же случае, пропускать этот шаг не стоит т.к. это приведет к существенной деградации результатов. Для стемминга я пользовался алгоритмом Портера.
Дальше были исключены слова встречающиеся в единственном экземпляре. Это тоже необязательный шаг, он не влияет на конечный результат, но сильно упрощает математические вычисления. В итоге у нас остались, так называемые, индексируемые слова, они выделены жирным шрифтом:
Латентно семантический анализ
На первом шаге требуется составить частотную матрицу индексируемых слов. В этой матрице строки соответствуют индексированным словам, а столбцы — документам. В каждой ячейке матрицы указано какое количество раз слово встречается в соответствующем документе.
Следующим шагом мы проводим сингулярное разложение полученной матрицы. Сингулярное разложение это математическая операция раскладывающая матрицу на три составляющих. Т.е. исходную матрицу M мы представляем в виде:
M = U*W*Vt
где U и Vt – ортогональные матрицы, а W – диагональная матрица. Причем диагональные элементы матрицы W упорядочены в порядке убывания. Диагональные элементы матрицы W называются сингулярными числами.
Прелесть сингулярного разложения состоит в том, что оно выделяет ключевые составляющие матрицы, позволяя игнорировать шумы. Согласно простым правилам произведения матриц, видно, что столбцы и строки соответствующие меньшим сингулярным значениям дают наименьший вклад в итоговое произведение. Например, мы можем отбросить последние столбцы матрицы U и последние строки матрицы V^t, оставив только первые 2. Важно, что при этом гарантируется, оптимальность полученного произведения. Разложение такого вида называют двумерным сингулярным разложением:
Давайте теперь отметим на графике точки соответствующие отдельным текстам и словам, получится такая занятная картинка:
РЕКЛАМНЫЙ БЛОК
[ Хотите знать больше о частной разведке? Регистрируйтесь и общайтесь на интернет-форуме it2b-forum.ru ]
Из данного графика видно, что статьи образуют три независимые группы, первая группа статей располагается рядом со словом «wikileaks», и действительно, если мы посмотрим названия этих статей становится понятно, что они имеют отношение к wikileaks. Другая группа статей образуется вокруг слова «премия», и действительно в них идет обсуждение нобелевской премии.
На практике, конечно, количество групп будет намного больше, пространство будет не двумерным а многомерным, но сама идея остается той же. Мы можем определять местоположения слов и статей в нашем пространстве и использовать эту информацию для, например, определения тематики статьи.
Улучшения алгоритма
Легко заметить что подавляющее число ячеек частотной матрицы индексируемых слов, созданной на первом шаге, содержат нули. Матрица сильно разрежена и это свойство может быть использовано для улучшения производительности и потребления памяти при создании более сложной реализации.
В нашем случае тексты были примерно одной и той же длины, в реальных ситуациях частотную матрицу следует нормализовать. Стандартный способ нормализации матрицы TF-IDF
Мы использовали двухмерную декомпозицию SVD-2, в реальных примерах, размерность может составлять несколько сотен и больше. Выбор размерности определяется конкретной задачей, но общее правило таково: чем меньше размерность тем меньше семантических групп вы сможете обнаружить, чем больше размерность, тем большее влияние шумов.
Замечания
Для написания статьи использовалась Java-библиотека для работы с матрицами Jama. Кроме того, функция SVD реализована в известных математических пакетах вроде Mathcad, существуют библиотеки для Python и C++.
Автор: Sergey Edunov
Источник: http://www.habrahabr.ru
Комментарий Елены Лариной
Статья вызвала довольно оживленное обсуждение на ХабраХабре и получила одобрительную оценку. Автор отражает принятый у большинства разработчиков подобных систем подход. Если говорить совсем коротко, он базируется на попытках исчислить семантику. Более 30 лет назад знаменитый советский математик А.Н.Колмогоров усомнился в возможности исчисления значений. Его соратник В.В.Налимов в своих последующих исследованиях по природе языка доказал принципиальную ограниченность такого подхода и наметил совершенно другие пути.
С развитием Интернета, тем не менее, числовой подход и оцифровывание терминов приобрели особое значение в связи с алгоритмами поисковых систем, базирующихся на индексировании. Собственно, разработка разнообразных библиотек, методов оцифровки и индексирования и породила сегодняшние могучие поисковики.
Подход, который старается развить автор публикации, подробно описан в блестящей книге К.Манинга, П.Рагхавана и Х. Щютце «Введение в информационный поиск», в гл.18. Книга в Штатах вышла в конце 2008 года, у нас была издана летом маленьким тиражом и разошлась буквально за неделю. В первом квартале в издательстве «Вильямс» выйдет второй тираж. Айтишники считают ее лучшей работой последнего времени в этой области.
Параллельно с означенным выше подходом развивается принципиально иной подход, часто называемый разработками по семантическому вебу. (Правда, различные группы понимают под семантическим вебом совершенно разные вещи.) ИМХО на значительную часть этих работ, кажется, наложили лапу люди из «Хрустального дворца» и Google. Об этом свидетельствует прекращение публикаций у нескольких наиболее продвинутых разработчиков в последние пару-тройку лет. Однако, как и в случае с Linux, несколько сообществ разработчиков инициативно разрабатывают элементы семантического веба, начиная от онтологий и кончая фильтрацией информационного шума, начиная от попыток неиндексационного подхода к определению значений, кончая алгоритмами, использующими новые языки программирования. Работы ведутся в режиме open source. Активно участвуют и люди из России и Украины. Конечно, у первых немерено ресурсов, но и очень много бюрократии, а также миллиардов, вложенных в готовые технологии. У вторых денег совсем мало, но зато у них свобода, мозги и честолюбие.
