Содержание к диссертации
Введение
ГЛАВА 1. Обзор моделей и алгоритмов классификации объектов 13
1.1 Введение 13
1.2 Содержательная постановка задачи классификации 14
1.3 Понятие классификации. Разновидности классификаторов 16
1.4 Признаки 21
1.5 Функция расстояния (метрика) в пространстве признаков 25
1.6 Модели текста в методах классификации 29
1.7 Цели исследования 34
ГЛАВА 2 Модель для постановки и решения задачи классификации объектов, описанных текстовыми признаками. модель анализа тематической близости текстов 37
2.1 Основные определения 37
2.2 Постановка задачи классификации в общем виде 40
2.3 Модель анализа тематической близости 42
2.4 Постановка задачи классификации на основе анализа близости текстовых признаков 56
2.5 Основные результаты и выводы по главе 2 57
ГЛАВА 3 Алгоритмическое обеспечение решения задачи классификации объектов на основе анализа тематической близости естественно-языковых признаков 58
3.1 Функция тематики слова 59
3.2 Функция «часть речи в предложении» ЧР(Сл) 60 у
3.3 Функция тематической близости слов словаря 62
3.4 Функция тематического ядра SN(t) 64
3.5 Функция сателлитов S(TIp, Сл) 66
3.6 Функция расстояния (метрика) в пространстве слов 68
3.7 Построение бета-модели текста 68
3.8 Функция расстояния (метрика) в пространстве бета-моделей 70
3.9 Агрегирование свойств текстовых признаков для формирования модели группы
3.10 Алгоритм классификации 77
3.11 Общий алгоритм решения прикладных задач с применением предложенной модели и рассмотренных алгоритмов 78
3.12 Основные результаты и выводы по главе 3 79
ГЛАВА 4 Автоматизированная система классификации объектов по значениям естественно-языковых признаков. проверка применимости модели и алгоритма к решениюзадач классификации 80
4.1 Введение. Современное применение классификаций и классификаторов в России 80
4.2 Архитектура автоматизированной системы КЕТА. Аспекты реализации...82
4.3 Представление данных в системе КЕТА 84
4.4 Решение задачи классификации основных фондов 88
4.5 Расчет доверительных интервалов серии экспериментов. Оценка экспериментальных данных 101
4.6 Основные результаты и выводы по главе 4 102
Заключение 102
Список использованной литературы
- Понятие классификации. Разновидности классификаторов
- Постановка задачи классификации в общем виде
- Функция тематического ядра SN(t)
- Представление данных в системе КЕТА
Введение к работе
Актуальность темы исследования. В настоящее время в различных областях человеческой деятельности накоплено огромное количество информации о материальных и нематериальных сущностях, их свойствах, поведении и связях. Работа любого эксперта с набором понятий и сущностей всегда строится на использовании классификаций (классификацией будем называть способ объединения схожих объектов в группы).
Построение классификаторов и механизмов классификации является хорошо известной задачей искусственного интеллекта и на протяжении многих лет является одной из наиболее востребованных и интенсивно развивающихся его ветвей.
Наряду с наборами данных, содержащими только числа, все больший вес в принятии решений приобретают данные сложных, нетривиально интерпретируемых типов, главным из которых является текст. Все чаще важная для анализа информация представлена в виде текстов на естественном языке [IBM Press, 2001].
Современные задачи классификации объектов в социальной сфере тесно связаны с имеющимися классификаторами [Шаров 1997, Шатров 1997, Тришин 2005]. Очевидно, что реальные задачи классификации данных в научных и прикладных задачах могут решаться только с помощью автоматизированных систем [Поляков 2001, Поспелов 1981].
Построение эффективной системы управления сферой образования, согласно концепции информационного обеспечения индустрии образования программы «Научное, научно-методическое, материально-техническое и информационное обеспечение системы образования» (Поляков 1999) также невозможно без разработки единой системы учета и классификации объектов, описанных текстовыми атрибутами [Поляков 2000, Поляков, Кузнецов, Позднеев 2001].
Однако существующие модели естественного языка и алгоритмы анализа текстов на естественном языке, как правило, направлены на анализ текстов путем построения модели заложенных в тексте знаний. Даже наиболее развитые модели текста [Апресян 1989, Мельчук 1965, Жолковский 1967, Растье 1990, Красилов 1961] не позволяют решать задачу классификации текстовых признаков с требуемым уровнем эффективности, так как либо чрезвычайно сложны и
специфичны, либо не имеют алгоритмического обеспечения предлагаемых в них методов. Несмотря на большое количество разработанных лингвистических моделей и методов классификации текстов, задача классификации текстов на естественных языках на основании тематической близости решается недостаточно эффективно [Анисимов, Марченко 2001].
Таким образом, актуальной является задача разработки моделей и алгоритмов классификации объектов, в описании которых присутствуют текстовые признаки.
Цель работы состоит в повышении эффективности выполнения классификации объектов, описанных текстовыми признаками на основе тематической близости за счет разработки и применения новой модели, новых метрик в пространствах текстовых атрибутов, алгоритмов многоуровневой классификации. Под повышением эффективности понимается сокращение трудоемкости относительно ручной классификации при качестве классификации, не уступающем автоматизированным аналогам. Для достижения данной цели были поставлены и решены следующие задачи:
исследовать подходы к сравнению текстовых признаков, провести обзор моделей, алгоритмов и систем классификации на основании тематической близости текстовых признаков;
описать особенности рассматриваемого класса задач, постановку задачи, описать модель представления текста для задачи анализа тематической близости, сформулировать задачу классификации с применением модели текстового признака;
разработать алгоритмы решения задачи классификации на модели, в том числе алгоритмы вычисления расстояния в пространстве текстовых признаков;
реализовать модели и алгоритмы в программном комплексе, проверить работу модели и алгоритмов на реальных задачах.
Методы исследований. Для решения поставленных задач были использованы методы системного анализа, методы искусственного интеллекта, методы интеллектуального анализа данных, а также применялись положения теории объектно-ориентированного проектирования программных систем и теории проектирования реляционных баз данных.
Научная новизна работы заключается в следующем:
предложено описание текстового признака объекта классификации, отличающееся от известных возможностью представления множества вариантов связей слов в предложениях, синонимии, тематической близости слов и позволяющее рассчитывать метрику в пространстве текстовых признаков, описывающем группы специальных иерархических рубрикаторов с учетом явления многозначности слов и вариативности описаний объектов различными экспертами;
предложена новая метрика для текстовых признаков объектов классификации, отличающаяся от известных возможностью построить жадный алгоритм выбора наиболее близких групп, построен алгоритм поиска оптимального сопоставления моделей текстовых признаков объектов классификации по критерию минимальной суммы расстояний сопоставленных терминальных узлов;
предложен новый подход к оценке тематической эквивалентности понятий, отличающихся от известных совместным использованием словарей синонимов, толковых словарей, методов контент-анализа и позволяющий наполнять нужной информацией систему автоматизированной классификации, осуществлять гибкую настройку алгоритмов с учетом специфики задачи;
впервые модифицирован подход к многоуровневой классификации, отличающийся построением агрегированных описаний групп по описаниям входящих в группы объектов с возможностью вычисления расстояния по методу ближайшего соседа.
Практическая ценность. Практическая ценность работы заключается в разработке подхода к решению задачи классификации объектов по специальным иерархическим классификаторам на основании тематического сходства текстовых признаков, решением важной прикладной задачи классификации по классификатору ОКОФ.
Практическая применимость подхода доказана актом о внедрении (Акт № 1 к договору на создание и передачу научно-технической продукции № 57/732-06 от 11 июня 2006 года) и успешным применением к решению задачи классификации основных фондов по общероссийскому классификатору основных фондов.
Достигнуты следующие результаты:
решены прикладные задачи классификации объектов, описанных естественноязыковыми признаками (по общероссийскому классификатору основных фондов);
описаны и реализованы общие алгоритмы построения бета-моделей текста, реализованы алгоритмы вычисления расстояния в пространствах слов и бета-моделей;
спроектирована и реализована «Автоматизированная система классификации объектов».
Апробация работы. Работа имеет следующие внедрения и апробации:
задача классификации основных фондов на примере ВУЗов ЮФО, система «КЕТА» применялась для классификации реальных наборов данных, обработано более 40 000 объектов основных фондов;
портал (ООО «ИНТЕРВОЛГА»), модуль автоматической классификации поступающих ресурсов по многоуровневому рубрикатору (Акт № 1 к договору на создание и передачу научно-технической продукции № 57/732-06 от 11 июня 2006 года);
программа зарегистрирована в Отраслевом фонде алгоритмов и программ (Свидетельство о регистрации №8210 от 26.04.2007).
Публикации. Основное содержание диссертации нашло отражение в 7 опубликованных научных работах, в том числе в 2 статьях в периодических и научно-технических изданиях, выпускаемых в Российской Федерации, в которых ВАК рекомендует публикацию основных научных результатов диссертаций; в одном свидетельстве об официальной регистрации программы для ЭВМ.
Структура и объем работы. Диссертация состоит из введения, четырех глав, выводов и приложений. Диссертация содержит 116 страниц основного текста, 13 рисунков, 80 формул. Библиографический список включает 138 наименований. Общий объем работы - 143 страницы.
Понятие классификации. Разновидности классификаторов
Определение 1.1. Основание классификации. Основанием классификации назовем некоторый важный признак объекта, используемый для разделении множества, обладающий тем свойством, что при различных значениях этого признака объекты должны попасть в разные группы классификатора.
В данном исследовании основанием классификации является тематическая близость текстов, тематическая близость описываемых понятий.
Традиционно выделяют две принципиально разных разновидности классификаций: фасетную и иерархическую [17].
Фасетная классификация. Под фасетной классификацией понимают способ разбиения множества объектов на основе значений ряда равнозначных признаков. Особенности и примеры применения фасетной классификации приведены в Приложении А. Основным преимуществом фасетного метода является гибкость структуры. Изменения в любом из фасетов не оказывают существенного влияния на все остальные. Недостатками фасетного метода классификации являются неполное использование емкости, сложность составления фасетов при разнообразной природе классифицируемых объектов.
Иерархическая классификация. Под иерархической классификацией понимают метод, при котором множество объектов последовательно делится на множества, образующие разбиение множества верхнего уровня, постепенно конкретизируя объект классификации. При этом основанием деления служит некоторый выбранный признак. Особенности и примеры применения иерархической классификации приведены в Приложении А. Основными преимуществами иерархического метода является большая информационная емкость. Значительным недостатком иерархической классификации является слабая гибкость структуры, обусловленная фиксированным основанием деления и заранее установленным порядком [28][46] [87].
Несмотря на перечисленные отличия, фасетная и иерархическая классикации обладают рядом общих свойств: непересекаемость классов, стремление к полноте, трудность отнесения объекта к классу вследствие отсутствия формально заданных критериев. Можно утверждать, что ввиду широкого применения классификаторов актуальными являются задачи автоматизации классификации объектов, описанных различными типами признаков.
Зайченко в [55] рассматривает общую постановку задачи классификации, которая требует, чтобы объект всегда описывался одним и тем же составом признаков и допускает некоторые варианты задания значений признаков, в том числе дискретные признаки (0, не определено или 1), конечное число значений или произвольное число из ограниченного интервала.
Рассматриваемые в большинстве современных работ методы предполагают, что анализу подвергаются лишь признаки, отнесенные к шкалам порядков, и игнорируют все остальные.
Постановка задачи классификации документов, рассмотренная в [62] трактует классификацию как построение приближенного отображения множества объектов на множество заданных классов, при этом описание характеристик документов по сути сводит задачу к ранее рассмотренной задаче классификации чисел [55]. В этой постановке модель текста такова, что он описывается рядом целочисленных или дробных характеристик, каждой из которых ставится в соответствие вес ее вклада в описание объекта, и объект в целом описывается рядом взвешенных числовых характеристик.
Однако важнейшим нерешенным вопросом остается способ описания текстов числами. Далее будет показано, что наиболее распространенные модели текста для задач классификации чрезвычайно упрощают понятие текста и не учитывают тематических отношений текстов. 1.3.3 Методы оценки качества классификации
В классической [51] постановке задачи построения систем распознавания выделяют этапы обучения, экзамена и эксплуатации. На этапе экзамена распознавателю последовательно предъявляется набор образов, которые он должен отнести к одному из заданных классов. Ошибкой классификации называют отнесение образа к иному классу, нежели указано в экзаменационной выборке.
Выделяют ошибки двух родов [85]: ошибку ложного отнесения объекта к классу и ошибку нераспознавания действительно принадлежащего классу объекта. Поскольку в рассматриваемой постановке задачи предполагается, что классы обладают свойством разбиения универсума, число ошибок первого рода всегда равно числу ошибок второго рода.
Значение функции ошибки равно количеству ошибок или доле их в некоторой тестовой выборке.
При отсутствии экзаменационной выборки или в условиях неопределенности вводят внутренние меры качества [55]. Наиболее подробно такие функции и теоретическое обоснование их введения рассматриваются в теории кластерного анализе} [17]. Значение функции неотрицательно и тем меньше, чем лучше классификация с точки зрения внутренней меры качества.
Постановка задачи классификации в общем виде
Введем понятие ослабевания близости (меры затухания близости) и обозначение г для этой величины.
Допустим, в словаре синонимов имеется запись о близости (или эквивалентности) А- В и В- С. Тогда согласно рассмотренному в разделе 2.3.5 явлению частичной транзитивности отношения близости близость понятий А и С имеет меньшее значение количественной меры, нежели каждая из связей А- В и В- С.
Рассмотрим аналогию с физической проводимостью. Допустим, между точками А и С имеется разность потенциалов, притом что имеются проводники между точками А и В с некоторой проводимостью Пдв и между точками В и С с некоторой проводимостью Пво Согласно известной из физики модели прово димость пары проводников А- В и В- С каждого проводника является величи на ПАС =-—. —.—. Аналогично тому, как в физике существует модель про /пАВ+/пвс водника электрического тока, в данной модели семантическая связь рассматривается как проводник близости. Введем величину ЭАС (2.29) как меру транзитивной близости слов А и С, вычисленную по паре связей А- В и В- С. g= и к и (2-30) /э +/э / JAB / - ВС Кроме предложенного формального способа (1.32) для измерения реальной близости пары слов могут применяться экспертные оценки. Оценка эксперта в каждом случае будет в большей или меньшей степени расходиться с вычисленным значением. Если рассмотреть все связи некоторой обучающей выборки и усреднить отношение оценки эксперта к вычисленной согласно (1.32) величине, получим количественную меру ослабления близости данной обучающей выборки.
Количественная мера ослабления связи предполагается постоянной словаря и неизменной в рамках задачи. Распространив вычисленную таким обра зом константу г на весь словарь связей, получим возможность рассчитывать оценки близости, приближенные к экспертным. Будем называть величину г мерой ослабевания близости.
Величина т является безразмерной, может принимать значения от 0 до 1. При т =0 близость не передается дальше первой связи (полное затухание), при т=\ затухание отсутствует. Любые значения г допустимы, однако на наш взгляд, наиболее оправданны значения от 0,5 до 0,9. Тогда отношение реальной близости понятий А и С Эдс к величине ЭАС и называется мерой ослабевания близости (1.33). т= 5АС (2.31) /э +/э или, проведя простейшие преобразования и выполнив подстановку (1.32), запишем ЭАС = т-эГс (2.32) Способ вычисления Эдс и т рассматривается далее.
В общем случае тематика текста может определяться различными его свойствами, лексикой, синтаксисом и тому подобным. В данном исследовании предлагается следующая упрощенная модель текста. Воспользуемся определением «тематического ядра» текста. Под тематическим ядром (СЯ), то есть набором информации, в наибольшей степени определяющей тематику текста, понимается совокупность тематик существительных и устойчивых сочетаний, употребленных в именительном падеже или базовой форме. Чтобы описать СЯ, определим функцию SN(t) (2.33) VteT:SN(t)={snl;sn2;...} (2.34) Где t - текст; SN(t) - функция тематического ядра; srij - элементы тематического ядра. Будем полагать, что в меньшей степени тематика текста определяется также:
Существительными, употребленными не в именительном падеже, связанными с элементами СЯ; Прилагательными (в т.ч. числительными и причастиями), связанными с элементами СЯ. Будем полагать, что тематика текста не зависит от: Наречий, междометий, частиц (кроме «не»); Вводных предложений; Неизвестных (отсутствующих в словаре) слов. Будем считать заданной функцию сателлитов S(Up, Сл) (2.35) где Сл - слово, Пр - предложение. Значением функции для заданного слова в предложении является варианты списков связанных с ним слов. VQ с Пр: S(nP,Cn)= {ЗД;...} (2.36) Где 81=(Сл;;Сл2;...;Сл1;) (2.37) Где Слі - первое связанное слово из варианта і. Вследствие того, что в естественном языке возможны ситуации, которые требуют анализа на уровне контекста и грамматики (Примеры: Эти типы стали есть в прокатном цехе), функция S в модели определяет несколько вариантов списков связанных слов. Допускается, что для таких сложных случаев функция S возвращает список всех возможных вариантов. Для описания тематики текста через тематику слов воспользуемся известной моделью И-ИЛИ дерева. Корнем дерева является определяемый текст. Первый уровень является И-уровнем и содержит элементы СЯ. Второй уровень является ИЛИ-уровнем и содержит варианты списка сателлитов для каждого элемента СЯ. Третий уровень является И-уровнем и содержит слова-сателлиты. Четвертый уровень является ИЛИ-уровнем и содержит слова словаря, сила семантической связи которых с соответственными элементами 3 уровня больше заданного порога. Пятый уровень является И-уровнем и содержит все значения функции С для соответственных элементов 4 уровня. Таким образом, любой текст в рамках модели описывается И-ИЛИ-деревом. Будем называть такое представление модели текста бета-моделью (или И-ИЛИ деревом модели текста).
Для того, чтобы сравнить два текста, нужно сопоставить их бета-модели. Модели сравнения графов рассматриваются далее.
Синонимами понятия «группа», используемого в данной работе, являются такие термины, как «класс», «кластер», «подмножество».
Согласно приведенному в разделе 1.7 анализу представления текста в системах классификации, для групп существуют модели, основанные на функциях подобия, нейросетевые модели со скрытой логикой, и модели, использующие Байесовскую логику.
Рассмотренная в первой части Главы 2 модель отличается детальным анализом текста и предложений, описание текста представляет собой сложный абстрактный объект «бета-модель». В связи с этим обстоятельством применение нейросетевых алгоритмов представляется неоправданным, т.к. представление такого дерева для нейросетевого анализа является нетривиальной и сложной задачей. Модель фильтра Байеса также малоприменима для моделирования зависимостей принадлежностей объектов группам в данном классе задач, т.к. различных бета-моделей и групп может быть огромное количество, и формиро вание обучающих последовательностей для такой модели потребует неоправданных затрат времени и ресурсов, особенно при учете относительно низкой эффективности современных байесовских фильтров для сложных задач и большого набора категорий.
Функция тематического ядра SN(t)
Сравнение И-ИЛИ-деревьев, а именно вычисление расстояния между ними при заданной функции расстояния на множестве листьев, является частным случаем задачи сравнения деревьев, а сравнение деревьев, в свою очередь, сводится к сопоставлению графов. Задача сопоставления графов детально рассмотрена в ряде современных исследований [14][3][13]. Как уже говорилось, одной из основных процедур в большинстве современных алгоритмов является выбор варианта сопоставления. Большинство алгоритмов пытаются найти в сравниваемых графах наибольший общий подграф (дерево) и далее сравнивать только различные подграфы [12].
Рассмотрим задачу сопоставления двух бета-моделей Б1 и Б2.
Поскольку корневая вершина определена, вариантом сопоставления в данном случае является выбор варианта сопоставления первого уровня моделей. Первый уровень является И - уровнем, следовательно, для полного сопоставления нужно провести число сопоставлений, равное числу размещений п из ш, где N - число вершин первого уровня в Б1, М - число вершин первого уровня в Б2, п - меньшее из М и N, m - большее из М и N. Каждое сопоставление должно быть оценено с точки зрения оптимальности решения. Очевидным представляется выбор пар сопоставления первого уровня согласно выбранным парам при сравнении быстрых портретов (рис 3.6.), однако такой выбор не гарантирует минимальности величины Dsat.
Поскольку деревья могут иметь разную структуру, не гарантировано, что для каждого листа найдется сопоставление. С точки зрения семантики модели имеет значение покрытие элементов И-уровней, ИЛИ-уровни менее важны, допустимо обработать лишь один из элементов на каждом уровне. Допустим, мы получили некое сопоставление Соп(А,В) с расстоянием Dsat. Подсчитаем число Norphan узлов на И-уровнях, чьи потомки на нижних уровнях не участвуют ни в одном сопоставлении листьев. Назначим штраф в Ltax за каждую такую вершину. Тогда с учетом штрафа для сопоставления Соп(А,В) расстояние вычисляется согласно (3.13). D sat = Dsat + Norphan Ltax (3.13) На каждом следующем из уровней дерева возникает аналогичная ситуация, когда требуется из многих вариантов сопоставлений выбрать наилучшее, выполнив полный перебор или оценив с помощью эвристик результативность того или иного сопоставления. Общая размерность задачи выбора оптимального сопоставления двух деревьев глубиной в 4 уровня методом полного перебора растет экспоненциально с ростом длины текста и превышает всякие разумные пределы.
К сожалению, не удалось сконструировать жадный алгоритм или алгоритм, основанный на методе ветвей и границ, выбирающий оптимально сопоставление «сверху», то есть анализирующий сопоставляемый поддеревья, хотя построение такого алгоритма представляется необходимым, чтобы сократить множество рассматриваемых вариантов и обеспечить нахождение оптимального решения.
Для решения задачи предлагается альтернативный подход: поиск оптимального сопоставления «снизу», то есть путем анализа списков листьев. Кратко его можно изложить следующим образом: поскольку определена лишь операция сравнения листьев дерева, а само дерево имеет фиксированную глубину, фактически подвергаться сравнению будут пары из списка листьев. Расстоянием в этом случае будет являться сумма расстояний между сопоставляемыми парами.
Очевидно, что для наименьшего расстояния в этом случае недостаточно для каждого листа первого (меньшего) дерева выбрать ближайший лист второго (простейший жадный алгоритм). Наличие структуры верхних уровней ограничивает свободу выбора по такому критерию, так как вынуждает выбирать только пары листьев, относящиеся к одной паре поддеревьев, кроме того, доказать оптимальность выбора на первом шаге без анализа ситуации в целом невозможно. Рассмотрим простой пример: пусть имеются две пары листьев и матрица расстояний имеет вид, приведенный в таблице 3.1 (на пересечениях -расстояния).
Таким образом имеется задача, которую не представляется возможным решить простым жадным алгоритмом, а полный перебор вариантов сопоставлений невозможен по причине большой размерности модели. Сформулируем задачу поиска оптимального сопоставления в терминах сопоставлений и анализа запрещенных комбинаций.
Пусть существует два списка листьев А и В первого и второго сравниваемых деревьев, будем обозначать их элементы а и b соответственно, длины [А] и [В] соответственно. Каждому элементу каждого списка поставим в соответствие набор из трех уникальных меток нетерминальных вершин дерева, помечающих путь от этого элемента до корня его дерева (см рис 3.7).
Метками каждого листа являются имена узлов бета-модели, через которые проходит путь от корня до листа: на приведенном примере листу С Слг1) следует приписать метки: {"S(snj)=S} ";"srii "; "Сл2 "} (путь и узлы выделены).
Рангом совпадения списков L(ax) и L(ay) назовем число совпавших меток при Рис ЪЛ Формирование меток листьев последовательном сравнении. На приве денном примере списки меток узлов Сі(Сл2) и С)(СЛі ) совпадают с рангом 2, а узлы С Слг1) и Сі(Сл23) имеют ранг совпадения 0.
Будем называть построением комбинации следующую процедуру. На первом шаге для первого элемента списка A aj выбирается для сопоставления произвольный элемент списка В bj. На каждом следующем шаге для і-го элемента списка А могут быть выбраны только те из элементов списка В, выбор которых не противоречит ранее сделанным сопоставлениям. Критерии определены следующим образом. Пусть элемент щ со списком меток Ца,) сопоставлен с элементов bj, имеющим список меток L(bj). Сопоставление непротиворечиво, если выполняются следующие требования: Во-первых, все листья ак, имеющие список меток меток L(a;), должны сопоставляться только с элементами bm, имеющими список меток L(bj). Во-вторых, все листья, ак, списки меток которых совпадает с L(aj) с рангом г, должны сопоставляться только с элементами bm, имеющими список меток L(bm), совпадающими с bm с рангом г. Если удается довести сопоставление до конца, то есть составить непротиворечивую цепочку сопоставлений, то построение комбинации является успешным.
Задача оптимального сопоставления заключается в выборе допустимой комбинации, для которой сумма расстояний в парах минимальна. Сформируем матрицу пар расстояний, содержащую [А] строк и [В] столбцов соответственно. Выберем наименьшее число в матрице, возьмем за исходное сопоставление строку и столбец, содержащие это число. Удалим из матрицы эту строку и этот столбец. Соблюдая требования непротиворечивости сопоставления, найдем некоторое допустимое сопоставление. Такое сопоставление не будет заведомо оптимальным по изложенным ранее причинам, однако будет достаточно близко к оптимуму. Обозначим расстояние для данного сопоставления как Dbest
Представление данных в системе КЕТА
В качестве широко известного прототипа рассмотренной в диссертационном исследовании задачи можно назвать задачу деления наборов электронных писем на две группы: рекламные и содержательные. Родоначальником всех применяемых в настоящее время классификаторов писем является Наивный Байесовский Классификатор (далее НБК).
А.Калининым в [62] проведено исследование практической эффективности различных версий НБК и комбинаций его с другими методами, в результате чего сделан вывод, что наименьшее число ложных срабатываний и наибольшую устойчивость к переобучению проявил НБК в сочетания с фильтром Фишера [8].
Особенностями постановки задачи и доступных автору реализаций метода является принципиальное отсутствие многоуровневости классификатора и учета связанных с этим обстоятельств.
Для того, чтобы провести независимое и адекватное сравнение, необходимо сформулировать условия эксперимента, соответствующие постановкам задачи для фильтра Фишера и предлагаемого подхода.
Характеристика эксперимента «Группы верхнего уровня» по сравнению метода НБК-Фишера и системы КЕТА. Экспериментальные данные представляют собой 2000 обучающих примеров, равномерно разбитые по 8 группам верхнего уровня классификатора (статистическая характеристика реальных задач отличается от экспериментальной: в разных учреждениях и в разные периоды времени распределение ОФ по группам верхнего уровня непостоянно; вследствие невозможности учета всех факторов принято решение о равномерном распределении для чистоты эксперимента). Экспериментальные данные очищены от всех коллизий. Единичным экспериментом является следующая последовательность процедур: 1. Случайное разделение (50% и 50%) множества примеров на обучающее и тестовое подмножества. 2. Проведение обучения НБК и настройки параметров системы КЕТА по обучающей выборке. 3. Проведение тестовой классификации с подсчетом совпадений. Для формирования серии проведем 100 единичных экспериментов. В серии рассчитаем: среднюю доля совпадений, среднеквадратическое отклонение доли совпадений, выделим примеры, вызвавшие в среднем наибольшее число ошибок (для экспертного анализа).
Результаты эксперимента «Группы верхнего уровня» приведены в таблице 4.5. Развернутый протокол эксперимента приведен в Приложении Е.
Число единичных экспериментов Характеристики метода НБК-Фишера Характеристики исследуемого предложенного метода Средняя доля совпадений Среднеквадратическое отклонение Средняя доля совпадений Среднеквадратическое отклонение 100 0,724 0,02296 0,756 0,0088 Характеристика эксперимента «Группы нижнего уровня» по сравнению метода НБК-Фишера и системы КЕТА. Экспериментальные данные представляют собой 2000 обучающих примеров, равномерно разбитые по 8 группам нижнего уровня классификатора подгруппы «Машины и оборудование». Экспериментальные данные очищены от всех коллизий. Стадией эксперимента является аналогичная предыдущему последовательность процедур.
Для формирования серии проведем 100 единичных экспериментов. В серии рассчитаем: среднюю доля совпадений, среднеквадратическое отклонение доли совпадений, выделим примеры, вызвавшие в среднем наибольшее число ошибок (для экспертного анализа).
Результаты эксперимента «Группы нижнего уровня» приведены в таблице ,4.6. Развернутый протокол эксперимента приведен в Приложении Е. Результаты эксперимента «Группы нижнего уровня». Число единичных экспериментов Характеристики метода НБК-Фишера Характеристики исследуемого предложенного метода Средняя доля совпадений Среднеквадратическое отклонение Средняя доля совпадений Среднеквадратическое отклонение 100 0,321 0,01376 0,658 0,00939
Характеристика эксперимента «Реальные данные» по сравнению метода НБК-Фишера и системы КЕТА. Экспериментальные данные представляют со бой 200 обучающих примеров, равномерно разбитые по 4 группам нижнего уровня классификатора разных подгрупп. Экспериментальные данные содержат коллизии. При обучении фильтра НБК-Фишера обработка коллизий не проводилась, при обучении КЕТА применялись методы «мягкого» разрешения. При контроле коллизии разрешались «мягко».
Стадией эксперимента является аналогичная предыдущим последовательность процедур. Для формирования серии проведем 100 единичных экспериментов. В серии рассчитаем: среднюю доля совпадений, среднеквадратическое отклонение доли совпадений, выделим примеры, вызвавшие в среднем наибольшее число ошибок (для экспертного анализа). Результаты эксперимента «Реальные данные» приведены в таблице 4.7. Развернутый протокол эксперимента приведен в Приложении Е. Таблица 4.7 - Результаты эксперимента «Реальные данные». Число единичных экспериментов Характеристики метода НБК-Фишера Характеристики исследуемого предложенного метода
