Латентно семантический анализ текста



Латентно-семантический анализ: разбор на примере (часть1)

В публикации приведено пошаговое применение латентно-статисчитеского анализа и предпринята попытка оценить его эффективность для решения практических задач.

Данные для анализа — описание заявок на заключение государственных контрактов с официального сайта Госзакупок. На практике большие объемы данных, как правило, хранятся в базе данных. В описываемом примере используется бд postgresql.

1. Выявить группы (кластеры) ключевых слов, позволяющие .
2. Разбить документы по кластерам .

Определения

Документ — строка (набор слов, одно или несколько предложений), относящаяся к одной единице информации (описание одного государственного контракта)

Этап 0. Подготовка данных

На данном этапе, чтобы снизить объем обработываемой информации, и повысить скорость работы алгоритма, проводится предварительная обработка документов. Обработка проводится в соответствии с целями и заранее сформулированными экспертными гипотезами. Гипотезы формулируются с учетом спицифики и предметной области обрабатываемого массива документов.

Для описываемой задачи были выдвинуты следующие гипотезы:

• стоп слова (союзы, предлоги и т.д.) и часто употребимые слова (встречающиеся в большом количестве документов) не несут полезной информации, на этапе подготовки их необходимо исключить,
• слова, встречающиеся в массиве документов только один раз, также не являются информативными и тоже исключаются,
• документ состоит только из русских слов и имен собственных (торговая марка, город и т.д.), которые прописаны в соотвествующих словарях. Слова не включенные в эти словари исключаются. Это некоторое упрощение практической задачи, но на понимание алгоритма латентно-статисчитеского анализа оно не влияет
• документ описывает объект закупок и его характеристики. Объект закупки — имя существительное, его характеристика — имя прилагательное. Все остальные типы слов из обработки исключаются.

Результатом выполнения данного этапа является частотный словарь, с расчетными характеристиками частоты вхождения каждого слова, значимости слова для каждого документа и др.

Реализовать данный этап можно средствами полнотекстового поиска postgresql

Шаг 0.0. Подготовка словарей

Для задачи нам необходим словарь русскоязычных слов:

• хранящий слова в формате ispell
• содержащий только имена существительные, прилагательные и имена собственные

Чтобы не формировать данный словарь вручную, воспользуемся словарем OpenCorpora. Как подготовить словарь для нашей задачи, описано в этой публикации. Будем надеяться, что слова, которыми описаны предмет и характеристики государственных контрактов по большей части присутствуют в нашем словаре 🙂

Проблема на данном шаге. Выбранный нами словарь в основном содержит общеупотребимые слова. Если предметная область к которой относятся документы специфична, она может содержать много важных слов не присуствующих в словаре. В этом случае нужно искать соотсвествующий словарь или формировать его вручную. Иначе эффективность алгоритма снижается

Шаг 0.1. Создание конфигурации полнотекстового поиска

Задача конфигурации в нашем случае — обработать каждый документ таким образом, чтобы на выходе получить только слова, имеющиеся в наших словарях. Стоп-слова и нераспознанные должны быть исключены. Кроме того, конфигурация должна приводить привести каждое слово к нормальной форме. С учетом перечисленных требований, конфигурация создается примерно так:

Подробнее о конфигурации полнотекстового поиска можно прочитать здесь

Проблема на данном шаге. Конфигурация не учитывает грамматических ошибок. Слово написанное с ошибкой не распознается и будет исключено. Если ошибок много — эффективность всего алгоритма снизится.

Шаг 0.3. Генерация частотного списка слов

Специфика массива документов нашего примера такова, что документы могут повторяться. Поэтому, прежде всего необходимо провести очистку, оставив только уникальные записи. Каждый документ имеет идентификатор (номер карточки), отбор уникальных записей будем проводить по этому номеру.

Кстати, при проверке оказалось, что документы с одинаковым номером могут совпадать не полностью. Поэтому, sql-команда ниже предполагает, что будет отобрана уникальная (по номеру) запись с максимальной длиной документа

Получили временную таблицу friq_word с уникальным списком слов (word), количеством документов в которых слово упоминается (ndoc) и общим числом вхождений слова в массив текстов (nentry).

Для дальнейшего анализа необходима дополнительная информация о распределении слов в документах. Запускаем sql-команды

В итоге получаем две временные таблицы:

• word_in_doc — сколько раз (nindoc) слово (word) повторяется в документе (number),
• all_words_in_doc — количество слов (c) в документе (number)

Теперь мы готовы оценить вес каждого слова в каждом документе. Для оценки используем метрику TF-IDF. Подробно о ней можно прочитать тут. Запускаем sql-команду

В итоге получаем таблицу, сохраненную в виде csv-файла в которой:

• number — идентификатор документа,
• word — слово
• tf_idf — вес слова для каждого документа

Приведенной командой мы дополнительно исключаем слова встречающиеся в массиве документов только один раз (см. выдвинутые гипотезы).

Проблема на данном шаге. Метрика выбрана экспертным способом. Если окажется, что она непригодна для данного массива документов — эффективность алгоритма снизится

Источник

Алгоритм LSA для поиска похожих документов

И снова наш аналитический отдел подготовил материал для читателей блога Netpeak. Передаю привет Кириллу Левенцу — он проделал титанический труд, чтобы изложить понятным языком не самые простые вещи.

Среди огромного числа алгоритмов, которые используются для поиска и анализа информации, особое место занимают те, чья цель — обнаружение скрытых закономерностей или неочевидных зависимостей.

Используя семантический анализ текста, мы можем сказать, например, что два текста похожи, даже если эта похожесть выражена косвенно. Или например «лыжи» и «автомобиль» по отдельности относятся к разным категориям, но будучи использованы вместе, могут быть интерпретированы в таких категориях, как «спорт» и «отдых».

Об одном из методов, который применяется для рекомендательных систем (коллаборативная фильтрация), информационного семантического поиска, разделения текстов по тематикам без обучения и многих других и пойдет речь далее. Метод этот называется латентно-семантическим анализом (LSA — Latent semantic analysis). Можно сказать, что это продвинутый SEO анализ текста.

Рассмотрим более подробно, что это за метод и как он работает

Уже из названия можно сделать вывод о том, что он должен делать, а именно находить скрытые смысловые взаимосвязи между объектами (будь-то слова в тексте или товары в магазине). Для текстов на естественных языках такой скрытой закономерностью может быть, например, наличие определенного набора слов в определенной теме. Представим себе такую задачу: у нас есть коллекция документов и мы хотим научиться отвечать на вопрос: два документа близки по тематике или нет. Вывод о схожести можно сделать, основываясь на том, какие слова и в каких пропорциях входят в каждый из документов.

Чтобы подготовить данные для этой задачи, используют подход, который называется «мешок слов».

Его суть состоит в том, что для нас неважен порядок слов в документе, в каких морфологических формах они представлены, а важно только количество вхождений конкретных слов. Предположим, что каждую тему можно охарактеризовать определенным набором слов и частотой их появления. Если в тексте конкретный набор слов употребляется с определенными частотами, то текст принадлежит к определенной теме.

Основываясь только на этой информации, строится таблица «слово-документ». Где строки соответствуют словам (а точнее, их леммам), а столбцы — документам. В каждой ячейке хранится 1, если слово есть в документе, и 0 — если нет. Хотя такой вариант и самый простой, но не самый лучший. Вместо 0 и 1 можно использовать, например, частоту слова в документе или tf-idf слова. Такой способ представления текстов в виде таблицы (или матрицы) называется векторной моделью текста. Теперь, для того чтобы сравнить два документа, нужно определить меру схожести двух столбцов таблицы.

Сделать это можно по-разному:

• скалярное произведение векторов — столбцов таблицы;
• косинусное расстояние (пожалуй самое адекватное);
• евклидовым расстоянием;
• манхэттенским расстоянием.

Чтобы лучше понять все вышесказанное, изобразим это графически на простом примере двух небольших текстов. Один текст про письменность, другой про неопределенность Гейзенберга. Стоп-слова удалены, а остальные приведены к основной форме (без окончаний). Каждая точка на графике — слово. На осях отложено, сколько раз слово встретилось в каждом документе. Т.е. если слово встретилось в тексте про неопределенность 3 раза, а в тексте про письменность 2 раза, то на рисунке это слово изобразим точкой с координатами (3,2).

Видно, что в этом примере некоторые слова встречались и в одном и в другом тексте приблизительно одинаково часто («свободн», «друг», «звук» и так дплее). Такие слова не дают возможности отличить тексты один от другого и в принципе сравнимы со стоп-словами. Но есть слова, которые характерны только одному из текстов. Имея такое представление текста, мы можем определять близость каждого слова к теме (как косинус угла между вектором с началом в (0;0) и концом в точке слова и осью, соответствующей документу). Если же такого слова в коллекции нету, то о нем мы ничего не можем сказать.

Для сравнения документов можно подсчитать сумму векторов-слов, которые в них входят и опять же оценить расстояние между ними. В рассмотренном примере слова распределились хорошо, так как тематики существенно разные. А если тематики схожи, то может получиться такая картина:

По сравнению с предыдущей картинкой видно, что документы существенно похожи, и, кроме того, есть слова, которые характеризуют общую тематику для обоих текстов (например «язык» и «письмен»). Такие слова можно назвать ключевыми для данной темы. Т.е. напрашивается вывод, что имея такое представление текстов, мы теоретически можем сгруппировать документы по близости их содержимого, и таким образом построить тематическое разбиение коллекции текстов. В частности может оказаться, что каждый документ — это отдельная тема. Также можно искать документы по запросу, при этом могут находиться документы, которые не содержат слов из запроса, но близки ему по теме.

Но в жизни оказывается, что документов и слов очень много (гораздо больше чем тем) и возникают следующие проблемы:

• размерности (вычисление близости между векторами становится медленной процедурой);
• зашумленности (например, посторонние небольшие вставки текста не должны влиять на тематику);
• разряженности (большинство ячеек в таблице будут нулевыми).

В таких условиях довольно логично выглядит идея, вместо таблицы «слово-документ» использовать что-то типа «слово-тема» и «тема-документ». Решение именно такой задачи предлагает LSA. Правда, интерпретация полученных результатов может оказаться затруднительной.

На рисунке приведен пример карты двух художественных текстов. Видно, что у них есть как свои особенности, так и много общего, и можно выделить новую тематику. Если говорить в терминах линейной алгебры, то нам нужно такое представление:

Числа в таблицах в общем случае не обязательно будут именно 0 и 1. Имея такое представление, мы можем кроме оценки близости слов и документов, также определять важные слова для каждой тематики.

Ограничения LSA:

1. Невозможно получить тематик больше чем документов/слов.
2. Семантическое значение документа определяется набором слов, которые, как правило, идут вместе.
3. Документы рассматриваются как просто наборы слов. Порядок слов в доку­ментах игнорируется. Важно только то, сколько раз то или иное слово встречается в документе.
4. Каждое слово имеет единственное значение.
5. Недостаток LSA — предположение о том, что карта слов в документах не имеет вид нормального распределения. С этой проблемой справляются другие модификации метода (вероятностный LSA и LDA).

LSA включает в себя следующие этапы:

1. Удаление стоп-слов, стемминг или лемматизация слов в документах;
2. Исключение слов, встречающихся в единственном экземпляре;
3. Построение матрицы слово-документ (бинарную есть/нет слова, число вхождений или tf-idf);
4. Разложение матрицы методом SVD (A = U * V * WT);
5. Выделение строк матрицы U и столбцов W, которые соответствуют наибольшим сингуляр­ным числам (их может быть от 2-х до минимума из числа терминов и документов). Конкретное количество учитываемых собственных чисел определяется предполагаемым количеством семантических тем в задаче. А вообще чем больше сингулярное число, тем сильнее в коллекции проявлена тема.

В итоге получается нечто такое:

Пример с небольшими документами

[Взят из статьи Indexing by Latent Semantic Analysis, 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, W T ).

Чтобы иметь возможность визуально оценить результат, выделим только две главные компоненты, соответствующие самым большим сингулярным числам. Используем значения в выделенных столб­цах как координаты и изобразим их в виде точек на плоскости (синим цветом документы, красным — слова, кругами — возможные тематики).

Рассмотрим расстояние между каждой парой слов. Было (желтым цветом выделены значения выше 0):

Стало после снижения размерности (зеленым цветом выделены значения больше 0,8):

Как и по картинке, так и по таблице видно, что термины образовали 2 группы (довольно условно) и по сравнению с исходной матрицей связи значительно усилены (как укрепились исходные, так и появились новые):

• [human, interface, computer, user, EPS, response, time],
• [survey, trees, graph, minors].

Между каждой парой документов.

Отношение термин документ.

Рассмотрим еще один пример: пусть имеются три документа, каждый — на свою тематику (первый про автомобили, второй про спорт и третий про компьютеры). Используя LSA, изобразим двумерное представление семантического пространства, и как в нем будут представлены слова (красным цветом), запросы (зеленым) и документы (синим). Напомню, что все слова в документах и запросах прошли процедуру лемматизации или стемминга.

Видно, что тема «компьютер» хорошо отделилась от двух других. А вот «спорт» и «авто» довольно близки друг другу. Для каждой темы проявились свои ключевые слова. Зеленым на рисунке изображен запрос «автомобил колес». Его релевантность к документам имеет следующий вид:

1. ‘sport.txt’ — 0.99990845
2. ‘auto.txt’ — 0.99987185
3. ‘computer.txt’ — 0.031289458

Из-за близости тем «спорт» и «авто» довольно сложно точно определить, к какой теме он принадлежит. Но точно не к «компьютерам». Если в системе, обученной на этих документах, попытаться определить релевантность к образовавшимся темам слова «рынок», то в ответ мы получим 0 (т.к. это слово в документах не встречалось ни разу). Добавим в систему документ по теме «финансы». Будем снова искать слово «рынок».

Источник

Латентно-семантический анализ

Латентно-семантический анализ (ЛСА) — это метод обработки информации на естественном языке, анализирующий взаимосвязь между коллекцией документов и терминами в них встречающимися, сопоставляющий некоторые факторы (тематики) всем документам и терминам.

В основе метода латентно-семантического анализа лежат принципы факторного анализа, в частности, выявление латентных связей изучаемых явлений или объектов. При классификации / кластеризации документов этот метод используется для извлечения контекстно-зависимых значений лексических единиц при помощи статистической обработки больших корпусов текстов [1] .

Содержание

История

Впервые ЛСА был применен для автоматического индексирования текстов, выявления семантической структуры текста и получения псевдодокументов [3] . Затем этот метод был довольно успешно использован для представления баз знаний [4] и построения когнитивных моделей [5] .

В последние годы метод ЛСА часто используется для поиска информации (индексация документов), классификации документов [6] , моделях понимания [7] и других областях, где требуется выявление главных факторов из массива информационных данных .

Описание работы ЛСА

ЛСА можно сравнить с простым видом нейросети, состоящей из трех слоев: первый слой содержит множество слов (термов), второй – некое множество документов, соответствующих определенным ситуациям, а третий, средний, скрытый слой представляет собой множество узлов с различными весовыми коэффициентами, связывающих первый и второй слои.

В качестве исходной информации ЛСА использует матрицу термы-на-документы, описывающую набор данных, используемый для обучения системы. Элементы этой матрицы содержат, как правило, веса, учитывающие частоты использования каждого терма в каждом документе и участие терма во всех документах (TF-IDF). Наиболее распространенный вариант ЛСА основан на использовании разложения диагональной матрицы по сингулярным значениям (SVD – Singular Value Decomposition). С помощью SVD-разложения любая матрица раскладывается во множество ортогональных матриц, линейная комбинация которых является достаточно точным приближением к исходной матрице.

Говоря более формально, согласно теореме о сингулярном разложении [8] , любая вещественная прямоугольная матрица может быть разложена на произведение трех матриц:

Таким образом, каждый терм и документ представляются при помощи векторов в общем пространстве размерности

Латентно-семантический анализ

Как находить тексты похожие по смыслу? Какие есть алгоритмы для поиска текстов одной тематики? – Вопросы регулярно возникающие на различных программистских форумах. Сегодня я расскажу об одном из подходов, которым активно пользуются поисковые гиганты и который звучит чем-то вроде мантры для SEO aka поисковых оптимизаторов. Этот подход называет латентно-семантический анализ (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 называются сингулярными числами.

Прелесть сингулярного разложения состоит в том, что оно выделяет ключевые составляющие матрицы, позволяя игнорировать шумы. Согласно простым правилам произведения матриц, видно, что столбцы и строки соответствующие меньшим сингулярным значениям дают наименьший вклад в итоговое произведение. Например, мы можем отбросить последние столбцы матрицы U и последние строки матрицы V^t, оставив только первые 2. Важно, что при этом гарантируется, оптимальность полученного произведения. Разложение такого вида называют двумерным сингулярным разложением:

Давайте теперь отметим на графике точки соответствующие отдельным текстам и словам, получится такая занятная картинка:

Из данного графика видно, что статьи образуют три независимые группы, первая группа статей располагается рядом со словом «wikileaks», и действительно, если мы посмотрим названия этих статей становится понятно, что они имеют отношение к wikileaks. Другая группа статей образуется вокруг слова «премия», и действительно в них идет обсуждение нобелевской премии.

На практике, конечно, количество групп будет намного больше, пространство будет не двумерным а многомерным, но сама идея остается той же. Мы можем определять местоположения слов и статей в нашем пространстве и использовать эту информацию для, например, определения тематики статьи.

Улучшения алгоритма

Легко заметить что подавляющее число ячеек частотной матрицы индексируемых слов, созданной на первом шаге, содержат нули. Матрица сильно разрежена и это свойство может быть использовано для улучшения производительности и потребления памяти при создании более сложной реализации.

В нашем случае тексты были примерно одной и той же длины, в реальных ситуациях частотную матрицу следует нормализовать. Стандартный способ нормализации матрицы TF-IDF

Мы использовали двухмерную декомпозицию SVD-2, в реальных примерах, размерность может составлять несколько сотен и больше. Выбор размерности определяется конкретной задачей, но общее правило таково: чем меньше размерность тем меньше семантических групп вы сможете обнаружить, чем больше размерность, тем большее влияние шумов.

Замечания

Для написания статьи использовалась Java-библиотека для работы с матрицами Jama. Кроме того, функция SVD реализована в известных математических пакетах вроде Mathcad, существуют библиотеки для Python и C++.

Источник