автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Повышение релевантности периодического тематического поиска информации в Web

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

имени М.В. Ломоносова Факультет Вычислительной Математики и Кибернетики

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

Щ

Максаков Алексей Владимирович

ПОВЫШЕНИЕ РЕЛЕВАНТНОСТИ ПЕРИОДИЧЕСКОГО ТЕМАТИЧЕСКОГО ПОИСКА ИНФОРМАЦИИ В XVЕВ

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

ооа15втзэ

МОСКВА 2007

003158739

Работа выполнена на кафедре автоматизации систем вычислительных комплексов факультета вычислительной математики и кибернетики МГУ им М.В. Ломоносова

Научный руководитель:

доктор физико-математических наук, профессор

Руслан Леонидович Сме ля некий

Официальные оппоненты:

доктор физико-математических наук, заведующий сектором Института прикладной математики РАН Михаил Михайлович Горбунов-Посадов

кандидат физико-математических наук,

старший научный сотрудник ВЦ РАН Виктор Иванович Филиппов

Ведущая ор1'анизация; Институт системного

программирования Российской академии наук

Защита диссертации состоится 26 октября 2007 г. в 11:00 на заседании диссертационного совета Д 501.001.44 при Московском государственном университете им. М.В, Ломоносова по адресу: 119992, ГСП-2, Москва, Воробьевы горы, МГУ, 2-ой учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ. С текстом автореферата можно ознакомиться на официальном сайте ВМиК МГУ им. М.В. Ломоносова http://www.cmc.msu.ru в разделе «Наука» -«Работа диссертационных советов» - «Д 501.001.44»

Автореферат разослан «У» сентября 2007 года.

Ученый секретарь I диссертационного совета профессор

Л. Трифонов

Общая характеристика работы

Актуальность темы

Развитие сетевых технологий, в том числе и сети Интернет, привело к значительному увеличению числа доступных информационных ресурсов и объемов передаваемой информации Зачастую это разнородная и слабо структурированная информация, обладающая высокой динамикой обновления Необходимость эффективного использования этого колоссального и динамично изменяющегося объема информации обуславливает актуальность и значимость исследований в области информационного поиска Согласно опросу пользователей Интернет1 более 63% от общего числа пользователей используют системы поиска в World Wide Web практически каждый день

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

1 Ramie L Search Engine use November 2005

http //www pewmternet org/pdfs/PIP_SearchData_1105 pdf

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

• Высокая динамичность и объем пространства поиска (согласно оценкам ежемесячно изменяется до 40%2 общего объема доступной информации, составляющего более чем 11 млрд web-страниц)

• Информационная потребность пользователя слабо изменяется со временем и остается актуальной в течение большого промежутка времени (носит долговременный характер)

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

Высокая динамичность пространства поиска и слабая изменчивость информационной потребности позволяют отнести задачу периодического тематического поиска к классу задач фильтрации информации3 В традиционных методах фильтрации для описания информационной потребности используются как наборы ключевых слов, так и обучающие коллекции документов Отличие задачи фильтрации на всем Web от традиционной задачи фильтрации состоит в том, что протокол передачи данных в Web HTTP4 реализует модель "запрос-ответ" и не позволяет оповещать об изменениях в данных Это приводит к тому, что обнаружить все изменения в Web, можно только проанализировав всю доступную информацию, объем которой очень велик В связи с этим в существующих методах фильтрации информации на всем Web для описания

2 Kahle В Preserving the Internet// Scientific American March 1997 p 82-83

3 Belkin N, Croft W Information filtering and information retrieval two sides of the same coin9//Communications of the ACM, Volume 35 , Issue 12 New York ACM Press, 1992 p 29-38

4 Liu L Query routing m large-scale digital library systems// In proc of the 15th conference on Data Engineering IEEE press, 1999 p 154-163

4

информационной потребности используются только наборы ключевых слов К недостаткам методов поиска, использующих запросы по ключевым словам для представления информационной потребности, относят слабую выразительность языка запросов и высокую трудоемкость составления оптимального запроса5, что приводит к низкому качеству тематического поиска в Web С другой стороны, существует множество успешно применяемых методов определения тематической принадлежности документов, в том числе и с использованием алгоритмов классификации (или методов машинного обучения6}, использующих обучающие коллекции документов Однако высокая вычислительная сложность задач обучения и классификации ограничивает практическую применимость таких методов для Web

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

Цель работы

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

В рамках данной работы исследуются решения следующих задач

1 Разработка метода периодического тематического поиска, обладающего свойствами методов поиска по ключевым словам в части полноты охвата информационных источников в Web и свойствами методов тематической фильтрации, основанных на

5 Kobayashi M, Takeda К Information retrieval on the Web// ACM Computing Surveys, vol 32, 2 New York ACM Press, 2000 p 144-173

6 Агеев M С Методы автоматической рубрикации текстов, основанные на машинном: обучении и знаниях экспертов Дис калд физ-мат наук 05 13 11 Московский гос унив -Москва, 2005

машинном обучении, в части высокой точности результатов поиска.

2 Исследование существующих методов машинного обучения с целью повышения их эффективности для использования в создаваемом методе периодического тематического поиска

3. Анализ эффективности предложенного метода в сравнении с существующими методами периодического тематического поиска информации в Web

Научная новизна

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

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

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

Практическая ценность

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

Результаты данной работы могут быть использованы в следующих областях

1 Для организации поиска новой информации в системах непрерывного обучения

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

Методы исследования

При разработке метода периодического тематического поиска в Web использовались методы статистического и лингвистического анализа текстов на естественном языке, методы математической статистики, методы экспериментальной проверки

Апробация работы и публикации

По теме диссертационного исследования опубликовано 7 печатных работ, в том числе одна - в издании из списка рекомендованных ВАК Результаты работы докладывались на объединенном научно-исследовательском семинаре кафедр Автоматизации систем вычислительных комплексов, Алгоритмических языков и Системного программирования факультета ВМиК МГУ, на научных семинарах лаборатории Вычислительных комплексов кафедры Автоматизации систем вычислительных комплексов факультета ВМиК МГУ, Российском семинаре по Оценке Методов Информационного поиска (РОМИП), а также на следующих конференциях.

• Международная научная конференция "Интеллектуализация обработки информации" (Алушта, 2002),

• Всероссийская научная конференция "Математические методы распознавания образов" (Звенигород, 2005),

• Всероссийская научная конференция "Электронные библиотеки, перспективные методы и технологии, электронные коллекции" (Суздаль, 2006)

Структура и объем диссертации

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

Краткое содержание диссертации

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

В первой главе приведен обзор методов информационного поиска в Web и тематической фильтрации с точки зрения эффективности их применения для решения задачи периодического тематического поиска

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

Далее, в разделе 1.2, приведены традиционные показатели качества поиска и общепринятая методология оценки качества поиска, применяемая в рамках конференции Text Retrieval Evaluation Conférence (TREC) и Российского семинара по Оценке Методов Информационного Поиска (РОМИП)

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

реализации метода (трудоемкость описания информационной потребности, универсальность и практическая применимость)

Раздел 1.4 посвящен анализу существующих решений в области периодического поиска с точки зрения их соответствия указным ранее критериям

Существующие решения в области периодического поиска можно разделить на 4 класса периодический поиск с использованием систем поиска по ключевым словам (СПКС), периодический поиск с использованием мета-информационнных поисковых систем, периодический поиск новой информации на подмножестве источников информации Web и поиск обновлений в тематических каталогах Показана низкая эффективность применения СПКС для решения задачи периодического тематического поиска Показано, что для СПКС также характерна высокая степень несоответствия между данными, хранящимися в поисковом индексе и реальным состоянием Web Частично эту проблему несоответствия можно решить путем использования при периодическом поиске мета-информационных поисковых систем Полнота периодического поиска новой информации на подмножестве источников информации Web оценивается как низкая7, и падает со временем, поскольку не предусмотрена возможность обнаружения новых источников в Web Тематические каталоги строятся вручную, что приводит к очень низкой полноте периодического поиска Также ограничение набора тем в каталогах приводит к нарушению требования универсальности поиска

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

7 Bun К , Ishizuka М Emerging Topic Tracking System// Proceedings of Web Intelligence

Conference London Springer-Verlag, 2001 p 125-130

9

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

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

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

В предложенном методе поиска информационная потребность представляется в виде пары

{q, D}, где q - запрос по ключевым словам, использующийся для первичного отбора документов из Web

D = {D+, D-} - обучающая выборка, описывающая тему, интересующую пользователя Данная обучающая выборка содержит примеры релевантных теме документов (£>+) и нерелевантных документов (D-)

Процесс поиска разделяется на два этапа

1 Отбор документов из Web, соответствующих запросу по ключевым словам q с помощью глобальных систем поиска по ключевым словам, таких как Google, Яндекс и т п Данный этап позволяет с одной стороны обеспечить высокую полноту

поиска, а с другой - существенно сократить объем обрабатываемой на следующем этапе информации 2 Уточнение результатов поиска с помощью классификатора, обученного на предоставленной пользователем обучающей выборке D Этот этап позволяет обеспечить высокую точность результатов поиска Ряд исследований8'9 показали, что применение тематической классификации результатов поиска позволяет существенно сократить время поиска нужной информации Разбиение линейного списка результатов поиска на тематически связанные подгруппы позволяет быстрее ориентироваться в полученных результатах и, как следствие, повысить удобство использования поисковой системы

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

D={Di+, D2+, D}+, , Z>n+, £>-}, где Д+ - обучающая выборка z-ой подтемы, п - общее количество подтем

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

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

8 Chen Н, Dumais S Bringing Order to the Web Automatically Categorizing Search // Proceedings of ACM SIGCHI Conference on Human Factors m Computing Systems, Vol 1 New York ACM Press, 2000 p 145-152

® Diao Y , Lu H, Wu D A comparative study of classification-based personal E-Mail filtering// In proceedings of 4th Pacific-Asia Conference on Knowledge Discovery and Data Mimng Kyoto Springer Verlag, 2000 p 408-419

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

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

Поскольку на этапе отбора документов из Web используется тот же метод поиска по ключевым словам, то доля упугценной в процессе поиска информации будет не больше, чем при прямом применении этого метода Таким образом, можно утверждать, что предложенный метод (обозначим егоМетф) не будет уступать методу поиска по ключевым словам Мкс, при условии, что он не будет уступать ему по качеству поиска на статической коллекции документов Для сравнения качества поиска на статической коллекции необходимо сравнить оценки полноты и точности этих методов Согласно разделу 2.2 процесс поиска состоит из двух этапов

1 отбор соответствующих запросу q' документов из Web с помощью метода поиска по ключевым словам М„(д'),

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

Выразим показатели полноты и точности предложенного метода через показатели полноты и точности отбора документа из Web с помощью поиска по ключевым словам MKC(q') и метода тематической фильтрации Мтф Обозначим общее количество релевантных документов как Np, количество отобранных на первом этапе — N0, количество релевантных из отобранных -

Npo и количество релевантных документов из итогового списка найденных -NPH-.

ПМ1и5р)^=Р(Мтф)

О

Р Р ро

Таким образом, точность предложенного метода равна точности тематической фильтрации Мтф, используемой на втором этапе поиска Полнота же определяется произведением полноты отбора документов Web по ключевым словам д' на полноту тематической фильтрации Покажем, что при выполнении определенных условий предложенный метод будет превосходить по качеству поиска, выраженному мерой F1, метод поиска по ключевым словам

Запрос по ключевым словам, результаты поиска по которому обладают наилучшим среди данного множества запросов Q показателем меры F1, будем называть F1 -оптимальным запросом на этом множестве.

q = aigmaxFl(g)

qeO

Полноту поиска с помощью Fl-оптимального запроса обозначим R(q), точность - Р(д)

Предположим, что на практике верны следующие утверждения1

1. Применяемый классификатор превосходит по полноте F1-оптимальный запрос на множестве запросов Q, которые может предложить пользователь, т.е За >1- ЩМтф)>а R(q) (1),

2. F1 -оптимальный запрос обладает полнотой меньше единицы R(q)<l (2)

Введем дополнительное условие-

3 Возможно подобрать запрос по ключевым словам q', уменьшающий ошибку, связанную с полнотой в произвольное количество раз

3q' R{q<) > R(q) (3)

Лемма Предположим, что утверждения (1), (2) верны, а также выполняется условие (3), причем R(q')>R(q) + b (1-*(<?))

Тогда V« > 1 ЭЪ<\ R(Mni6p) = R(q') ЩМтф)>R(q) Доказательство

Получим оценку значений параметра Ъ, при которых выполняется

условие R{MeilSp) — R(q') R(M^)>R(g)

a R(q) (R(q) + b (1 -*(<?))>*(<?),

R(q) + b (l-R(q))>l/a,

1 /a-R(g) 1 -R(g)

Поскольку a > 1, TO < j

1 ~R(q)

Обозначим Я = .

1 -R(q)

Таким образом, требуемое условие выполняется при Ь е [ЯД) Т к данное множество непустое, то при выполнении условия (3).

Va >1 в&<1 R(Mабр) = R(q') R(Mm<p)>R(q)- что и требовалось

доказать

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

• Путем включения множества ad-hoc запросов, предложенных пользователями для описания заданной темы

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

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

правил и по точности классификации Результаты апробации, приведенные в разделе 4 3, подтверждают, что качество поиска по F-мере с помощью предложенного метода выше качества поиска с помощью F-оптимального запроса на множестве запросов, предложенных пользователями. Таким образом, если используемый классификатор превосходит по точности F1-оптимальный запрос, то качество результатов гибридного подхода, выраженное мерой F1 в среднем будет выше, чем качество поиска по ключевым словам, при условии подбора для отбора документов из Web запроса по ключевым словам, обладающего достаточно высокой полнотой Теоретически возможно составление запроса, обладающего полнотой, равной единице, путем включения в него всех слов, которые могут встречаться в текстах, относящихся к заданной теме (таким образом, условие (3) выполнимо)

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

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

В разделах 3.1 - 3.3 приводятся общие требования к алгоритмам классификации в рамках рассматриваемой задачи, метрики качества классификации, основные этапы классификации текстов

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

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

В разделах 3-5-3.6 приведено описание методики оценки алгоритмов классификации, введены критерии сравнения эффективности алгоритмов классификации в рамках решения задачи периодического тематического поиска

В разделах 3.7-3.8 приводится обзор широко известных алгоритмов классификации и их сравнительный анализ На основе ряда независимых публикаций1011 делается вывод о преимуществе по качеству классификации алгоритма БУМ (метода опорных векторов) над другими известными алгоритмами Однако к недостаткам этого алгоритма следует отнести высокую вычислительную сложность обучения (0(1Vя), где а >1,712) Исходя из наличия требований к низкой вычислительной сложности обучения, требуется разработка алгоритмов, которые бы обладали меньшей вычислительной сложностью обучения при качестве классификации, близком к качеству алгоритма БУМ

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

10 Sebastiam F, Machine Learning in Automated Text Categorization// ACM Computing Surveys, vol 1,2002 p 1-47

1 ! Yang Y, Liu X A re-examination of text categorization methods// Proc of International ACM Conf on Research and Development m Information Retrieval (SIGIR-99) New York ACM Press, 1999 p 42-49

12 Chakrabarti S Mining The Web Discovering Knowledge From Hypertext Data Sail Francisco Morgan Kaufmann Publishers, 2004

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

В разделе ЗЛО рассмотрен предложенный автором способ оценки весов признаков, основанный на описанном в разделе 3.4 новом способе оценки значимости признака

Экспериментальные исследования, проведенные на четырех широко применяемых тестовых коллекциях документов, показали следующее-

• При решении задачи бинарной классификации качество результатов предложенного алгоритма построения нескольких разделяющих гиперплоскостей (МоёР^Ьег) сопоставимо с качеством алгоритма БУМ.

• Модифицированный метод Байеса при решении задачи бинарной классификации существенно проигрывает по качеству и алгоритму БУМ и алгоритму МосЦ^Ьег

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

• На всех тестовых коллекциях метод опорных векторов с применением предложенного в работе способа оценки весов признаков превосходит по качеству классификации все рассмотренные алгоритмы

• Использование фраз в качестве признаков позволяется повысить качество классификации на 1-2% для всех рассмотренных алгоритмов,

за исключением алгоритма SVM, для которого улучшение было незначительно и составило 0,4% • Сокращение пространства признаков с использованием критерия хи-квадрат или критерия соотношения порядков позволяет сократить размерность пространства в 5-10 раз без существенной потери качества классификации

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

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

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

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

Основные результаты работы

1 Предложен новый метод периодического тематического поиска информации в Web, созданный на основе композиции 18

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

■ алгоритм на основе построения нескольких разделяющих гиперплоскостей для решения задачи бинарной классификации

■ модифицированный алгоритм Байеса для случая большого количества классов в обучающей выборке

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

Представленные результаты получены автором самостоятельно и V изложены в следующих работах

1 Максаков A.B. Исследование способов уменьшения набора характеристик в алгоритмах классификации текстов// Труды Всероссийской научной конференции "Методы и средства

обработки информации" М Издательский отдел факультета ВМиК МГУ, 2003, стр 234-240

2. Максаков А В Масштабируемые алгоритмы классификации текстов// Труды 12-й конференции "Математические методы распознавания образов" (ММРО-12), Москва, 2005

3 Максаков А.В Об одном методе периодического тематического поиска информации в Web// Труды восьмой всероссийской научной конференции "Электронные библиотеки перспективные методы и технологии, электронные коллекции" М МАКС Пресс, 2006, стр 101-107

4. Максаков А В Об одном методе повышения качества периодического тематического поиска в Web// Вестн Моек ун-та Сер 15 Вычислительная математика и кибернетика, 2007 № 2, стр 35-44

5 Максаков А.В Оценка эффективности масштабируемых алгоритмов классификации текстов// Труды четвертого российского семинара по оценке методов информационного поиска Санкт-Петербург- НУ ЦСИ, 200, стр 92-100

6 Максаков А В Обеспечение контекстного поиска информации для баз знаний// Искусственный интеллект (Донецк), 2002 № 2, стр 493500

7 Максаков А В. Сравнительный анализ алгоритмов классификации и способов представления Web-документов// Труды третьего Российского семинара по Оценке Методов Информационного Поиска (РОМИП 2005) Санкт-Петербург НИИ Химии СПбГУ, 2005, стр 63-73.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01 12 99 г Подписано к печати 25 09 2007 г Формат 60x90 1/16 Услпечл 1,25 Тираж 100 экз Заказ 467 Тел 939-3890 Тел/Факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им МВ Ломоносова, 2-й учебный корпус, 627 к

ВВЕДЕНИЕ.

1. Обзор методов решения задачи периодического тематического поиска

1.1 Особенности задачи информационного поиска в Web.

1.2 Показатели качества поиска.

1.3 Требования к системам периодического тематического поиска и критерии их эффективности.

1.4 Существующие решения задачи периодического поиска в Web. 18 1.4.1 Периодический поиск с использованием систем поиска по ключевым словам.;.

1.4.2. Периодический поиск с использованием мета-информационнных поисковых систем.

1.4.3. Периодический поиск новой информации на подмножестве источников информации Web.

1.4.4.Поиск обновлений в тематических каталогах.

1.5 Основные подходы к решению задачи тематической фильтрации

1.5.1 Сравнение метода поиска по ключевым словам с методами поиска, основанными на использовании методов машинного обучения

1.5.2 Оценка необходимого объема вычислений для обработки новой информации Web.

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

1.6 Выводы.

2. Метод периодического тематического поиска, основанный на использовании классификаторов.

2.1 Постановка задачи.

2.2 Описание предложенного метода.

2.2.1 Схема работы метода.

2.3 Алгоритм составления запроса по ключевым словам на основе обучающей выборки.

2.4 Обоснование предложенного метода.

2.5 Выводы.

3. Методы решения задачи классификации текстов.

3.1 Требования к алгоритмам классификации.

3.2 Метрики качества классификации.

3.3 Основные этапы классификации текстов.

3.4 Основные подходы к представлению текстов.

3.4.1 Использование морфологического анализа.

3.4.2 Использование синтаксического анализа.

3.4.3 Определение пространства признаков.

3.4.4 Методы выбора признаков.

3.4.5 Кластеризация признаков.

3.4.6 Отбор фраз.

3.4.7 Определение весов признаков.

3.5 Оценка алгоритмов классификации на коллекциях документов.

3.6 Критерии сравнения алгоритма классификации.

3.7 Обзор алгоритмов классификации.

3.7.1 Метод Байеса.

3.7.2 Алгоритм ЯоссЫо.

3.7.3 Вероятностный классификатор ТБГОР.

3.7.4 Метод к-ближайших соседей.

3.7.5 Метод опорных векторов.

3.7.6 Нейронные сети.

3.7.7 Деревья решений.

3.7.8 Алгоритмы построения булевских формул.

3.8 Сравнительный анализ алгоритмов классификации.

3.9 Описание масштабируемых алгоритмов классификации текстов79 3.9.1 Модификация метода Байеса.

3.9.2 Метод построения нескольких разделяющих гиперплоскостей

3.10 Сопоставление весов признакам для метода опорных векторов

3.11 Экспериментальное исследование алгоритмов классификации и способов представления документов.

3.11.1 Методология проведения экспериментов.

3.11.2 Описание тестовых коллекций.

3.11.3 Результаты экспериментов.

3.11.4 Выводы.

4. Практическая реализация предложенного подхода.

4.1 Архитектура реализации.

4.2 Способы получения анализируемого множества документов из Web

4.3 Практическая апробация предложенного подхода.

4.4 Выводы.

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

В области информационного поиска отдельно выделяется задача тематического поиска, то есть целенаправленного поиска документов, относящихся с той или иной степенью релевантности к определенной теме, заявленной пользователем. При проведении исследований, обучении и профессиональной деятельности, в связи с высокой скоростью появления новой информации возникает потребность не только в нахождении сведений, соответствующих одной или нескольким темам, но и в постоянном получении новых данных. Одним из возможных вариантов удовлетворения этой потребности является периодическое обновление ранее полученных сведений, по аналогии с подпиской на тематические издания, такие как специализированные газеты и журналы. Для обеспечения такого рода доставки информации из Web необходимо решить задачу периодического тематического поиска, то есть такого поиска, при котором обновления ищутся не только на уже известных сайтах, но и ищутся новые сайты. Причем такой поиск ведется систематически, через определенные промежутки времени. Появление такого вида поиска также связано с особенностями Web, как информационного хранилища. Дело в том, что доступная информация динамически изменяется - появляются новые документы на уже известных Web-сайтах, а также появляются новые Web-сайты. Так, согласно [29], число Web-сайтов растет экспоненциально и за полгода, на момент опубликования статьи, прирост количества сайтов составил порядка 20 тысяч.

Отдельно следует рассмотреть вопрос востребованности сервиса периодического тематического поиска. Огромный объем информации, доступной в Web, и высокая скорость ее обновления обуславливают необходимость в средствах автоматизации периодического тематического поиска для этого источника информации. Согласно опросу [95], проведенному в сентябре 2005 года в США исследовательским центром изучения социального влияния Интернет, все большее количество пользователей используются поисковые системы практически каждый день (63%). Также растет доля пользователей, использующих Интернет для поиска информации, связанной с профессиональной деятельностью. На момент проведения опроса число таких пользователей составляло более четверти от общего количества пользователей Интернет (28%). Можно говорить о потребности в тематическом поиске информации для таких пользователей (практически любая должность предполагает знание и использование информации из узкого набора тем, который слабо изменяется в процессе выполнения должностных обязанностей). Также следует отметить, что согласно опросу [95] респонденты занимаются таким поиском практически каждый день. Таким образом, можно сделать вывод, что более четверти пользователей Интернет занимаются, по сути, тематическим поиском, причем делают это бессистемно и тратят на процесс поиска достаточно большие ресурсы: личное время и ресурсы поисковых машин. Использование систем периодического тематического поиска позволяет автоматизировать и систематизировать процесс поиска информации для этой категории пользователей.

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

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

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

• Высокая динамичность и объем пространства поиска (согласно оценкам ежемесячно изменяется до 40% [63] общего объема доступной информации, составляющего более чем 11 млрд. web-страниц [53])

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

Механизм периодического тематического поиска рис. 1.1. Процесс поиска с использованием систем периодического тематического поиска в Web

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

В области поиска информации исторически выделяются два сильно связанных типа задач [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], но в них для описания 8 информационной потребности используются только наборы ключевых слов. Методы, основанные на использовании запроса по ключевым словам, будем в дальнейшем называть методами поиска по ключевым словам.

К недостаткам метода поиска по ключевым словам относят слабую выразительность языка запросов и высокую сложность составления оптимального запроса, что приводит к низкому качеству тематического поиска в Web. С другой стороны существует множество успешно применяемых методов определения тематической принадлежности документов, в том числе и с использованием алгоритмов классификации (или методов машинного обучения [1]), использующих обучающие коллекции документов. Однако высокая вычислительная сложность задач обучения и классификации ограничивает практическую применимость таких методов для Web.

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

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

Основные результаты, полученные автором в ходе исследования и вынесенные на защиту, заключаются в следующем:

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

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

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

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

Содержание диссертации организовано следующим образом:

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

• В главе 2 описана схема работы нового метода периодического тематического поиска, основанного на комбинации традиционного

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

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

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

4.4 Выводы

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

101 полученных результатов. Результаты экспериментов позволяют говорить о перспективности предложенного метода для повышения релевантности периодического тематического поиска в Web.

Заключение

К основным результатам, полученным автором и описанным в данной диссертации (главы 2,3 и 4), относятся:

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

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

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

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

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

В качестве перспективного направления развития области диссертационного исследования следует отметить интеграцию систем автоматизированного периодического тематического поиска с тематическими сообществами, получившими широкое распространение в Web. С помощью такой интеграции можно добиться синергетического эффекта от объединения концепций совместного обучения (collaborative learning) [106] и машинного обучения, рассмотренного в данной работе. Так, тематические сообщества могут быть использованы в качестве поставщиков обучающих примеров для обучения классификаторов, а доступность автоматизированного сервиса периодического тематического поиска в свою очередь может интенсифицировать процесс анализа и обмена новой информацией внутри тематических Web-сообществ.

По теме диссертационного исследования опубликовано семь печатных работ [16-22].

1. Агеев М. С. Методы автоматической рубрикации текстов, основанные на машинном обучении и знаниях экспертов. Дис. канд. физ-мат. наук: 05.13.11. Московский гос. унив. Москва, 2005.

2. Вайнцвайг М.Н. Алгоритм обучения распознаванию образов "Кора" // Алгоритмы обучения распознаванию образов / Под ред. В.Н. Вапника. — М.: Сов. радио, 1973, стр. 110-116.

3. Вапник В.Н. Восстановление зависимостей по эмпирическим данным. М.: Наука, 1979.

4. Губин М. Исследование качества информационного поиска с использованием пар слов// Седьмая Всероссийская научная конференция RCDL. Ярославль, 2003

5. Зализняк А. Грамматический словарь русского языка. Русский язык, Москва, 1980

6. Кураленок И., Некрестьянов И. Оценка систем текстового поиска// Программирование. — 28(4), 2002, стр. 226-242 Коржов В. Программы локального поиска// Журнал "Открытые системы" #11, 2005

7. Максаков A.B. Исследование способов уменьшения набора характеристик в алгоритмах классификации текстов// Труды Всероссийской научной конференции "Методы и средства обработки информации" -М.: Издательский отдел факультета ВМиК МГУ, 2003, стр. 234-240.

8. Максаков A.B. Масштабируемые алгоритмы классификации текстов// Труды 12-й конференции "Математические методы распознавания образов" (ММРО-12), Москва, 2005.106

9. Максаков A.B. Обеспечение контекстного поиска информации для баз знаний// Искусственный интеллект (Донецк), 2002 № 2, стр. 493-500

10. Труды РОМИГГ2003// НИИ Химии СПбГУ / Под ред. И.С.Некрестьянова — Санкт-Петербург, 2003 — 132 стр.

11. Baeza-Yates R., Ribeiro-Beto В. Modern Information retrieval. New York: ACM Press, 1999.

12. Baker L., McCallum A. Distributional Clustering of Words for text Classification// Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM Press, 1998. p. 96-103

13. Barfourosh A., Nezhad H., Anderson M., Perils D. Information Retrieval on the World Wide Web and Active Logic: A Survey and Problem Definition// Technical report CS-TR-429. College Park: University of Maryland, 2002. p. 1-45.

14. Baudisch P., Dynamic Information Filtering. GMD Research series 2001 No 16, Darmstadt Technology University, 2001, Germany

15. Belkin N., Croft W. Information filtering and information retrieval: two sides of the same coin?// Communications of the ACM, Volume 35 , Issue 12. New York: ACM Press, 1992. p. 29 38

16. Bergman M. Deep Web: Surfacing Hidden Value// The Journal of Electronic Publishing 7(1), 2001.

17. Binkley J., Young L. Rama: An Architecture for internet information filtering// Journal of Intelligent information systems #5. Hingham: Kluwer academic publishers, 1996. p.81-99.

18. Brake D. Lost in Cyberspace // New Scientist. London: Red Business, 1997. p. 12-13.

19. Brin S., Page L. The anatomy of a large-scale hypertextual Web search engine// Computer Networks 30(1-7). London: Elsevier, 1998. p. 107-117.

20. Bun K., Ishizuka M. Emerging Topic Tracking System// Proceedings of Web Intelligence Conference. London: SpringerVerlag, 2001. p. 125-130.

21. Chakrabarti S. Data Mining for hypertext: A tutorial survey// SIGKDD Explorations, vol.1, issue 2. New York: ACM Press, 2000. p. 1-10

22. Chakrabarti S. Mining The Web Discovering Knowledge From Hypertext Data. San Francisco: Morgan Kaufmann Publishers, 2004

23. Chakrabarti S., Berg M., Dom B. Focused Crawling: A New

24. Approach to Topic-Specific Web Resource Discovery// In Proc. ofththe 8 conference on WWW. New York: Elseiver North Holland, 1999. p. 1623-1640.

25. Chen H., Dumais S. Bringing Order to the Web: Automatically Categorizing Search // Proceedings of ACM SIGCHI Conference on Human Factors in Computing Systems, Vol. 1. New York: ACM Press, 2000. p. 145-152

26. Cohen W., Fast Effective Rule Induction// Proceeding of 20th International Conference on Machine Learning. Tahoe: Morgan Kaufmann Publishers, 1995. p. 115-123.

27. Diao Y., Lu H., Wu D. A comparative study of classification-based personal E-Mail filtering// In proceedings of 4th Pacific-Asia Conference on Knowledge Discovery and Data Mining. Kyoto: Springer Verlag, 2000. p.408-419.

28. Douglis F., Ball T., Chen Y., Koutsofos E. The At&T Internet Difference Engine: Tracking and Viewing changes on the Web// World Wide Web #1: 1998. p. 27-44.

29. Driori O., Aron N. Using documents classification for displaying search results list// Journal of Information Science, 29, vol. 2. London: Chartered Institute of Library and Information Professionals, 2003. p. 97-106.

30. Dumais S., Cutrell E., Chen H. Optimizing search by showing results in contextII CHI '01: Proceedings of the SIGCHI conferenceon Human factors in computing systems. New York: ACM Press, 2001. p. 277-284.

31. Dumais S., Platt J., Heckerman D., Sahami M. Inductive learning algorithms and representations for text categorization. // In Proceedings of International Conference on Information and Knowledge Management. New York: ACM Press, 1998. p. 148155.

32. Eichler K. Automatic Classification of Swedish Email Messages. Master thesis, Eberhard-Karls-University, Sweden, 2005. http://www.sfs.uni-tuebingen.de/iscl/Theses/eichler.pdf

33. Filman R. Searching the Internet// IEEE Internet Computing, July 1998. p. 21-23

34. Fisher R. The use of multiple measurements in taxonomic problems// Eugenics, 7: 1936. p. 179-188

35. Frakes W., Baeza-Yates R. Information retrieval: Data structures and algorithms. Prentis Hall,Upper Saddle River, NJ, USA: 1992.

36. Francopoulo G. Experiments with Chunker and Lucene// Advances in Cross-Language Information Retrieval, Third Workshop of the Cross-Language Evaluation Forum, CLEF 2002. Heidelberg: Springer, 2002. p. 336-337.

37. Furnkranz J. A study using n-gram features for text categorization// Technical report OEFAI-TR-98-30. Vienna: Austrian Institute for Artificial Intelligence, 1998. p. 1-10.

38. Gulli A., Signorini A. The Indexable Web is more than 11.5 billion pages// Special interest tracks and posters of the 14th international conference on World Wide Web. New York: ACM Press, 2005. p. 902-903.

39. Haykin S. Neural Networks: A Comprehensive Foundation. New York: Macmillan College Publishing, 1994

40. Hersh W. OHSUMED: An Interactive Retrieval Evaluation and New Large Test Collection for Research// Proceedings of the 17th Annual International Conference on Research and Development in Information Retrieval/ New York: Springer-Verlag, 1994. p. 192201.

41. Hofmann T. Probabilistic latent semantic indexing// In Proc. of the SIGIR'99. NY: ACM Press, 1999. p. 50-57. Ingwersen P. Information retrieval interaction. London: Taylor Graham Publishing: 1992.

42. Joachims. A Probabilistic Analysis of the Rocchio algorithm with TFIDF for text categorization// Proc. of Int. Conf. on Machine Learning (ICML). San Francisco: Morgan Kaufmann Publishers, 1997. p. 143-151.

43. Joachims T. Estimating the Generalization Performance of a SVM Efficiently. // Proceedings of the International Conference on Machine Learning. San Francisco: Morgan Kaufman, 2000. p. 431438.

44. Joachims T. Making large-scale SVM learning practical// Advances in kernel methods: Support vector learning. Cambridge: MIT-Press, 1999. p. 169-184.

45. Joachims T. Text Categorization with Support Vector Machines: Learning with Many Relevant Features. // Proceedings of ECML-98, 10th European Conference on Machine Learning. Heidelberg: Springer, 1998. p. 137-142.

46. Juan, A., Ney, H.: Reversing and Smoothing the Multinomial Naive Bayes Text Classifier. In: Proc. of the 2nd Int. Workshop on Pattern Recognition in Information Systems (PRIS 2002). Alacant (Spain): 2002. p. 200-212

47. Kahle B. Preserving the Internet// Scientific American: March 1997. p. 82-83

48. Khare R., Cutting D., Sitaker K., Rifkin A. Nutch: A Flexible and Scalable Open-Source Web Search Engine// CommerceNet Labs Technical Report #04-04. May 10, 2005. http://www.master.netseven.it/files/262-Nutch.pdf

49. Koch T., Ardo A., Bremmer A., Lundberg S. The building and maintenance of robot based internet search services: A review of current indexing and data collection methods// Technical report, Lund University Library, Sweden, 1996

50. Kobayashi M., Takeda K. Information retrieval on the Web// ACM Computing Surveys, vol.32, 2. New York: ACM Press, 2000. p. 144-173.

51. Kolesnikov O., Lee W., Lipton R. Filtering spam using search engines//Georgia Tech Technical Report, GIT-CC-03-58, 2003. ftp://ftp.cc.gatceh.edu/pub/coc/tech reports/GIT-CC-03-58.pdf

52. Kullback S., Leibler R. On Information and Sufficiency// The Annals of Mathematical Statistics, Vol. 22, No. 1 (Mar., 1951). p. 79-86

53. Kwon J., Rao P., Moon B., Lee S. FiST: scalable XML document filtering by sequencing twig patterns// Proceedings of the 31st international conference on Very large data bases. New York: ACM Press, 2005. p. 217-228

54. Lang K. Newsweeder: Learning to filter netnews// Proceedings oftfithe 12 International Conference on Machine Learning. San Mateo: Morgan Kaufmann, 1995. p. 331-339.

55. Lawrence S., Giles C. Accessibility of information on the Web// Nature, 400 (July 8, 1999), p. 107-109

56. Lawrence S, Giles C. Context and page analysis for improved web search// IEEE Internet computing, vol.2, issue 4, 1999. p. 38-46

57. Lawrence S., Giles C. Inquirus, The {NECI} Meta Search Engine// Proc. Of 7th International World Wide Web Conference. Brisbane: Elsevier Science, 1998. p. 95-105.

58. Lawrence S., Giles C. Searching the World Wide Web// Science, 280(5360), 1998. p. 98-100.

59. Lewandowski D., Wahlig H., Gunnar M. The freshness of Web search engines' database// Journal of Information Science vol. 32, issue 2,2006. p. 131-146.

60. Lewis D. An Evaluation of Phrasal and Clustered Representation on a Text Categorization Task// Proceedings of International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM Press, 1992. p. 37-50.

61. Lewis D. Representation and learning in information retrieval. Dissertation, Dept. Of Computer and Information Science, Univ. of Massachusetts, 1992

62. Lewis D. Reuters-21578 text categorization test collection. Distribution 1.0. http://www.daviddlewis.com/resources/testcollections/reuters21578 /readme.txt

63. Liao C., Alpha S., Dixon P. Feature preparation in text categorization// Proc. of Australian Data Mining Workshop. Sydney: University of Technology, 2003. p. 23-34

64. Liu L. Query routing in large-scale digital library systems// In proc.th

65. Of the 15 conference on Data Engineering. IEEE press, 1999. p. 154-163.

66. Mackassy S. New Techniques in Intellegent Information Filtering. Ph.D. dissertation thesis, New Brunswick, New Jersey, 2003.

67. Marchionini G. Information Seeking in Electronic Environments. Cambridge series on human-computer interactions, 9, Cambridge University Press, 1995.

68. Marshall R. Generation of Boolean classification rules. // Proceedings of Computational Statistics 2000. Heidelberg: Springer-Verlag, 2000. p. 355- 360.

69. Mladenic D. Turning Yahoo to Automatic Web-Page Classifier// Proceedings of the 13 European Conference on Artificial Intelligence (ECAI'98) Brighton, UK: ECCAI Press, 1998. p. 473474

70. Mostafa J. A multilevel approach to intelligent information filtering: model, system and evaluation// ACM transactions on information systems. New York: ACM Press, 1997. p. 368-399.

71. Menczer F., Belew R. Adaptive retrieval agents: Internalizing local context and scaling up to the Web// Machine learning, vol. 39, issue 2-3. Boston: Kluwer academic publishers, 2000. p. 203-242.

72. Nigam K., McCallum A., Thrun S., and Mitchell T. Learning to classify text from labeled and unlabeled documents// Proc. of the 15th National Conf. on Artificial Intelligence. Menlo Park: AAAI Press, 1998. p. 729-799.

73. Ntoulas A., Cho J., Olston C. What's new on the Web? Theevolution of the Web from a Search Engine perpective// Inthproceedings of the 13 International World Wide Web Conference. New York:ACM Press, 2004. p. 1-12.

74. Oard D. The State of the Art in Text Filtering// User Modeling and User-Adapted Interaction, Volume 7, Issue 3. Hingham: Kluwer Academic Publishers, 1997. p. 147-178

75. Osinski S., Weiss, D. Carrot2: Design of a flexible and efficient Web information retrieval framework// In Proceedings A WIC 2005. Heidelberhg: Springer, 2005. p. 439-444.

76. Pazzani M., Nguyen L., Mantik S. Learning from hotlists and coldlists: Towards a WWW information filtering and seekingagentII 7th International Conference on Tools with Artificial Intelligence. Washington: IEEE Computer Society, 1995. p. 492.

77. Provost J. Naive-Bayes vs. rule-learning in classification of Email// Technical Report AI-TR-99-284. Austin: The University of Texas, Department of Computer Sciences, 1999. p. 1-4.

78. Porter M. (1980). An algorithm for suffix stripping// Program, 14(3), p. 130-137.

79. Quinlan R. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, 1993

80. Rainie L. Search Engine use November 2005. PDF] http://www.pewinternet.org/pdfs/PIP SearchData 1105.pdf96. van Rijsbergen C. Information Retrieval. Butterworth's and Co. — London, 1979 — 2nd edition.

81. Sahami M., Dumais S., Heckerman D., Horvitz E. A Bayesian Approach to Filtering Junk E-Mail// In proceedings of the AAAI'98 Workshop on Learning for Text Categorization, p. 55-62.

82. Salton G., Wong A., and Yang C. A vector space model for automatic indexingII Communications of the ACM, 18(11), 1988. p. 613-620.

83. Salton G., Buckley C. Term-weighting approaches in automatic text retrieval// Information Processing and Management, 24(5), 1988. p. 513-523.

84. Salton G., McGill M. Introduction to modern Information Retrieval. McGraw-Hill Computer Science Series. McGraw-Hill, New York, 1983

85. Sarawagi S., Nagaralu S. Data mining models as services on the internet// ACM SIGKDD explorations newletter, vol. 2, issue 1. New York: ACM Press, 2000. p. 24-28

86. Sebastiani F., Machine Learning in Automated Text Categorization//ACM Computing Surveys, vol.1,2002. p. 1-47115

87. Sebastiani F. Text Categorization// Text Mining and its Applications to Intelligence, CRM and Knowledge Management. Southampton: WIT Press, 2005. p. 109-129.

88. Sheth B. A Learning Approach to Personalized Information Filtering// Master thesis, Department of Electrical Engineering and Computer Science, 1994. 75 p.

89. Temperley D, Lafferty J., Sleator D. 1995.Link Grammar Parser. http://www.link.cs.cmu.edu/link

90. Twidale M., Nichols D., Smith G., Trevor J. Supporting collaborative learning during information searching// In proc. of 1st international conf. on collaborative learning. Mahwah: Lawrence Erlbaum associates, 1995. p. 367-370.

91. The Twelfth Text Retrieval Conference (TREC 2003). Appendix 1. Common Evaluation Measures. http://trec.nist.gov/pubs/trecl2/appendices/measures.ps

92. Vapnik V. The Nature of Statistical Learning Theory. SpringerVerlag, New York, 1995.

93. Voorhees E., Harman D. Overview of the seventh Text Retrieval Conference TREC 7// In Proceedings of the seventh Text Retrieval Conference TREC 7. Gaithersburg: NIST, 1998.

94. Wasson M. Classification Technology at LexisNexis // SIGIR 2001 Workshop on Operational Text Classification.

95. Wiener E., Pedersen, J., Weigend, A. A neural network approach to topic spotting// In Proceedings of SDAIR-95, 4th Annual Symposium on Document Analysis and Information Retrieval. Las Vegas, 1995. p. 317-332.

96. Wong S., Yao Y. An information-theoretic measure of term specificity// Journal of the American Society for Information Science, 43(1): p. 45-61, 1992.

97. Yan T., Garcia-Molina H. SIFT A tool for Wide-Area Information Dissemination// In proceedings of USENIX Technical conference. Berkley: USENIX association, 1995. p. 177-186.

98. Yang Y., Liu X. A re-examination of text categorization methods// Proc. of International ACM Conf. on Research and Development in Information Retrieval (SIGIR-99). New York: ACM Press, 1999. p. 42-49.

99. Yang Y., Pedersen J. A comparative study on feature selection in text categorization. // In: Proc. of ICML-97, 14th International Conf. On machine Learning. San Francisco: Morgan Kaufmann publishers, 1997. p. 412-420.

100. Zipf G. Human behaviour and the principle of least effort. Addison Wesley, 1949.