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

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

00317 1046

ПЕСКОВА ОЛЬГА ВАДИМОВНА

РАЗРАБОТКА МЕТОДА АВТОМАТИЧЕСКОГО ФОРМИРОВАНИЯ РУБРИКАТОРА ПОЛНОТЕКСТОВЫХ ДОКУМЕНТОВ

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

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

С/ ч

Москва - 2008

2 5

О

003171046

Работа выполнена в Московском государственном техническом университете им Н Э Баумана

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

Трусов Борис Георгиевич

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

Эрлих Александр Игоревич кандидат технических наук, доцент Цицин Алексей Георгиевич

Ведущая организация Всероссийский Институт Научной и

Технической Информации

Защита диссертации состоится «,/6» (иШиЛ 200 2_ года на заседании диссертационного совета Д 212 141 10 в Московском государственном техническом университете им Н Э Баумана по адресу 105005, Москва, 2-я Бауманская ул, д 5

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

Автореферат разослан <&0 » СММЛ 200 8_ г

Ученый секретарь

диссертационного совета Д 212 141 10 к т н, доцент ^ / CP Иванов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы.

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

Традиционными подходами к решению проблемы поиска информации в коллекциях полнотекстовых документов, являются поиск по ключевым словам (а) и классификационный поиск (б) В настоящей работе наиболее перспективным считается второй подход Эффективность поиска по ключевым словам существенно зависит от удачного описания информационных потребностей в форме запроса на естественном языке В противоположность этому классификационный поиск благодаря интуитивно понятному навигационному интерфейсу позволяет легко формулировать и уточнять информационные потребности, что повышает эффективность и удобство поиска документов Однако, традиционные механизмы классификационного поиска - универсальные библиотечные классификаторы (УДК, ГРНТИ, ББК) и специализированные предметные рубрикаторы, имеющие фиксированную структуру, не успевают изменяться вслед за темпом развития науки и техники или требуют высоких затрат как на адаптацию классификаторов, так и на классификацию по ним документов

Современные методы классификационного поиска основаны на механизме автоматической классификации текстов Данный подход, как правило, подразумевает применение методов категоризации, которые распределяют документы по предопределенному набору рубрик на основе знания, полученного из обучающего множества Разработке и тестированию алгоритмов данного вида, а также связанным с ними алгоритмам представления текстов посвящены труды таких авторов как М С Агеев, И Е Кураленок, И С Некрестьянов, В И Шабанов, Т Joachims, D D Lewis, R Е Schapire, Н Schutze, F Sebastiam, Y Yang, I Dagan, S T Dumais и ряда других Однако данный подход решает не все проблемы традиционного классификационного поиска вопрос регулярной актуализации предметных областей классификаторов и связанных с ней затрат решается путем

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

Таким образом, в настоящее время существует потребность в разработке методов классификации, которые способны на основе анализа текстов и внутренних связей между ними автоматически строить рубрикаторы коллекций полнотекстовых документов Среди известных методов автоматического анализа текстовых данных потенциально способных решить представленную проблему следует выделить методы кластеризации, которые автоматически разбивают документы на группы (кластеры) на основе анализа тематической близости между ними Разработке алгоритмов данного вида и способов оценки качества получаемого разбиения документов, а также связанным с ними алгоритмам представления текстов посвящены труды таких авторов как Д В Ландэ, М В Киселев, К М Кириченко, С J van Rijsbergen, G Saltón, D Manning, H Schutze, T Kohonen, О Eli Zamir, J С Bezdek, M Halkidi и ряда других Однако в большинстве работ разбиение документов на тематические группы рассматривается как промежуточный этап при формировании некоторого представления о составе анализируемых текстовых данных, не ставится задача формирования рубрикатора политематических коллекций в виде, близком к традиционному, способном служить механизмом классификационного поиска для конечного пользователя Более того, требование применимости метода классификации к различным политематическим коллекциям вызывает необходимость разработки подхода к формированию представления документов при условии отсутствия специализированной априорной информации

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

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

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

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

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

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

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

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

При разработке программного обеспечения применялись методы объектно-ориентированного программирования с использованием сред разработки Microsoft Visual Studio NET 2003 и СУБД Microsoft SQL Server 2000

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

В результате выполнения работы получены новые научные результаты

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

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

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

информационно-поисковые образы, что позволило повысить качество и скорость выполнения кластеризации множества текстов

На защиту выносятся:

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

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

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

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

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

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

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

Разработанный программный комплекс внедрен и используется в рамках единой Автоматизированной Библиотечной Информационной Системы МГТУ им Н Э Баумана Предложенные методы и алгоритмы применяются в подсистеме поддержки фонда электронных документов

Основные результаты работы докладывались и обсуждались на Всероссийских конференциях студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования» (Москва, 2005 и 2006 гг), 14-ой Международной конференции «Крым 2007' библиотеки и информационные ресурсы в современном мире науки,

культуры, образования и бизнеса» (Судак, 2007 г), 7-ой Международной конференции «НТИ-2007 информационное общество, интеллектуальная обработка информации, информационные технологии» (Москва, 2007 г)

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

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, выводов и списка литературы из 132 наименований Диссертация изложена на 150 страницах, содержит 46 рисунков и 12 таблиц

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность проблемы создания методов и средств классификации полнотекстовых документов в электронных хранилищах, сформулирована цель исследования и разработки метода автоматического формирования рубрикатора коллекции полнотекстовых документов в условиях отсутствия априорных сведений о предметных областях документов

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

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

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

Выходными данными задачи кластеризации является набор кластеров документов Выбор алгоритма кластеризации обусловлен его видом, поскольку производимый набор кластеров служит основой для формирования рубрикатора Рубрикатор предложено отображать в виде графа тематических групп (кластеров) документов, ребра которого отражают как иерархические, так и родственные связи между ними Глубина иерархии кластеров не более 2-3 уровней Кластерам присваивается автоматически полученное вербальное описание, состоящее из краткого названия и списка ключевых слов Такой способ организации рубрикатора документов выбран на основе опыта реализации и эксплуатации подсистемы систематизации АБИС МГТУ им Н Э Баумана

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

Во второй главе описан предлагаемый подход к автоматическому формированию рубрикатора документов Основные этапы автоматического формирования рубрикатора коллекции полнотекстовых документов включают (рис 1)

• формирование информационно-поисковых образов полных текстов документов,

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

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

выявление родственных связей между кластерами одного и того же уровня путём вычисления мер близости между их представителями; добавление при необходимости «родственного» ребра в граф рубрикатора.

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

Параметры! алгоритма

формирования образов ... ..........

доку^нтов , . . ...

I Модифицированный

'алгоритм послойной кластеризации

Коллекция неклассифицированных * поямотекстовых документов

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

А1

А "•4

/ > Система ¡классификации

признаков из документов: » отображение документов в пространство их признаков;

• предлагаемая редукция пространства признаков документов.

родственных 1 ■. между кластерами; 1 • формирование вербального ; описания вершин графа ] рубрикатора 1

Параметры алгоритма кластеризации документов

Пара ^етры алго|»итма

Кластеризация образов документов

А2

классификации

преобр« набора >

Кластеры .документов и отношения еду ними

кования ласгеров

Информационно-

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

Преобразование множества кластеров в рубрикатор коллекции документов

Коллекция классифици-: рованных полнотекстовых документов

ы*> Рубрикатор

J коллекции юлнотекстовых документов

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

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

Существенными характеристиками пространства признаков текстов

являются их высокая размерность (Л?/> может достигать десятков тысяч даже для не больших коллекций текстов) и связанная с ней недостаточно выразительная ориентация векторов-образов в пространстве признаков, что приводит не только к высоким вычислительным затратам, но и к низкому качеству разбиения на кластеры Анализ такой ситуации стал обоснованием необходимости разработки алгоритма редукции исходного пространства признаков

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

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

которого соответствуют документам Ребра, соединяющие вершины V, и v], имеют длину равную значению меры близости между образами г-ого и у-ого

документов ¿'""М.^,) (О < < 1) Тогда при экспериментально

подобранной входной последовательности пороговых значений мер близости между документами 1 = 4 > ч > >»»+1 =0 алгоритм кластеризации определяет последовательность подграфов графа близости сСсГ1, где С=(У,Е') и Е'=\еуеЕ г,™"^

G°-(F,0) и Qm+1 = q Алгоритм послойной кластеризации выделяет компоненты связности подграфа G', получая таким образом разбиение

коллекции документов (pi» ), называемое кластеризацией на уровне

_sim

lt В результате на выходе алгоритма получается т вложенных разбиении

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

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

F = F +F (1)

exler inter ^ ,

где Fexter - обобщенный внешний критерий качества кластеризации, F,„,er - обобщенный внутренний критерий качества кластеризации, t - время выполнения алгоритма кластеризации (без вычисления матрицы близости

документов), - условная величина, показывающая количество

документов, классифицируемых за секунду

Fexter = Fi-мера - Е, (2)

где F/-Mepa - это объединяющий показатель полноты и точности системы информационного поиска, Е - погрешность классификации

FMer=\CPCC\ + DI-DB + ^-+I, (3)

D

где СРСС - кофенетический коэффициент корреляции, DI - индекс Дана, DB - мера Дейвиса-Булдина, СН - индекс Калинского и Гарабача, I -/-индекс

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

В третьей главе описана структура программного комплекса (рис 2), реализующего алгоритм формирования образов документов, алгоритм

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

Пользовательский интерфейс системы

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

Оценка кластеризации документов

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

Компонент вычисления внешних мер качества разбиения

данных (при условии наличия

«эталонногов разбиения данных)

Программные

Г" Формирование информационно* поисковых образов документов

компоненты системы

Г Кластеризация

Г Формирование рубрикатора коллекции! документов и способа I его отображения

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

Компонент формирования графического отображения графа рубрикатора

Форми(

К0ЛЛ1 I

полноте докум ц

ование кцим (СТОВЫХ I

нтов

Компонент формирования коллекции текстов (из файлов форматов PDF, Word и простого текста)и сохранения информации об «эталонном» разбиении данных

Компонент управления хранимыми данными

Хранилище да шых системы

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

аюв-И №

Рис. 2. Структура программного комплекса

С помощью разработанной системы экспериментально исследован предлагаемый подход к кластеризации полнотекстовых документов Тестовыми данными являлись русскоязычные документы он-лайн библиотеки по информационным технологиям CITFORUM (http //www citforum ги) от 23 02 2006, содержащей 1572 разнородных с точки зрения размера и содержательного уровня документов Основными направлениями проведенного исследования являлись

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

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

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

• исследование процесса формирования вербальных описаний

10

кластеров коллекции документов.

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

В процессе испытания способа формирования образов документов, применяющего предложенный алгоритм редукции пространства признаков, проведён анализ его влияния на качество кластеризации этих образов. Данный анализ показал, что применение разработанного алгоритма редукции, во-первых, заметно сократило количество признаков (в 3,5 раза) и связей типа «документ-признак» (в 5,7 раз), что привело к существенному увеличению скорости кластеризации. Во-вторых, позволило повысить качество кластеризации текстов, что подтверждается оценкой значений внутренних и внешних мер качества разбиения документов. Для рассмотренной коллекции документов (случайной выборки 200 документов из коллекции библиотеки СПТОЛиМ) количественная оценка качества кластеризации повысилась почти в 11 раз с применением предложенного алгоритма редукции пространства признаков (рис. 3). Тот факт, что при заметном сокращении признаков получен рост значений мер качества разбиения документов позволил сделать вывод, что из документов были удалены именно невыразительные для их тематик признаки. Что подтвердило верность предположения, положенного в основу разработки алгоритма избирательной редукции.

Способ формирования образов документов:

1 - без редукции признаков;

2-е принудительной редукцией признаков;

3-е принудительной и избирательной редукцией признаков.

ьЫ

йн.

,5 я Е о о.

* о £ о ю 2-8-го о О ■& я

п Н

3,000 2,000 1,000 0,000

3,789

1,589

0,345

Ни

1

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

В результате испытания модифицированного алгоритма послойной кластеризации подобрана последовательность пороговых значений мер близости документов {ТГ; ТГ} и проведена оценка его эффективности в сравнении с результатами кластеризации с использованием: иерархического агломеративного алгоритма и исходного алгоритма послойной кластеризации

(С. А. Айвазян). Анализ значений обобщающего показателя эффективности алгоритма кластеризации ^ показал, что предлагаемый подход почти в 2,5 раза эффективнее, чем традиционный иерархический подход к кластеризации, и в 1,6 раза эффективнее исходного подхода послойной кластеризации применительно к выбранной тестовой коллекции полнотекстовых документов (рис. 4).

5 --

,5 га а о о.

ю г--8-га о

О -в- ¡5

о 5

2,66

1,77 1

4,25

Алгоритм кластеризации документов:

1 - иерархический агломеративный алгоритм;

2 - алгоритм послойной кластеризации (С. Айвазян);

3 - модифицированный алгоритм послойной кластеризации.

1

Рис. 4. Сравнительная оценка эффективности алгоритмов кластеризации

Анализ каждой составляющей, учтённой в обобщающем показателе эффективности алгоритма кластеризации F, показал, что:

• затраты времени на выполнение модифицированного алгоритма послойной кластеризации / оказалась в 2 раза ниже, чем у исходного алгоритма, и в 20 раз ниже, чем у иерархического алгоритма (рис. 5).

14000

- 12000

г я 5 10000

0£=Г с^го "Я

, Р 5 6000

8000

п- ц ф

2га£ а> а Ш

га

4000 2000 0

1 2503

1216 624

Алгоритм кластеризации документов:

1 - иерархический агломеративный алгоритм;

2 - алгоритм послойной кластеризации (С. Айвазян);

3 - модифицированный алгоритм послойной кластеризации.

1 2 3

Рис. 5. Сравнительная оценка времени выполнения алгоритма кластеризации / (с) для коллекции из 1572 разнородных документов

• по критерию Ршег заметное преимущество показал предложенный алгоритм - модифицированный алгоритм послойной кластеризации.

по критерию Ре>Лег получены незначительные различия качества кластеризации всеми тремя алгоритмами. Заметим, что критерии данного типа носят субъективный характер особенно для документов с нечётко очерченной тематикой.

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

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

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

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

На рис 6 представлен пример интерфейса навигации по выборке из коллекции документов библиотеки С1ТР01ШМ с помощью автоматически построенного рубрикатора коллекции_

^Навигации каллекции документе« с пмнцы« детвмятически л*стр*енн«г« руб»ик«т«р*

Назвонив кластера. 1Сети

Ключевые слова.

смш

кабел коммутатор концентра гор сет. лес, кабепьн.. сетев порт трафик, ETHERNET скс адаптер кедр станц. сегмент.коаксиальн маршрутизатор устройств соединен UTP волоконно-оптическ. подключен хаб прокладк офис, FDDI коммутац. оборудован коммутацион вит ток АТМ.розвтк. трос тополог., телефон канал оптическ пакет VLAN кольц. маршрутизац пропуски протокол монитор

'.„оос

rf-Fn,

Заглавие документе

Интеллектуальный мониторинг

Волокно в микротраншее

Волокно на весу

Волокно на весу-2

Коммунальный UTP

Оптимизация 1Р-трафика

Витая пара- все ли так просто?!

Коммутаторы FasVGigabit Ethernet для 'большой' се

Обнаружение несанкционированных подключена

Регуляторы трафика

Gigabit как стандарт корпоративной сети

Нестандартные решения для локальных сетей мал

Локальная сеть для офиса

ПРАВИЛА ОБЪЕДИНЕНИЯ РАБОЧИХ ГРУПП

ПРАВИЛА ПРОЕКТИРОВАНИЯ ЛВС РАБОЧЕЙ ГРУ

Рекомендации, выработанные практикой

Соединение двух или болев ПК

Высокоскоростные ЛВС

Коммутация ЛВС

Архитектура виртуальных сетей AutoTracker Практическое руководство по сетям Plug and-Play ППКПЛЬМЫР ГРТИ ЛПЯ НЛЧИНЯН1И1И* (нп ппимрпя I ANlTJ

<1 t_±г

Родственные кластеры

I Мера близости

Стандарта(волокон,коннектор оптическ разъем сварк.волокн наконечник, соединител LC MT-R 01179039731 lp-станции (ALCATEL IP телефон электрическ. Мбит, SIEMENS VERTICAL электросет широкополосн 01764134818

<]_I 2J

Рис. 6. Пример интерфейса навигации по выборке из коллекции документов с помощью автоматически построенного рубрикатора (выбрана рубрика «Сети»)

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

на электронных ресурсах библиотеки МГТУим Н Э Баумана - коллекции полных текстов авторефератов диссертаций Коллекция авторефератов насчитывала 234 документа научно-технической направленности, общим объемом 18,14 МБ простого текста Оценка качества ее кластеризации выполнена путем вычисления погрешности классификации по сравнению с

• индексом УДК, присвоенным авторами авторефератов диссертации В этом случае погрешность автоматической классификации составила 3,2%,

• областью знания по номенклатуре ВАК, по которой планировалась защита диссертации В этом случае погрешность составила 13,6%, что объясняется тематическим перекрытием укрупненных направлений, по которым осуществляется подготовка и защита диссертаций

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

5) Экспериментально подтверждена эффективность предложенных алгоритмов формирования образов документов и их кластеризации Формирование образов документов с применением предложенного алгоритма редукции привело на тестовой коллекции к увеличению в 11 раз значения критерия эффективности кластеризации по сравнению с формированием образов без использования механизма редукции Кластеризация документов с применением модифицированного алгоритма послойной кластеризации привела к увеличению критерия эффективности кластеризации в 2,5 раза по сравнению с кластеризацией на основе традиционного иерархического алгоритма

6) Итоговая проверка метода на политематической коллекции из 234 авторефератов диссертаций показала, что автоматическая классификация документов привела к погрешности в 3,2% по сравнению с классификацией по УДК каждого автореферата диссертации

РАБОТЫ ПО ТЕМЕ ДИССЕРТАЦИИ

1) Автоматизированная библиотечно-информационная система технического университета / А Е Шиваров, Г В Абрамов, О В Пескова, Н А Белостоцкий // Вестник МГТУ им Н Э Баумана Приборостроение - 2007 -№4 - С 21-32

2) Пескова О В Автоматизация работы с классификаторами документов библиотеки МГТУ им Н Э Баумана // Культура народов Причерноморья -2004 -Т 2, №48 - С 38-41

3) Пескова О В Автоматическая классификация электронных текстовых документов с применением механизма обратной связи // Технологии Microsoft в теории и практике программирования Труды всероссийской конференции студентов, аспирантов и молодых ученых -Москва, 2005 - С 54-55

4) Пескова О В Автоматическое формирование рубрикатора полнотекстовых документов //НТИ-2007 Материалы 7-ой международной конференции - Москва, 2007 - С 241-242

5) Пескова О В Автоматическое формирование тематической схемы коллекции документов // Технологии Microsoft в теории и практике программирования Труды всероссийской конференции студентов, аспирантов и молодых ученых - Москва, 2006 - С 66-68

6) Пескова О В Исследование и разработка метода автоматического анализа документов для формирования индексов УДК //Информатика и системы управления в XXI веке Сборник трудов молодых ученых, аспирантов и студентов МГТУ им Н Э Баумана — 2005 - №3 - С 90-92

7) Пескова О В Классификация документов в электронных библиотеках [Электронный ресурс] / О В Пескова // Крым 2007 Библиотеки и информационные ресурсы в современном мире науки, культуры, образования и бизнеса Материалы 14-ой Международной конференции -Судак, 2007 - Режим доступа

http //www gpntb ru/win/inter-events/crimea2007/cd/proceeding html, свободный

8) Пескова О В Методы автоматической классификации текстовых электронных документов // Научно-техническая информация Сер 2 - 2006 -№3 - С 13-20

9) Пескова О В Методы автоматической классификации электронных текстовых документов без обучения // Научно-техническая информация Сер 2 -2006 -№ 12 - С 21-32

10) Свидетельство об официальной регистрации программы для ЭВМ №2007610196 Автоматизированная библиотечно-информационная система «Яуза» / А Е Шиваров, Г В Абрамов, Н А Белостоцкий, О В Пескова -Москва, 2007 - 1с

11) Свидетельство об официальной регистрации программы для ЭВМ №2007614766 Информационная система автоматического формирования рубрикатора коллекции полнотекстовых документов «Авторубрикатор» /О В Пескова -Москва,2007 - 1с

Подписано к печати 16 05 08 Заказ № 295 Объем 1,0 печ л Тираж 100 экз Типография МГТУ им Н Э Баумана 105005, Москва, 2-я Бауманская ул , д 5 263-62-01

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

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

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

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

1.4. Задача формирования информационно-поисковых образов полнотекстовых документов.

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

Выводы по разделу 1.

2. Метод автоматического формирования рубрикатора полнотекстовых документов.

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

2.2. Кластеризация информационно-поисковых образов документов.

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

2.4. Оценка алгоритма кластеризации коллекции документов

Выводы по разделу 2.

3. Программная реализация метода автоматического формирования рубрикатора документов и его исследования.

3.1. Структура программного комплекса.

3.2. Исследование предлагаемого метода на основе испытаний программной системы.

3.3. Оценка эмпирических значений параметров формирования информационно-поисковых образов и их влияния на алгоритм кластеризации.

3.4. Исследование процесса формирования вербальных описаний кластеров коллекции документов.

3.5. Испытание способа формирования образов документов с применением предложенного алгоритма редукции пространства признаков.

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

3.7. Выводы по разделу 3.

4. Испытание системы автоматического формирования рубрикатора полнотекстовых документов.

4.1. Описание тестовой коллекции текстов.

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

Выводы.

В связи с наблюдаемым на протяжении последних десятилетий стремительным ростом объёмов хранилищ электронных документов особое значение приобретает разработка программных средств поиска информации. Одним из видов электронных документов являются документы, содержащие тексты на естественном языке, или полнотекстовые документы. Множество полнотекстовых документов, доступное через средства телекоммуникационного доступа для поиска, извлечения и доставки пользователю, называют коллекцией полнотекстовых документов. Частным случаем коллекции полнотекстовых документов является полнотекстовая электронная библиотека, документы которой снабжены корректным библиографическим описанием [54]. Приведём примеры коллекций полнотекстовых документов, носящих научную и техническую направленность, а таюке находящихся в свободном доступе в глобальной сети Интернет: а) полнотекстовые электронные библиотеки такие, как «Научная электронная библиотека eLroRARY.RU» [35], «Открытая Русская Электронная Библиотека» [37] и др. Электронные библиотеки в большинстве случаев являются одним из фондов традиционных библиотек, стремящихся соответствовать современным требованиям обслуживания читателей. Так «Открытая Русская Электронная Библиотека» появилась как фонд электронных документов Российской Государственной библиотеки [50]. б) научные и технические журналы, предоставляющие читателям доступ к полным текстам опубликованных статей такие, как «В мире науки» [34] и «Открытые системы» [38]. в) общедоступные коллекции технических материалов аналитического, обзорного или новостного характера, соответствующие одному тематическому направлению, объединённые с образовательной целью, такие, как коллекция русскоязычных статей, книг, руководств по информационным технологиям CITFORUM [65] и электронная библиотека «Наука и техника» [64].

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

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

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

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

Во-вторых, современный темп роста объемов коллекций документов, позволяет утверждать, что даже в тех ситуациях, когда пользователь воспользовался, поиском по запросу или другим способом сузил область поиска документов, например, отфильтровав коллекцию документов по дате создания, возникает проблема выбора требуемых документов, поскольку часто объём выборокходержит сотни документов. Например, в коллекциях [35, 38, 65] по запросу «кластер» поисковые машины, имеющиеся на соответствующих Веб-сайтах, отобрали 2450, 2283 и 809 документов соответственно. Очевидно, что читатель не сможет просмотреть все найденные документы, и вероятно, так и не найдёт нужные документы. Решить эту проблему способна система классификации документов -полученной выборки. Если документы выборки представлять в виде набора тематических групп, на которые разбиваются, например, релевантные, запросу документы, то пользователь сможет легко выбрать интересующую-его область. Заметим, что ответ поисковой машины из предыдущего примера содержал документы из различных предметных областей, таких как системы управления и информационные технологии, организация производства, экономика и социология, неорганическая химия, прикладная механика и техническая физика, зоология, сельское хозяйство и т. д.

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

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

Поисковые качества системы классификации зависят от вида классификационной схемы коллекции документов. В электронных полнотекстовых библиотеках часто по традиции применяют универсальные библиотечные классификаторы - УДК [59], ББК [58], ГРНТИ [16]. Например^ в научной электронной библиотеке eLIBRARY.RU [35] применяется ГРНТИ, в Открытой Русской Электронной Библиотеке [37] -ББК. В большинстве полнотекстовых коллекций, зародившихся в сети Интернет, используются собственные предметные рубрикаторы как, например, в коллекции документов CITFORUM [65].

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

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

При современном темпе роста объемов информационных массивов, нетрудно представить, какими чрезмерно трудоёмкими процессами будут как классификация всего фонда электронных документов вручную, так- и построение собственного рубрикатора для заданного множества документов -вручную. Помочь в решении данной проблемы способны программные средства, выполняющие автоматическую классификацию. В последнее время стало возможным воплощение идеи автоматической классификации документов по ряду причин. Во-первых, речь идёт о полнотекстовых документах, которые могут быть представлены в виде, пригодном для автоматического анализа с помощью программных средств. Во-вторых, к настоящему моменту в научном сообществе накопился достаточно большой опыт исследования и разработки таких систем. Причём интерес к данной проблеме среди исследователей систем поиска в коллекциях текстов в локальных или глобальных сетях не только не угасает, но в последние два десятилетия является повышенным [51, 120, 104]. Это в первую очередь вызвано скачком в развитии программно-аппаратной базы, которая стала пригодной для тестирования разработанных ранее математических методов автоматической классификации.

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

1) Классификация полнотекстовых документов с обучением, или категоризация документов: документы классифицируются по предопределенному рубрикатору на основании знаний о том, какими признаками должны обладать документы, относящиеся к той или иной рубрике. Разработке и тестированию алгоритмов категоризации документов, а также связанным с ними алгоритмам представления текстов посвящены труды таких авторов как Агеев М., Кураленок И., Некрестьянов И. С., Шабанов В.И., Joachims Т., Lewis D. D., Schapire R. Е., Schutze Н., Sebastiani F., Yang Y., Dagan I., Dumais S.T. и ряда других. I

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

Ландэ Д. В., Киселев М. В., Кириченко К. М., Rijsbergen С. J., Salton. G., t

Manning D., Schutze H., Kohonen Т., Zamir O. Eli, Bezdek J. C., Halkidi M. и ряда других.

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

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

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

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

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

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

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

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

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

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

• предложен новый метод автоматического формирования рубрикатора коллекции полнотекстовых документов, применимый для произвольных массивов научно-технических документов без ограничений на их объём и тематику, в условиях отсутствия специализированной априорной информации для формализации их содержания;

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

Практическая значимость работы заключается в применении разработанного в диссертации метода и программной системы в электронных библиотеках^ в качестве элемента их поисковых систем. Предложенный подход к автоматической"; классификации дркументов позволяет решать проблему навигации как по полной коллекции документов; так. и> по. её подмножествам, динамически? формируя для? каждого случая наиболее подходящий: предметный рубрикатор; отражающий иерархические и родственные связи между областями знаний и обладающий автоматически получаемыми вербальными описаниями этих, областей знаний! Такой элемент поисковой системы способен выполнять функции как самостоятельного поискового аппарата; так и служить средством повышения качества работы других поисковых механизмов.

Разработанный программный комплекс внедрен и используется в рамках единой Автоматизированной Библиотечной^ Информационной! Системы МГТУ им. Н.Э. Баумана [1, 52]. Предложенные методы и алгоритмы- применяются в подсистеме поддержки фонда электронных документов.

Основные результаты работы докладывались и обсуждались на Всероссийских конференциях студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования» (Москва, 2005 и 2006 гг.), 14-ой Международной конференции «Крым 2007: библиотеки и информационные ресурсы в современном мире науки, культуры, образования и бизнеса» (Судак, 2007 г.), 7-ой Международной конференции «НТИ-2007: информационное общество, интеллектуальная обработка информации, информационные технологии» (Москва, 2007 г.).

По теме диссертации опубликовано 9 печатных работ и 2 свидетельства об официальной регистрации программы для ЭВМ," в том числе одна статья в журнале, входящем в перечень ведущих рецензируемых научных журналов и изданий.

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

Выводы

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

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

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

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

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

6) Итоговая проверка метода на политематической коллекции из 234 авторефератов диссертаций показала, что автоматическая классификация документов привела к погрешности в 3,2% по сравнению с классификацией по УДК каждого автореферата диссертации.

1. Автоматизированная библиотечно-информационная система технического университета / А. Е. Шиваров, Г. В. Абрамов, О. В. Пескова, Н. А. Белостоцкий // Вестник МГТУ им. Н.Э. Баумана. Приборостроение. -2007,-№4.-С. 21-32.

2. Авторефераты диссертаций. [Электронный ресурс] / Казанский государственный технический университет им. А. Н. Туполева. Электрон, дан. - Казань. - Режим доступа: http://www.kstu-kai.ru/science/dissertations/, свободный.

3. Авторефераты диссертаций. [Электронный ресурс] / Санкт-Петербургский государственный горный институт. Электрон, дан. - Спб. -Режим доступа: http://www.spmi.ru/skeleton/l/912, свободный.

4. Авторефераты диссертаций. [Электронный ресурс] / Санкт-Петербургского университета телекоммуникаций им. проф. А. М. Бонч-Бруевича. Электрон. дан. - СПб. - Режим доступа: http://www.sut.ru/science/dissertationboard/dissertationboard.html, свободный.

5. Авторефераты диссертаций. [Электронный ресурс] /Московский государственный технологический универсистет СТАНКИН. Электрон. дан. - М. - Режим доступа: http://www.stankin.ru/sciense/kandiddis.html, свободный.

6. Авторефераты диссертаций. [Электронный ресурс] / Тульский государственный универсистет. Электрон, дан. - Тула. - Режим доступа: http://www.tsu.tula.ru/disser/index.php?pageno=7&all=10&archive=l, свободный.

7. Авторефераты диссертаций. [Электронный ресурс] /Московский авиационный институт. Электрон, дан. - М. - Режимдоступа: http://www.mai.ru/science/thesis.htm, свободный.

8. Авторефераты диссертаций. [Электронный ресурс] / Уфимский государственный авиационный технический университет. Электрон, дан. — Уфа. — Режим доступа: http://www.ugatu.ac.ru/science/dissov/kl/05.13 Л 1/index.php, свободный.

9. Агеев М.С. Официальные метрики РОМИП'2004 / М.С. Агеев, И.Е Кураленок // Российский семинар по Оценке Методов Информационного Поиска (РОМИП 2004) Пущино, 2004.

10. Алгоритм выделения псевдооснов Мартина Портера. [Электронный ресурс]. Электрон. дан. - Режим доступа: г http://snowball.sourceforge.net, свободный.

11. Банк данных ВИНИТИ: состояние и перспективы развития / Ю. М. Арский, Т. М. Леонтьева, И. Ю. Никольская, А. Н. Шогин. -Москва, 2006.-241 с.

12. Браславский П. И. Автоматические операции с запросами к машинам поиска интернета на основе тезауруса: подходы и оценки Электронный ресурс. Электрон, текст, дан. - Режим доступа: http://www.dialog-21.ru/Archive/2004/Braslavskij.htm, свободный.

13. Воройский Ф.С. Основы проектирования автоматизирования библиотечно-информационных систем: Монография. М.: Физматлит, 2002. - 384 с.

14. Григорьев А.Н. Многоуровневый классификатор-навигатор по откликам информационно-поисковой системы / А. Н. Григорьев,

15. Д. В. Ландэ // Компьютерная лингвистика и интеллектуальные технологии: труды международной конференции Диалог'2006 М.: Наука, 2006. - С. 329-331.

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

17. Губин М. В. Модели и методы представления текстового документа в системах информационного поиска / М. В. Губин // Научно-техническая информация. Сер. 1. 2004. - №12. - С. 12-24.

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

19. Гусарова JI. Проверка обоснованности кластерного решения / JI. Гусарова, И. Яцкив // Reliability and statistics in transportation' and communication (RelStat'03). Рига, 2004. - Т. 5, №2. - C.49-56.

20. Гусев В.Д. Алгоритм выявления устойчивых словосочетаний с учетом их вариативности (морфологической и комбинаторной) / В.Д. Гусев, Н.В. Саломатина // Труды международной конференции Диалог'2004. М.: Наука, 2004. - С. 530-535.

21. Джонс М. Т. Программирование искусственного интеллекта в приложениях / М. Тим Джонс; Пер. с англ. Осипов А. И. М.: ДМК Пресс, 2004.-312 е.: ил.

22. Дрейпер Н., Смит Г. Прикладной регрессионный анализ: В 2-х кн. / Пер. с англ. 2-е изд., перераб. и доп. - М.: Финансы и статистика, 1986 - Кн. 1. — 366с., ил. (Математико-статистические методы за рубежом).

23. Дубров А. М. Обработка статистических данных методом главных компонент. -М.: Статистика, 1978. 135 е.: ил.

24. Елисеева И. И., Рукавишников В. О. Группировка, корреляция, распознавание образов (Статистические методы классификации и измерения связей). -М.: Статистика, 1977. 144 е.: ил.

25. Кириченко К.М Обзор методов кластеризации текстовой информации Электронный ресурс. / К. М. Кириченко, М. Б. Герасимов-Электрон. текст, дан. 2001. - Режим доступа: http://www.dialog-21.ru/Archive/2001/volume2/226.htm, свободный.

26. Коваленко А. Вероятностный морфологический анализатор русского и украинского языков Электронный ресурс. / А. Коваленко.

27. Электрон. текст. дан. — Режим доступа:http://linguist.nm.ru/stemka/stemka.html, свободный.

28. Максаков А. Оценка эффективности масштабируемых алгоритмов классификации текстов / А. Максаков // Труды четвертого российского семинара РОМИП'2006. Пущино, 2006. - С. 92-100.

29. Математическая статистика: Учеб. для вузов / В. Б. Горяинов, И. В. Павлов, Г. М. Цветкова и др.; Под ред. С. В. Зарубина, А. П. Крищенко. -2-е издание, стереотип. М.: Изд-во МГТУ им. Н. Э. Баумана, 2002. - 424 с.

30. Научная электронная библиотека eLIBRARY.RU. Электронный ресурс. Электрон, дан. - М., 2008 - . - Режим доступа: http://elibrary.ru.

31. И. С. Некрестьянов Тематико-ориентированные методы информационного поиска: Дис. . канд. физ.-мат. наук: 05.13.11. СПб. -2000.

32. Открытая Русская Электронная Библиотека Электронный ресурс. Электрон, дан. - М. : Рос. гос. б-ка, 1999- . - Режим доступа: http://orel.rsl.ru, свободный.

33. Открытые системы Электронный ресурс.: многопредмет. науч. журн. Электрон, журн. - М. - Режим доступа: http://www.osp.ru/os/,свободный.

34. Пескова О. В. Автоматизация работы- с классификаторами документов библиотеки МГТУ им. Н. Э. Баумана / Or В. Пескова // Культура народов Причерноморья. 2004. - Т. 2, № 48. - С. 38-41.

35. Пескова О. В. Методы автоматической классификации текстовых электронных документов / О. В. Пескова // Научно-техническая информация. Сер. 2. 2006. - №3. - С. 13-20.

36. Пескова О. В. Методы автоматической классификации электронных текстовых документов без обучения7 О. В. Пескова // Научно-техническая информация. Сер. 2. 2006. - № 12. - С. 21-32.

37. Пескова О. В. Автоматическое формирование рубрикатора полнотекстовых документов / О. В. Пескова // НТИ-2007: Материалы 7-ой международной конференции. Москва, 2007. - С. 241-242.

38. Прикладная статистика: Исследование зависимостей: Справ, изд. / С. А. Айвазян, И. С. Енюков, Л. Д. Мешалкин; Под. ред. С. А. Айвазяна. М.: Финансы и статистика, 1985. - 487с.: ил.

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

40. Просиз Дж. Программирование для Microsoft .NET: Пер. с 'англ. -М.: Издательско-торговый дом «Русская редакция», 2003. 704 е.: ил.

41. Российская государственная библиотека Электронный ресурс. / Центр информ. технологий РГБ ; ред. Власенко Т.В. ; Web-мастер Козлова Н.В. Электрон, дан. - М. : Рос. гос. б-ка, 1997 - . - Режим доступа: http://www.rsl.ru, свободный.

42. Российский семинар по Оценке Методов Информационного поиска. Труды второго российского семинара РОМИП'2004. Пущино, 2004.-214с.

43. Свидетельство об официальной регистрации программы для ЭВМ №2007610196. Автоматизированная библиотечно-информационная система «Яуза» / А. Е. Шиваров, Г. В. Абрамов, Н. А. Белостоцкий, О. В. Пескова. Москва, 2007. - 1с.

44. Свидетельство об официальной регистрации программы для

45. ЭВМ №2007614766. Информационная система автоматического формирования рубрикатора коллекции полнотекстовых документов «Авторубрикатор» / О. В. Пескова- Москва, 2007. 1с.

46. Солтон Дж. Динамические библиотечно-информационные системы. Пер. с англ. - М.: Мир, 1979. - 558 с.

47. Справочник по вычислительным методам статистики / Пер. с англ. В. С. Занадворова; Под. ред. и с предисл. Е. М. Четыркина. М.: Финансы и статистика, 1982 - 344 е., ил.

48. Стариков А. Самоорганизующиеся карты Электронный ресурс. Электрон. текст. дан. - 2000. - Режим доступа: http://www.basegroup.ru/neural/som.htm, свободный.

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

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

51. Шабанов В.И. Модели и методы автоматической классификациитекстовых документов: Дис. . канд. техн. наук: 05.13.11. М., 2003. - 227с.

52. Шрайберг Я. Л Современные тенденции развития библиотечно-информационных технологий // Крым-2001: Междунар. конф. Судак, 2001. -Т. 1.-С. 9-12.

53. Шрайберг Я.Л., Воройский Ф.С. Автоматизированныебиблиотечно-информационные системы России: состояние, выбор, внедрение, развитие. М.: Либерея, 1996. - 271 с.

54. Штовба С. Д. Введение в теорию нечетких множеств и нечеткую логику Электронный ресурс. — Электрон, текст, дан. Режим доступа: http://matlab.exponenta.ru/fuzzylogic/bookl/index.php, свободный.

55. Электронная библиотека «Наука и техника» Электронный ресурс. Электрон, дан. - Режим доступа: http://n-t.ru, свободный.

56. Электронная библиотека технической литературы по информационным технологиям CITFORUM. [Электронный ресурс]., -Электрон, текст, и граф. дан. Режим доступа: http://www.citforum.ru, свободный.

57. Aizawa A. Linguistic Techniques to Improve the Performance of Automatic Text Categorization Electronic resource. 2001. - Electronic text and graphic data. - Access - mode: research.nii.ac.jp/~akiko/papers/NLPRS2001Aizawa.pdf.

58. Apte C., Weiss S.M. Data Mining with Decision Trees and Decision Rules Electronic resource. 1997. - Electronic text and graphic data. - Access mode: citeseer.ist.psu.edu/apte97data.html.

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

60. Berger A. L. A Maximum Entropy Approach to Natural Language Processing / A. L. Berger, S. A.Delia Pietra, V. J. Delia Pietra // Computational Linguistics. 1996. - Vol. 22, Num. 1 - P. 39-71.

61. Wall M. E. Singular value decomposition and principal component analysis / M. E. Wall, A.Rechtsteiner, L. M. Rocha // A Practical Approach to Microarray Data Analysis. Kluwer, 2003. - P. 91-109.

62. Bezdek J. С., Pal N. R. Some New Indexes of Cluster Validity //IEEE Transactions On Systems, Man And Cybernetics. 1998. - Vol. 28, No. 3.-P. 301-315.

63. Boutin F., Hascoet M. Cluster Validity Indices for Graph Partitioning // Proceedings of the Eight International Conference on Information Visualization (IV'04). IEEE-2004.

64. Cristianini N. Latent Semantic Kernels / N. Cristianini, J. Shawe-Taylor, H. Lodhi // Journal of Intelligent Information Systems. 2002. - Vol. 18(2-3).-P. 127-152.

65. Dagan I. Mistakedriven learning in text categorization / I. Dagan, Y. Karov, D. Roth // Proceedings of EMNLP-97, 2nd Conference on Empirical Methods in Natural Language Processing. Providence , 1997. - P. 55-63.

66. Dempster A. P. Maximum likelihood from incomplete data via the EM algorithm / A. P. Dempster, N. M. Laird, D. B. Rubin // Journal of the Royal Statistical Society. Series В (Methodological). 1977. - Vol.39, No. 1. - P. 1-38.

67. Dittenbach M. Uncovering hierarchical structure in data using the growing hierarchical self-organizing map / M. Dittenbach, A. Rauber, D. Merkl //Neurocomputing. 2002. - Vol. 48. - P. 199-216.

68. Freeman R. Т., Yin H. Adaptive topological tree structure for document organisation and visualisation // Neural Networks. Elsevier Science Ltd. Vol. 17. - 1255-1271. - 2004.

69. Guo D., Berry M. W. Knowledge-Enhanced' Latent Semantic Indexing // Information Retrieval. 2003 - Vol. 6. - P. 225-250.

70. Halkidi M. 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.

71. Jain A. K. Data Clustering: A Review / A. K. Jain, M. N. Murty, P. J. Flynn // ACM Computing Surveys. 1999. - Vol. 31, No. 3. - P. 264-323.

72. Joachims T. Text categorization with support vector machines: learning with many relevant features // In Proceedings of ECML-98, 10th European Conference on Machine Learning. Chemnitz, 1998. - P. 137-142.

73. Jones K. S. A Statistical Interpretation of Term Specificity and Its Application in Retrieval // Journal of Documentation. 1972. - № 2(34). - P. 8793.

74. Kanade P.M., Hall L. O. Fuzzy Ants as a Clustering Concept // 22nd international conference of the North American fuzzy information processingsociety NAFIPS. Chicago, 2003. - P. 227-232.

75. Kaski S. Data exploration using self-organizing maps // Acta Polytechnica Scandinavica, Mathematics, Computing and Management in Engineering Series. 1997. -No.82. - P. 57.

76. Kelledy F., Smeaton A.F. Automatic Phrase Recognition and Extraction from Text // Proceedings of the 19th Annual BCS-IRSG Colloquium on IR Research. Aberdeen, 1997. - P. 493 - 496.

77. Khan M. S., Khor S. W. Web document clustering1 using a hybrid neural network // Applied Soft Computing. 2004. - Vol. 4. - P. 423-432.

78. Ко Y. Improving text categorization using the importance of sentences / Y. Ко, J. Park, J. Seo // Information Processing and Management. -2004.-Vol. 40.-P. 65-79.

79. Kohonen T. Self organization of a massive document collection / 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.

80. Kuo-Lung W., Miin-Shen Y. A cluster validity index for fuzzy clustering // Pattern Recognition Letters. 2005. - Vol. 26. - P. 1275-1291.

81. Kural Y. Deciphering clusters representations / Y. Kural, S. Robertson, S. Jones // Information Processing and Management. 2001. - Vol. 37.-P. 593-601.

82. Lam B. S. Y., Yan H. A new cluster validity index for data with merged clusters and different densities // Systems, Man and Cybernetics: IEEE1.ternational Conference. 2005. - Vol. 1. - P. 798-803.

83. Lampos C. Archiving the Greek Web / C. Lampos, M. Eirinaki, D. Jevtuchova, M. Vazirgianni // Proceedings of 4th International Web Archiving Workshop (IWAW04). Bath, UK, 2004. - P.

84. Landauer Т. K. Introduction to Latent Semantic Analysis /Т.К. Landauer, P. W. Foltz, D. Laham // Discourse Processes. 1998. - Vol. 25.-P. 259-284.

85. Lewis D. D. Naive (Bayes) at Forty: The Independence Assumption in Information Retrieval И Lecture Notes In Computer Science: Proceedings of the 10th European Conference on Machine Learning. 1998. - Vol. 1398. - P. 415.

86. Liu J., Chua T.-S. Building Semantic Perceptron Net forf-Topic Spotting // Proceedings of the 39th Annual Meeting of the Association for Computational Linguistics. Toulouse, 2001. - P. 434-441.

87. 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.

88. MacQueen J. B. Some Methods for classification and Analysis of Multivariate Observations // Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley, 1967. - Vol. 1. - P. 281-297.

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

90. Massey L. Evaluating quality of text clustering with ART1

91. Proceedings of the International Joint Conference on Neural Networks. -Portland, 2003. Vol. 2. - P. 1402-1407.

92. Maulik U., Bandyopadhyay S. Performance Evaluation of Some Clustering Algorithms and Validity Indices // IEEE Transactions On Pattern Analysis And Machine Intelligence. 2002. - Vol. 24, No. 12. - P. 1650 - 1654.

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

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

95. Moyotl-Hernandez E., Jimenez-Salazar H. An Analysis on Frequency of Terms for Text Categorization // Procesamiento del lenguaje natural. 2004. -Vol. 33.-P. 141-146.

96. Moyotl-Hernandez E., Jimenez-Salazar H. Some Tests in Text Categorization using Term Selection by DTP // Proceedings of the Fifth Mexican International Conference on Computer Science ENC'04. Colima, 2004. - P. 161-167.

97. Ontrup J., Ritter H. Large-scale data exploration with the hierarchically growing hyperbolic SOM // Neural Networks. 2006. - Vol. 19. -P. 751-761.

98. Pakhira M. K., Bandyopadhyay S., Maulik U. A study of some fuzzy cluster validity indices, genetic clustering and application to pixel classification

99. М. К. Pakhira, S. Bandyopadhyay, U. Maulik // Fuzzy Sets and Systems. -2005. Vol. 155.-P. 191-214.

100. Roussinov D., Zhao J. L. Automatic discovery of similarity relationships through Web mining // Decision Support Systems. 2003. - Vol. 35.-P. 149-166.

101. Salton G. Term-weighting approaches in automatic text retrieval: Technical Report / G. Salton, C. Buckley New York: Cornell University, 1987. -lip.

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

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

104. Siolas G., d'Alche Buc F. Support vector machines based on semantic kernel for text categorization // International Joint Conference on Neural Networks: Proceedings of IEEE. Istanbul, 2000. - Vol.5. - P. 205-209.

105. Sinka M. P., Corneb D. W. The BankSearch web document dataset:investigating unsupervised clustering and category similarity // Journal of Network and Computer Applications. 2004. - Vol. 28. - P. 129-146.

106. Stein B. On Cluster Validity and the Information Need of Users / B. Stein, S. M. zu Eissen, F. WiBbrock // 3rd IASTED Int. Conference on Artificial Intelligence and Applications: Proceedings of AIA 03. Benalmadena, 2003.-P. 216-221.

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

108. Torra V. Exploration of textual document archives using a fuzzy hierarchical clustering algorithm in the GAMBAL system / V. Torra, S. Miyamoto, S. Lanau // Information Processing and Management. 2005. - Vol. 41. -P.587-598.

109. Tsekouras G. E. On the use of the weighted fuzzy c-means in'fuzzy modeling // Advances in Engineering Software. 2005. - Vol. 36. - P. 287-300.

110. Weigend A. S. Exploiting Hierarchy in Text Categorization // Information Retrieval. 1999. - Vol. 1. - P. 193-216.

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

112. WordNet Electronic resource. Electronic text data. - Access mode: http://wordnet.princeton.edu.

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

114. Zamir О. E. Clustering Web Documents: A Phrase-Based Method for

115. Grouping Search Engine Results Electronic resource. Electronic text and graphic data. - 1999. - Access mode:http://turing.cs.washington.edu/papers/zamirthesis.pdf.

116. 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.

117. Использование подсистемы позволило повысить качество поисковых средств электронного каталога библиотеки.

118. Председатель комиссии: Члены комиссии:

119. Агеева Т.И.) (Колобаев Л.И.) (Симончик Л. П.)