Авторефераты по всем темам >>
Авторефераты по техническим специальностям
На правах рукописи
Толчеев Владимир Олегович
СИСТЕМАТИЗАЦИЯ, РАЗРАБОТКА МЕТОДОВ И КОЛЛЕКТИВОВ РЕШАЮЩИХ ПРАВИЛ КЛАССИФИКАЦИИ БИБЛИОГРАФИЧЕСКИХ ТЕКСТОВЫХ ДОКУМЕНТОВ
Специальность 05.13.01 - системный анализ, управление и обработка информации (энергетика, приборостроение, информатика, производственные процессы)
АВТОРЕФЕРАТ
диссертации на соискание ученой степени доктора технических наук
Москва - 2009
Работа выполнена на кафедре Управления и информатики Московского энергетического института (технического университета).
Официальные оппоненты: доктор технических наук, профессор Орлов Александр Иванович доктор технических наук, профессор Фомичев Владимир Александрович доктор технических наук, профессор Фролов Александр Борисович
Ведущая организация: Институт проблем управления им. В.А. Трапезникова РАН
Защита состоится 8 октября 2009 г. в 16 часов в Малом актовом зале МЭИ (ТУ) на заседании диссертационного совета Д.212.157.08 при Московском энергетическом институте (техническом университете) по адресу г. Москва, ул. Красноказарменная, д.
14, МЭИ.
Отзывы в количестве двух экземпляров, заверенные и скрепленные печатью учреждения, просим присылать по адресу: 111250, г. Москва, ул. Красноказарменная, д.
14, Ученый Совет МЭИ.
С диссертацией можно ознакомиться в библиотеке МЭИ.
Автореферат разослан У____Ф ___________ 2009 г.
Ученый секретарь диссертационного совета кандидат технических наук, доцент Д.Н. Анисимов
Общая характеристика работы
Актуальность темы. Для современного этапа развития общества характерна информатизация всех сфер деятельности, в результате которой текстовые данные в электронном виде превратились в ресурс, во многом определяющий научно-технический и экономический потенциал государства. По оценкам экспертов, в настоящее время около 70% накопленной и используемой обществом цифровой информации находится в неструктурированной (текстовой) форме.
В сложившейся ситуации особую актуальность приобретают работы по созданию систем обработки текстовой информации (СОТИ). В последнее десятилетие в России и за рубежом было разработано и внедрено значительное число коммерческих СОТИ, ориентированных, прежде всего, на массового потребителя. При этом значительно меньше внимания было уделено созданию инструментальных средств для удовлетворения информационных потребностей пользователей (специалистов-предметников), занятых научно-исследовательской деятельностью. К числу основных информационных потребностей данной категории пользователей следует отнести: мониторинг публикуемых научных материалов и отслеживание тенденций, происходящих в области профессиональных интересов; выявление и получение из имеющегося документального потока значимых научных статей, необходимых для проведения НИОКР и подготовки современных учебных курсов, диссертационных работ.
Общеизвестно, что в Интернет, корпоративных хранилищах информации в некоммерческом доступе обычно находятся библиографические документы. Если СОТИ ориентирована на работу с такими документами, то появляется возможность на основе их анализа проводить отбор и адресный заказ небольшого числа платных полнотекстовых статей, необходимых для успешного проведения научных исследований. Данный подход к обработке информации обеспечивает снижение материальных затрат на подписку и закупку периодических изданий и материалов конференций, что особенно важно для малых научных коллективов (кафедра, лаборатория, отдел) и специалистовпредметников, самостоятельно проводящих исследования.
Чаще всего информационная потребность специалиста-предметника состоит не только в выделении релевантных документов из общего документального потока, но также в разнесении этого текстового массива на тематические группы, соответствующие более узким вопросам (подтемам). Поэтому практически все современные СОТИ содер жат модуль классификации документальной информации в качестве одного из основных компонентов системы.
Методы классификации давно находятся в центре внимания многих коллективов разработчиков. Вместе с тем до сих пор не создано универсального решающего правила, обладающего большой обобщающей способностью и показывающего устойчиво высокую точность на различных выборках. Более того, в условиях изначально непредсказуемой структуры текстовой выборки многие достаточно точные методы классификации показывают противоречивые результаты и их точность от выборки к выборке варьируется в значительных пределах. В большинстве практических задач использование только одного метода не может гарантировать желаемых результатов.
Обзор и анализ публикаций в области обработки данных показывает, что один из наиболее эффективных подходов к увеличению точности и устойчивости классификации основан на синтезе коллективов решающих правил (КРП, комитетов классификаторов). В КРП для принятия решения о классификации документа используется не один, а m методов, каждый из которых самостоятельно присваивает метку класса, после чего формируется общий результат классификации, например, с помощью простого голосования членов комитета.
К числу важных достоинств КРП необходимо отнести следующие свойства.
1) Групповые решения обладают значительно большей устойчивостью и независимостью от структуры и размера выборок. В КРП компенсируются неточности и ошибки, возникающие из-за ограниченного размера обучающей выборки, наличия в ней нерелевантных шумовых элементов, несовершенства методов, используемых на стадии предварительной обработки данных. В условиях практически полного отсутствия априорной информации о структуре документального массива комитеты классификаторов позволяют получать наиболее точное из возможных решений за счет использования дополняющих друг друга решающих правил и специальных стратегий обучения.
2) Существует возможность наращивания сложности решающего правила путем увеличения числа членов КРП до той степени, которая отвечает требованиям решаемой задачи классификации, обеспечивая заданную точность.
3) Групповые решения легко интерпретируются, что особенно важно при применении КРП на практике.
Основным недостатком данного подхода является низкое быстродействие и высокая ресурсозатратность (вычислительная сложность) при обучении. В связи с этим особую актуальность приобретают работы по синтезу высокоточных, быстродействующих и малозатратных КРП для обработки и анализа библиографических текстовых документов. Как показывают специально проведенные автором исследования, для решения данной задачи требуется разработка новых (или усовершенствование уже имеющихся) индивидуальных методов классификации.
Объектом исследований в данной работе являются системы обработки текстовой информации, позволяющие автоматизировать процесс анализа документов и обеспечивающие своевременное получение и распределение информации по классам согласно профессиональным потребностям пользователя.
Предметом исследований в диссертации являются индивидуальные и коллективные методы классификации библиографической текстовой информации.
Цель работы заключается в разработке новых методов классификации и синтезе коллективов решающих правил, обеспечивающих высокую точность, быстродействие и небольшую ресурсозатратность решения задачи классификации библиографических текстовых документов.
Методы исследования. Полученные в диссертации результаты основываются на применении аппарата системного анализа, теории вероятностей, математической статистики, линейной алгебры, теории множеств, вычислительной геометрии, теории алгоритмов, систем искусственного интеллекта, численных методов, имитационного моделирования.
Научная новизна.
1. На основе системного анализа процесса обработки библиографических текстовых документов предложен критерий, учитывающий требования к процедурам выявления информативных терминов, обучения и классификации по точности, быстродействию, ресурсозатратам; построена модель процесса, имеющая модульную структуру, что позволяет оценить влияние различных этапов обработки и анализа библиографических данных на значение целевого критерия.
2. Проведена систематизация процедур выявления информативных терминов и методов классификации текстовых данных, сформулированы рекомендации по их использованию. Построена классификационная матрица, которая позволяет осущест влять обоснованный выбор процедур выявления информативных терминов и методов классификации, исходя из требований к точности, быстродействию и ресурсозатратам.
3. Разработано три новых метода классификации библиографических текстовых документов (модифицированный метод ближайшего соседа, обобщенный метод ближайшего соседа и метод MI- профилей). Адаптированы метод - профилей и метод - профилей для решения задач классификации библиографических тексто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Цмерном пространстве, где М - количество признаков (размер словаря терминов):
Т X x(j1),..., x(ji),..., x(jM ). (1) j Здесь x(i) - вес термина i в документе j (j=1,Е,N, N - количество документов в j выборке, i=1,Е,M).
Выборка текстовых документов может быть представлена в виде матрицы Удокумент - терминФ, строки которой представляют собой документы, а столбцы - термины, содержащиеся в этих документах. Для определения весов терминов в документах используются специальные методы взвешивания (например, tfc-взвешивание, см. формулу (3)).
В первой главе также обосновывается применение методологии системного анализа для решения поставленных в диссертации задач. На основе методологии системного анализа формируется целевой критерий (ЦК) Уточность-быстродействиересурсозатратностьФ, которому должны удовлетворять разрабатываемые в диссертации инструментальные средства. Такой критерий может быть записан в виде:
P 1 1 , ( Z Zдопуст.), (2) t t где P (precision) - точность системы обработки текстовых данных, t - быстродействие системы, - ошибка системы, Z - затраты на этапе обучения, Zдопуст. - допустимые затраты ресурсов на этапе обучения.
При этом точность оценивается по экзаменационной (тестовой) выборке как отношение количества правильно проклассифицированных документов к общему размеру экзаменационной выборки. Под быстродействием понимается время, которое затрачивается алгоритмом для классификации нового документа (присвоения документу метки класса). Под затратами понимаются временные и материальные ресурсы, необходимые для формирования обучающих и экзаменационных выборок, организации и проведения настройки параметров процедур обработки и анализа текстовых данных.
Обычно при настройке параметров различных методов классификации используются одни и те же выборки и алгоритмы предварительной обработки данных, поэтому эти затраты одинаковы для большинства методов классификации и их можно зафиксировать, относя к УнеизбежнымФ потерям, всегда возникающим при проведении классификации текстовых документов. В этом случае главным фактором, определяющим показатель ресурсозатратности, становятся затраты на стадии обучения, возникающие при настройке параметров решающих правил на обучающих и экзаменационных выборках.
В диссертационной работе оценивание быстродействия классификации и затрат на стадии обучения проводится с использованием инструментария теории алгоритмов на основе расчета вычислительной сложности. Математический аппарат теории алгоритмов позволяет получать оценки вычислительной сложности алгоритма вне зависимости от производительности компьютерной техники с помощью оценки количества необходимых элементарных вычислительных операций. Таким образом, вычислительная сложность в работе будет рассчитываться с помощью О-оценок, которые зависят от размера входных данных алгоритма.
В первой главе в рамках методологии системного анализа строится модель процесса обработки библиографической текстовой информации. В модель включены следующие модули: УСбор информации и формирование выборокФ; УПредварительная обработка данныхФ, которая объединяет процедуры удаления разметки и стоп-слов, выде ления основ слов (stemming), индексирования и выявления информативных признаков, представления текстового массива в виде матрицы Удокумент-терминФ; УВыбор методов классификацииФ; УОбучение классификаторовФ; УОценка точности, быстродействия и затратФ.
Предложенная модель позволяет выделить наиболее важные модули с точки зрения ЦК. К таким модулям относятся:
1) предварительная обработка текстовой информации, прежде всего, выбор процедуры выявления информативных признаков;
2) выбор классификаторов и их обучение; объединение классификаторов в высокоточные, быстродействующие и малозатратные КРП.
В рамках сформулированной цели работы наиболее логичным и естественным шагом является анализ существующих методов классификации и выявление из них таких решающих правил, на основе которых можно сформировать высокоточные, быстродействующие и малозатратные комитеты. Однако, учитывая многоаспектность и разнохарактерность исследований, проводившихся в области теории классификации, такая задача представляется нетривиальной. Для ее решения в данной работе используется методология системного анализа. С позиций системного анализа осуществляется систематизация процедур, выполняемых на наиболее ответственных этапах обработки и анализа текстовых данных, и оценивается их взаимосочетаемость. Причем предлагаемая систематизация строится на общих принципах как для процедур выявления информативных признаков, так и для методов классификации.
Для проведения объективной систематизации процедур выявления информативных признаков и методов классификации были проанализированы практически все доступные (на момент подготовки работы) материалы по данной проблематике. Эти материалы состояли из известных публикаций, экспертных суждений и собственных экспериментальных исследований.
В качестве основного результата систематизации процедур выявления информативных признаков, следует отметить выделение алгоритмов взвешивания, которые наиболее полно удовлетворяют сформулированному ЦК. Наилучшие результаты в данной работе были получены для tfc-взвешивания, которое рассчитывается по формуле:
N fij log Ni x(ji) , (3) M N fij log Ni i где fij - частота слова i в документе j, N - число документов в выборке, М - число слов в выборке после удаления служебных слов и выделения корней слов, Ni - общее количество документов, содержащих слово i.
Главный итог систематизации методов классификации заключается в том, что выявлено крайне незначительное число известных классификаторов, которые обладают приемлемыми показателями по быстродействию, точности и затратам на стадии обучения (к таким классификаторам можно отнести метод центроидов и наивный байесовский метод). В связи с этим важным направлением исследований в области теории классификации является разработка новых (или модификация известных) методов, которые должны обладать высокой точностью и высоким быстродействием, а также быть приемлемыми с точки зрения требуемых ресурсозатрат. Кроме того, проведенная систематизация позволяет отнести синтез КРП к перспективному и актуальному направлению исследований. При этом особый интерес вызывает решение проблемы построения высокоточных, быстродействующих, малозатратных комитетов.
Проведенная систематизация процедур выявления информативных признаков и методов классификации позволяет сформировать единую классификационную таблицу, которая существенно облегчает исследователю выбор средств для решения той или иной практической задачи обработки библиографической текстовой информации. Фактически такая таблица является аналогом номограммы, которая в зависимости от требований к точности, быстродействию и допустимым затратам позволяет рекомендовать наиболее подходящие алгоритмы выявления информативных признаков и классификации.
Во второй главе проводится обзор основных направлений исследований в области разработки коллективов решающих правил. Под коллективом решающих правил в работе понимается совокупность методов классификации {J1,..., Jm}, объединенных для выработки общего решения. Сравнительный анализ различных стратегий голосования в КРП позволяет сделать вывод, что если комитет составляется из разнородных класси фикаторов, обладающих приблизительно одинаковой индивидуальной (достаточно высокой) точностью, то предпочтительно использовать простое голосование. В таких неоднородных КРП каждый классификатор имеет равный вес при принятии решения и новое наблюдение X относится к тому классу, за который проголосовало большинN ство членов КРП.
Отметим, что простое голосование не увеличивает совокупной сложности синтезируемых КРП и не приводит к росту затрат на стадии обучения. Кроме того, для простого голосования можно теоретически рассчитать верхнюю точностную границу, к которой будут стремиться комитетные решения. Для расчета необходимо сделать следующие предположения: все методы, используемые в КРП, независимы; точность членов комитета известна и все решающие правила являются равноточными; КРП состоит из нечетного количества классификаторов (3 m 9 ).
Определим верхнюю точностную границу комитета, который может состоять соответственно из трех, пяти, семи или девяти методов классификации, при этом индивидуальная точность р членов КРП меняется от 0,6 до 0,9. Результаты расчета приведены в таблице 1. Анализ полученных результатов показывает, что применение КРП на основе простого голосования гарантирует увеличение точности по сравнению с точностью отдельных классификаторов, членов комитета, если они являются независимыми и их индивидуальная точность p 0,5.
Таблица p m m 3 m 5 m 7 m p 0,0,648 0,682 0,710 0,7p 0,0,784 0,837 0,874 0,9p 0,0,896 0,942 0,966 0,9p 0,0,972 0,991 0,997 0,9Принципы проведения селекции методов для их включения в неоднородные КРП остаются одним из наименее формализованных и разработанных вопросов в теории классификации. В данной работе для отбора классификаторов в КРП используются меры разнородности. Проведенный автором сравнительный анализ мер разнородности позволил выделить Цстатистику в качестве наиболее подходящей меры разнородности Q при синтезе неоднородных КРП на основе простого голосования.
Q Цстатистика показывает связь между ошибками, которые допускаются двумя решающими правилами Js и J из коллектива. Парная Q Цстатистика рассчитывается p по следующей формуле:
ad bc Qsp . (4) ad bc Здесь a - число раз, когда оба решающие правила Js и J сделали правильную p классификацию; b - число раз, когда решающее правило Js сделало правильную классификацию, J - неправильную; c - число раз, когда решающее правило J сделало p p правильную классификацию, Js - неправильную; - число раз, когда оба решающие d правила Js и 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 тех X (l 1,..., Nl, Nl N), которые принадлежат выявленной области.
l Эвристика, позволяющая осуществить поставленную цель, заключается во введе нии опорных точек (ОТ) P1,..., PS. Такие ОТ должны быть расположены на достаточном расстоянии друг от друга, например, являться центроидами различных классов.
Алгоритм обучения ММБС.
Входными данными алгоритма являются: обучающая выборка документов, представленная в виде матрицы Удокумент-терминФ; количество и расположение опорных точек (далее предполагается, что ОТ - центроиды всех классов, общее число ОТ S G ).
Выходные данные алгоритма представляются в виде упорядоченных матриц Dn ( n 1,..., S; S G ; G - количество классов).
Для обучения ММБС необходимо выполнить следующие шаги.
1. Вычисление расстояний от всех документов обучающей выборки X (l 1,..., N) до l опорных точек, получение NЦмерных векторов расстояний:
( ( ( d11) d21) ds1) ( ( ( d12) d22) ds2). (6) d1 ; d2 ; Е; d s d (N ) (N ) (N ) d1 d2 s 2. Проведение сортировки внутри векторов d1, d2,..., d так, чтобы элементы s ( ( ( d1l), d2l),..., dsl) располагались по возрастанию расстояния до опорных точек (от са мых близких к самым дальним) и расширение векторов d1, d2,..., d до матриц s D1, D2,..., Ds размерностью N 3. Первый добавленный столбец содержит целочис ленные значения, соответствующие исходному (до сортировки) номеру элемента; второй - метки классов, к которым относятся элементы.
( dn j) | j | Q ( dn1) ( ( dnr) | r | Q dn2) | | dn => Dn , (7) ( ( dn f ) | f | Q dni) | | ( dnN ) (m) dn | m | Q где n - порядковый номер опорной точки (n 1,..., S; S G) ; j,r,f,m,i - порядковые номера наблюдений в исходной выборке размера N, ,, , - метки классов (,, , 1,..., G ).
Алгоритм классификации ММБС.
Входными данными алгоритма являются: новое наблюдение X, заданное вектором N весов терминов (или экзаменационная выборка документов, представленная в виде матрицы Удокумент-терминФ); упорядоченные матрицы Dn (n 1,..., S; S G), полученные на стадии обучения.
Выходные данные алгоритма представляют собой метку класса, к которому отнесен но вый документ X.
N 1. Расчет расстояний от нового наблюдения X до опорных точек N ( ( (N 1) (l) d1N 1), d2N 1),..., d. Поиск таких расстояний dn (l=1,..,N; n=1,Е, S ) из первоs го столбца упорядоченных матриц D1, D2,..., Ds, которые были бы наиболее близки к ( ( (N 1) ( d1N 1), d2N 1),..., d. Определение расстояний dnl1), которые расположены в s (l) упорядоченных матрицах Dn в следующей позиции за элементами dn, т.е. справед( ( ( ливо: dnl) dnN1) dnl1). Вычисление радиусов и приращений радиусов проводится по формулам:
(l) ( ( Rn dn ; Rn dnl1) dnl). (8) 2. Определение номеров точек из второго столбца упорядоченных матриц (l) D1, D2,..., Ds, соответствующих найденным на предыдущем шаге расстояниям dn.
Поиск общих точек, которые находятся в -области пересечения гиперколец с центра( ( ми в опорных точках. Для этого анализируются точки, соответствующие d1l) и d1l 1), (l) (l1) ( ( d2l) и d2l 1),Е, ds и d.
s 3. В случае, если на предыдущем шаге обнаружить общие точки не удалось, увеличи( ( ваются приращения радиусов Rn (Rn dnl2) dnl)).
Теперь поиск общих точек производится среди расширенного числа многомерных на( ( ( ( ( ( ( ( ( блюдений: d1l), d1l1), d1l2) ; d2l), d2l1), d2l2) ;..., dsl), dsl1), dsl2).
Увеличение Rn проводится аналогичным образом до тех пор, пока не обнаружатся общие точки.
4. На основании правила ближайшего соседа (или правила к-БС) принимается решение об отнесении нового наблюдения X к одному из классов, при этом в голосовании N участвуют только те наблюдения, которые попали в общую многомерную область пересечения гиперколец.
Важная особенность ММБС заключается в том, что имеется возможность на стадии обучения за счет увеличения ОТ снижать ошибку классификации. В работе излагается специальный алгоритм определения числа ОТ для обеспечения заданной точности.
В этом алгоритме первоначально в качестве опорных точек используются центроиды всех классов. Затем, при необходимости, из выборки случайным образом извлекаются дополнительные наблюдения. Если они успешно проходят проверки на удаленность от уже имеющихся ОТ и на принадлежность к населенной области признакового пространства, то эти наблюдения становятся новыми опорными точками.
Главной целью разработки ММБС являлось повышение быстродействия прототипа - МБС (или метода к-БС) при классификации новых наблюдений. В этой связи необходимо оценить количество операций, исполняемых в ММБС на стадии классификации X нового наблюдения. Рассчитаем вычислительную сложность алгоритма ММБС N на основе использования О-оценок.
Количество операций для расчета расстояний от нового наблюдения X до S N опорных точек: O1этап S O(M ), где O(М ) - вычислительная сложность операции классиф.
расчета евклидова расстояния.
Количество операций по определению расстояний в упорядоченных матрицах Dn (n 1,..., S):
2этап Oклассиф. S O(logN), где O(logN) - вычислительная сложность операции двоичного поиска.
Таким образом, на этапе классификации число необходимых операций вычисляется следующим образом:
общее 2этап OММБС(классиф.) O1этап Oклассиф. S O(M) S O(logN). (9) классиф.
На стадии обучения общая вычислительная сложность алгоритма ММБС включает расчет расстояний до ОТ (вычислительная сложность S O(NM )) и проведение сортировки (вычислительная сложность S O(N log N)):
общее OММБС(обучения) S O(NM ) S O(N log N). (10) Известно, что количество операций, необходимое для классификации нового наобщее блюдения в методе ближайшего соседа, равно ОМБС(классиф.) (NM ) N O(M ). Тогда общее общее OММБС(классиф.) OМБС(классиф.), так как в формуле (9) S N и O(logN) O(NM ).
В диссертации детально исследуются характеристики разработанного ММБС. В частности, анализируется механизм принятия решений. Отмечается, что если в методе кБС областью принятия решений является гиперсфера, то в ММБС такой областью является гипермногогранник, получаемый в результате пересечения гиперколец около классифицируемого наблюдения. В связи с этим область принятия решений в ММБС будет включать не только ближайших соседей (БС), содержащихся в гиперсфере, но и дополнительные точки, лежащие ближе к вершинам гипермногогранника.
Таким образом, решение в ММБС не всегда принимается исходя из анализа ближайших соседей. Используя понятие, введенное в литературе по непараметрическим методам классификации, можно назвать точки, лежащие внутри гипермногогранника, но не принадлежащие гиперсфере, аппроксимированными ближайшими соседями. Наблю апр дение X является аппроксимированным соседом для X, если справедливо нераN венство:
* апр * d(X, X ) d(X, X ) 1 d(X, X ). (11) N 1 N 1 N * Здесь X - ближайший сосед для X, - положительная малая величина.
N Алгоритм ММБС предоставляет потенциальную возможность для дальнейшего улучшения точности метода без существенного снижения быстродействия. Для этого в данной работе предлагается новая процедура классификации, получившая название обобщенного метода ближайшего соседа (ОМБС). Основная идея метода заключается в том, чтобы проводить взвешивание аппроксимированных БС, участвующих в принятии решений в ММБС. Это должно снизить ошибку за счет уменьшения влияния наиболее удаленных из аппроксимированных БС, которые получают меньший вес при определении метки класса.
Возможность появления среди аппроксимированных соседей точек, достаточно удаленных от классифицируемого наблюдения, обусловлена тем, что в ряде случаев гипермногогранник может быть вытянут (из-за структуры выборки) в одном (или нескольких) направлениях М-мерного признакового пространства.
В данной работе для проведения взвешивания соседей используется специально разработанная уточненная формула взвешивания:
(dк d ) (dк d1) j, d d j . (12) (1 )(dк d1) j 1, d dj В уточненной формуле взвешивания кЦй сосед имеет вес, который определяется значением коэффициента взвешивания :
к . (13) (1 ) Экспериментальная настройка коэффициента взвешивания в процессе обучения позволяет корректировать веса различных соседей. Согласно проведенным автором исследованиям уточненная формула взвешивания обеспечивает более высокую точность классификации по сравнению с известными формулами линейного взвешивания.
Вышеизложенный алгоритм ММБС оперирует расстояниями от новой точки X до опорных, взвешивание которых нецелесообразно. В связи с этим расчет весов N проводится для соседей, попавших в общую область . Алгоритмы обучения ММБС и выбора опорных точек в полной мере применимы для ОМБС. На стадии классификации первые три шага алгоритма ОМБС также аналогичны алгоритму классификации ММБС.
После чего выполняется дополнительные шаги.
Дополнительные шаги для алгоритма классификации ОМБС.
4. Для выявленных на предыдущем шаге точек, попавших в общую область , рассчитываются расстояния до классифицируемого наблюдения X. Найденные расN БС БС стояния d1,..., dк сортируются по возрастанию. С целью определения весов для попавших в общую область точек применяется уточненная формула линейного взвешивания (см. формулу (12)).
5. Осуществляется взвешенное голосование среди точек, попавших в общую об ласть. Новое наблюдение X относится к классу, получившему наибольший вес при N голосовании к-взвешенных соседей из области .
В диссертационной работе приводится также алгоритм экспериментальной настройки коэффициента взвешивания .
В ОМБС увеличивается время классификации нового наблюдения по сравнению с ММБС, однако быстродействие ОМБС остается значительно более высоким, чем у МБС или метода кЦБС.
Так, в ОМБС добавляется по сравнению с ММБС дополнительный третий этап, включающий расчет расстояний от к точек, попавших в общую область , их сортировку и последующее взвешивание:
3этап Oклассиф. к O(M ) O(к logк) к (3О (2) 2О*(2) 2О (2) О**(2)). (14) Здесь - вычислительная сложность элементарных операций (сложение, умO(2) ножение, сравнение и т.п.), которые не зависят от размера входных данных.
Таким образом, количество вычислительных операций, которые осуществляются в ОМБС на этапе классификации, определяется следующим соотношением:
общее 2этап OОМБС(классиф.) O1этап Oклассиф. О3этап классиф. классиф.
S O(M) S O(logN) к O(M) O(к logк) к (3О (2) 2О*(2) 2О (2) О**(2)) (S к) O(M). (15) В (15) учтено, что О(logN) O(M), и.
O(к logк) O(M ) O(2) O(M ) Наряду с методом ближайшего соседа, позволяющим вводить новые эвристики, особый интерес при разработке простых классификаторов представляют профильные методы, основанные на вычислении некоторого формального объекта - профиля класса.
Наиболее известным профильным методом является метод центроидов (МЦ). Вместе с тем при использовании М - возникает ряд сложностей, главная из которых состоит в том, что многие термины с большим весом входят в профили сразу нескольких классов.
Для преодоления этой проблемы в диссертационной работе применяется подход, заключающийся в построения профилей классов на основе анализа двумерной таблицы сопряженности размера 2х2. Отличие данного подхода от центроидного заключается в том, что в профиль включаются термины, не только часто встречающиеся в данном классе, но и редко встречающиеся в других классах.
В диссертации рассматриваются принципы построения профилей классов на основе использования трех подходов: 2 - статистики; Q - статистики; улучшенного критерия взаимной информации, который был предложен автором.
Разработанные процедуры получили названия метода 2 Цпрофилей, метода Q - профилей и метода MIЦпрофилей (MI сокращение от Mutual Information - взаимная информация). В этих алгоритмах на этапе обучения проводится выявление наиболее информативных терминов для каждого класса на основе применения 2 - статистики, Q - статистики или улучшенного критерия взаимной информации. Затем полученный 2 - профиль ( - профиль или MI-профиль) используется для проведения классификации Q новых наблюдений.
В методах непараметрического оценивания 2 -статистика для данных, представленных таблицей сопряженности размера 2х2, рассчитывается по формуле:
(AD BC) 2 (x(i),Qg ) N. (16) (A B)(C D)(A C)(B D) В формуле (16) использованы следующие обозначения: А - число раз, когда термин x(i) и класс встречаются вместе; В - число раз, когда x(i) встречается без ;
Qg Qg C - число раз, когда встречается без ; D - число раз, когда и не встреQg x(i) Qg x(i) чаются; N - общее количество документов в выборке.
Величина Q - статистики во введенных выше обозначениях может быть рассчиAD BC тана по формуле: Q(x(i),Qg ) . (17) AD BC В данной работе предлагается улучшенный критерий взаимной информации. В предлагаемом критерии параметр A в числителе формулы известного в литературе критерия взаимной информации возводится в степень r:
Ar N r MI (x(i),Qg ) log2 A BA C. (18) Возведение в степень параметра А позволяет существенно увеличить значение взаимной информации для высокочастотных терминов и скомпенсировать основной недостаток классического алгоритма по заниженному взвешиванию наиболее информативных терминов.
В предложенных процедурах на этапе обучения проводится выявление информативных терминов и составление профилей для каждого класса на основе расчета весов терминов с помощью 2 Цстатистики, Q - статистики или улучшенного критерия взаимной информации. После чего составляется матрица профилей классов - Р. Столбцы матрицы сортируются в порядке убывания значений весов. Единственным управляющим параметром для всех трех методов является пороговое значение Т, которое опре деляет длину профиля классов M (предполагается, что все классы имеют одинаковую g длину профиля M1 M2 ,..., MG ).
На этапе классификации рассчитываются значения весов классов g, которые представляют собой Уинформационные суммыФ, соответствующие каждому классу. Расчет весов классов проводится по формуле:
Mg g tfi (x(i),Qg ), (19) iгде (x(i),Qg ) рассчитывается по одной из формул (16)-(18), tfi - частота встречаемости iЦго термина в классифицируемом документе, M - количество наиболее информаg тивных терминов, включенных в профиль gЦго класса.
Решающее правило в методе 2 Цпрофилей, методе Q - профилей и методе MI - профилей одинаково и имеет вид: классифицируемый документ X относится к тому N классу, которому соответствует наибольшая сумма весов ( X Qg, если g max, N для g, g 1,..., G).
В диссертационной работе приводится детальное описание алгоритмов обучения профильных методов и определения длины профиля.
Вычислительная сложность профильных методов. В рассмотренных выше профильных методах на этапе классификации рассчитываются значения весов классов по формуле (19). Для этого требуется следующее количество вычислительных операций:
общее общее общее O 2профиль(классиф.) ОQпрофиль(классиф.) OMI профиль(классиф.) (20) O1 O2 [G M (O * (2) О (2))] [(G 1) O(2)].
g где O1 - количество операций, необходимых для определения весов классов 1,Е,G, O2 - количество операций сравнений, необходимых для определения наибольшего веса класса.
Сравнение вычислительной сложности профильных методов с вычислительной сложностью наивного байесовского метода и метода центроидов показывает, что методы Цпрофилей, Q - профилей и MIЦпрофилей имеют практически такое же быст родействие, как наивный байесовский метод, который является одним из наиболее скоростных среди известных классификаторов. При этом быстродействие методов 2 - профилей, - профилей и MIЦпрофилей выше быстродействия МЦ.
Q Проведенная в данной главе разработка новых методов позволила существенно расширить число простых классификаторов, которые могут рассматриваться в качестве кандидатов для включения в высокоточные, быстродействующие и малозатратные КРП.
Глава 4 посвящена организации экспериментов и исследованию разработанных методов классификации и коллективов решающих правил на различных выборках библиографических текстовых документов, сопоставлению характеристик новых методов с характеристиками известных процедур. Особое внимание в главе уделяется оценке точности, разнородности, быстродействия, ресурсозатратности методов классификации, выработке рекомендаций по настройке их параметров, выбору решающих правил для их объединения в КРП согласно приведенной выше процедуре синтеза комитетов на основе простых классификаторов.
Логика изложения, многоаспектность проведенных исследований потребовали разделения результатов на две большие достаточно самостоятельные группы.
В первой группе приводятся результаты формирования выборок для проведения исследований; сравнительного анализа процедур выбора информативных признаков и мер близости; организации процесса обучения и тестирования решающих правил; разработки новых малозатратных методов классификации, обеспечивающих высокую точность и быстродействие; настройки их параметров; исследования временных и точностных характеристик, сопоставления с уже известными процедурами; выявления зависимости точности и быстродействия методов классификации от структуры выборки текстовых документов.
Вторая группа состоит из результатов, непосредственно связанных с синтезом высокоточных, быстродействующих и малозатратных КРП. В ней содержатся итоги исследований по отбору простых классификаторов для их включения в комитет; расчету мер разнородности для кандидатов в члены КРП; формированию КРП с заданными свойствами из числа отобранных простых классификаторов; сопоставлению точности и быстродействия коллективных и индивидуальных методов; выявлению зависимости точности и быстродействия КРП от количества членов комитета, размера и структуры выборки.
В данной работе использовались коллекции текстовых документов из библиографической базы данных (БД) Compendex (COMPuterized ENgineering inDEX), цифровой библиотеки (ЦБ) ResearchIndex и цифровой библиотеки ACM (Association for Computing Machinery - Ассоциация по вычислительной технике). Все вышеназванные ЦБ и БД имеют встроенный экспертно составленный рубрикатор, что позволяет избежать субъективизма и предвзятости при формировании обучающих и экзаменационных выборок.
Основные эксперименты проводились на девяти выборках одинаковой структуры (по три выборки из БД Compendex, ЦБ ResearchIndex, ЦБ ACM). Каждая обучающая выборка состояла из 700 библиографических документов, распределенных по семи классам, в классах содержалось одинаковое число текстов. Каждая экзаменационная выборка содержала по 140 документов (по двадцать документов в классе). Сформированные обучающие и экзаменационные выборки, использованные автором при проведении исследований, доступны на сайте кафедры Управления и информатики МЭИ (
При проведении предварительной обработки текстовых данных использовался словарь стоп-слов и осуществлялось выделение основ слов. Проведенные эксперименты позволили зафиксировать размер словаря равным 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,MI-проф. 0,252 0,Q-проф. 0,256 0,Хи-проф. 0,226 0,8Метод к-БС 0,255 147,Полученные экспериментальные результаты хорошо согласуются с теоретическими оценками вычислительной сложности и подтверждают, что все методы, разработанные в работе для классификации текстовых документов обладают высоким быстродействием, которое в разы превосходит быстродействие метода к-БС (при этом быстродействие разработанных профильных методов выше быстродействия высокоскоростного метода центроидов). В то же время предложенные методы обладают достаточно высокой точностью, соизмеримой с точностью УклассическихФ классификаторов (метода кБС и МЦ).
Таблица 2 содержит средние значения ошибок и быстродействия, рассчитанные по девяти выборкам. В работе также приводятся ошибки методов на каждой из выборок, оценивается устойчивость классификации и анализируется влияние структуры документальных массивов на результирующую точность.
Благодаря разработке новых методов, проведенной при выполнении данной работы, увеличилось число простых классификаторов, которые могут быть использованы для формирования комитета. Это позволило на практике синтезировать КРП, удовле творяющие сформулированным в диссертации требованиям по точности, быстродействию и допустимым затратам на стадии обучения.
На основе вышеизложенной процедуры синтеза КРП на основе простых классификаторов было синтезировано два новых комитета классификаторов: КРП -1, состоящий 2 из метода -профилей, М - и ОМБС; КРП -2, состоящий из метода -профилей, МЦ, метода MIЦпрофилей, ММБС, ОМБС.
Сравнительный анализ характеристик синтезированных КРП и известных индивидуальных классификаторов также проводился на девяти выборках. В таблице 3 приведены полученные на выборках ошибки, рассчитана средняя ошибка ( ) и размах ( ).
В качестве базовых классификаторов для сопоставления использовались М - и метод кБС.
Таблица Выборка \ Ошибка М - Метод к-БС КРП-1 КРП- метода В1 0,192 0,271 0,114 0,1В2 0,214 0,293 0,207 0,1В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,1В7 0,3 0,335 0,278 0,В8 0,307 0,343 0,293 0,2В9 0,293 0,3 0,278 0,2 0,2кБС 0,255 КРП1 0,189 КРП2 0,1Средняя ошибка М - 0,208 0,193 0,1и размах 0,2Приведенные в таблице 3 результаты свидетельствуют о том, что синтезированные КРП обеспечивают более высокую точность и устойчивость к выборочным изменениям в сопоставлении с базовыми классификаторами. При этом сформированные комитеты обладают большим быстродействием, чем метод к-БС.
Необходимость многократных экспериментов для настройки параметров решающих правил ведет к тому, что тестовые выборки фактически становятся частью процесса обучения. Тем самым ослабляется их роль как независимого критерия точности классификации. В данной диссертации были использованы три дополнительные вы борки из БД Compendex, на которых были подтверждены точностные и временные характеристики разработанных коллективных и индивидуальных методов.
Важным результатом экспериментальных исследований процедур анализа текстовых данных должен стать ответ на вопрос: насколько значимо улучшается точность классификации при использовании коллективов решающих правил по сравнению с индивидуальными методами. Для определения того, насколько существенно отличаются ошибки синтезированного комитета (КРП-1) и индивидуальных базовых классификаторов в работе применялся непараметрический критерий Вилкоксона (критерий знаковых рангов для связанных выборок). Согласно критерию имеются статистически значимые различия между ошибками, полученными при использовании КРП-1 и метода центроидов. Это позволяет сделать вывод о том, что снижение ошибки при коллективной классификации по сравнению с ошибками метода центроидов носит систематический неслучайный характер.
В главе 5 дается обоснование необходимости проведения разработки собственного программного обеспечения, приводится структура и функциональные возможности двух разработанных программных комплексов, предназначенных для обработки и анализа библиографических текстовых документов.
ПК УСКАТФ (УСистема Классификации и Анализа ТекстаФ) ориентирован, прежде всего, на автоматизированный мониторинг тематических ресурсов Интернет и проведение фильтрации-классификации получаемой информации в соответствии с профессиональными потребностями пользователя. Кроме того, он предоставляет возможность построения моделей предметных областей, проведения наукометрического анализа и выявления из документального потока фрагментов значимой для специалистапредметника информации.
УИПК (УУчебно-исследовательский программный комплексФ) позволяет решать две взаимосвязанные проблемы. Во-первых, УИПК является важной составляющей учебного процесса на кафедре Управления и информатики МЭИ и на его основе реализован лабораторный практикум по курсу Интеллектуальные информационные системы. Во-вторых, он позволяет студентам (магистрам, аспирантам, инженерам, преподавателям кафедры) осуществлять самостоятельные полномасштабные исследования процедур обработки и анализа библиографических текстовых документов в рамках курсового проектирования, квалификационных и научно-исследовательских работ, а также проводить разработку дополнительных модулей, расширяющих функциональные возможности УИПК. Алгоритмическую основу УИПК составляют разработанные автором методы классификации и синтезируемые из них КРП.
Основное внимание в главе 5 уделяется организации автоматизированного мониторинга научно-технических информационных ресурсов. Для выбора наиболее авторитетных в области специализации пользователя научных изданий в работе предлагается процедура выявления тематических журналов по заданным предметным областям. При этом основная задача данной процедуры заключается в увеличении точности поиска релевантной информации и обеспечении пользователя наиболее ценными публикациями.
В ходе разработки процедуры обосновывается использование импакт-факторов журналов для выявления наиболее рейтинговых и авторитетных изданий; определяется необходимое значение импакт-фактора для изданий, специализирующихся в области Информатики; формализуются действия пользователя по окончательному выбору количества и номенклатуры отслеживаемых изданий; рассматриваются способы уточнения сформированного списка журналов в ходе практической эксплуатации.
Разработанная процедура была использована для автоматизации системы информационного обеспечения научно-технической деятельности в ряде организаций: Республиканском исследовательском научно-консультационном центре экспертизы (РИНКЦЭ), кафедре Микросистемной техники МИРЭА, кафедре Управления и информатики МЭИ. Мониторинг тематических изданий и фильтрация-классификация публикаций были проведены с помощью ПК УСКАТФ. На основе анализа результатов эксплуатации и экспертных оценок специалистов, представляющих организации-заказчики, был сделан вывод об эффективности практического использования разработанных в работе индивидуальных и коллективных методов для обработки и анализа массивов научных библиографических документов.
Разработанные в диссертации инструментальные средства были использованы для обработки и анализа базы данных научных публикаций Института проблем химической физики РАН (ИПХФ РАН, г.Черноголовка). Анализ включал проведение следующих исследований: выделение из массива научных публикаций наиболее активных ученых и формирующихся вокруг них групп соавторов; установление связи между продуктивностью и соавторством; определение основных тематик исследований (профилей научных групп); отслеживание изменения тематик работ с течением времени. Результаты проведенных исследований, предоставленные для экспертного анализа, получили высокую оценку специалистов ИПХФ РАН, а выявленные закономерности нашли практическое применение при организации процесса планирования и управления НИОКР.
В ходе выполнения диссертации на базе разработанного алгоритмического, программного и методического обеспечения был построен терминологический портрет журнала Информационные технологии, определена область специализации журнала и выявлены наиболее близкие тематические издания. В работе показано, что для решения задач данного класса целесообразно использовать профильные методы, разработанные в диссертации.
В пятой главе также приводятся результаты использования УИПК в учебных и исследовательских целях, указывается, что разработанный программный комплекс существенно отличается от имеющихся программных средств в рассматриваемой предметной области, реализуя, наряду с классическими методами, оригинальные эффективные процедуры индивидуальной и коллективной классификации, предложенные и апробированные в ходе выполнения данной работы.
В заключении подведены итоги проведенных исследований и кратко изложены основные выводы и результаты.
Основные результаты работы 1. Показано принципиальное отличие задачи обработки и анализа текстовых данных от обработки и анализа фактографических наблюдений или распознавания образов.
Предложен целевой критерий синтеза системы обработки библиографической текстовой информации, учитывающий требования к точности, быстродействию и ресурсозатратам. На основе предложенного целевого критерия методом системного анализа построена модель, имеющая модульную структуру, что позволяет оценить влияние различных стадий обработки данных на значение целевого критерия.
2. С единых позиций проанализированы алгоритмы предварительной обработки и классификации библиографических текстовых данных, проведена их систематизация.
Построена классификационная матрица, которая позволяет осуществлять обоснованный выбор процедур выявления информативных признаков и методов классификации, исходя из требований к точности, быстродействию и ресурсозатратам.
3. Для организации экспериментальных исследований предложена методика формирования выборок, состоящих из библиографических текстовых документов. Обосновано использование метода обучающих-тестовых выборок для обучения и тестирования при проведении экспериментов.
4. Показано, что использование индивидуальных классификаторов не всегда способно обеспечить малую ошибку группировки текстовых документов, их оценки не являются устойчивыми, сильно изменяясь от выборки к выборке. Это связано с нарушением на практике ряда стандартных допущений (о независимости признаков, компактности выборки, сферичности (линейной разделимости) классов и т.п.), необходимых для эффективного функционирования конкретного решающего правила.
Для достижения более высокой точности в специализированной литературе предложено использовать дополнительные процедуры, приводящие чаще всего к синтезу коллективных решений. Однако существующие способы построения КРП не позволяют в полной мере формировать комитеты с заданными свойствами по точности, быстродействию, ресурсозатратности, уделяя завышенное внимание вопросам снижения ошибки классификации.
5. В работе с позиций предложенного ЦК рассмотрены имеющиеся комитеты классификаторов, проведен сравнительный анализ стратегий принятия решений в КРП.
Показано, что комитеты на основе простого голосования способны улучшить точность классификации по сравнению с точностью индивидуальных классификаторов. Методом имитационного моделирования исследована взаимосвязь между точностью методов и их разнородностью. Результаты моделирования наряду с проведенными экспериментальными исследованиями позволили выявить информативные диапазоны изменения данных характеристик.
6. В целях синтеза высокоточных, быстродействующих, малозатратных комитетов в работе уточняется понятие простого классификатора и вводятся требования, которым должны удовлетворять такие классификаторы. Предложена процедура синтеза КРП с заданными свойствами на основе простых классификаторов. Проведенный теоретический анализ вычислительной сложности алгоритмов классификации позволил выделить среди известных методов те, которые соответствуют требованиям к простым классификаторам.
7. Исходя из требований, которым должны удовлетворять простые классификаторы разработан и исследован ряд новых методов классификации: модифицированный метод ближайшего соседа, обобщенный метод ближайшего соседа, метод MI-профилей, а также для проведения группировки библиографических текстовых документов адаптированы метод -профилей и метод Q -профилей. Показаны принципиальные отличия разработанных процедур от уже известных. Даны рекомендации по выбору значений внутренних параметров в предложенных алгоритмах.
Разработанные в диссертации методы предназначены как для самостоятельного применения при классификации библиографических текстовых документов, так и для использования в качестве простых классификаторов при формировании высокоточных, быстродействующих и малозатратных КРП.
8. Получены оценки количества вычислительных операций, необходимых для классификации текстовых документов с помощью разработанных методов (ММБС и ОМБС) и показано, что они требуют меньшего количества вычислительных операций по сравнению с прототипом (методом к-ближайших соседей). Также показано, что быстродействие метода MIЦпрофилей, метода Цпрофилей и метода Q Цпрофилей значительно выше, чем у известных эвристических процедур (в частности метода центроидов и метода к-ближайших соседей).
9. На основе предложенной автором процедуры синтезированы и исследованы высокоточные, быстродействующие и малозатратные КРП, сформированные из простых классификаторов и состоящие из трех и пяти членов. Обосновано включение в комитеты методов, ряд из которых разработан лично автором. Впервые получены КРП-1, состоящий из метода -профилей, метода центроидов, обобщенного метода ближайшего соседа, и КРП-2, включающий метод -профилей, метод центроидов, метод MI - профилей, модифицированный метод ближайшего соседа и обобщенный метод ближайшего соседа. На выборках из библиографических текстовых документов показано, что синтезированные КРП обеспечивают более высокую точность и устойчивость по сравнению с методом к-БС и методом центроидов, а также обладают более высоким быстродействием в сопоставлении с методом к-БС.
10. Разработанные методы и ряд известных классификаторов реализованы в программных комплексах, созданных в ходе выполнения диссертационной работы. Опыт эксплуатации этих программных средств подтверждает эффективность полученных теоретических и научно-методических результатов. Практическое использование разработанных ПК позволяет решать важные прикладные задачи по отслеживанию научных публикаций в заданных предметных областях, выявлению содержательных фрагментов из неструктурированной информации и построению моделей (профилей) предметных областей, сопровождению учебного процесса. Разработанное программное обеспечение может быть адаптировано к различным предметным областям и требованиям пользователей, при необходимости оно может дополняться новыми модулями.
11. В рамках созданной в работе автоматизированной системы информационного обеспечения научно-технической деятельности предложена комплексная процедура выявления групп тематических журналов в информационных ресурсах Интернет. Использование данной процедуры позволило решить задачу своевременного обеспечения тематическими публикациями ряда научно-исследовательских и образовательных организаций, повысив эффективность научной деятельности заказчиков.
12. Разработан, апробирован и внедрен в учебный процесс учебноисследовательский программный комплекс, предназначенный для подготовки специалистов в области обработки и анализа текстовых данных. Продемонстрированы возможности УИПК по проведению комплексных исследований методов обработки и анализа текстовой информации. Алгоритмическую основу УИПК составляют разработанные автором методы классификации и синтезируемые из них КРП.
Основные публикации по теме работы 1. Толчеев В.О. Разработка и исследование новых модификаций метода ближайшего соседа. Приложение к журналу Информационные технологии, №3, 2005, с. 1-32.
2. Толчеев В.О. Современные методы обработки и анализа текстовой информации.
Учебное пособие. М.: Изд-во МЭИ, 2006 - 75с.
3. Толчеев В.О. Синтез коллективов решающих правил для проведения классификации текстовых документов. Информационные технологии, №10, 2007, с. Ц3238.
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, с.8587.
31. Кульга Д.В., Толчеев В.О., Филимонов Н.Б. Построение и анализ терминологического портрета журнала Информационные технологии. Международная конференция УИнформационные средства и технологииФ том 3. МЭИ. Изд-во Станкин, 2008, с. 104-105.
32. Некрасов И.В., Толчеев В.О. Экспериментальные исследования методов классификации текстовых документов. Научная сессия МИФИ 2005. М. МИФИ, 2005, стр. 152-153.
33. Зенкина Ю.И., Толчеев В.О. Разработка программного комплекса для отбора тематических изданий и публикаций в области информатики. Алушта. Изд-во Тульского государственного университета, 2007, с. 256-257.
34. Некрасов И.В., Толчеев В.О. Информационно-поисковая система для обработки научно-технической информации. Международная конференция УИнформационные средства и технологииФ том 1. МЭИ. Изд-во Станкин, 2001, с. 114-117.
Авторефераты по всем темам >>
Авторефераты по техническим специальностям