Векторная модель и косинусное сходство (Cosine similarity)

В это статье я хочу ознакомить вас с примером использования векторной модели и рассказать как используется косинусное сходство —  Cosine similarity в информационном поиске.

Документ в векторной модели рассматривается как неупорядоченное множество термов. Термами в информационном поиске называют слова, из которых состоит текст, а также такие элементы текста, как, например, 2010, II-5 или Тянь-Шань.

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

Хорошее описание представлено в wiki (на русском, на английском).

Как рассчитать косинусное сходство? (Cosine similarity)

Рассмотрим небольшую коллекцию C, которая содержит следующие три документа:

Document 1 new york times
Document 2 new york post
Document 3 los angeles times

Некоторые термы встречаются в двух документах, некоторые только в одном. Общее количество документов N=3.

Рассчитаем значения idf (функции от величины, обратной количеству документов коллекции, в которых встречается этот терм) для термов:

angeles  log2(3/1)=1.584
los log2(3/1)=1.584
new log2(3/2)=0.584
post log2(3/1)=1.584
times log2(3/2)=0.584
york log2(3/2)=0.584

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

angeles los new post times york
Document 1 0 0 1 0 1 1
Document 2 0 0 1 1 0 1
Document 3 1 1 0 0 1 0

Теперь мы умножим значения tf на значения idf для каждого терма, получаем следующую матрицу: (Все термы встречаются только один раз в каждом документе в нашей небольшой коллекции, так что максимальное значение для нормализации будет 1.)

angeles los new post times york
Document 1 0 0 0.584 0 0.584 0.584
Document 2 0 0 0.584 1.584 0 0.584
Document 3 1.584 1.584 0 0 0.584 0

Для заданного поискового запроса: “new new times”, мы вычислим tf-idf вектор для запроса, и вычислим схожесть каждого документа из коллекции с заданным запросом, используя измерение косинусной схожести (cosine similarity). При вычислении tf-idf значений для термов из запроса мы разделим частоту на максимальную частоту (2) и умножим на значения idf.

query 0 0 (2/2)*0.584=0.584 0 (1/2)*0.584=0.292 0

Рассчитаем длину каждого документа и запроса:

Length of d1 = sqrt(0.584^2+0.584^2+0.584^2)=1.011

Length of d2 = sqrt(0.584^2+1.584^2+0.584^2)=1.786

Length of d3 = sqrt(1.584^2+1.584^2+0.584^2)=2.316

Length of q = sqrt(0.584^2+0.292^2)=0.652

Затем рассчитаем схожесть пл формуле

:

cosSim(d1,q) = (0*0+0*0+0.584*0.584+0*0+0.584*0.292+0.584*0) / (1.011*0.652) = 0.776

cosSim(d2,q) = (0*0+0*0+0.584*0.584+1.584*0+0*0.292+0.584*0) / (1.786*0.652) = 0.292

cosSim(d3,q) = (1.584*0+1.584*0+0*0.584+0*0+0.584*0.292+0*0) / (2.316*0.652) = 0.112

Согласно полученным значениям схожести, конечный порядок в котором документы будут представлены как результат запроса будет: d1, d2, d3.

 

(Visited 884 times, 1 visits today)

Добавить комментарий

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.