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

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

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

МИХЕЕВ ВЛАПИИИР АЛЕКРАНПРПИИЧ -

АЛГОРИТМЫ ОБУЧЕНИЯ С ГОЛОСОВАНИЕМ ДРЕВОВИДНЫХ-ПРАВИЛ

Специальность 05. 13. 01 "Управление в технических системах"

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

Москва - 1995

Работа выполнена в Институте проблем передачи информации РАН Научный руководитель:

кандидат технических наук В.С. Переверзев-Орлов

Официальные оппоненты:

доктор технических наук Е. В. Бауман

на заседании диссертационного совета Д. 003. 29.01 при Институте проблем передачи информации РАН по адресу: 101447 Москва, Б. Каретный пер., 19.

С диссертацией мохао ознакомиться в библиотеке Института проблем передачи информации РАН.

кандидат технических наук М. Н. Вайнцвайг

Ведущая организация: Всероссийский институт научной и

технической информации Миннауки РФ и РАН

Защита, состоится " О" ДахХ~У- 1996 г. в часов

Автореферат разослан

Ученый секретарь Диссертационного совета Д. 003. 29. 01 доктор технических наук, профессор

Степанов С.

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

^туапъндстъ _теиу

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

Технология Партнерских систем применяется для решения 1адач в которых существенную роль играют неформализованный игат специалиста, его интуиция. Данные о прецедентах в таких |адачах обычно составлены из разнотипных описаний (ранговые, :атегориалыше), они характеризуются болыним числом [епомеренных, неточностью входных описаний, размытостью и ^однозначностью классификации. Как правило отсутствует :акая-либо апприорная информация о вероятностной структуре [ространства описания.

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

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

Древовидные правила позволяют строить модели на данных 5ольшой размерности по объектам и по признакам, допускаются разнотипные переменные, пересекающиеся классы. Возможна работа : неоднородными описаниями, то есть когда характер взаимосвязи переменных различен в разных областях пространства описаний. Иравовидные правила могут использоваться для восстановления "непрерывных" закономерностей. Главные недостатки древовидных

- г -

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

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

Цельлабояы

1) Анализ существующих подходов к порождению классификационных и регрессионных деревьев и методов синтеза голосующих коллективов решающих правил

2) Разработка алгоритмов синтеза дерева ревений

3) Разработка и исследование алгоритмов построения голосующих коллективов классификационных и регрессионных деревьев

4) Экспериментальная проверка разработанных алгоритмов, сопоставление качества моделирования с известными методами.

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

2) Рассмотрена формальная модель классификационного голосования на основе которой получены оценки надежности модели голосующего коллектива

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

- з -

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

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

5) Сформулированы качественные требования к множеству древовидных правил, составляющих коллектив регрессионных деревьев

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

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

1) Метод восстановления закономерностей с голосованная древовидных правил

2) Алгоритм синтеза дерева решений

3) Алгоритмы построения голосующих коллективов классификационных и регрессионных деревьев

Разработан класс алгоритмов обучения, ориентированных на решение задач в области оптимизации прямого предложения. Эти алгоритмы реализованы в виде программной системы ФРАГМЕНТ-ПОТЕНЦИАЛ, которая была аппробирована на широком круге задач, различавшихся природой источника данных и их размерностью.

Па теме диссертации опубликовано 7 печатных работ. Основные результаты докладывались на 3-х конференциях молодых ученых ИППИ РАН, конференции с международным участием "Математические методы распознавания образов-7", на семинарах лаборатории информационных технологий и анализа данных ИППИ РАН.

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

КРАТКОЕ СОЛЕР1ЛНИЕ РАБОТЫ.

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

ПЕРВАЯ_ГЛАВА посвяивна обзору известных литературных данных, отражаввих основные достижения теории деревьев ревений и голосующих алгоритмов обучения.

Идея "демократического* обобвения суждений отдельных субьектов известна человечеству с древнейаих времен. Использование голосования в общественной хизни стран с развитой демократией вообиэ не требует никаких дополнительных комментариев. В технике похожие аффекты используются при мажорировании электронных схем (Иур,Шенон), обнаружении сигналов методом накопления (Харкевич), обработке результатов наблюдений (Зльясберг). В распознавании образов принцип голосования или частичной прецедентное™ охотно используется многими конструкторами алгоритмов. Наибольвий вклад в развитие алгоритмов этого класса внесли Бонгард, Вайнцвайг, Журавлев, Переверзав-Орлов. Теория голосования исследовалась в работах Вайнцвайга,Поляковой,Левита, Некоторые оценки надежности распознавания для алгоритма 'КОРА* получены Вапником и Червоненкисом. В работах Зуева представлен ряд математических техник для оценки вероятности оаибхи при голосовании независимых правил.

Первые публикации, посвященные деревьям ревений относятся к началу 60-х годов. В 1963 году Морган и Сонквист разработали программу восстановления регрессии AID (Automatic interaction Detection) в Институте Социальных Исследований Мичиганского университета, там же в 1973 году Морган и Мессендхер предложили аналогичный алгоритм для решения классификационных задач. Основными вопросами развитой с тех пор теории деревьев ревений были критерий выбора наилучшего логического условия ветвления в нетерминальном узле и критерий прекращения ветвления или способ определения оптимальной сложности дерева.

Наиболее полно эти вопросы нашли отражение в работах Бреймана, Злыаена. Фрейдмана и Стоуна.

Наиболее близкий в идеологической плане к предлагаешь! алгоритма« методом обучения распознаванию является разработанный Переверзевым-Орловым класс алгоритмов ЬРАГМЕНТ-ПОТЕНЦИАЛ. В этом методе в качестве решателей при голосовании использовались кусочно-линейные Функции.

Во ВТОРОЙ.ГЛАВЕ рассмотрена базовая процедура построения древовидного рзаавдего правила, применимая как для классификационных, так и для регрессионных задач.

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

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

В работе рассмотрен алгоритм построения древовидного

- в

решающего правила со следующими основными элементами:

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

2) В качестве функции потерь Для рангового отклика на выборке '¿»Уд •• х2'Ух гДе - описание обьекта,

у^ - неотрицательный ранговый отклик, рассматривается следующее соотновение X

*« I ( . Е + I

1-1 j.e)<e( J j<a >е(

здесь е^-оценка отклика Л-го обьекта

3) Критерий выбора условия ветвления, разбивавшего фрагмент г на два фрагмента ^ и г2 для предсказания рангового отклика будет иметь вид

I

-> МАХ

1 I Уi I F I

i. т i

41 В качестве функции потерь для категориального отклика рассматривается соотновение

1 N 1 К N

Я"*--«¡Г (Т. РЦ- д., I I Рц>

1-1 11 " 1 1-1 11

здесь N - число классов

P1J ~ лоля °0ъектов i_r0 класса отнесенных к j-му классу При выборе условия ветвления необходимо стремиться к тому, чтобы максимально уменьшить величину R.

, 5) Если класс условий ветвления s невелик, то для выбора наилучшего условия ветвления s' допускается использование прямого перебора. Часто класс условий может быть задан параметрически с помощью вектора параметров (а(, .. • Задача выбора запишется в виде

s' = arg HIN а , .. ,а ) А 1

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

)

- ?

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

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

Далее последовательно:

- для вновь включенного в модель узла строятся разбиения составляющих его фрагментов

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

- узел соответствующий найденному разбиению включается в модель

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

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

7) Для выбора дерева оптимальной сложности ожидаемые потери на дереве т представляются в виде

я(т) - (т) 4- а»1т1 + ь

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

а* IГI +b = J?t (Т) - R, (Т)

Число таких уравнений в системе равну числу моделей в иерархии, Rt ¡т) - эмпирическая оценка потерь на обучающей подвыборке, Rt(Т) - эмпирическая оценка потерь на тестовой подвыборке.

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

- в -

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

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

Таблица 1. Сопоставление различных алгоритмов построения древовидных правил

Метод Обучение Экзамен

chaid 13 85 24 .89

cart 7 48 31 .92

Фрагмент 17 05 21 .16

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

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

качество моделирования в целом также повышается.

В ТШЬЕЙ.ГЛАВЕ для анализа основных свойств голосующих коллективов классификационных деревьев рассмотрена модель с независимо овивающимися правилами. Пусть у нас имеется п~2к древовидных правил для решения двухклассовой классификационной задачи. Каждое правило относит обьект к одному из двух классов и ошибается с вероятностью непревышающей р. Решение о Принадлежности объекта к классу принимается по простому "демократическому" больиинству голосов. Если предположить, что правила ошибаются независимо, то для вероятности ошибки голосующего коллектива справедлива оценка

(4„,к .V« ,

Р <

/ГШ—

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

">-7Г"

Однако в этом случае , практически мы используем не р1 , а некоторую оценку

V V й,

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

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

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

1-(1-2р)' р с--

Ч(1~2р)г

Пусть теперь в результате неоптимального выбора сложности модели вероятность оги^ки одного правила составит

р + б

Голосужщую модель можно считать устойчивой к г.еоптямалыюыу выбор] сложности, если справедливо

р( р + Ъ ) - р( р ) < б то есть если

ар

Выражение для границы зоны устойчивости запишется в виде п(1-гр)3~4

При фиксированном р , необходимое число правая определяется соотновениен

(1-2р)3

При фиксированной я необходимая надежность правил затшется как

р < -§- г 1 - 75 >

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

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

- все правила должны быть высоконадежными

- все правила должны быть "различающимися" .

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

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

- все правила строятся в различных подпространствах пространства описаний

- все прагма строятся с использований« различных, но возможно пересекающихся классов условий ветвления

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

Еае одним методом синтеза коллектива является подход, базируваийся на анализе обученности. Осповная идея подхода заключается а прямом формирования коллектива с заданными свойствами. Требования эти формулируются так - все правила имеют одинаковую достаточно высокую надежность и омбки правил равномерно разбросаны по материалу обучения.

Для реиевия этой задачи вводится функционал качества

коллектива специального вяла ■

С - I 1<х ) 1»!

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

- -> ИАГ

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

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

- ta -

место при исполъзованиии других подходов.

ЧЕТВЕРТАЯ.ГЛАВА посвящена алгоритмам восстановления регрессии с помощью голосующих коллективов древовидных правил.

Аналогом голосования для случая аппроксимации числового отклика является вычисление среднего арифметического оценок, даваемых частными регрессионными уравнениями - аналогами частных решающих правил в случае распознавания. Пусть для задачи восстановления зависимости числовой случайной величины у от случайного вектора х построено я регрессионных функций: Yr(x), г-;,..,R. С помощью голосования получаем из них регрессионную функцию

я

- i I хг(х)

" r-z г

Изучим ошибку такой регрессии. Обозначим через у(х) условную случайную величину у при фиксированном значении х, у(к) - ее математическое ожидание. Тогда

у(х) - у(х) + с(х) где е(х) - случайная величина с нулевым математическим ожиданием. Для ошибки голосования имеем:

R R

y(x)-Y(x) - i £ - | [yw-rrw+ew]

Обозначая смещение каждой из исходных регрессий, г»1,. ,,я:

получаем:

6rW " У(х) - Уг(х)

К

У(Х1-У(Х) = к Е Ь (Х) + е(х) * х-1 *

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

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

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

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

я -

если а*1г| < If,I

У, 1*. I У, falFl - lrt I) '

-Г ' 2* - TFT > + - 1 «fMrMr.l; raa4e

здесь У - суммарный отклик во фрагменте F. у, - суммарный отклик во фрагменте rt. Задавая некоторое множество значений параметра а мы получаем возможность строить коллектив правил, каждое из которых будет соответствовать определенной величине а. .

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

Голосующий коллектив будем строить последовательным добавлением очередного правила к множеству имеющихся. ПусТь к моменту синтеза очередного правила, для i-ro объекта имеется уже некоторая оценка отклика е^. Перед построением первого дерева все е^ одинаковы и равны среднему отклику по выборке

1 1 ei - —£ ь

Определим величину аргумента невязки для 1-го объекта

di " УГв1

Теперь, сохраняя oöay» схему построения дерева из главы 2, изменим критерий выбора наилучшего логического условия ветвления из класса s-{slf ..

в' - arg МАХ IE d - £ d I s I : € Г^ l i x e r2

здесь как и прежде рассматривается разбиение фрагмента F на два новых фрагмента f1 и f2. Этот критерий приводит к тому, что в Fj и Т2 концентрируются объекты с заниженной и завышенной оценками отклика. То есть происходит как бы аккумуляция в одном фрагменте объектов, имеющих похожие-остатки, отсюда и проистекает название рассматриваемого алгоритма. Для того, чтобы эффект голосования проявлялся, разумно потребовать, чтобы точность аппроксимации отклика во фрагменте была не ниже заданного порога. Тогда с одной стороны, мы получаем множество примерно равноточных правил, а с другой стороны в силу того, что мы исповедуем принцип аккумуляции остатков, для объектов с больной величиной невязки при построении очередного правила будет обеспечиваться все более точная оценка отклика.

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

Ключевым вопросом конструирования такого алгоритма является определение обученности объекта для задачи восстановления регрессии. Пусть как и прежде величина отклика i-ro объекта равна

. Обозначим величину оценки отклика в i-й точки r-м правилом через eri

. eri " V*iJ

Иод обученностыо i-ro объекта будем понимать

а .

где r(a,b)~ некоторая мера невязки, например г(а,Ь)-\а-Ь\ или г(а,Ь)-(а-Ъ)2, у - средний отклик в выборке .

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

5-Е t(li> 1-1 1

здесь суммирование ведется по всем объектам обучающей выборки, í - некоторая выпуклая ограниченная сверху функция. Построение коллектива заключается в последовательном добавлении регрессионных деревьев в голосующий коллектив. При синтезе r+1-ro правила задач« построения регрессионного дерева запишется в виде

- - 5Сг) -> МАХ

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

1

I £•(!<) г (у -> min 1-1 1

Отсюда видно, что построение очередного правила полностью эквивалентно синтезу регрессионного дерева в котором объекты перевзвешены с помощью f (i^). В базовой процедуре построения регрессионного дерева из главы 2, для того, чтобы использовать ее для добавления правила в голосующий коллектив, необходимо изменить лишь критерий выбора наилучшего логического условия ветвления в узле. Кроме этого, после включения очередного правила нам придется пересчитывать значения f (J^j .

В ПЯТОИ_ГЛАВЕ приводятся экспериментальные результаты, полученные с помощью программной системы ФРАГМЕНТ-ПОТЕНЦИАЛ, реализующей основные алгоритмы, представленные в работе.

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

классами - "Соли сердечного происхождения* и "боли невралгического происхождения" была разделена на обучающую и экзаменационную выборки обьенон соответственно 115 и 121 объект. Объекты характеризовались примерно сотней признаков. Модель состояла из двадцати правил по 4 нетерминальных узла в каждом. Результаты применения модели приведены в таблице 2. В этой таблице представлены матрицы перепутывания классов на обучении и экзамене, элемент матрицы показывает в процентах долю 1-го класса, распознанного как класс.

Таблица 2 . Диагностика природы болей в области груди

Выборка Классы 1 2

Обучение 1 100\ 0\

2 01 100%

Экзамен 2 loot 0*

2 б% 94%

Характер поведения различных алгоритмов построения коллективов регрессионных деревьев исследовался на реальных данных по задаче оптимизации прямого маркетинга. Данные для эксперимента были предоставлены фирмой cross/zint. Набор данных с бинарным откликом содержал 229850 объектов в обучающей выборка и 241975 в экзаменационной. Суммарный отклик объектов из материала обучения был 2455, в экзаменационной выборке - 2389. Объекты описывались с помощью восьми переменных. Для оценки качества модели использовался критерий равный отношению площади, ограниченной кривой динамики .отклика к произведению числа обьектов на суммарный отклик. Аналитически этот критерий записывается в виде

Е ( i у, ♦ Е

i"> v it е <е, 1 ¡, в '

Л » -*—!-----1—!-

1*1 У, i м

здесь « - оценка отклцка для ¿-го объекта . Результаты экспериментов представлены таблицей 3, в клетках таблицы наклонной

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

Таблица 3. Алгоритмы синтзза голосуюдах коллективов

Алгоритмы(Число правил 1 3 6 10

Варьирование параметров 17.05/ 21.16 16,20/ 21.13 15.64/ 20.99 15.50/ 20.97

Аккумуляция остатков 34.50/ 35.85 3».30/ 29.70 31.55/ 31.95 20.05/ 30.90

Анализ обученности 22.50/ 22.85 21.30/ 21.70 20.75/ 21.15 20.85/ 31.10

Сопоставляя различные. алгоритмы построения голосующих коллективов можно отметить-и* некоторый характерные черты. Алгоритм варьирования параметров позволяет монотонно улучвать качество модели на экзакййацйьнной выборке с увеличением члена правил. При этом качество повели на обучающей выборке сначала растет, а затем несколько йадает, обычно этот эффект начинает наблюдаться при 15-20 правилах. Разность между качеством модели на' обучении и экзамене может составлять оаутимую величину. Основным • достоинством алгоритма аккумуляция остатков является, то, что с его паяояья иохно строить модели, состояние из правил со сложностью значительно меньаей оптимально®. Это позволяет существенно сократить Бремя построения модели. К недостаткам этого алгоритма следует отнести возможность "переподгонки' при использовании недостаточно простых правил. Алгоритм анализа обученности строит вполне устойчивые модели в тон смысле, что разность качества на обучении и экзамене невелика. Вместе с те« абсолютная величина критерия качества может Выть ниже чем у других алгоритмов.

В таблице 4 представлена результаты сопоставления качества моделей, построенных с помояьв различных методов восстановления отклика. Программы и данные для эксперимента представлены фирмой cross/2 int. Для эксперимента было взято пять наборов данных э каждом из которых имелась информация о не менее чем 100000 обьектов. Каждый обьект описывался 8-13 переменными, отобранными и сегментированными по максимуму корреляции с откликом из. нескольких сотен переменных. Данные эти были получены из различных источников й описывали некоторые задачи оптимизации прямого маркетинга.

Из таблицы видно, что алгоритм ФРАГМЕНТ всегда позволяет

- 1В

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

Таблица 4. Сопоставление различных методов восстановления отклика

Катод 1 Задача 1 2 3 4 5

САЙТ «•.85/ 43.12 32.45/ 33.52 27.86/ 28.07 7.74/ 35.67 7.48/ 31,92

сиа10 42.29/ 43.21 26.42/ 34.52 26.38/ 27.67 13.85/ 24,89

РЕГРЕССИЯ 42.62/ 42.83 29.58/ 30.33 26.64/ 26.77 25.09/ 24.97 20.72/ 21.38

шрагнвнт 42.25/ 42.97 31.58/ 32.31 25.74/ 26.73 23.59/ 23.69 20.85/ 21.10

ЗАКЛЮЧЕНИЕ

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

2) Использование парадигмы голосования существенно расширяет возможности использования деревьев решений

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

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

5) Предложенные алгоритмы в ряде случаев позволяют восстанавливать регрессию эффективнее параметрических методов и •известных алгоритмов построения классификационных и регрессионных деревьев

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

7) Рассматриваете в работе алгоритмы допускают построение легко интерпретируемых моделей и позволяют естественны! образом использовать апприорные знания специалиста в 'процессе их генерации

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

По теме диссертации опубликованы следующие работы :

1. Генкин А. В., Михеев В. А., Лереверзев-Орлов В. С. Размытые деревья решений. Тезисы докладов Конференции с международным участием : Математические методы распознавания образов-?, Москва 1995.

2. Михеев В. А. Система интерактивного извлечения знаний из данных "Лога". Труды xxvi| конференции молодых ученых ИППИ РАН, Москва 1992.

3. Михеев В. А. Метод параметрической адаптация алгоритмов голосования. Труды xxvin конференции молодых ученых ИППИ РАН, Москва 1993.

4. Михеев В. А. Оценка надежности алгоритмов голосования. Труды xxix конференции молодых ученых ИППИ РАН, Москва 1994.

5. Михеев В. А. Голосующий алгоритм восстановления распределений классов. Труды xxix конференции молодых ученых ИППИ РАН, Москва 1994.

6. Михеев В. А. Алгоритм синтеза древовидного решающего правила. Тезисы докладов Конференции с международным участием : Математические методы распознавания образов-7, Москва 1995.

7. Mlkheev V.A. A grade potential forming. Pattern recognition and Image analysis,n.4, 1993.

о