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

Задачи поиска в сетях

Векторно-пространственная модель поиска

Большинство известных информационно-поисковых систем базируется на использовании векторно-пространственной модели описания данных (Vector Space Model), предложенной Г. Солтоном в 1975 г. и примененной им в системе SMART. Данная модель является классической алгебраической. В рамках этой модели документ описывается вектором в евклидовом пространстве, в котором каждому терму, использующемуся в документе, ставится в соответствие его весовое значение, которое определяется на основе статистической информации о его появлении как в отдельном документе, так и во всем документальном массиве. Описание запроса, соответствующего необходимой пользователю тематике, также представляет собой вектор в том же евклидовом пространстве термов. Для оценки близости запроса и документа используется скалярное произведение соответствующих векторов запроса и документа.

В рамках этой модели каждому терму ti в документе dj соответствует

некоторый неотрицательный вес wij.

В этой модели запросу q, который представляет собой также множество термов, не соединенных между собой никакими логическими операторами, также соответствует вектор весовых значений wiq.

Ландэ Д.В., Снарский А.А., Безсуднов И.В. Интернетика: Навигация в сложных сетях:| модели и алгоритмы. - M.: Либроком (Editorial URSS), 2009. - 264 с.

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

как информационные векторы

и

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

Его встречаемости в данном документе, то есть:

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

где ni — число документов, в которых используется терм tj, а N — общее количество документов в массиве.

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

где freqiq - частота терма ti из запроса в тексте документа, состоящего из n термов.

Обычно весовые значения Wij нормируются, что позволяет рассматривать документ как ортонормированный вектор. Такой метод взвешивания термов имеет стандартное обозначение - TF IDF, где TF указывает на частоту появления терма в документе (term frequency), а IDF — на величину, обратную числу документов массива, содержащих данный терм (inverse document frequency).

Когда возникает задача определения тематической близости двух документов или документа и запроса, в этой модели используется простое скалярное произведение sim(d1,d2), двух соответствующих векторов весовых значений

( wі1,…. wnl) и (wi2, …..wn2), которое, очевидно, соответствует косинусу угла между векторами - образами документов d1 и d2. Очевидно, sim(d1,d2) принадлежит диапазону [0, 1]. Чем больше величина sim(d1, d2) — тем более близки документы d1 и d2. Для любого документа d имеем s1m(d,d) = 1. Аналогично мерой близости документа dj и запроса q является величина:

Векторно-пространственная модель представления данных обеспечивает системам, построенным на ее основе, такие возможности:

  • — обработку запросов без ограничений их длины;
  • — простоту реализации режима поиска подобных документов (каждый документ может расматриваться как запрос);
  • — сохранение результатов поиска с возможностью выполнения уточняющего поиска.

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

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