Нечеткий поиск
Методы нечеткого поиска основаны на расширенной логической модели и теории нечетких множеств . Существует две классические модели нечеткого поиска: смешанный минимум и максимум (МММ) и модель Пейса. Обе модели не предоставляют способа оценки весов запросов, однако это учитывается алгоритмом P-норм .
Смешанная модель минимума и максимума (МММ) [ править ]
В теории нечетких множеств элемент имеет различную степень принадлежности, скажем d A , к данному множеству A вместо традиционного выбора членства (является элементом/не является элементом).
В МММ [1] с каждым индексным термином связано нечеткое множество. Вес документа по отношению к индексному термину A считается степенью членства документа в нечетком множестве, связанном с A . Степень принадлежности объединения и пересечения в теории нечетких множеств определяется следующим образом:
В соответствии с этим документы, которые должны быть получены по запросу формы A или B связанном с объединением двух множеств A и B. , должны находиться в нечетком множестве , Аналогично, документы, которые должны быть получены по запросу формы A и B , должны находиться в нечетком множестве, связанном с пересечением двух наборов. Следовательно, можно определить сходство документа с запросом or как max(d A , d B ) и сходство документа с запросом and как min(d A , d B ) . Модель MMM пытается смягчить логические операторы, рассматривая сходство запроса и документа как линейную комбинацию минимального и максимального веса документа.
Дан документ D с весами индексных терминов d A1 , d A2 , ..., d An для терминов A 1 , A 2 , ..., An и запросы:
Q или = (A 1 или A 2 или ... или A n )
Q и = (А 1 и А 2 и ... и А н )
сходство запроса и документа в модели МММ вычисляется следующим образом:
SlM(Q или , D) = C or1 * max(d A1 , d A2 , ..., d An ) + C or2 * min(d A1 , d A2 , ..., d An )
SlM(Q и , D) = C and1 * min(d A1 , d A2 , ..., d An ) + C and2 * max(d A1 , d A2 ..., d An )
где C or1 , C or2 — коэффициенты «мягкости» для оператора или , а C and1 , C и 2 — коэффициенты мягкости для оператора и . Поскольку мы хотели бы придать максимальную важность веса документа при рассмотрении запроса или и минимальную большую важность при рассмотрении запроса и , обычно мы имеем C or1 > C or2 и C and1 > C and2 . Для простоты обычно предполагается, что C or1 = 1 - C or2 и C and1 = 1 - C and2 .
Ли и Фокс [2] эксперименты показывают, что наилучшие результаты обычно достигаются при C и 1 в диапазоне [0,5, 0,8] и при C or1 > 0,2. В целом, вычислительные затраты MMM невелики, а эффективность поиска намного выше, чем при использовании стандартной логической модели .
Модель темпа [ править ]
Модель Пейса [3] является общим расширением модели МММ. По сравнению с моделью MMM, которая учитывает только минимальный и максимальный веса для терминов индекса, модель Пейса включает все веса терминов при расчете сходства:
где r — постоянный коэффициент, а w di расположен в порядке возрастания для запросов и и в порядке убывания для запросов или . Когда n = 2, модель Пейса демонстрирует то же поведение, что и модель МММ.
Эксперименты Ли и Фокса [2] показали, что установка r на 1,0 для запросов и и 0,7 для запросов или обеспечивает хорошую эффективность поиска. Вычислительные затраты для этой модели выше, чем для модели МММ. Это связано с тем, что модель MMM требует только определения минимального или максимального набора весов терминов каждый раз, когда and или or рассматривается предложение , что можно сделать за O(n) . Модель Пейса требует, чтобы веса терминов были отсортированы в порядке возрастания или убывания, в зависимости от того, and ли предложение или предложение or рассматривается . Для этого требуется как минимум алгоритм сортировки 0(n log n) . Также необходимо много вычислений с плавающей запятой.
со стандартной логической моделью сравнению по Улучшения
Ли и Фокс [2] сравнил стандартную логическую модель с моделями MMM и Paice с тремя наборами тестов: CISI, CACM и INSPEC. Ниже представлены результаты улучшения средней средней точности:
| СНГИ | CACM | ИНСПЕК | |
|---|---|---|---|
| М-М-М | 68% | 109% | 195% |
| Пейс | 77% | 104% | 206% |
Это очень хорошие улучшения по сравнению со стандартной моделью. МММ очень близок к результатам Пейса и P-нормы, что указывает на то, что это может быть очень хороший метод и наиболее эффективный из трех.
Последние работы [ править ]
В 2005 году Канг и др. . [4] разработали нечеткую систему поиска, индексируемую идентификацией понятий.
Если мы посмотрим на документы с использованием чистого подхода Tf-idf , даже исключив стоп-слова, найдутся слова, более соответствующие теме документа, чем другие, и они будут иметь одинаковый вес, поскольку имеют одинаковую частоту терминов. Если мы примем во внимание намерения пользователя в отношении запроса, мы сможем лучше взвесить условия документа. Каждый термин можно идентифицировать как понятие в определенной лексической цепочке, которая передает важность этого понятия для данного документа.
Они сообщают об улучшениях по сравнению с Paice и P-norm по средней точности и полноте для пяти наиболее популярных документов.
Zadrozny [5] вновь обратился к нечеткой модели поиска информации. Он далее расширяет нечеткую расширенную булевую модель следующим образом:
- принятие лингвистических терминов в качестве весов важности ключевых слов также в документах
- принимая во внимание неопределенность относительно представления документов и запросов
- интерпретация лингвистических терминов при представлении документов и запросов, а также их сопоставление с точки зрения нечеткой логики Заде (исчисление лингвистических высказываний)
- рассмотрение некоторых прагматических аспектов предлагаемой модели, в частности методов индексации документов и запросов.
Предложенная модель позволяет уловить как неточность, так и неопределенность, связанную с представлением и поиском текстовой информации.
См. также [ править ]
Дальнейшее чтение [ править ]
- Фокс, Э.; С. Бетрабет; М. Кошик; В. Ли (1992), Информационный поиск: алгоритмы и структуры данных; Расширенная логическая модель , Prentice-Hall, Inc., заархивировано из оригинала 28 сентября 2013 г. , получено 9 сентября 2017 г.
Ссылки [ править ]
- ^ Фокс, Э.А.; С. Шарат (1986), Сравнение двух методов мягкой логической интерпретации при поиске информации , Технический отчет TR-86-1, Технологический институт Вирджинии, факультет компьютерных наук
- ↑ Перейти обратно: Перейти обратно: а б с Ли, туалет; Э.А. Фокс (1988), Экспериментальное сравнение схем интерпретации логических запросов
- ^ Пейс, CD (1984), Мягкая оценка логических поисковых запросов в системах информационного поиска , Информационные технологии, Res. Дев. Приложения, 3(1), 33-42
- ^ Кан, Бо Ён; Дэ-Вон Ким; Хэ-Юнг Ким (2005), «Поиск нечеткой информации, индексируемый посредством идентификации понятий», Текст, речь и диалог , Конспекты лекций по информатике, том. 3658, Springer Berlin/Heidelberg, стр. 179–186, doi : 10.1007/11551874_23 , ISBN 978-3-540-28789-6
- ^ Задрозный, Славомир; Новацка, Катажина (2009), «Пересмотр модели нечеткого поиска информации», Fuzzy Sets and Systems , 160 (15), Elsevier North-Holland, Inc.: 2173–2191, doi : 10.1016/j.fss.2009.02.012