«БИНАРНЫХ РЕШАЮЩИХ ДЕРЕВЬЕВ ...»

Таврический национальный университет им. В.И. Вернадского

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

ДЮЛИЧЕВА Юлия Юрьевна

УДК 519.68

МОДЕЛИ КОРРЕКЦИИ

РЕДУЦИРОВАННЫХ БИНАРНЫХ РЕШАЮЩИХ ДЕРЕВЬЕВ

01.05.01 – Теоретические основы информатики и кибернетики

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

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

доктор физико-математических наук, профессор ДОНСКОЙ Владимир Иосифович Симферополь –

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ ……………………………………………………………………. Раздел 1. Методы синтеза и редукции решающих деревьев: обзор и задачи исследования ……………………………………………... 1.1. Постановка задачи распознавания и основные понятия теории решающих деревьев ……………………………………………… 1.2. Задача синтеза решающих деревьев. Выбор критерия ветвления……………………………………………………………. 1.3. Задача редукции ветвей решающих деревьев. Выбор критерия остановки ветвления ……………………………………………….. 1.4. Выводы ……………………………………………………………. Раздел 2. Методы оценивания решающих деревьев ………………………. 2.1. Оценивание бинарного решающего дерева на основе подхода к закономерности как неслучайности …………………………... 2.2. Обоснование редукции ветвей решающего дерева на основе подхода к закономерности как неслучайности ………………….. 2.3. Оценка VCD для основных классов решающих функций, представленных решающими деревьями ………………………… 2.3.1. Оценка VCD класса решающих функций, представленных решающим деревом ограниченного ранга ……………………………………………………….. 2.3.2. Оценка VCD класса решающих функций, представленных бинарным решающим деревом с двумя классами…………………………………………………… 2.4. Выводы……………………………………………………………... Раздел 3. Алгоритмы синтеза и принятия решений эмпирическим решающим лесом …………………………………………………... 3.1. Эмпирический решающий лес: основные определения ……..….. 3.2. DFBSA – последовательный алгоритм синтеза эмпирического решающего леса по ссылкам …………………………….……… 3.3. Алгоритмы принятия решений эмпирическим решающим лесом 3.4. Алгебраическая алгоритмическая модель коррекции rнекорректного эмпирического леса ……………………………... 3.5. Оценка VCD класса решающих функций, представленных rредуцированным эмпирическим лесом …………………..………. 3.6. Выводы …………………………………………………………….. Раздел 4. Программная реализация и апробация алгоритма DFBSA синтеза эмпирического решающего леса…………………………. 4.1. Программная реализация алгоритма синтеза эмпирического решающего леса ………………………………………………….… 4.2. Апробация алгоритма DFBSA синтеза эмпирического решающего леса…………………………………………………….. 4.3. Выводы …………………………………………………………….. ЗАКЛЮЧЕНИЕ ………………………………………………………………......

ВВЕДЕНИЕ

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

Актуальность темы.

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

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

Начиная от первых научных работ Ховленда (Hoveland), Ханта (Hunt) и А.Ш.

Блоха в 50-60-х годах XX века, исследователи и разработчики информационных систем во всем мире по сей день активно изучают методы анализа, синтеза и редукции РД и публикуют результаты по теории и практическому использованию решающих деревьев. В связи с нежелательностью усложнения РД, являющегося результатом “перенастройки” на обучающую выборку, особенно актуальной является проблема обоснования ограничения сложности решающих деревьев. Эта проблема с точки зрения структуры РД связана с редукцией решающих деревьев.

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

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

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

Связь с научными программами, планами, темами.

Диссертационная работа выполнена согласно плану научноисследовательской работы кафедры информатики Таврического национального университета им. В.И. Вернадского по госбюджетной тематике на 2001-2004 г.г.

«Разработка гибридной универсальной программной оболочки для построения экспертных систем и логических систем поддержки принятия решений», № государственной регистрации работы 0102U001575.

Цели диссертационной работы:

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

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

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

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

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

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

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

4. Получить оценку сложности эмпирического решающего леса и изучить распознавания.

точности классификации.

теоретических результатов, полученных в диссертации.

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

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

1. Обоснован процесс редукции ветвей РД на основе вероятностного стандартных обучающих таблицах конъюнктивных закономерностей как ветвей РД заданного ранга и в целом – оценки возможности “случайного” обнаружения РД-структуры заданной сложности.

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

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

исследована сложность и получена оценка VCD класса решающих правил, порождаемых эмпирическим решающим лесом.

5. На основе алгебраического подхода к распознаванию построена модель алгебраической коррекции r-некорректного эмпирического леса.

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

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

Личный вклад.

Все представленные в диссертации результаты получены лично автором.

Научному руководителю профессору Донскому В.И., соавтору работ [20, 22, 23], принадлежат постановки задач и часть совместно проведенных экспериментов с использованием программного комплекса “Дуэль” [21].

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

Результаты работы докладывались и обсуждались на Международной научно-практической конференции “Знание – Диалог - Решение” (СанктПетербург, июнь, 2001 г.); Международной конференции по индуктивному моделированию (Львов, май, 2002 г.); IV Международной научной конференции «Интеллектуализация обработки информации» (Алушта, июнь, 2002 г.);

Международной научной конференции “On Problems of Decision Making and Control under Uncertainties” (Алушта, сентябрь, 2003 г.); 11-й Всероссийской конференции “Математические методы распознавания образов” (Пущино, ноябрь, 2003 г.); на научных конференциях профессорско-преподавательского состава факультета математики и информатики Таврического национального университета им. В.И. Вернадского (2002, 2003 гг.); на научном семинаре кафедры информатики Таврического национального университета им. В.И.

Вернадского.

Публикации. Перечисленные результаты отражены в 11 публикациях, квалификационных изданий Украины, утвержденных ВАК Украины; 5 статей в научных журналах и сборниках научных работ; 3 публикации в тезисах научных конференций.

Структура и объем работы. Содержание работы изложено в рукописи, состоящей из 108 страниц, 12 рисунков, 8 таблиц.

Диссертационная работа включает введение, четыре раздела и заключение.

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

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

В разделе 3 диссертационной работы описана новая классифицирующая модель – эмпирический решающий лес (подраздел 3.1); приведен алгоритм синтеза эмпирического решающего леса (подраздел 3.2), а также различные алгоритмы принятия решений эмпирическим решающим лесом (подраздел 3.3) – последовательный алгоритм принятия решений с переходами по “ссылкам”, алгоритм принятия решений на основе наиболее “компетентной” ветви РД эмпирического решающего леса, алгоритм принятия решений на основе непротиворечивые логические описания классов в виде дизъюнктивных алгебраического подхода построена модель коррекции r-некорректного эмпирического решающего леса (подраздел 3.4); получена оценка VCD rредуцированного эмпирического леса (подраздел 3.5), позволяющая сделать вывод о том, что переход от единичного решающего дерева к r-редуцированному эмпирическому лесу не изменяет порядка VCD. В тоже время обеспечивается коррекция, позволяющая настроиться по обучающей выборке на правильную классификацию как можно большего числа объектов.

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

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

МЕТОДЫ СИНТЕЗА И РЕДУКЦИИ РЕШАЮЩИХ ДЕРЕВЬЕВ:

ОБЗОР И ЗАДАЧИ ИССЛЕДОВАНИЯ

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

Методы распознавания образов хорошо зарекомендовали себя при решении формализованных областях, при наличии трудно выявляемых нетривиальных закономерностей между признаками. К настоящему времени разработано несколько основных направлений в теории распознавания, объединяющих сотни конкретных алгоритмов и методов. В качестве таковых следует отметить перцептронные модели, ведущие свое начало от работ Ф.Розенблатта [38, 42], метод потенциальных функций [38], статистические модели распознавания [3, 42, 70, 161], модели распознавания, основанные на построении кусочно-линейных (или более сложных) разделяющих поверхностей в признаковом пространстве [31, 32, 33, 34], алгоритмы, основанные на построении решающих деревьев [2, 7, 8, 9, 12, 22, 41, 42, 44, 45, 52, 60], структурные (лингвистические) методы [42, 49], модели частичной прецедентности [33, 42], алгебраический подход Ю.И.Журавлева [30, 31, 32, 33], нейросетевые алгоритмы [42], методы, основанные на теории нечетких множеств [42] и др. Основанные на различных идеях, гипотезах и принципах, а также их сочетаниях, эти подходы имеют свои достоинства и недостатки, различные требования к исходным данным, ограничения на области применения. Однако все они сводятся к поиску полезной информации в пространстве возможных объектов и ее корректному обобщению.

Герберт Симон определил обучение следующим образом. “Обучение – это любое изменение в системе, приводящее к улучшению решения задачи при ее повторном предъявлении или к решению другой задачи на основе тех же данных” [42]. Это краткое определение затрагивает множество вопросов, связанных с разработкой обучаемых программ. Обучение обычно подразумевает обобщение на основе накопленного опыта. Поскольку область всевозможных обучающих данных обычно достаточно широка, обучающая система заведомо не может обработать все возможные объекты, и полученный ограниченный выборочный опыт она должна корректно распространить на недостающие объекты. Такая задача эмпирической индукции (induction) – обобщения обучающих данных (выборки) – является центральной для обучения и лежит в основе теории распознавания образов. Для большинства задач имеющихся в наличии данных недостаточно, чтобы гарантировать получение в результате обобщения точного решения. Поэтому обучающие системы неизбежно должны обобщать информацию эвристически, т.е. отбирать те аспекты, которые, скорее всего, окажутся полезными в будущем. Такой критерий отбора иногда называют индуктивным порогом (inductive bias) [42].

Суть задачи обучения распознаванию по прецедентам состоит в следующем [19].

Известно, что некоторое множество M может быть представлено в виде объединения конечного числа собственных подмножеств K1, K 2, K, K l так что M = K j. Эти подмножества называются классами, а элементы множества M – допустимыми объектами. Допустимые объекты, информация о которых получена на основе опыта, называют прецедентами. Точной информации о классах нет: для них неизвестны ни аналитическое описание, ни алгоритмический способ проверки принадлежности произвольного допустимого объекта M 1 K1, M 2 K 2, K, M l K l, для которых известно точно: если допустимый объект x принадлежит подмножеству M j, то он принадлежит классу K j j = 1, l.

Можно сказать, что предикаты " x K j " частично заданы на множестве Требуется, используя только указанное множество M 0, называемое обучающим, найти правило распознавания, позволяющее для любого допустимого объекта x M вычислить предикаты " x K j ", j = 1, l. Сложность данной задачи заключается в том, что, располагая ограниченной информацией, необходимо её экстраполировать, а сделать это можно различными способами.

Если K j K q = для 1 j < q l, то говорят, что поставленная задача является задачей обучения распознаванию с непересекающимися классами. В противном случае, если найдутся такие j и q, что K j K q, речь идет о задаче с пересекающимися классами. Случай пересекающихся классов может быть сведен к случаю непересекающихся классов путем выделения областей пересечения в “новые” классы. Очевидно, что для задач с непересекающимися классами, экстраполирующее правило определяется некоторым разбиением признакового пространства на l областей.

При решении задачи распознавания образов по прецедентам используется следующая эмпирическая гипотеза [36]: считается, что при выборе объектов подмножества M 0 из множества M не делается предпочтения одного объекта другому, т.е. объекты подмножества M 0 из генеральной совокупности M выбираются случайным образом.

В геометрической интерпретации задача обучения распознаванию по прецедентам имеет следующий смысл. Пусть выбрано некоторое признаковое пространство X n размерности n, каждый реальный объект заменяется своей векторной моделью, т.е. описанием в виде последовательности значений признаков. Естественно называть модель объектов точкой в многомерном пространстве. Точки из множеств M 1, K, M l, образующие в пространстве признаков X n конечные множества, должны быть разделены некоторым набором гиперповерхностей так, чтобы в любом полученном в результате разделения X n подмножестве содержались точки только одного класса из обучающего множества M 0.

Совокупность векторов-объектов из обучающего множества M 0 может быть записана в виде таблицы Tmnl, называемой стандартной таблицей обучения, где m – число объектов обучающего множества; n – размерность признакового пространства (число признаковых предикатов (признаков)); l - число классов. В таблице обучения Tmnl отдельно выделен столбец с номером n+1, называемый целевым, содержащий метки классов, которым принадлежат объекты обучающего множества. Обычно считается, что задана непротиворечивая таблица обучения, т.е. в ней нет ни одной пары одинаковых объектов с указанной принадлежностью к разным классам.

В настоящей диссертационной работе к обучающей информации – таблице Tmnl - предъявляется дополнительное условие: значения предикатов " x K j ", j = 1, l, являются достоверными на множестве Tmnl. В дальнейшем всюду таблицы обучения Tmnl полагаются булевыми: если (x1,K, x j,K, xn ) = ~ Tmnl, то xi {0, 1}, i = 1, n.

Задача обучения распознаванию образов по прецедентам состоит из двух этапов: обучение по эмпирическим данным и собственно распознавание.

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

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

Привлекательность решающих деревьев определяется возможностями:

структурные закономерности в данных;

- синтеза наборов эмпирических закономерностей в виде конъюнкций и - простой организации процедуры принятия решений;

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

максимального использования всей начальной обучающей информации;

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

Для дальнейшего изложения понадобятся следующие основные понятия и факты.

ациклический граф с выделенной вершиной, называемой корневой вершиной (корнем) дерева.

Конструктивно дерево можно определить рекуррентно следующим образом [1].

1. Единственная вершина является деревом; эта же вершина является 2. Пусть n – это вершина, а T1, T2, K, Tk - деревья с корнями n1, n2, K, nk соответственно. Можно построить новое дерево, сделав n “родителем” Путем из вершины n1 в вершину nk называется последовательность вершин n1, n2, K, nk, где для всех i, 1 i k, вершина ni является “родителем” вершины ni +1. Длиной пути называется число, на единицу меньшее числа вершин, составляющих этот путь. Глубина вершины определяется как длина пути (он единственный) от корня до этой вершины.

Определение 1.2 [19]. Бинарным (ориентированным) деревом (БД) называется дерево, имеющее следующие свойства:

- в корневую вершину не входит ни одна дуга;

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

Вершины бинарного решающего дерева, имеющие две выходящие дуги, называются внутренними или нетерминальными вершинами, а остальные вершины – терминальными или листьями.

Определение 1.3 [19, 61]. Решающим называется бинарное дерево (БРД), обладающее следующими свойствами:

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

- две дуги, выходящие из внутренней вершины помечены значениями, принимаемыми предикатом в вершине, из которой они выходят;

- концевые вершины (листья) помечены метками классов w1, w 2, K, w l ;

- ни в одной ветви дерева нет двух одинаковых вершин.

Легко видеть, что БРД представляет собой алгоритмическое отображение ABDT : B n ® {w1, w 2, K, w l }, где B n = {0,1}n – множество вершин единичного n мерного куба, {w1, w 2, K, w l } - множество меток классов, образующих разбиение множества M.

На рисунке 1.1 для примера представлено бинарное решающее дерево с указанием решающих правил для каждого из классов w1 и w 2.

Рис 1.1. Бинарное решающее дерево, задающее решающие правила для классов Определение 1.4 [19]. Решающее дерево, не совершающее ни одной ошибки на Tmnl, называется корректным решающим деревом относительно таблицы обучения, в противном случае – некорректным решающим деревом.

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

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

Для любого булевого набора a Tmnl, принадлежащего классу w (a ), вычисляются числа k1 (a ) наборов b Tmnl таких, что r a, b q, 1 q n, и r (, ) - расстояние Хэмминга, q - параметр. Обозначим k D (a ) = k 2 (a ) - k1 (a ).

точки a * ) соответствует наибольшее значение k D a * по сравнению с другими шарами радиуса q с центрами a Tmnl. В таком случае a * объявляется Осуществляется синтез экстремального БРД по информации Tmnl (полагаем, построено экстремальное m1 -БРД Tm ) и по информации Tmnl \ a * (полагаем, построено экстремальное m 2 -БРД Tm ). Чем больше величина m1 - m 2, тем больше оснований исключить a * из Tmnl, получая лучшие статистические оценки Для возможности построения корректного на обучающей информации БРД, использующего только признаки с номерами i1, i2, K, is, необходимо и достаточно, чтобы множество { i1, i2, K, is } было тестом таблицы Tmnl [45]. Известно, что для почти всех таблиц при n ®, m ® и условии lim m 2 n / 2 = 0, для любого положительного e = o(1) любые 2(1 + e ) log 2 m столбцов таблицы образуют тест [12, 46]. Следовательно, для широкого класса произвольных булевых таблиц при синтезе БРД можно получить набор корректных деревьев, использующих полностью или частично разные переменные.

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

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

f = f ( x1, x2, K, xn ) называется функцией k-значной логики, если на всяком наборе a = (a1, a 2, K, a n ) значений переменных x1, x2, K, xn, где a i E k, значение f (a ) также принадлежит множеству E k.

Определение 1.5. Решающие деревья, у которых из каждой вершины выходят не более k ребер, реализующие алгоритмические отображения вида Ak,l = f : Ek K Ek ® {0,1, K, (l - 1)} называются k-решающими деревьями (kn РД).

В [19] была обоснована полнота класса функций алгебры логики, представимых в виде бинарного решающего дерева (БРД). Обобщим этот результат и покажем, что имеет место полнота класса функций k-значной логики, представимых в виде k-РД.

Теорема 1.1. Любое алгоритмическое отображение из класса Ak, l может быть построено в виде k-РД.

Доказательство. Пусть справедливости разложения f по одной (любой) переменной:

корневая вершина дерева, представленная на рисунке 1.2.

Если хотя бы одна из функций f s, s E k, полученных после построения f ( x1,K, xi -1, xi +1,K, xn ) = f (x1,K, xi -1,s, xi +1,K, xn ), не является константой, то к ней, как к функции (n - 1) -ой переменной, снова применяется разложение вида (1.1), определяющее следующий шаг построения k-РД.

Рис.1.2. Первый шаг ветвления. Из корневой вершины выходят k ребер.

Если же для некоторого s E k выполняется f ( x1, K, xi -1, s, xi +1, K, xn ) = g = const, т.е. оставшиеся незафиксированными переменные не являются существенными, то лист дерева, соответствующий ребру xi = s, становится терминальным и помечается константой g.

Используя такие предикаты, можно любое k-РД преобразовать в эквивалентное (реализующее то же самое алгоритмическое отображение) БРД. Для этого следует каждую внутреннюю вершину k-РД заменить бинарным поддеревом, показанным на рисунке 1.3.

Рис.1.3. Бинарное поддерево, заменяющее внутренние вершины k-РД.

Следует заметить, что подсчет числа различных бинарных решающих деревьев представляет интерес в связи с получением оценок статистической надежности решающих правил, основанных на построении деревьев, и изучением алгоритмов синтеза БРД с наименьшим числом листьев [13]. Однако, точная формула для нахождения числа БРД d (n, k, m ) с n внутренними вершинами, m листьями и kзначными метками листьев неизвестна. Известна лишь асимптотическая оценка Теорема 1.2 [13]. d (n, k, m ) ~ (m - 1)! (k (k - 1)) n(n - 1) Для дальнейшего изложения понадобится следующее неравенство [13].

Число булевых функций от n переменных b(n, 2, m ), представимых в виде БРД с ровно m листьями, удовлетворяет неравенству Отметим некоторые важные свойства бинарных решающих деревьев:

1. БРД с ограниченным (и небольшим) числом листьев определяют для случая двухэлементных (0,1) решений чрезвычайно узкий класс булевых функций, асимптотически (при числе аргументов n ® ) сколь угодно узкий по сравнению даже с классом линейных булевых функций L (n ) P2 (n ) [13];

2. Как отмечалось выше, любая булева функция из P2 (n ) может быть представлена в виде БРД [19];

3. Если m - число листьев, то для класса D (n, m ) булевых функций, представимых в виде БРД не более чем с m листьями, при условии 2 m 2n ( n -число признаков) справедливо включение D (n, m ) D(n, m + 1) Свойства 1,2,3 и положения статистической теории обучения [3] обосновывают возможность оптимизационного синтеза БРД, корректного на непротиворечивой таблице обучения Tmnl, путем минимизации параметра m.

4. Синтез БРД с минимальным числом листьев m по непротиворечивой таблице обучения Tmnl является сложной экстремальной задачей из класса 5. Построенное БРД с m листьями далее позволяет со сложностью O (n ) получить логическое описание синтезированных правил для распознавания классов объектов в виде дизъюнктивных нормальных форм (ДНФ) [19].

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

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

1.2. Задача синтеза решающих деревьев. Выбор критерия ветвления Алгоритмы синтеза решающих деревьев по непротиворечивой таблице обучения Tmnl обычно состоят из следующих основных этапов: выбор признакового предиката во внутреннюю вершину РД согласно некоторой эвристике, т.е. выбор критерия ветвления, выбор условия для прекращения ветвления – получение терминальных вершин, т.е. выбор критерия остановки, и определение метки класса, приписываемой терминальной вершине.

Различные эвристики, используемые в алгоритмах синтеза РД, зависят от особенностей информации, представленной в непротиворечивой таблице обучения, прежде всего, от шкалы [36, 41], в которой измеряются значения признаков; от наличия пропусков в данных; от числа анализируемых объектов по отношению к числу признаков таблицы обучения, от наличия “шума” в начальной информации и.т.п. В случае бинарных признаков, задача синтеза РД в случае непересекающихся классов – это задача построения разбиения куба B n на интервалы наименьшего ранга или наибольшей размерности, покрывающие как можно больше точек одного и того же класса. Напомним, что подмножество элементарной конъюнкции K r-го ранга, вещественных (непрерывных) признаков, задача синтеза РД обычно сводится к построению разбиения признакового пространства R n поверхностями достаточно простого вида [34].

Синтез разбиения признакового пространства интервалами максимальной размерности приводит к задаче построения оптимального решающего дерева с минимальным числом листьев. Исследованию этой задачи посвящены работы [15, 19, 96], в которых обосновывается NP полнота задачи поиска корректного БРД с минимальным числом листьев по непротиворечивой таблице обучения.

Доказательство Л.Хьяфила и Р. Ривеста основано на полиномиальной сводимости задачи о точном покрытии, для которой установлена NP-полнота, к изучаемой задаче [96]. Доказательство этого же факта Донским В.И. основано на полиномиальной сводимости задачи целочисленного 0-1-линейного программирования общего вида к задаче поиска РД с минимальным числом листьев [15]. В работе Zantema H., Bodlaender H. [160] обоснована NP полнота задачи поиска РД с минимальным числом листьев, дающего эквивалентные заданному РД решения. Заметим, что два решающих дерева дают эквивалентные решения, если они реализуют одну и ту же функцию, т.е. “вычисляют” одну и ту же метку класса для каждого допустимого объекта.

информативной подсистемы признаков, состоящей в указании части признаков из непротиворечивой таблицы обучения, в пространстве которых заданные множества объектов, представляющие разные классы, разделяются достаточно просто [36, 38]. Синтезированные по обучающей информации РД определяют набор эмпирических закономерностей. В общем случае сформулировать понятие закономерности представляется довольно сложным. Загоруйко Н.Г., Ёлкина В.Н., Лбов Г.С. в работе [36] под закономерностью понимают “…устойчивое формализованное правило, фиксирующее зависимость между различными частями таблицы”.

В связи с важностью критериев отбора признаков при ветвлении представляет интерес работа Ю.И. Журавлева, в которой предлагается оценивать информативность признаков с помощью тупиковых тестов непротиворечивой таблицы обучения. При этом наиболее информативным считается тот признак, который вошел в большее число минимальных достаточных наборов признаков (тупиковых тестов). В [12, 15] было доказано, что используя тупиковый тест бинарной таблицы обучения, можно построить РД с числом листьев m :

k m 2 r, где k – число классов, r – число признаков, образующих тупиковый тест. Тогда можно предложить тривиальный переборный алгоритм синтеза оптимального РД: сначала надо построить все тупиковые тесты таблицы обучения, затем на этих тупиковых тестах построить РД и среди построенных деревьев выбрать оптимальное (с наименьшим числом листьев). Однако, реализация такого алгоритма весьма затруднительна, т.к. эффективных алгоритмов построения всех тупиковых тестов нет, а построение всех тупиковых тестов – сложная переборная задача [46]. Известно, что среди РД с одинаковым числом листьев предпочтительнее то, в котором наборы из обучающей выборки распределены равномерно по интервалам, соответствующим конъюнкциям решающей булевой функции [19].

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

Пусть для разбиения интервала N t на некотором шаге выбирается признак xk, N t = N tRight N tLeft, N tRight N tLeft =.

Определение 1.6 [19]. Будем говорить, что признак xk обладает свойством полной отделимости, если множество A(k ) содержит объекты только одного класса; множество B (k ) содержит объекты только одного класса и классы объектов из A(k ) и B (k ) различны.

Определение 1.7 [19]. Будем говорить, что признак xk обладает свойством частичной отделимости, если множество A(k ) или множество B (k ) содержит объекты только одного класса.

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

В зависимости от выбора алгоритма разбиения, по имеющемуся набору обучающих объектов, может быть построено некоторое множество решающих деревьев, позволяющих корректно классифицировать эти объекты. В этом случае следует выбрать РД, которое с наибольшей вероятностью позволит корректно классифицировать объекты, не участвовавшие в обучении. Обычно, таким деревом считают в некотором смысле “простейшее” РД, безошибочное на всех обучающих объектах. В основу такого предположения положена проверенная временем эвристика, согласно которой предпочтение отдается простоте без дополнительных ограничений. Этот принцип впервые был сформулирован в году философом-схоластом Вильямом из Оккама (William of Occam) и получил название “бритвы Оккама” (Occam’s Razor). “Глупо прилагать больше усилий, чем нужно для достижения цели… Не стоит приумножать сущности сверх необходимого”. Более современная версия этого принципа сводится к выбору простейшего ответа, соответствующего исходным данным [42, 56, 120].

Если объекты описаны произвольными наборами значений переменных (булевыми, вещественными, качественными), иначе говоря, являются точками некоторого произвольного допустимого множества X, то для построения БРД используется система признаковых предикатов Pj : X ® {0,1}, j = 1, n. Некоторые признаковые предикаты могут быть заданы при постановке задачи, другие – найдены путём использования статистических или метрических методов анализа начальных данных [44, 45].

отличаются друг от друга по типу признаковых предикатов, рассматриваемых во внутренних вершинах решающего дерева. Известны следующие основные типы признаковых предикатов, используемых в алгоритмах синтеза РД [45]:

1) простейшие признаковые предикаты по порогу(-ам) одного признака, вещественных признаков);

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

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

Приведем обзор наиболее известных алгоритмов синтеза решающих деревьев.

Один из таких широко известных алгоритмов синтеза РД – ID3 алгоритм – предложен Р. Куинланом. Он включает в себя метод отбора множества объектов, по которым строится РД, и тест на статистическую независимость выбираемых признаков. Куинлан [8, 9, 10, 42, 45, 63, 68, 71] предложил использовать теоретико-информационную меру (E-меру), основанную на энтропии для оценивания меры неопределенности в классификации, возникающей при использовании рассматриваемого признака во внутренней вершине РД.

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

Алгоритм ID3 построения решающего дерева можно описать следующим образом:

1) если все объекты обучающего множества точно из одного класса, то решающее дерево есть лист, содержащий в качестве ответа метку этого 2) в противном случае:

a) определить признак xbest, обладающий минимальной E-оценкой по b) для каждого значение vbest, j признака xbest построить ветвь от xbest к решающему поддереву, построенному рекурсивно на всех обучающих объектах со значением vbest, j признака xbest.

Пусть далее X = {x1, x2, K, xn } – множество признаков, используемых для описания прецедентов, для каждого признака xi множество его возможных значений обозначим Vi ; vij - индивидуальные значения признака xi, i = 1,2,K, n, j = 1,2,K, Vi. Е-оценка – это результат определения информационной функции Е признака в вершине.

Для данной вершины в случае двух классов имеем: p - число объектов первого класса; q - число объектов второго класса; pij - число объектов первого класса со значением vij признака xi ; qij - число объектов второго класса со значением vij признака xi. Тогда E ( xi ) = энтропия I (, ), как обычно в теории информации [39, 50, 153], определяется выражением:

Выбор признака с минимальной Е-оценкой равносилен выбору признака с максимальным приростом информации, определяемым как i = 1,2,K, n.

Алгоритм ID3 позволяет построить корректное относительно начальной информации решающее дерево, на основе которого каждый объект из исходного непротиворечивого обучающего множества будет классифицироваться правильно [9, 10, 47].

Среди недостатков ID3 алгоритма можно выделить следующие:

- E-мера предоставляет при построении дерева преимущество признакам с бльшим числом возможных значений. Отметим, что в работах Гупала А.М., Цветкова А.М. [9,10] приведен улучшенный вариант E-меры – мера отношения, устраняющая этот недостаток;

- наличие “горизонтального” эффекта (horizon effect) – алгоритм выбирает признаки, основываясь на “локальной” мере, т.е. осуществляет на каждом шаге синтеза “локальное” разбиение подмножества объектов, которые “попали” во внутреннюю вершину РД;

“неоптимального” признака не способен осуществить возврат на уровень вверх с целью замены “неоптимального” признака.

характеризуют бльшую часть эвристических алгоритмов синтеза РД.

Известно семейство алгоритмов ID4, ID5, ID5R, также использующих энтропийный критерий, создание которых было направлено на устранение недостатков алгоритма ID3 и повышение его эффективности. Так, алгоритм ID строит решающее дерево и модифицирует его по мере того, как становится доступным новый объект. ID5 и ID5R устраняют недостатки алгоритма ID4.

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

В автореферате диссертации Цветкова А.М. [48] приведены оценки сложности этих алгоритмов, представленные в таблице 1.1, где n - число признаков, b-максимальное количество значений признаков, m - число объектов из обучающего множества.

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

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

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

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

В работах [45, 61, 109, 110, 138] описан эвристический критерий разбиения, используемый в методе CART (Classification and Regression Trees). В случае двух F (CART 1) = max {p (t ) i (t ) - p (t Left ) i (t Left ) + p (t Right ) i (t Right ) }, а для многоклассовой задачи – F (CART 2 ) называемая функция засоренности: i (t ) = P(w1 | t ) P(w2 | t ) ; iG (t ) - функция i, k = 1,2, K, l ; p (t ) - оценка вероятности попадания объектов обучающей выборки объема m в вершину t в случае известных априорных вероятностей qi классов wi, вероятностей p (t ) = ; P (wi | t ) - оценка условной вероятности класса wi в вероятностей классов) или P(wi | t ) = t вероятностей классов); mi - число объектов обучающей выборки класса wi ; nt(i ) число объектов класса wi в вершине t; nt - количество объектов всех классов wi в вершине t, т.е. nt = nt(i ) ; l - число классов.

В работе [137, 151] предложен алгоритм, использующий расстояние Колмогорова-Смирнова для выбора признаковых предикатов во внутренние вершины РД. В случае двух классов требуется найти пороговое значение a, вещественного признака xk на два подмножества объектов: те, для которых xk < a, и те, для которых xk a. Предполагается, что заданы плотности распределения вероятностей f A ( xk ) и f B ( xk ) для классов А и В соответственно;

коэффициенты ошибок классификации для классов А и В равны, и равны априорные вероятности появления объектов каждого класса. Тогда оптимальный по Бейесу порог a определяется как число, минимизирующее вероятность того, что признаковый предикат, определяющий решающее правило, произведет неправильную классификацию. Считается, что заданы также кумулятивные (интегральные) функции распределения FA (xk ) и FB ( xk ), соответствующие плотностям распределения вероятностей f A ( xk ) и f B ( xk ). Оптимальное пороговое значение a максимизирует величину значение называется расстоянием Колмогорова-Смирнова между двумя распределениями для признака xk. Расстояние Колмогорова-Смирнова вычисляется для каждого признака, и во внутреннюю вершину выбирается признак, имеющий максимальное расстояние Колмогорова-Смирнова между распределениями.

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

Лбовым Г.С. и др. в работе [41] были предложены эвристические алгоритмы формирования логических решающих функций с выделением признаковых предикатов, позволяющих строить понятия при разнотипных признаках. Алгоритм CORAL ориентирован на распознавание K классов ( K 2 ).

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

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

Работы [58, 82, 90, 97, 102, 114, 129, 141, 142, 143, 144] посвящены методам добавления повторяющихся элементов (bagging) и усиления (boosting) часто используемым в комбинации с методами синтеза и редукции решающих деревьев, что позволяет повысить их эффективность. В методе баггинга или добавления повторяющихся элементов производится взвешенное голосование классификаторов, обученных на различных подвыборках данных, либо на различных частях признакового описания объектов. Выделение подмножеств объектов и/или признаков производится, как правило, случайным образом. Метод бустинга или усиления также является разновидностью взвешенного голосования, однако классификаторы строятся последовательно, и процесс увеличения различий между ними управляется детерминированным образом, т.е. для каждого классификатора, начиная со второго, веса обучающих объектов пересчитываются так, чтобы классификатор как можно точнее настраивался на тех объектах, на которых чаще ошибались все предыдущие классификаторы. Веса классификаторов вычисляются исходя из числа допущенных ими ошибок.

Заметим, что использование достаточно “изощренных” эвристик оправдано сложностью задачи синтеза экстремальных по статистическим свойствам РД.

Донским В.И. предложен ряд критериев выбора признаков – Z1, D, W критерии, а также алгоритм LISTBB, комбинирующий и определяющий порядок использования перечисленных одношаговых алгоритмов.

Опишем подробно D-критерий [15, 19] максимальной отделимости пар разных классов. Пусть Tmt n Tmnl такое подмножество наборов, что Tmt n N t ;

K t (i ) число пар объектов различных классов из Tmt n, которые имеют различное значение по переменной xi. Если D i * = max K t (i ) и для разбиения выбирается признак xi*, то будем говорить, что используется D-критерий ветвления.

Обобщим D-критерий ветвления, предложенный в [19] для бинарных РД, на случай синтеза k-РД, при k>2. Будем полагать, что обучающая информация состоит из m векторов, случайно и независимо выбранных из Ekn (декартовой степени n множества Ek ), для каждого из которых достоверно известно, какому из l классов он принадлежит, причем среди них нет одинаковых векторов с указанной принадлежностью к разным классам, т.е. задана стандартная таблица Tmnl, n+1 столбец которой служит для указания меток классов и не используется при выполнении теоретико-множественных операций над таблицей.

Определение 1.7. k-значным интервалом ранга r в Ekn называется называется направлением интервала, а набор значений (s 1, s 2, K, s r ) - кодом интервала.

Если r = 0, то N r = Ekn ; если r = n, то N r состоит из единственной точки, принадлежащей Ekn.

Пусть на шаге ветвления t при синтезе k-РД разбиению подлежит интервал N r(t ). Для ветвления, вообще говоря, может быть выбрана любая переменная, номер которой j не принадлежит направлению интервала N r(t ). Обозначим K t ( j ) число пар наборов различных классов в непустой таблице различающихся по переменной x j. Если K t j * = max K t ( j ) и для ветвления выбирается переменная x j *, будем говорить, что используется D-критерий ветвления.

Определение 1.8. (D, m ) -сужением k-значного интервала N r ранга r по DD - критерий ветвления определим так, что при вычислении чисел K t ( j ) используется подтаблица Tmnl \ N r( D, m )(t ), где N r(D, m )(t ) - сужение интервала N r(t ), подлежащего разбиению. Если переменная x j * выбирается по DD -критерию, то множество ребер, выходящих из внутренней вершины, соответствующей переменной s {E k \ D} и еще одного ребра, соответствующего множеству значений D.

Отметим, что DD - критерий особенно полезен при синтезе k-РД по начальной информации Tmnl, имеющей пропуски – неизмеренные или неизвестные значения некоторых признаков. В этом случае символу сопоставляется пропуск значения в таблице Tmnl. Совокупность строк из Tmnl, имеющих пропуск значения переменной x j *, образует подтаблицу, которая далее используется для синтеза дерева с условием, что при последующих ветвлениях переменная x j * использоваться не будет. Шаг ветвления, допускающий пропуски, поясняется рисунком 1.4.

Рис.1.4. Шаг ветвления с выделением подтаблицы по множеству D Аналогично, могут быть обобщены и другие критерии ветвления S1, S2, Z1, W. На основе такого обобщения осуществляется синтез k-РД, близких к оптимальным, алгоритмом, который можно отнести к типу GREEDY. Класс k-РД при этом расширяется до класса (k+1)-РД, допускающих принятие решений при наличии пропусков в информации. Таким образом, алгоритмы принятия решений, основанные на решающих деревьях и допускающие работу с пропусками в начальной информации, дают возможность полнее использовать обучающую информацию.

Рассмотренные методы синтеза решающих деревьев имеют следующие недостатки [45]:

- являются очень чувствительными к “разбросу” объектов обучающей - обычно требуют наличия обучающих выборок большого объема;

- построение оптимального решающего дерева часто требует больших ресурсов ЭВМ (процессорного времени и памяти);

- количество возможных альтернативных структур РД для конкретной задачи, как правило, очень велико;

- выбор признаков во внутренних вершинах РД обычно глобально - относятся к алгоритмам типа GREEDY, т.е. не способны к переоценке и, при необходимости, к замене признакового предиката, ранее выбранного во внутреннюю вершину РД;

- трудно решается задача оптимизации структуры классификатора.

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

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

1.3. Задача редукции ветвей решающих деревьев. Выбор критерия остановки ветвления Процесс синтеза РД чаще всего направлен на создание “идеального” классификатора, который правильно (точно) классифицирует любой объект обучающего множества, т.е. полностью “настраивается” на объекты обучающего множества в том числе, возможно, и на “зашумленные” объекты. В результате проявляется так называемый эффект “переподгонки” или переобучения, способствующий потере точности классификации при распознавании объектов из множества M \ M 0 (не участвовавших в обучении) и излишнему усложнению структуры РД.

На протяжении десятилетий усилия исследователей в области обучения распознаванию на основе решающих деревьев [55, 57, 60, 65, 72, 73, 74, 76, 78, 80, 81, 84, 87, 91, 92, 104, 107, 109, 110, 111, 112, 115, 119, 124, 126, 127, 136, 139, 140, 147, 161] были направлены на разработку стратегий избежания переподгонки на обучающем множестве, основными из которых являются стратегии редукции или отсечения ветвей РД.

Процесс чрезмерного усложнения структуры РД (увеличение числа листьев, рост ветвей в глубину), вызванный излишним следованием “зашумленным” данным, называется переподгонкой (overfitting). Уточним понятие “зашумленных” объектов. Процесс извлечения объектов из генеральной совокупности для формирования обучающей выборки предполагается случайным и независимым выбором. Из генеральной совокупности должны быть выбраны любые произвольные, но неискаженные, не подверженные в процессе выбора никаким изменениям объекты. Только при таком условии обучающая таблица Tmnl будет “отражать” свойства генеральной совокупности.

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

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

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

распространенные эвристические стратегии редукции решающих деревьев.

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

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

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

1. Редукция на основе сокращенной ошибки (Reduced Error Pruning(REP)) [60, 61, 75, 76, 78, 106]. Согласно стратегии REP обучающее множество разбивается на два подмножества: множество, предназначенное для синтеза РД, и множество, предназначенное для редукции РД. Решающее дерево T полностью “настраивается” на объекты множества синтеза РД. Синтез редуцированного дерева производится на объектах множества редукции. Для каждой внутренней вершины осуществляется сравнение числа ошибок классификации на множестве редукции I (T (t )), допускаемых поддеревом с корневой вершиной t с числом ошибок классификации на множестве редукции I (t ), которое возникнет в результате преобразования вершины t в лист согласно мажоритарному правилу.

Если I (T (t )) I (t ), то поддерево с корневой вершиной t редуцируется. Далее процесс редукции применяется к полученному редуцированному дереву до тех пор, пока для всех внутренних вершин не будет выполнено условие I (T (t )) < I (t ).

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

Недостатки стратегии REP [75, 76] заключаются в том, что - нет четкого указания, как выбирать метки классов для листьев, получаемых в процессе редукции. Здесь существуют две возможности:

использовать мажоритарное правило класса на объектах обучающего множества или на объектах множества редукции;

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

- стратегия приводит к чрезмерной редукции ветвей РД, особенно в случае, когда число объектов множества редукции существенно меньше числа объектов множества синтеза РД.

2. Редукция на основе пессимистической ошибки (Pessimistic Error Pruning (PEP)) [60, 61, 76, 78, 106]. Стратегия использует одно и то же обучающее множество и для синтеза и для редукции РД. Пусть коэффициент ошибки в вершине t на объектах обучающего множества определяется как где - число объектов обучающего множества, не принадлежащих мажоритарному классу; n(t ) - число объектов обучающего множества, попавших в вершину t. Оценка коэффициента ошибки в вершине t на объектах обучающего множества имеет вид:

Аналогично, для поддерева T (t ) с вершиной t коэффициент ошибки на обучающем множестве имеет вид:

осуществляется, если e ' (t ) e ' (T (t )) + SE [e ' (T (t ))], где вычисленная в предположении, что распределение ошибок биномиально.

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

3. Редукция на основе минимальной ошибки (Minimum Error-Pruning (MEP)) [60, 61, 76, 78, 106]. Стратегия осуществляет редукцию, просматривая вершины дерева снизу вверх, направленную на поиск одного дерева, минимизирующего “ожидаемый коэффициент ошибки”. И синтез и редукция РД осуществляются на одном и том же обучающем множестве.

В случае k классов, ожидаемая вероятность того, что объект, попавший в вероятность pi (t ). Для простоты будем полагать, что значение m одинаково для всех классов. pi (t ) называется m-вероятностной оценкой. При распознавании “нового” объекта, попавшего в вершину t, коэффициент ожидаемой ошибки задается как Согласно стратегии MEP для каждой внутренней вершины t сначала вычисляется ожидаемый коэффициент ошибки, называемый статической ошибкой STE (t ), затем ожидаемый коэффициент ошибки поддерева T (t ), называемый динамической ошибкой DYE (t ). DYE (t ) вычисляется как взвешенная сумма ожидаемых коэффициентов ошибки для “сыновей” вершины t, где вес ps вероятность того, что объект из t достигнет “сына” s вершины t. В ранних версиях этой стратегии в качестве веса ps принималась часть обучающих объектов, достигших s -го “сына”. Параметр m выбирается произвольно.

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

4. Редукция на основе критического значения (Critical Value Pruning, CVP) [60, 61, 76, 78, 106]. Согласно этой стратегии внутренняя вершина дерева редуцируется, если значение, полученное в процессе выбора признака во внутреннюю вершину РД, не превышает фиксированного критического значения, т.е. CVP учитывает информацию, “накопленную” на этапе синтеза РД. Однако может случиться так, что условие редукции выполняется в вершине t и не выполняется для ее “сыновей”. В этом случае ветвь T (t ) не подвергается редукции. Степень редукции изменяется в зависимости от критического значения:

чем больше критическое значение, тем “жестче” редукция. CVP состоит из двух этапов:

- Редукция Tmax с увеличением критического значения (строится совокупность РД для разных значений критического значения);

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

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

5. Редукция на основе оценки цены-сложности (Cost-Complexity Pruning, (CCP)) [60, 61, 76]. Этот метод используется для редукции РД в упоминаемой ранее (пункт 1.2) системе CART и состоит из двух этапов:

- Выбор “оптимального” РД Ti из параметрического семейства согласно оценке “истинных” коэффициентов ошибок деревьев (коэффициентов ошибок на объектах контрольного множества).

На первом этапе основная идея построения параметрического семейства состоит в том, что РД Ti +1 получается из Ti редуцированием тех ветвей, которые определяют минимальное увеличение коэффициента ошибки на обучающем множестве по сравнению с ветвью, преобразованной в лист в результате коэффициент ошибки увеличивается на величину r (t ) - r (T (t )), в то время как число его листьев уменьшается на единицу. Таким образом, следующее обучающем множестве в результате преобразования ветви в лист, т.е. в результате редукции. Затем, Ti +1 из параметрического семейства получается путем редукции всех вершин РД Ti с минимальным значением a. Первое дерево семейства T получается в результате редукции исходного (ранее нередуцированного) РД Tmax, последнее дерево семейства TL - корневое дерево.

На втором этапе выбирается “оптимальное” РД из параметрического семейства Tmax (a ) на основе оценки точности классификации. Здесь предлагается два подхода оценивания “истинного” коэффициента ошибки для каждого дерева:

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

- использование множества редукции.

6. Редукция, основанная на ошибке (Error-Based Pruning (EBP)) [60, 61, 76, упоминавшемся ранее. Отличие этой стратегии от ранее перечисленных стратегий состоит в том, что, кроме редукции, РД упрощается за счет перестройки его структуры. EBP упрощает РД T за счет перемещения ветви T (t ) на место “родительской” для t вершины.

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

Замещение выполняется, если коэффициент ошибки для “будущего” листа не больше, чем сумма коэффициентов ошибок для листьев данного поддерева.

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

7. Стратегии редукции РД на основе использования принципа минимальной длины описания (Minimum Description Length Principle (MDLP)) [54, 117, 118, 132].

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

Procedure PruneTree (вершина N) 10. if N – лист return C (M 0 ) + 20. min_cost1:=PruneTree(N1);

30. min_cost2:=PruneTree(N2);

40. min_costN:= min{ (M 0 ) + 1, Csplit ( N ) + 1 + min_cost1 + min_cost2 };

50. if min_costN=C(M0)+ 60. редуцировать “сыновей” N1 и N2 вершины N;

70. return min_costN где M 0 - обучающее множество; l -число классов; m – число объектов в обучающем множестве; mi - число объектов класса i , i = 1,2, K, l. Величина C (M 0 ) называется стохастической сложностью. Эвристический подход MDLP также представляется недостаточно обоснованным.

8. Редукция на основе DI индекса [84, 85]. Большая часть методов редукции (REP, PEP, MEP, CVP, CCP) направлена на минимизацию коэффициента ошибки поддеревьев, т.е. и “засоренность” листьев и глубину ветвей, называемый далее DI-индекс (Depth-Impurity Index). Индекс качества РД T имеет максимальное значение тогда и только тогда когда выполнены два условия:

DI (T ) = a i 1 - j W 'i f depth W 'i, где W1, W'2,K, W'm - листья РД T, a i = мера “примесей” D.

DI-индекс учитывает глубину РД, чем длиннее ветвь, тем меньше “качество” РД. Согласно DI-редукции, редуцируются все поддеревья дерева T с корнем W, удовлетворяющие условию DI (T ) 1 - j (W ).

В работах [139, 140] отмечается, что в случаях, когда при синтезе РД индукторов с большей ошибкой, чем при использовании более тщательно “настроенных” на обучающую выборку деревьев. К сожалению, в этой работе отсутствуют строгие обоснования выводов, касающихся переподгонки.

число листьев) [140], приведенная на рисунке 1.5, с нашей точки зрения, верно характеризует процесс синтеза РД.

Рис 1.5. Кривая в координатах “ошибка” (p) - “сложность” ( m ) Действительно, при малом m > m опт, m = m, получается “вырожденный” классификатор, настроенный “поточечно”.

Используя свойства единичных интервалов для почти всех булевых функций можно обосновать положения работы [140]. Нужно отметить, что принципиальное значение имеет модель начальной информации: являются ли данные таблицы обучения достоверными и непротиворечивыми (“шум” отсутствует) или в обучающем множестве возможны ошибки (наличие “шума”).

Если в таблице обучения имеется “зашумленный” объект, то стратегия избежания переподгонки должна быть направлена на “отбрасывание” такого объекта: в идеальном случае именно на нем при ошибке обучения должна остановиться подгонка.

Таким образом, любая стратегия, направленная на избежание переподгонки, может ухудшить качество распознавания [139, 140]. Однако в защиту стратегий редукции выступают многочисленные эксперименты. Эффективность стратегий редукции можно объяснить не столько природой эвристических методов, сколько удачным подбором областей для проведения экспериментов, а также подстройкой стратегий редукции под эмпирические данные за счет варьируемого параметра – уровня значимости. Следует отметить, что нет четкого теоретического обоснования, как выбирать значения для уровня значимости, в связи с чем классификатор типа РД оказывается либо недостаточно, либо чрезмерно редуцированным.

Отсутствие достаточного теоретического обоснования эффективности стратегий редукции, а также выявления их недостатков в ходе проведения многочисленных экспериментов привели к поиску других стратегий избежания переподгонки [80]. Среди них методы синтеза совокупности решающих деревьев – решающих лесов (С4.5 decision forests) такие как метод случайных подпространств [59, 93, 94, 95], позволяющий строить, в случайно выбранных подпространствах заданного признакового пространства, корректные решающие деревья, используя в качестве критерия ветвления алгоритм С4.5 (результаты практического применения этого метода представлены в [66]); алгоритм “дровосека” (Lumberjack algorithm) синтеза решающего леса с переходами по ссылкам [152], основанный на анализе структуры РД с установкой ссылки перехода на другое дерево леса, при появлении в исходном дереве одинаковых поддеревьев; алгоритмы наращивания отдельных вершин РД (grafting) [156, 157];

алгоритмы выбора признаковых предикатов с возвратом (look ahead algorithms или backtracking method) [125]. Метод увеличения точности прогноза РД за счет “прививки” РД или наращивания отдельных вершин представляет собой процесс обработки построенного нередуцированного РД и направлено на выявление таких областей признакового пространства, которые не заняты обучающими объектами или заняты только неверно расклассифицированными обучающими объектами, и рассмотрение возможных способов разбиения таких областей. Рассматриваются различные “альтернативные” ветви, которые могут дать лучшую классификацию “сомнительной” области, чем исходное дерево. В этом случае “альтернативная” ветвь встраивается на место внутренней вершины предшествующей листу. В работе [157] отмечается, что подобное наращивание незначительно увеличивает сложность структуры РД и в то же время увеличивает точность классификации объектов не участвовавших в обучении.

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

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

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

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

Возникает постановка следующей достаточно “тонкой” новой проблемы.

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

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

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

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

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

Для достижения поставленных целей в диссертационной работе ставятся следующие задачи.

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

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

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

4. Получить оценку сложности эмпирического решающего леса и изучить распознавания.

точности классификации.

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

МЕТОДЫ ОЦЕНИВАНИЯ РЕШАЮЩИХ ДЕРЕВЬЕВ

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

Вероятностный подход к оцениванию эмпирических закономерностей и решающих правил основывается на представлении закономерности как неслучайности. В основе такого подхода лежит намеченный А.Н.Колмогоровым путь построения математической теории, позволяющей придать точный смысл понятию “случайность” как отсутствию закономерности [40]. В соответствии с колмогоровским представлением о природе случайности, полученные в диссертации результаты, связаны со сложностью изучаемых конструктивных объектов – деревьев и леса.

закономерность как неслучайность в следующем смысле.

Пусть обучающая информация Tmn в задаче классификации представлена указанием m булевых векторов длины n ; Tmn B n = {0,1}. Таблица обучения Tmn представляет собой случайную независимую выборку: каждый объект обучающей выборки получается путем случайного выбора из генеральной совокупности объектов, и выбор каждого последующего объекта не зависит от результата выбора предыдущих объектов. Предположим, объекты генеральной совокупности ("~ ) P(~ ) = 2 - n. Тогда вероятностная мера любого интервала ранга k есть 2 n-k 2 n = 2 - k (отношение числа векторов, у которых k координат зафиксировано к общему числу булевых векторов длины n), а вероятность того, что при зафиксированному интервалу ранга k, есть 1 - 2 - k. Иначе говоря, случайно выбранная точка не попадает в заданный интервал ранга k с вероятностью 1 - 2 - k. При m независимых испытаниях такое непопадание в указанный вероятностью меньшей, чем величина W (m, n, k ) = C n 2 k 1 - 2 - k Cn 2 k - число различных интервалов ранга k в B n. Следовательно, при случайном выборе m точек для обучения из генеральной совокупности B n с равномерным распределением (формирование эмпирической таблицы Tmn ) любой интервал Противоположное событие, состоящее в том, что указанный интервал пуст 1 - P(m, n, k ) > 1 - W (m, n, k ). А.Д. Закревским в [37] была приведена таблица 2. значений W (m, n, k ) для достаточно типичных случаев m = 200, n = 100.

По таблице 2.1 виден четкий порог дискриминации: пустые интервалы ранга k 3 почти достоверно являются закономерно пустыми при данных m и n ;

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

предполагает использование модели генеральной совокупности с равномерным распределением объектов.

Изучая закономерность – гипотезу, можно оценить вероятность того, что она может быть обнаружена по выборке, извлеченной из генеральной совокупности с равномерным распределением, т.е. случайно. Если эта вероятность достаточно мала, то случайное обнаружение закономерности представляется маловероятным; также маловероятным в таком случае является равномерное распределение объектов генеральной совокупности.

Уточним понятие конъюнктивной закономерности ранга r относительно таблицы обучения Tmn.

называется конъюнктивной закономерностью ранга r относительно таблицы обучения Tmn, если среди n столбцов этой таблицы найдутся такие r столбцов с номерами i1, i2, K, ir и не входящий в их число столбец с номером k, что для всех переменная xk принимает одно и то же значение g s. При этом множества В задачах обучения распознаванию или формирования понятий булева переменная является характеристической функцией некоторого класса объектов и называется целевой. Например, если xk = 1, то объект принадлежит указанному классу, а если xk = 0 - не принадлежит.

С точки зрения теоретико-множественного подхода, конъюнктивная закономерность K r ранга r соответствует интервалу N K r размерности (n - r ), содержащему объекты только одного класса из таблицы обучения Tmn.

Поскольку для поиска закономерностей используется случайно выбранная таблица Tmn из генеральной совокупности Tmn булевых таблиц размерности m n, то конъюнктивная закономерность может быть обнаружена случайно в таблице Tmn, если столбец с номером k случайно окажется заполненным значениями, соответствующими некоторой функции f. Функция f ставит в соответствие набору s i1, s i2,K, s ir зафиксированное значение целевого столбца. Случайность такого обнаружения оценил А.Д. Закревский [37]. Ему принадлежит следующий результат, важный для дальнейшего исследования РД; поэтому этот результат строго доказан ниже.

Теорема 2.1. Пусть Tmn - булева таблица, случайно выбранная из генеральной совокупности Tmn таблиц размерности m n с равномерным распределением на Tmn. Тогда вероятность P(m, n, r ) случайного обнаружения удовлетворяет неравенству Доказательство. В соответствии с равномерным распределением таблиц на Tmn, для произвольного столбца таблицы Tmn любое из его 2 m возможных значений равновероятно.

Пусть Ar - событие, состоящее в появлении в случайной таблице Tmn хотя бы одной закономерности ранга r. Событие Ar всегда происходит одновременно конъюнктивная закономерность ранга r определяется зафиксированным набором зафиксированной целевой переменной xk (столбцом k ). Различные события H f,~,k, вообще говоря, не являются несовместными: может существовать несколько разных зафиксированных закономерностей ранга r одновременно.

Поэтому Число различных событий H f,~,k конечно и равно мощности множества M :

где 2 2 - число различных функций f P2 (r ) ; C n - число способов выбора r любых столбцов из n ; (n - r ) - число способов выбрать целевой столбец из оставшихся.

По теореме умножения зависимых событий и теореме сложения совместных событий без учета вероятностей совместного появления событий H f,~,k согласно (2.2), можно оценить вероятность события Ar :

Событие Ar при условии H f,~,k наступает тогда, когда столбец, соответствующий целевой переменной xk, принимает единственный набор значений из 2 m наборов значений длины m, в точности определяемый функцией f. Обозначим этот набор a f. Событие, состоящее в появлении набора a f в столбце k таблицы Tmn, Следовательно, P( Ar ) < На практике этот результат приводит к поиску конъюнкций, ранг которых, как правило, не должен превышать число семь [37].

Если оценка вероятности P(m, n, r ) мала, и в таблице Tmn, извлеченной из произвольной генеральной совокупности таблиц, обнаружена закономерность ранга r, то правомерно считать, что эта закономерность будет появляться и на других таблицах, извлекаемых из этой совокупности, и отражать обнаруженное свойство генеральной совокупности.

неслучайность”, можно заключить: если случайное появление закономерности гипотезы имеет вероятность P(m, n, r ), то ее неслучайное появление имеет вероятность W (m, n, r ) = 1 - P(m, n, r ). Иначе говоря, если в эмпирической таблице Tmn обнаружена закономерность ранга r, то она имеет место на всей генеральной свойство.

принятия решения:

т.е. определяет значение целевой переменной xk при условии, когда вектор ~ = ( x, x,K, x ) попадает в интервал N, соответствующий конъюнкции K, содержащейся в левой части импликации (2.3). Поэтому можно говорить о “неслучайном выводе решения” при помощи конъюнктивной закономерности с вероятностью W (m, n, r ).

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

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

Если бинарное решающее дерево BDTm,m,n с m листьями корректно на конъюнкции попарно ортогональны, поскольку соответствуют различным ветвям дерева [15]. Указанные выше свойства BDTm,m,n и неравенство 2.1 позволяют получить следующую оценку.

Теорема 2.2. Вероятность PBDT (m, m, n ) того, что при использовании эмпирической таблице обучения Tmn, будет получен случайный вывод о свойстве равновероятно из множества булевых векторов длины n - 1, удовлетворяет неравенству где r1, r2, K, rm - ранги конъюнкций, соответствующих ветвям дерева.

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

предъявлении объекта ~ он будет классифицироваться ветвью бинарного решающего дерева BDTm,m,n, соответствующей конъюнкции K j, т.е. попадет в интервал N K j. P Сл / N K j = P(m, n, r j ) и оценено неравенством (2.1). Поэтому Замечание 2.1. В случае, когда целевая переменная (целевой столбец) задана отдельно от эмпирической таблицы обучения Tmn, т.е. не входит в число ее столбцов, неравенство аналогичное (2.4) имеет вид где PBDT (m, m, n ) - вероятность случайного вывода целевого свойства деревом, построенным по стандартной начальной информации с n булевыми признаками.

Замечание 2.2. Оценки (2.4), (2.5) характеризуют среднее значение (математическое ожидание) оценки вероятности случайного вывода на множестве всех допустимых объектов ~ при заданных рангах r, r, K, r конъюнкций, соответствующих ветвям БРД BDTm,m,n.

2.2. Обоснование редукции ветвей решающего дерева на основе подхода к закономерности как неслучайности Редукция решающего дерева – процесс упрощения структуры РД, направленный на избежание “переподгонки” на объектах обучающего множества.

Интуитивно ясно: если структура РД усложняется за счет роста отдельных ветвей дерева, то такие ветви должны редуцироваться, как статистически ненадежные. В противном случае, будет построено решающее правило, “настроенное” на отдельные объекты (небольшие группы объектов) выборки и даже, возможно, на зашумленные объекты.

Обозначим Dm,m,n - класс всевозможных решающих деревьев с ровно m листьями, которые могут быть построены на объектах стандартной таблицы обучения Tmn. Исходя из оценки (2.5), полученной в пункте 2.2, введем на множестве Dm,m,n функционал качества j : Dm,m,n ® R следующего вида:

Функционал j (d ) является оценкой “худшего” случая при использовании для принятия решения самой “неблагоприятной” ветви дерева – ветви дерева наибольшего ранга. Это обосновывается следующей леммой 2.1.

Лемма 2.1. Величина h(n, m, r ) = C n 2 -(m +r -2 ) монотонно возрастает с ростом Доказательство. Пусть a (r, r + 1) = h(n, m, r + 1) h(n, m, r ), тогда Убедимся, что a (r, r + 1) > 1, при r 2 и n r + 1. Действительно, т.к. по условию равенство 22 растет быстрее линейной функции r + 1 с ростом ранга ветви r.

Лемма 2.2. Минимум функционала j (d ) на множестве РД Dm,m,n достигается при m = 2 k, k N, в случае, если d * - полное дерево; а при m 2 k - в случае, когда дерево d * обладает следующим свойством:

r1, r2, K, rm - ранги конъюнкций, соответствующих ветвям РД d *.

Доказательство. Рассмотрим два взаимно исключающих случая согласно условию леммы.

дереву d повлечет удаление вершины из хотя бы одной ветви и добавление вершины в хотя бы одну другую ветвь, поскольку число листьев m должно оставаться неизменным. Тогда rmax k + 1 и по лемме 2.1 о монотонности функционала j (d ) > j d *.

2) Пусть m 2 k, k N. Рассмотрим любое дерево d Dm,m,n. Оно не может быть полным в силу ограничения на m и, следовательно, среди рангов r1, r2, K, rm найдутся различные. Выберем rmin = min{r1, r2,K, rm } и rmax = max{r1, r2, K, rm }.

Удалив одну внутреннюю вершину, предшествующую листу из ветви с рангом rmax, и добавив ее в ветвь, соответствующую rmin, получим уменьшение величины rmax = rmax d, где d - новое дерево, полученное из d перестройки, но тогда и только тогда, когда rmax - rmin 2. По лемме 2.1 это повлечет уменьшение значения функционала j d < j (d ).

конъюнкции.

Определение 2.3. Бинарное решающее дерево называется равномерным, если ранги его ветвей отличаются не более чем на единицу.

наименьшую равномерную оценку (2.6) вероятности получения случайного заключения имеют равномерные деревья.

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