автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Разработка и модификация моделей и алгоритмов поиска данных в INTERNET/INTRANET среде для улучшения качества поиска

На правах рукописи

Хорошко Максим Болеславович

РАЗРАБОТКА И МОДИФИКАЦИЯ МОДЕЛЕЙ И АЛГОРИТМОВ ПОИСКА ДАННЫХ В ЕЧТЕШЕТЯ1ЧТКА]ЧЕТ СРЕДЕ ДЛЯ УЛУЧШЕНИЯ КАЧЕСТВА ПОИСКА

Специальность 05.13. 17 - «Теоретические основы информатики»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

5 ДЕК 2013

" Новочеркасск-2013

005542380

Работа выполнена на кафедре «Информационные и измерительные системы и технологии» ФГБОУ ВПО ЮРГПУ(НПИ) им М.И. Платова.

Научный руководитель кандидат технических наук, доцент

Воробьев Сергей Петрович

Официальные оппоненты Ромм Яков Евсеевич

доктор технических наук, профессор, ФГБОУ ВПО «Таганрогский государственный педагогический институт имени А.П. Чехова», заведующий кафедрой информатики

Шестаков Сергей Александрович

кандидат технических наук, ООО «Прог-Форс», директор компании

Ведущая организация ФГВОУ ВПО «Военная академия

связи имени Маршала Советского Союза С.М.Буденного» Министерства обороны Российской Федерации, г. Санкт - Петербург

Защита состоится «27» декабря 2013 г. в 10:20 на заседании диссертационн совета Д 212.208.21 Южного федерального университета по адресу: 347 г. Таганрог, пер. Некрасовский, 44, ауд. Д- 406.

С диссертацией можно ознакомиться в Зональной научной библиот Южного федерального университета по адресу: 344000, г. Ростов-на-Д ул. Пушкинская, 148.

Автореферат разослан «25» ноября 2013 г.

Ученый секретарь диссертационного совета Д 212.208.21,

доктор технических наук, fj'ß^ Боженюк A.B.

профессор

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Объемы обрабатываемой электронной информации нарастают большими темпами - этому способствует активное внедрение мультимедиа, широкое распространение корпоративных и глобальных сетей, отказ большинства предприятий от бумажного документооборота и переход на автоматизированные системы управления предприятием. В подобной ситуации резко возросла потребность в системах поиска и анализа данных, а также возник спрос на интеллектуализацию информационно-поисковых систем (ИПС).

В настоящее время работает ряд авторитетных международных конференций, посвящённых обсуждению вопросов информационного поиска, например, таких как: 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, АОТ и др.

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

Ряд авторитетных исследователей внесли своими научными трудами значительный вклад в развитие информационно-поисковых систем: И.С. Некрестьянов, И.Е. Кураленок, В.Ю. Добрынин, А.Г. Дубинский, А.Е. Ермаков, М.Р. Когаловский, A.B. Сокирко, G. Saltón, 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.

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

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

Диссертационная работа выполнена в рамках научного направления ФГ ВПО ЮРГПУ(НПИ) им М.И. Платова «Теория, принципы и технологии построе информационно-вычислительных и измерительных систем», госбюджетной т 7.05 «Разработка теории, методов оптимизации функциональной и програм технической платформы корпоративных информационных систем» (Утвержд решениями ученого совета от 25.04.2001г. и 15.05.2003г).

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

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

Для достижения поставленной цели решаются следующие задачи:

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

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

3. Разработка и исследование модификаций методов построения индекса.

4. Анализ и разработка модификации алгоритмов информационного поис части расчета критерия релевантности документа.

5. Разработка имитационной модели информационно-поисковой систем целью возможной оценки предлагаемых технических решений.

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

Объектом исследования является технология функционирования, мет построения индексов, метрики оценки, модели и алгоритмы информацион поисковых систем.

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

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

Основные положения выносимые на защиту.

1. Новая метрика «Чувствительная метрика ошибок», которая оценивает первые N -документов на соответствие полученной релевантности. Чем выше документ в списке, тем меньше допустима ошибка, т.к. пользователи просматривают документы по порядку.

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

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

4. Модификация алгоритмов поиска информации Sphinx, Lucene, Xapian с помощью генетического алгоритма, позволяющая улучшить характеристики модели корпоративного поиска.

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

6. Имитационная модель информационно-поисковой системы, позволяющая оценить эффективность принятых теоретических и технических решений при построении серверной и клиентской части программного комплекса.

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

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

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

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

Реализация результатов работы. Разработанные в диссертационной раб теоретические и практические результаты внедрены в ООО «ВелесВент», О «НГЧ».

Разработанный программный продукт имеет свидетельство об официаль регистрации программных систем и баз данных в Российском агентстве по патен и товарным знакам (РОСПАТЕНТ):

программная система IRSI/ Информационно-поисковая система информаци Intranet/Internet среде. Зарегистрировано в Реестре программ для ЭВМ 6.07.2011 per. №2011616861

Апробация работы и публикации. Основные положения диссертаци отдельные ее результаты обсуждались и получили положительные отзывы на:

• VII Международной научно-практической конференции «Моделирова Теория, методы и средства», 2007г. (г. Новочеркасск)

• Научно-технической конференции студентов и аспирантов ЮРГТУ (F «Студенческая весна 2008» (г. Новочеркасск)

• VIII Межрегиональной научно-практической конференции студентов аспирантов, 2008 г. (г. Новокузнецк)

• II Российской летней школе по информационному поиску, 2008г. «RuSIR 2008> Таганрог)

• VII, XI Международной научно-практической конференции «Теория, мет проектирования, программно-техническая платформа корпоратив информационных систем», 2009г, 2013г. (г. Новочеркасск)

• IV Российской летней школе по информационному поиску, 2010г. «Ru 2010» (г. Воронеж)

По теме диссертации опубликовано 17 статей, три из них в рекомендован ВАК изданиях, получено свидетельство о регистрации программного продукта.

Структура диссертационной работы. Диссертация содержит 224 стан основного текста, 95 рисунков, 22 таблицы и состоит из введения, четырех г заключения, списка литературы из 100 наименований и трех приложений объемо страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность темы диссертации. Формулирую цель работы и задачи, описываются применяемые методы исследования, науч новизна, практическая значимость работы и основные положения, выносимые защиту.

В первой главе диссертации приведена классификация поисковых систе моделей информационного поиска, рассмотрены следующие технологии ИПС: • StackSearch, как реализация классической технологии;

• Google, на основе происходящих процессов без учета распределения по серверам;

• распределенная ИПС Яндекс.

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

Проведен эксперимент в системе имитационного моделирования Anylogic, который показал, что данное изменение позволит уменьшить нагрузку сервера на 6%. На рисунке 1 показана модифицированная архитектура, включающая модуль индексирования.

Архитектура ИПС состоит из следующих хранилищ и модулей.

Хранилища:

1) URL - хранит адреса страниц, которые находятся в очереди на индексацию;

2) ссылки - хранит связи между документами;

3) индексы - хранит индексы документов, чтобы легко можно было найти документы, в которых встречается данное слово, и наоборот, найти слова из документа;

4) документы - хранит тексты документов;

5) кэш - хранит сформированную выдачу по часто задаваемым запросам

6) статистика запросов - хранит статистику запросов.

Модули:

1) сетевые роботы - занимаются обходом сети в поиске новых документ

2) индексирование — выполняет процесс индексирования документа;

3) обработка ссылок - находит новые документы по ссылкам и отправля очередь на индексацию;

4) ранжирование — выбирает документы удовлетворяющие запроса сортирует их в порядке уменьшения значимости;

5) получение результата - ведет статистику запросов и если для запроса сформированы результаты поиска в кэше, то выдает ее пользователю, в против случае посылает запрос модулю ранжирования;

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

Также в данной главе рассмотрены существующие алгоритмы пои информации в корпоративных сетях: Sphnix, Lucene, Xapian, которые использ модификацию метода ВМ25.

Представлена обобщенная математическая модель ИПС. На вход мод поступает запрос Qj, к базе документов D = {dlt..., dcount], где count - об количество документов. Поисковая система выдает по запросу пользователя ве документов Dres = (,d[es, ...,d^s), где rd - количество результатов пои Вычисляется релевантность документа dk по запросу Qj - Rjk = Rel(Qj, dk документы сортируются в порядке её уменьшения. Также релевантность докуме стремится к пертинентности документа Per{d.\es,Qj). Необходимо определ оптимальный алгоритм АР, который обеспечит необходимое соотношение факто для получения представления документов с максимальной релевантностью.

Для проведения эксперимента учитываются только запросы согласованностью экспертов Каппа > 0.67, Р(А) — доля совпавших оце экспертов, Р{Е) — ожидаемая доля случайно совпавших оценок.

Dres = (d[es.....drrf),

Rel(Qj,dk) = RJtk,

Rel(d\es, Qj) Per{d\es,Qj),

Per(d{es) -» max(Per(d[es), Per(d[es)),

AP

Rel(Drlt Qj) -> (SF, DF_Out, DFlnner, GF, OF) -> max, Каппа

l-P(E)

И ограничениями:

J_ * V" £i < T KP <l'

K*P*KP > D, RJ. 1 > Щ.2 > "" > Rj,rd> Metrikaiirnodelj^ max, Metrika_errorl(modelj) min, Каппа > 0.67,

где тойеI] - определяется функцией вычисления релевантности, К = {&!,...,кп) - скорость индексации изменяется в зависимости от компьютера и определяет количество документов в минуту, на п - компьютерах, Р = {рх, ...,рп} -время доступности компьютера (минут в сутки).

Необходимо проиндексировать все документы за Т минут для поддержания БД в актуальном состоянии. КР - коэффициент параллельной обработки документов.

(БР, ОР_Оиг, О^/ппе,-, ОР) - факторы, от которых зависит релевантность документа запросу, подразделяются на:

• статические - не зависят от запроса;

о динамические - зависят от запроса и вычисляются в момент обращения, подразделяются на: внешние ОР_ОиЬ и внутренние ОР,ппег;

• географический фактор С/7 - зависит от местонахождения пользователя;

• собственные факторы ОР - учитывают нахождения документа в доверяемых

каталогах, клики пользователей.

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

Во—второй главе рассмотрены методы оценки эффективности систем информационного поиска - представлен набор метрик, используемый на международной конференции ТЯЕС и включающий: полноту, точность, 11-точечный график полноты/точности, Ьрге/, среднюю точность. Проведена оценка существующих метрик, и на основе их анализа предложена чувствительная метрика ошибок:

и * ч с \ReiUser, - Йе^А МеШкаЕг = у ---— * ,

г=1 1

где N - число документов, выданных системой на запрос <7 пользователя. Для каждого документа имеется оценка релевантности экспертом (ЯеШзег), оценка релевантности системы (Де/Р5) и номер документа в выдаче (/).

Коэффициент к - динамический коэффициент, учитывающий увеличение или уменьшение разности релевантности на каждом шаге.

Г<И/егИе11_1 > (ИГегЯеи, к> = к^ + Л| = | <Н/егЯе¿¡-1 = ¿¿/егйе/,, /с£ =

( Л/егДс/^ < Л/егД^, = -

где Л/егДе/ = \RelUseri - Йе/Р5£|. '

Пример расчета метрики представлен в таблице 1, при N=10.

В итоге формируется суммарная ошибка, равная МеШкаЕг - 12,24. Одну треть данной ошибки составляет первая строка, т.к. разница релевантности ПС и оценки экспертов равняется четырем, а если бы оценка экспертов равнялась оценке ПС, то на данном шаге получили бы нулевое значение метрики. Сложность данного алгоритма составит 0(ЛГ), т.к. алгоритм содержит один цикл.

Таблица 1. Пример расчета метрики ошибки

Позиция документа, i RelUser RelPS diferRet к MetrikaErt

1 6 0 4 - 6-10 1 =4

2 8 9 1 0.5 8-9 —— » 0.5 = 0.25

3 5 8 3 0.5+3/3=1.5 5-8 — .1.5 = 1.5

4 3 7 4 1.5+4/4=2.5 3-7 -» 2.5 = 2.5 4

5 10 6 4 2.5 10-6 —-—«2.5 = 2

6 3 5 2 2.5-2/6=2.17 3-5 —-»2.17 = 0.72

7 3 4 1 2.17-1/7=2.03 3-4 —- » 2.03 = 0.29

8 4 3 1 2.03 4-3 ——»2.03 = 0.25 R

9 4 2 2 2.03+2/9=2.25 4-2 —-— * 2.25 = 0.5

10 2 1 1 2.25 2-1 -^-»2.25 = 0.23

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

Экспериментальное исследование метрики на выборке случайных запросо рассчитанной для пары [документ - запрос] показало, что предложенная метр очень чувствительна на наличие релевантных документов в первых стро результатов поиска. Данную метрику необходимо вычислять в совокупност остальными метриками.

Таким образом получается оптимальный набор метрик для оценки V полнота, точность, аккуратность, ошибка, F-мера, чувствительная метрика ошибо Данный набор метрик позволит сравнить методы поиска информации определить оптимальный метод взвешивания документа. Имея оценки экспертов

Estimate(Querylt Document¡, Expertс) по паре запрос Query, документ Document данного эксперта Expertc (где номер запроса, j — номер документа, с — номер эксперта), необходимо вычисл значения метрик Metrika.

В связи с тем, что несколько экспертов оценивают пару документ-запрос, то бу учитываться средняя оценка: EstimatejniiUe^Queryi, Documentу) — Estimate{Queryit Documentj,

Expertc), где CE — количество экспертов.

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

На вход модели поступает запрос пользователя, состоящий из терминов Q¡ = [termi,... .term cq}, где cq - количество терминов в запросе. Имеется индексный файл состоящий из терминов и номеров документа, в которых он встречается: Index - {(termin, idDocí,..., idDoc¡),..., (termin, idDocít..., idDocj)} Необходимо получить документы с данным термином:

nres _ (fires jres \

u — \uidD0Ci- — •uidDocci)

idDocj = FInd(term f, Index) где ci - количество индексов документа, idDocj - индекс документа, FInd(term Index) - функция получения индекса документа. При выполнении условий:

term 1 - termin, (1) 7*(Dres) -> min, (2) T(Dres) - время получения результирующего вектора документа.

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

Индексный файл Index разбиваем на части /nd¡, где et - количество терминов. При этом структура индексного файла выглядит следующим образом:

Indi = {idDoci,...,idDocci}. Термин разбиваемся на символы,

termy = (¿1u¿2u...u¿|tenn/|).

Конечный индексный файл находится по определенному пути, получаем его используя функцию Get(Lí U L2 U ... U ¿|£егтП;.|). Модифицированная модель представлена ниже:

г)res _ (fires fires \

и — \uidDocv'— •aidDoccl)<

Index = {Ind1 U Ind2 U ... U Indct},V termct, idDocj = FInd(lnd{),

¡ndi = Get(L1VL2U...ULltermjl),

term/" = (¿1U¿2U...U¿|term.|),

при выполнении условий 1, 2.

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

• размер индекса практически не отличается;

• скорость индексации на 30% выше, чем у инвертированных файлов;

• время ответа на 15% меньше, чем у инвертированных файлов.

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

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

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

1) Создается начальная популяция. Случайным образом из диапазо коэффициентов от Cmin до Стах (диапазон устанавливается для каждо алгоритма) подбираем кп наборов коэффициентов и переводим их в двоичн вид.

2) Вычисляется приспособленность хромосом. Оценивается ошибка для каждо набора коэффициентов.

3) Выбираются два родителя с наименьшей ошибкой для операции скрещивани

4) Выбираются хромосомы для операции мутации.

5) Оценивается приспособленность нового набора коэффициентов.

6) Если ошибка набора (nt) больше заданной ошибки (senter~), то переходим пункту 3, иначе пункт 7.

7) Полученный набор коэффициентов, который минимизирует ошибк возвращается в модель поиска.

Рассмотрены более детально основные аспекты:

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

• Ошибка оценивается по следующей формуле:

71

i=О

где r(di,qi') - средняя оценка документа экспертами, по запросу score(di,qi) - полученная релевантность документа dh по запросу qt.

Проведено экспериментальное исследование для получения оптимальнь операций скрещивания и мутации.

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

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

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

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

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

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

Также проведена оценка сложности генетического алгоритма. Из анализа операций получены две самые длительные операции:

• оценка ошибки, 0(50Кп), выполняется за tt сек;

• вычисление целевой функции 0(f)*0(Kn), выполняется за t2 сек.

Количество операций генетического алгоритма О (operation) равно:

О (operation) = i O(S0Kn)M50Kn) > 0(f) * 0(Кп), ^operation) |0(/) # 0(Кп) (К50Кп) < 0(/) „ 0(/fn)

Количество итераций ГА может варьироваться от одной до бесконечности, но имея ограничения по времени сверху tmax (по умолчанию в программе это значение равно 5 часам) и зная время итерации titer, получим, что нам необходимо It — (3600 * tmax)/titer итераций.

_ (tu ti > t2 Uer ~ U2, t2 > t,

Общая сложность алгоритма составит 0(деп) = О (It * operation). Данный ГА используется во всех экспериментальных исследованиях моделей информационного поиска, для которых было создано две базы запросов -документов. Первая база используется для обучения алгоритма, вторая для оценки. Тестовые коллекции были предоставлены организацией РОМИП, использовались две коллекции:

• псевдослучайная выборка сайтов из домена narod.ru объемом 728 ООО документов;

• набор, содержащий новостные сообщения из 25 источников и охватывающий 3 временных интервала (около 31 500 документов).

Были сформированы запросы трех типов:

• информационные запросы;

• навигационные запросы; •транзакционные запросы.

Всего сформировано около 5 000 запросов в равных соотношениях. В различных экспериментах использовалось различное количество запросов и документов - это обусловлено в основном временем выполнения запроса к базе документов.

Выполнено экспериментальное исследование алгоритмов поиска информации и их модификации с помощью ГА.

Булев поиск работает с запросами содержащими логические операции: И, НЕТ. Релевантность вычисляется по формуле:

Score(d,g) = ^gisi,

i=1

где l - количество зон документа (заголовок, сноски, текст), д^ - вес зо документа, s£ - значение фактора. Приведена оценка сложности алгоритма, кото составила 0(N).

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

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

В модели векторного пространства релевантность рассчитывается следующей формуле:

, (V(q)y(d))

score(q.d) = limif(dW

где V(q) - векторное представление запроса, V(d) — векторное представлен документа. В качестве векторов в эксперименте использовалась оценка веса запро wt q и нормированный вес термина в документе — wt d.

wt,q = tf * idf,

где tf — частота термина в запросе, idf - обратная документная часто вычисляемая по формуле:

idf = lgfr

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

wt.d = : . tf , , Jz'ilTtf2

Оценка сложности данного алгоритма составляет 0(N3).

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

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

Вероятностная модель - оценивает вес документа по схеме Okapi ВМ25 и рассчитывается по следующей формуле:

где tftd — частота термина t в документе d, a Ld и Lave — длина документа d и средняя длина документа во всей коллекции. Переменная —это положительный параметр настройки, с помощью которого производится калибровка частоты термина. Если /q = 0, то модель становится бинарной (частота термина не учитывается), а если параметр к1 принимает большие значения, то это эквивалентно прямому подсчёту частоты термина. Переменная b — еще один параметр настройки (0 < b < 1), определяющий нормировку по длине документа: b = 1 соответствует полноценному масштабированию веса термина с помощью длины документа, a b = 0 не предусматривает нормировки по длине.

Оценка сложности данного алгоритма составит 0(/V3).

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

Модификация модели обратной связи по релевантности. Имеется запрос пользователя и частично знание о релевантности документов. Алгоритм Роккио предлагает использовать модифицированный запрос qm .

d¡eDr dj€Dr

где q0 — оригинальный вектор запроса, Dr и Dnr — множества известных релевантных и нерелевантных документов соответственно, а, /? и у— веса каждого слагаемого. С помощью генетического алгоритма будем подбирать веса слагаемых и сравним с базовой моделью, в которой веса установлены рекомендуемым значениям: я = 1, Р = 0,75 и у = 0,15. Оценка сложности данного алгоритма составляет 0(/V2).

Как показали исследования, метод RF позволяет очень эффективно повысить релевантность результатов. Для его успешного использования необходимы запросы, в которых существует достаточно много релевантных документов. А использование генетического алгоритма позволяет еще улучшить данную модель на 5%.

В модификации языковой модели реализована функция дивергенции Кульбака-Лейблера, она позволяет оценить риск вернуть документ d в качестве релевантного запросу q между соответствующими языковыми моделями.

R(d;q) = KL{Md\\Mq)=YjP(,t\Mq)log^^)

Для подбора генетическим алгоритмом введем дополнительные коэффициенты gen:

gen1*P(t\Mq)

K(d;<7) = KL(Md\\Mq) = ^P(t|M4) log

t&¡ gen2 * P(t\Md)

Здесь Md — языковая модель документа d, Mq — языковая модель запроса - термины, входящие в запрос q.

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

Ht\Md) = П ^

1 Lteq bd

р(ФО = П tJr

1 i-teq ¡-■q

Где tft d, tftq— частота термина t в документе d и запросе q соответственн Ld, Lq — количество лексем в документе d и запросе q соответственно. Оце сложности данного алгоритма составляет 0(N2).

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

Проведены исследования современных средств полнотекстового noue Sphinx, Lucene, Xapian, они используют стандартные модели со свои модификациями, которые подразумевают встраивание коэффициентов подбираем с помощью ГА.

Все три алгоритма по-разному ведут себя для различных типов запрос данные представлены в таблице 2. Оптимальными являются: по информационн запросам Xapian показывает на 10% лучше; по транзакционным запросам Lucene 6%; по навигационным запросам Sphinx на 7%. По однословным запросам Xapian 5% лучше; по двухсловным Lucene на 15% лучше; по трехсловным Sphinx лучше 13%.

После подбора коэффициентов ГА, метрики улучшились в среднем на 12 Также алгоритмы перераспределились: по информационным запросам Sphii показывает на 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 Lucenc Sphinix / Lucene

Lucene Lucene Lucene

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

релевантности.

(FReW{Qj,dk), T(Qj~) — type1 FRel(Qj, dk) = | FRel2(Qj, dk), T(Qy) = type2 \FRelfC(Qj, dk). T(Qj) = typefc где - функция определения типа запроса.

Ограничения 1,2 сохраняются.

Проведен эксперимент, который показывает эффективность данного подхода. Благодаря внедрениям ГА, метрики улучшились в среднем на 12%, а после выбора модели поиска, для запроса получилось улучшить характеристики еще на 7%.

После всех изменений, характеристики полученной модели увеличились на

20%.

В четвертой главе приводится модель ИПС, включающая 6 уровней и 5 процессов. Основные процессы:

• обучение — эксперт вводит запросы и помечает релевантные документы;

• индексирование - из хранилища берутся адреса документов для индексирования, и строится необходимый индекс;

• поиск — по запросу пользователя отбираются документы и выдаются по мере уменьшения веса документа;

• анализ - анализируются запросы пользователей, их поведение;

• АРМ - набор пользовательских API функций для обращения к поисковой системе.

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

Рассмотрено внедрение ИПС на сервер в виде модуля, что позволило уменьшить число повторных запросов на 50% и время нахождения человека на странице на 65%. Описано внедрение ИПС с дополнительной опцией разграничения доступа в зависимости от ПК или пользователя на предприятии, имеющем 33 ПК. После внедрения ИПС на предприятии, время на передачу (поиск) информации уменьшилось на 40%.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

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

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

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

7. Разработаны программные продукты, реализующие предложенные модифика алгоритмов и позволяющие выполнять поиск по документам в Internet/Intra среде. Проведенные экспериментальные исследования предложенных реше показали увеличение значения параметров эффективности на 40%, уменьше числа повторных запросов на 50%.

8. Результаты диссертационной работы внедрены в рамках информационных сис предприятий «НГЧ» и ООО «ВелесВент». По теме диссертации опубликовано печатных работ, в том числе 3 в рекомендованных ВАК изданиях, получ свидетельство о регистрации программного продукта.

СПИСОК ОСНОВНЫХ ПУБЛИКАЦИЙ Публикации в ведущих изданиях, рекомендованных ВАК

1. Хорошко, М.Б. Модификация алгоритма булевого поиска / М. Б. Хорошк Известия высших учебных заведений. Северо-Кавказский регион. Сер Технические науки. - 2011 № 3 - С. 14-18

2. Воробьев С.П., Хорошко, М.Б. Модификация модели векторного простран для ранжирования документов/ Воробьев С.П., Хорошко, М.Б// Электронн журнал «Инженерный вестник Дона», 2012 г. http://www.ivdon.ru/magazine/archive/n3v2012/976

3. Воробьев С.П., Хорошко, М.Б. Модификация схемы ВМ25 с помо генетического алгоритма / Воробьев С.П., Хорошко, М.Б// Электронный жур «Инженерный вестник Дона», 2012 г. http://www.ivdon.rU/magazine/archive/n4tly2012/l 177

Публикации в сборниках научных статей, трудов и материалов конференщ

4. Хорошко М.Б. Обзор математических моделей информационного поиск Компьютерные технологии в науке, производстве, социальных и экономичес процессах : материалы VII Междунар. науч. - практ. конф., г. Новочеркасск, ноября 2007 г. / Юж. - Рос. гос. техн. ун-т (НПИ). - Новочеркасск: ЮРГТУ, 20 С. 83-89.

5. Хорошко М. Б. Информационно-поисковая система для интернета. // Теор методы проектирования, программно-техническая платформа корпоративн информационных систем : материалы VI Междунар. науч. - практ. конф.

Новочеркасск, 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

V\

корпоративных информационных систем : материалы VIII Междунар на практ. конф., г. Новочеркасск, июнь 2010 г. / Юж. - Рос. гос. техн ун-т <НГ Новочеркасск : ЮРГТУ, 2010. - С. 76-80.

16. Хорошко М. Б Использование модифицированной модели обратной связ релевантности. // Теория, методы проектирования, программно-техниче платформа корпоративных информационных систем : материалы XI Между

nPfrKT' К°НФ" П НовочеРкасск> 28 мая 2013 г. / Юж. - Рос. гос. техн (НИИ). - Новочеркасск : ЮРГТУ, 2013. - С. 71-79.

17. Хорошко М. Б. Оценка алгоритмов поиска информации CPHIKS LUCE XAPIAN. // Теория, методы проектирования, программно-техниче платформа корпоративных информационных систем : материалы XI Между науч. - практ. конф., г. Новочеркасск, 28 мая 2013 г. / Юж. - Рос. гос техн (НИИ). - Новочеркасск : ЮРГТУ, 2013. - С. 79-85.

Личный вклад автора в работах, опубликованных в соавторстве-

1; "°ДИФГ1ИЯ МТЛИ вект°РН0Г0 пространства для ранжирова документов; [3] - модификация схемы ВМ25 с помощью генетическ алгоритма. 'мсш^к

Соискатель

Хорошко М.Б.

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования «Южно - Российский государственный политехнический университет (НПИ) имени М. И. Платова»

04201458254 На правах рукописи

Хорошко Максим Болеславович

РАЗРАБОТКА И МОДИФИКАЦИЯ МОДЕЛЕЙ И АЛГОРИТМОВ ПОИСКА ДАННЫХ В INTERNET/INTRANET СРЕДЕ ДЛЯ УЛУЧШЕНИЯ КАЧЕСТВА ПОИСКА

Специальность 05.13, 17 - «Теоретические основы информатики»

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель -кандидат технических наук, доцент С.П. Воробьев

Новочеркасск, 2014 г.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ...................................................................................................5

1. АНАЛИЗ ИНТЕРНЕТ ТЕХНОЛОГИЙ И ФОРМАЛИЗАЦИЯ ПРОБЛЕМЫ ИНФОРМАЦИОННОГО ПОИСКА............................................11

1.1 Классификация поисковых систем и моделей информационного поиска......................................................................................11

1.2 Особенности реализации технологии информационно-поисковой системы...............................................................................................................17

1.3 Анализ существующих постановок и методов решения задачи оптимизации информационного поиска..........................................................31

1.4 Формализация проблемы оптимизации информационного поиска и построение математической модели ИПС...................................................39

Выводы по главе 1...................................................................................44

2. ФОРМИРОВАНИЯ НАБОРА МЕТРИК ЭФФЕКТИВННОСТИ ДЛЯ ОЦЕНКИ СИСТЕМ ИНФОРМАЦИОННОГО ПОИСКА................................45

2.1 Постановка задачи оценки информационно-поисковой системы 45

2.2 Метрики оценки информационно-поисковых систем..................48

2.3 Экспериментальное исследование предложенной метрики ошибок ..............................................................................................................................62

2.4 Оценка релевантности и выбор оптимального набора метрик.....64

2.5 Оценка качество системы и её полезность для пользователя.......71

Выводы по главе 2...................................................................................74

3. МЕТОДЫ ПОСТРОЕНИЯ ИНДЕКСА ПОИСКОВОЙ СИСТЕМЫ. 75

3.1 Метод инвертированных и сигнатурных файлов...........................77

3.2 Суффиксные массивы.......................................................................80

3.3 Построение индекса в виде дерева..................................................82

3.4 Индексные структуры для нечетких сравнений.............................90

Хеширование по сигнатуре.....................................................................91

3.5 Модификация метода инвертированных файлов...........................92

3.6 Экспериментальное исследование методов построения индекса 95

Выводы по главе 3...................................................................................97

4. МОДИФИКАЦИЯ АЛГОРИТМОВ ОПТИМИЗАЦИИ ИНФОРМАЦИОННОГО ПОИСКА И ИХ ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ................................................................................................98

4.1 Описание генетического алгоритма для системы поиска и оценка сложности...........................................................................................................99

4.2 Описание экспериментальных исследований...............................104

4.3 Модификация алгоритмов булевого поиска и их экспериментальное исследование..................................................................107

4.4 Модификация модели векторного пространства для ранжирования и экспериментальное исследование алгоритмов..........................................112

4.5 Модификация вероятностной модели информационного поиска и экспериментальное исследование..................................................................119

4.6 Экспериментальное исследование модификации методов обратной связи по релевантности..................................................................123

4.7 Экспериментальное исследование модификации языковых моделей информационного поиска................................................................129

4.8 Оценка алгоритмов поиска информации Sphinx, Lucene, Xapian ............................................................................................................................134

4.9 Улучшенная модель поиска............................................................141

Выводы по главе 4.................................................................................146

5. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ ИНФОРМАЦИОННОГО ПОИСКА И ИХ ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ ...............................................................................................................................148

5.1 Модель информационно-поисковой системы..............................148

5.2 Имитационные модели информационно-поисковой системы.... 151

5.3 Проектирование приложения - информационно поисковой системы IRSI.....................................................................................................158

5.4 Программная реализация алгоритмов...........................................170

Выводы по главе 5.................................................................................175

ЗАКЛЮЧЕНИЕ.........................................................................................176

ЛИТЕРАТУРА...........................................................................................178

ПРИЛОЖЕНИЕ А.....................................................................................188

ПРИЛОЖЕНИЕ Б.....................................................................................223

ПРИЛОЖЕНИЕ В.....................................................................................224

ПРИЛОЖЕНИЕ Г.....................................................................................225

ВВЕДЕНИЕ

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

В настоящее время работает ряд авторитетных международных конференций, посвященных обсуждению вопросов информационного поиска, например, таких как: WWW (World Wide Web) Conference -специально организованная конференция для решения задач связанных с Интернет; TREC (Text Retrieval Conference) - серия конференций, сконцентрированных на исследовании различных областей информационного поиска и их задач. Она поддерживается National Institute of Standards and Technology (NIST) и Association of Religion Data Archives (ARDA), расположенных в США, начиная с 1992. Целью TREC является поддержка исследований сообщества информационного поиска с помощью предоставления инфраструктуры, необходимой для развития его технологий. Из Российских конференций посвященные вопросам информационного поиска, можно выделить всероссийскую конференцию «Электронные библиотеки» (RCDL).

Также вопросами улучшения качества поиска и внедрением информационно-поисковых систем, занимаются коммерческие организации Яндекс, Галактика-Зум Sphinx, Lucene, Google и др.

Многие системы поиска информации проходят тестирование на конференциях TREC, WWW Conference, таким образом задавая приоритетные направления для проведения исследований в области поиска.

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

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

Диссертационная работа выполнена в рамках научного направления ФГБОУ ВПО ЮРГПУ(НПИ) им М.И. Платова «Теория, принципы и технологии построения информационно-вычислительных и измерительных систем», госбюджетной темы 7.05 «Разработка теории, методов оптимизации функциональной и программно-технической платформы корпоративных информационных систем» (Утверждено решениями ученого совета от 25.04.2001г. и 15.05.2003г).

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

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

Для достижения поставленной цели решаются следующие задачи:

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

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

3. Разработка и исследование модификаций методов построения индекса.

4. Анализ и разработка модификации алгоритмов информационного поиска в части расчета критерия релевантности документа.

5. Разработка имитационной модели информационно-поисковой системы с целью возможной оценки предлагаемых технических решений.

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

Объектом исследования является технология функционирования, методы построения индексов, метрики оценки, модели и алгоритмы информационно-поисковых систем.

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

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

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

Основные положения выносимые на защиту.

1. Новая метрика «Чувствительная метрика ошибок», которая оценивает первые N - документов на соответствие полученной релевантности. Чем выше документ в списке, тем меньше допустима ошибка, т.к. пользователи просматривают документы по порядку.

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

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

4. Модификация алгоритмов поиска информации Sphinx, Lucene, Xapian с помощью генетического алгоритма, позволяющая улучшить характеристики модели корпоративного поиска.

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

6. Имитационная модель информационно-поисковой системы, позволяющая оценить эффективность принятых теоретических и технических решений при построении серверной и клиентской части программного комплекса.

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

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

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

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

Реализация результатов работы. Разработанные в диссертационной работе теоретические и практические результаты внедрены в ООО «ВелесВент», ОАО «НГЧ».

Разработанный программный продукт имеет свидетельство об официальной регистрации программных систем и баз данных в Российском агентстве по патентам и товарным знакам (РОСПАТЕНТ): • программная система IRSI/ Информационно-поисковая система информации в Intranet/Internet среде. Зарегистрировано в Реестре программ для ЭВМ 6.07.2011 г., per. № 2011616861

Апробация работы и публикации. Основные положения диссертации и отдельные ее результаты обсуждались и получили положительные отзывы на:

• VII Международной научно-практической конференции «Моделирование, Теория, методы и средства», 2007г. (г. Новочеркасск)

• Научно-технической конференции студентов и аспирантов ЮРГТУ (НПИ) «Студенческая весна 2008» (г. Новочеркасск)

• VIII Межрегиональной научно-практической конференции студентов и аспирантов, 2008 г. (г. Новокузнецк)

• II Российской летней школе по информационному поиску, 2008г. «RuSIR 2008» (г. Таганрог)

• VII, XI Международной научно-практической конференции «Теория, методы, проектирования, программно-техническая платформа корпоративных информационных систем», 2009г, 2013г. (г. Новочеркасск)

• IV Российской летней школе по информационному поиску, 2010г. «RuSIR 2010» (г. Воронеж)

По теме диссертации опубликовано 17 статей, три из них в рекомендованных ВАК изданиях, получено свидетельство о регистрации программного продукта.

Структура диссертационной работы. Диссертация содержит 173 станицы основного текста, 74 рисунка, 22 таблицы и состоит из введения, пяти глав, заключения, списка литературы из 100 наименований и трех приложений объемом 38 страниц.

и

1. АНАЛИЗ ИНТЕРНЕТ ТЕХНОЛОГИЙ И ФОРМАЛИЗАЦИЯ ПРОБЛЕМЫ ИНФОРМАЦИОННОГО ПОИСКА

1.1 Классификация поисковых систем и моделей информационного поиска

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

Информационный поиск — это один из ключевых механизмов доступа пользователей к нужной им информации. Один из первых фундаментальных обзоров задач информационного поиска и информационно-поисковых систем был представлен в работе Рейзенберга, «Information Retrieval» [9], и не смотря на то, что данная работа была опубликована в 1979 году, это до сих пор один из полных и исчерпывающих обзоров по информационному поиску.

Существующие информационные системы, работающие с электронными документами, можно условно разделить на две категории: информационно-поисковые системы (в зарубежной терминологии они фигурирую под термином information retrieval systems), и системы выборки данных [10]. Стоит отметить, что данная классификация условна и в её контексте многие современные информационные системы совмещают в себе свойства как систем выборки данных, так и информационно-поисковых систем. Базовые отличия этих двух систем представлены в таблице 1.1.

Таблица 1.1 Базовые отличия систем выборки данных и ИПС

Наименование Система выборки данных Информационно поисковая система

Соответствие данных поисковому запросу точное частичное

Классификация документов детерминированная вероятностная

Язык запросов искусственный естественный

Критерии выборки документов булева функция релевантности вероятностная функции релевантности

Устойчивость к ошибкам в данных и запросах неустойчивы устойчивы

Типичным примером систем выборки данных являются классические реляционные СУБД, где в качестве языка запросов используется тот или иной диалект языка запросов SQL. В современных системах выборки данных основной задачей является обеспечение надёжного и эффективного хранения данных, а также высокой скорости в�