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

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

Толчеев Владимир Олегович СИСТЕМАТИЗАЦИЯ, РАЗРАБОТКА МЕТОДОВ И КОЛЛЕКТИВОВ РЕШАЮЩИХ ПРАВИЛ КЛАССИФИКАЦИИ БИБЛИОГРАФИЧЕСКИХ ТЕКСТОВЫХ ДОКУМЕНТОВ Специальность 05.13.01 – системный анализ, управление и обработка информации (энергетика, приборостроение, информатика, производственные процессы)

АВТОРЕФЕРАТ

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

Москва - 2009

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

Официальные оппоненты: доктор технических наук, профессор Орлов Александр Иванович доктор технических наук, профессор Фомичев Владимир Александрович доктор технических наук, профессор Фролов Александр Борисович

Ведущая организация: Институт проблем управления им. В.А. Трапезникова РАН

Защита состоится 8 октября 2009 г. в 16 часов в Малом актовом зале МЭИ (ТУ) на заседании диссертационного совета Д.212.157.08 при Московском энергетическом институте (техническом университете) по адресу г. Москва, ул. Красноказарменная, д.

14, МЭИ.

Отзывы в количестве двух экземпляров, заверенные и скрепленные печатью уч реждения, просим присылать по адресу: 111250, г. Москва, ул. Красноказарменная, д.

14, Ученый Совет МЭИ.

С диссертацией можно ознакомиться в библиотеке МЭИ.

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

Ученый секретарь диссертационного совета кандидат технических наук, доцент Д.Н. Анисимов

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

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

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

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

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

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

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

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

К числу важных достоинств КРП необходимо отнести следующие свойства.

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

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

3) Групповые решения легко интерпретируются, что особенно важно при приме нении КРП на практике.

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

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

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

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

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

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

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

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

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

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

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

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

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

7. Рассчитаны оценки вычислительной сложности синтезированных КРП.

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

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

Практическая ценность результатов.

1. Разработан программный комплекс (ПК) “СКАТ” (“Система Классифика ции и Анализа Текста”), реализующий полный цикл обработки и анализа библиогра фической текстовой информации. ПК “СКАТ” ориентирован на использование ши роким кругом пользователей, не имеющих специальных знаний в области теории классификации и программирования.

2. Разработанный ПК “СКАТ” позволяет пользователям получать и обраба тывать в автоматизированном режиме текстовые документы из библиографических баз данных и с Интернет-сайтов. Показано, что предложенные в диссертации мето ды, алгоритмически и программно реализованные в ПК, эффективны при обработке больших массивов библиографических текстовых данных, обладают высокой точно стью, быстродействием, не требуют существенных затрат на стадии обучения. Под тверждено, что точность классификации может быть повышена при формировании КРП с учетом обоснованных в работе рекомендаций.

3. Теоретические результаты и опыт применения ПК “СКАТ” в эксперимен тальных исследованиях обобщены в методике использования данного ПК для клас сификации библиографических документов из научных журналов, получаемых из се ти Интернет.

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

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

Реализация результатов. Разработанный ПК “СКАТ” внедрен в эксплуатацию в Федеральном государственном учреждении Научно-исследовательском институте “Рес публиканский исследовательский научно-консультационный центр экспертизы” (ФГУ НИИ РИНКЦЭ). ПК “СКАТ” был использован для автоматизированного получения с сайтов электронных издательств англоязычных публикаций по заданным научно техническим тематикам и фильтрации-классификации документального массива. Прак тическое применение разработанного программно-алгоритмического и методического обеспечения подтверждается актом о внедрении.

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

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

Разработанный учебно-исследовательский программный комплекс внедрен в учебный процесс для проведения лабораторного практикума по курсу «Интеллектуаль ные информационные системы», курсового и дипломного проектирования на кафедре Управления и информатики МЭИ, что подтверждается актом о внедрении.

Апробация работы. Материалы диссертации докладывались на одиннадцати ме ждународных конференциях “Информационные средства и технологии” (1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 гг. Москва, МЭИ), на восьми Науч ных сессиях МИФИ (2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 гг. Москва, МИФИ), на семи научно-технических семинарах “Современные технологии в задачах управле ния, автоматики и обработки информации” (2002, 2003, 2004, 2005, 2006, 2007, 2008 гг.

Алушта, МАИ).

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

Структура и объем работы. Диссертация состоит из введения, пяти глав, заклю чения, списка литературы, содержащего 284 наименований, 6 приложений. Основной текст диссертации излагается на 335 машинописных страницах, содержит 27 рисунков и 25 таблиц.

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

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

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

(M ) Т (1) (i ) X j x j,..., x j,..., x j. (1) (i ) Здесь x j – вес термина i в документе j (j=1,…,N, N – количество документов в выборке, i=1,…,M).

Выборка текстовых документов может быть представлена в виде матрицы “доку мент – термин”, строки которой представляют собой документы, а столбцы – термины, содержащиеся в этих документах. Для определения весов терминов в документах ис пользуются специальные методы взвешивания (например, tfc-взвешивание, см. форму лу (3)).

В первой главе также обосновывается применение методологии системного ана лиза для решения поставленных в диссертации задач. На основе методологии системно го анализа формируется целевой критерий (ЦК) “точность-быстродействие ресурсозатратность”, которому должны удовлетворять разрабатываемые в диссерта ции инструментальные средства. Такой критерий может быть записан в виде:

P 1 ( Z Z допуст. ),, (2) t t где P (precision) – точность системы обработки текстовых данных, t – быстродействие системы, – ошибка системы, Z – затраты на этапе обучения, Z допуст. – допустимые затраты ресурсов на этапе обучения.

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

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

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

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

“Предварительная об работка данных”, которая объединяет процедуры удаления разметки и стоп-слов, выде ления основ слов (stemming), индексирования и выявления информативных признаков, представления текстового массива в виде матрицы “документ-термин”;

“Выбор методов классификации”;

“Обучение классификаторов”;

“Оценка точности, быстродействия и затрат”.

Предложенная модель позволяет выделить наиболее важные модули с точки зре ния ЦК. К таким модулям относятся:

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

2) выбор классификаторов и их обучение;

объединение классификаторов в высо коточные, быстродействующие и малозатратные КРП.

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

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

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

N f ij log N i x (ji ), (3) N M f ij log Ni i где fij – частота слова i в документе j, N – число документов в выборке, М – число слов в выборке после удаления служебных слов и выделения корней слов, Ni – общее количе ство документов, содержащих слово i.

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

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

Во второй главе проводится обзор основных направлений исследований в об ласти разработки коллективов решающих правил. Под коллективом решающих правил в работе понимается совокупность методов классификации {J 1,..., J m }, объединенных для выработки общего решения. Сравнительный анализ различных стратегий голосования в КРП позволяет сделать вывод, что если комитет составляется из разнородных класси фикаторов, обладающих приблизительно одинаковой индивидуальной (достаточно вы сокой) точностью, то предпочтительно использовать простое голосование. В таких не однородных КРП каждый классификатор имеет равный вес при принятии решения и новое наблюдение X N 1 относится к тому классу, за который проголосовало большин ство членов КРП.

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

точность чле нов комитета известна и все решающие правила являются равноточными;

КРП состоит из нечетного количества классификаторов ( 3 m 9 ).

Определим верхнюю точностную границу комитета, который может состоять со ответственно из трех, пяти, семи или девяти методов классификации, при этом индиви дуальная точность р членов КРП меняется от 0,6 до 0,9. Результаты расчета приведены в таблице 1. Анализ полученных результатов показывает, что применение КРП на осно ве простого голосования гарантирует увеличение точности по сравнению с точностью отдельных классификаторов, членов комитета, если они являются независимыми и их индивидуальная точность p 0,5.

Таблица m3 m5 m 7 m p m p 0,6 0,648 0,682 0,710 0, p 0,7 0,784 0,837 0,874 0, p 0,8 0,896 0,942 0,966 0, p 0,9 0,972 0,991 0,997 0, Принципы проведения селекции методов для их включения в неоднородные КРП остаются одним из наименее формализованных и разработанных вопросов в теории классификации. В данной работе для отбора классификаторов в КРП используются ме ры разнородности. Проведенный автором сравнительный анализ мер разнородности по зволил выделить Q –статистику в качестве наиболее подходящей меры разнородности при синтезе неоднородных КРП на основе простого голосования.

Q –статистика показывает связь между ошибками, которые допускаются двумя решающими правилами J s и J p из коллектива. Парная Q –статистика рассчитывается по следующей формуле:

ad bc Q sp. (4) ad bc Здесь a – число раз, когда оба решающие правила J s и J p сделали правильную классификацию;

b – число раз, когда решающее правило J s сделало правильную клас сификацию, J p – неправильную;

c – число раз, когда решающее правило J p сделало правильную классификацию, J s – неправильную;

d – число раз, когда оба решающие правила J s и J p сделали неправильную классификацию.

На основе специально проведенного имитационного моделирования и экспери ментальных исследований в работе выявлен наиболее информативный диапазон изме нения меры разнородности: Q [0;

0,85]. Данный диапазон используется при отборе ме тодов для их включения в КРП.

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

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

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

Первый принцип непосредственно связан с требованием простоты модели. В простом классификаторе количество настраиваемых на этапе обучения параметров не должно превосходить трех – J {1, 2, 3 }.

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

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

O п.к. ( M ) Oк БС ( M ). (5) Здесь Oп.к. ( M ) - количество вычислительных операций, необходимых для клас сификации документа с помощью простого классификатора, Oк БС (M ) - количество вычислительных операций, необходимых для классификации документа методом к-БС.

Так, если быстродействие простого классификатора в десять раз выше быстро действия метода к-БС, то в случае объединения независимых равноточных ( p 0,7 ) простых классификаторов в комитет размером m 9 теоретически возможно достичь 90% точности при более высоком быстродействии КРП, чем у метода к-БС.

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

В данной работе к кандидатам в члены КРП предъявляются следующие требова ния:

1) средняя точность простого классификатора на различных выборках должна быть не ниже 70 % (средняя точность находится в интервале р [0,7;

0,8] ), при этом точность всех методов–претендентов на участие в комитете, соизмерима и не отличается более чем на 5 процентов;

2) средняя разнородность метода–претендента на место в комитете (по отношению к другим членам КРП), измеренная с помощью Q –статистики, должна удовлетворять не равенству Qсредняя 0,85.

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

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

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

2. Быстродействие. Быстродействие синтезируемых КРП должно быть выше бы стродействия базового классификатора (метода к-БС).

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

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

Шаг 1. Все методы, кандидаты для включения в КРП, последовательно обучаются и тестируются с использованием процедуры обучающей-тестовой выборки, проводится экспериментальный анализ точности, быстродействия и необходимых затрат на стадии обучения. Из имеющихся методов в качестве кандидатов отбираются те, которые явля ются простыми классификаторами и имеют точность в интервале p [0,7;

0,8].

Шаг 2. Для отобранных методов вычисляется мера разнородности с помощью Q –статистики. Выбираются методы, обладающие наилучшими показателями “точ ность–разнородность”, и из них формируется КРП, максимальный размер которого не превосходит семи.

Шаг 3. Проводится анализ точности, быстродействия и ресурсозатратности полу ченного комитета. Если средняя ошибка коллективного решения не уменьшается на 4% по сравнению со средней ошибкой метода к-БС, то необходимо вернуться на предыду щий шаг и увеличить размер КРП или сформировать комитет из другой комбинации разнородных методов или расширить число простых классификаторов, являющихся кандидатами для включения в комитет.

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

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

Целью алгоритма является определение области в M–мерном пространстве, в ко торую попадает новое наблюдение X N 1, и использование для классификации только тех X l (l 1,..., N l, N l N ), которые принадлежат выявленной области.

Эвристика, позволяющая осуществить поставленную цель, заключается во введе нии опорных точек (ОТ) P1,..., PS. Такие ОТ должны быть расположены на достаточ ном расстоянии друг от друга, например, являться центроидами различных классов.

Алгоритм обучения ММБС.

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

количество и расположение опорных точек (далее предполагается, что ОТ - центроиды всех классов, общее число ОТ S G ).

Выходные данные алгоритма представляются в виде упорядоченных матриц Dn ( n 1,..., S ;

S G ;

G - количество классов).

Для обучения ММБС необходимо выполнить следующие шаги.

1. Вычисление расстояний от всех документов обучающей выборки X l (l 1,..., N ) до опорных точек, получение N–мерных векторов расстояний:

d1(1) d 21) d (1) ( ( 2) ( 2) ( 2) s d1 1 ;

d2 d d ;

…;

d s d s. (6) (N ) (N ) (N ) d1 d 2 d s 2. Проведение сортировки внутри векторов d1, d 2,..., d s так, чтобы элементы (l ) (l ) (l ) располагались по возрастанию расстояния до опорных точек (от са d1, d 2,..., d s мых близких к самым дальним) и расширение векторов d1, d 2,..., d s до матриц D1, D2,..., Ds размерностью N 3. Первый добавленный столбец содержит целочис ленные значения, соответствующие исходному (до сортировки) номеру элемента;

вто рой – метки классов, к которым относятся элементы.

d ( j) Q d (1) | j | nr ) ( 2) n ( dn Q | r | dn | | d n i ) Dn ( f ), = (7) ( d n Q | f | dn | | ( m) d nN ) ( d n Q | m | где n – порядковый номер опорной точки (n 1,..., S;

S G) ;

j,r,f,m,i – порядковые но мера наблюдений в исходной выборке размера N,,,, – метки классов (,,, 1,..., G ).

Алгоритм классификации ММБС.

Входными данными алгоритма являются: новое наблюдение X N 1, заданное вектором весов терминов (или экзаменационная выборка документов, представленная в виде мат рицы “документ-термин”);

упорядоченные матрицы Dn (n 1,..., S;

S G), получен ные на стадии обучения.

Выходные данные алгоритма представляют собой метку класса, к которому отнесен но вый документ X N 1.

1. Расчет расстояний от нового наблюдения до опорных точек X N ( N 1) ( N 1) ( N 1) (l ). Поиск таких расстояний d n (l=1,..,N;

n=1,…, S ) из перво d1, d2,..., d s го столбца упорядоченных матриц D1, D2,..., Ds, которые были бы наиболее близки к ( N 1) ( N 1) ( N 1) (l 1). Определение расстояний d n, которые расположены в d1, d2,..., d s (l ) упорядоченных матрицах Dn в следующей позиции за элементами d n, т.е. справед ( N 1) d nl 1). Вычисление радиусов и приращений радиусов проводится (l ) ( ливо: d n d n по формулам:

Rn d nl 1) d nl ).

(l ) ( ( Rn d n ;

(8) 2. Определение номеров точек из второго столбца упорядоченных матриц (l ) D1, D2,..., Ds, соответствующих найденным на предыдущем шаге расстояниям d n.

Поиск общих точек, которые находятся в -области пересечения гиперколец с центра и d1 l 1), (l ) ( ми в опорных точках. Для этого анализируются точки, соответствующие d (l 1) d 2l ) и d 2l 1),…, d s и d s (l ) ( (.

3. В случае, если на предыдущем шаге обнаружить общие точки не удалось, увеличи ( l 2) d nl ) ).

( ваются приращения радиусов Rn ( Rn d n Теперь поиск общих точек производится среди расширенного числа многомерных на (l 1) (l 2 ) (l 1) (l 2 ) (l 1) (l 2 ) (l ) (l ) (l ) блюдений: d1, d1, d1 ;

d2, d2, d2 ;

..., d s, d s, ds.

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

4. На основании правила ближайшего соседа (или правила к-БС) принимается решение об отнесении нового наблюдения X N 1 к одному из классов, при этом в голосовании участвуют только те наблюдения, которые попали в общую многомерную область пересечения гиперколец.

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

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

Главной целью разработки ММБС являлось повышение быстродействия прототи па – МБС (или метода к-БС) при классификации новых наблюдений. В этой связи необ ходимо оценить количество операций, исполняемых в ММБС на стадии классификации нового наблюдения X N 1. Рассчитаем вычислительную сложность алгоритма ММБС на основе использования О-оценок.

Количество операций для расчета расстояний от нового наблюдения X N 1 до S опорных точек: O1этап. S O( M ), где O(М ) - вычислительная сложность операции классиф расчета евклидова расстояния.

Количество операций по определению расстояний в упорядоченных матрицах Dn (n 1,..., S ) :

2 этап Oклассиф. S O(log N ), где O(logN ) - вычислительная сложность операции двоичного поиска.

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

общее OММБС(классиф.) O1этап. Oклассиф. S O(M ) S O(log N ).

2этап (9) классиф На стадии обучения общая вычислительная сложность алгоритма ММБС включа ет расчет расстояний до ОТ (вычислительная сложность S O(NM ) ) и проведение сор тировки (вычислительная сложность S O( N log N ) ):

общее OММБС(обучения) S O(NM ) S O( N log N ). (10) Известно, что количество операций, необходимое для классификации нового на общее блюдения в методе ближайшего соседа, равно ОМБС (классиф.) ( NM ) N O( M ). Тогда общее общее S N OММБС (классиф.) OМБС (классиф.), так как в формуле (9) и O(log N ) O(NM ).

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

Таким образом, решение в ММБС не всегда принимается исходя из анализа бли жайших соседей. Используя понятие, введенное в литературе по непараметрическим ме тодам классификации, можно назвать точки, лежащие внутри гипермногогранника, но не принадлежащие гиперсфере, аппроксимированными ближайшими соседями. Наблю апр дение X является аппроксимированным соседом для X N 1, если справедливо нера венство:

d ( X *, X N 1 ) d ( X апр, X N 1 ) 1 d ( X *, X N 1 ). (11) Здесь X * - ближайший сосед для X N 1, - положительная малая величина.

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

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

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

( d к d j ) ( d к d1 ), d j d j (1 )(d к d1 ). (12), d j d В уточненной формуле взвешивания к–й сосед имеет вес, который определяется значением коэффициента взвешивания :

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

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

После чего выполняется дополнительные шаги.

Дополнительные шаги для алгоритма классификации ОМБС.

4. Для выявленных на предыдущем шаге точек, попавших в общую область, рассчитываются расстояния до классифицируемого наблюдения X N 1. Найденные рас стояния d1БС,..., d к сортируются по возрастанию. С целью определения весов для БС попавших в общую область точек применяется уточненная формула линейного взвеши вания (см. формулу (12)).

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

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

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

Так, в ОМБС добавляется по сравнению с ММБС дополнительный третий этап, включающий расчет расстояний от к точек, попавших в общую область, их сорти ровку и последующее взвешивание:

Oклассиф. к O( M ) O(к log к ) к (3О (2) 2О * (2) 2О (2) О ** (2)). (14) 3этап Здесь O(2) - вычислительная сложность элементарных операций (сложение, ум ножение, сравнение и т.п.), которые не зависят от размера входных данных.

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

общее OОМБС (классиф.) O1этап. Oклассиф. Оклассиф.

2 этап 3этап классиф S O(M ) S O(logN ) к O(M ) O(к log к) к (3О (2) 2О * (2) 2О (2) О ** (2)) (S к) O(M ). (15) В (15) учтено, что О(log N ) O(M ), O(к log к) O(M ) и O(2) O(M ).

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

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

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

В диссертации рассматриваются принципы построения профилей классов на ос нове использования трех подходов: 2 – статистики;

Q - статистики;

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

Разработанные процедуры получили названия метода 2 –профилей, метода Q – профилей и метода MI–профилей (MI сокращение от Mutual Information – взаимная ин формация). В этих алгоритмах на этапе обучения проводится выявление наиболее ин формативных терминов для каждого класса на основе применения - статистики, Q статистики или улучшенного критерия взаимной информации. Затем полученный профиль ( Q – профиль или MI-профиль) используется для проведения классификации новых наблюдений.

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

( AD BC ) ( x, Qg ) N 2 (i ). (16) ( A B)(C D)( A C )(B D) В формуле (16) использованы следующие обозначения: А – число раз, когда тер мин x (i ) и класс Q g встречаются вместе;

В – число раз, когда x (i ) встречается без Q g ;

C – число раз, когда Q g встречается без x (i ) ;

D – число раз, когда Q g и x (i ) не встре чаются;

N – общее количество документов в выборке.

Величина Q – статистики во введенных выше обозначениях может быть рассчи AD BC Q ( x (i ), Q g ) тана по формуле:. (17) AD BC В данной работе предлагается улучшенный критерий взаимной информации. В предлагаемом критерии параметр A в числителе формулы известного в литературе кри терия взаимной информации возводится в степень r:

Ar N.

MI ( x, Q g ) log r (i ) (18) A B A C Возведение в степень параметра А позволяет существенно увеличить значение взаимной информации для высокочастотных терминов и скомпенсировать основной недостаток классического алгоритма по заниженному взвешиванию наиболее информа тивных терминов.

В предложенных процедурах на этапе обучения проводится выявление информа тивных терминов и составление профилей для каждого класса на основе расчета весов терминов с помощью 2 –статистики, Q – статистики или улучшенного критерия вза имной информации. После чего составляется матрица профилей классов – Р. Столбцы матрицы сортируются в порядке убывания значений весов. Единственным управляю щим параметром для всех трех методов является пороговое значение Т, которое опре деляет длину профиля классов M g (предполагается, что все классы имеют одинаковую длину профиля M 1 M 2,..., M G ).

На этапе классификации рассчитываются значения весов классов g, которые представляют собой “информационные суммы”, соответствующие каждому классу. Рас чет весов классов проводится по формуле:

Mg g tf i ( x (i ), Q g ), (19) i где ( x (i ), Qg ) рассчитывается по одной из формул (16)-(18), tf i – частота встречаемо сти i–го термина в классифицируемом документе, M g – количество наиболее информа тивных терминов, включенных в профиль g–го класса.

Решающее правило в методе 2 –профилей, методе Q – профилей и методе MI– профилей одинаково и имеет вид: классифицируемый документ X N 1 относится к тому классу, которому соответствует наибольшая сумма весов ( X N 1 Q g, если g max, для g, g 1,..., G ).

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

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

O общее общее общее ОQ профиль(классиф.) OMI профиль( классиф.) профиль( классиф.) (20) (O * (2) О (2))] [(G O1 O2 [G M g 1) O(2)].

где O1 - количество операций, необходимых для определения весов классов 1,…, G, O2 - количество операций сравнений, необходимых для определения наи большего веса класса.

Сравнение вычислительной сложности профильных методов с вычислительной сложностью наивного байесовского метода и метода центроидов показывает, что ме тоды 2 –профилей, Q – профилей и MI–профилей имеют практически такое же быст родействие, как наивный байесовский метод, который является одним из наиболее ско ростных среди известных классификаторов. При этом быстродействие методов 2 – профилей, Q – профилей и MI–профилей выше быстродействия МЦ.

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

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

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

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

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

организации процесса обучения и тестирования решающих правил;

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

настройки их параметров;

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

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

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

расчету мер разнородности для кандидатов в члены КРП;

формированию КРП с заданными свойствами из числа отобранных простых классификаторов;

сопоставлению точности и быстродействия коллективных и индивидуальных методов;

выявлению зависимости точности и быстродействия КРП от количества членов комитета, размера и структуры выборки.

В данной работе использовались коллекции текстовых документов из библио графической базы данных (БД) Compendex (COMPuterized ENgineering inDEX), цифро вой библиотеки (ЦБ) ResearchIndex и цифровой библиотеки ACM (Association for Com puting Machinery - Ассоциация по вычислительной технике). Все вышеназванные ЦБ и БД имеют встроенный экспертно составленный рубрикатор, что позволяет избежать субъективизма и предвзятости при формировании обучающих и экзаменационных вы борок.

Основные эксперименты проводились на девяти выборках одинаковой структуры (по три выборки из БД Compendex, ЦБ ResearchIndex, ЦБ ACM). Каждая обучающая вы борка состояла из 700 библиографических документов, распределенных по семи клас сам, в классах содержалось одинаковое число текстов. Каждая экзаменационная выбор ка содержала по 140 документов (по двадцать документов в классе). Сформированные обучающие и экзаменационные выборки, использованные автором при проведении ис следований, доступны на сайте кафедры Управления и информатики МЭИ (http://uii.mpei.ru).

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

В результате проведенных исследований были определены следующие настройки параметров для методов, используемых в работе: для метода к-БС количество ближай ших соседей к = 29;

для ММБС: к=23, количество опорных точек равно количеству цен троидов классов S=7;

для ОМБС: к=23, S=7, коэффициент взвешивания =0,21;

для ме тода 2 –профилей пороговое значение Т=50, для метода Q–профилей и метода MI– профилей Т=75 (r=3). Метод центроидов и наивный байесовский метод не имеют на страиваемых параметров.

После настройки параметров методов был проведен сравнительный анализ их ошибок и быстродействия. Быстродействие оценивалось путем расчета процессорного времени выполнения операций (CPU-time). CPU-time измеряется в милисекундах и яв ляется специфической характеристикой конкретного компьютера, используемого для проведения расчетов. В данной работе измерения проводились на процессоре Pentium (3.0 Ггц и 1Гб ОЗУ).

Таблица Метод \ Характеристики Средняя ошибка Среднее быстродействие (мсек) МЦ 0,212 1, НБМ 0,29 0, ММБС 0,259 15, ОМБС 0,248 22, 0,252 0, MI-проф.

0,256 0, Q-проф.

Хи-проф. 0,226 0, Метод к-БС 0,255 147, Полученные экспериментальные результаты хорошо согласуются с теоретиче скими оценками вычислительной сложности и подтверждают, что все методы, разрабо танные в работе для классификации текстовых документов обладают высоким быстро действием, которое в разы превосходит быстродействие метода к-БС (при этом быстро действие разработанных профильных методов выше быстродействия высокоскоростно го метода центроидов). В то же время предложенные методы обладают достаточно вы сокой точностью, соизмеримой с точностью “классических” классификаторов (метода к БС и МЦ).

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

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

На основе вышеизложенной процедуры синтеза КРП на основе простых классифи каторов было синтезировано два новых комитета классификаторов: КРП -1, состоящий из метода 2 -профилей, МЦ и ОМБС;

КРП -2, состоящий из метода 2 -профилей, МЦ, метода MI–профилей, ММБС, ОМБС.

Сравнительный анализ характеристик синтезированных КРП и известных инди видуальных классификаторов также проводился на девяти выборках. В таблице 3 при ведены полученные на выборках ошибки, рассчитана средняя ошибка ( ) и размах ( ).

В качестве базовых классификаторов для сопоставления использовались МЦ и метод к БС.

Таблица Выборка \ Ошибка МЦ Метод к-БС КРП-1 КРП- метода В1 0,192 0,271 0,114 0, В2 0,214 0,293 0,207 0, В3 0,3 0,3 0,214 0, В4 0,064 0,135 0,1 0, В5 0,121 0,15 0,107 0, В6 0,121 0,171 0,114 0, В7 0,3 0,335 0,278 0, В8 0,307 0,343 0,293 0, В9 0,293 0,3 0,278 0, МЦ 0,212 к БС 0,255 КРП 1 0,189 КРП 2 0, Средняя ошибка 0,193 0, 0, 0, и размах Приведенные в таблице 3 результаты свидетельствуют о том, что синтезирован ные КРП обеспечивают более высокую точность и устойчивость к выборочным измене ниям в сопоставлении с базовыми классификаторами. При этом сформированные коми теты обладают большим быстродействием, чем метод к-БС.

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

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

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

ПК “СКАТ” (“Система Классификации и Анализа Текста”) ориентирован, преж де всего, на автоматизированный мониторинг тематических ресурсов Интернет и про ведение фильтрации-классификации получаемой информации в соответствии с профес сиональными потребностями пользователя. Кроме того, он предоставляет возможность построения моделей предметных областей, проведения наукометрического анализа и выявления из документального потока фрагментов значимой для специалиста предметника информации.

УИПК (“Учебно-исследовательский программный комплекс”) позволяет решать две взаимосвязанные проблемы. Во-первых, УИПК является важной составляющей учебного процесса на кафедре Управления и информатики МЭИ и на его основе реали зован лабораторный практикум по курсу «Интеллектуальные информационные систе мы». Во-вторых, он позволяет студентам (магистрам, аспирантам, инженерам, препода вателям кафедры) осуществлять самостоятельные полномасштабные исследования про цедур обработки и анализа библиографических текстовых документов в рамках курсо вого проектирования, квалификационных и научно-исследовательских работ, а также проводить разработку дополнительных модулей, расширяющих функциональные воз можности УИПК. Алгоритмическую основу УИПК составляют разработанные автором методы классификации и синтезируемые из них КРП.

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

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

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

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

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

Разработанная процедура была использована для автоматизации системы инфор мационного обеспечения научно-технической деятельности в ряде организаций: Рес публиканском исследовательском научно-консультационном центре экспертизы (РИНКЦЭ), кафедре Микросистемной техники МИРЭА, кафедре Управления и инфор матики МЭИ. Мониторинг тематических изданий и фильтрация-классификация публи каций были проведены с помощью ПК “СКАТ”. На основе анализа результатов эксплуа тации и экспертных оценок специалистов, представляющих организации-заказчики, был сделан вывод об эффективности практического использования разработанных в работе индивидуальных и коллективных методов для обработки и анализа массивов научных библиографических документов.

Разработанные в диссертации инструментальные средства были использованы для обработки и анализа базы данных научных публикаций Института проблем химиче ской физики РАН (ИПХФ РАН, г.Черноголовка). Анализ включал проведение следую щих исследований: выделение из массива научных публикаций наиболее активных уче ных и формирующихся вокруг них групп соавторов;

установление связи между продук тивностью и соавторством;

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

отслеживание изменения тематик работ с течением времени. Результаты проведенных исследований, предоставленные для экспертного анализа, получили высо кую оценку специалистов ИПХФ РАН, а выявленные закономерности нашли практиче ское применение при организации процесса планирования и управления НИОКР.

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

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

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

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

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

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

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

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

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

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

5. В работе с позиций предложенного ЦК рассмотрены имеющиеся комитеты классификаторов, проведен сравнительный анализ стратегий принятия решений в КРП.

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

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

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

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

8. Получены оценки количества вычислительных операций, необходимых для классификации текстовых документов с помощью разработанных методов (ММБС и ОМБС) и показано, что они требуют меньшего количества вычислительных операций по сравнению с прототипом (методом к-ближайших соседей). Также показано, что быстро действие метода MI–профилей, метода 2 –профилей и метода Q –профилей значитель но выше, чем у известных эвристических процедур (в частности метода центроидов и метода к-ближайших соседей).

9. На основе предложенной автором процедуры синтезированы и исследованы высокоточные, быстродействующие и малозатратные КРП, сформированные из простых классификаторов и состоящие из трех и пяти членов. Обосновано включение в комитеты методов, ряд из которых разработан лично автором. Впервые получены КРП-1, состоя щий из метода 2 -профилей, метода центроидов, обобщенного метода ближайшего со и КРП-2, включающий метод 2 -профилей, метод центроидов, метод MI– седа, профилей, модифицированный метод ближайшего соседа и обобщенный метод бли жайшего соседа. На выборках из библиографических текстовых документов показано, что синтезированные КРП обеспечивают более высокую точность и устойчивость по сравнению с методом к-БС и методом центроидов, а также обладают более высоким быстродействием в сопоставлении с методом к-БС.

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

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

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

Основные публикации по теме работы 1. Толчеев В.О. Разработка и исследование новых модификаций метода ближайшего соседа. Приложение к журналу «Информационные технологии», №3, 2005, с. 1-32.

2. Толчеев В.О. Современные методы обработки и анализа текстовой информации.

Учебное пособие. М.: Изд-во МЭИ, 2006 – 75с.

3. Толчеев В.О. Синтез коллективов решающих правил для проведения классифи кации текстовых документов. Информационные технологии, №10, 2007, с. –32 38.

4. Толчеев В.О. Комплексный подход к классификации текстовых документов. Ав томатизация и современные технологии, №8, 2005, с. 39-45.

5. Толчеев В.О. Анализ точностных характеристик модифицированного метода ближайшего соседа. Информационные технологии, №4, 2006, с. 52-58.

6. Толчеев В.О. Модели и методы классификации текстовой информации. Ин формационные технологии, №5, 2004, с. 6-14.

7. Толчеев В.О. Методы выявления информативных признаков в задаче классифи кации текстовых документов. Информационные технологии, №8, 2005, с. 14-21.

8. Толчеев В.О. Взвешенные и редуцированные методы ближайшего соседа. Вест ник МЭИ, №5, 2005, с. 84-90.

9. Толчеев В.О. Обзор методов классификации текстовых документов. Автомати зация и современные технологии, №10, 2005, с. 28-33.

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

Вестник МЭИ, №1, 2004, стр. 76-81.

11. Мальцев П.П., Стяжкин В.Б., Толчеев В.О. Об опыте использования методики выявления тематических журналов. Информационные технологии, №7, 2007, с.

65-71.

12. Некрасов И.В., Толчеев В.О. Построение модели представления библиографиче ского документа. Информационные технологии, №11, 2005, с. 57-63.

13. Некрасов И.В., Толчеев В.О. Современные средства поиска, обработки и анализа текстовой информации. Вестник МЭИ, №1, 2002, стр. 52-55.

14. Толчеев В.О. Функциональные возможности и области применения интеллек туальных агентов и многоагентных систем. Микросистемная техника, №4, 2002, с. 10-15.

15. Толчеев В.О. О новых подходах к разработке сложных интеллектуальных сис тем. Микросистемная техника, №2, 2002, с. 24-28.

16. Колосов О.С., Анисимов Д.Н., Толчеев В.О., Ягодкина Т.В., Гришин В.И., Спи ридонов Д.К. Итоги работ в области идентификации на кафедре управления и информатики МЭИ. Приборы и системы, №8, 2001, с. 22-29.

17. Толчеев В.О. Методика синтеза коллективов решающих правил на основе “про стых” классификаторов. Международная конференция Информационные средства и технологии. Том 2. МЭИ. Изд-во «Станкин», 2006, стр. 150-154.

18. Толчеев В.О. Формирование быстродействующих коллективов решающих правил.

Международная конференция “Современные технологии в задачах управления, ав томатики и обработки информации”. Алушта. Изд-во МИФИ, 2006, с. 338.

19. Толчеев В.О. Расчет верхней точностной границы для коллективов решающих пра вил, использующих простое голосование. Международная конференция “Современ ные технологии в задачах управления, автоматики и обработки информации”. Алуш та. Изд-во Тульского государственного университета, 2007, с. 282-283.

20. Толчеев В.О. Исследование зависимости между точностью и разнородностью в коллективах решающих правил с помощью имитационного моделирования. Между народная конференция “Информационные средства и технологии” том 2. МЭИ. Изд во «Станкин», 2007, с. 91-93.

21. Толчеев В.О. Обобщенный метод ближайшего соседа. Международная конферен ция “Информационные средства и технологии” том 2. МЭИ. Изд-во «Станкин», 2005, стр. 183-185.

22. Кокорев П.В., Толчеев В.О. Улучшенный критерий взаимной информации для клас сификации текстовых документов. Международная конференция “Современные технологии в задачах управления, автоматики и обработки информации”. Алушта.

Изд-во СГАУ, 2005, с. 293.

23. Кокорев П.В., Толчеев В.О. Разработка метода 2 -профилей для классификации текстовых документов. Международная конференция “Современные технологии в задачах управления, автоматики и обработки информации”. Алушта. Изд-во МИФИ, 2006, с. 309.

24. Толчеев В.О. Профильные методы классификации библиографических документов.

Международная конференция “Современные технологии в задачах управления, ав томатики и обработки информации”. Алушта. Изд-во СПб. ГУАП, 2008, с.264-265.

25. Толчеев В.О. Методика выявления периодических изданий, наиболее значимых для специалистов. Международная конференция “Информационные средства и техноло гии” том 1. МЭИ. Изд-во «Станкин», 1999, с. 187-190.

26. Толчеев В.О. О проведении классификации текстовых документов по их заголовкам.

Международная конференция “Современные технологии в задачах управления, ав томатики и обработки информации”. Алушта. Изд-во МГАПИ, 2002, с. 88-89.

27. Бородкин А.А., Толчеев В.О. Исследование влияния структуры выборки и процедур предварительной обработки на точность классификации текстовой информации.

Международная конференция “Информационные средства и технологии”. Том 2.

МЭИ. Изд-во Станкин, 2007, с. 33-34.

28. Бородкин А.А., Толчеев В.О. Об оценке точностных и временных характеристик методов классификации библиографических текстовых документов. Научная сессия МИФИ 2008. Том 11. М. МИФИ, 2008, стр. 152-153.

29. Некрасов И.В., Толчеев В.О. Разработка программного комплекса для классифика ции текстовых документов. Международная конференция “Информационные сред ства и технологии” том 2. МЭИ. Изд-во «Станкин», 2002, с. 160-163.

30. Бородкин А.А., Толчеев В.О. Структура и функциональные возможности учебно исследовательского программного комплекса. Международная конференция “Ин формационные средства и технологии” том 3. МЭИ. Изд-во «Станкин», 2008, с.85 87.

31. Кульга Д.В., Толчеев В.О., Филимонов Н.Б. Построение и анализ терминологическо го портрета журнала «Информационные технологии». Международная конферен ция “Информационные средства и технологии” том 3. МЭИ. Изд-во «Станкин», 2008, с. 104-105.

32. Некрасов И.В., Толчеев В.О. Экспериментальные исследования методов класси фикации текстовых документов. Научная сессия МИФИ 2005. М. МИФИ, 2005, стр. 152-153.

33. Зенкина Ю.И., Толчеев В.О. Разработка программного комплекса для отбора те матических изданий и публикаций в области информатики. Алушта. Изд-во Туль ского государственного университета, 2007, с. 256-257.

34. Некрасов И.В., Толчеев В.О. Информационно-поисковая система для обработки на учно-технической информации. Международная конференция “Информационные средства и технологии” том 1. МЭИ. Изд-во «Станкин», 2001, с. 114-117.