Разработка методов и инструментальных средств повышения пертинентности поиска в современных информационных средах

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

ТЕРЕХОВ Алексей Андреевич

Разработка методов и инструментальных средств
повышения пертинентности поиска
в современных информационных средах

Специальность 05.13.17 – «Теоретические основы информатики»

АВТОРЕФЕРАТ

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

кандидата технических наук

Москва 2010

Работа выполнена на кафедре вычислительной и прикладной математики ГОУВПО «Рязанский государственный радиотехнический университет».

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

Белов Владимир Викторович

Официальные оппоненты: доктор технических наук, профессор

Ковшов Евгений Евгеньевич

кандидат технических наук, доцент

Елхов Алексей Викторович

Ведущая организация: Филиал ФГУП
ГНПРКЦ «ЦСКБ Прогресс»
ОКБ «Спектр»

Защита состоится « » _______2010 г. в ____ часов на заседании диссертационного совета Д 212.147.03 при Московском государственном университете печати по адресу 127550, г. Москва, ул. Прянишникова, дом 2А

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

Автореферат разослан “___” 2010 г.

Ученый секретарь доктор технических наук

диссертационного совета: профессор Агеев В.Н.

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

Актуальность проблемы. Накопленные к настоящему времени колоссальные объемы информации в совокупности с непрерывно увеличивающимися темпами её роста определяют актуальность и значимость исследований в области информационного поиска. Бурное развитие сетевых технологий, в том числе и Интернета, способствуют значительному увеличению доступных информационных ресурсов и объемов передаваемой информации. Зачастую это разнородная, слабо структурированная и избыточная информация, обладающая высокой динамикой обновления.

При сегодняшних объемах доступной информации решение задач информационного поиска является приоритетным для обеспечения своевременного доступа к интересующим данным в рамках информационной среды (ИСр).

Концепция информационной среды впервые была предложена Ю.А. Шрейдером, который рассматривает информационную среду не только как проводника информации, но и как активное начало, воздействующее на её участников. Информационная среда – совокупность технических и программных средств хранения, обработки и передачи информации, а также социально-экономических и культурных условий реализации процессов информатизации.

В настоящее время работает ряд авторитетных международных конференций, посвящённых обсуждению вопросов информационного поиска, например, таких как:

• TREC (Text Retrieval Conference) – цикл конференций организованный под эгидой NIST (National Institute for Standards and Technology) – одного из авторитетных органов стандартизации информационных технологий в США;
• SIGIR (Special Interest Group on Information Retrieval) – цикл конференций проводимых ACM SIGIR (ACM – Association of Computing Machinery) –международной группой специалистов по информационному поиску;
• WWW (World Wide Web) Conference – специально организованная конференция для решения задач, связанных с Интернет.

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

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

Также необходимо отметить ряд отечественных научных школ:

• SPBU IR Group – исследовательская группа в области информационного поиска (Санкт-Петербургский Государственный Университет);
• Исследовательский центр ИИ ИПС РАН;
• Центр информационных исследований (НИВЦ МГУ).

Кроме того, существуют коммерческие организации, занимающиеся не только вопросами исследований, но и вопросами внедрения информационных технологий, это такие известные организации как Яндекс, Рамблер, Апорт, НейрОК, Гарант-Парк-Интернет, Галактика-Зум, ABBYY-FTR, AOT и др.

Ряд авторитетных исследователей внесли своими научными трудами значительный вклад в развитие информационно-поисковых систем: И.С. Некрестьянов, И.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. Kleinberg, J. Sparck, D. Carmel, S. Brin, L. Page, A. Singhal., T. Haveliwala.

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

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

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

Задачи исследования. Для достижения целей диссертационной работы необходимо решение следующих задач.

1. Формализация описаний факторов ранжирования поисковых систем сети Интернет.
2. Модификация существующих факторов ранжирования, слабо защищенных от влияния искусственно создаваемых непродуктивных связей между компонентами сети.
3. Создание методологии оценки пертинентности информационного поиска на основе экспертных оценок.
4. Разработка концепции поисковой системы многоальтернативного поиска и адаптивного переранжирования.

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

Научная новизна работы состоит в следующем.

1. Созданы новые методики: 1) расчета основных факторов ранжирования документов с алгоритмической завершённостью вычислительных процедур; 2) экспертной оценки пертинентности документов на основе показателей контентной эквивалентности; 3) вычисления PageRank страниц для произвольного фрагмента сети.

2. Предложены новые количественные показатели: 1) контентной эквивалентности двух последовательностей разной длины как числовых, так и лингвистических; 2) пертинентности откликов поисковых систем на запросы пользователей (пертинентностная точность выдачи; подлинная пертинентность документа; максимальная пертинентность документов выдачи; кумулятивная пертинентность выдачи; векторная пертинентность выдачи; средние значения указанных ранее показателей, вычисляемые по 32-м точечным значениям); 3) авторитетности страниц ресурсов сети Интернет.

3. Сформулированы и доказаны теоремы, определяющие: 1) свойства показателей контентной эквивалентности; 2) диапазон возможных значений показателя авторитетности страниц произвольного фрагмента сети Интернет; 3) зависимость показателя авторитетности страниц произвольного фрагмента сети Интернет от авторитетности страниц, не вошедших в рассматриваемый фрагмент.

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

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

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

Для практического воплощения концепции интерфейсной поисковой системы в диссертации созданы два программных продукта (AltoSearch/АльтПоиск и SearchAnalizer/ПоискАнализатор), позволяющие автоматически формировать общую выдачу – обобщённый набор документов, получаемых от нескольких поисковых систем сети Интернет в ответ на запрос пользователя и расчет показателей контентной эквивалентности. Создан макет интерфейсной поисковой системы, опытная эксплуатация которого в рабочем процессе ООО «Мегапром» показала повышение подекадного среднего значения подлинной пертинентности на 10 – 18 % по сравнению с популярными поисковыми системами.

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

Реализация и внедрение результатов работы. Разработанные в диссертационной работе теоретические и практические результаты внедрены в ООО «Мегапром», ОАО «Рязанский проектно-технологический институт» (ОАО РПТИ), в ГОУВПО «Рязанский государственный радиотехнический университет» (ГОУВПО РГРТУ).

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

1. программная система SearchAnalizer/ ПоискАнализатор. Зарегистрировано в Реестре программ для ЭВМ 24.04.2009 г., рег. № 2009612105;
2. программа AltoSearch/АльтПоиск. Зарегистрировано в Реестре программ для ЭВМ 24.04.2009 г., № 2009612104.

Информация о регистрации указанных программ содержится в журнале: Программы для ЭВМ, базы данных, топологии интегральных микросхем (RU ОБПБТ) № 3 (68). 2009 г. С. 90.

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

1. Формализованные описания основных факторов ранжирования поисковых систем сети Интернет и методика их расчета.
2. Показатели контентной эквивалентности двух последовательностей разной длины как числовых, так и лингвистических.
3. Теоремы, определяющие свойства показателей контентной эквивалентности.
4. Показатели пертинентности откликов поисковых систем на запросы пользователей.
5. Методика экспертной оценки пертинентности на основе показателей контентной эквивалентности.
6. Теорема, определяющая диапазон возможных значений показателя авторитетности страниц произвольного фрагмента сети Интернет.
7. Теорема, определяющая зависимость показателя авторитетности страниц произвольного фрагмента сети Интернет от авторитетности страниц, не вошедших в рассматриваемый фрагмент.
8. Методика вычисления PageRank страниц для произвольного фрагмента сети.
9. Методика исследования зависимости авторитетности страниц произвольного фрагмента сети от внешнего потока PageRank.
10. Дополнительный показатель авторитетности страницы как фактор ранжирования в поисковых системах – SolidPageRank.
11. Концепция интерфейсной поисковой системы многоальтернативного поиска и адаптивного переранжирования.
12. Рекурсивный алгоритм определения структуры произвольного фрагмента сети Интернет.

Апробация работы. По теме диссертации сделаны доклады на 15-й Международной научно-технической конференции «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций», Рязань, 2008 г.; XII Всероссийской научно-технической конференции студентов, молодых учёных и специалистов «Новые информационные технологии в научных исследованиях и в образовании», Рязань, 2007 г.; XIII Всероссийской научно-технической конференции студентов, молодых учёных и специалистов «Новые информационные технологии в научных исследованиях и в образовании», Рязань, 2008 г.; XIV Всероссийской научно-технической конференции студентов, молодых учёных и специалистов «Новые информационные технологии в научных исследованиях и в образовании», Рязань, 2009 г.; 4-й межвузовской научно-технической студенческой конференции «Актуальные проблемы персональных компьютеров и сетей», Москва, 2006 г.; Международной конференции «Инновационное управление в информационной среде», Рязань, 2007 г.; Третьей международной конференции «Инновационное управление в информационной среде», Рязань, 2008 г.;., а также на научных семинарах кафедры ВПМ РГРТУ.

Публикации. По теме диссертации опубликовано 20 научных работ, в том числе 11 материалов и тезисов докладов на международных и всероссийских конференциях и семинарах. Опубликовано 5 статей, из них 2 в издании, включённом в список ВАК. В Реестре программ для ЭВМ зарегистрированы 2 программы.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, основных обозначений и сокращений, списка использованной литературы и приложений. Основной текст содержит 146 страниц, 5 таблиц, 38 рисунка. Список литературы состоит из 117 наименований. Приложения выполнены на 5 страницах.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

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

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

,

где , , – аппроксимирующие коэффициенты, для каждой ПС свои; – монотонно неубывающая функция, и .

Определены новые показатели пертинентности откликов поисковых систем на запросы пользователей, предназначенные для реализации процедур адаптации алгоритмов формирования итоговой выдачи: 1) пертинентностная точность выдачи ; 2) подлинная пертинентность документа ; 3) максимальная пертинентность документов выдачи ; 4) кумулятивная пертинентность выдачи ; 5) векторная пертинентность выдачи ; 6) средние значения указанных показателей, вычисляемые по 32-м точечным значениям: , , , , .

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

Степень емкостной контентной эквивалентности

Степень относительной контентной эквивалентности

Степень абсолютной контентной эквивалентности

Степень эквивалентности по обобщенной ранговой корреляции

Степень эквивалентности по условной ранговой корреляции

Степень эквивалентности по плотности общих элементов

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

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

Теорема 6. Пусть задан произвольный фрагмент сети Интернет следующими признаками: 1) матрицей смежности страниц сайтов ; 2) значением коэффициента затухания . Тогда:

1. сумма PageRank всех страниц рассматриваемого фрагмента равна , если каждая страница имеет хотя бы одну ссылку на другие страницы, или формально:

.

2. сумма PageRank всех страниц рассматриваемого фрагмента меньше , если фрагмент содержит хотя бы одну страницу, не имеющую ссылок на другие страницы, или формально:

;