close

Вход

Забыли?

вход по аккаунту

?

uploaded 0C54292717

код для вставкиСкачать
На правах рукописи
Хорошко Максим Болеславович
РАЗРАБОТКА И МОДИФИКАЦИЯ МОДЕЛЕЙ И
АЛГОРИТМОВ ПОИСКА ДАННЫХ В INTERNET/INTRANET
СРЕДЕ ДЛЯ УЛУЧШЕНИЯ КАЧЕСТВА ПОИСКА
Специальность 05.13. 17 – «Теоретические основы информатики»
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата технических наук
Новочеркасск – 2013
2
Работа выполнена на кафедре «Информационные и измерительные системы и
технологии» ФГБОУ ВПО ЮРГПУ(НПИ) им М.И. Платова.
Научный руководитель
кандидат технических наук, доцент
Воробьев Сергей Петрович
Официальные оппоненты
Ромм Яков Евсеевич
доктор технических наук, профессор,
ФГБОУ ВПО «Таганрогский
государственный педагогический
институт имени А.П. Чехова»,
заведующий кафедрой информатики
Шестаков Сергей Александрович
кандидат технических наук,
ООО «Прог-Форс»,
директор компании
Ведущая организация
ФГВОУ ВПО «Военная академия
связи имени Маршала Советского
Союза С.М.Буденного»
Министерства обороны Российской
Федерации, г. Санкт – Петербург
Защита состоится «27» декабря 2013 г. в 10:20 на заседании диссертационного
совета Д 212.208.21 Южного федерального университета по адресу: 347928,
г. Таганрог, пер. Некрасовский, 44, ауд. Д- 406.
С диссертацией можно ознакомиться в Зональной научной библиотеке
Южного федерального университета по адресу: 344000, г. Ростов-на-Дону,
ул. Пушкинская, 148.
Автореферат разослан «25» ноября 2013 г.
Ученый секретарь
диссертационного совета
Д 212.208.21,
доктор технических наук,
профессор
Боженюк А.В.
3
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность проблемы. Объемы обрабатываемой электронной информации
нарастают большими темпами – этому способствует активное внедрение
мультимедиа, широкое распространение корпоративных и глобальных сетей, отказ
большинства предприятий от бумажного документооборота и переход на
автоматизированные системы управления предприятием. В подобной ситуации резко
возросла потребность в системах поиска и анализа данных, а также возник спрос на
интеллектуализацию информационно-поисковых систем (ИПС).
В настоящее время работает ряд авторитетных международных конференций,
посвящённых обсуждению вопросов информационного поиска, например, таких как:
TREC (Text Retrieval Conference) – серия конференций, сконцентрированных на
исследовании различных областей информационного поиска и их задач. Она
поддерживается National Institute of Standards and Technology (NIST) и Association of
Religion Data Archives (ARDA), расположенных в США, начиная с 1992. Целью TREC
является поддержка исследований сообщества информационного поиска с помощью
предоставления инфраструктуры, необходимой для развития его технологий; WWW
(World Wide Web) Conference – специально организованная конференция для
решения задач, связанных с Интернет.
Из Российских конференций, посвященных вопросам информационного
поиска, нужно отметить ежегодную всероссийскую конференцию «Электронные
библиотеки» (RCDL). Кроме того, существуют коммерческие организации,
занимающиеся не только вопросами исследований, но и внедрением
информационных технологий, это такие известные организации как Яндекс, Рамблер,
Апорт, Галактика-Зум, ABBYY-FTR, AOT и др.
Высокий авторитет конференций TREC, WWW Conference и участие в них
ведущих
исследовательских
коллективов
и
разработчиков
технологий
информационного поиска во многом определяет приоритетные направления
исследований и задает общие принципы развития поисковых систем.
Ряд авторитетных исследователей внесли своими научными трудами
значительный
вклад
в
развитие
информационно-поисковых
систем:
И.С. Некрестьянов, И.E. Кураленок, В.Ю. Добрынин, А.Г. Дубинский, А.Е. Ермаков,
М.Р. Когаловский, А.В. Сокирко, G. Salton, A. Singhal, M. Mitra, S. Lawrence, P. Foltz,
E. Fox, J. Cho, R. Baeza-Yates, K. Tajima, C. Van Rijsbergen, L. Gravano, J., J. Sparck, D.
Carmel, S. Brin, L. Page, A. Singhal., T. Haveliwala.
Существует достаточно широкий спектр предлагаемых решений в области
информационного поиска, начиная от построения глобальных распределенных
информационных структур и поисковых систем, заканчивая элементарными на
первый взгляд вопросами анализа документов при помощи латентно семантического
анализа. Все они, безусловно, важны и полезны при решении своих специфических
задач. Тем не менее, именно от методов ранжирования документов во многом зависит
эффективность существующих поисковых систем. Но современные корпоративные
информационно-поисковые системы, в основе которых по большей степени лежит
4
полнотекстовый поиск и классический алгоритм ранжирования не учитывают
индивидуальность каждой коллекции документов, необходимости подстраиваться
под каждый запрос в зависимости от его типа и длины.
Диссертационная работа выполнена в рамках научного направления ФГБОУ
ВПО ЮРГПУ(НПИ) им М.И. Платова «Теория, принципы и технологии построения
информационно-вычислительных и измерительных систем», госбюджетной темы
7.05 «Разработка теории, методов оптимизации функциональной и программнотехнической платформы корпоративных информационных систем» (Утверждено
решениями ученого совета от 25.04.2001г. и 15.05.2003г).
Диссертационная работа посвящена вопросам повышения качества результатов
поиска в современной информационной среде.
Целью диссертационной работы является модификация и исследование
математических моделей и технологий информационного поиска в корпоративных
информационных системах путем изменения функции вычисления релевантности,
что позволяет увеличить партинентность результатов поиска, а также снизить время
индексации путем реорганизации хранения индексного файла.
Для достижения поставленной цели решаются следующие задачи:
1. Теоретический анализ вопросов построения архитектуры и технологий
информационно-поисковых систем, ориентированный на повышение
эффективности в зависимости от типа запроса пользователя.
2. Разработка и исследование модификаций существующих методов
ранжирования в поисковых системах. Принципиальным отличием нового
метода является то, что в зависимости от типа запроса он применяет
различные алгоритмы ранжирования.
3. Разработка и исследование модификаций методов построения индекса.
4. Анализ и разработка модификации алгоритмов информационного поиска в
части расчета критерия релевантности документа.
5. Разработка имитационной модели информационно-поисковой системы с
целью возможной оценки предлагаемых технических решений.
Методы исследований и достоверность результатов. В работе использованы
методы теории принятия решений, имитационного моделирования, а также теории
вероятностей
и
генетических
алгоритмов.
Достоверность
результатов
подтверждается корректным применением элементов теории принятия решений,
планирования экспериментов, сопоставлением полученных экспериментальных
результатов с имитационным моделированием, непротиворечивостью предложенных
математических моделей и методов поиска решения, а также положительной оценкой
внедрения результатов.
Объектом исследования является технология функционирования, методы
построения индексов, метрики оценки, модели и алгоритмы информационнопоисковых систем.
Предметом исследования являются массивы данных, обрабатываемые в
информационно поисковой системе и математические модели, их описывающие.
5
Научная новизна. В диссертации получены следующие новые научные и
практические результаты: модификация метода инвертированных файлов,
позволяющая повысить скорость возвращения списка документов, содержащих
необходимый термин; метрика оценки для математической модели, учитывающая
положение релевантных документов; модификация математических моделей
информационного поиска путем изменения методов вычисления релевантности
документа с использованием генетического алгоритма, что позволяет повысить
партинетность результатов поиска;
модель ИПС, использующая необходимый
алгоритм в зависимости от типа запроса пользователя; модификация технологии
работы информационно-поисковой системы, использующая предлагаемые
теоретические результаты.
Основные положения выносимые на защиту.
1. Новая метрика «Чувствительная метрика ошибок», которая оценивает первые  –
документов на соответствие полученной релевантности. Чем выше документ в
списке, тем меньше допустима ошибка, т.к. пользователи просматривают
документы по порядку.
2. Модификация метода инвертированных файлов, заключающаяся в хранении
файла индекса по пути его термина. Данный метод на тестовой коллекции показал
лучшие результаты, чем метод инвертированных файлов.
3. Модификация алгоритмов: булевого поиска, модели векторного пространства,
вероятностной модели, обратной связи по релевантности, языковых моделей с
помощью внедрения генетического алгоритма, для расчета релевантности
документа. Модификации показали лучший результат, по сравнению с базовыми
алгоритмами.
4. Модификация алгоритмов поиска информации Sphinx, Lucene, Xapian с помощью
генетического алгоритма, позволяющая улучшить характеристики модели
корпоративного поиска.
5. Модель поиска, которая выбирает алгоритм ранжирования в зависимости от
количества слов и типа информационного запроса. Данная модель позволяет
улучшить такие характеристики системы, как: полнота, точность, ошибка.
6. Имитационная модель информационно-поисковой системы, позволяющая оценить
эффективность принятых теоретических и технических решений при построении
серверной и клиентской части программного комплекса.
7. Модификация архитектуры информационно-поисковой системы, позволяющая
уменьшить количество операций чтение/запись из хранилища.
Теоретическая ценность работы заключается в построении и исследовании
моделей информационно-поисковых систем, методов построения индекса.
Практическая ценность. Совокупность полученных теоретических и
практических результатов может использоваться для построения корпоративных и
интерфейсных информационно-поисковых систем, позволяющих повысить качество
результатов поиска.
6
Для практического применения системы в диссертации создан программный
продукт (IRST), позволяющий выполнять поиск в корпоративной информационной
среде и по нескольким сайтам.
Реализация результатов работы. Разработанные в диссертационной работе
теоретические и практические результаты внедрены в ООО «ВелесВент», ОАО
«НГЧ».
Разработанный программный продукт имеет свидетельство об официальной
регистрации программных систем и баз данных в Российском агентстве по патентам
и товарным знакам (РОСПАТЕНТ):
программная система IRSI/ Информационно-поисковая система информации в
Intranet/Internet среде. Зарегистрировано в Реестре программ для ЭВМ 6.07.2011 г.,
рег. № 2011616861
Апробация работы и публикации. Основные положения диссертации и
отдельные ее результаты обсуждались и получили положительные отзывы на:
 VII Международной научно-практической конференции «Моделирование,
Теория, методы и средства», 2007г. (г. Новочеркасск)
 Научно-технической конференции студентов и аспирантов ЮРГТУ (НПИ)
«Студенческая весна 2008» (г. Новочеркасск)
 VIII Межрегиональной научно-практической конференции студентов и
аспирантов, 2008 г. (г. Новокузнецк)
 II Российской летней школе по информационному поиску, 2008г. «RuSIR 2008» (г.
Таганрог)
 VII, XI Международной научно-практической конференции «Теория, методы
проектирования,
программно-техническая
платформа
корпоративных
информационных систем», 2009г, 2013г. (г. Новочеркасск)
 IV Российской летней школе по информационному поиску, 2010г. «RuSIR
2010» (г. Воронеж)
По теме диссертации опубликовано 17 статей, три из них в рекомендованных
ВАК изданиях, получено свидетельство о регистрации программного продукта.
Структура диссертационной работы. Диссертация содержит 224 станицы
основного текста, 95 рисунков, 22 таблицы и состоит из введения, четырех глав,
заключения, списка литературы из 100 наименований и трех приложений объемом 38
страниц.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность темы диссертации. Формулируются
цель работы и задачи, описываются применяемые методы исследования, научная
новизна, практическая значимость работы и основные положения, выносимые на
защиту.
В первой главе диссертации приведена классификация поисковых систем и
моделей информационного поиска, рассмотрены следующие технологии ИПС:

StackSearch, как реализация классической технологии;
7

Google, на основе происходящих процессов без учета распределения по
серверам;

распределенная ИПС Яндекс.
Представлена технология модифицированной системы, основное отличие
которой заключается в том, что модуль индексирования сразу создает индекс для
входящего документа и заносит документ в хранилище, при этом выделяя все
необходимые параметры страницы: ссылки, объем текста, дата публикации и т.д. В
этом случае документ не проходит два этапа: первоначальное занесение его в
хранилище документов, а затем его выбор и обработка.
Проведен эксперимент в системе имитационного моделирования Anylogic,
который показал, что данное изменение позволит уменьшить нагрузку сервера на 6%.
На рисунке 1 показана модифицированная архитектура, включающая модуль
индексирования.
Сеть
базы
данных
файлы
мультимедиа
документы
Сетевые
роботы
URL
Модуль
индексирования
Модуль
обработки
ссылок
Кеш
Ссылки
Модуль получения
результата
Индексы
Документы
Ранжирование
результат
Статистика запросов
Поисковая
машина
запрос
Клиент
Рис. 1. Модифицированная архитектура ИПС
Архитектура ИПС состоит из следующих хранилищ и модулей.
Хранилища:
1)
URL – хранит адреса страниц, которые находятся в очереди на
индексацию;
2)
ссылки – хранит связи между документами;
3)
индексы – хранит индексы документов, чтобы легко можно было найти
документы, в которых встречается данное слово, и наоборот, найти слова из
документа;
4)
документы – хранит тексты документов;
8
5)
кэш – хранит сформированную выдачу по часто задаваемым запросам;
6)
статистика запросов – хранит статистику запросов.
Модули:
1)
сетевые роботы – занимаются обходом сети в поиске новых документов;
2)
индексирование – выполняет процесс индексирования документа;
3)
обработка ссылок – находит новые документы по ссылкам и отправляет в
очередь на индексацию;
4)
ранжирование – выбирает документы удовлетворяющие запросам и
сортирует их в порядке уменьшения значимости;
5)
получение результата – ведет статистику запросов и если для запроса уже
сформированы результаты поиска в кэше, то выдает ее пользователю, в противном
случае посылает запрос модулю ранжирования;
6)
Поисковая машина – с ней непосредственно общается пользователь. На
вход она получает запрос и выдает результаты поиска пользователю.
Также в данной главе рассмотрены существующие алгоритмы поиска
информации в корпоративных сетях: Sphnix, Lucene, Xapian, которые используют
модификацию метода BM25.
Представлена обобщенная математическая модель ИПС. На вход модели
поступает запрос  , к базе документов  = {1 , … ,  }, где  – общее
количество документов. Поисковая система выдает по запросу пользователя вектор

), где  – количество результатов поиска.
документов  = (1 , … , 
Вычисляется релевантность документа  по запросу  – , = ( ,  ) и
документы сортируются в порядке её уменьшения. Также релевантность документа
стремится к пертинентности документа ( ,  ). Необходимо определить
оптимальный алгоритм , который обеспечит необходимое соотношение факторов
для получения представления документов с максимальной релевантностью.
Для проведения эксперимента учитываются только запросы с
согласованностью экспертов Каппа > 0.67, () — доля совпавших оценок
экспертов, () — ожидаемая доля случайно совпавших оценок.

),
 = (1 , … , 
( ,  ) = , ,
( ,  ) → ( ,  ),
( ) → max(( ), ( )),

(1 ,  ) → (, _,  , , ) → ,
Каппа =
()−()
1−()
,
И ограничениями:
1

∗ ∑=1  < ,


 ∗  ∗  > ,
,1 > ,2 > ⋯ > , ,
 ( ) → ,
_ ( ) → ,
Каппа > 0.67,
9
где  – определяется функцией вычисления релевантности,  =
{1 , … ,  } - скорость индексации изменяется в зависимости от компьютера и
определяет количество документов в минуту, на  – компьютерах,  = {1 , … ,  } –
время доступности компьютера (минут в сутки).
Необходимо проиндексировать все документы за  минут для поддержания БД
в актуальном состоянии.  – коэффициент параллельной обработки документов.
(, _,  , , ) – факторы, от которых зависит релевантность
документа запросу, подразделяются на:
 статические  - не зависят от запроса;
o динамические – зависят от запроса и вычисляются в момент обращения,
подразделяются на: внешние _ и внутренние  ;
 географический фактор  - зависит от местонахождения пользователя;
 собственные факторы  - учитывают нахождения документа в доверяемых
каталогах, клики пользователей.
При рассмотрении моделей информационного поиска будут отображены
только функции вычисления релевантности документа по запросу.
Во второй главе рассмотрены методы оценки эффективности систем
информационного поиска – представлен набор метрик, используемый на
международной конференции TREC и включающий: полноту, точность, 11-точечный
график полноты/точности, , среднюю точность. Проведена оценка
существующих метрик, и на основе их анализа предложена чувствительная метрика
ошибок:

 = ∑
=1
| −  |
∗  ,

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

−1 >  ,
 = −1 +

 = −1
 = −1 =  ,


<

,

=

−
,
−1


−1
{

где  = | −  |.
Пример расчета метрики представлен в таблице 1, при N=10.
В итоге формируется суммарная ошибка, равная  = 12,24. Одну
треть данной ошибки составляет первая строка, т.к. разница релевантности ПС и
оценки экспертов равняется четырем, а если бы оценка экспертов равнялась оценке
ПС, то на данном шаге получили бы нулевое значение метрики. Сложность данного
алгоритма составит (), т.к. алгоритм содержит один цикл.
Таблица 1. Пример расчета метрики ошибки
10
Позиция
документа, 




1
6
0
4
-
2
8
9
1
0.5
3
5
8
3
0.5+3/3=1.5
4
3
7
4
1.5+4/4=2.5
5
10
6
4
2.5
6
3
5
2
2.5-2/6=2.17
7
3
4
1
2.17-1/7=2.03
8
4
3
1
2.03
9
4
2
2
2.03+2/9=2.25
10
2
1
1
2.25

6 − 10
=4
1
8−9
∗ 0.5 = 0.25
2
5−8
∗ 1.5 = 1.5
3
3−7
∗ 2.5 = 2.5
4
10 − 6
∗ 2.5 = 2
5
3−5
∗ 2.17 = 0.72
6
3−4
∗ 2.03 = 0.29
7
4−3
∗ 2.03 = 0.25
8
4−2
∗ 2.25 = 0.5
9
2−1
∗ 2.25 = 0.23
10
В итоге формируется суммарная ошибка, равная  = 12,24. Одну
треть данной ошибки составляет первая строка, т.к. разница релевантности ПС и
оценки экспертов равняется четырем, а если бы оценка экспертов равнялась оценке
ПС, то на данном шаге получили бы нулевое значение метрики. Сложность данного
алгоритма составит (), т.к. алгоритм содержит один цикл.
Экспериментальное исследование метрики на выборке случайных запросов и
рассчитанной для пары [документ – запрос] показало, что предложенная метрика
очень чувствительна на наличие релевантных документов в первых строках
результатов поиска. Данную метрику необходимо вычислять в совокупности с
остальными метриками.
Таким образом получается оптимальный набор метрик для оценки ИПС:
полнота, точность, аккуратность, ошибка, F-мера, чувствительная метрика ошибок.
Данный набор метрик позволит сравнить методы поиска информации и
определить оптимальный метод взвешивания документа.
Имея оценки экспертов
( ,
 ,
 )
по паре запрос , документ  данного эксперта  (где  –
номер запроса,  – номер документа,  – номер эксперта), необходимо вычислить
значения метрик .
В связи с тем, что несколько экспертов оценивают пару документ-запрос, то будет
учитываться средняя оценка:
1
 ( ,  ) = ∑
( ,  ,
 =1
 ),
где  – количество экспертов.
В работе рассмотрены методы построения индекса: в виде дерева, суффиксных
массивов, сигнатурных файлов, инвертированных файлов. Одним из используемых
моделей является метод инвертированных файлов.
11
На вход модели поступает запрос пользователя, состоящий из терминов  =


{ 1 , … ,   }, где  – количество терминов в запросе. Имеется индексный
файл состоящий из терминов и номеров документа, в которых он встречается:
 = {( , 1 , … ,  ), … , ( , 1 , … ,  )}
Необходимо получить документы с данным термином:


 = (
, … , 
)
1


 = (  , )
где  – количество индексов документа,  – индекс документа,

(  , ) – функция получения индекса документа.
При выполнении условий:

  =  ,
(1)
 )
(
→ ,
(2)
 )
(
– время получения результирующего вектора документа.
В базовом варианте данного метода индекс хранится в едином структурированном
файле. Модификация заключается в разбиении единого файла на множество
индексных файлов, каждый из которых хранится в отдельной папке,
соответствующий конкретному термину.
Индексный файл  разбиваем на части  , где  – количество терминов.
При этом структура индексного файла выглядит следующим образом:
 = {1 , … ,  }.
Термин разбиваемся на символы,
 = (1 ∪ 2 ∪ … ∪ | | ).

Конечный индексный файл находится по определенному пути, получаем его
используя функцию (1 ∪ 2 ∪ … ∪ || ).
Модифицированная модель
представлена ниже:


 = (
, … , 
),
1

 = {1 ∪ 2 ∪ … ∪  }, ∀  ,
 = ( ),
 =  (1 ∪ 2 ∪ … ∪ | | ),


 = (1 ∪ 2 ∪ … ∪ | | ),

при выполнении условий 1, 2.
Благодаря такой организации хранения индекса для любого термина сразу
известно, где искать файл индекса, и для его получения тратится меньше времени,
чем для единого индексного файла. Сравнительный анализ полученной модели с
другими методами построения индекса показал, что:

размер индекса практически не отличается;

скорость индексации на 30% выше, чем у инвертированных файлов;

время ответа на 15% меньше, чем у инвертированных файлов.
В третьей главе приведен анализ существующих поисковых алгоритмов, в
ходе которого был выявлен основной существенный недостаток – алгоритмы не
подстраиваются под существующие документы. Данная проблема очень актуальна,
т.к. в различных организациях имеется свой тип документов, а каждый тип
12
документов необходимо ранжировать по разному, например: бухгалтерские бланки
чем новее, тем более актуальны, а в продукции большее значение имеет полное
соответствие запросу. Очевидно, что данная задача относится к классу NP-сложных
задач (классификация в теории вычислительной сложности). Для решения такого
типа задач используются эвристические алгоритмы, в качестве одной из альтернатив
возможно использование генетических алгоритмов для автоматической подстройки
информационно-поисковой системы.
Генетический алгоритм для подбора коэффициентов получает на вход
количество коэффициентов (), используемых в модели, и возвращает подобранные
коэффициенты. Общий алгоритм выглядит следующим образом:
1) Создается начальная популяция. Случайным образом из диапазона
коэффициентов от  до  (диапазон устанавливается для каждого
алгоритма) подбираем  наборов коэффициентов и переводим их в двоичный
вид.
2) Вычисляется приспособленность хромосом. Оценивается ошибка для каждого
набора коэффициентов.
3) Выбираются два родителя с наименьшей ошибкой для операции скрещивания.
4) Выбираются хромосомы для операции мутации.
5) Оценивается приспособленность нового набора коэффициентов.
6) Если ошибка набора (1 ) больше заданной ошибки ( ), то переходим к
пункту 3, иначе пункт 7.
7) Полученный набор коэффициентов, который минимизирует ошибку,
возвращается в модель поиска.
Рассмотрены более детально основные аспекты:
 Все коэффициенты генерируются изначально случайным образом по
равномерному закону при ограничении сверху и снизу. Затем переводятся в
двоичный вид, чтобы можно было применять операции скрещивания и
мутации.
 Ошибка оценивается по следующей формуле:

 = ∑(( ,  ) − ( ,  ))2 ,
=0
где ( ,  ) – средняя оценка документа  экспертами, по запросу  .
( ,  ) – полученная релевантность документа  , по запросу  .
Проведено экспериментальное исследование для получения оптимальных
операций скрещивания и мутации.
Операция отбора. После проведения ряда экспериментов было выявлено, что
для более быстрого получения максимума целевой функции отбор хромосом должен
осуществляться по следующему принципу: для операции скрещивания берутся две
самые лучшие хромосомы, и случайным образом  хромосом.
Для операции мутации берутся две хромосомы с самой низкой
приспособленностью и  хромосом.
Операция скрещивания. Для выбора оптимальной операции скрещивания был
проведен ряд экспериментов с различными методами. В результате определились два
оптимальных метода. Для проверки эффективности случайным образом делалась
выборка запросов от одного до ста. В качестве параметра, определяющего
13
оптимальность, бралась средняя оценка релевантности выдачи по данным запросам.
Во время эксперимента отключались другие операции. Таким образом, функция
достигает максимума при сращивании методом «расчески» и очень близка при
скрещивании «пополам». Решено оставить оба варианта в алгоритме, и эксперименты
доказали эффективность выбранного способа
Для определения оптимальной мутации был проведен эксперимент, где
оценивалась средняя релевантность документов выданных системой при
отключенных других механизмах.
В результате эксперимента выяснилось, что
мутация достигает максимума при вероятности мутирования бита, равной 40%.
В результате эксперимента были получены оптимальные операции
скрещивания и мутации для данного генетического алгоритма.
Также проведена оценка сложности генетического алгоритма. Из анализа
операций получены две самые длительные операции:
 оценка ошибки, (50 ), выполняется за 1 сек;
 вычисление целевой функции () ∗ ( ) , выполняется за 2 сек.
Количество операций генетического алгоритма О() равно:
(50 ), (50 ) > () ∗ ( ),
О() = {
() ∗ ( ), (50 ) < () ∗ ( ).
Количество итераций ГА может варьироваться от одной до бесконечности, но
имея ограничения по времени сверху  (по умолчанию в программе это значение
равно 5 часам) и зная время итерации  , получим, что нам необходимо  =
(3600 ∗  )/ итераций.
 ,
1 > 2
 = {1 ,
2 > 1
2
Общая сложность алгоритма составит () = О( ∗ ).
Данный ГА используется во всех экспериментальных исследованиях моделей
информационного поиска, для которых было создано две базы запросов –
документов. Первая база используется для обучения алгоритма, вторая для оценки.
Тестовые коллекции были предоставлены организацией РОМИП, использовались две
коллекции:
 псевдослучайная выборка сайтов из домена narod.ru объемом 728 000
документов;
 набор, содержащий новостные сообщения из 25 источников и охватывающий 3
временных интервала (около 31 500 документов).
Были сформированы запросы трех типов:
 информационные запросы;
 навигационные запросы;
 транзакционные запросы.
Всего сформировано около 5 000 запросов в равных соотношениях.
В различных экспериментах использовалось различное количество запросов и
документов – это обусловлено в основном временем выполнения запроса к базе
документов.
Выполнено экспериментальное исследование алгоритмов поиска информации
и их модификации с помощью ГА.
14
Булев поиск работает с запросами содержащими логические операции: И, ИЛИ,
НЕТ. Релевантность вычисляется по формуле:

(, ) = ∑   ,
=1
где  – количество зон документа (заголовок, сноски, текст),  – вес зоны
документа,  – значение фактора. Приведена оценка сложности алгоритма, которая
составила ().
В данной формуле вес зоны документа подбираются генетическим алгоритмом
и методом динамического программирования. Результаты сравниваются со
значениями метрик, полученных полным перебором.
Эксперимент показал, что генетический алгоритм обладает лучшими
значениями метрик, по сравнению с другими методами. Его эффективно
использовать для подбора коэффициентов , чтобы минимизировать ошибку
вычисления релевантности.
В модели векторного пространства релевантность рассчитывается по
следующей формуле:
(, ) =
⃗ (),
⃗ ())
(
,
⃗ ()‖∙‖
⃗ ()‖
‖
⃗ () – векторное представление запроса, 
⃗ () – векторное представление
где 
документа. В качестве векторов в эксперименте использовалась оценка веса запроса
, и нормированный вес термина в документе – , .
, =  ∗ ,
где  – частота термина в запросе,  – обратная документная частота,
вычисляемая по формуле:

 =  ,

где  – размер базы документов,  – количество документов с данным
термином.

, =
,
√∑|термин|
2
=1
Оценка сложности данного алгоритма составляет ( 3 ).
В данном примере вес термина в документе учитывал только частоту термина,
но возможны и другие варианты взвешивания документа. Ручной подбор схемы
взвешивания для коллекции документов займет большее время: был проведен
эксперимент для подбора схемы взвешивания, использующую одну из трех схем ,
, или  − .
Модификация с генетическим алгоритмом обладает лучшими значениями метрик,
по сравнению с базовым алгоритмом. Но при этом не оправдана сама эффективность
использования векторной модели для ранжирования, т.к. вычисление косинусной
меры сходства между вектором запроса и каждым вектором документа коллекции,
сортировка по релевантности и выбор  лучших документов является довольно
затратным процессом и требует выполнения десятков тысяч арифметических
операций.
15
Вероятностная модель – оценивает вес документа по схеме Okapi BM25 и
рассчитывается по следующей формуле:
(1 +1)

 = ∑∈ log [ ] ∙
,


1 ((1−)+×(  ))+

где  — частота термина  в документе , a  и  — длина документа 
и средняя длина документа во всей коллекции. Переменная 1 — это положительный
параметр настройки, с помощью которого производится калибровка частоты термина.
Если 1 = 0, то модель становится бинарной (частота термина не учитывается), а если
параметр 1 принимает большие значения, то это эквивалентно прямому подсчёту
частоты термина. Переменная  — еще один параметр настройки (0 ≤  ≤ 1),
определяющий нормировку по длине документа:  = 1 соответствует полноценному
масштабированию веса термина с помощью длины документа, а  = 0 не
предусматривает нормировки по длине.
Оценка сложности данного алгоритма составит ( 3 ).
Генетический алгоритм встраивается как подбор коэффициентов для формулы
ранжирования. По результатам экспериментов, модификация с генетическим
алгоритмом не дала лучших результатов, чем базовая, т.к. за отведенное время ей не
удалось подобрать более оптимальных параметров.
Модификация модели обратной связи по релевантности. Имеется запрос
пользователя и частично знание о релевантности документов. Алгоритм Роккио
предлагает использовать модифицированный запрос  .
1
1
 = 0 + 
∑  − 
∑  ,
| |
| |
 ∈
 ∈
где 0 — оригинальный вектор запроса,  и  — множества известных
релевантных и нерелевантных документов соответственно, ,  и — веса каждого
слагаемого. С помощью генетического алгоритма будем подбирать веса слагаемых и
сравним с базовой моделью, в которой веса установлены рекомендуемым значениям:
 = 1,  = 0,75 и  = 0,15. Оценка сложности данного алгоритма составляет
( 2 ).
Как показали исследования, метод RF позволяет очень эффективно повысить
релевантность результатов. Для его успешного использования необходимы запросы,
в которых существует достаточно много релевантных документов. А использование
генетического алгоритма позволяет еще улучшить данную модель на 5%.
В модификации языковой модели реализована функция дивергенции КульбакаЛейблера, она позволяет оценить риск вернуть документ d в качестве релевантного
запросу q между соответствующими языковыми моделями.
(| )
(; ) = ( || ) = ∑ (| ) 
(| )
∈
Для подбора генетическим алгоритмом введем дополнительные коэффициенты
:
1 ∗ (| )
(; ) = ( || ) = ∑ (| ) 
2 ∗ (| )
∈
16
Здесь  — языковая модель документа d,  — языковая модель запроса , 
– термины, входящие в запрос .
В качестве модели документа и запроса используется следующая формула:
,
P(| ) = ∏
∈ 
,
P(| ) = ∏
∈ 
Где , , , — частота термина t в документе d и запросе  соответственно, a
 ,  — количество лексем в документе d и запросе  соответственно. Оценка
сложности данного алгоритма составляет ( 2 ).
Как показали исследования, внедрение генетического алгоритма позволяет
улучшить данную модель на 20%.
Проведены исследования современных средств полнотекстового поиска:
Sphinx, Lucene, Xapian, они используют стандартные модели со своими
модификациями, которые подразумевают встраивание коэффициентов подбираемых
с помощью ГА.
Все три алгоритма по-разному ведут себя для различных типов запросов,
данные представлены в таблице 2. Оптимальными являются: по информационным
запросам Xapian показывает на 10% лучше; по транзакционным запросам Lucene на
6%; по навигационным запросам Sphinx на 7%. По однословным запросам Xapian на
5% лучше; по двухсловным Lucene на 15% лучше; по трехсловным Sphinx лучше на
13%.
После подбора коэффициентов ГА, метрики улучшились в среднем на 12%.
Также алгоритмы перераспределились: по информационным запросам Sphiinx
показывает на 15% лучше; по транзакционным запросам Lucene на 20%, по
навигационным запросам Sphinx на 11%.
По однословным запросам Xapian на 6% лучше; по двухсловным и
трехсловным Sphinx и Lucene с разницей около 2%.
Таблица 2. Поисковые механизмы в зависимости от типов запросов
по количеству слов в запросе
Тип запроса
1
2
3
Xapian
Lucene / Sphinix
Sphinix / Lucene
Информационные
Sphinix
Sphinix
Sphinix
Xapian
Lucene/ Sphinix
Sphinix / Lucene
Навигационные
Sphinix
Sphinix
Sphinix
Xapian
Sphinix / Lucene
Lucene
Транзакционные
Lucene
Lucene
Lucene
В связи с такой разницей поведения алгоритмов по разным типам запросов,
предложена улучшенная модель поиска, которая в зависимости от типа запроса
использует необходимый алгоритм. Улучшенная модель включает обобщенную
математическая модель ИПС, с добавлением 1 ( ,  ) – функции определения
релевантности.
17
1 ( ,  ),
( ) = 1
( ) = 2
( ,  ) = { 2 ( ,  ),
 ( ,  ),
( ) = 
где ( ) – функция определения типа запроса.
Ограничения 1,2 сохраняются.
Проведен эксперимент, который показывает эффективность данного подхода.
Благодаря внедрениям ГА, метрики улучшились в среднем на 12%, а после выбора
модели поиска, для запроса получилось улучшить характеристики еще на 7%.
После всех изменений, характеристики полученной модели увеличились на
20%.
В четвертой главе приводится модель ИПС, включающая 6 уровней и 5
процессов. Основные процессы:
 обучение – эксперт вводит запросы и помечает релевантные документы;
 индексирование - из хранилища берутся адреса документов для индексирования,
и строится необходимый индекс;
 поиск – по запросу пользователя отбираются документы и выдаются по мере
уменьшения веса документа;
 анализ – анализируются запросы пользователей, их поведение;
 APM - набор пользовательских API функций для обращения к поисковой
системе.
Описывается работа ИПС, схема хранения данных, которая подразумевает
создание XML файлов индекса, и работы с базой данных. Представлена
имитационная модель ИПС со стороны сервера, клиента и пользователя. Модель
позволяет оценить среднее количество документов в очереди на индексацию, среднее
время индексации документа, среднее время обработки запроса, количественно
обрабатываемых заявок, время поиска пользователем необходимой информации.
Рассмотрено внедрение ИПС на сервер в виде модуля, что позволило
уменьшить число повторных запросов на 50% и время нахождения человека на
странице на 65%. Описано внедрение ИПС с дополнительной опцией разграничения
доступа в зависимости от ПК или пользователя на предприятии, имеющем 33 ПК.
После внедрения ИПС на предприятии, время на передачу (поиск) информации
уменьшилось на 40%.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ
1. Предложена модификация архитектуры
и технологии работы ИПС,
отличающаяся тем, что модуль индексирования сразу создает индекс для
входящего документа, что позволяет сократить количество операций
чтение/запись из хранилища и уменьшить нагрузку на сервер на 6%.
2. Представлена новая обобщенная математическая модель информационнопоисковой системы, которая отличается учетом специфики функции вычисления
релевантности и метрик эффективности, а также наличием статических,
динамических, собственных и географических факторов.
3. Предложена новая метрика ошибок, учитывающая нахождение релевантных
документов в первых пунктах результатов поиска и экспериментально
подтверждена её эффективность в сравнении с традиционными: точностью,
полнотой и F-мерой.
18
4. Предложена модификация метода инвертированных файлов, заключающаяся в
хранении индекса по пути, формируемом на основании его термина, и
экспериментально подтверждено увеличение скорости индексации на 30%,
уменьшение времени ответа на 15%.
5. Рассмотрены и предложены модификации методов вычисления релевантности
документа в алгоритмах булева поиска, модели векторного пространства,
вероятностной и языковой моделях, метода обратной связи на основе вычисления
коэффициентов с использованием генетического алгоритма, который позволяет
улучшить методы поиска в среднем на 12%.
6. Предложена новая модель поиска, которая выполняет выбор алгоритма
ранжирования в зависимости от количества слов в запросе и от типа
информационного запроса, что позволяет улучшить характеристики
информационно-поисковой системы на 20%.
7. Разработаны программные продукты, реализующие предложенные модификации
алгоритмов и позволяющие выполнять поиск по документам в Internet/Intranet
среде. Проведенные экспериментальные исследования предложенных решений
показали увеличение значения параметров эффективности на 40%, уменьшение
числа повторных запросов на 50%.
8. Результаты диссертационной работы внедрены в рамках информационных систем
предприятий «НГЧ» и ООО «ВелесВент». По теме диссертации опубликовано 17
печатных работ, в том числе 3 в рекомендованных ВАК изданиях, получено
свидетельство о регистрации программного продукта.
СПИСОК ОСНОВНЫХ ПУБЛИКАЦИЙ
Публикации в ведущих изданиях, рекомендованных ВАК
1. Хорошко, М.Б. Модификация алгоритма булевого поиска / М. Б. Хорошко //
Известия высших учебных заведений. Северо-Кавказский регион. Серия:
Технические науки. – 2011 № 3 – С. 14-18
2. Воробьев С.П., Хорошко, М.Б. Модификация модели векторного пространства
для ранжирования документов/ Воробьев С.П., Хорошко, М.Б// Электронный
журнал
«Инженерный
вестник
Дона»,
2012
г.
№3,
http://www.ivdon.ru/magazine/archive/n3y2012/976
3. Воробьев С.П., Хорошко, М.Б. Модификация схемы BM25 с помощью
генетического алгоритма / Воробьев С.П., Хорошко, М.Б// Электронный журнал
«Инженерный
вестник
Дона»,
2012
г.
№4,
http://www.ivdon.ru/magazine/archive/n4t1y2012/1177
Публикации в сборниках научных статей, трудов и материалов конференций
4. Хорошко М.Б. Обзор математических моделей информационного поиска //
Компьютерные технологии в науке, производстве, социальных и экономических
процессах : материалы VII Междунар. науч. - практ. конф., г. Новочеркасск, 16
ноября 2007 г. / Юж. – Рос. гос. техн. ун-т (НПИ). – Новочеркасск : ЮРГТУ, 2007.
С. 83-89.
5. Хорошко М. Б. Информационно-поисковая система для интернета. // Теория,
методы проектирования, программно-техническая платформа корпоративных
информационных систем : материалы VI Междунар. науч. - практ. конф., г.
19
Новочеркасск, 26 мая 2008 г. / Юж. – Рос. гос. техн. ун-т (НПИ). – Новочеркасск
: ЮРГТУ, 2008. С. 221-227.
6. Хорошко М.Б.
Оценка эффективности поисковых систем. // VIII
Межрегиональная научно-практическая конференция студентов и аспирантов :
материалы конф., 11 апр. 2008г. : в 3-х т. / Новокузнецк. филиал - ин-т гос. обр.
учрежд. высш. проф. обр. «Кемеровск. гос. ун-т». – Новокузнецк, 2008. – Т.1. С.
11-12.
7. Хорошко М. Б. Система поиска информации в Интернете. // Студенческая
научная весна 2008 : материалы Межрегион. науч.-техн. конф. студентов,
аспирантов и молодых ученых Южного федерального округа / Юж. – Рос. гос.
техн. ун-т (НПИ). – Новочеркасск : ЛИК, 2008. – С. 97-99.
8. Хорошко М.Б. Алгоритмы, используемые в поисковых системах. // Теория,
методы проектирования, программно-техническая платформа корпоративных
информационных систем : материалы VII Междунар. науч. - практ. конф., г.
Новочеркасск, 25 мая 2009 г. / Юж. – Рос. гос. техн. ун-т (НПИ). – Новочеркасск
: ЮРГТУ, 2009. - С. 272-284.
9. Хорошко М. Б. Контекстно-зависимые аннотации. // Теория, методы
проектирования,
программно-техническая
платформа
корпоративных
информационных систем : материалы VII Междунар. науч. - практ. конф., г.
Новочеркасск, 26 мая 2009 г. / Юж. – Рос. гос. техн. ун-т (НПИ). – Новочеркасск
: ЮРГТУ, 2009. - С. 232-242.
10. Хорошко М. Б. Методы формирования контекстно-зависимых аннотаций. //
Результаты исследований 2009 : материалы 58-й науч. – техн. конф.
профессорско-преподавательского состава, науч. работников, аспирантов и
студентов ЮРТУ (НПИ) / Юж. – Рос. гос. техн. ун-т (НПИ). – Новочеркасск :
ЮРГТУ, 2009. -С. 277-278.
11. Хорошко М. Б. Оценка качества поиска. // Теория, методы проектирования,
программно-техническая платформа корпоративных информационных систем :
материалы VII Междунар. науч. - практ. конф., г. Новочеркасск, 25 мая 2009 г. /
Юж. – Рос. гос. техн. ун-т (НПИ). – Новочеркасск : ЮРГТУ, 2009. - С. 242-250.
12. Хорошко М. Б. Типы, модели и методы информационного поиска. // Теория,
методы проектирования, программно-техническая платформа корпоративных
информационных систем : материалы VII Междунар. науч. - практ. конф., г.
Новочеркасск, 25 мая 2009 г. / Юж. – Рос. гос. техн. ун-т (НПИ). – Новочеркасск
: ЮРГТУ, 2009. - С. 251-272.
13. Хорошко М. Б. Нейронные сети. // Теория, методы проектирования,
программно-техническая платформа корпоративных информационных систем :
материалы VIII Междунар. науч. - практ. конф., г. Новочеркасск, июнь 2010 г. /
Юж. – Рос. гос. техн. ун-т (НПИ). – Новочеркасск : ЮРГТУ, 2010. - С. 80-83.
14. Хорошко М. Б. Нейронные сети высокого порядка и радиально базисные сети. //
Теория, методы проектирования, программно-техническая платформа
корпоративных информационных систем : материалы VIII Междунар. науч. практ. конф., г. Новочеркасск, июнь 2010 г. / Юж. – Рос. гос. техн. ун-т (НПИ). –
Новочеркасск : ЮРГТУ, 2010. - С. 83-87.
15. Хорошко М. Б. Нейронные сетевые методы распознавания изображений. //
Теория, методы проектирования, программно-техническая платформа
20
корпоративных информационных систем : материалы VIII Междунар. науч. практ. конф., г. Новочеркасск, июнь 2010 г. / Юж. – Рос. гос. техн. ун-т (НПИ). –
Новочеркасск : ЮРГТУ, 2010. - С. 76-80.
16. Хорошко М. Б. Использование модифицированной модели обратной связи по
релевантности. // Теория, методы проектирования, программно-техническая
платформа корпоративных информационных систем : материалы XI Междунар.
науч. - практ. конф., г. Новочеркасск, 28 мая 2013 г. / Юж. – Рос. гос. техн. ун-т
(НПИ). – Новочеркасск : ЮРГТУ, 2013. - С. 71-79.
17. Хорошко М. Б. Оценка алгоритмов поиска информации CPHIKS, LUCENE,
XAPIAN. // Теория, методы проектирования, программно-техническая
платформа корпоративных информационных систем : материалы XI Междунар.
науч. - практ. конф., г. Новочеркасск, 28 мая 2013 г. / Юж. – Рос. гос. техн. ун-т
(НПИ). – Новочеркасск : ЮРГТУ, 2013. - С. 79-85.
Личный вклад автора в работах, опубликованных в соавторстве:
[2] - модификация модели векторного пространства для ранжирования
документов; [3] - модификация схемы BM25 с помощью генетического
алгоритма.
Соискатель
Хорошко М.Б.
Документ
Категория
Без категории
Просмотров
11
Размер файла
863 Кб
Теги
0c54292717, uploaded
1/--страниц
Пожаловаться на содержимое документа