Методы автоматического порождения поисковых эвристик
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?я Lexem[i] Є LexemSet)
Конъюнкция Con ложна на множестве лексем LexemSet, если хотя бы одна лексема из множества лексем конъюнкции {Lexem[i]} не содержится во множестве LexemSet.
Рассмотрим алгоритм построения конъюнкций:
Пусть relevanceConjunction - искомое множество конъюнкций. Первоначально оно пусто.
Программа начинает составлять все возможные уникальные конъюнкции Con[m] размера от 1-го слова до максимального количества слов, заданного экспертом, из множества relevanceLexemSet. При этом программа проверяет, истинность полученной конъюнкции на множестве IrrelevanceLexemSet. Если Con[m] ложна на множестве IrrelevanceLexemSet, то Con[m] добавляется в relevanceConjunction. В противном случае такая конъюнкция отбрасывается.
Таким образом, мы получаем искомую ДНФ (множество relevanceConjunction), в которой каждая конъюнкция истинна на множестве relevanceLexemSet и ложна на множестве IrrelevanceLexemSet. То есть получает система ДНФ, истинную на множестве релевантных текстов и ложную на множестве нерелевантных текстов. Использование полученной ДНФ в качестве набора эвристик - очевидно: каждая найденная конъюнкция является эвристикой.
Пример:
Пусть:
Множество relevanceLexemSet = {A, B, C, D}
Множество IrrelevanceLexemSet = {B, D}
Максимальное количество лексем в конъюнкции = 2.
Тогда:
Искомое множество relevanceConjunction = {A, C, AB, AC, AD, BC, CD}, то есть мы отбросили конъюнкции B, D, BD, которые истинны на множестве IrrelevanceLexemSet.
Следует также отметить, что описанная выше процедура, может быть повторена экспертом при необходимости любое количество раз, а, полученные в результате эвристики будут сохранены в системе.
Благодаря такому подходу, эксперт сможет за несколько шагов найти именно тот набор эвристик, который будет наиболее эффективно улучшать поиск для пары (рубрика, вид ресурс) с точки зрения пертинентности.
Как правило, количество конъюнкций в ДНФ может быть достаточно большим (100-1000 конъюнкций), и нет смысла выводить эксперту все без исключения конъюнкции. Тем более что большинство конъюнкций не будут эффективно решать проблему поиска, описанную выше, так как представляют собой малоинтересные с точки зрения поиска наборы слов.
Поэтому на основании статистики встречаемости полученных эвристик в релевантных текстах, происходит сортировка и последующее отображение эксперту наиболее часто встречающихся эвристик.
При этом эксперт обладает возможностью отредактировать получившийся список и удалить из него лишние, на его взгляд, эвристики.
4.Оценка полученных результатов
После того, как искомый набор эвристик получен, эксперт должен проверить результаты поиска и оценить эффективность полученного набора эвристик с точки зрения пертинентности.
В экспертной системе механизм поиска организован следующим образом:
Система отправляет информационно-поисковой системе (Google, Яндекс) группу запросов. Каждый запрос - эвристика из набора.
Система получает результаты поиска от каждого запроса, ранжирует их и отображает эксперту.
Алгоритм ранжирования устроен следующим образом:
Первичная сортировка текстов происходит по тому же принципу, как были отсортированы тексты информационно-поисковой системой (Google, Яндекс)
Вторичная сортировка происходит по убыванию частоты встречаемости эвристики, которой принадлежит текст.
Следует отметить, что эксперт обладает возможностью просмотреть не только обобщенный список найденных документов, но и результаты поиска для каждой эвристики по отдельности.
Таким образом, применение экспертной системы для автоматического порождения эвристик, позволит эксперту за несколько шагов, гарантированно подобрать искомый набор эвристик, который обеспечит повышение пертинентности результатов поиска в сравнении с другими существующими поисковыми системами применимо к выбранной предметной области.
Рассмотрим пример: Необходимо подобрать эвристики для рубрики черви предметной области Информационная безопасность.
.Первый шаг: поиск текстов
На этом шаге допустим, что эксперт вводит в строку поиска просто слово червь. Естественно, что он получает весьма не удовлетворительную выборку с точки зрения пертинентности.
рис. 3: Результаты поиска текстов
2.Второй шаг: Построение ДНФ
На основе найденных текстов, эксперт запускает процесс построения ДНФ.
В итоге система выдает ему следующий список эвристик:
Червь вредоносный файл
Червь вирус файл
Новость червь файл
Червь вирус
Червь файл
Новость червь
Файл
Как видно, за счет того, что выборка релевантных текстов содержала относительно небольшое количество текстов, в списке есть лишние эвристики (файл, новость, новость файл). Но, во-первых, эксперт может удалить лишние эвристики. А, во-вторых, экспертная система нашла уже те эвристики, которые, скорее всего, смогут вполне удовлетворить информационную потребность пользователя (червь вирус файл, червь вирус, червь файл).
.Проверка полученных результатов
Результаты поиска по полученным эвристикам:
рис. 4: Результаты поиска
Насколько видно, уже сейчас результаты поиска экспертной системой намного превосходят результаты поиска, полученные Яндексом.
При этом следует отметить тот факт, что поскольку экспертная система посылает несколько запросов поисковой системе, то, как правило, количество текстов, удовлетворяющих информационную потребность пользователя в несколько раз больше, за счет того, что резу?/p>