Методы нечеткого поиска основаны на расширенной булевой модели и теории нечетких множеств . Существует две классические модели нечеткого поиска: смешанная модель Min and Max (MMM) и модель Paice. Обе модели не предоставляют способа оценки веса запроса, однако это учитывается алгоритмом P-норм .
В теории нечетких множеств элемент имеет различную степень принадлежности, скажем d A , к данному множеству A вместо традиционного выбора принадлежности (является элементом/не является элементом).
В MMM [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 и = (A 1 и A 2 и ... и A n )
Сходство запроса и документа в модели МММ вычисляется следующим образом:
SlM(Q или , D) = C или1 * max(d A1 , d A2 , ..., d An ) + C или2 * min(d A1 , d A2 , ..., d An )
SlM(Q и , D) = C и1 * min(d A1 , d A2 , ..., d An ) + C и2 * max(d A1 , d A2 ..., d An )
где C or1 , C or2 — коэффициенты «мягкости» для оператора or , а C and1 , C and2 — коэффициенты мягкости для оператора and . Поскольку мы хотели бы придать максимуму веса документа большую важность при рассмотрении запроса or , а минимуму большую важность при рассмотрении запроса and , то обычно мы имеем 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 или1 > 0,2. В целом, вычислительная стоимость MMM низкая, а эффективность поиска намного лучше, чем у стандартной булевой модели .
Модель Paice [3] является общим расширением модели MMM. По сравнению с моделью MMM, которая учитывает только минимальный и максимальный вес для индексных терминов, модель Paice учитывает все веса терминов при расчете сходства :
где r — постоянный коэффициент, а w di располагается в порядке возрастания для и запросов и в порядке убывания для или запросов. При n = 2 модель Paice показывает такое же поведение, как и модель MMM.
Эксперименты Ли и Фокса [2] показали, что установка r на 1,0 для запросов и и 0,7 для запросов или дает хорошую эффективность поиска. Вычислительная стоимость для этой модели выше, чем для модели MMM. Это связано с тем, что модель MMM требует только определения минимума или максимума набора весов терминов каждый раз, когда рассматривается предложение and или or , что может быть сделано за O(n) . Модель Пейса требует, чтобы веса терминов были отсортированы в порядке возрастания или убывания, в зависимости от того, рассматривается ли предложение and или or . Для этого требуется как минимум алгоритм сортировки 0(n log n) . Также требуется много вычислений с плавающей точкой.
Ли и Фокс [2] сравнили стандартную булеву модель с моделями MMM и Paice с тремя тестовыми наборами, CISI, CACM и INSPEC. Вот представленные результаты для среднего улучшения точности:
Это очень хорошие улучшения по сравнению со Стандартной моделью. MMM очень близка к результатам Paice и P-norm, что указывает на то, что она может быть очень хорошей техникой и является наиболее эффективной из трех.
В 2005 году Канг и др. [4] разработали нечеткую поисковую систему, индексированную по идентификации концепций.
Если мы посмотрим на документы с использованием чистого подхода Tf-idf , даже исключив стоп-слова, то найдутся слова, более релевантные теме документа, чем другие, и они будут иметь одинаковый вес, поскольку имеют одинаковую частоту терминов. Если мы примем во внимание намерение пользователя в запросе, мы сможем лучше взвесить термины документа. Каждый термин может быть идентифицирован как концепция в определенной лексической цепочке, которая передает важность этой концепции для этого документа.
Они сообщают об улучшениях по сравнению с Paice и P-norm по средней точности и полноте для 5 лучших извлеченных документов.
Задрозный [5] пересмотрел модель нечеткого информационного поиска. Он далее расширяет нечеткую расширенную булеву модель следующим образом:
Предложенная модель позволяет учесть как неточность, так и неопределенность, касающиеся представления и поиска текстовой информации.
