Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Алгебраическая модель. В рамках алгебраических моделей документы и запросы описываются в виде векторов в многомерном пространстве. Каркасом для таких моделей выступают алгебраические методы. Рассмотрим модель векторного пространства.
Основная идея очень проста - сопоставить каждому документу некоторой коллекции его образ - вектор в некотором евклидовом пространстве таким образом, чтобы образы близких документов были близки. Любой запрос можно также рассматривать как некоторый текст. Поисковая система, получив запрос пользователя, должна построить его образ - вектор в том же пространстве. В качестве результата поиска выдается список документов, ранжированный по близости образа документа к образу запроса. Рассмотрим классическую модель.
Пусть коллекция D состоит из документов а документ содержит множество различных термов , где – полное множество всех различных термов, встречающихся в документах. Обозначим – число вхождений i-го терма в j-й документ, – число документов коллекции D, содержащих терм . Вес терма в документе обозначим через . Выражение для расчета веса терма имеет следующий вид:
, (1)
где . Будем считать, что если терм не входит в документ .
Если сопоставить документу в качестве его образа вектор
(2)
получим, что каждому документу сопоставлен вектор единичной длины. При этом вес терма тем выше, чем чаще встречается этот терм в документе , и чем реже в остальных документах коллекции.
Описанный метод взвешивания термов называется "tfidt" методом, где обозначение tf указывает на частоту встречаемости термина в документе (term frequency), а idf – на величину обратную числу документов коллекции, содержащих данный терм (inverse document frequency).
В качестве некоторой меры близости документов и можно взять скалярное произведение
,
равное косинусу угла между векторами – образами документов и
, (3)
где –j-я компонента вектора (2), вычисленная согласно (1).
Величина принадлежит диапазону . При этом для любого документа d имеем . Таким образом, чем больше величина тем ближе считаются документы и .
Если использовать описанную выше методику и для некоторого запроса составить его образ, равный вектору , тогда мерой близости запроса документу считается величина
.
Данная модель считается более адекватной реальности, чем чистая булева модель. Однако она имеет крупные недостатки.
Во-первых, в отличие от булевой модели, для этой модели нет эффективного способа найти все документы d, для которых выполняется где есть некоторое пороговое значение.
Тривиальный перебор всех документов неприемлем для большой коллекции. Существуют методы, обобщающие идею поиска элемента в упорядоченном списке методом деления пополам на многомерные пространства - например, используются так называемые многомерные деревья (R-дерево), однако эти подходы требуют дальнейшего исследования. Наиболее практичные на сегодня подходы - объединение векторной модели с булевой моделью и кластеризация.
В первом случае по запросу пользователя выполняется булевский поиск - все термины запроса соединяются операцией OR. Далее полученное множество документов ранжируется в соответствии с моделью векторного пространства.
Во втором случае множество образов всех документов коллекции разбивается на несколько кластеров. Каждый кластер содержит множество близких друг другу по расстоянию образов документов. Для каждого кластера находится центроид - документ, чей образ расположен наиболее близко к геометрическому центру кластера. Поиск по запросу разбивается на два этапа. На первом запрос сопоставляется с центроидами всех кластеров. Определяются кластеры, образы центроидов которых наиболее близки образу запроса. Далее поиск проводится в выбранных кластерах.
Модель векторного пространства — алгебраическая модель представления текстовых документов.
Каждый документ представляется как вектор vj. Каждая компонента такого вектора vij отвечает какому-то слову. Значение i-й компоненты j-го вектора берётся равной весу по TF-IDF для i-го слова и j-го документа:
vij = tf-idfij.
При этом, если слово не встречается в данном документе, то значение соответствующей компоненты вектора равно 0.
Угол между двумя векторами v1 и v2 будет являться мерой схожести данных документов: чем ближе угол к 0, тем более похожи документы; если угол равен π/2, то документы совершенно не похожи.
На практике легче вычислять не сам угол, а его косинус:
cos θ = v1 • v2 / ||v1|| ||v2||
(как обычно, скалярное произведение векторов делится на произведение их норм).
Чем ближе cos θ к 1, тем более похожи документы; если cos θ = 0 то документы совершенно не похожи.
При интернет- поиске поисковый запрос представляется в виде вектора точно так же, как документ, а затем сравнивается со всеми документами, имеющимися в кэше. Посредством вычисления косинуса угла между запросом и документом осуществляется ранжирование по релевантности: чем больше косинус, тем выше в списке результатов поиска документ.
G. Salton, A. Wong, C. S. Yang (1975). A Vector Space Model for Automatic Indexing. Communications of the ACM, vol. 18, nr. 11, pages 613–620.
Весовые функции
В качестве меры важности слова не обязательно всегда использовать TF-IDF, то есть TF в качестве локальной весовой функции и IDF — в качестве глобальной. Можно использовать любую кобинацию из следующих (и многих других, на самом деле) локальных и глобальных весовых функций.
Локальные весовые функции:
Binary: lij = 1, если слово i есть в документе j, =0 в противном случае
«Вариация на тему» индикаторной (характеристической) функции
TermFrequency (TF): lij = tfij, сколько раз слово i встретилось в документе j
- Наша «родная» TF из TF-IDF. Чем чаще слово встречается в документе, тем лучше оно его характеризует.
Log: lij = log (tfij + 1).
Почти как TF, но чем больше данных слов мы уже встретили, тем менее ценно следующее встреченное слово для характеризации документа.
Augnorm: lij = (1 + tfij / MAXi tfij ) / 2
«Aug» означает «augmented». Тоже «вариация на тему» TF.
Глобальные весовые функции
Binary: gi = 1
Normal: gi = 1 / (∑j tfij^2)^(1/2)
Idf: gi = log (n/dfi)
n — сколько документов в наборе,
dfi — сколько документов из набора содержит слово i.
Наша «родная» IDF из TF-IDF. Чем меньше документов, содержащих i-е слово, тем более это слово будет ценно для характеризации документа, в котором оно встретилось.
GfIdf: gi = gfi / dfi,
где
gfi — сколько раз слово i встречается во всём наборе документов
Похожа на Idf, только другой числитель и без логарифма. Знаменатель по-прежнему говорит, что чем меньше документов, тем более значимо слово. Числитель же говорит, что чем чаще слово встречается во ВСЕХ документах, тем оно значимее.
Entropy: gi = 1 + ∑j (pij log pij / log n),
где pij = tfij / gfi.
Используется формула для «общевселенского» понятия энтропии — ожидаемого количества информации, необходимого для полного определения состояния системы:
S = — k ∑j Pj ln Pj,
где Pj — вероятности пребывания рассматриваемой системы в различных состояниях при условии, что мы имеем полную информацию о системе. В качестве этих вероятностей состояний системы у нас выступают tfij / gfi, представляющая собой по сути условную вероятность j-го документа при i-м слове.
Недостатки VSM
Недостатком Vector Space Model является то, что эта модель не справляется с синонимией (когда разные слова имеют одно значение) и полисемией (когда одно слово имеет разные значения). Этот недостаток во многом преодолевается с помощью метода латентного семантического анализа. В нём выделяются не просто слова (terms), а понятия (concepts). Переход к понятийному пространству осуществляется путем нахождения аппроксимирующей матрицы с меньшим рангом с помощью методов линейной алгебры.
Алгебраическая модель в силу высокой адекватности моделируемым процессам отношения между поисковыми образами документов и запросов, а также процедурам построения релевантных подмножеств оказалась удобным инструментом для исследования данной задачи. В качестве организации поискового множества, обеспечивающего быстрый и эффективный поиск, была предложена зонно-иерархическая структура (Z-структура) [2], породившая класс поисковых алгоритмов (названных алгоритмами отсечения), позволяющих сужать область поиска за счет исключения поисковых подмножеств, заведомо не содержащих релевантных запросу документов.
В основе Z-структуры лежит процедура разбиения поискового множества на конечное число непустых и непересекающихся подмножеств и построения для них характеристических векторов, отражающих информационные особенности каждого из подмножеств. Такой подход к организации поискового множества позволяет ставить и решать задачи построения многоуровневой Z-структуры, ее расширения для изменяющихся во времени массивов данных, выполнять процедуры оптимизации Z-структуры с целью сокращения времени поиска.
Были доказаны фундаментальные утверждения, позволяющие связать результаты решения поискового уравнения на множестве характеристических векторов с задачей построения релевантных подмножеств и определившие основные поисковые алгоритмы.
Следует отметить, что в отличие от классических методов кластеризации данный подход позволяет решать проблемы избыточности хранения элементов архива и обеспечивает высокое соответствие критериям полноты и точности поиска.
Характерной чертой Z-структуры поискового множества и порожденных ею алгоритмов отсечения является компактность программной реализации, что позволяет использовать для решения прикладных задач весьма скромные по своим параметрам компьютеры. С другой стороны, заложенный в Z-структуре внутренний параллелизм открывает возможности для применения вычислительных систем с параллельной архитектурой, что в значительной степени снимает проблему размерности решаемых задач.
Идея Z-структуры, разработанная изначально для решения задачи поиска в АИПС, оказалась настолько плодотворной, что нашла свое применение и развитие в различных приложениях, требующих обработки больших информационных массивов по заданным поисковым критериям. В частности, это относится к таким прикладным системам, как обработка графических образов, распознавание рукописного текста, системы безопасности на основе анализа биометрической информации, анализ временных рядов в направлении поиска закономерностей в них, формирование цифрового информационного контента электронных библиотек, определение облика сложных технических систем с заданными свойствами и ко многим другим.