Построение и исследование полных решающих деревьев для задач классификации по прецедентам тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Генрихов, Игорь Евгеньевич

• Генрихов, Игорь Евгеньевич
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Генрихов, Игорь Евгеньевич

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

1.1 Основные понятия, используемые при построении классического решающего дерева

1.2 Синтез корректного бинарного решающего дерева с помощью алгоритма построения допустимого разбиения

1.3 Описание алгоритма С4.5 в случае целочисленной информации

1.4 Описание алгоритма С4.5 в случае вещественнозначной информации и наличия пропусков

1.5 О методах решения задачи распознавания, основанных на поиске информативных фрагментов в признаковых описаниях объектов. Связь с решающими деревьями

1.6 Основные выводы

Глава 2. Описание распознающих алгоритмов, основанных на построении полных решающих деревьев

2.1 Основные понятия и схемы построения полных решающих деревьев

2.2 Описание алгоритма Полный С4.5

2.3 Описание алгоритмов АС1.Уоюе, AGI.La.max, AGI.La.sum и А01.В1аз

2.4 Критерий выбора оптимального порога перекодировки

2.5 Основные выводы

Глава 3. Практические исследования распознающих процедур, основанных на построении полных решающих деревьев

3.1 Тестирование алгоритма Полный С4.5

3.2 Тестирование алгоритмов АСТУоюе, AGI.La.max и AGI.La.sum

3.3 Тестирование алгоритма АС1.В1аБ

3.4 Изучение переобученное™ распознающих процедур, основанных на построении полных решающих деревьев

3.5 Исследование полного решающего дерева как выпуклой корректирующей процедуры

3.6 Основные выводы

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

4.1 Числовые характеристики полного решающего дерева

4.2 Оценки емкости семейства полных решающих деревьев

4.3 Оценки времени синтеза полного решающего дерева

4.4 Применение теории отступов для анализа обобщающей способности полного решающего дерева

4.5 Исследование эмпирической радемахеровской сложности полного решающего дерева

4.6 Основные выводы

ЗАКЛЮЧЕНИЕ

БИБЛИОГРАФР1ЧЕСКИЙ СПИСОК

ПРИЛОЖЕНИЯ

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

ВВЕДЕНИЕ

Для решения прикладных задач классификации, распознавания и прогнозирования, возникающих в различных плохо формализованных областях, успешно применяются методы распознавания образов [2, 30, 40, 57, 86, 102]. Одной из центральных задач распознавания образов является задача распознавания по прецедентам, стандартная постановка которой заключается в следующем [39].

Исследуется некоторое множество объектов М. Объекты множества М описываются системой признаков {xj,. Известно, что множество М представимо в виде объединения непересекающихся подмножеств, называемых классами К^...,^, /> 2. Имеется конечное множество объектов (прецедентов

или обучающих объектов) {б*!,..из М, о которых известно каким классам

они принадлежат. Требуется по предъявленному описанию некоторого объекта из М определить класс, которому принадлежит этот объект.

Одним из известных инструментов решения рассматриваемой задачи являются деревья решений. Первые работы, связанные с построением деревьев решений, выполнены К. И. Ховлендом и Э. Б. Хантом [89-93] в конце 50-х начале 60-х годов XX века. Важные результаты для развития этого направления были получены в работе Э. Б. Ханта, Дж. Мэрина и Ф. Дж. Стоуна "Experiments in Induction" [94], вышедшей в 1966 году. Вопросы, связанные с построением решающих деревьев (РД), рассматривались в следующих работах: Г. X. Бабич [1], А. Ш. Блох [3], И. Л. Букатова [4], Р. С. Гольдман [16], В. А. Дискант [17], Г. Л. Жуков [38], А. Д. Закревский и Н. Р. Торопов [41], А. В. Карелина и Ю. Н. Печерский [43], А. М. Кукинов [47], Г. С. Лбов [48, 49], И. Б. Сироджа [55], В. И. Донской [20-24], Ю. Ю. Дюличева [23, 24, 27, 28], М. Ю. Мошков [51, 113, 114], А. Гловацки [84], Л. Н. Канал [95], А. В. Кулкарни [101], М. В. Курзински [103], Дж. My и К. С. Фу [82], X. Дж. Пайн и В. С. Мейзель [119], Д. А. Прис [123], Дж. Р. Куинлан [98, 124-127], Л. Брейман [67-70], X. Хауска и П. Ш.

Цвайн [87], П. А. Чу и Р. М. Грей [73, 74], В. Бунтин [71], Р. Кохави [96, 97], В. Подгорелец и П. Коколь [121, 122] , С. К. Мёрфи [115, 116], Дж. К. Мартин [108], Р. Е. Шапиро, Ю. Фреунд Л. Мейсон [79-81], Р. Керби, Э. Франк, Д. Голмес, Б. Фахрингер [88], В. Ю. Лох [104-106].

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

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

В работах Е. В. Дюковой, Н. В. Пескова [29, 75] предложена новая конструкция РД, названная полным решающим деревом (ПРД). В отличие от классического РД, в ПРД на каждой итерации строится так называемая полная вершина, которой соответствует набор признаков X. В набор X попадают все признаки, удовлетворяющие выбранному критерию ветвления. Далее по аналогии с классическим РД проводится ветвление по каждому из признаков, входящих в X. В ПРД, в отличие от классического РД, описание распознаваемого объекта 51 может попасть в разные листья ПРД. Поэтому, в указанных работах, при выборе класса, которому принадлежит объект 5",

использовался простейший вариант коллективного голосования по листьям дерева (голосование по большинству). Предложенная модель РД была успешно продемонстрирована в [29, 75] на примере усовершенствования алгоритма построения допустимого разбиения (АДР) [22].

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

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

Актуальной задачей является исследование обобщающей способности распознающего алгоритма (надежности и качества принятия решения), которая является фундаментальной проблемой в теории обучаемых систем (machine learning theory). С этой проблемой связаны вопросы переобученное™ (overfitting, overtraining) распознающего алгоритма. Переобученность распознающего алгоритма означает, что алгоритм слишком «подогнан» под обучающую информацию и, как следствие, качество распознавания на новых объектах оказывается плохим [7, 102, 118]. В середине 80-х годов получил широкое распространение подход к изучению обобщающей способности распознающих алгоритмов на основе статистической теории обучения Вапника-Червоненкиса [5, 6]. В основе данной теории лежит принцип

равномерной сходимости частоты ошибок на обучении к частоте ошибок на любой другой выборке. Для оценки скорости сходимости этих частот было введено понятие емкости исследуемого семейства решающих функций. Основной недостаток статистического подхода заключается в том, что вероятностные оценки качества решающей функции, базирующиеся на значении емкости используемого семейства решающих функций, оказываются сильно завышенными. В комбинаторной теории надежности по прецедентам, предложенной К. В. Воронцовым [7], были получены точные оценки вероятности переобучения для ряда модельных семейств алгоритмов, учитывающие эффект расслоения и связности рассматриваемого семейства решающих функций. Точные оценки требуют доработки и адаптации с учетом особенностей прикладной задачи и используемого семейства решающих функций [7]. На практике популярностью пользуются оценки вероятностности ошибки классификатора, основанные на понятии радемахеровской сложности семейства решающих функций [66, 99, 100] и на понятии отступа (margin) обучающего объекта от границы класса [85, 102, 109, 130], которому принадлежит этот объект.

Представляют интерес задачи изучения комбинаторной сложности РД (получения оценок мощности множества вершин и мощности множества ребер) и временной сложности синтеза РД.

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

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

В диссертационной работе были сформулированы следующие задачи.

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

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

2. Изучение обобщающей способности ПРД, а именно получение оценок емкости семейства ПРД. Исследование эмпирической радемахеровской сложности ПРД. Получение оценки обобщающей способности ПРД с применением теории отступов. Разработка методики снижения переобученное™ ПРД.

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

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

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

Практические результаты. Показано, что построенные в работе распознающие алгоритмы на основе ПРД дают более высокое качество распознавания по сравнению с классическими методами построения РД (С4.5 [125], АДР, CART [67]) на большинстве рассмотренных реальных задачах. Проведено также сравнение с более современными методами распознавания, использующими РД, такими как LADTree [88], RandomForest [68] и С5.0 [126], которое показало, что разработанные алгоритмы не менее эффективны на большинстве задач, а в некоторых случаях показывают лучшее качество классификации. Аналогичные результаты получены и при сравнении с алгоритмом вычисления оценок [40], стохастическим алгоритмом голосования по тупиковым тестам [37, 40] и нейронной сетью [40].

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

Теоретические результаты. Развит подход к синтезу ПРД. Построены и

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

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

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

Публикации. По теме диссертации опубликовано 9 печатных работ [8-15, 83]; из них 4 статьи входят в список ВАК РФ [13-15, 83]. Описания основных результатов включались в отчеты РФФИ 07-01 -00516-а, 10-01-00770-а и в отчеты по грантам президента РФ по поддержке ведущих научных школ НШ

№5294.2008.1 и НШ №7950.2010.1.

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

В главе 1 рассмотрены методы построения РД в распознающих алгоритмах АДР и С4.5. Показана связь алгоритмов АДР и С4.5 с распознающими алгоритмами, основанными на поиске информативных фрагментов в признаковых описаниях объектов [33, 34, 36].

В разделе 1.1 введены основные понятия, используемые в работе. Для задачи с целочисленными признаками описана процедура синтеза РД.

Показано, что ветви РД, порожденной внутренними вершинами хл,...,х] ,

можно поставить в соответствие пару {В,К), где К е {КХ,...,К1}, а В -элементарная конъюнкция (э.к.) вида , где сг - метка дуги, выходящая

из вершины xJ , i = 1 ,...,г, ха = 1, если х = сг, и ха = 0 иначе.

Наиболее часто применяется следующее решающее правило. Пусть построено РД с /л листьями [В^К^^^В^К^. Из построения РД следует,

что если найдется /, / е (1,...,//}, такое, что где Nв - интервал

истинности э.к. Вр то 5" относится к классу К]. В противном случае

происходит отказ от распознавания.

В разделе 1.2 описан алгоритм АДР, строящий корректное БРД. В разделах 1.3 и 1.4 описан алгоритм С4.5 для двух случаев: 1) для задачи с целочисленной информацией; 2) для задачи с вещественнозначной информацией и с наличием пропусков в признаковых описаниях объектов.

Выбор признака для построения внутренней вершины РД в алгоритме С4.5 осуществляется на основе энтропийного критерия.

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

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

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

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

В разделе 1.5 на примере алгоритмов голосования по представительным наборам показана связь РД с логическими методами поиска информативных фрагментов в признаковых описаниях обучающих объектов [31, 33-35, 37, 39]. Продемонстрировано, что алгоритм АДР строит некоторое множество представительных наборов. Алгоритм С4.5 нацелен на построение «почти» представительных наборов для каждого класса К, т.е. таких фрагментов, которые наиболее часто встречаются в описаниях обучающих объектов класса К и достаточно редко в описаниях обучающих объектов из других классов.

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

В разделе 2.1 приведены основные понятия, используемые при построении ПРД, и для указанных выше случаев описаны основные принципы синтеза ПРД.

Пусть v — висячая вершина дерева, порожденная ветвью с обычными вершинами xj{,...,xj ,и сг(, г е{1,...,г}, — метка дуги, выходящая из вершины Xj .

Определение 2.2. Набор Nv={ax,...,an) называется порождающим набором для листа v, если aj = <т, при i = l,...,r, и cCj="*" при j g Ц,...,уг}.

Каждой висячей вершине ПРД ставится в соответствие пара

(JVv,{fflJ,...,£»'}), где Nv - порождающий набор для вершины v, -

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

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

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

Приведем описание решающих правил, используемых при классификации распознаваемого объекта S = (bv...,bn) с помощью ПРД.

В случае целочисленной информации низкой значности под описанием объекта S в вершине v понимается вектор S(v) = (Д,...,в котором Ph = bj

при г = 1 ,...,г, иначе Р- = "* ".

В случае вещественнозначной информации под описанием объекта S в вершине v понимается вектор S(v) = (/3},...,/3n), в котором fij =1, если

bJt >d(xJt), иначе Ph =0 при z' = l,...,r, и р. ="*" при j £{jx,...,jr).

Определение 2.10. Лист v называется голосующим за S, если S(v) = Nv. Пусть Q(S) - множество всех голосующих листьев ПРД за объект S. Для каждого /е{1,...,/} вычисляется оценка принадлежности объекта S классу Kt,

имеющая вид = , / = 1,...,/. Объект S зачисляется в класс Кп

если Г(5',^:;.)=шахГ(5',^), z = l,...,/, r(S,Ki)* r(S,Kj) при z* j, j = \,...,/.

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

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

Опишем ситуацию, когда в описаниях объектов имеются пропуски.

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

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

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

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

В разделе 2.3 описаны алгоритмы AGI.Voice, AGI.La.max, AGI.La.sum и AGI.Bias, использующие схемы синтеза ПРД из разд. 2.1 для задач классификации с вещественнозначной информацией и с наличием пропусков в признаковых описаниях объектов. Отличие указанных алгоритмов друг от

друга заключается в способе вычисления оценки û)lv, i е {1,...,/}, для висячей вершины v. Процедура выделения набора признаков, образующего полную вершину, аналогична процедуре, используемой в алгоритме Полный С4.5.

В разделе 2.4 описан критерий выбора оптимального порога d{x) для бинарной перекодировки текущих значений признака х, используемый в алгоритмах AGI.Voice, AGI.La.max, AGI.La.sum и AGI.Bias. Выбор порога d{x) позволяет оценить информативность признака х, и в дальнейшем из наиболее информативных признаков построить полную вершину ПРД.

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

В главе 3 проведено тестирование на прикладных задачах разработанных алгоритмов: Полный С4.5, AGI.Voice, AGI.La.max, AGI.La.sum и AGI.Bias. Качество этих алгоритмов оценивалось методом скользящего контроля («leave-one-out», LOO) [86, 102].

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

В разделе 3.1 проведено сравнение алгоритма Полный С4.5 с алгоритмами Полный АДР (усовершенствованный с помощью ПРД алгоритм АДР) [29, 75] и С4.5 [125].

В разделах 3.2 и 3.3 проведено сравнение алгоритмов AGI.La.max, AGI.Voice, AGI.La.sum и AGI.Bias с алгоритмом С5.0 (усовершенствованная версия алгоритма С4.5) [126] и с алгоритмами из системы «Распознавание 2.0» [40], а именно с нейронной сетью, алгоритмом вычисления оценок, стохастическим алгоритмом голосования по тупиковым тестам, линейным дискриминантом Фишера, алгоритмом построения РД с применением генетического метода, методом синтеза БРД и с методом к ближайших соседей. Алгоритмы AGI.La.sum и AGI.Bias также сравнивались с алгоритмами из системы «WEKA» [132], а именно с алгоритмом J48 (аналог алгоритма С4.5), SimpleCART (аналог алгоритма CART [67]), RandomForest [68] («бэггинг» над РД) и LADTree [88] («бустинг» [80, 81] над РД). Тестирование алгоритмов проводилось на 25 реальных задачах, собранных в отделе Математических проблем распознавания и методов комбинаторного анализа ВЦ РАН.

На шести задачах проведен ROC-анализ [77, 78] алгоритмов НС, ГМ,

1 ^ А Ъ/

ГТТ, AGI.La.sum и AGI.Bias.

В разделе 3.4 предложена процедура снижения эффекта переобучения ПРД. Первый этап процедуры - синтез начального ПРД с использованием методики, описанной в разд. 2.1, и вычисление характеристик дерева, а именно: средней глубины дерева, обозначаемой D, и среднего числа обучающих объектов J, описания которых попадают в висячую вершину дерева. Второй этап процедуры - синтез итогового ПРД. Итоговое ПРД отличается от начального ПРД тем, что текущая ветвь обрывается и строится лист дерева, если глубина текущей ветви превышает значение D или число объектов в текущем множестве обучающих объектов меньше значения J. Также рассматривались варианты построения итогового ПРД с использованием одной из указанных характеристик и с небольшими отступами от точных значений. Указанная методика исследована на примере алгоритма AGI.Bias.

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

В главе 4 получены точные оценки мощности множества вершин ПРД и мощности множества ребер ПРД, верхние оценки емкости (VCD) [5, 6] семейства бинарных ПРД (БПРД) и оценки времени синтеза ПРД. На основе понятий из теории отступов получена оценка обобщающей способности ПРД. Проведено исследование эмпирической радемахеровской сложности ПРД.

В разделе 4.1 в случае, когда из каждой обычной вершины в ПРД выходят ровно две дуги, получены значения числовых характеристик ПРД в зависимости от глубины дерева к. Найдено максимальное число полных вершин FV(k), максимальное число обычных вершин SV(k), максимальное число листьев L(k), максимальное число ребер R(k). Показано, что к<гтп{п,т — 1}.

Обозначим через А* - число размещений из п по к.

Теорема 4.1.1. Имеет место

1А

А V

m*)=Zl12"4'1,sr(k)=zl12i-i4, т=2к4, т=з sv^.

В разделе 4.2 с помощью метода программирования оценки емкости (pVCD) [25, 26], предложенного В. И. Донским, получены верхние оценки емкости семейства БПРД. Метод pVCD основан на понятии Колмогоровской сложности конечных объектов [45] и заключается в получении сжатого двоичного описания элемента рассматриваемого семейства.

Пусть FDM l n к - семейство БПРД с не более fi листьями и глубиной не

более к, в котором БПРД строится для задачи распознавания с п признаками и / классами. Обозначим через WCD(FD^ 1пк) - емкость семейства FDM 1пк.

С использованием метода pVCD получена следующая оценка VCD {FD^nk )<М(к + 321) + ((к + 2)ju -1) [log(« + 2)].

В разделе 4.3 на примере алгоритма AGI.Bias получены оценки времени Т(п,т,1) синтеза ПРД.

Пусть к — глубина ПРД.

Теорема 4.3.1. Имеет место следующая оценка времени построения ПРД:

Tin,т,I) = 0{Акп (т - к)(т -к +1)1) + 0(Акп (т - к)(п - к +1)). Теорема 4.3.3. Если на каждом шаге построения ПРД в полную вершину попадает не больше трех признаков из Х(Т), то

Т(п, m, 1) = 0( З*"1 (т - к)(п -к+ \){т-к +1)/) + (9(3* (т - к)(п - к +1)) . В разделе 4.4 с использованием понятий из теории отступов для задачи с двумя классами получена оценка обобщающей способности ПРД. На реальных задачах проанализированы распределения отступов обучающих объектов.

Пусть D - распределение на Мх{-1,1}, Г = {51,...,5'т} - множество

обучающих объектов выбранных независимо и случайно из D.

Показано, что решающая функция FDT(S) на основе ПРД с ¡л листьями для объекта S может быть представлена в следующем виде:

FDT(S) = sgn

Zt^A(S)

, где ст. е{-1,1} - метка класса для /-ого листа,

1 7

J. /

jff. (iS) = 1, если описание объекта S принадлежит NB , иначе

Bt(S) = 0, г = 1,...,/л.

Пусть U = 5 где Rj - множество предикатов для признака Xj, э.к.

Bi - конъюнкция предикатов, i е {1,...,//}.

Теорема 4.4.3. Пусть VCD(U) - емкость семейства U, и пусть д > О. Тогда с вероятностью не меньше \-д над множеством Т, для каждой решающей функции FDT(S) и для любого в > 0 справедливо

/д [error] < 2РТ (margin < в) + с/т(\/в2 (vlnm + lnd)ln (m02/v} + ln(l/<5)),

где /^(margin < в) - вероятность того, что отступ для случайно выбранного объекта из Т не превысит величины в, [error] - вероятность ошибки ПРД на

объекте S еМ, v = ^^a^yCDiU), d = max, dt, di - глубина i-ого листа.

В разделе 4.5 на прикладных задачах проведено исследование эмпирической радемахеровской сложности ПРД.

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

Заключение диссертации по теме «Теоретические основы информатики», Генрихов, Игорь Евгеньевич

Основные результаты диссертации.

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

2. Исследованы вопросы обобщающей способности ПРД. С помощью метода рУСЭ получена верхняя оценка емкости семейства БПРД. Для задачи с двумя классами на основе теории отступов получена оценка обобщающей способности семейства ПРД. Экспериментально изучена эмпирическая радемахеровская сложность ПРД. Разработана и исследована методика снижения переобученности ПРД.

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

ЗАКЛЮЧЕНИЕ

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

Список литературы диссертационного исследования кандидат физико-математических наук Генрихов, Игорь Евгеньевич, 2013 год

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Бабич Г. X. Принятие решений на основе анализа дерева решений в условиях неполноты информации // Кибернетика. - 1986. - № 5. - С. 113120.

2. Барсегян А. А., Куприянов М. С., Степаненко В. В., Холод И. И. Методы и модели анализа данных: OLAP и Data Mining. - Спб.: БХВ-Петербург, 2004.-336 с.

3. Блох А. Ш. Об одном алгоритме обучения для задач по распознаванию образов // Вычислительная техника в машиностроении. - 1966. - №10. -С. 37-43.

4. Букатова И. Л. Эволюционное моделирование и его приложения. - М.: Наука, 1979.-231 с.

5. Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.-448 с.

6. Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. - М.: Наука, 1974.-416 с.

7. Воронцов К. В. Комбинаторная теория надёжности обучения по прецедентам: Дис. док. физ.-мат. наук: 05-13-17. - М.: ВЦ РАН, 2010. -271 с.

8. Генрихов И. Е., Дюкова Е. В. Полные решающие деревья в задачах классификации по прецедентам // Всеросс. конф. Математические методы распознавания образов-15. - М.: МАКС Пресс, 2011. - С. 84-87.

9. Генрихов И. Е., Дюкова Е. В. Исследование комбинаторных свойств и сложности построения полных решающих деревьев // Всеросс. конф. Математические методы распознавания образов-15. - М.: МАКС Пресс, 2011.-С. 88-91.

10. Генрихов И. Е. Построение полного решающего дерева на базе алгоритма С4.5 // Сообщение по прикладной математике. - М.: ВЦ РАН, 2009. - 24 с.

11. Генрихов И. Е., Дюкова Е. В. Усовершенствование алгоритма С4.5 на основе использования полных решающих деревьев // Всеросс. конф. Математические методы распознавания образов-14. - М.: МАКС Пресс, 2009.-С. 104-107.

12. Генрихов И. Е., Дюкова Е. В. Построение и исследование распознающих процедур на основе полных решающих деревьях // Междунар. конф. Интеллектуализация обработки информации-8. - М.: МАКС Пресс, 2010. — С. 117-120.

13. Генрихов И. Е., Дюкова Е. В. Классификация на основе полных решающих деревьев // Ж. вычисл. матем. и матем. физ. - 2012. - Т. 52, № 4. - С. 750761.

14. Генрихов И. Е. Исследование переобученное™ распознающих процедур на основе полных решающих деревьев // Программные продукты и системы. -2011.-№ 4 (96).-С. 141-147.

15. Генрихов И. Е. О сложности построения полных решающих деревьев // Естественные и технические науки. — 2012. - № 1 (57). - С. 327-336.

16. Гольдман С. Р. Логические методы диагноза непрерывных объектов // Автоматика и телемеханика. — 1979. - № 5.

17. Дискант В. А. Алгоритмы построения правил классификации в структурно-аналитических моделях распознавания // Математические методы анализа динамических систем. - 1983. - № 7. - С. 124-127.

18. Дискретная математика и математические вопросы кибернетики. Т. 1. / Под ред. С. В. Яблонского и О. Б. Лупанова. - М.: Наука, 1974. - 312 с.

19. Дмитриев А. И., Журавлев Ю. И., Кренделев Ф. П. О математических принципах классификации предметов или явлений // Дискретный анализ. — Новосибирск: ИМ СО АН СССР, 1966. - № 7. - С. 3-17.

20. Донской В. И. Алгоритмы обучения, основанные на построении решающих деревьев // ЖВМиМФ. - 1982. - Т. 22, № 4. - С. 963-974.

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

интеллекта и распознавания образов: Тезисы докл. - Киев, 1984. - С. 45-47.

22. Донской В. И., Башта А. И. Дискретные модели принятия решений при неполной информации. - Симф.: Таврия, 1992. - 166 с.

23. Донской В. И., Дюличева Ю. Ю. Алгоритмы синтеза г-редуцированного эмпирического леса // Математические методы распознавания образов: 11-ая Всерос. конф. Тезисы докл. - Пущино, 2003. - С. 71-74.

24. Донской В. И., Дюличева Ю. Ю. Деревья решений с к-значными переменными // Междунар. конф. "Знание - Диалог - Решение". — Спб.: Лань, 2001. - Т. 1. - С. 201 -207.

25. Донской В. И. Колмогоровская сложность классов общерекурсивных функций с ограниченной емкостью // Таврический вестник информатики и математики. - 2005. - № 1. - С. 25-34.

26. Донской В. И. Оценки емкости классов алгоритмов эмпирического обобщения, полученные рУСБ методом // Ученые записки Таврического национального университета им. В. И. Вернадского. - 2010. - Том 23 (62), №2.-С. 56-65.

27. Дюличева Ю. Ю. Принятие решений на основе индуктивной модели эмпирического леса // Искусственный интеллект. - 2002. - № 2. — С. 110115.

28. Дюличева Ю. Ю. Модели коррекции редуцированных бинарных решающих деревьев: Дис. канд. физ.-мат. наук: 01.05.01. - Симф.: Таврический национальный ун-т им. В. И. Вернадского, 2004. - 127 с.

29. Дюкова Е. В., Песков Н. В. Об алгоритме классификации на основе полного решающего дерева // Всеросс. конф. Математические методы распознавания образов-13. - М.: МАКС Пресс, 2007. - С. 125-126.

30. Дюкова Е. В. Алгоритмы распознавания типа Кора: сложность реализации и метрические свойства // Распознавание, классификация, прогноз (матем. методы и их применение). - М.: Наука, 1989. — № 2. - С. 99-125.

31. Дюкова Е. В. Дискретные (логические) процедуры распознавания: принципы конструирования, сложность реализации и основные модели.

Учебное пособие для студентов математических факультетов педвузов. -М.: МПГУ, 2003.-30 с.

32. Дюкова Е. В., Журавлев Ю. И. Дискретный анализ признаковых описаний в задачах распознавания большой размерности // ЖВМиМФ. - 2000. - Т. 40, №8. -С. 1264-1278.

33. Дюкова Е. В., Журавлёв Ю. И., Рудаков К. В. Об алгебро-логическом синтезе корректных процедур распознавания на базе элементарных алгоритмов // ЖВМиМФ. - 1996. - Т. 36, № 8. - С. 215-223.

34. Дюкова Е. В., Инякин А. С. Задача таксономии и тупиковые покрытия целочисленной матрицы // Сообщения по прикладной математике. - М.: ВЦ РАН, 2001.-28 с.

35. Дюкова Е. В., Песков Н. В. Поиск информативных фрагментов описаний объектов в дискретных процедурах распознавания // ЖВМиМФ. - 2002. -Том 42, №5.-С. 741-753.

36. Дюкова Е. В., Журавлев Ю. И., Песков Н. В., Сахаров А. А. Обработка вещественнозначной информации логическими процедурами распознавания // Искусственный интеллект. - 2004. - № 2. - С. 80-85.

37. Дюкова Е. В. Асимптотически оптимальные тестовые алгортимы в задачах распознавания // Проблемы кибернетики. - 1982. - Т. 39. - С. 165-199.

38. Жуков JI. Г. Об одном алгоритме индуктивного формирования понятий // Вопросы кибернетики. - М.: Наука, 1977. - № 18. - С. 167-171.

39. Журавлев Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. - 1978. - № 33.-С. 5-68.

40. Журавлев Ю. И., Рязанов В. В., Сенько О. В. Распознавание. Математические методы. Программная система. Практические применения. - М.: ФАЗИС. - 2006.

41. Закревский А. Д., Торопов Н. Р. Обучение распознаванию образов в булевом пространстве // Самообучающиеся автоматические системы. -1966. - М.: Наука. - С. 67-72.

42. Иванов Б. Н. Дискретная математика. Алгоритмы и программы. -М.: Лаборатория Базовых Знаний, 2003. - 288 с.

43. Карелина А. В., Печерский Ю. Н. Теоретико-графовые методы в распознавании образов. - Кишинев: Штиинца, 1978. - 91 с.

44. Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников. - М.: ФИЗМАТЛИТ, 2006. - 814 с.

45. Колмогоров А. Н. Теория информации и теория алгоритмов. - М.: Наука, 1987.-304 с.

46. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. / Пер. с англ. под ред. А. Шеня. - М.: МЦНМО, 2002. - 955 с.

47. Кукинов А. М. О некоторых рекуррентных алгоритмах обучения классификации // Математическая обработка медико-биологической информации. - М.: Наука, 1976. — С. 46-57.

48. Лбов Г. С. Методы обработки разнотипных экспериментальных данных. -Новосибирск: Наука, 1981. - 160 с.

49. Лбов Г. С., Котюков В. И., Манюхин А. И. Об одном алгоритме распознавания в пространстве разнотипных признаков // Вычислительные системы. - 1973. - Т. 55. - С. 98-107.

50. Матросов В. Л., Стеценко В. А. Лекции по дискретной математике. Учебное пособие для магистрантов математических факультетов педагогических университетов. - М.: Прометей, 1997. - 220 с.

51. Мошков М. Ю. Деревья решений. Теория и приложения. Учебное пособие. - Н. Новгород: изд-во Нижегородского ун-та, 1994. - 175 с.

52. Новиков Ф. А. Дискретная математика для программистов. Учебник для вузов / Ф. А. Новиков. - 2-е изд. - СПб.: Питер, 2006. - 364 с.

53. Полигон: веб-система для тестирования алгоритмов классификации на реальных и модельных данных, 2008. URL: http://poligon.machinelearning.ru/ (дата обращения: 03.06.2010).

54. Реброва О. Ю. Применение методов интеллектуального анализа для решения задачи медицинской диагностики // Новости искусственного

интеллекта. - 2004. - № 3. - С. 76-80.

55. Сироджа И. Б. Системный анализ структурно-аналитических алгоритмов распознавания образов для автоматизации классификационной обработки данных КОД // Модели и системы обработки данных. - 1978. - № 2. - С. 79-102.

56. Ту Дж., Гонсалес Р. Принципы распознавания образов. / Пер. с англ. под ред. Ю. И. Журавлева. - М.: Мир, 1978. - 414 с.

57. Тюрин Ю. Н., Макаров А. А. Анализ данных на компьютере. - М.: Инфра-М, 2003. - 544 с.

58. Чегис И. А., Яблонский С. В. Логические способы контроля электрических схем // Труды МИАН СССР. - 1958. - Т. 58. - С. 270-360.

59. Шеннон К. Работы по теории информации и кибернетике. / Пер. с англ. под ред. Р. Л. Добрушина и О. Б. Лупанова. - М.: Издательство иностранной литературы, 1963. - 836 с.

60. Яблонский С. В. Введение в дискретную математику. Учебное пособие для вузов. - М.: Наука, 1986. - 384 с.

61. Яглом А. М., Яглом И. М. Вероятность и информация. - М.: Наука, 1973. -512 с.

62. Aha D. W., Breslow L. A. Simplifying decision trees: A survey // The Knowledge Engineering. - Cambridge University Press, New York, 1997. -Vol. 12, no. l.-Pp. 1-40.

63. Anyanwu M., Shiva S. Comparative analysis of serial decision tree classification algorithms // International Journal of Computer Science and Security. - 2009. -Vol. 3, no. 3.-Pp. 230-240.

64. Asuncion A., Newman D. UCI Machine learning repository [http://www.ics.uci.edu/~mlearn/MLRepository.html]. Irvine, CA: University of California, School of Information and Computer Science, 2007. (дата обращения: 15.02.2009).

65. Bartlett P. L. For valid generalization the size of the weights is more important than the size of the network // Advances in Neural Information Processing

Systems. - 1997. - Vol. 9. - Pp. 134-140.

66. Bartlett P. L., Mendelson S. Rademacher and Gaussian complexities: Risk bounds and structural results // Journal of Machine Learning Research. - 2002. -Vol.3.-Pp. 463-482.

67. Breiman L., Friedman J. H., Olshen R. A., Stone C. J. Classification and regression trees. - Belmont, California, U.S.A.: Wadsworth Publishing Company, 1984.-368 p.

68. Breiman L. Random forests // Machine Learning. - 2001. - Vol. 45, no. 1. - Pp. 5-32.

69. Breiman L. Bias, variance, and arcing classifiers: Tech. Rep. 460: Statistics Department, University of California, 1996.

70. Breiman L. Bagging predictors // Machine Learning. - 1996. - Vol. 26, no. 2. -Pp. 123-140.

71. Buntine W. Learning classification trees // Statistics and Computing. - 1992. -Vol. 2.-Pp. 63-73.

72. Burges C. J. C. A tutorial on support vector machines for pattern recognition // Data Mining and Knowledge Discovery. - 1998. - Vol. 2, no. 2. - Pp. 121-167.

73. Chou P. A., Gray R. M. On decision trees for pattern recognition // IEEE Symposium on Information Theory, Ann Arbor, Michigan, 1986. - 69 p.

74. Chou P. A., Lookabaugh T., Gray R. M. Optimal pruning with applications to tree-structured source coding and modeling // IEEE Transactions on Information theory. - 1989. - Vol. 35. - Pp. 299-315.

75. Djukova E. V., Peskov N. V. A classification algorithm based on the complete decision tree // Pattern Recognition and Image Analysis. - 2007. - Vol. 17, no. 3. -Pp. 363-367.

76. Djukova E. V., Peskov N. V. Selection of typical objects in classes for recognition problems // Pattern Recognition and Image Analysis. - 2002. - Vol. 12, no. 3.-Pp. 243-249.

77. Fawcett T. ROC graphs: notes and practical considerations for researchers // HP Labs Tech Report.-2003.-Vol. 31, no. 4.-Pp. 1-38.

78. Fawcett T. An introduction to ROC analysis // Pattern Recognition Letters. -2006. - Vol. 27, no. 8. - Pp. 861-874.

79. Freund Y., Mason L. The alternating decision tree learning algorithm // International Conference on Machine Learning. - Morgan Kaufmann, 1999. -Pp. 124-133.

80. Freund Y., Schapire R. E. Experiments with a new boosting algorithm // International Conference on Machine Learning. - Morgan Kaufmann, 1996. -Pp. 148-156.

81. Freund Y., Schapire R. E. A decision-theoretic generalization of on-line learning and an application to boosting // European Conference on Computational Learning Theory. - 1995. - Pp. 23-37.

82. Fu K. S., Mui J. Automated classification of nucleated blood cells using a binary tree classifier // IEEE Transactions on Pattern Analysis and Machine Intelligence. - 1980. - Vol. 2, no. 5. - Pp. 429-443.

83. Genrikhov I. E. Synthesis and analysis of recognizing procedures on the basis of full decision trees // Pattern Recognition and Image Analysis. - 2011. - Vol. 21, no. l.-Pp. 45-51.

84. Glovazky A. Determination of redundancies is a set of patterns // IEEE Transactions on Information Theory. - 1956. - Vol. 2, no. 4. - Pp. 151-153.

85. Golea M., Bartlett P. L., Lee W. S., Mason L. Generalization in decision trees and DNF: Does size matter? // Advances in Neural Information Processing Systems. -1998. - Vol. 10. - Pp. 259-265.

86. Han J., Kamber M. Data mining: concepts and techniques. - Morgan Kaufmann, 2006. - 743 p.

87. Hauska H., Swain P. H. The decision tree classifier: design and potential // IEEE Transactions on Geoscience Electronics. - 1975. - Vol. 15, no. 3. - Pp. 142-147.

88. Holmes G., Pfahringer B., Kirkby R., Frank E., Hall M. Multiclass alternating decision trees // European Conference on Machine Learning. - Springer-Verlag, 2002.-Pp. 105-122.

89. Hovland C. I., Hunt E. B. The computer simulation of concept attainment //

Behavioral Science. - 1960. - Vol. 5, no. 3. - Pp. 265-267.

90. Hovland C. I., Hunt E. B. Order of consideration of different types of concepts // Experimental Psychology. - 1960. - Vol. 59, no. 4. - Pp. 220-225.

91. Hovland C. I. Computer simulation of thinking // American Psychologist. -1960.-Vol. 15, no. 11.-Pp. 687-693.

92. Hovland C. I., Hunt E. B. Programming a model of human concept formulation // Proceedings of the Western Joint Computer Conference, AFIPS 19. - 1961. -Pp. 145-155.

93. Hunt E. B. Concept learning: an information processing problem. - New York: Wiley, 1962.-286 p.

94. Hunt E. B., Marin J., Stone P. J. Experiments in induction. - New York: Academic Press, 1966. - 247 p.

95. Kanal L. N. Problem-solving models and search strategies for pattern recognition // IEEE Transactions on Pattern Analysis and Machine Intelligence. -1979.-Vol. 1, no. 2.-Pp. 193-201.

96. Kohavi R., Kunz C. Option decision trees with majority votes // International Conference on Machine Learning. - Morgan Kaufmann, 1997. - Pp. 161-169.

97. Kohavi R. Scaling Up the accuracy of Naive-Bayes classifiers: a decision-tree hybrid // International Conference on Knowledge Discovery and Data Mining. -1996.-Pp. 202-207.

98. Kohavi R., Quinlan J. R. Decision tree discovery // Handbook of Data Mining and Knowledge Discovery. - Oxford University Press, 2002. - Pp. 267-276.

99. Koltchinskii V. Rademacher penalties and structural risk minimization // IEEE Transactions on Information Theory. - 2001. - Vol. 47, no 5. - Pp. 1902-1914.

100. Koltchinskii V., Panchenko D. Empirical margin distributions and bounding the generalization error of combined classifiers // The Annals of Statistics. - 2002. -Vol.30, no. l.-Pp. 1-50.

101.Kulkarni A. V. On the mean accuracy of hierarchical classifiers // IEEE Transactions on Computers. - 1978. - Vol. 27, no. 8. - Pp. 771-776.

102. Kuncheva L. I. Combining pattern classifiers methods and algorithms. - John

Wiley & Sons, Inc., Hoboken, New Jersey, 2004. - Pp. 154-163.

103. Kurzynski M. W. The optimal strategy of a tree classifier // Pattern Recognition. - 1983.-Vol. 16, no. l.-Pp. 81-87.

104. Loh W. Y., Kim H. Classification trees with bivariante linear discriminant node models // Computational and Graphical Statistics. - 2003. - Vol. 12, no. 3. - Pp. 512-530.

105. Loh W. Y., Vanichsetakul N. Tree-structured classification via generalized discriminant analysis // American Statistical Association. - 1988. - Vol. 83. -Pp. 715-728.

106. Loh W. Y. Regression trees with unbiased variable selection and interaction detection // Statistica Sinica. - 2002. - Vol. 12. - Pp. 361-386.

107. Lozano F. Model selection using Rademacher penalization // In Proceedings of the 2nd ICSC Symposium on Neural Computation (NC2000). Berlin, Germany. 2000 ICSC Academic Press.

108. Martin J. K. An exact probability metric for decision tree splitting and stopping // Machine Learning. - 1997. - Vol. 28, no. 2-3. - Pp. 257-291.

109. Mason L. Margins and combined classifiers: A thesis submitted for the degree of Doctor of Philosophy of The Australian National University. - 1999. - 118 p.

110. Mason L., Bartlett P. L., Golea M. Generalization error of combined classifiers // Computer and System Sciences. - 2002. - Vol. 65, no 2. - Pp. 415-438.

111. McDiarmid C. On the method of bounded differences. In: Surveys in Combinatorics // J. Siemons (Ed.), London Mathematical Soc. Lecture Notes, 141, Cambridge Univ. Press. - 1989. - Pp. 148-188.

112. Michie D., Spiegelhalter D. J., Taylor C. C. Machine learning, neural and statistical classification. - London: Ellis Horwood, 1994. - 298 p.

113. Moshkov M. J. On decision trees for (1, 2)-Bayesian networks // Fundamenta Informaticae. - 2002. - Vol. 50, no. 1. - Pp. 57-76.

114. Moshkov M. J. Greedy algorithm with weights for decision tree construction // Fundamenta Informaticae. - 2010. - Vol. 104, no. 3. - Pp. 285-292.

115. Murthy S. K. On growing better decision trees from data: Ph. D. dissertation /

Johns Hopkins University, Baltimore, Maryland, 1997. - 198 p.

116. Murthy S. K. Automatic construction of decision trees from data: A multi-disciplinary survey // Data Mining and Knowledge Discovery. - 1998. - Vol. 2, no. 4.-Pp. 345-389.

117. Neville J., Jensen D., Friedland L., Hay M. Learning relational probability trees // International Conference on Knowledge Discovery and Data Mining. - 2003. - Pp. 625-630.

118. Nilsson N. J. Introduction to machine learning. - Department of Computer Science, Stanford University, CA, 1998. - Pp. 81-96.

119. Payne H. J., Meisel W. S. An algorithm for constructing optimal binary decision trees // IEEE Transactions on Computers. - 1977. - Vol. 26, no. 9. - Pp. 905916.

120. Peng L., Lei L. A review of missing data treatment methods // Intelligent Information Management Systems and Technologies. - 2005. - Vol. 1, no. 3. -Pp. 412-419.

121. Podgorelec V., Kokol P., Stiglic В., Rozman I. Decision trees: an overview and their use in medicine // Medical Systems. - Kluwer Academic/Plenum Press, 2002. - Vol. 26, no. 5. - Pp. 445-463.

122. Podgorelec V., Kokol P. Evolutionary decision forests - decision making with multiple evolutionary constructed decision trees // Problems in Applied Mathematics and Computational Intelligence. - WSES Press, 2001. - Pp. 97103.

123. Preece D. A. Identification keys and diagnostic tables // Math. Scientist. - 1976. -Vol. l.-Pp. 43-56.

124. Quinlan J. R. Bagging, boosting, and C4.5 // Proceedings of 13th National Conference on Artificial Intelligence. - 1996. - Pp. 725-730.

125. Quinlan J. R. C4.5: Programs for machine learning. - Morgan Kaufmann, San Mateo, CA, 1993.-302 p.

126. Quinlan J. R. See5/C5.0 DEMO, RULEQUEST RESEARCH, 2008. URL: http://www.rulequest.com/see5-info.html (дата обращения: 10.03.2010).

127. Quinlan J. R. Induction of decision trees // Machine Learning. - Kluwer Academic Publishers, Boston, 1986. - Vol. 1, no. 1. - Pp. 81-106.

128. Safavian S. R., Landgrebe D. A. Survey of decision tree classifier methodology // IEEE Transactions on Systems, Man and Cybernetics. - 1991. - Vol. 21, no. 3.-Pp. 660-674.

129. Sauer N. On the density of families of sets // Combinatorial theory Series A. — 1972.-no 13.-Pp. 145-147.

130. Schapire R. E., Freund Y., Lee W. S., Bartlett P. L. Boosting the margin: a new explanation for the effectiveness of voting methods // Annals of Statistics. -1998.-Vol. 26, no. 5.-Pp. 1651-1686.

131. Senko О. V., Dokukin A. A. Optimal forecasting based on convex correcting procedures // New Trends in Classification and Data Mining. ITHEA, Sofia. -2010.-Pp. 62-72.

132. WEKA: suite of machine learning software, developed at the University of Waikato, New Zealand, 2009. URL: http://www.cs.waikato.ac.nz/~ml/weka/ (дата обращения: 20.11.2010).