Зайцев Применение методов Дата Мининг для поддержки процессов управления ИТ-услугами.Учебное пособие 2009

Подобным образом изменяется и критерий (2.9). Если проверка имеет n выходных значений, то критерий (2.9) считается как в случае, когда исходное множество разделено на n+1 подмножеств.

Пусть теперь проверка X с выходными значениями O1, O2, …, On выбрана на основе модифицированного критерия (2.11).

Нам надо решить, что делать с пропущенными данными. Если пример из множества T с известным выходом Oi ассоциирован с подмножеством Ti, вероятность того, что пример из множества Ti равна 1. Пусть тогда каждый пример из подмножества Ti имеет вес, указывающий вероятность того, что пример принадлежит Ti. Если пример имеет значение по атрибуту A, тогда вес равен 1, в противном случае пример ассоциируется со всеми множествами T1, T2, …, Tn, с соответствующими весами

.

Легко убедиться, что

.

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

Классификация новых примеров. Такая же методика приме-

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

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

31

2.4. Алгоритм CART

Алгоритм предназначен для решения задач классификации и регрессии [8]. Существует также несколько модифицированных версий – алгоритмы IndCART и DB-CART. Алгоритм IndCART является частью пакета Ind и отличается от CART использованием иного способа обработки пропущенных значений, не осуществляет регрессионную часть алгоритма CART и имеет иные параметры отсечения. Алгоритм DB-CART базируется на следующей идее: вместо того чтобы использовать обучающий набор данных для определения разбиений, используем его для оценки распределения входных и выходных значений и затем используем эту оценку, чтобы определить разбиения. DB аббревиатура от distribution based. Утверждается, что эта идея дает значительное уменьшение ошибки классификации, по сравнению со стандартными методами построения дерева. Основными отличиями алгоритма CART от алгоритмов семейства ID3 являются:

•бинарное представление дерева решений;

•функция оценки качества разбиения;

•механизм отсечения дерева;

•алгоритм обработки пропущенных значений;

•построение деревьев регрессии. Проанализируем их подробнее.

Бинарное представление дерева решений. В алгоритме CART

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

1 Алгоритмическое решение:

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

32

Функция оценки качества разбиения. Обучение дерева реше-

ний относится к классу обучения с учителем, то есть обучающая и тестовая выборки содержат классифицированный набор примеров. Оценочная функция, используемая алгоритмом CART, базируется на интуитивной идее уменьшения неопределённости в узле. Рассмотрим задачу с двумя классами и узлом, имеющим по 50 примеров одного класса. Узел имеет максимальную «неопределённость». Если будет найдено разбиение, которое разбивает данные на две подгруппы 40:5 примеров в одной и 10:45 в другой, то интуитивно «неопределённость» уменьшится. Она полностью исчезнет, когда будет найдено разбиение, которое создаст подгруппы 50:0 и 0:50. В алгоритме CART идея «неопределённости» формализована в индексе Gini. Если набор данных Т содержит данные n классов, тогда индекс Gini определяется как

,

где pi – вероятность (относительная частота) класса i в T.

Если набор Т разбивается на две части Т1 и Т2 с числом примеров в каждом N1 и N2 соответственно, тогда показатель качества разбиения будет равен

.

Наилучшим считается то разбиение, для которого Ginisplit (T) минимально.

Обозначим через N – число примеров в узле – предке, L, R – число примеров соответственно в левом и правом потомке, li и ri – число экземпляров i-го класса в левом/правом потомке. Тогда качество разбиения оценивается по следующей формуле:

.

33

Чтобы уменьшить объем вычислений формулу можно преобразовать:

.

Так как умножение на константу не играет роли при минимизации:

В итоге, лучшим будет то разбиение, для которого величина максимальна. Реже в алгоритме CART используются другие

критерии разбиения (Twoing, Symmetric Gini и др.) [13].

Правила разбиения. Вектор предикторных переменных, подаваемый на вход дерева, может содержать как числовые (порядковые) так и категориальные переменные. В любом случае в каждом узле разбиение идет только по одной переменной. Если переменная числового типа, то в узле формируется правило вида xi <= c, где с – некоторый порог, который чаще всего выбирается как среднее арифметическое двух соседних упорядоченных значений переменной xi обучающей выборки. Если переменная категориального типа, то в узле формируется правило xi V(xi), где V(xi) – некоторое непустое подмножество множества значений переменной xi в обучающей выборке. Следовательно, для n значений числового атрибута алгоритм сравнивает n-1 разбиений, а для категориального типа (2n-1 – 1). На каждом шаге построения дерева алгоритм последовательно сравни-

34

вает все возможные разбиения для всех атрибутов и выбирает наилучший атрибут и наилучшее разбиение для него2.

2 Алгоритмическое решение:

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

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

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

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

Обе эти операции связаны (если действовать «в лоб») с перемещением значительных объемов табличных данных. Можно существенно снизить временные затраты на построение дерева, если использовать индексированный источник данных (таблицу). Обращение к данным в таком источнике происходит не напрямую, а посредством логических индексов строк данных. Сортировать и разделять такой источник данных можно с минимальной потерей производительности.

Третья операция, занимающая 60–80% времени выполнения программы, – вы-

числение индексов

для всех возможных разбиений. Если у нас имеется n

числовых атрибутов и m примеров в выборке, то получается таблица n*(m-1) индексов, которая занимает значительный объем памяти. Этого можно избежать, если использовать один столбец для текущего атрибута и одну строку для лучших (максимальных) индексов по всем атрибутам. Можно и вовсе использовать только несколько числовых значений, получив быстрый, однако плохо читаемый код. Значительно увеличить производительность можно, если считать, что L = N – R, li = ni – ri , а li и ri изменяются всегда и только на единицу при переходе на следующую строку для текущего атрибута. То есть подсчет числа классов, а это основная операция, будет выполняться быстро, если знать число экземпляров каждого класса всего в таблице и при переходе на новую строку таблицы изменять на единицу только число экземпляров одного класса – класса текущего примера.

Все возможные разбиения для категориальных атрибутов удобно представлять по аналогии с двоичным представлением числа. Если атрибут имеет n уникальных значений, то получаеи 2n – разбиений. Первое (где все нули) и последнее (все единицы) нас не интересуют, тогда получаем 2n – 2. Так как порядок множеств здесь тоже неважен, получаем (2n – 2)/2 или (2n-1 – 1) первых (с единицы) двоичных представлений. Если {A, B, C, D, E} – все возможные значения некоторого атрибута X, то для текущего разбиения, которое имеет представление, скажем {0, 0, 1, 0, 1} получаем правило X in {C, E} для правой ветви и [ not {0, 0, 1, 0, 1} = {1, 1, 0, 1, 0} = X in {A, B, D} ] для левой ветви.

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

35

Механизм отсечения дерева. Наличие механизма отсечения дерева (minimal cost-complexity tree pruning) – наиболее серьезное отличие алгоритма CART от других алгоритмов построения дерева. CART рассматривает отсечение как получение компромисса между двумя проблемами: получение дерева оптимального размера и получение точной оценки вероятности ошибочной классификации.

Основная проблема отсечения – большое количество всех возможных отсеченных поддеревьев для одного дерева. Более точно, если бинарное дерево имеет |T| – листов, тогда существует ~ [1.5028369|T|] отсечённых поддеревьев. И, если дерево имеет, хотя бы 1000 листов, тогда число отсечённых поддеревьев становится просто огромным.

Базовая идея метода – не рассматривать все возможные поддеревья, ограничившись только «лучшими представителями» согласно приведённой ниже оценке.

Обозначим через |T| – число листов дерева, R(T) – ошибку классификации дерева, равную отношению числа неправильно классифицированных примеров к числу примеров в обучающей выборке. Определим C(T) как полную стоимость (оценку показателя затрат и сложности) дерева Т:

C(T) = R(T) + *|T|,

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

Определим через Tmax – максимальное по размеру дерево, которое предстоит обрезать. Если мы зафиксируем значение , тогда существует наименьшее минимизируемое поддерево для этого , для которого выполняются следующие условия:

С(T()) = minT <= Tmax C(T) if C(T) = C(T()) then T() <= T

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

36

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

Хотя имеет бесконечное число значений, существует конечное число поддеревьев дерева Tmax. Можно построить последовательность уменьшающихся поддеревьев дерева Tmax - T1 > T2 > > T3 > … > { t1}, где t1 – корневой узел дерева; такую, что Tk – наименьшее минимизируемое поддерево для [k, k+1). Это важный результат, так как он означает, что мы можем получить следующее дерево в последовательности, применив отсечение к текущему дереву. Это позволяет разработать эффективный алгоритм поиска наименьшего минимизируемого поддерева при различных значениях . Первое дерево в этой последовательности – наименьшее поддерево дерева Tmax, имеющее такую же ошибку классифика-

ции, как и Tmax, т.е. T1 = T( = 0).

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

Для получения следующего дерева в последовательности с соответствующим ему значением выполним следующие действия. Обозначим через Tt – ветвь дерева Т с корневым узлом t. Определим, при каких значениях дерево T – Tt будет лучше, чем Т. Если провести отсечку в узле t, тогда его вклад в полную стоимость де-

рева T – Tt станет равным C({t}) = R(t) + , где R(t) = r(t)* p(t); r(t) – ошибка классификации узла t и p(t) – пропорция случаев, ко-

торые «прошли» через узел t. Альтернативный вариант: R(t)= m/n,

3 Алгоритм вычисления T1 из Tmax прост. Найти любую пару листов с общим предком, которые могут быть объединены, т.е. отсечены в родительский узел без увеличения ошибки классификации. R(t) = R(l) + R(r), где r и l – листы узла t. Продолжать пока таких пар больше не останется. Так мы получим дерево, имеющее такую же стоимость как Tmax при = 0, но менее ветвистое, чем Tmax.

37

где m – число примеров классифицированных некорректно, а n – общее число классифицируемых примеров для всего дерева.

Вклад Tt в полную стоимость дерева Т составит C(Tt) = R(Tt) + + | Tt |, где

.

Дерево T – Tt будет лучше, чем Т, когда C({t}) = C(Tt), потому что при этой величине они имеют одинаковую стоимость, но T – Tt наименьшее из двух. Когда C({t}) = C( Tt), получаем:

,

решая это уравнение для , получаем:

.

Далее для любого узла t в Т1, если увеличиваем , тогда для

дерево, полученное отсечением в узле t, будет лучше, чем Т1. Основная идея изменений состоит в следующем. Вычислим зна-

чение для каждого узла в дереве Т1, и затем выберем «слабые связи» (их может быть больше чем одна), т.е. те узлы, для которых величина

является наименьшей. Мы отсекаем Т1 в этих узлах, чтобы получить Т2 – следующее дерево в последовательности. Затем мы продолжим

38

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

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

Рис. 2.3. Дерево Тmax

4 Предлагаемое алгоритмическое решение:

Т1 = Т(=0)

1 = 0 k = 1

while Тk > {root node} do begin

для всех нетерминальных узлов (!листов) в t Тk

,

k + 1 = mint gk(t)

Обойти сверху-вниз все узлы и обрезать те, где

gk(t) = k + 1, чтобы получить Tk+1 k = k + 1

end.

39

Узлы необходимо обходить сверху вниз, чтобы не отсекать те из них, которые отсекутся сами собой в результате отсечения n-го предка. Очевидно, что Т1 = Тmax, так как все листы содержат примеры одного класса и отсечение любого узла (t3 или t5) приведёт к возрастанию ошибки классификации. Затем мы вычисляем g1(t) для всех узлов t в Т1.

.

Здесь R(t1) – ошибка классификации. Если превратить t1 в лист, то следует сопоставить ему какой либо класс; так как число примеров обоих классов одинаково (равно 100), то класс выбираем наугад, в любом случае он неправильно классифицирует 100 примеров. Всего дерево обучалось на 200 примерах (100+100=200 для корневого

узла). R(t1) = m/n. m=100, n=200. R(t1) = 1/2.

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

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

.

– количество листов поддерева с корнем в узле t1. Их – 5.

Получаем:

g1(t1) = (1/2 – 0)/(5 – 1) = 1/8.

g1(t2) = 3/20. g1(t3) = 1/20. g1(t5) = 1/20.

Узлы t3 и t5 оба хранят минимальное значение g1, и, обрезая дерево Т1 в двух этих узлах мы получаем новое дерево Т2, (рис. 2.4).

Далее мы продолжаем вычислять значение g для дерева Т2. g2(t1) = (100/200 – (0/200 + 10/200 + 10/200)) / (3 – 1) = 2/10. g2(t2) = (60/200 – (0/200 + 10/200)) / (2 – 1) = 1/4.

40