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

005015968

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

( /

Бородкин Артем Александрович

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

Специальность 05.13.01 - системный анализ, управление и обработка информации (энергетика, приборостроение, информатика, производственные процессы)

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

Москва - 2012

3 Ш 2012

005015968

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

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

доцент

Толчеев Владимир Олегович

Официальные оппоненты: Ковшов Евгений Евгеньевич

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

заведующий кафедрой «Управление и информатика в технических системах» ФГБОУ ВПО МГТУ «СТАНКИН»

Орлов Александр Иванович

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

профессор кафедры «Экономика и организация производства» ФГБОУ ВПО МГТУ им. Н.Э. Баумана

Ведущая организация: ФГБУН Институт проблем управления

им. В.А. Трапезникова РАН

Защита состоится "24" мая 2012 г. в 16 часов 00 мин. на заседании диссертационного совета Д 212.157.08 при НИУ МЭИ по адресу: 111250, Москва, ул. Красноказарменная, д. 14, Малый актовый зал.

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

Отзывы в двух экземплярах, заверенные печатью, просьба направлять по адресу: 111250, Москва, ул. Красноказарменная, д. 14, Ученый совет НИУ МЭИ.

Автореферат разослан "23" апреля 2012 года

Ученый секретарь ^//¡г

диссертационного совета Д 212.157.08 (1пМ/

кандидат технических наук, доцент ¿гЧ' Д.Н.Анисимов

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

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

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

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

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

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

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

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

текстовых документов.

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

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

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

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

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

5. Разработать и применить комплексную методику выбора процедур (и параметров) обработки и анализа текстовых данных на основе статистических непараметрических критериев.

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

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

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

1. Обоспован и исследован 1фитерий выявления "внутренних" документов, основанный на новой формуле линейного взвешивания ¿-ближайших соседей.

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

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

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

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

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

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

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

Апробация работы. Материалы диссертации докладывались на четырех конференциях "Информационные средства и технологии" (2007, 2008, 2009, 2010 гг., Москва, МЭИ), на Научной сессии МИФИ (2008 г., Москва, МИФИ), на двух научно-технических семинарах "Современные технологии в задачах управления, автоматики и обработки информации" (2007, 2011 гг., Алушта, МАИ).

Публикации. По теме диссертации опубликовано 10 работ, в том числе 2 статьи в журналах из Перечня ВАК.

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

жений. Основной текст диссертации излагается на 150 машинописных страницах и содержит 34 рисунка и 17 таблиц.

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

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

В первой главе вводятся ключевые термины и определения, используемые в работе, формулируется задача классификации и редукции обучающих выборок, С учетом специфики решаемой задачи описываются основные этапы обработки и анализа текстовой информации. Для этапа сбора данных излагаются рекомендации по выбору объема и способа формирования обучающих выборок. На этапе начальной и содержательной обработки массив документов описывается в виде матрицы «документ-термин». При этом отдельный документ представляется вектором (точкой) в М-мерном пространстве терминов. Для получения координат этого вектора проводится взвешивание терминов (применяется формула (/-^-взвешивания или ее модификации). Для снижения размерности многомерного пространства в работе используется процедура выделения корней слов (стемминг). На этапе разведочного анализа текстовых данных рассматривается целесообразность выявления глобальных выбросов с помощью принципа расстояния и построения диаграмм размаха Тьюки. Для настройки параметров классификаторов и методов редукции в работе используются обучающие и тестовые выборки. Оценка ошибок классификации осуществляется на экзаменационных выборках.

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

(1) и a>j=< dk 1

dk~dj+dj

j

Здесь ¿/у-расстояние между классифицируемым документом и егоу'-м ближайшим соседом, найденное с помощью евклидовой метрики расстояния (/ = 1,..., к)\ и </4 - расстояния между классифицируемым документом и соответственно его 1-ми к-м ближайшими соседями; т1- - весу-го ближайшего соседа.

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

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

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

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

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

гиперсферу радиуса К у с центром в X^ .

В работе исследуется шесть критериев определения "внутренних" документов: критерий расчета соотношения числа "своих" документов (одного класса с Xу) и числа "чужих" документов (из других классов) внутри гиперсферы радиуса ^; критерий вычисления соотношения евклидовых расстояний (расстояний между X] и "своими" документами в гиперсфере радиуса и расстояний между X } и "чужими" документами в гиперсфере); критерий рангового взвешивания для определения весов документов в гиперсфере (при этом ближайший документ к X^

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

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

имеющий вид: у = —г-_ >1-5 (3)

Ю + У\>

Здесь м>+- сумма весов ближайших соседей документа Xпринадлежащих %-щ классу, м>~- сумма весов ближайших соседей документа Xне принадлежащих §-му классу (веса вычисляются по формуле (2)), 8- пороговое значение, позволяющее регулировать степень редукции и выбираемое из интервала [0;0,5).

9

Так как значение д в формуле (3) заранее неизвестно, то для применения критерия на практике требуется определить два параметра: пороговое значение 8 и радиус гиперсферы Я]. Такие задачи обычно решаются в ходе экспериментальных

исследований путем фиксирования величины одного из параметров и настройки другого. В данной диссертационной работе настройка параметра Я j при фиксированном 8 проводится так, чтобы получить наибольшее количество "внутренних" документов, к которым применима операция объединения. Алгоритм расчета радиуса окрестности

Входные данные: обучающая выборка размера N (массив векторов {X} },/ = 1,...,АО; значение 8 из диапазона [0;0,5), критерий у .

Выходные данные: радиусы окрестности для каждого класса ^.....Л .....Ле;' массив "внутренних" документов (массив векторов

{X = N] < Ю, массив попарных расстояний {Щ.

Описание алгоритма:

1. Рассчитываются попарные расстояния между всеми документами выборки и сохраняются в массиве {Щ. Находится минимальное и максимальное значение расстояний. Вычисляются значения радиусов окрестностей:

= (4)

2. Для каждого значения радиуса г,- (; = 0,...,99) по заданному критерию у определяются "внутренние" документы. Подсчитывается количество "внутренних" документов внутри #-го класса ( £ = 1,...,(?).

3. В качестве радиуса окрестности выбирается такое значение г,, при котором количество "внутренних" документов g-тo класса - максимально

= 1.....б^-

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

Алгоритм модифииированного метода прототипов

Входные данные-, обучающая и тестовая выборка, массив "внутренних" документов (массив векторов {X] },] = значения радиусов окрестности для каждого класса ,,Яе,...,Ка, критерий /, массив попарных расстояний {Щ.

Выходные данные: редуцированная обучающая выборка, полученная за счет слияния "внутренних" документов (размер редуцированного множества Ы2 < Л',).

Описание алгоритма:

1. Для всех "внутренних" документов X } выполняются следующие операции:

a. В массиве попарных расстояний {Щ для X } находятся "свои" соседи (Хт ебг) " "чужие" соседи (Xр ¡ёQg), попавшие в гиперсферу радиуса

Д,-

b. Рассчитывается значение разницы 2 между количеством "своих" и "чужих" соседей.

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

3. Из упорядоченного списка выбираются 5 документов, принадлежащих разным классам (5<С). Для каждого из выбраттых документов выполняется объединение (усреднением) X; с его ближайшим "своим" соседом. Для нового элемента, полученного усреднением, находится значение критерия у. Объединение признается успешным, если для всех 8 новых документов выполняется условие у > 1 — <5 (то есть документы по-прежнему относятся к категории "внутренние"), в противном случае осуществляется иной выбор документов. В случае успешного объединения множество векторов сокращается на Я документов. Если ни для одного класса не удается найти документ, удовлетворяющий указанному условшо, то осуществляется переход к шагу 5.

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

5. Вывод редуцированного множества внутренних документов.

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

1. Задается целевой показатель, критерий определения "внутренних" документов, непараметрический классификатор.

2. По алгоритму расчета радиуса окрестности вычисляются радиусы окрестностей для каждого класса .....Д.,...,.^, выбирается значение порога 5, выявляется массив "внутренних" документов.

3. Согласно модифицированному методу прототипов на основе объединения "внутренних" документов формируется редуцированная обучающая выборка.

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

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

Исходные решающие правила при использовании непараметрических методов дня классификации редуцированных выборок не изменяются. Эффект увеличения быстродействия достигается за счет сокращения размера обучающей выборки и, как следствие, снижения числа вычислительных операций, которые необходимы для определения класса нового документа. Для метода ¿-ближайших соседей справедливо: О" = N • О(М). Здесь о^"^ - число вычислительных операций, необходимых для определения метки класса документа; 0(М)~ вычислительная сложность наиболее ресурсозатратной операции расчета (евклидова) расстояния, Ы- размер обучающей выборки до редукции, М-размер словаря терминов (количество терминов в документе).

Выигрыш в быстродействии метода £-ближайтпих соседей обеспечивается в том случае, если в ходе выполнения редукции были объединены документы из обучающего массива (т.е. М2 < Л')-

Во второй главе также дается описание выборок, применяемых для исследований. В экспериментах используется девять выборок - по три выборки из англоязычных библиографических баз данных А СМ (выборки обозначаются А1,А2,АЗ), Compendex (С1,С2,СЗ), Researchlndex (R1,R2,R3). Обучающие выборки содержат 700 документов, тестовые и экзаменационные выборки включают 140 документов, во всех выборках документы поровну распределены по 7 классам. Кроме того, в экспериментальных исследованиях используется шесть выборок библиографических документов из русскоязычной цифровой библиотеки eLibrary. Три из них {VI, V2, V3) имеют одинаковое количество документов в классах (объем обучающих выборок JV= 200, размер тестовых и экзаменационных п = 50, количество классов в выборках G ~ 5), три другие - (V4, V5, V6) имеют размер обучающих выборок N = 266 и неодинаковое распределение документов по классам (jV, = 70, N2 = 63, N} = 53, Nt=N,= 40), размер тестовых и экзаменационных выборок п = 68. На основе проведешшх экспериментов даются рекомендации по выбору параметров предложенного метода.

На рисунке 1 приведена зависимость минимальной степени редукции, полученной на девяти англоязычных выборках, от величины д при использовании различных критериев выявления "внутренних" документов: а) критерия вычисления соотношения евклидовых расстояний; б) критерия линейного взвешивания документов по формуле (2); в) обобщенного критерия.

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

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

Рисунок 2. Изменение ошибок метода к-БС на экзаменационных выборках при использовании различных критериев выявления "внутренних" документов

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

Анализ результатов, приведенных на рисунках 1 и 2, позволяет сделать вывод, что «умеренной» редукции соответствует интервал варьирования 8 от 0,35 до 0,4 (при уменьшении значений 8 будет проводиться «мягкая» редукция, а при увеличении - «агрессивная»). Отметим также, что критерий линейного взвешивания документов по формуле (2) обеспечивает практически такую же степень редукции, как и более сложный дня расчета обобщающий критерий (при этом критерий линейного взвешивания на большинстве редуцированных выборок обеспечивает более высокую точность классификации).

На рисунке 3 показана зависимость количества "внутренних" документов от радиуса окрестности Rg (для класса «Control systems synthesis», при 8 = 0.4).

1 OS

■too 9S

ffi 0O

Радиус окрес-шоста^

Рисунок 3. Зависимость количества "внутренних" документов от радиуса окрестности в классе «Control systems synthesis» при использовании весового критерия.

На основе проведенных экспериментальных исследований определено, что дои вышеуказанного диапазона изменения 5 средние значения Rg будут изменяться в интервалах: Rg е [0,87; 1,18].

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

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

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

Таблица 1

Англоязычные выборки Русскоязычные выборки

ИЯОР-4 Разработанный метод редукции ОЯОР-4 Разработанный метод редукции

Выборка Ае М Ае А/ Выборка Ае Д/ Ае Д?

А1 -4.29 66 0.71 23 VI 8 42 2 21

А2 2.14 58 -2.86 23 У2 0 39 -2 24

АЗ 0 54 0.71 22 УЗ 2 41 0 19

С1 0 51 -1.43 18 У4 4.41 44 2.94 23

С2 0 56 -3.57 18 У5 7.35 45 1.47 17

сз -2.86 52 -2.15 18 У6 8.82 47 2.94 12

ю -0.72 55 -0.72 17

112 0.71 44 0 18

Ю 2.14 54 0.71 15

В таблице 1 использованы обозначения: Де- изменение ошибки метода к-

ближайших соседей на редуцированных выборках (в %), Д/ - увеличение быстродействия классификации на редуцированных выборках (в %).

Исследование точности классификации метода ¿-ближайших соседей на редуцированных выборках, полученных с помощью разработанного метода редукции и метода ИЯОР4, показало, что разработанный метод обеспечивает большую точность, чем ИКОР4, и на всех выборках удовлетворяет целевому показателю, обеспечивая на англоязычных и русскоязычных выборках увеличение быстродействия в среднем на 19%. Дополнительные исследования разработанного метода редукции продемонстрировали его устойчивость к незначительным изменениям структуры выборок (вариациям размера выборок и количества документов в классах). Эксперименты на выборках из БД ЯезеагсМпЛех с разным количеством документов в обучающей выборке показали, что разработанный метод редукции, в отличие от 01ЮР4, на всех выборках удовлетворяет требованиям целевого показателя и обеспечивает более высокую точность.

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

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

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

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

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

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

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

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

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в изданиях, рекомендованных ВАК:

1. Бородкин A.A., Толчеев В.О. Разработка учсбно-исследовательского программного комплекса для обработки и анализа библиографических текстовых документов. Вестник МЭИ №1 2010, с. 96-102

2. Бородкин A.A., Толчеев В.О. Разработка комплексной процедуры редукции для увеличения быстродействия непараметрических методов классификации текстовых документов. Заводская лаборатория. Диагностика материалов. №11 2011, с.64-69.

Другие статьи и материалы конференций:

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

4. Бородкин A.A., Толчеев В.О. Исследование влияния структуры выборки и процедур предварительной обработки на точность классификации текстовой информации. Международная конференция "Информационные средства и технологии". Том 2. МЭИ. Изд-во Станкин, 2007, с. 33-34.

5. Бородкин A.A. Комплексная процедура редукции выборок текстовых документов // Международный форум информатизации МФИ-2010. Труды XVIII международной научно-технической конференции «Информационные средства и технологии». Т.З. - М.:МЭИ, 2010-е. 251-254

6. Бородкин A.A., Толчеев В.О. Методы удаления нерелевантных документов из обучающих выборок. Международный форум информатизации МФИ-2009.

Труды XVII международной научно-технической конференции «Информационные средства и технологии». Т.З. - М.:МЭИ, 2009 - с. 169-173

7. Бородкин A.A., Толчеев В.О., Часовский A.B. Исследование зависимости точности классификации от структуры выборки// Современные технологии в задачах управления, автоматики и обработки информации: труды XVI Международного научно-технического семинара. Сентябрь 2007 г., Алушта. - Тула: Изд-во ТулГУ, 2007 - с. 244-245

8. Бородкин A.A., Толчеев В.О. Структура и функциональные возможности учебно-исследовательского программного комплекса. Международный форум информатизации МФИ-2008. Труды XVI международной научно-технической конференции «Информационные средства и технологии». Т.З. - М.:МЭИ, 2008 -с. 85-87

9. Бородкин A.A. Толчеев В.О. Применение метода потенциальной функции для классификации библиографических текстовых документов // Научная сессия МИФИ-2008. Сборник научных трудов. Т.П. Технологии разработай программных систем. Информационные технологии. - М.: МИФИ, 2008 - с. 150151.

10. Бородкин A.A., Дербенев Н.В., Толчеев В.О. Программно-алгоритмические средства обработки и анализа библиографической текстовой информации. Современные технологии в задачах управления, автоматики и обработки информации: тезисы докладов XX Международного научно-технического семинара (г. Алушта, 18-24 сентября 2011 г.) - Пенза: Изд-во ПТУ, 2011 - с. 267-268.

Подписано в печать íl. Dty, зак. Тир. п.л. /JÓ

Полиграфический центр МЭИ Красноказарменная ул., д. 13

61 12-5/2644

ФГБОУ ВПО «Национальный исследовательский университет «МЭИ»

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

Бородкин Артем Александрович

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

Специальность 05.13.01. - системный анализ, управление и обработка информации (энергетика, приборостроение, информатика, производственные

процессы)

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

Научный руководитель: д. т. н., доцент В. О. Толчеев

Москва-2012

Введение...................................................................................................................4

ГЛАВА 1. ПРОЦЕСС И МЕТОДЫ ОБРАБОТКИ ДОКУМЕНТАЛЬНОЙ ИНФОРМАЦИИ....................................................................................................12

1.1. Основные термины и определения...........................................................12

1.2. Этапы процесса обработки и анализа текстовой информации..............13

1.3. Сбор данных и формирование выборок...................................................17

1.4. Начальная и содержательная обработка текстовых документов..........19

1.5. Разведочный анализ текстовых данных...................................................21

1.6. Способы оценки точности классификации..............................................26

1.7. Непараметрические методы классификации...........................................28

1.7.1. Метод ближайшего соседа.................................................................28

1.7.2. Метод ^-ближайших соседей.............................................................30

1.7.3. Взвешенный метод Ышижайших соседей.......................................31

1.7.4. Метод потенциальных функций........................................................34

1.8. Способы устранения общих недостатков непараметрических методов .............................................................................................................................35

1.9. Целевой показатель редукции...................................................................36

Выводы...............................................................................................................41

ГЛАВА 2. РАЗРАБОТКА МЕТОДА РЕДУКЦИИ ОБУЧАЮЩЕЙ ВЫБОРКИ .................................................................................................................................42

2.1. Редуцированные методы...........................................................................42

2.1.1. Метод нахождения прототипов.........................................................43

2.1.2. Инкрементные и декрементные методы редукции..........................45

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

2.3. Критерии определения "внутренних" документов.................................54

2.4. Алгоритм выбора радиуса гиперсферы...................................................58

2.5. Модифицированный метод прототипов для объединения "внутренних" документов.........................................................................................................60

2.6. Метод редукции обучающих выборок.....................................................62

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

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

2 8.1. Формирование обучающих, тестовых и экзаменационных выборок .........................................................................................................................64

2.8.2. Настройка параметров метода редукции..........................................65

Выводы...............................................................................................................75

ГЛАВА 3. РАЗРАБОТКА И ПРИМЕНЕНИЕ МЕТОДИКИ ВЫБОРА ПРОЦЕДУР (И ПАРАМЕТРОВ) ОБРАБОТКИ И АНАЛИЗА ТЕКСТОВЫХ

ДАННЫХ НА ОСНОВЕ НЕПАРАМЕТРИЧЕСКИХ КРИТЕРИЕВ................76

3.1. Применение непараметрических критериев в задачах обработки и анализа текстовых документов........................................................................77

3.2. Основные непараметрические критерии для анализа связанных

выборок...............................................................................................................

3.2.1. Критерий Фридмана............................................................................80

3.2.2. Критерий Вилкоксона.........................................................................82

3.3. Методика выбора процедур (и параметров) обработки и анализа текстовых данных на основе непараметрических критериев.......................84

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

3.4.1. Результаты исследований на англоязычных библиографических выборках.........................................................................................................86

3.4.2. Результаты исследований на русскоязычных библиографических выборках.......................................................................................................Ю4

Выводы.............................................................................................................

ГЛАВА 4. РАЗРАБОТКА ПРОГРАММНЫХ СРЕДСТВ ДЛЯ ПРЕДВАРИТЕЛЬНОЙ ОБРАБОТКИ И АНАЛИЗА

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

4.1 Сравнительный анализ известных разработок Text Mining..................111

4.2 Структура и функциональные возможности учебно-исследовательского программного комплекса (УИПК).................................................................115

4.3. Разработка комплекса лабораторных работ по курсу «Интеллектуальные информационные системы» с использованием УИПК ...........................................................................................................................128

4.4. Применение УИПК для решения прикладных задач...........................129

Выводы.............................................................................................................135

ЗАКЛЮЧЕНИЕ....................................................................................................136

ЛИТЕРАТУРА.....................................................................................................I39

Приложение 1 Лабораторные работы..............................................................151

Приложение 2 Настройка параметров для выборок из русскоязычной

цифровой библиотеки eLibrary..........................................................................157

Приложение 3 Акты о внедрении......................................................................159

Введение

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

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

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

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

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

Анализ российских и зарубежных публикаций в области Data and Text Mining показывает, что основные усилия разработчиков сконцентрированы на построении классификаторов, обладающих высокой точностью [1,3,4,5]. Под оценкой точности в данной работе понимается отношение правильно классифицированных документов к общему числу классифицируемых документов. Для увеличения точности используются различные подходы: синтез коллективов решающих правил, организация ресурсозатратного обучения для высокоточной настройки параметров методов, увеличение размера и количества обучающих выборок, тщательное выявление информативных признаков (терминов) [6,7,8,9,10].

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

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

На современном этапе высокое быстродействие является обязательным условием применения классификаторов для решения таких задач как обработка коротких новостных сообщений в информационных агентствах, анализ вопросов, поступающих в ходе on-line конференций, автоматизированное разнесение документов по классам в больших цифровых библиотеках, реализация эффективного документооборота в крупных компаниях. Кроме того, при разработке программно-алгоритмических средств Text Mining для решения широкого круга прикладных проблем требуется учитывать режим «перегрузки» системы обработки текстовых данных, когда интенсивность обрабатываемого документального потока достигает пиковых значений.

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

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

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

Непараметрические методы (НМ) обеспечивают достаточно высокую точность, однако затрачивают значительное время на классификацию новых наблюдений. В специализированной литературе предлагаются различные модификации НМ с целью увеличения быстродействия. Эти модификации можно разделить на две большие группы: методы ускоренного поиска ближайшего соседа, в которых на этапе обучения проводится упорядочивание обучающей выборки для более быстрого нахождения ближайшего соседа (ближайших соседей) и методы редукции (сокращения) размеров обучающих выборок [10,17,18,19,20,21].

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

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

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

возможным из-за чрезвычайно высоких темпов роста объема обрабатываемой информации. Многие организации ориентируется на проведение гибридной обработки данных. В режиме пакетной обработки offline автономно от пользователя проводится формирование выборок (по заданным тематикам) и предварительная обработка документальной информации, которая включает ресурсоемкие процедуры с большим числом вычислительных операций. Затем с участием пользователя в режиме реального времени on-line проводится анализ данных: обучение, переобучение и дообучение классификаторов, анализ влияния различных факторов на точность классификации, сопоставление различных решающих правил и выбор наилучшего метода для решения конкретной задачи. Причем зачастую многие исследования повторяются неоднократно и направлены на проверку различных гипотез исследователя и, в конечном итоге, удовлетворения его информационных потребностей. Именно на этапе анализа происходят основные временные затраты пользователя и использование режима on-line позволяет существенно повысить эффективность его научно-исследовательской деятельности. Таким образом, разработка процедуры редукции обучающих выборок, ускоряющей непараметрические методы на «алгоритмическом» уровне вне зависимости от используемой техники, должна обеспечить экономию времени пользователя на стадии анализа документальной информации и оценки получаемых результатов.

Принимая во внимание вышесказанное, сформулируем цель диссертационного исследования.

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

Для достижения указанной цели необходимо:

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

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

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

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

5. Разработать и применить комплексную методику выбора процедур (и параметров) обработки и анализа текстовых данных на основе статистических непараметрических критериев.

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

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

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

1. Обоснован и исследован критерий выявления "внутренних" документов, основанный на новой формуле линейного взвешивания ^-ближайших соседей.

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

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