Деревья классификации

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

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

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

3.4 Определение "подходящих" размеров дерева

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

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

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

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

V-кратная кросс-проверка. Второй тип кросс-проверки, реализованный  в модуле Деревья классификации, - так называемая V-кратная кросс-проверка. Этот вид кросс-проверки разумно  использовать в случаях, когда  в нашем распоряжении нет отдельной  тестовой выборки, а обучающее множество слишком мало для того, чтобы из него выделять тестовую выборку. Задаваемое пользователем значение V (значение по умолчанию равно 3) определяет число случайных подвыборок - по возможности одинакового объема, - которые формируются из обучающей выборки. Дерево классификации нужного размера строится V раз, причем каждый раз поочередно одна из подвыборок не используется в его построении, но затем используется как тестовая выборка для кросс-проверки. Таким образом, каждая подвыборка V - 1 раз участвует в обучающей выборке и ровно один раз служит тестовой выборкой. Цены кросс-проверки, вычисленные для всех V тестовых выборок, затем усредняются, и в результате получается V-кратная оценка для цены кросс-проверки, которая, вместе со своей стандартной ошибкой, доступна в таблице результатов Последовательность деревьев.

Функция цены, которая  требуется для кросс-проверочного отсечения по минимальной цене-сложности, вычисляется по мере построения дерева, начиная с ветвления в корневой вершине, пока дерево не достигнет максимально допустимого размера, определяемого величиной Число неклассифицированных. Цена для обучающей выборки пересчитывается при каждом новом ветвлении дерева, так что в результате получается, вообще говоря, убывающая последовательность цен (это отражает улучшение качества классификации). Цена обучающей выборки называется ценой обучения, чтобы отличать ее от цены кросс-проверки, - это необходимо делать, поскольку V-кратная кросс-проверка также производится при каждом новом ветвлении дерева. В качестве значения цены для корневой вершины следует использовать оценку цены кросс-проверки из V-кратной кросс-проверки. Размер дерева можно определить как число терминальных вершин, потому что для бинарных деревьев при каждом новом ветвлении размер дерева увеличивается на единицу. Введем теперь так называемый параметр сложности. Положим его сначала равным нулю, и для каждого дерева (начиная с исходного, состоящего из одной вершины) будем вычислять функцию, равную цене дерева плюс значение параметра сложности, умноженное на размер дерева. Станем теперь постепенно увеличивать значение параметра сложности, пока значение этой функции для максимального дерева не превысит ее значения для какого-либо из деревьев меньшего размера, построенных на предыдущих шагах. Примем это меньшее дерево за новое максимальное дерево и будем дальше увеличивать значение параметра сложности, пока значение функции для этого дерева не станет больше ее значения для какого-то еще меньшего дерева. Будем продолжать этот процесс до тех пор, пока дерево, состоящее из единственной корневой вершины, не станет максимальным. (Читатели, знакомые с численными методами, заметили, что в этом алгоритме мы использовали так называемую штрафную функцию. Она представляет собой линейную комбинацию цены, которая в общем случае убывает с ростом дерева, и размера дерева, который линейно растет. По мере того, как значение параметра сложности увеличивается, большие по размеру деревья получают все больший штраф за свою сложность, пока не будет достигнуто пороговое значение, при котором более высокая цена меньшего дерева будет перевешиваться сложностью большего дерева.

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

Выбор дерева по результатам  усечений. Выберем теперь из последовательности оптимально усеченных деревьев дерево "подходящего размера". Естественным критерием здесь является Цена кросс-проверки. Не будет никакой ошибки, если мы в качестве дерева "подходящего размера" выберем то, которое дает наименьшую цену кросс-проверки, однако часто оказывается, что есть еще несколько деревьев с ценой кросс-проверки, близкой к минимальной. Breiman и др. (1984) высказывают разумное предложение, что в качестве дерева "подходящего размера" нужно брать наименьшее (наименее сложное) из тех, чьи цены кросс-проверки несущественно отличаются от минимальной. Авторы предложили правило "1 SE": в качестве дерева "подходящего размера" нужно брать наименьшее дерево из тех, чьи цены кросс-проверки не превосходят минимальной цены кросс-проверки плюс умноженная на единицу стандартная ошибка цены кросс-проверки для дерева с минимальной Ценой кросс-проверки.

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

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

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

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

ЗАКЛЮЧЕНИЕ

Цель построения деревьев классификации заключается в  предсказании (или объяснении) значений категориальной зависимой переменной, и поэтому используемые методы тесно  связаны с более традиционными методами Дискриминантного анализа, Кластерного анализа, Непараметрической статистики и Нелинейного оценивания. Широкая сфера применимости деревьев классификации делает их весьма привлекательным инструментом анализа данных, но не следует, поэтому полагать, что его рекомендуется использовать вместо традиционных методов статистики. Напротив, если выполнены более строгие теоретические предположения, налагаемые традиционными методами, и выборочное распределение обладает некоторыми специальными свойствами, то более результативным будет использование именно традиционных методов. Однако, как метод разведочного анализа, или как последнее средство, когда отказывают все традиционные методы, деревья классификации, по мнению многих исследователей, не знают себе равных Андронов А.М., Копытов Е.А., Гринглаз Л.Я. Теория вероятностей и математическая методика, и методология обработки информации. СПб., 2004.