El'Manuscript '08
Konferencijos
Организационный комитет
Programos komitetas
Konferencijos darbo kryptys
Mokyklos veiklos kryptys ir temos
Pagrindinės datos
Registracija ir taikymas
Dalyvio mokestis
Программа конференции
Список участников
Konferencijos medžiaga
Проекты и ресурсы
Organizacinė Infromacija
Kultūrinė programa
Фотоотчет





Lost Password?
No account yet? Register
We have 3 guests online
RSS-ленты новостей
rss20.gif

Portalo kūrimą rėmė Rusijos humanitarinių mokslų fondas, projektas Nr. 07-04-12140в.

Портал зарегистрирован 05 августа 2010 г. в Федеральной службе по надзору в сфере связи, информационных технологий и массовых коммуникаций (Роскомнадзор) в качестве средства массовой информации, номер свидетельства ЭЛ № ФС 77 - 41581. Учредитель В. А. Баранов. 

(c) "Informacinės technologijos ir rašytinis palikimas", 2008-2016

Расширенная булева модель поиска PDF Print E-mail
Written by: Руслан Владимирович Шарапов, Екатерина Викторовна Шарапова, Тамара Евгеньевна Меркулова   
Четверг, 26 Июнь 2008

icon Тезисы в формате DOC (190 kB 2008-07-12 20:19:48) icon Тезисы в формате PDF (192.79 kB 2008-07-12 20:16:36)

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

В булевой модели запросы пользователей представляют собой логические выражения, в которых слова связаны операторами AND, OR и NOT. Для того чтобы документ был найден, в нем должны содержаться все слова, связанные оператором AND, или хотя бы одно из слов, связанных оператором OR. Не трудно заметить, что при сложных запросах, состоящих из нескольких слов, и большом количестве документов в поисковой базе может наблюдаться некий дисбаланс результатов поиска:

-        список результатов поиска при использовании оператора AND может оказаться слишком коротким, так как из результатов поиска исключаются все документы, в которых отсутствует хотя бы одно из слов запроса;

-        список результатов поиска при использовании оператора OR может оказаться слишком большим, так как в результаты поиска включаются все документы, в которых встречается хотя бы одно из слов запроса.

Кроме того, у булевой модели есть существенный недостаток в ней нет возможности установить веса термов (слов) и, соответственно, нельзя провести ранжирование результатов поиска. По сути, при поиске документы делятся на две группы – соответствующие и несоответствующие запросу. Так, при использовании оператора AND документы, не содержащие по крайней мере одного из слов запроса, являются столь же несоответствующими запросу, как и документы, не содержащие ни одного из слов запроса. Аналогично при использовании оператора OR: документы, содержащие одно из слов запроса, в равной степени соответствуют запросу, как и документы, содержащие все слова запроса.

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

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

Впервые расширенная модель была предложена Дж. Солтоном и Е. Фоксом [Salton, and et. 1983; Baeza-Yates, and et. 1999]. Основная идея состоит в комбинации булевой формулировки запроса и элементов векторной модели. В сущности, предлагается расширить булеву модель элементами векторной модели. Эта модифицированная модель получила название расширенной булевой модели (Extended Boolean Model) [Baeza-Yates, and et. 1999]. В дальнейшем модель была дополнена другими исследователями [Wong, and et. 1988; Paice 1984, Fox, and et. 1986].

Рассмотрим конъюнктивный (оператор AND, пересечение) логический запрос sharapov_fig17.jpg. Согласно булевой модели, если документ содержит только терм kx или терм ky, то он не соответствует запросу так же, как документ, не содержащий ни одного из термов. Однако такой бинарный критерий выбора из двух альтернатив является недостаточно гибким. Аналогичная ситуация наблюдается при дизъюнктивных запросах (оператор OR, объединение).

Если рассматриваются только два слова в запросе (терма), то можно отобразить запросы и документы на двумерной карте (рисунок 1) [Baeza-Yates, and et. 1999]. Документ dj позиционируется в этом пространстве на основе весов wx,j и wy,j, связанных с парами [kx, dj] и [ky, dj]. После проведения нормализации, эти веса будут принимать значения между 0 и 1. Например, эти веса могут вычисляться как TF-IDF коэффициенты (аналогично векторной модели):

wx,j=tfnorm x,j × idfnorm x,

sharapov_fig2.jpg,

sharapov_fig3.jpg,

где tfnorm x,j - нормализованная частота терма kx в документе dj;

idfnorm x - нормализованная инверсная частота документов для терма kx;

tfx,j - частота терма kx в документе dj;

tfmax x,j  - максимальная частота терма kx в документе dj;

idf x - инверсная частота документов для терма kx;

idfmax x – максимальная инверсная частота документов для терма kx;

fx,j - нормализованная частота терма kx в документе dj.

 
sharapov_fig1_kazan08.jpg 

 Рис. 1 Пространство, составленное из двух термов kx и ky

На рисунке видны две интересные особенности.  Во-первых, для дизъюнктивного запроса sharapov_fig4.jpg точка (0,0) является самой нежелательной. Это позволяет считать расстояние от (0,0) как меру подобия запросу qor. Во-вторых, для конъюнктивного запроса sharapov_fig5.jpg точка (1,1) является самой желательной. Это дает возможность считать расстояние от точки (1,1) как меру подобия запросу qand. Кроме того, такие расстояния могут быть нормализованы. В результате меры подобия документа запросу будут выглядеть следующим образом [Baeza-Yates, and et. 1999]:

sharapov_fig6.jpg

sharapov_fig7.jpg

Если веса – логические (то есть sharapov_fig8.jpg), то документ будет располагаться в одном из четырех углов – (0,0), (0,1), (1,0) или (1,1). Тогда значения для sim(qor,d) ограничены 0, 1/ и 1. Аналогично, значения для sim(qand,d) ограничены 0, 1-1/ и 1. Если учесть, что число термов в коллекции документов равно t, булева модель может быть расширена, чтобы рассматривать евклидовы расстояния в t-мерном пространстве.

Проводя обобщение, можно принять теорию векторных норм. Модель p-нормы обобщает понятие расстояния, включающего не только евклидовы расстояния, но и p-расстояния, где 1≤p≤∞ вновь введенный параметр, значение которого определяется во время формирования запроса. Обобщенный дизъюнктивный запрос тогда можно представить как

sharapov_fig9.jpg

Аналогично, обобщенный конъюнктивный запрос можно представить как

sharapov_fig10.jpg

Тогда функции соответствия документов запросу будут

sharapov_fig11.jpg

sharapov_fig12.jpg

 

 

P-норма обладает несколькими интересными свойствами [Baeza-Yates, and et. 1999]. Во-первых, когда p=1, получаем

sharapov_fig13.jpg

 

Во-вторых, при p=∞ можно записать

sim(qor, dj)=max(wi, j)

sim(qand, dj)=min(wi, j)

Таким образом, для p=1 конъюнктивные и дизъюнктивные запросы определяются суммой весов термов в документах, подсчитанных на основе формул подобия в векторном пространстве. Для p=∞ запросы оцениваются согласно терминам нечеткой логики. Изменяя параметр p между 1 и бесконечность, мы можем изменить p-норму, варьируя ранжирование между векторной и булевой моделями. Это весьма хороший аргумент в пользу использования расширенной булевой модели.

Обработка более общих запросов выполняется путем группировки операторов в предопределенном порядке. Например, рассмотрим запрос sharapov_fig14.jpg. Подобие sim(q, dj) между документом dj и этим запросом вычисляется как

sharapov_fig15.jpg

 

 

 

 

Эта процедура может быть применена рекурсивно независимо от числа операторов AND/OR. Еще одна интересная особенность расширенной булевой модели – возможность использования комбинаций различных значений параметра p в том же самом запросе. Например, запрос

sharapov_fig16.jpg

показывает, что k1 и k2 должны считаться как в векторной модели, но k3 должна присутствовать обязательно (то есть конъюнкция интерпретируется как логическая операция).

Надо заметить, что расширенная булева модель ослабляет булеву алгебру, интерпретирующую логические операции в терминах алгебраических расстояний. В этом смысле это – гибридная модель, которая включает свойства и теоретических, и алгебраических моделей.

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

Список литературы

Salton, and et. 1983 – Salton, G. Extended Boolean Information Retrieval. Communications of the ACM / G. Salton, E. Fox, H. Wu. –  1983. – 26(11). – P. 1022-1036.

Baeza-Yates, and et. 1999 – Baeza-Yates, R. Modern information retrieval / R. Baeza-Yates, B. Ribeiro-Neto. – Addison Wesley : ACM Press Books, 1999

Frakes, and et. 1992 – Frakes, W. Information Retrieval: Data Structures & Algorithms / W. Frakes, R. Baeza-Yates. – Prentice-Hall, 1992.

Wong, and et. 1988 – Wong, S. K. M. Extended Boolean Query Processing in the Generalized Vector Space Model / S. K. M. Wong, W. Ziarko, V. V. Raghavan, P. C. N. Wong // Information Systems. – 1988. – 14(1). –  P. 47-63.

Paice 1984 – Paice, C. P. Soft Evaluation of Boolean Search Queries in Information Retrieval Systems / C. P. Paice // Information Technology, Res. Dev. Applications. – 1984. – 3(1). – P. 33-42.

Fox, and et. 1986 – Fox, E. A. Comparison of Two Methods for Soft Boolean Interpretation in Information Retrieval. Technical Report TR-86-1 / E. A. Fox, S. A. Sharat. – Virginia Tech, Department of Computer Science, 1986.

 

An expanded Boolean model for searching

Ruslan V. Sharapov, Ekaterina V. Sharapova, Tamara E. Merkulova

Murom Institute of Vladimir State University, Murom, Russia

This paper considers opportunities for updating Boolean models for retrieval of search results. Information about expanded Boolean models and opportunities for application in information retrieval systems are given.

 
< Prev   Next >