Содержание к диссертации
Введение
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
- Анализ существующих постановок и методов решения задачи оптимизации информационного поиска
- Оценка релевантности и выбор оптимального набора метрик
- Индексные структуры для нечетких сравнений
- Модификация алгоритмов булевого поиска и их экспериментальное исследование
Введение к работе
Актуальность проблемы. Объемы обрабатываемой электронной информации нарастают большими темпами - этому способствует активное внедрение мультимедиа, широкое распространение корпоративных и глобальных сетей, отказ большинства предприятий от бумажного документооборота и переход на автоматизированные системы управления предприятием. В подобной ситуации резко возросла потребность в системах поиска и анализа данных, а также возник спрос на интеллектуализацию информационно-поисковых систем (ИПС).
В настоящее время работает ряд авторитетных международных конференций, посвященных обсуждению вопросов информационного поиска, например, таких как: TREC (Text Retrieval Conference) - серия конференций, сконцентрированных на исследовании различных областей информационного поиска и их задач. Она поддерживается National Institute of Standards and Technology (NIST) и Association of Religion Data Archives (ART)А), расположенных в США, начиная с 1992. Целью TREC является поддержка исследований сообщества информационного поиска с помощью предоставления инфраструктуры, необходимой для развития его технологий; WWW (World Wide Web) Conference - специально организованная конференция для решения задач, связанных с Интернет.
Из Российских конференций, посвященных вопросам информационного поиска, нужно отметить ежегодную всероссийскую конференцию «Электронные библиотеки» (RCDL). Кроме того, существуют коммерческие организации, занимающиеся не только вопросами исследований, но и внедрением информационных технологий, это такие известные организации как Яндекс, Рамблер, Апорт, Галактика-Зум, ABBYY-FTR, АОТ и др.
Высокий авторитет конференций TREC, WWW Conference и участие в них ведущих исследовательских коллективов и разработчиков технологий информационного поиска во многом определяет приоритетные направления исследований и задает общие принципы развития поисковых систем.
Ряд авторитетных исследователей внесли своими научными трудами значительный вклад в развитие информационно-поисковых систем: И.С. Некрестьянов, И.Е. Кураленок, В.Ю. Добрынин, А.Г. Дубинский, А.Е. Ермаков, М.Р. Когаловский, А.В. Сокирко, G. Salton, A. Singhal, М. Mitra, S. Lawrence, P. Foltz, E. Fox, J. Cho, R. Baeza-Yates, K. Tajima, С 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. Модификация алгоритмов поиска информации Sphinx, Lucene, Xapian с помощью генетического алгоритма, позволяющая улучшить характеристики модели корпоративного поиска.
5. Модель поиска, которая выбирает алгоритм ранжирования в зависимости от количества слов и типа информационного запроса. Данная модель позволяет улучшить такие характеристики системы, как: полнота, точность, ошибка. 6. Имитационная модель информационно-поисковой системы, позволяющая оценить эффективность принятых теоретических и технических решений при построении серверной и клиентской части программного комплекса.
7. Модификация архитектуры информационно-поисковой системы, позволяющая уменьшить количество операций чтение/запись из хранилища.
Теоретическая ценность работы заключается в построении и исследовании моделей информационно поисковых систем, методов построения индекса.
Практическая ценность. Совокупность полученных теоретических и практических результатов может использоваться для построения корпоративных и интерфейсных информационно-поисковых систем, позволяющих повысить качество результатов поиска.
Для практического применения системы в диссертации создан программный продукт (IRSI), позволяющий выполнять поиск в корпоративной информационной среде и нескольким сайтам.
Реализация результатов работы. Разработанные в диссертационной работе теоретические и практические результаты внедрены в ООО «ВелесВент», ОАО «НГЧ». Разработанный программный продукт имеет свидетельство об официальной регистрации программных систем и баз данных в Российском агентстве по патентам и товарным знакам (РОСПАТЕНТ): программная система IRSI/ Информационно-поисковая система информации в Intranet/Internet среде. Зарегистрировано в Реестре программ для ЭВМ 6.07.2011 г., рег. № 2011616861
Оценка релевантности и выбор оптимального набора метрик
Информационный поиск представляет собой преимущественно эмпирическую дисциплину, требующую тщательной и осторожной оценки эффективности новых методов на тестовых коллекциях документов. Основным показателем полезности поиска является удовлетворение пользователя, которое, в свою очередь, зависит в том числе и от скорости ответа и размера индекса. При этом вполне естественно предположить, что релевантность результатов является самым важным фактором. Однако мнение пользователей не всегда совпадает с представлениями разработчиков о качестве системы. Например, степень удовлетворения пользователя обычно очень сильно зависит от интерфейса (включая вёрстку страницы), ясность представления результатов и скорость отклика – хотя эти понятия не связаны с качеством возвращаемых результатов.
Постановка задачи оценки информационно-поисковой системы Для оценки стандартным способом информационно-поисковой системы по произвольным запросам необходима тестовая коллекция, состоящая из трех компонентов[43]. 1) Коллекция документов. 2) Набор тестовых информационных потребностей, выраженных в виде запросов. 3) Набор оценок релевантности, представленных, как правило, в виде бинарных утверждений релевантный и нерелевантный относительно каждой пары «запрос-документ».
Стандартный подход к оценке информационно-поисковых систем опирается на понятие релевантных и нерелевантных документов. В соответствии с информационными потребностями пользователей документ из тестовой коллекции проходит бинарную классификацию: релевантный или нерелевантный. Это решение называется эталонной (gold standard or ground truth) оценкой релевантности. Коллекция тестовых документов и на 46
бор информационных потребностей должны иметь достаточный объём: оценку следует усреднять по действительно большой совокупности тестов, поскольку результаты поиска сильно отличаются для разных документов и информационных потребностей. В качестве первого очень грубого приближения достаточным минимумом считается набор из 50 информационных потребностей [44].
Релевантность оценивается по отношению к информационной потребности, а не по запросу. Например, информационная потребность может быть сформулирована так. «Правда ли, что процессоры Intel более производительны для расчета математических моделей, чем Athlon?»
Этот вопрос можно преобразовать в запрос следующего вида, который использует булевы операции: [Процессор AND Intel AND Athlon AND производительны AND расчета AND математических AND моделей] Документ является релевантным, если он соответствует заданной информационной потребности, а не просто если он содержит все слова из запроса. По однословному запросу системе трудно понять, в чём заключается информационная потребность, а пользователю она известна и он оценивает полученные результаты на основе своей информационной потребности. Для того чтобы оценить систему, необходимо явно сформулировать информационную потребность, относительно которой будут судить о релевантности или нерелевантности найденных документов. Для оценки релевантности используется бинарное решение.
Большинство метрик, применяемых в современной оценке текстового поиска, основываются на отношении релевантности документа запросу. Метрики для неупорядоченного множества документов основаны на бинарной классификации документов «релевантен/не релевантен» по отношению к выбранному запросу. Данные метрики основываются на матрице классификации представлены в таблице 2.1. Таблица 2.1. Классы информационных ресурсов по отношению к их включению в ответ и релевантности
Здесь a — количество документов, найденных системой и релевантных с точки зрения экспертов; Ъ — количество документов, найденных системой, но не релевантных с точки зрения экспертов; с — количество релевантных документов, не найденных системой; d — количество нерелевантных документов, не найденных системой.
Многие системы содержат разные веса (часто называемые параметрами), с помощью которых можно настроить их производительность. При оценке таких систем не следует учитывать результаты поиска по тестовой коллекции, полученные путем подбора параметров, обеспечивающих максимум производительности для данной коллекции. Это объясняется тем, что такая настройка завышает ожидаемую производительность системы, поскольку веса специально настраиваются так, чтобы обеспечить максимальную производительность на конкретном множестве запросов, а не на случайной их выборке. В таких случаях необходимо сформировать одну или несколько рабочих тестовых коллекций документов и подбирать параметры для них. После этого система с настроенными параметрами проходит испытание на тестовой коллекции. Результаты, полученные при таком тестировании, можно рассматривать как несмещённую оценку производительности системы [43].
Индексные структуры для нечетких сравнений
Если система информационного поиска уже создана и эксплуатируется многочисленными пользователями, то её разработчики могут оценить возможные изменения, развернув разные варианты системы и фиксируя показатели, свидетельствующие об удовлетворённости пользователей тем или иным вариантом. Этот метод часто используется в системах веб-поиска.
Чаще всего используется метод А/В теста [42]. В ходе такого теста в функционирующей системе изменяется только один аспект и на её модифицированный вариант случайным образом направляется небольшая доля трафика (скажем, 1-10% пользователей), в то время как большинство пользователей по-прежнему применяют текущую версию. Например, если исследуется модификация алгоритма ранжирования, то можно перенаправить случайную выборку пользователей на новый вариант системы и оценить определенные показатели, такие как частота кликов по первым позициям выдачи или по любому результату на первой странице. (Этот конкретный вариант метода называется анализом кликов (методом неявной обратной связи).
В основе А/В-тестирования лежит проведение серии тестов (последовательно или параллельно), в каждом из которых исследуется влияние только одной переменной. При выполнении каждого теста изменяется только один параметр по сравнению с контрольной версией (текущей версией системы). Это позволяет легко выяснить, положительно или отрицательно влияет изменение этого параметра на работу системы. Такое тестирование работающей системы позволяет просто оценить влияние изменений на пользователей и, при достаточно большом количестве пользователей, учесть даже очень маленькие эффекты. В принципе, изменяя одновременно несколько параметров случайным образом, можно было бы использовать более мощные аналитические методы многомерного статистического анализа, например множественную линейную регрессию. Однако на практике А/В -тестирование используется широко, поскольку его легко организовать, понять и объяснить руководству.
Выводы по главе 2
1) Рассмотрены основные метрики используемые для оценке эффективности ИПС, проанализированы их достоинства и недостатки.
2) Предложена новая метрика ошибок, которая заключается в оценке первых iV - документов на соответствие полученной релевантности и релевантности экспертов: чем выше документ - тем меньше допустимая ошибка, т.к. пользователи просматривают документы по порядку.
3) Проведена экспериментальная оценка предложенной метрики ошибок по сравнению с точностью, полнотой и F-мерой, показана ее эффективность.
4) В качестве метрики для определения оптимального алгоритма предложено использовать комплексный подход, включающий, набор метрик: полнота - характеризует способность системы находить нужные пользователю документы, но не учитывает количество нерелевантных документов, выдаваемых пользователю; точность - характеризует способность системы выдавать в списке результатов только релевантные документы; аккуратность - показывает отношение правильно принятых системой решений к общему числу решений; ошибка - показывает отношение неправильно принятых системой решений к общему числу решений; F-мера - единая метрика, объединяющая метрики полноты и точности в одну метрику; чувствительная метрика ошибок - показывает, насколько более релевантные документы находятся выше в результатах поиска. Большинство современных информационно-поисковых систем для осуществления поиска строят на основе исходной информации логические и физические структуры данных, представляющие собой поисковый индекс, который позволяет реализовать некоторую заданную модель информационного поиска. Преобразование информации в информационно-поисковых системах строящих поисковый индекс, обычно состоит из следующих базовых этапов:
1) Анализ данных исходного множества текстовых документов и их преобразование в вид, удобный для построения полнотекстового индекса вычислительной машиной, выделение из документов содержательной информационной основы.
2) Анализ данных полученных в пункте 1. и последующее построение поискового индекса. В данном случае индекс является представлением данных, логическая модель которого определяет способ обработки и интерпретации данных и позволяет осуществлять информационный поиск.
3) Преобразование поисковых запросов в формат, позволяющий использовать поисковый индекс для вычисления функции релевантность запросов и документов и выборки релевантных запросу документов. При обработке информации и построении поискового индекса потенциально можно использовать достаточно широкий спектр методов анализа текстовой информации документов, как например методы статистического, семантического, синтаксического и лингвистического анализа текста. Однако методы, анализирующие семантику и синтаксис текстовой информации [49,50], вплоть до настоящего времени не получили широкого распространения ввиду своей сложности и относительно низкой эффективности.
Модификация алгоритмов булевого поиска и их экспериментальное исследование
На основе анализа существующих поисковых алгоритмов был выявлен основной существенный недостаток - алгоритмы не подстраивается под существующие документы. Данная проблема очень актуальна т.к. в различных организациях и бизнес-процессах кардинально меняется тип документов, а каждый тип документов необходимо ранжировать по разному: например, бухгалтерские бланки чем новее, тем более актуальны, а в характеристиках продукции большее значение имеет полное соответствие запросу. Очевидно, что данная задача относится к классу NP-сложных задач (классификация в теории вычислительной сложности). Для решения такого типа задач в большинстве случаев используются эвристические алгоритмы -поэтому возможно использование генетических алгоритмов (ГА) для автоматической подстройки информационно поисковой системы. Выделяют три особенности алгоритма эволюции: каждое новая популяция состоит только из «жизнеспособных» хромосом; каждая новая популяция «лучше» (в смысле целевой функции) предыдущей; в процессе эволюции последующая популяция зависит только от предыдущей [86]. ГА согласно [86] отличаются от других оптимизационных и поисковых процедур следующим: работают в основном не с параметрами, а с закодированным множеством параметров; осуществляют поиск из популяции точек, а не из единственной точки; используют целевую функцию, а не ее различные приращения для оценки информации; используют не детерминированные, а вероятностные правила. Генетический алгоритм берет множество натуральных параметра оптимизационной проблемы и кодирует их как последовательность конечной длины в некотором конечном алфавите. ГА работает до тех пор, пока не будет выполнено заданное количество генераций или на некоторой генерации не будет получено решение заданного качества (возникнет преждевременная сходимость, когда найден локальный оптимум), или ГА не может найти из него выход. В отличие от других методов оптимизации, генетические алгоритмы как правило анализируют различные области пространства решений одновременно и более приспособлены к нахождению новых областей с лучшими значениями целевой функции за счет объединения квазиоптимальных решений из разных популяций.
Описание генетического алгоритма для системы поиска и оценка сложности Эволюционный процесс представляется как способность «лучших» хромосом оказывать большее влияние на состав новой популяции на основе длительного выживания и более многочисленного потомства [32].
Основные этапы процесса эволюции, на основе которого создаются нужные схемы генетического поиска, согласно Холланду следующие [8]: 1) Конструирование начальной популяции. Вводится точка отчета поколений t = 0. Вычисляется приспособленность хромосом популяции, а затем средняя приспособленность популяции. 2) Установка t = t + 1. Выбираются два родителя (хромосомы) для кроссинговера. Он выполняется случайным образом пропорционально приспособляемости родителей. 3) Формирование генотипа потомка. С заданной вероятностью производится над генотипами выбранных хромосом кроссинговер. Выбирают один из потомков A(t) с 100 вероятностью 0,5 и сохраняют его, как члена новой популяции. Последовательно применяют к A(t) оператор инверсии, а затем мутации с заданными вероятностями. Полученный генотип потомка сохраняют как A (t). 4) Отбор хромосомы случайным образом для исключения ее из популяции. Обновление текущей популяции заменой отобранной хромосомы на A (t). 5) Определение приспособленности (целевой функции) A (t) и пересчет средней приспособленности популяции. 6) Если t = заданному, то переход к шагу 7, если нет, то переход к шагу 2. 7) Конец работы.
Рассмотрим более детально основные аспекты: Все коэффициенты генерируется изначально случайным образом по равномерному закону при ограничении сверху и снизу. Затем переводятся в двоичный вид, чтобы можно было применять операции скрещивания и мутации. Ошибка оценивается по следующей формуле: п є = У(г(сіііЧі) - score{di qi))2, i=o где r(di,qi)– средняя оценка документа dt экспертами, по запросу qt; score(di, qi) - полученная релевантность документа dt по запросу qt. Проведем экспериментальное исследование, для получения оптимальных операций скрещивания и мутации.
Операция отбора. После проведения экспериментов, в которых хромосомы выбирались по различным критериям: L - лучших; S - средних; Н - худших; Nkr - случайных, и их комбинаций . Было выявлено, что для более быстрого получения максимума целевой функции отбор хромосом должен осуществляться по следующему принципу. Для операции скрещивания берется две самых лучших хромосомы и случайным образом Nkr хромосом. Для операции мутации берется две хромосомы с самой низкой приспособленностью и Nmut хромосом.
Операция скрещивания. Для выбора оптимальной операции были проведены эксперименты с точками разрыва в К местах при двойном, тройном и четвертном кроссинговере. В результате определились два оптимальных метода, показанные на рисунке 3.1.
Для проверки эффективности, случайным образом делалась выборка запросов от одного до ста. В качестве параметра, определяющего оптимальность, бралась средняя оценка релевантности выдачи по данным запросам. Во время эксперимента отключались другие операции. Таким образом, функция достигает максимума при сращивании методом «расчески» и очень близко при скрещивании «пополам» (рис. 4.1). Решено оставить оба варианта в алгоритме и эксперименты доказали эффективность выбранного способа. По различным запросам метод расчески достигает максимальной точки по одному набору запросов, метод пополам по двум, а использование двух методов по четырем.
