Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,118

ПОИСК И РАНЖИРОВАНИЕ ДОКУМЕНТОВ С ИСПОЛЬЗОВАНИЕМ МУЛЬТИАГЕНТНОЙ СИСТЕМЫ

Иванова Г.С. 1 Андреев А.М. 1 Шоуман М.А. 1
1 Московский государственный технический университет им. Н.Э. Баумана
Информационный поиск – деятельность, направленная на получение информационных ресурсов, релевантных информационным потребностям пользователя, из имеющейся в Интернете коллекции. Количество документов, содержащих требуемую информацию, в том числе в неструктурном виде, непрерывно растет. Соответственно растет и количество документов, находимых по поисковым запросам, что, в свою очередь, приводит к тому, что задача оценки релевантности документов запросу все еще является актуальной. В статье рассматривается модель структуры мультиагентной поисковой системы в виде нечеткого метаграфа. На основе этой модели получена система нечеткого логического вывода, позволяющая ранжировать найденные системой документы по степени их релевантности. Приведены результаты двух экспериментов по оценке релевантности результатов поиска с применением систем нечеткого вывода Мамдани и Сугено.
информационный поиск
мультиагентные системы
модель векторного пространства
нечеткий метаграф
системы нечеткого вывода
1. Иванова Г.С. Автоматический поиск информации с использованием мульти-агентной системы / Г.С. Иванова, А.М. Андреев, В. И. Нефедов, М.А. Шоуман, Е.В. Егорова // Электромагнитные волны и электронные системы. – 2015. – Т. 20 – № 2 . – С. 33–38.
2. Иванова Г.С. Модели объектов задач структурного синтеза // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. – 2006. – № 12. – Режим доступа: http://technomag.edu.ru/doc/62361.html (дата обращения 15.09.2015).
3. Dashore P., Jain S. Fuzzy Metagraph and Hierarchical modeling.//International Journal on Computer Science and Engineering. – 2011. – Vol. 3. – № 1. – P.435–449.
4. Raghavan P., Schütze H., Manning D. Introduction to Information Retrieval // Cambridge University Press. – 2008.
5. Singhal A. Modern Information Retrieval: A Brief Overview // Bulletin of the IEEE Computer Society Technical Committee on Data Engineering. – 2001. – Vol. 4. – P. 35–43.
6. Tan Z. Fuzzy Metagraph and Its Combination with the Indexing Approach in Rule-Based Systems // IEEE transactions on knowledge and data Engineering. – 2006. – Vol.18, – № 6. – P. 829–841.
7. Thirunavukarasu A., Maheswari S. Fuzzy metagraph based knowledge representation of decision support system // International Journal on Computer Engineering and technology. – 2012. – Vol. 3. – P. 157–166.
8. Thirunavukarasu A., Maheswari S. Technical Analysis of Fuzzy Metagraph based Decision Support System for Capital Market // Journal of Computer Science. – 2013. – Vol. 9. – P. 1146–1155.

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

Подавляющее множество документов в сети содержит неструктурированную информацию, а потому выявление степени соответствия документа запросу – задача нетривиальная и предполагает использование интеллектуальных методов. В настоящее время разработано большое количество методов, в том числе интеллектуальных, оценки релевантности результатов информационного поиска [4, 5]. Однако эти методы имеют большую вычислительную сложность, а потому малоприменимы при большом количестве полученных результатов.

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

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

Построение модели мультиагентной интеллектуальной системы информационного поиска

Мультиагентный подход эффективен в том случае, если структура системы и взаимодействие между объектами хорошо проработаны. Рассмотрим функции, которые должна выполнять интеллектуальная система информационного поиска.

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

● ввод ключевых слов;

● поиск в Интернете по ключевому слову;

● извлечение требуемой информации из Веб-источников;

● интеллектуальный анализ добытых текстов;

● сохранение выходных данных в базе данных [1].

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

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

Второй агент – поисковый – отправляет ключевое слово в поисковую машину Google, которая возвращает ссылки, собирая URL доступных веб-сайтов в Интернете, и передает их третьему агенту.

Третий агент – извлечения информации – автоматически извлекает тексты по URL-ссылкам, в том числе большое количество различных неструктурированных текстовых ресурсов, и передает их для дальнейшей обработки.

Четвертый агент – интеллектуальной обработки текстов – извлекает полезную информацию из текста, используя лексемизацию (удаление знаков препинания, специальных символов и замену отступов и других нетекстовых символов одним пробелом) и фильтрацию стоповых слов (удаление слов, которые не относятся к документам). А также вычисляет веса терминов в документах (TF-IDF) [1] для дальнейшей оценки степени релевантности документа.

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

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

Метаграф представляет собой иерархическую структуру, основанную на графе, в которой каждый узел является множеством, имеющим один или более элементов. Эта модель сохраняет все свойства графов [2–3, 6–7].

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

ivanov02.wmf

где ivanov03.wmf – множество операций, осуществляемых в процессе поиска и интеллектуальной обработки документов; ivanov04.wmf – нечеткое множество на X – множество операций, осуществляемых в процессе поиска и интеллектуальной обработки документов с учетом неопределенности ivanov05.wmf, где μ – функция принадлежности, ivanov06.wmf (таблица); ivanov07.wmf – множество сообщений, передаваемых между агентами:

ivanov08.wmf

ivanov09.wmf

ivanov10.wmf

ivanov11.wmf

Каждому агенту в модели соответствует подмножество операций, которые он выполняет:

● интерфейсному агенту – ivanov22.wmf

● поисковому агенту – ivanov23.wmf

● агенту извлечения документов – ivanov24.wmf

● агенту интеллектуальной обработки текстов – ivanov25.wmf

● агенту ранжирования результатов поиска – ivanov26.wmf

Полученный нечеткий метаграф мультиагентной системы информационного поиска показан на рис. 1.

Условные обозначения элементарных операций поиска

Элемент множества

Обозначение

Моделируемая операция

ivanov12.wmf

UI

Ввод ключевого словосочетания через интерфейс пользователя

ivanov13.wmf

GIS

Передача ключевого сочетания Google

ivanov14.wmf

CURL

Получение ссылок на документы

ivanov15.wmf

SURL

Сохранение ссылок

ivanov16.wmf

RD

Извлечение документов по ссылке

ivanov17.wmf

DT

Лексемизация текста документа

ivanov18.wmf

DF

Фильтрация текста документа

ivanov19.wmf

DS

Выделение частей речи в тексте документа

ivanov20.wmf

TW

Вычисление веса каждого термина в документе

ivanov21.wmf

OE

Оценка соответствия документа ключевым словам

Мультиагентная система, построенная по указанной модели, включает систему принятия решения о степени соответствия документа запросу.

Система принятия решений о степени соответствия документа запросу

В основу системы принятия решения о степени соответствия документа запросу, включенной в агент 5, положены системы нечеткого вывода Мамдани и Сугено. Исходными данными для систем нечеткого вывода являются оценки весов соответствия для каждого термина запроса и для каждого документа из найденных [1], рассчитанные агентом 4. Применение при этом интеллектуальной обработки текстов позволяет получить более точные оценки весов терминов.

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

Для получения интегрированной оценки степени релевантности документа di запросу q в эксперименте используем косинусную меру оценки сходства, описанную в [5]:

ivanov27.wmf

где w(tj, di) – вес j-го термина в i-м документе di; w(tj, q) – вес j-го термина в запросе q.

pic_23.tif

Рис. 1. Структура процесса интеллектуального информационного поиска в виде нечеткого метаграфа

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

Экспериментальные исследования применения систем нечеткого вывода Мамдани и Сугено для получения оценок степени релевантности найденных документов запросу

Вычислительный эксперимент был проведен на наборе документов, извлеченных мультиагентной системой по ключевому словосочетанию «Компьютерные науки».

Таким образом, вектор запроса q = (tj), ivanov28.wmf включал два термина (m = 2):

ivanov29.wmf.

С помощью мультиагентной системы было получено множество D документов (примерно 1,5 млн), содержащих заданные термины. Для каждого документа di ∈ D в системе были определены веса терминов t1 и t2 – w(t1, di) и w(t2, di). Веса тех же терминов в запросе были приняты одинаковыми: w(t1, q) = 0,7, w(t2, q) = 0,7.

В системах нечеткого вывода Мамдани и Сугено были использованы правила:

1. Если (w (t1, q) – высокое) и (w(t1, di) – высокое), то (cos (q, di) – высокая оценка).

2. Если (w(t1, q) – низкое) и (w(t1,di) – низкое), то (cos (q, di) – низкая оценка).

3. Если (w(t2, q) – высокое) и (w(t2, di) – высокое), то (cos (q, di) – высокая оценка).

4. Если (w(t2, q) – низкое) и (w(t2, di) – низкое), то (cos(q, di) – низкая оценка).

pic_24.tif

Рис. 2. Функция принадлежности входа w(t2, q)

pic_25.tif

а б

pic_26.tif

в г

Рис. 3. Результаты оценки соответствия документа запросу с использованием системы нечеткого вывода Мамдани: a – оценка для наименее соответствующего документа; б – оценка для наиболее соответствующего документа; в–г – распределение оценок для 35 документов по терминам t1 и t2

В процессе нечеткого вывода типа Мамдани для входных лингвистических переменных w(t1, q), w(t2, q), w(t1, di) и w(t2, di) использовались треугольные функции принадлежности, как показано в примере на рис. 2 (форма функции показана в нотации пакета MATLAB).

В эксперименте с применением системы нечеткого вывода типа Мамдани веса терминов, полученные после интеллектуальной обработки текстов документов, пересчитывались с использованием треугольной функции принадлежности и приведенных выше правил. Далее были рассмотрены первые 35 документов. Расчет балла соответствия для документа, наименее соответствующего запросу из первых 35, показан на рис. 3, а (значение центроида 0,573).

Расчет балла соответствия для документа, наиболее соответствующего запросу, показан на рис. 3, б (значение центроида 0,666). Оценки балла соответствия для остальных 33-х документов распределены в диапазоне значений равном 0,093. Графически распределение результатов вычисления косинусного сходства для 35 документов по двум терминам «Компьютерная», «наука», показаны на рис. 3, в–г.

Во втором эксперименте применялась система нечеткого вывода Сугено. Также были рассмотрены первые 35 документов. Расчет балла соответствия для документа, наименее соответствующего запросу, показан на рис. 4, а (значение центроида 0,714). Расчет балла соответствия для документа, наиболее соответствующего запросу, показан на рис. 4, б (значение центроида 0,999). Оценки балла соответствия для остальных 33-х документов распределены в диапазоне значений равном 0,285, что примерно в 3 раза больше, чем в предыдущем эксперименте. Графически распределение результатов вычисления косинусного сходства для 35 документов по двум терминам «Компьютерная», «наука» показаны на рис. 4, в–г.

Выполненные эксперименты позволяют сделать вывод, что для оценки балла ранжирования документа с использованием метода сходства (косинус) можно использовать оба типа систем нечеткого вывода. Однако система нечеткого вывода Сугено обеспечивает лучшие результаты, чем система Мамдани, поскольку обеспечивает оценку, близкую к оценкам, получаемым аналитическими способами с существенно большей вычислительной сложностью [4, 5].

pic_27.tif

а б

pic_28.tif

в г

Рис. 4. Результаты оценки соответствия документа запросу с использованием системы нечеткого вывода Сугено: a – оценка для наименее соответствующего документа; б – оценка для наиболее соответствующего документа; в–г – распределение оценок для 35 документов по терминам t1 и t2

 

Выводы

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

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

Рецензенты:

Черненький В.М., д.т.н., профессор, заведующий кафедрой «Системы обработки информации и управления», Московский государственный технический университет им. Н.Э. Баумана, г. Москва;

Карпенко А.П., д.ф.-м.н., профессор, заведующий кафедрой «Системы автоматизированного проектирования», Московский государственный технический университет им. Н.Э. Баумана, г. Москва.



Библиографическая ссылка

Иванова Г.С., Андреев А.М., Шоуман М.А. ПОИСК И РАНЖИРОВАНИЕ ДОКУМЕНТОВ С ИСПОЛЬЗОВАНИЕМ МУЛЬТИАГЕНТНОЙ СИСТЕМЫ // Фундаментальные исследования. – 2015. – № 10-3. – С. 489-494;
URL: http://fundamental-research.ru/ru/article/view?id=39243 (дата обращения: 21.11.2018).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.252