Матричный латентно-семантический анализ текстовых данных

Материал из DvoWiki
Перейти к: навигация, поиск

Краткая аннотация

Алгоритм матричного латентно-семантического анализа данных основывается на использовании матричной модели описания данных. В рамках данной модели вся структура документов представляется в виде числовой матрицы, строки которой характеризуют документы из структуры, а столбцы - терминологический набор. Ячейками этой матрицы являются некоторые весовые коэффициенты, определяющие значимость конкретного терма в выбранном документе. Данное представление базы текстовых данных позволяет, как будет показано ниже, даже с учетом значительного снижения размерности матриц, оценивать близость запросов и документов путем скалярного произведения двух малоразмерных векторов.


Математическое описание алгоритма

Математический аппарат данного алгоритма основан на сингулярном разложении начальной матрицы. Данный метод позволяет выявлять и использовать семантические связи между документами и термами внутри документов, что позволяет увеличивать точность поиска при обработке больших массивов документов. Из матричного анализа известно, что любая прямоугольная матрица A_{{}}^{{}} может быть разложена на произведение трех матриц: A=U\Sigma \;V^{T}. Где U_{{}}^{{}} и V_{{}}^{{}} - ортонормированные матрицы, так называемые - левая и правая сингулярные матрицы, а \Sigma \;_{{}}^{{}} - диагональная матрица сингулярных значений.

Доказано, что если в матрице \Sigma \;_{{}}^{{}} оставить только k_{{}}^{{}} наибольших сингулярных чисел, а в матрицах U_{{}}^{{}} и V_{{}}^{{}} только соответствующие этим числам столбцы, то произведение получившихся матрицA\cong \;A_{{k}}=U_{{k}}\Sigma \;_{{k}}V_{{k}}^{T}, будет наилучшим приближением исходной матрицы A_{{}}^{{}} матрицей ранга не превышающего k_{{}}^{{}}.

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

Для поиска используются матрицы U_{k}^{{}} и V_{k}^{T}. Которые в условиях данной модели представляют собой - строки матрицы U_{k}^{{}} являются образами термов, и аналогично столбцы матрицы V_{k}^{T} являются образами документов в неком k_{{}}^{{}}-мерном вещественном пространстве скрытых факторов.

Таким образом, осуществляется составление основной, так называемой, обучающей модели. При дальнейшем пополнении документом d_{{}}^{{}} информационного массива при уже имеющейся раннее подготовленной обучающей модели, для которой проведено сингулярное разложение, нет необходимости проводить его заново. В этом случае, вычисляется образ документа d'=\Sigma \;_{k}^{{-1}}U_{{k}}^{T}d, который просто дописывается последней строкой в матрицу V_{k}^{{}} как раз и отвечающей за новый документ.

Поиск по информационному массиву производится путем задания некоего запроса, представляющего из себя m_{{}}^{{}}-мерный вектор, i_{{}}^{{}}-й элемент которого равен 1_{{}}^{{}}, когда терм с номером i_{{}}^{{}} входит в запрос, и 0_{{}}^{{}} - в противном случае. Далее вычисляется образ запроса q'=q^{{T}}U_{{k}}\Sigma \;_{{k}}^{{-1}} в k_{{}}^{{}}-мерном пространстве латентных факторов. И тогда мера близости запроса q_{{}}^{{}} и некоторого документа d_{{}}^{{}} оценивается скалярной величиной произведения вектора q_{{}}^{{,}} и столбца d_{{}}^{{}} матрицы V_{k}^{T} отвечающего необходимому документу.


Описание реализованного алгоритма

Алгоритм матричного латентно-семантического анализа реализован в виде java-класса, который включает в себя все основные возможности данного метода, а также некоторые дополнительные.

Начальная подготовка основной матрицы осуществляется путем составления словаря используемых термов. Его можно составить различными способами, от полностью ручного составления этого файла, до автоматического, на основе всех термов (слов) используемых в основном обучающем множестве документов. Предпочтительным является использование второго метода с некоторым улучшением - использованием таблицы соответствия между словами, полученными из документов и "начальной формы" этих слов (для наилучшего результата необходимо использовать не только преобразование формы слова, но в некоторых случаях и изменение слов в соответствии со словарем синонимов). Этот метод позволяет значительно сократить количество термов и тем самым уменьшить необходимые алгоритму ресурсы.

Таким образом мы получаем документ содержащий все используемые термы и некоторую нормирующую таблицу, которая приводит любое слово из документа в множество рассматриваемых термов. Далее на основе полученных данных и основного обучающего множества формируется таблица из m_{{}}^{{}} строк (количество термов) и n_{{}}^{{}} столбцов (количество документов), где в качестве значений a_{{ij}}^{{}} используется количество вхождений i_{{}}^{{}}-ого терма в j_{{}}^{{}}-ый документ. Далее данная матрица раскладывается по средствам метода сингулярного разложения и путем выбора размерности k_{{}}^{{}} создаются матрицы U_{k}^{{}} размерности m_{{}}^{{}} на k_{{}}^{{}}, V_{k}^{T} размерности k_{{}}^{{}} на n_{{}}^{{}} и вектор \Sigma \;_{k}^{{}} размерности k_{{}}^{{}}.

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

Основываясь на полученном разложении, можно получить следующие результаты:

  • Определить корреляцию (близость) двух термов
  • Определить корреляцию двух документов
  • Определить корреляцию запроса и любого выбранного документа
  • Выделить наиболее подходящие к данному запросу документы


Определение корреляции двух термов

Одной из самых трудоемких является система определения корреляции двух термов, которая основывается на близости двух векторов покомпонентно. Для этого рассматриваются два вектора-строки a_{{}}^{{}} и b_{{}}^{{}} матрицы A_{k}^{{}} (A_{k}=V_{k}^{T}\Sigma \;_{k}U_{k}), которые представляют собой образы выбранных термов. Далее в соответствии с компонентами данных векторов составляются два вектора a' и b' связанных с найденными следующим образом:

  • каждому компоненту исходного вектора ставится в соответствие число от 1 до k.
  • минимальной компоненте ставится число 1, максимальной k

Далее, корреляция вычисляется по следующей формуле cor=1-{\frac  {6\sum _{{i=1}}^{{k}}(a'_{{i}}-b'_{{i}})}{k(k^{2}-1)}}

Определение корреляции двух документов

Вычисление корреляции между двумя выбранными документами осуществляется путем нахождения скалярного произведения векторов - строк матрицы V_{{}}^{T} отвечающих двум выбранным дкументам.

Определение корреляции запроса и любого выбранного документа

Вначале осуществляется вычисление вектора запроса, по заданному множеству термов. Далее вычисляется образ запроса q'=q^{{T}}U_{{k}}\Sigma \;_{{k}}^{{-1}}. Корреляция в этом случае cor=\sum _{{i=1}}^{{k}}q'_{{i}}V_{k}^{T}(s), где V_{k}^{T}(s) - столбец матрицы V_{k}^{T} соответствующий необходимому документу.

Выделение наиболее подходящих к данному запросу документов

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

Исходники в Subversion

svn://ftp.dvo.ru/nexo/lsa


Сопутствующие ссылки

Latent Semantic Analysis @CU Boulder