VII Международная студенческая научная конференция Студенческий научный форум - 2015

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

Анализируя существующие решения-аналоги, отметим, что к ним относятся все известные веб-поисковики (Google, Yahoo, Baidu, Yandex), Apache Lucene. При этом отметим некотрые ограничения, присущие рассмотренным решениям:

• Поисковый запрос для текстовых материалов ограничен строкой поиска

• Отсутствует возможность определения тематики запроса в виде онтологии

• Нельзя установить важность каждого термина относительно других

Целью данной работы является разработка программы, представляющей собой мультиагентную систему(МАС), осуществляющую сбор в сети Интернет данных из размещенных в ней документов и получение на основе заданной пользователем онтологии наиболее релевантных документов, с учетом веса терминов.

В процессе разработки МАС необходимо решить следующие задачи:

• построить базу данных для хранения необходимой информации,

• разработать агентов для веб-поиска (веб-пауков), индексации (индексаторов), взаимодействия с базой данных и обработки пользовательского запроса;

• вычислять на основе пользовательского запроса релевантность заданных документов;

• построить индекс для эффективного поиска документов по заданному пользователем запросу

Введем некоторые определения, используемые в дальнейшем для описания предметной области.

Информационный поиск (Informationretrieval)

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

Основные этапы поиска:

• определение (уточнение) информационной потребности и формулировка информационного запроса;

• определение совокупности возможных держателей информационных массивов (источников);

• извлечение информации из выявленных информационных массивов;

• ознакомление с полученной информацией и оценка результатов поиска.

Поисковый робот (веб-паук)

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

Поисковый индекс

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

Релевантность

Семантическое соответствие поискового запроса и поискового образа документа (может быть выражено численно).

Интеллектуальный агент

Программа, самостоятельно выполняющая задание, указанное пользователем, в течение длительных промежутков времени.

Онтология

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

КРАТКАЯ ТЕОРИЯ

Рассмотрим основные математические методы, используемые для реализации приложения.

Обработка онтологии

Термины в онтологии связаны друг с другом отношениями: «суперкласс — подкласс» или от общего к частному. Для определения коэффициента веса термина из онтологии используется следующий подход:

Для каждого термина в онтологии высчитывается количество его суперклассов (C_SUPER) и общее число суперклассов и подклассов термина (C_TOTAL).

Тогда коэффициент веса термина

Таким образом, больший вес в запросе имеют более конкретные термины.

Обработка полученных терминов

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

Пусть RV - область слова после первой гласной или конец слова, если гласных больше нет.

R1 - область слова после первой негласной после гласной или конец слова если такой негласной нет.

R2 - область слова после первой негласной после гласной в R1 или конец слова если такой негласной нет.

Например, для слова "противоестественный":

RV - "тивоестественный", R1 - "ивоестественный", R2 - "оестественный".

Таким образом, алгоритм работает только в области RV.

Алгоритм Портера

Если в слове есть хотя бы одна гласная

Найти RV

1.Если RV заканчивается на суффикс деепричастия совершенного вида

Удалить этот суффикс

Перейти к шагу 2

Иначе если RV заканчивается на возвратный суффикс глагола

Удалить этот суффикс

Если RV заканчивается на суффикс причастия или прилагательного

Удалить этот суффикс

Перейти к шагу 2

Если RV заканчивается на суффикс глагола

Удалить этот суффикс

Перейти к шагу 2

Если RV заканчивается на суффикс существительного

Удалить этот суффикс

Перейти к шагу 2

2.Если RV заканчивается на "и", то удалить ее.

3.Если R2 заканчивается на "ост" или "ость", то удалить их

4.Если RV заканчивается на "нн", то убрать одну "н"

или если RV заканчивается на "ейше", "ейш", то убрать их и убрать одну "н"

или если RV заканчивается на "ь", то убрать его.

Инвертированный индекс

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

Тогда инвертированный индекс - структура данных, в которой для каждого слова коллекции документов в соответствующем списке перечислены пары вида . Где - номер документа - число повторений слова t в документе d. Также хранится количество документов, в которых встречается слово или длина списка

Применение инвертированного индекса позволяет за приемлемое время производить поиск и определение релевантности.

Оценка релевантности

Для оценки релевантности документов имеющимся терминам применялась векторная модель.

d_j = (w_1j, w_2j, …, w_nj)

где d_j — векторное представление j-го документа, w_ij — вес i-го термина в j-м документе, n — общее количество различных терминов во всех документах коллекции.

Располагая таким представлением для всех документов, можно находить расстояние между точками пространства и тем самым решать задачу подобия документов — чем ближе расположены точки, тем больше похожи соответствующие документы.

Большинство функций вычисления меры сходства в векторной модели используют следующие статистические величины в различных комбинациях.

- частота термина t в документе d

- частота термина t в запросе q

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

- частота термина t в коллекции документов

N - число документов в коллекции

n - число терминов в коллекции

Все эти величины комбинируются таким образом, чтобы:

1) Меньший вес имели термины, встречающиеся в большом количестве документов

2) Больший вес имели термины, встречающиеся много раз в одном документе

3) Меньший вес имели документы, содержащие большое количество терминов

Классической формулировкой меры сходства в векторной модели является косинус угла между вектором запроса и вектором документа .

В качестве метода вычисления меры сходства использовалась функция TF-IDF (term frequency - inverse document frequency, частота термина - обратная частота документа)

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

для данного запроса является константой, тогда мера сходства может быть вычислена как

Алгоритм определения релевантности

Для каждого документа d

Выделить сумму

Для каждого термина в запросе

Вычислить и умножить его на - коэффициент веса термина

Для всех пар в инвертированном индексе для данного

Вычислить

Вычислить вектор

Для всех

Вычислить

Упорядочить документы по убыванию

Описание алгоритма функционирования программы

Программа выполнена в виде мультиагентной системы — системы взаимодействующих интеллектуальных агентов.

 

Внешняя среда

пользователь

 

 

пользовательский интерфейс

 

 

Система поиска

 

 

агент-обработчик запросов

 

 

агент-посредник с БД

 

 

индексатор 1

 

 

индексатор 2

 

 

индексатор 3

веб-паук 1

 

 

веб-паук 2

 

 

веб-паук 3

 

Рис.1 Архитектура приложения

Рис.1 Архитектура мультиагентного приложения

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

Как только в базе данных появляются записи — индексеры просят у агента БД полученные веб-пауками данные. Получив данные, индексеры возвращают инвертированный индекс агенту БД для записи его в базу.

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

ID документа

ID слова

 

ID слова

 

 

ID

документа

 

Рис.2 Архитектура базы данных

Описание метода организации входных и выходных данных

Входными данными являются:

1. URL на первоначальный сайт для поиска. Например, http://hse.ru. Для более обширного поиска по сети Интернет - рекомендуется ссылка на сайт со статистикой посещаемости (http://liveinternet.ru например).

2. Онтология в формате RDF/XML с расширением .OWL

Рис. 3 Пример онтологии

Выходными данными являются собственно ссылки на документы в сети Интернет, отсортированные по убыванию релевантности.

Программа написана целиком на языке Java.

Для реализации агентов был использован фреймворк с открытым исходным кодом Java AgentDevelopment Environment (JADE). Выбор именно этого средства обусловлен тем, что он написан на языке Java и наследует все его преимущества, главным из которых является кроссплатформенность.

Для хранения данных использовалась база данных Derby (JavaDB), так как она поставляется в комплекте с Java Development Kit и доступна пользователям с установленной Java.

При чтении файлов онтологии использован пакет с открытым исходным кодом Apache Jena, который также написан полностью на Java.

Выделение ссылок из Интернет документов является крайне важным для производительности системы процессом, поэтому была использована высоко оптимизированная библиотека с открытым исходным кодом jSoup, написанная на Java.

Было проведено испытание работоспособности программы

1.  
   1.  
      •  

        1. Проверка загрузки онтологии. Если загрузка онтологии прошла нормально, то пользователь увидит ее абсолютный путь

1.  
   1.  
      •  

        1. Проверка управлением агентами. При нажатии на "запустить", "остановить", "пауза", "продолжить" программа должна выполнить соответствующие действия. Показателем верности работы этой части является блокировка клавиш для предотвращения ошибок. Например при нажатии на "пауза" пользователь увидит следующее:

1.  
   1.  
      •  

        1. Через 35 секунд пользователь получает результат работы программы - ссылки на документы и уведомление о том, что программа выдала результат

1.  
   1.  
      •  

        1. При переходе по найденным ссылкам стандартный браузер системы пользователя должен открыть сам источника

Список источников и литературы

1. Justin Zobel and Alistair Moffat "Inverted Files for Text Search Engines"; 2006 год.

2. Buttcher and Stefan "Information Retrieval: Implementing and Evaluating Searсh Engines"; 2010 год.

3. R. Goyal, V.Gupta, V.Sharma, P.Mittal; “Ontology based web retrieval”; 2007 год

4. wikipedia.org

5. M.F.Porter "An algorithm for suffix stripping"; 1980 г.

Код для цитирования: Скопировать