Содержание к диссертации
ВВЕДЕНИЕ 5
1. Обзор методов решения задачи периодического тематического поиска 12
Особенности задачи информационного поиска в Web 12
Показатели качества поиска 14
Требования к системам периодического тематического поиска и критерии их эффективности 16
1.4 Существующие решения задачи периодического поиска в Web. 18
1.4.1 Периодический поиск с использованием систем поиска по
ключевым словам ; 20
Периодический поиск с использованием мета-информационнных поисковых систем 24
Периодический поиск новой информации на подмножестве источников информации Web 25
1.4.4ХІОИСК обновлений в тематических каталогах 26
1.5 Основные подходы к решению задачи тематической фильтрации
27
Сравнение метода поиска по ключевым словам с методами поиска, основанными на использовании методов машинного обучения 29
Оценка необходимого объема вычислений для обработки новой информации Web 32
Варианты практического использования методов машинного . обучения для решения задачи периодического тематического поиска... 32
1.6 Выводы 35
2. Метод периодического тематического поиска, основанный на
использовании классификаторов 38
Постановка задачи 38
Описание предложенного метода 39
2.2.1 Схема работы метода 43
Алгоритм составления запроса по ключевым словам на основе обучающей выборки 45
Обоснование предложенного метода 46
2.5 Выводы 50
3. Методы решения задачи классификации текстов 51
Требования к алгоритмам классификации 51
Метрики качества классификации 53
Основные этапы классификации текстов 54
Основные подходы к представлению текстов 55
Использование морфологического анализа 57
Использование синтаксического анализа 57
Определение пространства признаков 58
Методы выбора признаков 59
Кластеризация признаков 60
Отбор фраз 61
Определение весов признаков 62
Оценка алгоритмов классификации на коллекциях документов. 63
Критерии сравнения алгоритма классификации 64
Обзор алгоритмов классификации 67
Метод Байеса 67
Алгоритм Rocchio 68
Вероятностный классификатор TFIDF 70
Метод k-ближайших соседей 70
Метод опорных векторов 71
Нейронные сети 72
Деревья решений 73
Алгоритмы построения булевских формул 75
Сравнительный анализ алгоритмов классификации 77
Описание масштабируемых алгоритмов классификации текстов79 3.9.1 Модификация метода Байеса 79
3.9.2 Метод построения нескольких разделяющих гиперплоскостей
81
Сопоставление весов признакам для метода опорных векторов83
Экспериментальное исследование алгоритмов классификации и способов представления документов 83
Методология проведения экспериментов 83
Описание тестовых коллекций 84
Результаты экспериментов 84
Выводы 89
4. Практическая реализация предложенного подхода 90
Архитектура реализации 90
Способы получения анализируемого множества документов из Web 92
Практическая апробация предложенного подхода 96
4.4 Выводы 101
Заключение 103
Список литературы 105
Введение к работе
Развитие сетевых технологий, в том числе и сети Интернет, привело к значительному увеличению доступных информационных ресурсов и объемов передаваемой информации. Зачастую это разнородная, слабо структурированная и избыточная информация, обладающая высокой динамикой обновления. Необходимость эффективного использования этого колоссального и динамично изменяющегося объема информации обуславливает актуальность и значимость исследований в области информационного поиска.
В области информационного поиска отдельно выделяется задача тематического поиска, то есть целенаправленного поиска документов, относящихся с той или иной степенью релевантности к определенной теме, заявленной пользователем. При проведении исследований, обучении и профессиональной деятельности, в связи с высокой скоростью появления новой информации возникает потребность не только в нахождении сведений, соответствующих одной или нескольким темам, но и в постоянном получении новых данных. Одним из возможных вариантов удовлетворения этой потребности является периодическое обновление ранее полученных сведений, по аналогии с подпиской на тематические издания, такие как специализированные газеты и журналы. Для обеспечения такого рода доставки информации из Web необходимо решить задачу периодического тематического поиска, то есть такого поиска, при котором обновления ищутся не только на уже известных сайтах, но и ищутся новые сайты. Причем такой поиск ведется систематически, через определенные промежутки времени. Появление такого вида поиска также связано с особенностями Web, как информационного хранилища. Дело в том, что доступная информация динамически изменяется - появляются новые документы на уже известных Web-сайтах, а также появляются новые Web-сайты. Так, согласно [29], число Web-сайтов растет экспоненциально и за
полгода, на момент опубликования статьи, прирост количества сайтов составил порядка 20 тысяч.
Отдельно следует рассмотреть вопрос востребованности сервиса периодического тематического поиска. Огромный объем информации, доступной в Web, и высокая скорость ее обновления обуславливают необходимость в средствах автоматизации периодического тематического поиска для этого источника информации. Согласно опросу [95], проведенному в сентябре 2005 года в США исследовательским центром изучения социального влияния Интернет, все большее количество пользователей используются поисковые системы практически каждый день (63%). Также растет доля пользователей, использующих Интернет для поиска информации, связанной с профессиональной деятельностью. На момент проведения опроса число таких пользователей составляло более четверти от общего количества пользователей Интернет (28%). Можно говорить о потребности в тематическом поиске информации для таких пользователей (практически любая должность предполагает знание и использование информации из узкого набора тем, который слабо изменяется в процессе выполнения должностных обязанностей). Также следует отметить, что согласно опросу [95] респонденты занимаются таким поиском практически каждый день. Таким образом, можно сделать вывод, что более четверти пользователей Интернет занимаются, по сути, тематическим поиском, причем делают это бессистемно и тратят на процесс поиска достаточно большие ресурсы: личное время и ресурсы поисковых машин. Использование систем периодического тематического поиска позволяет автоматизировать и систематизировать процесс поиска информации для этой категории пользователей.
Необходимость постоянного получения новой информации релевантной заявленной теме при обучении, профессиональной деятельности, проведении научных исследований и в других областях деятельности
обуславливает практическую значимость решения задачи периодического тематического поиска документов в Web.
С точки зрения пользователя процесс поиска будет выглядеть следующим образом:
Подписка на
интересующую
тему
Пользователь
Релевантные
теме документы
Механизм
периодического
тематического
поиска
рис. 1.1. Процесс поиска с использованием систем периодического тематического поиска в Web Следует отметить, что сервис периодической доставки релевантных документов имеет практический смысл только в том случае, если тематическая потребность остается актуальной и неизменной в течение большого промежутка времени. В этих условиях можно сформулировать следующие особенности задачи периодического поиска в Web:
Высокая динамичность и объем пространства поиска (согласно
оценкам ежемесячно изменяется до 40% [63] общего объема доступной информации, составляющего более чем 11 млрд. web-страниц [53])
Информационная потребность пользователя слабо изменяется со
временем и остается актуальной в течение большого промежутка времени (носит долговременный характер).
Результаты поиска необходимо предоставить пользователю в течение ограниченного, вполне определенного интервала времени.
В области поиска информации исторически выделяются два сильно связанных типа задач [30,31,82]: информационного поиска (information retrieval) и фильтрации информации (information filtering). Системы информационного поиска применяются в условиях высокой изменяемости информационной потребности пользователей и относительной статичности используемого хранилища информации. Системы фильтрации информации напротив, предназначены для получения релевантных документов из высоко динамичных источников информации, но при этом делается допущение о том, что интересы пользователей слабо изменяются со временем. Условие долговременности информационной потребности позволяет отнести задачу периодического тематического поиска к классу задач тематической фильтрации информации.
Традиционно задача фильтрации информации рассматривается как задача выбора релевантных данных из постоянно изменяющихся потоков документов [85,89], таких как новостные сообщения [33,70,104,113], почтовые сообщения [42,67,97]. Отличие задачи фильтрации на всем Web от традиционной задачи фильтрации состоит в том, что протокол передачи данных в Web HTTP [80] реализует модель "запрос-ответ" и не позволяет оповещать об изменениях в данных. Это приводит к тому, что обнаружить все изменения в Web можно только проанализировав всю доступную информацию, объем которой очень велик. Образно говоря, задача фильтрации в Web отличается от традиционной примерно так же, как работа коммивояжера отличается от работы продавца в магазине.
В традиционных методах фильтрации для описания информационной потребности используются как наборы ключевых слов [33,113], так и обучающие коллекции документов [42,67,97]. Существуют методы информационной фильтрации и для всего Web [36,86], но в них для описания
информационной потребности используются только наборы ключевых слов. Методы, основанные на использовании запроса по ключевым словам, будем в дальнейшем называть методами поиска по ключевым словам.
К недостаткам метода поиска по ключевым словам относят слабую выразительность языка запросов и высокую сложность составления оптимального запроса, что приводит к низкому качеству тематического поиска в Web. С другой стороны существует множество успешно применяемых методов определения тематической принадлежности документов, в том числе и с использованием алгоритмов классификации (или методов машинного обучения [1]), использующих обучающие коллекции документов. Однако высокая вычислительная сложность задач обучения и классификации ограничивает практическую применимость таких методов для Web.
В этих условиях разработка метода периодического тематического поиска в Web в условиях долговременности информационной потребности пользователя и динамичности пространства поиска, повышающего качество поиска по сравнению с традиционными методами, представляется актуальной.
Основным вкладом данной работы, определяющим ее научную новизну, является создание метода периодического тематического поиска, успешно сочетающего методы поиска по ключевым словам, обеспечивающие высокую полноту охвата информационных источников в Web, и методы тематической фильтрации, основанные на машинном обучении, позволяющие достичь более высокого качества поиска по сравнению с другими известными методами. Повышение качества поиска в рамках автоматизированного процесса нахождения новой тематически-ориентированной информации по сравнению с существующими методами обуславливает практическую ценность предложенного метода.
Основные результаты, полученные автором в ходе исследования и вынесенные на защиту, заключаются в следующем:
1. Предложен новый метод периодического тематического поиска
информации в Web, созданный на основе композиции метода поиска по
ключевым словам и метода тематической фильтрации с помощью
классификаторов текстов. Данный метод учитывает долговременный
характер информационной потребности и динамичность пространства поиска
и позволяет повысить релевантность результатов поиска.
2. Разработаны оригинальные масштабируемые алгоритмы
классификации, обладающие меньшей вычислительной сложностью
обучения и сопоставимым качеством классификации по сравнению с одним
из лучших известных алгоритмов - методом опорных векторов:
алгоритм на основе построения нескольких разделяющих гиперплоскостей для решения задачи бинарной классификации
модифицированный алгоритм Байеса для случая большого количества классов в обучающей выборке
Сформулированы условия эффективного совместного применения алгоритмов классификации и способов предварительного анализа текста при построении систем периодического тематического поиска.
Реализован прототип системы периодического тематического поиска в Web и получены экспериментальные оценки полноты и точности предложенного метода, показывающие его преимущество перед существующими методами.
Содержание диссертации организовано следующим образом:
В главе 1 дается обзор методов информационного поиска в Web и тематического поиска с точки зрения их применения для решения задачи периодического тематического поиска. Описываются базовые технологии, достоинства и недостатки методов, общепринятые методы оценки релевантности результатов поиска.
В главе 2 описана схема работы нового метода периодического тематического поиска, основанного на комбинации традиционного
метода поиска по ключевым словам и тематической фильтрации документов с помощью методов машинного обучения. Приводится обоснование эффективности предложенного метода по сравнению с традиционным методом поиска по ключевым словам при выполнении определенных условий. Обсуждается выполнимость этих условий на практике. Описываются требования к алгоритмам классификации в рамках предложенного метода.
