Методы автоматического порождения поисковых эвристик
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
ySQL.
3.2Принцип работы экспертной системы
Очевидно, что программная система самостоятельно не сможет понять, что тот или иной документ соответствует информационной потребности пользователя. Но что если человек, а в данном случае эксперт, подскажет ему, какие тексты относятся к выбранной тематике, а какие нет. Тем самым, эксперт обучит систему отличать тексты, соответствующие выбранной теме от несоответствующих текстов. В этом и заключается основной принцип работы экспертной системы по автоматическому подбору эвристик.
Рассмотрим поподробнее, каким же образом этот принцип реализован в экспертной системе.
Алгоритм подбора эвристик для пары (рубрика, ресурс) в экспертной системе состоит из следующих этапов:
.Обучение экспертной системы
.Автоматическое построение набора эвристик
.Оценка полученных результатов поиска
3.3Обучение экспертной системы
Обучение экспертной системы происходит независимо для каждой пары (рубрика, вида ресурса).
Введем следующие определения, используемые в процессе обучения экспертной системы:
Релевантный текст - это текст, соответствующий выбранной тематике пары (рубрика, вид ресурса). Следовательно, релевантный текст удовлетворяет информационную потребность пользователя в выбранном разделе знаний.
Нерелевантный текст - это текст, несоответствующий выбранной тематике пары (рубрика, вид ресурса). Следовательно, релевантный текст не удовлетворяет информационную потребность пользователя в выбранном разделе знаний.
Таким образом, процесс обучения экспертной системы основан на определении экспертом релевантных и нерелевантных текстов по отношению к выбранной тематике пары (рубрика, вид ресурса).
Алгоритм обучения экспертной системы:
.Эксперт выбирает рубрику и вид ресурса
.Эксперт вводит любой запрос в поисковую систему, который на его взгляд адекватен выбранной тематике
.Экспертная система посылает запрос информационно-поисковой системе (Google, Яндекс) и отображает результаты поиска эксперту
.Эксперт на основании субъективных критериев выбирает из результатов поиска релевантные и нерелевантные тексты и сохраняет их в системе
При необходимости, эксперт может неограниченное количество раз повторить процесс обучения. Система сохраняет все отобранные экспертом тексты и позволяет при необходимости редактировать и удалять их.
Как только эксперт решит, что обучающая выборка текстов, на его взгляд полна, то он может запустить автоматический подбор эвристик.
3.4Логические методы автоматического подбора эвристик
Автоматический подбор эвристик основан на логических методах извлечения из обучающей выборки текстов формулы логики высказываний. Главной задачей данной формулы является отделение множества релевантных текстов от множества нерелевантных текстов.
В качестве формулы, разделяющей два множества текстов, решено было использовать дизъюнктивную нормальную форму (ДНФ).
Дизъюнктивная Нормальная Форма (ДНФ) - это дизъюнкция элементарных конъюнкций и их отрицаний [14].
Теорема: Любая формула логики высказываний может быть представлена в виде дизъюнктивной нормальной формы [14].
В соответствии с данной теоремой, можно утверждать, что любой набор формул логики высказываний можно преобразовать в ДНФ.
Пропозициональной переменной в ДНФ является утверждение о том, что последовательность символов встречается в релевантном тексте. А каждая конъюнкция построена таким образом, что она будет истинна на множестве релевантных текстов и ложна на множестве нерелевантных текстов. Следует заметить, что невозможно найти единственную конъюнкцию, которая бы разделяла два множества текстов. Именно поэтому в качестве формулы логики высказываний была выбрана ДНФ.
Рассмотрим алгоритм построения ДНФ:
.Анализ релевантных и нерелевантных текстов
Пусть {relevanceText[i]} - набор релевантных текстов для пары (рубрика, ресурс), а {IrrelevanceText[j]} - набор нерелевантных текстов для пары (рубрика, ресурс).
В процессе анализа текстов для каждого текста (релевантного и нерелевантного) система получает набор лексем со статистикой встречаемости в тексте:
{relevanceTextLexem[i]} - набор лексем для i-го релевантного текста со статистикой встречаемости лексемы в i-ом релевантном тексте.
{IrrelevanceTextLexem[j]} - набор лексем для j-го нерелевантного текста со статистикой встречаемости лексемы в j-ом нерелевантном тексте.
В качестве лексем могут выступать все части речи в нормальной форме, кроме предлогов, союзов, местоимений, частиц и междометий.
.Построение множества релевантных лексем
На этом этапе программа формирует из наборов {relevanceTextLexem[i]} каждого i-го релевантного текста, множество уникальных релевантных лексем (relevanceLexemSet) со статистикой встречаемости в релевантных текстах.
.Построение множества нерелевантных лексем
На этом этапе программа формирует из наборов {IrrelevanceTextLexem[j]} каждого j-го нерелевантного текста, множество уникальных релевантных лексем (IrrelevanceLexemSet) со статистикой встречаемости в нерелевантных текстах.
.Построение конъюнкций
Для описания алгоритма построения конъюнкций введем следующие утверждения:
Конъюнкция Con - это набор лексем Lexem[i] (Con = Lexem[1] & Lexem[2] & … Lexem[m])
Конъюнкция Con истинна на множестве лексем LexemSet, если все лексемы конъюнкции {Lexem[i]} содержатся во множестве лексем LexemSet. (То есть Con истинна на множестве LexemSet, если для любого i | Lexem[i] Є Con, выполняет?/p>