Векторная модель

Ве́кторная моде́ль (англ. vector space model) — в информационном поиске представление коллекции документов векторами из одного общего для всей коллекции векторного пространства.

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

ОпределениеПравить

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

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

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

Более формально

d_j = (w_1j, w_2j, …, w_nj)

где d_j — векторное представление j-го документа, w_ij — вес i-го терма в j-м документе, n — общее количество различных термов во всех документах коллекции.

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

Методы взвешивания термовПравить

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

• булевский вес — равен 1, если терм встречается в документе и 0 в противном случае;
• tf (term frequency, частота терма) — вес определяется как функция от количества вхождений терма в документе;
• tf-idf (term frequency — inverse document frequency, частота терма — обратная частота документа) — вес определяется как произведение функции от количества вхождений терма в документ и функции от величины, обратной количеству документов коллекции, в которых встречается этот терм.

Косинусное сходствоПравить

Косинусное сходство — это мера сходства между двумя векторами предгильбертового пространства, которая используется для измерения косинуса угла между ними.

Если даны два вектора признаков, A и B, то косинусное сходство, cos(θ), может быть представлено используя скалярное произведение и норму:

$\text{similarity}=\cos <!--\; \; -->(\mathrm{\theta <!--\; \theta \; -->})=\frac{A\cdot <!--\; \cdot \; -->B}{\Vert <!--\; \Vert \; -->A\Vert <!--\; \Vert \; -->\Vert <!--\; \Vert \; -->B\Vert <!--\; \Vert \; -->}=\frac{\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{A}_i\times <!--\; \times \; -->B_i}{\sqrt{\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}(A_i{)}^2}\times <!--\; \times \; -->\sqrt{\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}(B_i{)}^2}}$${\text{similarity}}=\cos(\theta )={A\cdot B \over \|A\|\|B\|}={\frac {\sum \limits _{{i=1}}^{{n}}{A_{i}\times B_{i}}}{{\sqrt {\sum \limits _{{i=1}}^{{n}}{(A_{i})^{2}}}}\times {\sqrt {\sum \limits _{{i=1}}^{{n}}{(B_{i})^{2}}}}}}$ 

В случае информационного поиска, косинусное сходство двух документов изменяется в диапазоне от 0 до 1, поскольку частота терма (веса tf-idf) не может быть отрицательной. Угол между двумя векторами частоты терма не может быть больше, чем 90°.

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

«Мягкая» косинусная мераПравить

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

Например, в области обработки естественного языка сходство между объектами весьма интуитивно. Такие признаки как слова, N-граммы или синтаксические N-граммы могут быть довольно схожи, хотя формально они считаются различными признаками в векторной модели. Например, слова «играть» и «игра» различны и, таким образом, отображаются в различных измерениях в векторной модели, хотя, очевидно, что они связаны семантически. В случае N-грамм или синтаксических N-грамм может быть применено расстояние Левенштейна (кроме того, расстояние Левенштейна может быть также применено и к словам).

Для расчета «мягкой» косинусной меры вводится матрица s сходства между признаками. Она может рассчитываться, используя расстояние Левенштейна или другие меры сходства, например, различные меры сходства в Wordnet. Затем производится умножение с применением данной матрицы.

Если даны два N-мерных вектора a и b, то мягкая косинусная мера рассчитывается следующим образом:

$\begin{array}{r}{\mathrm{s}\mathrm{o}\mathrm{f}\mathrm{t}\mathrm{\_<!--\; \_\; -->}\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{n}\mathrm{e}}_1<!--\; \; -->(a,b)=\frac{{\sum <!--\; \sum \; -->}_{i,j}^N{s}_{ij}{a}_i{b}_j}{\sqrt{{\sum <!--\; \sum \; -->}_{i,j}^N{s}_{ij}{a}_i{a}_j}\sqrt{{\sum <!--\; \sum \; -->}_{i,j}^N{s}_{ij}{b}_i{b}_j}},\end{array}$${\begin{aligned}\operatorname {soft\_cosine}_{1}(a,b)={\frac {\sum \nolimits _{{i,j}}^{N}s_{{ij}}a_{i}b_{j}}{{\sqrt {\sum \nolimits _{{i,j}}^{N}s_{{ij}}a_{i}a_{j}}}{\sqrt {\sum \nolimits _{{i,j}}^{N}s_{{ij}}b_{i}b_{j}}}}},\end{aligned}}$ 

где s_ij = сходство(признак_i, признак_j).

При отсутствии сходства между признаками (s_ii = 1, s_ij = 0 для i ≠ j)), данное уравнение эквивалентно общепринятой формуле косинусного сходства.

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

ЛитератураПравить

• Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze An Introduction to Information Retrieval Архивная копия от 9 декабря 2012 на Wayback Machine Draft. Online edition. Cambridge University Press. — 2009. — 544 pp.
• Daniel Jurafsky, James H. Martin Speech and Language Processing. An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. Second Edition. Pearson Education International. — 2009. — 1024 pp.

См. такжеПравить

• Apache Lucene — программная реализация информационного поиска, основанная на векторной модели.