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

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

ИИ4Ы7931

БОРИСЮК Федор Владимирович

система поиска текстовых документов на основе автоматически формируемого электронного каталога

Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ

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

2010

004617931

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

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

доктор технических наук, профессор Швецов В.И.

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

Карпычев В.Ю. (г. Н. Новгород)

доктор технических наук, профессор, Подольский В.Е. (г. Тамбов)

Ведущая организация

ГОУ ВПО "Саратовский государственный технический университет".

Защита состоится «2-5» а <Ць<£ь№2010 г. в / ^^часов на заседании Совета по защите дшсторских и кандидатских диссертаций Д 212.166.13 при Нижегородском государственном университете им. Н.И. Лобачевского по адресу: 603950, Н. Новгород, пр. Гагарина, д. 23.

С диссертацией можно ознакомиться в фундаментальной библиотеке Нижегородского государственного университета им. Н.И. Лобачевского.

Автореферат размещен на сайте http://www.vmn.ru университета ННГУ им. Н.И. Лобачевского.

Автореферат разослан «2--У» Н^З^Л. 2010 г.

Ученый секретарь диссертационного совета кандидат физико-математических наук, доцент

Савельев В.П.

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

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

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

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

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

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

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

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

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

— разработана модель поиска с тематическим ранжированием, на основе автоматически построенного электронного каталога;

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

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

— разработана программная система поиска (поисковая система) на основе модели поиска по ключевым словам с тематическим ранжированием, на основе автоматически построенного электронного каталога текстовых документов;

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

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

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

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

В рамках реализации этой модели разработаны:

• Новый метод тематического ранжирования, основанный на автоматически построенном электронном каталоге.

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

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

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

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

жегородского государственного университета им. Н.И. Лобачевского" (http://www.unn.ru/e-library/vestnik.html) на интернет-портале Нижегородского государственного университета им. Н.И. Лобачевского.

Апробация результатов. Результаты диссертации докладывались и обсуждались на всероссийской конференции «Технологии Microsoft в теории и практике программирования 2009» (Н. Новгород, 2009 г.), международной научно-практической конференции по графическим информационным технологиям и системам «КОГРАФ-2009» (Н. Новгород, 2009), 9-й международной конференции "Высокопроизводительные параллельные вычисления на кластерных системах" (Владимир, ВлГУ, 2009), всероссийской научной школе для молодежи "Управление информационными ресурсами образовательных, научных и производственных организаций" (Магнитогорск, Магнитогорский государственный университет, 2009), всероссийской конференции «Технологии Microsoft в теории и практике программирования 2010» (Н.Новгород, 2010), международном коллоквиуме SYRCoSE (Н. Новгород, 2010), на семинаре кафедры математического обеспечения ЭВМ факультета ВМК ННГУ.

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

• Новая модель информационного поиска по ключевым словам с тематическим ранжированием, основанная на использовании автоматически построенного электронного каталога.

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

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

• Архитектура и функциональные возможности разработанной программной системы.

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

Публикации и личный вклад автора. Основное содержание диссертации нашло отражение в 6 опубликованных научных работах, в том числе 1 статья в рецензируемом издании, рекомендованном ВАК РФ.

Также, принята в печать научная статья "Распределенная реализация построения индекса поискового каталога" в № 1 (2011 г.) журнала Вестник ННГУ им. Н.И. Лобачевского, входящего в список ВАК. Результаты совместных научных работ [1,2,4,6], использованные в диссертационной работе, принадлежат лично автору диссертации.

Структура и объем работы. Работа состоит из введения, трех глав, заключения, списка литературы. Общий объем работы составляет 115 страниц. Список литературы составляет 68 наименований. Основные результаты излагаются в главах 2 и 3.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

1. Введение

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

2. Общая характеристика проблемы тематического ранжирования, на основе автоматически построенного электронного каталога текстовых документов

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

Задача информационного поиска по ключевым словам заключается в автоматическом поиске документов, содержащих заданные ключевые слова, в текстовой коллекции. Ключевое слово - это слово в тексте, способное в совокупности с другими ключевыми словами представлять текст. Рассмотрим коллекцию текстовых документов D = {Dj, ... , Dn} на некотором естественном языке. В целях задачи поиска каждый из документов представляется в виде его информационно-поискового образа - вектора ключевых слов A- = {ti,...,tv}. Выделение ключевых слов представляет собой процедуру выборки наи-

более значимых слов документа. Множество векторов ключевых слов документов представляет пространство На рис. 1 изображена матрица отображения множества документов в пространство признаков - ключевых слов. Элементами матрицы являются веса ключевых слов по отношению к рассматриваемому документу.

ti t2 ... tv

di Wn W)2 W,v

d2 W21 W22 W2V

... Wy

dn Wni WN2 WNV

Рис. 1. Отображение множества документов в пространство признаков

Пусть имеется запрос q={tji,..., tjL} е Rv, характеризующий некоторую информационную потребность. Тогда целью задачи поиска по ключевым словам является построение ранжированного по заданной функции ранжирования F списка документов Dib ... , DiK соответствующих данному запросу q. Функция ранжирования должна удовлетворять свойству упорядоченности, то есть для пары документов Di, Dj выполняется F(Dj) > = F(Dj), если документ Dj в большей степени соответствует запросу q, чем документ Dj. Наиболее известным примером функции ранжирования является Okapi ВМ251 (функция базового ранжирования), которая ранжирует документы в зависимости от их веса, вычисленного на основе встречаемости слов запроса в каждом из рассматриваемых документов (без учёта взаимоотношений между словами).

Модель поиска с тематическим ранжированием

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

1 Stephen E. Robertson, Steve Walker, Susan Jones, Micheline Hancock-Beaulieu, and Mike Gatford. Okapi at TREC-3. In Proceedings of the Third Text Retrieval Conference (TREC 1994). Gaithersburg, USA, 1994.

3 К = {Кь ..., KL}, которые возможно выделить.

В данной работе предлагается ранжировать документ выше, если он соответствует тематике поискового запроса. Под тематикой поискового запроса понимается превалирующая тематика Кь (которая может быть явно задана, или определяться по формуле ниже) из множества тематических групп IQ,, документы которых присутствуют в результатах Qr поискового запроса: Kq={Kii,..., К,м} d К, где Vce{ib...,iM},aD; с Qr, i е [1,| Qr |]: Dj е К,,

Kb(q) = maxc(maxf (Вес_базовой_фуикции_ранжирования(0|)): D, е КС,КС с Kq).

В качестве тематической функции ранжирования в рамках данной работы были разработаны и предлагаются формулы (1) для подсчета веса документа D из результатов поискового запроса, где base-Weight(D) - вес документа, выдаваемый базовым алгоритмом ранжирования (например, алгоритмом ВМ25); Тор - количество выдаваемых результатов на поисковой странице, Total - количество всех поисковых результатов, удовлетворяющих запросу q.

F(D) = Вес _ документа{В, Кь) = baseWeight{D) + categoryInfluence{D, Kb); deg_ cat(D) = baseWeight(D) * (1 - (max Weight - baseWeight(D))); deg_ ncat(D) = (max Weight - baseWeight(D)) * (1 - baseWeight(D))\

(1)

-, если De К,

categoryInfluence{D, Kb) =

norm

Top Total

norm

--,если_D £Kb

norm = 2™™"'"**'£ Log2(1 + /); X baseWeight(D,) = 1; max Weight = maxD (baseWeight(D));

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

Для построения иерархии электронного каталога используются

методы текстовой кластеризации. В частях 1.3—1.4 первой главы приводится постановка задачи текстовой кластеризации, и производится обзор и анализ существующих алгоритмов текстовой кластеризации. Входными данными задачи текстовой кластеризации являются образы текстовых документов/) = {А,...,-£)лг}, каждый из которых представлен многомерным вектором в пространстве признаков. В рамках задачи текстовой кластеризации в исследуемой коллекции текстовых документов предполагается наличие множества тематических групп (другими словами - кластеров) К = {Кь ..., Кь}, которые возможно выделить. Выделение тематических групп (текстовая кластеризация) заключается в поиске неизвестного множества групп К схожих документов, в соответствии с некоторой мерой близости между объектами кластеризации. Наиболее часто применяемой мерой близости является косинусная мера близости между векторами документов (2):

V -

,Ьу) = С05(< (Л ,Бу)) = ■ ™ ■ _ (2)

ЛЕ<м2*Л>)2

V 1=0 V 1=0

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

Для оценки методов кластеризации в данной работе решено использовать общепринятую меру оценки качества - стандартную П-меру2. Б1-мера (3) оценивает, насколько разбиение построенное алгоритмом кластеризации совпадает с "эталонным" разбиением, подготовленным экспертом:

2* Точность* Полнота

^1 =--(3)

Точность + Полнота

Целью является максимизация меры.

Для измерения качества работы алгоритма тематического ранжи-

2 B. Stein, S. Meyer zu Eissen, F. Wißbrock. On Cluster Validity and the Information Need of Users. In Proc. 3rd IASTED

International Conference on Artificial Intelligence and Applications (AIA'03), 2003. P. 404-413.

рования в работе используется общепринятая метрика КОСО@Ьч3, описываемая формулой (4):

100 2/(г) — 1 Iй"

Л®С(?@14=—£———; ыосо@ь = -5-£л®сс@1, (4)

^ + г) £?г<н

Так же как и для Р1-меры, метрика N000 дает оценку ранжирования, подготовленного алгоритмом ранжирования для заданного запроса я, по сравнению с "эталонным" ранжированием, подготовленным экспертом. В качестве итоговой оценки алгоритма ранжирования подсчитывается среднее значения метрики (5), для

всей коллекции подготовленных экспертом запросов (размером Ят).

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

3. Разработка тематического ранжирования на основании автоматического построения электронного каталога текстовых документов

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

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

3 К. Jarvelin and J. Kekalainen. IR evaluation methods for retrieving highly relevant documents. In SIGIR, 2000. P. 41-48.

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

Для оценки важности рассматриваемой основы слова по отношению к документу в данной работе применялись формулы TF-IDF (5). Выделяют понятия TFj (term frequency) - частоты основы tj в документе D, а также IDF (inversed document frequency) - обратная частота встречаемости основы tj в документах коллекции, N - общее количество документов коллекции, DN; - количество документов, содержащее основу tj.

IDF(t.) = log fl + ———1; ДеСррО = . ^^ 2 (5)

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

Рис. 2. Структура дерева областей

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

1) Инициализация алгоритма иерархической кластеризации по областям.

В качестве исходных данных на данном этапе алгоритма выступают документы Б = {Вь...Д}к}, представленные множеством ключевых слов Ц= {1],..., 1у}- Первоначально все поступающие документы попадают в специальную область дерева, называемую корзиной, до тех пор, пока количество документов не превысит заранее заданный предел. При превышении предела область-корзина разбивается на подобласти (используется алгоритм К-средних), которые присоединяются к верхнему уровню дерева.

2) Этап обработки входящего потока документов.

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

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

предложено использовать программную модель MapReduce4. Концепция MapReduce состоит в том, что производимые вычисления разбиваются на функции Map и Reduce. Функция Map трансформирует входные данные в промежуточный список пар ключ/значение. Функция Reduce берет список пар ключ/значение, который генерирует Map и свертывает его по ключу (на выходе одна пара ключ/значение для каждого ключа). В части 2.7 второй главы данной работы представлено описание распределенной версии алгоритма подготовки образов текстовых документов. Распределенная версия алгоритма построения образов текстовых документов состоит из двух шагов.

Входные данные Документы в текстовом формате.

Map Построить вектор частот встречаемости основ слов документа.

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

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

На первом шаге происходит построение вектора DF(BCTpe4ae-мости слов в документах коллекции), который состоит из записей <основа слова, количество документов, содержащее данную основу>: в функции Map производится подсчет уникальных вхождений основ слов в рассматриваемый документ, в функции Reduce аккумулируются результаты подсчетов для каждой основы слова по всей коллекции документов. На втором шаге, происходит формирование образов текстовых документов (рис. 3).

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

4 Jeffrey Dean, Sanjay Ghemawat. MapReduce: simplified data processing on large clusters // Communications of the ACM. 2008. V. 51. P. 107-113.

шагов. На первом шаге алгоритма производится подготовка дерева областей верхнего уровня (рис. 4).

Входные данные Образы документов в виде векторов ключевых слов.

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

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

Рис. 4. Формирование дерева областей верхнего уровня

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

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

Map Для каждого входного образа документа определить область дерева верхнего уровня. Выходные пары (ключ, значение) = (идентификатор области верхнего уровня, образ документа). Внутренними средствами Hadoop выходные пары Map группируются по ключу и далее передаются на вход Reduce.

Reduce Для всех документов отображенных на шаге Map в подобласть дерева верхнего уровня - построить поддерево областей.

Рис. 5. Параллельная реализация иерархической кластеризации по областям

Тематическое ранжирование списка результатов поиска

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

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

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

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

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

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

Компонент построения иерархической структуры каталога

Компонент иерархической кластеризации текстовых документов по области м

Компонент построения названий и описании рубрик иерархического каталога

Компонент оценки результатов текстовой кластеризации

Ж

Компонент алгоритмов параллельного построения электронного каталога

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

Распределенное построение индекса текстовой коллекции

Компонент построений образов Л текстовых документов

Компонент извлечения текстовых данных из других форматов prif, ».

Компонент извлечения ключевых ело» из текстовых документов

Компонент ранжирования результатов поиска {В!И25, по группам, по тематике)

Компонент оценки ранжирования результатов поиска

Веб интерфейс взаимодействия с пользователем

Компонент поиска результатов в построенном индексе

'омпонент поиска с тематический ранжированием результатов

...... Индекс поисковой системы

Q О О О

Рис. 6. Архитектура разработанной программной системы поиска по ключевым словам с тематическим ранжированием

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

для проверки работоспособности алгоритма были выбраны две коллекции - русскоязычная и англоязычная: коллекция статей журнала "Вестник Нижегородского государственного университета им. Н.И. Лобачевского" (1972 русскоязычных текста, 1 ГБ данных), коллекция новостных статей "20№\¥50гоир8" (20000 англоязычных текстов, 46 МБ данных).

Используя введенный критерий оценки качества кластеризации (Б 1-мера), были проведены численные эксперименты по измерению качества работы предлагаемого алгоритма и традиционных алгоритмов иерархической кластеризации, которые показали превосходство предлагаемого алгоритма иерархической кластеризации по областям, используемого для автоматического построения иерархии каталога, по сравнению с традиционными алгоритмами иерархической кластеризации. Результаты сравнения приведены на рис. 7 и рис. 8.

Иерархический Послойная Разделительный Иерархическая Агломеративный кластеризация Ктеапз кластеризация

по областям

Рис. 7. Сравнение качества работы алгоритмов текстовой кластеризации по Р1-мере качества кластеризации на тестовой коллекции "Вестник"

> о

8 I

о

6 I

а |

15 N 10 | 5

I О

3545 сек.

-403 сек.

9 сек.

~6~еек~

Иерархмческий Агломератиеный

Послойная Разделительный Иерархическая кластеризация Ктеап5 кластеризация по

областям

Рис. 8. Сравнение времени работы последовательных алгоритмов текстовой кластеризации (в логарифмической шкале, по основанию 2)

Исследование параллельных версий предложенных алгоритмов

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

е

о в

а

а

ш

12 4 6

Количество процессорных ядер

—4—»20000

документов

документов

Рис. 10. Зависимость времени работы иерархической кластеризации по областям от количества задействованных в вычислениях процессорных ядер

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

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

го университета им. Н.И. Лобачевского", которые показали превосходство предлагаемого алгоритма ранжирования по сравнению с базовым алгоритмом Okapi ВМ25 (рис. 11).

1 77,, 25% 78,39%

Okapi ВМ25 Тематическая Ранжирование

группировка результатов по результатов заданной тематике

Рис. 11. Качество работы алгоритмов ранжирования по метрике ЫОСО@Ю

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

На рис. 12 приведен график изменения метрики ЫБСО@Ю в зависимости от количества запросов: при увеличении количества запросов до 30 наблюдается стабилизация значения критерия качества N000(0)10.

5 Труды РОМИП 2009. Российский семинар по оценке методов информаци онного поиска. Санкт-Петербург. 2009. 198 с.

5 10 15 20 25 30

Количество запросов

Рис. 12. График изменения метрики ЫБСО@Ю в зависимости от количества запросов

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

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

1) Разработана новая модель информационного поиска с тематическим ранжированием, основанным на автоматически построенном электронном каталоге. Предложенные методы тематического ранжирования показали улучшение качества ранжирования результатов поиска от 1% до 15% по метрике МОСО@Ю.

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

3) Предложен новый метод текстовой кластеризации - иерархическая кластеризация по областям текстовых документов, учитывающий недостатки существующих алгоритмов иерархической текстовой кластеризации. Разработаны последовательные и параллельные версии предложенного алгоритма. Проведенные испытания показали преимущество в качестве предложенного алгоритма иерархической кластеризации по областям по сравнению с тремя традиционными алгоритмами кластеризации. Улучшение качества кластеризации составило от 9 % до 22%.

4) Разработаны параллельные версии алгоритмов извлечения тек-

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

5) Разработан метод автоматического выбора названия и описания для сформированных кластеров автоматически построенного электронного каталога.

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

Публикации в изданиях, рекомендованных ВАК РФ

1) Борисюк Ф.В. Новый метод поиска на основе иерархической кластеризации по областям текстовых документов / Борисюк Ф.В., Швецов В.И. // Вестник ННГУ им. Н.И. Лобачевского. 2009. № 4. С. 165-171.

Публикации в прочих изданиях

2) Борисюк Ф.В. Иерархическая кластеризация по областям текстовых документов / Борисюк Ф.В., Швецов В.И. // Материалы всероссийской конференции Технологии Майкрософт в теории и практике программирования. 2009. С. 48-54.

3) Борисюк Ф.В. Выделение ключевых слов в научной коллекции гипертекстовых документов / Борисюк Ф.В. // Сборник материалов всероссийской научной школы для молодежи "Управление информационными ресурсами образовательных, научных и производственных организаций". Магнитогорск, Магнитогорский государственный университет. 2009. С. 31-32.

4) Борисюк Ф.В. Параллельная реализация построения индекса поисковой системы с использованием платформы Hadoop / Борисюк Ф.В., Швецов В.И., Белоусова И.И. // 9-я международная конференция "Высокопроизводительные параллельные вычисления на кластерных системах". Владимир, Владимирский государственный университет. 2009. С. 48-61.

5) Борисюк Ф.В. Параллельная реализация иерархической кластеризации по областям текстовых документов / Борисюк Ф.В. // Материалы всероссийской конференции Технологии Майкрософт в теории и практике программирования. 2010. С. 38-40.

6) Borisyuk F.V. Adaptation of Hierarchical clustering by areas for automatic construction of electronic catalogue / Borisyuk F.V., Shvetsov V.l. // Proceedings of SYRCoSE, 2010. P. 141-145.

Подписано к печати 23.11.2010. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Гарнитура Times. Усл. печ. л. 1. Тираж 100 экз. Заказ 734.

Отпечатано в Центре цифровой печати Нижегородского госуниверситета им. Н.И. Лобачевского 603000, Н. Новгород, ул. Б. Покровская, 37.

Введение.^.

Глава I. Общая характеристика проблемы тематического ранжирования, на основе автоматически построенного электронного каталога текстовых документов.

1.1 Предлагаемая математическая модель поиска по ключевым словам с тематическим ранжированием.

1.2 Предлагаемая математическая модель автоматического построения электронного каталога.

1.3 Постановка задачи текстовой кластеризации.

1.4 Обзор существующих алгоритмов текстовой кластеризации.

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

1.4.2 Алгоритмы основанные на технологии нейронных сетей.

1.4.3 Алгоритмы кластеризации, основанные на концепции плотности.

1.4.4 Алгоритмы, основанные на теории графов.

1.4.5 Иерархические алгоритмы, строящие бинарное дерево.

1.4.6 Алгоритм кластеризации основанный на суффиксном дереве.

1.4.7 Методы нечеткой кластеризации.

1.5 Оценка качества кластеризации текстовой коллекции.

1.6 Оценка качества ранжирования поисковых результатов.

1.7 Постановка задачи формирования информационных образов текстовых документов.

1.8 Морфологический анализ.

1.9 Обзор методов статического анализа формирования информационных образов документов.

1.9.1 Критерий порога частоты встречаемости слова в документах коллекции.

1.9.2 Критерий информационного веса слова в рубрике.

1.9.3 Критерий прироста информации.

1.10 Оценка важности терминов по формуле TF-IDF.

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

Глава II Разработка математической модели поиска по ключевым словам с тематическим ранжированием на основании автоматического построения электронного каталога текстовых документов.

2.1 Подготовка информационных образов текстовых документов.

2.2 Построение инвертированного индекса.

2.3 Иерархическая кластеризация по областям текстовых документов.

2.3.1 Инициализация алгоритма иерархической кластеризации по областям.

2.3.2 Этап обработки входящего потока документов.

2.3.3 Критерий качества уровня дерева.

2.3.4 Операция разделения области.

2.3.5 Операция интеграции подобластей.

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

2.4 Преобразование иерархии кластеров в иерархию электронного каталога

2.5 Построение вербального описания иерархического каталога.

2.6 Описание выбранной технологии распределенного программирования MapReduce.

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

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

2.9 Поиск по ключевым словам с тематическим ранжированием, на основе электронного каталога.

Выводы по главе II.

Глава III. Программная реализация системы поиска с тематическим ранжированием, на основе автоматически построенного электронного каталога

3.1 Структура программного комплекса поисковой системы с тематическим ранжированием, на основе автоматически построенного электронного каталога.

3.1.1 Компонент построения иерархической структуры каталога.

3.1.2 Компонент построения образов текстовых документов.

3.1.3 Компонент поиска с тематическим ранжированием результатов.

3.1.4 Компонент алгоритмов параллельного построения электронного каталога.

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

3.3 Выбор параметров алгоритма иерархической кластеризации по областям

3.4 Результаты испытаний предлагаемой математической модели автоматического построения электронного каталога.

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

3.4.2 Исследование предлагаемого способа формирования описания кластеров.

3.4.3 Результаты испытаний параллельных версий разработанных алгоритмов.

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

Выводы по главе III.

Выводы.

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

Традиционными подходами к решению данной задачи являются: классификационный поиск и поиск по ключевым словам. К классификационному поиску относится поиск с использованием различных тематических классификаторов, рубрикаторов, электронных каталогов, которые позволяют искать (автоматически или вручную) документы в небольшом подмножестве исходной коллекции документов по интересующей' пользователя тематике. Рубрикатор (электронный каталог) обычно представляет собой множество рубрик, объединенных в иерархию. К каждой рубрике приписываются соответствующие ее тематике документы. В настоящее время распространены два вида рубрикации. -ручной и автоматизированный. При ручном процессе рубрикации при добавлении в каталог нового документа его нужно вручную проанализировать и определить, к каким рубрикам каталога он относится, после этого документ становится доступным для поиска. Среди традиционных ручных методов каталогизации можно выделить универсальные библиотечные классификаторы, например, УДК [1], ГРНТИ[2], ББК[3]. Данные классификаторы имеют фиксированную структуру и зачастую не поддерживают высоких темпов развития различных областей знаний в науке и технике, а также требуют высоких временных затрат на адаптацию классификаторов, и классификацию по ним документов. 6

Существуют автоматизированные системы поддержки рубрикатора, в которых для каждой рубрики хранится множество признаков, используя которые программа определяет, какой рубрике соответствует анализируемый документ. Можно выделить два существующих класса поддержки автоматизированных систем поддержки каталогов: а) методы, основанные на знаниях, когда список признаков для каждой рубрики составляется экспертом; б) методы, основанные на алгоритмах машинного обучения, которые автоматически извлекают признаки документов на основании подготовленного экспертами обучающего множества (заранее подготовленного множества отрубрицированных документов). Разработками в данной сфере занимались такие исследователи как М. С. Агеев [4], И. С. Некрестьянов [5], В. И. Шабанов [6], Т. Joachims [7], D. D. Lewis [8], Н. Schutze [9], F. Sebastiani [10], S. Т. Dumais [11], P. Bennett [12] и ряд других. Основным недостатком существующих автоматизированных систем является их статичность и невозможность автоматически, без участия эксперта перестроить сформированный ранее каталог. Для примера, трудоёмкость описания рубрик для первого класса методов составляет до 8 человеко-часов^ на одну рубрику [13].

При втором способе поиска пользователь вводит ключевые слова, отражающие его информационную-потребность. При этом результатом поиска, как правило, является достаточно-большое количество документов, среди которых пользователь должен выбрать нужные. Отметим, что одно и то же ключевое слово может соответствовать разным понятиям, поэтому результат поиска заведомо избыточен. Кроме этого, пользователь может ввести ключевые слова не соответствующие интересующему его документу. Для улучшения качества выдаваемых поисковых результатов не так давно появилось новое направление в области информационного поиска поюпочевым словам — поиск поюпочевым словам с использованием категориальной- информации подготовленных вручную электронных каталогов. Среди наиболее известных работ можно выделить работы P. Bennett [14], S. Т. Dumais [15], R. White [15], М. Daoud [16], В. Xiang 7

17]. В данных работах использовался созданный и поддерживаемый группой экспертов-волонтеров по всему миру каталог ODP (Open Directory Project) [18]. Исследователям удалось повысить качество выдаваемых поисковых результатов за счет их тематического ранжирования, когда наиболее важные по тематике документы помещаются алгоритмом ранжирования выше в списке результатов. Однако, исследователи применяли тематическое ранжирование с заранее предопределенным набором тематических групп, а также использовали помощь экспертов при подготовке обучающего множества алгоритма ранжирования, поэтому для применения данного подхода на конкретной области знаний требуется подготовка соответствующего классификатора. Как было замечено, подготовка нового или адаптация существующего классификатора является достаточно затратной, поэтому требуется применение новых, более эффективных методов подготовки электронных тематических каталогов.

Среди известных подходов к решению задачи автоматического построения иерархического каталога можно выделить работы О.В. Песковой [19], а также Tao Li и Shenghuo Zhu [20], D.R. Cutting [63]. В данных работах использовались алгомеративные (построение иерархии снизу вверх) алгоритмы текстовой кластеризации построения иерархической структуры каталога. Однако в данных работах не предполагалось использование автоматически сформированного каталога в задаче тематического ранжирования. Предложенные в данных работах методы автоматического построения^ электронного каталога обладают высокой вычислительной трудоемкостью, что является существенным минусом при учете объемов накопленных текстовых данных. Также можно отметить, что в настоящее время уже невозможно иметь эффективную инфраструктуру без использования распределенных вычислений. Предложенные в упомянутых работах подходы не предлагают распределенных программных решений. Поэтому требуется разработать эффективные методы текстовой кластеризации, которые смогли бы автоматически строить электронный каталог, и позволяли распределенную поддержку больших коллекций текстовых документов. 8

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

Цель работы

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

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

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

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

- разработаны последовательные и параллельные варианты алгоритмов извлечения текстовых признаков;

- разработана математическая модель поиска с тематическим ранжированием, на основе автоматически построенного электронного каталога;

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

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

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

Методы исследований, достоверность и обоснованность результатов.

Для решения поставленных задач были использованы методы математического моделирования, системного анализа, методы математической статистики, кластерного анализа. Эффективность разработанных алгоритмов оценивалась с помощью математических методов анализа алгоритмов. В разработке программного обеспечения применялись методы объектно-ориентированного программирования с использованием инструментов интегрированной среды разработки Eclipse [21]. Для разработки параллельных версий алгоритма использовались программные средства платформы для распределенных вычислений Apache Hadoop [22].

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

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

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

В рамках реализации этой модели разработаны:

• Новый метод тематического ранжирования, основанный на автоматически построенном электронном каталоге.

• Новую математическую модель автоматического построения электронного

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

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

Практическая значимость работы

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

Внедрение

Произведена апробация и внедрение предложенных в данной работе математических моделей и методов поиска по ключевым словам с тематическим ранжированием, на основе автоматически' построенного электронного каталога, в качестве поисковой системы с тематическим ранжированием по статьям журнала "Вестник Нижегородского государственного университета им. Н.И. Лобачевского" (http://www.unn.ru/e-library/vestnik.html) на интернет-портале Нижегородского государственного университета им. Н.И. Лобачевского.

Апробация результатов

Результаты диссертации докладывались и обсуждались на всероссийской конференции «Технологии Microsoft в теории и практике программирования 2009» (ДНовгород, 2009 г.) [23], международной научно-практической

11 конференции по графическим информационным технологиям и системам «КО-ГР АФ-2009» (Н.Новгород,2009), 9-й международной конференции "Высокопроизводительные параллельные вычисления на кластерных системах" (Владимир, ВлГУ, 2009) [24], всероссийской' научной школе' для молодежи "Управление информационными ресурсами образовательных, научных и производственных организаций" (Магнитогорск, Магнитогорский государственный университет, 2009) [25], всероссийской конференции «Технологии Microsoft в теории и практике программирования' 2010» (Н.Новгород, 2010) [26], международном коллоквиуме SYRCoSE (Н.Новгород, 2010) [27], на семинаре кафедры математического обеспечения-ЭВМ факультета ВМК ННГУ.

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

• Новая математическая модель информационного поиска по ключевым словам с тематическим ранжированием, основанная на использовании автоматически построенного электронного каталога.

• Новая математическая- модель автоматического построения электронного каталога текстовых документов без. ограничения на тематику и размер исходнойтекстовой коллекции:

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

• Архитектура и функциональные возможности разработанной программной системы.

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

Основное содержание диссертации нашло отражение в 6 опубликованных научных работах, в том числе 1 статья в рецензируемом издании, рекомендованном ВАК РФ. Также, принята в печать научная статья "Распределенная реализация построения индекса поискового каталога" в №1 (2011 г.) журнала Вестник ИНГУ им. Н.И. Лобачевского, входящего в список ВАК. Результаты совместных научных работ [23,24,27,28], использованные в диссертационной работе, принадлежат лично автору диссертации.

Структура и объем работьг

Работа состоит из введения, трех глав, заключения, списка литературы. Общий объем работы составляет 115 страниц. Список литературы составляет 68 наименований. Основные результаты излагаются в главах 2 и 3.

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

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

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

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

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

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

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

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

• преобразование иерархии кластеров в иерархию электронного каталога;

• автоматическое формирование названий и описания для сформированных кластеров автоматически построенного электронного каталога.

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

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

• В части 2.7 второй главы данной работы представлено описание распределенной версии алгоритма подготовки образов текстовых документов.

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

В части 2.9 второй главы диссертации представлено описание алгоритмов тематического ранжирования, основанных на автоматически построенном электронном каталоге.

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

Программная поисковая система по ключевым словам с тематическим ранжированием, на основе автоматически построенного- электронного каталога, разработана с использованием технологий объектно-ориентированного анализа с использованием инструментов интегрированной среды разработки Eclipse и платформы для распределенных вычислений Apache Hadoop:

Разработанная программная система- состоит из четырех основных компонент:

• Компонент построения иерархической структуры каталога;

• Компонент поиска с тематическим ранжированием результатов;

• Компонент построения информационных образов документов;

• Компонент алгоритмов параллельного построения электронного каталога.

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

Результаты апробации представленных в настоящей работе параллельных версий алгоритмов индексирования и» иерархической? кластеризации по областям показали линейное ускорение в зависимости от количества задействованных вычислительных узлов. Таким образом, в результате применения используемой в настоящей работе парадигмы.распределенных вычислений1 МарКес1исе удалось существенно сократить время построения; индекса коллекции текстовых документов и проведения^ кластеризации текстовых данных.

Используя введенный критерий? оценки'качества ранжирования (КБ(1!(3@10 [30]), были проведены численные эксперименты по измерению качества работы предлагаемых алгоритмов ранжирования на коллекции научных статей журнала "Вестник Нижегородского государственного университета им. Н.И. Лобачевского", которые показали превосходство предлагаемого алгоритма ранжирования по сравнению с базовым алгоритмом Okapi ВМ25 [31].

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

Основные результаты кандидатской диссертации:

1) Разработана новая математическая модель информационного поиска с тематическим ранжированием, основанным на автоматически построенном электронном каталоге. Предложенные методы тематического ранжирования показали улучшение качества ранжирования результатов поиска от 1% до Л 5,6% по метрике NDCG@10.

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

3) Предложен новый метод текстовой кластеризации - иерархическая» кластеризация по областям текстовых документов, учитывающий недостатки существующих алгоритмов иерархической текстовой кластеризации. Разработаны последовательные и параллельные версии предложенного алгоритма. Проведенные испытания' показали преимущество в качестве предложенного алгоритма иерархической кластеризации по областям по сравнению с тремя традиционными алгоритмами кластеризации. Улучшение качества кластеризации составило от 9 % до 22% по метрике F1'.

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

5) Разработан метод автоматического выбора названия и описания для сформированных кластеров автоматически построенного электронного каталога.

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

1. Государственный рубрикатор научно-технической информации.

2. Всероссийский институт научной и технической информации. 5-е изд. - М.: ВИНИТИ, 2001.-391 с.

3. Сукиасян Э.Р. Новые таблицы Библиотечно-библиографической классификации. Организация и технология использования. Методические рекомендации. М.: Либерея, 2005. - 96 с.

4. Универсальная десятичная классификация. УДК: сокр. изд. М.: . ВИНИТИ РАН, 2006. - 148 с.

5. Агеев М.С. Автоматическая рубрикация текстов: методы и проблемы.

6. Агеев М.С., Добров Б.В., Лукашевич Н.В. // Ученые записки Казанского Государственного Университета. Серия Физико-математические науки. -2008 Том 150, книга 4 - с.25-40.

7. Добрынин В. Ю. Оценка тематического подобия текстовых документов. / В. Ю. Добрынин, В.В. Клюев, И. С. Некрестьянов

8. Электронные библиотеки: перспективные методы и технологии: Труды второй всероссийской научной конференции. Санкт-Петербург, 2000. - с. 54-62.

9. Андреев A.M. Модели и методы автоматической классификации текстовых документов. / Андреев А.М.,Березкин Д.В.,Сюзев В.В., Шабанов В.И. // Вестник МГТУ. Сер. Приборостроение. М.:Изд-во МГТУ.- 2003.- №3.

10. Т. Joachims. Transductive Inference for Text Classification using Support Vector-Machines. International Conference on Machine Learning // Proceedings of the Sixteenth International Conference on Machine Learning, 1999. p. 200 -209.

11. Sebastiani F. Machine Learning in Automated Text Categorization // ACM Computing Surveys. 2002. - Vol. 34, No. 1. - 47 p.

12. Dumais S. T. "Hierarchical classification of web content" / Dumais S. T., Chen H. //Proceedings ofSIGIR'00. 2000. p. 256-263:

13. Bennett P.N. Classification-Enhanced Ranking. / Bennett P.N., Svore K., Dumais S.T. // Proceedings of the 19th Annual International World Wide Web Conference (WWW* 10). Raleigh, NC. April 2010. P. 111-120.

14. Daoud M. Using a concept-based user context for search personalization. / Daoud M., Tamine-Lechani L., Boughanem M. Electronic resource. Access mode: ftp://ftp.irit.MMT/SIG/DaoudMariamICDMKE,08.pdf

15. Biao Xiang. Context-aware ranking in web search./ Biao Xiang, Daxin

16. Jiang, Jian Pei, Xiaohui Sun, Enhong Chen, Hang Li. // In SIGIR '10: Proceeding of the 33 rd international ACM SIGIR conference on Research and development in information retrieval (2010), pp. 451-458.

17. Open directory project. Electronic resource. Access mode: http://www.dmoz.org/

18. Пескова О. В. Разработка метода автоматического формирования рубрикатора полнотекстовых документов: Дис. . канд. техн. наук: 05.13.17. — Москва, МГТУ им. Н. Э. Баумана. 2008.

19. Tao Li. Hierarcical document classification using automatically generated hierarchy. / Tao Li, Shenghuo Zhu. // Journal of Intelligent Information Systems, V. 29, Issue 2,2007, p. 211 230.

20. The Eclipse Foundation. Electronic resource. Access mode: http://www.eclipse.org/

21. Apache Hadoop project. Electronic resource. Access mode: http://hadoop.apache.org/

22. Борисюк Ф.В. Иерархическая кластеризация по областям текстовых документов. / Борисюк Ф.В., Швецов В.И. // Материалы всероссийской конференции Технологии Майкрософт в теории и практике программирования 2009, с. 48-54.

23. Борисюк Ф.В. Параллельная реализация иерархической кластеризации« по областям текстовых документов. // Материалы всероссийской конференции Технологии Майкрософт в теории-и практике программирования 2010, с. 38-40.

24. BorisyukF.V. Adaptation of Hierarchical clustering by areas for automatic construction of electronic catalogue. / Borisyuk F.V., Shvetsov V.I. // SYRCoSE. 2010; -p. 141-145.

25. Борисюк Ф.В. Новый метод поиска на основе иерархической кластеризации по областям текстовых документов. / Борисюк Ф.В., Швецов В.И. // Вестник ННГУ им. Н.И. Лобачевского, 2009, № 4, с. 165-171.

26. Словарь по-естественным наукам. Глоссарий.ру - Электрон, дан.- -- Режим доступа: www.glossary.ru, свободный.

27. Search Engine Land industry online publication site. Electronic resource. Accessmode: http://searchengineland.com/search-illustrated-search-engine-click-thru-behavior-youve-got-to-be-in-the-top-ten-11883

28. Марков А. Концепция построения электронного архива.// Открытые системы. 1997.- №1. -с. 54-58

29. С. А. Айвазян. Прикладная статистика: Классификация и снижение размерности: Справ, изд. / С. А. Айвазян, В. М. Бухштабер, И. С. Еню-ков, JI. Д. Мешалкин; Под. ред. С. А. Айвазяна. М.: Финансы и статистика, ' 1989. - 607с.: ил.

30. Halkidi М. On Clustering Validation Techniques / M. Halkidi, V. Batistakis, M. Vazirgiannis // Journal of Intelligent Information Systems, Kluwer Academic Publishers. Manufactured in The Netherlands. 2001. - 17:2/3. - P. 107-145.

31. MacQueen J. B. Some Methods for classification and Analysis of Multivariate Observations// Proceedings of5-th Berkeley Symposium on

32. Mathematical Statistics and Probability. Berkeley, 1967. - Vol. 1. - P. 281-297.

33. Arthur D. How Slow is the k-Means Method? / Arthur D., Vassilvitskii S. // Proceedings of the twenty-second annual symposium on Computational geometry table of contents, Sedona, Arizona, USA. 2006. p. 144-153.

34. Mendes M.E.S. Dynamic Knowledge Representation for e1.arning Applications / Mendes M.E.S., Sacks L. // Proc. of the 2001 BISC International Workshop on Fuzzy Logic and the Internet, FLINT'2001. Berkeley, 2001.-P. 176-181.

35. Kohonen T. Self organization of a massive document collection

36. T. Kohonen, S. Kaski, K. Lagus, J. Salojarvi, J. Honkela, V. Paatero, A. Saarela // IEEE Transactions on neural networks. 2000. - Vol. 11, No. 3. - P. 574 - 585.

37. Ester M. A Density-Based Algorithm for Discovering Clusters in1.rge Spatial Databases with Noise / M. Ester, H.-P .Kriegel, J. Sander, X. Xu

38. Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining (KDDL96). Portland, 1996. - P. 226-231.

39. Zheng Xiao-Shen Algorithm of documents clustering based on minimum spanning tree / Zheng Xiao-Shen, He Pi-Lian, Tian Mei, Yuan Fu-Yong // International Conference on Machine Learning and Cybernetics. Xi-an, 2003.-Vol. l.-P. 199-203.

40. Manning C. D., Schutze H. Foundations of statistical natural language processing. Cambridge: MIT Press, 1999. - 620 p.

41. Zamir O. E. Clustering Web Documents: A Phrase-Based Method for Grouping-Search Engine Results Electronic resource. Electronic text and" graphic data. - 1999. - Access mode:http://turing.cs.washington:edu/papers/zamirthesis.pdf.

42. Nurminen M. ExtMiner: combining multiple ranking and-clustering algorithms for structured document retrieval / M. Nurminen, A. Honkaranta,

43. T. Karkkainen // Proceedings of Database and Expert Systems Applications, 2005. Sixteenth International Workshop on. Copenhagen, 2005. - P. 1036-1040.

44. E. Ukkonen. On-lme constoction of suffix trees. Electronic resource. . Access mode:http://citeseerx.ist.psu:edu/viewdoc/download?doi=l 0; 1.1.74.8759&rep=rep 1 &ty pe=pdf:

45. Porter M.F. An Algorithm.for Suffix Stripping, Program, 14(3). 1980. p. 130-137

46. Jl B. Lovins; Development of a stemming algorithm. Mechanical Translation and Computational Linguistics 11.- 1968; p.22-31.

47. Bekkerman R. Using Bigrams in Text Categorization. / Bèkkerman R., Allan J. Electronic resource. 2003. - Electronic text and graphic data: - Access mode: www.cs.umass.edu/~ronb/papers/bigrams.pdf.

48. Mladenic D. Word sequences as features in textlearning. / Mladenic D., Grobelnik M. // Proceedings of the 17th Electrotechnical and Computer Science Conference. Ljubljana, 1998.-P. 145-148.

49. Tan Ch.-M. The Use of Bigrams to Enhance Text Categorization /Ch.-М. Tan, Y.-F. Wang, Ch.-D. Lee// Information Processing and Management. 2002. - Vol. 38 (4). - P. 529-546.

50. Губин M.B. Исследование качества информационного поиска с использованием пар слов / Губин М. В. // Научно-техническая информация. Сер.2. 2005. - №2. - С. 13-16.

51. Peng Н.С. Feature selection based on mutual information: criteria of max-dependency, max-relevance, and min-redundancy. / Peng H.C., Long F., Ding C. // IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 27, No. 8, p. 1226-1238,2005.

52. Yang Y. A. Comparative Study on Feature Selection in Text Categorization: / Yang Y. A.,Pedersen J. O. // The Fourteenth International Conference on Machine Learning: Proceedings of ICML'97. San Francisco, 1997. - P. 412-420.

53. Luhn H.P. A statistical approach to mechanized encoding and search of library information. // IBM Journal of Research and Development. 1957. -№1.-P. 309-317.

54. Salton G. Weighting approaches in automatic textretrieval. / Salton G., Buckley C. // Information Processing and Management. -1988. Vol. 24(5). - P. 513-523.

55. The Porter stemming algorithm. Electronic resource. Access mode: http://tartarus.org/~martin/PorterStemmer/

56. Baeza-Yates R. Ribeiro-Neto B. Modern information retrieval. Reading, Massachusetts: Addison-Wesley Longman. 1999. p. 192.

57. Treeratpituk P. Automatically labeling hierarchical clusters. / Treeratpituk P., Callan J. // Proceedings of the 2006 international conference on Digital government research. 2006. P. 167-176

58. Труды РОМИП 2009. Российский семинар по оценке методов информационного поиска. Под ред. Некрестьянинова И.С. Санкт-Петербург: НУ ЦСИ. 2009. - 198 с.

59. Buckley С., Voorhees Е. Evaluating evaluation measure stability. // Proceedings of the SIGIR'00. 2000. p. 33-40.

60. А. Акт о внедрении результатов диссертации1. У'1 ВЕРЖДЛЮ» ^«УТВЕРЖДАЮ»проректор по информатизации и ' Проректор-по научной работедовузовской гюдгот овке у Г- Нижегорож^го государственногогосударственного *, ^ 'униием«^<Гим>>И1Л!обачсиского

61. З&нпепыакташ^ Н.И.Лобачевского • " • ' ' ' ( Гупбаюн С.Н.

62. Швецов в.и. ~: •; ^•„ /$* /{./О

63. АКТ о внедрении результатов диссертации «Система поиска текстовых документов на основе автоматически формируемогоэлектронного каталога»

64. Процесс внедрения проходил с 14 октября по 3 ноября 2010 г.

65. На момент подписания настоящего Акта система установлена на сервере Нижегородского университета по URL адресу http://www.unn.ru/e-library/vcslnik.html.

66. Начальник отдеда.телекоммуникаций ИНГУ ^-ЧрГ Горохов С.В.

67. Заведующий лабораторией WWW-серверов ¿C%t,fСоколова Е.И.1. Разработ'Н;1. Борискж Ф.В.