Латентно-семантический анализ. Как вы находите тексты с похожим смыслом? Каковы алгоритмы поиска текстов с одинаковой тематикой? — Такие вопросы регулярно возникают на различных форумах для программистов. Сегодня я расскажу об одном подходе, который активно используется поисковыми гигантами и который звучит как мантра для SEO, или оптимизаторов поисковых систем. Этот подход называется латентно-семантическим анализом (LSA), или латентно-семантическим индексированием (LSI).
Предположим, перед вами стоит задача написать алгоритм, который сможет отличить новости о поп-звездах от новостей об экономике. Первое, что приходит в голову, — отобрать слова, которые встречаются только в статьях каждого типа, и использовать их для классификации. Очевидная проблема при таком подходе — как перечислить все возможные слова и что делать, если в статье встречаются слова из нескольких классов. Дополнительную трудность представляют омонимы. То есть, слова с несколькими значениями. Например, слово "банки" может означать стеклянную посуду в одном контексте и финансовые учреждения в другом.
Латентно-семантический анализ отображает документы и отдельные слова в так называемое семантическое пространство, в котором проводятся все дальнейшие сравнения. При этом делаются следующие допущения:
1) Документы — это просто набор слов. Порядок слов в документах не учитывается. Важно лишь то, сколько раз слово встречается в документе.
2) Семантический смысл документа определяется набором слов, которые обычно идут вместе. Например, в отчетах о фондовом рынке часто встречаются слова "фонд", "акции", "доллар".
3) Каждое слово имеет одно значение. Это, конечно, сильное упрощение, но именно оно делает проблему разрешимой.
Пример
Для примера я выбрал несколько заголовков из различных новостей. Они не выбираются полностью наугад, идея заключается в том, что случайная выборка потребовала бы очень большого количества данных, что сильно затруднило бы дальнейшую работу. Поэтому было выбрано несколько заголовков.
Первым делом из этих заголовков были удалены так называемые знаки "стоп". Это слова, которые встречаются в любом тексте и не используются взаимозаменяемо, прежде всего все союзы, частицы, предлоги и многие другие слова. Полный список используемых знаков остановки смотрите в моей предыдущей статье о знаках остановки
Затем была проведена операция стеблирования. Она не является обязательной; некоторые источники утверждают, что хорошие результаты достигаются и без нее. Действительно, если коллекция текстов достаточно велика, этот шаг можно пропустить. Если тексты на английском языке, этот шаг также можно пропустить, так как количество разновидностей словоформы в английском языке гораздо меньше, чем в русском. В нашем случае пропуск этого этапа нецелесообразен, так как это приведет к значительному ухудшению результатов. Для стеблирования мы использовали алгоритм Портера.
Затем мы исключили слова, которые встречаются только один раз. Это также необязательный шаг, он не влияет на конечный результат, но значительно упрощает математический расчет. Нам остались так называемые индексируемые слова, которые выделены жирным шрифтом:
1. британской полиции известно местонахождение основателя WikiLeaks.
2. в американском суде начинается процесс против российского спамера
3. церемония вручения Нобелевской премии мира, которую бойкотировали 19 стран
4. основатель Wikileaks Джулиан Ассанж арестован в Великобритании
5 Украина игнорирует церемонию вручения Нобелевской премии мира
6. шведский суд отказался рассматривать апелляцию основателя Wikileaks
7. НАТО и США разрабатывают планы по защите Балтии от России
8. британская полиция нашла основателя Wikileaks, но не арестовала его
9. Нобелевские премии будут вручены сегодня в Стокгольме и Осло
Латентно семантический анализ
Первым шагом является создание матрицы частот индексированных слов. В этой матрице строки соответствуют индексированным словам, а столбцы — документам. Каждая ячейка матрицы показывает, сколько раз слово встречается в соответствующем документе.
На следующем этапе мы выполняем сингулярное разложение полученной матрицы. Сингулярное разложение — это математическая операция, которая разлагает матрицу на три элемента. То есть, мы представляем исходную матрицу M в виде:
Где U и V t — ортогональные матрицы, а W — диагональная матрица. А диагональные элементы матрицы W упорядочены по убыванию. Диагональные элементы матрицы W называются сингулярностями.
Латентно-семантический анализ. TV #68
Прелесть сингулярного разложения в том, что оно выделяет ключевые компоненты матрицы, позволяя нам игнорировать шум. Следуя простым правилам произведения матриц, мы видим, что столбцы и строки, соответствующие меньшим сингулярным значениям, вносят наименьший вклад в конечный продукт. Например, мы можем отбросить последние столбцы матрицы U и последние строки матрицы V^t, оставив только первые 2. Важно, что оптимальность полученного произведения гарантирована. Такое распределение называется двумерным сингулярным распределением:
Теперь отметим точки на графике, соответствующие каждому тексту и слову, получим красивую картинку:
Векторные представления слов. TF-IDF. Латентно-семантический анализ. Коллокации
Из этого графика видно, что статьи образуют три независимые группы. Первая группа статей связана со словом "wikileaks", и действительно, если вы посмотрите на названия этих статей, то увидите, что они связаны с wikileaks. Другая группа статей формируется вокруг слова "премия", и действительно, здесь обсуждается Нобелевская премия.
На практике, конечно, количество групп будет гораздо больше, а пространство будет многомерным, а не двумерным, но идея остается той же. Мы можем определить расположение слов и статей в нашем пространстве и использовать эту информацию, например, для определения темы статьи.
Улучшения алгоритма
Легко заметить, что подавляющее число ячеек в матрице частот индексированных слов, созданной на первом этапе, содержат нули. Матрица является сильно разреженной, и это свойство может быть использовано для повышения производительности и потребления памяти при создании более сложной реализации.
В нашем случае тексты были примерно одинаковой длины, в реальных ситуациях матрица частот должна быть нормализована. Стандартный способ нормализации матрицы TF-IDF
Мы использовали двумерное разложение SVD-2; в реальных примерах размерность может составлять несколько сотен и более. Выбор размерности зависит от конкретной задачи, но общее правило таково: чем ниже размерность, тем меньше семантических групп можно обнаружить; чем выше размерность, тем больше влияние шума.
Замечания
Для написания данной статьи использовалась библиотека Java для работы с матрицами. Кроме того, функция SVD реализована в известных математических пакетах, таких как Mathcad, а также существуют библиотеки для Python и C++.
