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

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

ГЕНРИХОВ ИГОРЬ ЕВГЕНЬЕВИЧ

ПОСТРОЕНИЕ И ИССЛЕДОВАНИЕ ПОЛНЫХ РЕШАЮЩИХ ДЕРЕВЬЕВ ДЛЯ ЗАДАЧ КЛАССИФИКАЦИИ ПО ПРЕЦЕДЕНТАМ

05.13.17 - теоретические основы информатики

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

2 б СЕН 2013

Москва-2013

005533824

Работа выполнена на кафедре теоретической информатики и дискретной математики математического факультета в Федеральном государственном бюджетном образовательном Учреждении Высшего профессионального образования Московский педагогический государственный университет

Научный руководитель: доктор физико-математических наук, профессор

Дюкова Елена Всеволодовна Официальные оппоненты: Сенько Олег Валентинович, доктор физико-

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

науки Институт математики и механики им. Н. Н. Красовского Уральского отделения Российской академии наук

Защита диссертации состоится <<2Ч »оухцд!^ 2013 г. в 1к00 часов на заседании диссертационного совета Д 002.017.02 при Федеральном государственном бюджетном Учреждении науки Вычислительный центр им. А. А. Дородницына Российской академии наук по адресу: 119333, Москва, ул. Вавилова, дом 40, конференц-зал.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного Учреждения науки Вычислительный центр им. А. А. Дородницына Российской академии наук.

Ученый секретарь Диссертационного совета Д 002.017.02, д.ф.-м.н„ профессор

Автореферат разослан >>ЦццО(1^а 2013

В. В. Рязанов

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

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

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

1 Djukova Е. 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.

3

принадлежит объект 5, осуществляется на основе коллективного голосования по листьям дерева (голосования по большинству). Предложенная модель РД была успешно продемонстрирована её авторами на примере усовершенствования алгоритма построения допустимых разбиений (АДР).

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

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

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

Представляют интерес задачи изучения комбинаторной сложности РД

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

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

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

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

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

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

Для задачи с т объектами и п признаками (при фиксированной глубине

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

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

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

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на научных семинарах кафедры «Теоретической информатики и дискретной математики» в МПГУ; на научных семинарах ВЦ РАН; на мероприятии «Круглый стол молодых ученых по приоритетным направлениям развития науки», проводимом в МПГУ, 2007 г. и 2008 г.; на 14-ой Всероссийской конференции «Математические методы распознавания образов», гор. Суздаль, 2009 г.; на 8-ой Международной конференции «Интеллектуализация обработки информации», гор. Пафос (Кипр), 2010 г.; на 15-ой Всероссийской конференции «Математические методы распознавания образов», гор. Петрозаводск, 2011 г.

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

№5294.2008.1 и НШ №7950.2010.1.

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

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

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

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

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

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

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

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

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

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

Обозначим через Т и Х(Т) соответственно подмножество обучающих объектов и подмножество признаков, рассматриваемые на текущем шаге построения РД. На первом шаге Т = {5[,...,8т}, Х{Т) = {х\,...,хп}.

На текущем шаге синтеза РД строится либо внутренняя вершина, либо лист

дерева. Для построения внутренней вершины выбирается некоторый признак х из Х(Т), который наилучшим образом разделяет объекты из разных классов. Пусть V - множество различных значений признака х, встречающихся в описаниях объектов из Т . В этом случае из вершины, соответствующей признаку * , строится | У\ дуг, помеченных разными числами из V. Далее по каждой дуге осуществляется спуск и строится либо лист дерева, либо следующая внутренняя вершина. При спуске по дуге с меткой а, а е V, из Т удаляются те объекты, для которых значение признака х не равно а, из Х(Т) удаляется признак х. Данный процесс синтеза РД повторяется до тех пор, пока не выполнится условие останова.

Пусть ветвь РД порождена внутренними вершинами х^ , <тг - метка дуги, выходящей из вершины х^^ / = 1,...,г. Тогда рассматриваемой ветви можно поставить в соответствие пару (В,К), где К е {А']К;}, а В - элементарная

конъюнкция (э.к.) вида Xе7' ...х*', в которой ха = 1, если х = о, и ха = 0 иначе. Л Зг

Пусть Ыв - интервал истинности э.к. В . По построению

Определение 1.11. Ветвь РД называется корректной, если наборы из (51],} р| А<д являются описаниями объектов только одного класса. В этом случае интервал Nв называется допустимым.

Определение 1.12. РД называется корректным, если каждая ветвь РД является корректной.

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

если найдется г, г е{1, такое, что 5 е N, то 5 относится к классу К^ . В

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

В разделе 1.2 описан алгоритм АДР, строящий корректное БРД. Алгоритм АДР разбивает множество описаний обучающих объектов на непересекающиеся

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

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

В разделе 1.3 рассмотрен случай целочисленной информации.

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

Пусть V = {k\,...,kj} - множество текущих значений признака , е Х(Т).

Текущее множество обучающих объектов Т разбивается на подмножества где и е {/q,...,/cy}, состоит из объектов, для которых значение признака х равно и. Обозначим через f(KhT), i е{1,...,/}, - число объектов из множества Т, относящихся к классу Kj. Вероятность Pt(T), г'е{1,...,/}, того, что случайно выбранный объект из множества Т будет принадлежать классу Kj, равна f(KjJ)/\T\.

Количество информации (энтропия), необходимое для определения класса, которому принадлежит объект из множества Т , вычисляется по формуле

info(T) = -£^cOlog/Hn-

Количество информации, необходимое для определения класса, которому принадлежит объект из множества Т при разбиении Т по значениям признака х, оценивается величиной Info(x) =

Информационный выигрыш (information gain), получаемый при выборе признака х, вычисляется по формуле Gain(x) = Info(T) - rnfo(x).

Потенциальная информация, получаемая при разбиении множества Т по значениям признака х, оценивается величиной

9

Splitlnfo(x) = -2Вб7(| Г(м) \/\ T Qlogfl ТЫ \/\ T |).

В качестве признака для ветвления выбирается признак х из Х(Т), для которого величина GainRatio(x) = Gain(x)/SplitInfo(x) (нормированный информационный выигрыш) принимает наибольшее значение.

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

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

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

Данная процедура повторяется для каждого признака из Х(Т). После этого из Х(Т) выбирается наиболее информативный по критерию GainRatio(x) признак x0p¡ с оптимальным порогом d{xop¡) . Далее строится внутренняя вершина с меткой (xopt,d(xopt)). Следует отметить, что при ветвлении из этой вершины признак x0p¡ не удаляется и рассматривается на следующем шаге

наравне с другими признаками.

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

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

Пусть Н = {х^,...,х] } , г<п, - набор из г различных признаков, где

е{л:\,...,хп}, / = 1,...,г, и пусть БеМ, Б = {а\,...,ап) . Набор Н выделяет в описании объекта 5 фрагмент (Я, Н) - (ау ,...,ау).

Определение 1.13. Фрагмент (Я,П), БеК, называется представительным набором для класса К, если для любого обучающего объекта 5' £ К имеет место

В алгоритмах голосования по представительным наборам на этапе обучения для каждого класса К , К е {А'],..., А'/} , строится некоторое множество представительных наборов.

Пусть листу РД соответствует пара (В,К), В = х°.х..л7/. Тогда, очевидно,

А ]г

(<х1,...,о>) - фрагмент, содержащийся в описаниях обучающих объектов 5' из класса К таких, что У е Л'й . Нетрудно также видеть, что в случае корректной ветви набор (сг\,...,аг) - представительный набор для класса К.

Из сказанного следует, что алгоритм АДР строит некоторое множество представительных наборов, так как этот алгоритм строит корректное РД. В дереве, построенном алгоритмом С4.5, ветви не всегда являются корректными. Алгоритм С4.5 нацелен на построение «почти» представительных наборов для каждого класса К, т.е. таких фрагментов, которые наиболее часто встречаются в описаниях обучающих объектов класса К и достаточно редко в описаниях обучающих объектов из других классов.

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

В разделе 2.1 приведены основные понятия, используемые при построении

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

Опишем структуру ПРД.

На каждом шаге построения ПРД строится либо лист дерева, либо формируется набор из различных признаков X = {xtl,...,xt } , Icl(í) ,

образующий полную вершину. Далее из этой полной вершины строится ровно \Х\ дуг с метками tb...,tq, каждая из которых входит в обычную вершину,

соответствующую признаку xt., xt. el, i = \,...,q. При ветвлении из вершины, соответствующей признаку х , происходит удаление признака х из Х(Т) и удаление некоторых обучающих объектов из Т.

Определение 2.1. Ветвью в ПРД называется путь, начинающийся в корне дерева и заканчивающийся в вершине ПРД.

Пусть v - лист дерева, порожденная ветвью с обычными вершинами Xjl,...,Xjr, и ег,, /' е {1,...,г}, - метка дуги, выходящей из вершины х¡ .

Определение 2.2. Набор Nv = (a\,...,an) называется порождающим набором для листа v, если ccj. =cr¿ при i = ],...,г, и ccj ="*" при j ч {j{,...,jr}.

Каждой висячей вершине ПРД ставится в соответствие пара (ÍVv,{c4,...,í»'}) , где Nv - порождающий набор для вершины v, {al,...,со!,} -вектор оценок за классы, способ вычисления этих оценок будет указан ниже.

Определение 2.6. Глубиной ветви в ПРД называется число обычных вершин, которые содержит эта ветвь, исключая концевую вершину ветви.

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

Определение 2.8. Глубиной ПРД называется максимальная глубина среди всех построенных ветвей дерева.

Определение 2.9. Ярусом i -ого уровня (i -ым ярусом) в ПРД называется совокупность полных и обычных вершин, порожденных ветвями с глубиной /-1, а также совокупность листьев дерева, порожденных ветвями с глубиной i.

Как правило, используются два способа ветвления из обычной вершины,

соответствующей признаку х, х е Х(Т). Первый способ предпочтителен в случае бинсрной или целочисленной информации низкой значности, а второй в случае вещественнозначной или целочисленной информации высокой значности.

Способ 1. Пусть V, \V\>2, - множество различных значений признака х, встречающихся в описаниях объектов из Т. В этом случае из обычной вершины х выходит | V\ дуг, помеченных разньми числами. Пусть а, ег е V , - метка одной из дуг, выходящих из вершины х. При спуске из вершины х по дуге с меткой а удаляются те объекты из Т, для которых значение признака х не равно а.

Способ 2. Для ветвления из обычной вершины, соответствующей признаку х , осуществляется бинарная перекодировка текущих значений признака х с помощью «оптимального» порога d(x) (разд. 2.4). Рассматриваемая вершина помечается парой (x,d(x)). Спуск из вершины (x,d(x)) происходит по двум ветвям, при этом левая ветвь помечается 0, а правая - 1. При спуске из вершины (x,d(x)) по левой (правой) ветви удаляются те объекты из Т, для которых значение признака х больше (не больше) d(x).

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

Способ 1. Под описанием объекта S в вершине v понимается вектор S(v) = (Д,...,/?„), в котором fij. = bj. при / = 1,...,/•, иначе Pj = "*".

Способ 2. Под описанием объекта S в вершине v понимается вектор ¿'(V) = (/?!,...,/?„}, в котором Pj. =1, если bj. >d(xj.), иначе Pj. =0 при г' = 1,...,г,

и Pj ="*" при j<£{j\,...,jr}-

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

имеющая вид r(S,Kj) = ' ' ~'

Объект 5 зачисляется в класс К¡, если:

r(S,K¿)= птах r{S,Kj),i = \,...,l, r(S,K¡) & Г(Б,КЛ при ¡Ф j, y =1,...,/. j=U-J

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

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

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

Стоит отметить, что при синтезе ПРД происходит лавинообразный рост вершин и ветвей. В связи, с чем увеличивается время классификации объекта S. Для сокращения времени классификации предложено строить только голосующие за S листья дерева. Например, при ветвлении из обычной вершины, соответствующей признаку Xj., строится только ветвь с меткой <т,, где al = J3j.. В случае, когда описание объекта S содержит пропуски, то при классификации этого объекта признаки с пропущенными значениями исключаются из {х\,...,хп}. Данная методика позволяет сократить время классификации на скользящем контроле («leave-one-out», LOO) более чем в 2 раза. Если же имеется контрольная выборка и синтез ПРД для каждого объекта из контрольной выборки требует значительного времени, то целесообразнее один раз полностью построить ПРД.

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

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

Вектор оценок для висячей вершины v с порождающим набором Nv в

алгоритме Полный С4.5 определяется следующим образом. Пусть mJ, - число обучающих объектов класса K¡, i s {1,...,/}, описания которых равны Nv. Оценка

m'v -1, если иначе a'v = 0.

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

Вектор оценок ...,«'} для висячей вершины v с порождающим набором Nv в указанных алгоритмах определяется следующим образом. Пусть ти(, , /е{1,...,/}, — число обучающих объектов класса K¡, описания которых равны Nv, m' - число всех обучающих объектов класса K¡ , m* = max m'v и пусть

my = »4 • Тогда

1) в алгоритме AGI.Voice оценка со\ =1, если m'v - m*, иначе - 0 ;

2) в алгоритме AGI.La.max оценка co'v = (m'v + l)/(mv + /), если m'v = m*v , иначе ü)'v = 0;

3) в алгоритме AGI.La.sum оценка o>'v = (m'v + l)/(/wv + /);

4) в алгоритме AGI.Bias оценка а>1 = (m'v + \)/(т' + /).

В разделе 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 на прикладных задачах. Качество этих алгоритмов сравнивалось с распознающими алгоритмами из системы интеллектуального анализа данных, распознавания и прогнозирования «Распознавание 2.0» (разработано в ВЦ РАН), с распознающими алгоритмами из широко распространенной системы «WEKA», основанных на построении РД, а также с алгоритмом С5.0. Качество алгоритмов оценивалось методом LOO функционалами 0 = m+/m , © = ?,■// и Q= min^, , где q, - процент

правильно распознанных объектов класса K¡, m' - общее число правильно распознанных объектов.

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

В разделе 3.1 проведено сравнение алгоритма Полный С4.5 с алгоритмами Полный АДР (усовершенствованный с помощью ПРД алгоритм АДР) и С4.5. Тестирование проводилось на прикладных задачах из различных областей.

Вычислялась величина 0. Алгоритм Полный С4.5 показал лучшие результаты.

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

Следует отметить, что функционал 0 не рассматривался, так как при неравномерном распределении обучающих объектов по классам как правило 0>0.

Наилучшие результаты среди разработанных алгоритмов показал алгоритм AGI.Bias, который нацелен на случай неравномерного распределения объектов по классам. Качество алгоритма AGI.Bias по показателю Q превосходит все указанные в тестировании алгоритмы на большинстве задач. По показателю 0 алгоритм AGI.Bias лучше алгоритмов С5.0, МБРД, ГМ, J48, ABO, SimpleCART, LADTree, и немного уступает алгоритму НС на большинстве задач. При сравнении с другими алгоритмами по показателю 0 алгоритм AGI.Bias на одних типах задач (с целочисленной информацией, с пропусками) немного превосходит эти алгоритмы, а на других задачах (с вещественнозначной информацией, без пропусков) немного уступает.

На шести задачах проведен ROC-анализ алгоритмов НС, ГМ, ГТТ и AGI.La.sum. Методика ROC-анализа позволяет выявить соотношение ошибок первого и второго рода. Ошибка первого рода - отнесение объекта из первого

17

класса во второй класс. Ошибка второго рода - отнесение объекта из второго класса в первый класс. Лучшим алгоритмом стал алгоритм ГТГ, второй результат показал алгоритм AGI.La.sum, третий результат - алгоритм НС, четвертый результат - ГМ. По результатам 1ЮС-анализа алгоритмов AGI.La.sum и АСГ.Вшя показано преимущество алгоритма АСТ.Е^аэ.

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

Указанная методика исследована на примере алгоритма А01.В1аз. Счет на прикладных задачах показал эффективность предложенной методики, в среднем снижение переобученное™ ПРД с комбинацией «£> и J» составило 5%.

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

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

проведено исследование радемахеровской сложности ПРД.

В разделе 4.1 получены значения числовых характеристик ПРД в зависимости от глубины дерева к. Найдено максимальное число полных вершин РУ(к) , максимальное число обычных вершин ЗУ (к) , максимальное число листьев Ь(к) и максимальное число ребер Я(к). Показано, что к < тт{п,т-1}.

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

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

тк) = ^=121~ХЛп\ = Цк) = 2кл1 П(к) = ЗХУ(к).

Найденные оценки также являются оценками аналогичных характеристик для бинарного ПРД (БПРД).

Известно, что для классического БРД справедливо

П(к) = 2БУ(к)> Щ) = 2к и БУ{к) = Ь(к) -1.

Полученные результаты свидетельствуют о значительной комбинаторной сложности ПРД по сравнению с классическим РД.

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

Пусть РВ^ п к - семейство БПРД с не более /и листьями и глубиной не более к, в котором БПРД строится для задачи распознавания с п признаками и / классами. Обозначим через / „ 4) - емкость семейства ЛОу /^д.

Получена оценка ЧСЪ{РЭ^1п к) < /и(к+32/) + ((к + 2)// - 1)[~1ое(и + 2)].

Для сравнения оценка емкости семейства БРД с не более ц листьями, в котором БРД строится для задачи с п признаками и двумя классами, не превышает величины {/.I - 1)([~11 + + 3)]).

Таким образом, полученная оценка емкости семейства БПРД превосходит оценку емкости семейства БРД примерно в к + 2 раза. Также показано, что

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

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

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

Теорема 4.3.1. Имеет место следующая оценка времени построения ПРД: Т{п, m,l) = 0(Л* (m - k)(m -к +1)/) + 0(Л* (m - к)(п -к+1)).

Теорема 4.3.2. Если на каждом шаге построения ПРД в полную вершину попадает не более ["«'/2] признаков, где п' =| Х{Т) |, то

T(n,mJ) = 0{(k + iKm-k)(m-k+\)lA^/2k) + 0((k + l)(m-kXn-k+l)A^/2k).

Теорема 4.3.3. Если на каждом шаге построения ПРД в полную вершину попадает не больше трех признаков из Х(Т), то

T(n,m,l) = 0(f-\m - k)(m-к +1)/) + 0(3* О - k)(n -к +1)).

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

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

Определение 4.6. Отступом объекта S называется величина margin(5) = 65i(S)-maxyii{5Jj'(5)}, где к - номер правильного класса для S,

cji(S) - оценка классификатора за принадлежность S классу Kj, - 1.

Далее рассматривается стандартная задача распознавания с двумя классами, при этом метки классов принадлежат множеству Y = {-1,1} . Пусть D -распределение на MxY , Т = <lS],...,Sm} - множество обучающих объектов выбранных независимо и случайно из D.

Решающая функция /Г0Г(5) на основе ПРД с ¡л листьями для объекта Л7 может быть представлена в следующем виде:

FDT(S) = sgn(/(S)) = sgn

где crj е Y - метка класса г-ого листа, = 1. Если описание объекта S для

i -ого листа принадлежит NB,, то /¡¿(S) = 1, иначе = 0, / =1,...5/и.

Пусть - множество предикатов для признака Ху, э.к. - конъюнкция

предикатов, г'е{1,...,//}. Обозначим через U = [J"] •

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

PD [error] <2 Рт (margin < в) + cjm (l/<92 (v In m + In d) In (тв1 /v) + In (l/<5)), где PT (margin <в) - вероятность того, что отступ для случайно выбранного объекта из Г не превысит величины в, PD [error] - вероятность ошибки ПРД на

объекте S<eM, v = ^a^dyCDiU), d ^ max,-d,, где d, -глубина /-ого листа.

Таким образом, получено, что выпуклая комбинация (ПРД) сглаживает прогнозы базовых классификаторов (РД).

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

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

Определение 4.7. Эмпирической радемахеровской сложностью (ЭРС.) семейства Н на обучающей выборке Т называется величина

ЛГ(Я) = Ег-

SUP ИеН

где г = {r\,...,rm) - вектор

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

21

Важность данного понятия отражена в следующем неравенстве. Пусть Р{К) - вероятность ошибки функции И на произвольном объекте \'(И) — частота ошибок функции /г на обучении. Тогда для любого б > 0 и для любой функции /г € Н с вероятностью не меньшей 1 - 8 справедливо

Р{И) < у(/г) + Яг (Я) + Зл/1п (2/5)/2т.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

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

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

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

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

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

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

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

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

9. Genrikhov I. Е. 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.

117-120.

Напгчатано с готового оригинал-макета

Подписано в печать 10.09.2013 г. Формат 60x90 1/16. Усл. печл. 1,0. Тираж ЮОэкз. Заказ 277.

Издательство ООО 'МАКС Пресс" Лицешия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы,МГУ им. МБ. Ломоносова, 2-й учебны й корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

МОСКОВСКИЙ ПЕДАГОГИЧЕСКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ

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

04201 362793

ГЕНРИХОВ ИГОРЬ ЕВГЕНЬЕВИЧ

ПОСТРОЕНИЕ И ИССЛЕДОВАНИЕ ПОЛНЫХ РЕШАЮЩИХ ДЕРЕВЬЕВ ДЛЯ ЗАДАЧ КЛАССИФИКАЦИИ ПО ПРЕЦЕДЕНТАМ

05.13.17 - теоретические основы информатики

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

Научный руководитель доктор ф.-м. наук Дюкова Елена Всеволодовна

Москва-2013

СОДЕРЖАНИЕ

ВВЕДЕНИЕ.........................................................................................4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПРИЛОЖЕНИЯ..............................................................................162

ВВЕДЕНИЕ

Для решения прикладных задач классификации, распознавания и прогнозирования, возникающих в различных плохо формализованных областях, успешно применяются методы распознавания образов [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 осуществляется на основе энтропийного критерия.

В случае вещественнозначной информ