Организация поиска информации
Информация - Компьютеры, программирование
Другие материалы по предмету Компьютеры, программирование
ляется набором ключевых слов, называемых индексными терминами. Индексные термины используются для индексирования и обобщения содержимого документа. Различные индексные термины отличаются по релевантности, когда используются для описания содержимого документа. Этот эффект отражается в назначении числовых весов каждому индексному термину документа.
Пусть ti - индексный термин, dj - документ, а wi,j?0 - вес, связанный с парой (ti, dj). wi,j определяет качество индексного термина для описания смыслового содержания документа. Каждый документ связан с вектором индексных терминов:
,j=g(dj), где g - это функция, которая вычисляет вес термина ti в документе dj (wi,j=0 обозначает термин ti, который не появляется в dj) и M - это количество индексных терминов.
Веса индексных терминов, как правило, предполагаются независимыми друг от друга. Это означает, что знания о весе wi,j, связанном с парой (ti, dj), ничего не говорят нам о весе wi+1,j связанном с парой (ti+1, dj). Это является упрощением, потому что вхождения индексных терминов в документе взаимосвязаны. Более поздние модели ИП (LSI, pLSA, LDA) в явном виде обращаются к корреляции индексных терминов.
2.1 Булева модель
Булева модель поиска информации - это простая поисковая модель, основанная на теории множеств и булевой алгебре. Значимость индексного термина представлена с помощью двоичного веса:
связан с парой (ti, dj).
Rdj - с набором индексных терминов для документа.- с набором документов для индексного термина.
Запросы определяются как логические выражения над индексными терминами (используя логические операции AND, OR и NOT). Например, Brutus AND Caesar, NOT Calpurnia. Релевантность определяется в виде двоичного свойства документа:
SC(q, dj)=0 или SC(q, dj) = 1.
Пример. Пусть есть коллекция из трех документов:
d1 = [1,1,1]T= [1,0,0]T= [0,1,0]T
В коллекции используются 3 термина. Множества документов, соответствующих терминам:
Rt1 = {d1, d2}, Rt2 = {d1, d3}, Rt3 = {d1}
Тогда результатами запросов будут:
Каждый логический запрос может быть переписан в дизъюнктивной нормальной форме. Например:
= ta ? (tb ? tc) = qdnf = (ta ? tb ? tc) ? (ta ? tb ? tc) ? (ta ? tb ? tc)
Каждая дизъюнкция представляет собой идеальный набор документов. Документ удовлетворяет запросу, если он содержится в терминах дизъюнкции:
= (ta ? tb ? tc)? (ta ? tb ? tc)? (ta ? tb ? tc)
qdnf = (1,1,1)? (1,1,0)? (1,0,0)
SC(q,dj)=
Достоинства булевой модели:
Логические выражения имеют точную семантику.
Используются структурированные запросы.
Для опытных пользователей она интуитивна.
Простой и аккуратный формализм позволял принять ее во многих ранних коммерческих библиографических системах.
Недостатки булевой модели:
Не осуществляется ранжирование. Стратегия поиска основана на двоичном критерии решения, т.е. документ предполагается либо релевантным, либо нерелевантным.
Не просто перевести информационное требование в логическое выражение.
2.2 Векторная модель
Векторная модель представляет документы и запросы в виде векторов в пространстве терминов. Значимость индексного термина представлена вещественным весом.
,j ?0 связан с парой (ti, dj)
Каждый документ представлен вектором в M-мерном пространстве, где M - это количество индексных терминов
Каждый термин представляет собой единичный вектор
указывающий направление i-ой оси. Множество векторов ti, i=1,…M формируют канонический базис для евклидова пространства M. Любой вектор документа dj может быть представлен его разложением по каноническому базису (см. рис.1):
Рисунок 1. Векторное пространство, образованное тремя терминами.
Документы, близкие друг к другу в векторном пространстве, похожи друг на друга. Запрос так же представляется в виде вектора:
Модель векторного пространства вычисляет сходство SC(q, dj) между запросом и каждым документом и составляет ранжированный список документов. Она принимает во внимание документы, которые соответствуют условиям запроса лишь частично. Ранжированный набор найденных документов более эффективен (лучше соответствует информационной потребности пользователя), чем набор документов, найденных булевой моделью. Существуют различные меры, которые могут быть использованы для оценки сходства документов.
.3 Меры подобия
Мера подобия между документами должна отвечать следующим требованиям:
Если d1 рядом с d2, то d2 рядом с d1.
Если d1 рядом с d2, а d2 рядом с d3, то d1 находится недалеко от d3.
Не существует документов ближе к d, чем сам d.
Примеры мер подобия:
Евклидова дистанция.
Косинусное подобие.
Скалярное произведение.
Мера Жаккара.
Коэффициент Дайса.
Мера Шимкевича-Симпсона.
Евклидова дистанция - это длина разностного вектора:
Она может быть преобразована в коэффициент подобия различными способами:
Нужно также решить вопрос нормализации, так как евклидова дистанция, примененная к ненормированным векторам, как правило, делает любой большой документ нерелевантным для большинства запросов, так как запросы обычно имеют короткую длину. Длинные документы будут похожи друг на друга из-за длины, а не из-за темы. Косинусное подо