О сервисе WebGround

Ваша тема


Новости сайта

Литература

обложка книгиИнтернетика. Навигация в сложных сетях: модели и алгоритмы
Большакова Е.И., Клышинский Э.С., Ландэ Д.В., Носков А.А., Пескова О.В., Ягунова Е.В. Автоматическая обработка текстов на естественном языке и компьютерная лингвистикаАвтоматическая обработка текстов на естественном языке и компьютерная лингвистика (pdf)
Ягунова Е.В., Макарова О.Е., Антонова А.Ю., Соловьев А.Н. Разные методы компрессии в исследовании понимания новостного текстаРазные методы компрессии в исследовании понимания новостного текста (pdf)
Крылова И.В, Пивоварова Л.М., Савина А.В., Ягунова Е.В. Исследование новостных сегментов российской «снежной революции»: вычислительный эксперимент и интуиция лингвистовИсследование новостных сегментов российской «снежной революции»: вычислительный эксперимент и интуиция лингвистов (pdf)
Ягунова Е.В. Исследование перцептивной устойчивости фонем как элементов речевой цепиИсследование перцептивной устойчивости фонем как элементов речевой цепи (pdf)
Ягунова Е.В. Вариативность структуры нарратива и разнообразие стратегий пониманияВариативность структуры нарратива и разнообразие стратегий понимания (pdf)
Ягунова Е.В., Пивоварова Л.М. Экспериментально-вычислительные исследования художественной прозы Н.В. ГоголяЭкспериментально-вычислительные исследования художественной прозы Н.В. Гоголя (pdf)
Ягунова Е.В. Вариативность стратегий восприятия звучащего текстаВариативность стратегий восприятия звучащего текста (pdf)
Ягунова Е.В. Спонтанный нарратив у детей и у взрослыхСпонтанный нарратив у детей и у взрослых (pdf)
Ягунова Е.В. Исследование избыточности русского звучащего текстаИсследование избыточности русского звучащего текста (pdf)
Ягунова Е.В. Фонетические признаки опорных сегментов и восприятие русского текстаФонетические признаки опорных сегментов и восприятие русского текста (pdf)
Ягунова Е.В. Коммуникативная и смысловая структура текста и его восприятиеКоммуникативная и смысловая структура текста и его восприятие (pdf)
Ягунова Е.В. Где скрывается смысл бессмысленного текста?Где скрывается смысл бессмысленного текста? (pdf)
Ягунова Е.В. Эксперимент в психолингвистике: Конспекты лекций и методические рекомендацииЭксперимент в психолингвистике: Конспекты лекций и методические рекомендации (pdf)
Ягунова Е.В. Теория речевой коммуникацииТеория речевой коммуникации (pdf)
Антонова А.Ю., Клышинский Э.С., Ягунова Е.В. Определение стилевых и жанровых характеристик коллекций текстов на основе частеречной сочетаемостиОпределение стилевых и жанровых характеристик коллекций текстов на основе частеречной сочетаемости (pdf)
Ягунова Е.В. Эксперимент и вычисления в анализе ключевых слов художественного текстаЭксперимент и вычисления в анализе ключевых слов художественного текста (pdf)
Ягунова Е.В. Ключевые слова в исследовании текстов Н.В. ГоголяКлючевые слова в исследовании текстов Н.В. Гоголя (pdf)
Пивоварова Л.М., Ягунова Е.В. Информационная структура научного текста. Текст в контексте коллекцииИнформационная структура научного текста. Текст в контексте коллекции (pdf)
Савина А.Н., Ягунова Е.В. Исследование коллокаций с помощью экспериментов с информантамиИсследование коллокаций с помощью экспериментов с информантами (pdf)
Ягунова Е.В., Пивоварова Л.М. От коллокаций к конструкциямОт коллокаций к конструкциям (pdf)
Пивоварова Л.М., Ягунова Е.В. Извлечение и классификация терминологических коллокаций на материале лингвистических научных текстовИзвлечение и классификация терминологических коллокаций на материале лингвистических научных текстов (pdf)
Julia Kiseleva. Grouping Web Users based on Query LogGrouping Web Users based on Query Log (pdf)
Julia_Kiseleva_Unsupervised_Query_Segmentation_Using_Click_Data_and_Dictionaries_Information.pdfUnsupervised Query Segmentation Using Click Data and Dictionaries Information (pdf)
Четыре лекции о методе
Начала предметного анализа методов (на примере метода Ф.Бэкона)
Вариативность стратегий восприятия звучащего текста
Извлечение и классификация коллокаций на материале научных текстов. Предварительные наблюдения
Природа коллокаций в русском языке. Опыт автоматического извлечения и классификации на материале новостных текстов
Войтишек А. Повторы. Лирические рефреныПовторы. Лирические рефрены (pdf)
Войтишек А. Новое. Лирические рефреныНовое. Лирические рефрены (pdf)
Войтишек А. Всё об одном и том жеВсё об одном и том же. 500 лирических рефренов к 50-летию (pdf)
Войтишек А. Тысяча-часть-1Тысяча-часть-1 (pdf)
Войтишек А. Тысяча-часть-2Тысяча-часть-2 (pdf)
Войтишек А. АлфавитАлфавит (pdf)

2.1. Булева модель поиска

 

2.1.1. Классическая булева модель

 

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

В рамках булевой модели документы и запросы представляются в виде множества термов - ключевых слов и устойчивых словосочетаний. Каждый терм представлен как булева переменная: 0 (терм из запроса не присутствует в документе) или 1 (терм из запроса присутствует в документе). При этом весовые значения терма в документе принимает лишь два значения: .

В булевой модели запрос пользователя представляет собой логическое выражение, в котором термы связываются логическими операторами конъюнкции (AND, ), дизъюнкции (OR, ) и отрицания (NOT, ). Известно, что любое логическое выражение можно представить дизъюнкцией некоторых выражений, соединенных между собой операцией конъюнкции (дизъюнктивной нормальной формой, ДНФ - dnf).

Покажем, как на практике запрос, составленный из логических операторов и скобок, определяющих приоритет операторов, приводится к ДНФ. Рассмотрим пример из [68] – запрос:  Если сопоставить множествам документов, содержащих термы из запроса  и  соответствующие диаграммы Эйлера (рис. 3), то легко можно видеть, что исходный запрос эквивалентен запросу  , т.е. дизъюнктивная нормальная форма запроса примет вид: , где каждая из двоичных компонент ассоциируется с  или  (или их отрицаниями), а запятая между двоичными компонентами – с операциями конъюнкции.

         Рис. 3. Три конъюнктивных компоненты запроса

 

В булевой модели запрос – это булево выражение. Так как оно приводится к дизъюнктивной нормальной форме, то можно записать:

 ,

где  - -я конъюнктивная компонента формы запроса . Тогда мера близости документа  и запроса   -   (от англ. – similarity, близость) в булевой модели определяется выражением:

1

То есть  принимает значение 1, если существует такая конъюнктивная компонента , входящая в дизъюнктивную нормальную форму , что инверсная функция  каждого терма  данной конъюнктивной компоненты совпадает с этой же инверсной функцией для документа . В противном случае  оказывается равной 0.

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

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

-         текстовой, содержащей текстовую часть всех документов;

-         указателей текстов, которая включает указатели на местонахождение документов в текстовой таблице;

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

-         инверсной, содержащей списки номеров документов и координаты отдельных слов в документах.

Поиск по слову в базе данных системы такой архитектуры осуществляется в соответствии с алгоритмом:

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

         2. Происходит обращение к инверсной таблице, по которой определяются номера документов, содержащих данное слово, и координаты всех вхождений слова в текстах базы данных.

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

         4. По номеру документа происходит прямое обращение к фрагменту текстовой таблицы – документу, после чего следует вывод найденного документа.

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

 

2.1.2. Расширенная булева модель

 

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

Для того чтобы устранить этот недостаток и вместе с тем использовать вычислительные преимущества булевой модели, Г. Солтоном (G. Salton), Э.А. Фоксом (E. Fox) и Г. Ву (H.Wu) в 1983 году была предложена расширенная булева модель [130].

В соответствии с этой моделью, каждому терму приписывается вес - значение из интервала [0, 1]. Пусть  - массив документов, в документ  входят термы  и . Тогда парам и  ставятся в соответствие весовые значения  и . Эти значения могут быть определены, например, по формуле:

где  - нормализованная частота терма   в документе , а   - величина, обратная нормированному количеству документов во всем массиве (инверсная частота), содержащих терм .

 

Герхард Солтон (1927-1995)

 

Вместо документа в рамках модели рассматривается  вектор из  термов (в простейшем  случае – двух) , который также можно рассматривать  как точку в квадрате [0, 1] x [0, 1]. Близость между документами можно интерпретировать как некоторое нормированное расстояние между соответствующими точками.

В соответствии с расширенной булевой моделью вводятся меры близости между документом и запросом для двух типов запросов:  и   следующим образом:

        

 Если еще более расширить модель и предположить, что соответствующие термы могут  иметь вес в запросе, соответственно, a и b, то определяется:

           

В рассмотренных выше случаях использовалась  модель степени 2, которая легко обобщается до модели степени , где . В этом случае предполагается, что запросы состоят из  термов, соединенных обобщенными операторами дизъюнкции () и конъюнкции () степени :  и  . При этом вводится такое определение близости этих запросов и документа:

Очевидно,  что для   справедливо:

При  будет   выполняться:

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

Например, в случае, если запрос представляет собой выражение,   то выполняется:

  

 

2.1.3. Модель нечеткого поиска

 

Теория нечетких множеств (Fuzzy set theory), предложенная Л.А. Заде (L.A. Zade), расширяющая классическую теорию множеств,  основывается на той идее, что функция принадлежности элемента множеству может принимать произвольные значения в интервале [0, 1], а не только  0 или 1 [18].

Лотфи А. Заде

 

По определению, нечетким множеством (fuzzy set)  на универсальном множестве  (любой природы) является совокупность пар , где  степень принадлежности элемента  нечеткому множеству . Степень принадлежности - это число из диапазона [0, 1]. Чем выше степень принадлежности, тем в большей мере элемент  соответствует свойствам нечеткого множества. Функцией принадлежности называется функция, которая позволяет вычислить степень принадлежности произвольного элемента универсального множества к нечеткому множеству.

Пусть  и  - два нечетких множества над универсальным множеством  , а  дополнение  до  и . Функцию принадлежности  можно  определить, например, следующим образом:

Л. Заде ввел также понятия носителя, высоты и точки перехода нечеткого множества [18]. Носителем  нечеткого множества  называется множество таких точек , для которых величина  положительна. Высотой нечеткого множества  называется величина . Точкой перехода нечеткого множества  называется такой элемент множества , степень принадлежности которого множеству  равна  1/2.

В качестве примера,  также предложенного в [18], рассматривается универсальное множество , представляющее собой интервал [0, 100], и переменная  принимающая значения из этого интервала, интерпретируемая как «возраст». При этом нечеткое подмножество универсального множества ,   обозначаемое термином «старый», можно задать функцией принадлежности вида (рис. 4):

В этом примере носителем нечеткого множества «старый» является интервал [50, 100], высота множества «старый» близка к 1, а точкой перехода является значение   (рис. 4). Таким образом, говоря простым языком, если возраст человека составляет 55 лет, то его соответствие понятию «старый» составляет 0.5, а если 70, то близко к 0.9. Человека же моложе 50 лет () вообще нельзя назвать старым. Заметим, что функция принадлежности выбиралась из субъективных представлений о том, с какого возраста начинается старость.

В модели нечеткого поиска каждый терм запроса рассматривается как нечеткое множество, а каждый документ рассматривается по степени принадлежности этому множеству. При этом рассматривается матрица взаимосвязей термов , элемент которой  определяет взаимосвязь между термами  с индексами  и :

где  - количество документов, содержащих терм ,  - количество документов, содержащих терм , а  - количество документов, содержащих оба терма.

 

Рис. 4. Функция принадлежности нечеткого множества, определяемого значением «старый»

 

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

Документ  ассоциируется с м термом , если его собственные термы ассоциируются с . Если хотя бы один терм  из  строго ассоциируется с термом с индексом  (т.е.  ), то  и терм  является «хорошим» нечетким индексом документа . Если же это не так и можно считать, что , то  заменяется алгебраической суммой  (что вполне оправдано для большого словаря). Кроме того, вместо функции  при вычислении функции принадлежности в случае реализации оператора дизъюнкции между разными термами также применяется суммирование, что также  является некоторым огрублением изначально определенной модели. Для вычисления конъюнкции, соответственно, используется произведение элементов .

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

где  - -я конъюнктивная компонента,  - количество конъюнктивных компонент .

Соответственно, функция принадлежности    документа  нечеткому множеству  соответствующему запросу  (и рассматриваемая как параметр для ранжирования релевантных документов),  вычисляется следующим образом:

Мебель из массива мебельный хаб мебель из массива.