Методы построения функции схожести документов

Методы построения функции схожести документов

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

Наибольшее распространение сегодня получили три метода оценки сходства документов: метод выделения ключевых слов, метод взвешенных ключевых слов и метод латентных семантик (latent semantic indexing - LSI) - скрытых семантических зависимостей.

1. Метод выделения ключевых слов.

Основной принцип - выделение списка ключевых слов для каждого документа и формирования на основе этого списка единого информационного массива ключевых слов.

Совокупность  документов В можно представить как массив: В = {D1,D2,D3,..., Dn}, где D — документ. Не акцентируя внимание на структуре каждого из этих документов, их можно представить как набор ключевых слов: D = {ki1,ki2,ki3,..., kim}, где kij — ключевое слово. Объединяя наборы ключевых слов всех документов, можно сформировать информационный массив ключевых слов: K = {k1,k2,k3,...,kN}.

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

В качестве примера одной из наиболее простых  функций сходства можно привести следующую функцию сходства: F(Di,Dj) = [Qij]/[Mij], где Qij — множество совпавших ключевых слов, Mij — общее для Di и Dj множество ключевых слов.

Усовершенствованием метода выделения ключевых слов является метод взвешенных ключевых слов. Данный метод основывается на представлении документов в виде неупорядоченного набора слов, встречающихся в этом документе, с присвоенным каждому из них весовым коэффициентом, характеризующим значимость этого слова для выражения общего смысла всего документа. Расчет весовых коэффициентов часто производится по методике TFIDF (term frequency times inverse document frequency), определяющей вес того или иного слова в документе на Основе частоты его встречаемости в данном документе и относительно общего количества документов, в которых это слово присутствует. Если документ имеет некоторую структуру (заголовок, аннотацию, авторов и т.п.), то весовые коэффициенты слов могут быть модифицированы в соответствии с их месторасположением в тексте: например, коэффициенты слов, присутствующих в заголовке, могут быть увеличены.

Метод латентных семантик LSI. Одним из методов, учитывающих скрытые взаимосвязи, является латентное семантическое индексирование LSI.

LSI представляет  собой расширение стандартного  векторного метода. Основная идея алгоритма — статистическая оценка и учет скрытых (латентных) ассоциаций между словами в документах. Вместо представления документов как дискретных векторов в пространстве независимых слов LSI рассматривает и ключевые слова, и документы как непрерывные вектора в базисе из к ортогональных "индексирующих" размерностей, полученных в ходе SVD-анализа. Разные исследователи определяют меру сходства между этими векторами либо через их скалярное произведение, либо через косинус угла между ними. Авторы отдают предпочтение первому подходу, так как он учитывает вклад слов, встречающихся в документах более одного раза.

Данный  метод, несмотря на более высокую  сложность математического аппарата, обладает рядом неоспоримых достоинств. Так как количество полученных размерностей гораздо меньше первоначального  числа терминов, последние перестают  быть независимыми. Например, если два, на первый взгляд никак не связанных между собой слова, используются в нескольких сходных по содержанию документах, они будут иметь близкие вектора (в смысле величины их скалярного произведения) в k-мерном пространстве факторов. Таким образом, термины, входящие в профиль пользователя, рассматриваются не сами по себе, а в контексте фильтруемых документов. Метод "улавливает" их скрытую, латентную структуру, более глубокую, чем просто статистика встречаемости слов. Кроме того, ввиду небольшого числа "индексирующих" размерностей существенно сокращается вычислительная сложность алгоритма, что позволяет использовать его на практике в промышленных масштабах.

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