< Попер   ЗМІСТ   Наст >

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

Метод кластерного анализа LSA/LSI (латентного семантического анализа/ индексирования) [базируется на сингулярном разложении матриц (SVD, Singular Value Decomposition). Пусть массиву документов ставится в соответствие матрица A, строки которой соответствуют документам, а столбцы весовым значениям термов (размер словаря термов - т). Сингулярным разложением матрицы А ранга г размерности mX n называется ее разложение вида где U и V — ортогональные матрицы размерности m X r и соответственно, а S — диагональная матрица, элементы которой если , а диагональные элементы

Диагональные элементы матрицы S называют сингулярными значениями матрицы A.

Ортогональные матрицы II и V обладают таким свойством:

Доказано, что приведенное выше разбиение матрицы А обладает той особенностью, что если в матрице 5 оставить только к наибольших сингулярных значений (обозначим такую матрицу как ), а в матрицах и и V — только соответствующие этим значениям колонки (соответственно, матрицы то матрица будет наилучшей по Фробениусу аппроксимацией исходной матрицы А матрицей с рангом, не превышающим к . Напомним, что нормой матрицы X размерности М • N по Фробениусу является выражение:

Таким образом, для матриц А и Ак доказано, что:

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

Ак определяет к -мерное факторное пространство, на которое проецируются, как документы (с помощью матрицы V), так и термины (с помощью матрицы и). В полученном факторном пространстве документы и термины группируются в области, имеющие некоторый общий скрытый смысл. Т.е. получаемые области и представляют собой кластеры.

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

В практике информационного поиска особое значение отводится матрицам

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

к — мерном пространстве. Иными словами, эти векторы задают искомое представление термов и документов в к — мерном пространстве скрытых факторов.

Существуют также методы инкрементного обновления всех значений, используемых в ЬБА. При пополнении новым документом ё (например, новым результатом поиска по запросу) информационного массива, для которого уже проведено сингулярное разложение, можно не вычислять разложение заново. Достаточно аппроксимировать его, вычисляя образ нового документа на основе ранее вычисленных образов термов и весов факторов. Пусть ё — вектор весов термов нового документа (новый столбец матрицы А), тогда его образ можно вычислить по формуле:

Если ц — вектор запроса пользователя размерности т, 1 — й элемент которого равен 1, если терм с номером 1 входит в запрос, и 0 - в противном случае, то образ запроса ц в пространстве латентных факторов будет иметь вид:

В этом случае мера близости запроса ц и документа ё оценивается величиной скалярного произведения векторов

(здесь обозначает ё — й столбец матрицы

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

Метод LSA широко применяется при ранжировании выдачи информационно-поисковых систем, основанных на цитировании. Это алгоритм HITS (Hyperlink Induced Topic Search) - один из двух самых популярных сегодня в области информационного поиска. Если вспомнить понятие матрицы инциденций A (п. 2.8), то алгоритм HITS обеспечивает выбор наиболее авторитетных документов (авторов - ap или посредников - hp), которые соответствуют собственным векторам матриц

И с наибольшими модулями собственных значений. Покажем, что алгоритм HITS эквивалентен LSA. Действительно, пусть, в соответствии с сингулярным разложением:

S — квадратная диагональная матрица. Тогда

гдедиагональная матрица с элементами

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

Наряду с тем, что метод ЬБЛ не нуждается в предварительной настройке на специфический набор документов, качественно выявляет латентные факторы, к его недостаткам можно отнести невысокую производительность (скорость вычисления SVD соответствует порядку

Где D — множество документов, Т — множество термов, к — размерность пространства факторов) и то, что он не предусматривает возможность пересечения кластеров, что противоречит практике. Кроме того, ввиду своей вычислительной трудоемкости метод ЬБЛ применяется только для относительно небольших матриц.

 
< Попер   ЗМІСТ   Наст >