Ирина Эланс

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

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

ПЛАН

Введение

1. Основные идеи

2. Характеристики деревьев классификации

2.1 Иерархическая природа деревьев классификации

2.2 Гибкость метода деревьев классификации

3. Вычислительные методы

3.1 Выбор критерия точности прогноза

3.2 Выбор типа ветвления

3.3 Определение момента прекращения ветвлений

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

Заключение

Список литературы

ВВЕДЕНИЕ

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

Что же такое деревья классификации? Представьте, что вам нужно придумать устройство, которое отсортирует коллекцию монет по их достоинству (например, 1, 2, 3 и 5 копеек). Предположим, что какое-то из измерений монет, например - диаметр, известен и, поэтому, может быть использован для построения иерархического устройства сортировки монет. Заставим монеты катиться по узкому желобу, в котором прорезана щель размером с однокопеечную монету. Если монета провалилась в щель, то это 1 копейка; в противном случае она продолжает катиться дальше по желобу и натыкается на щель для двухкопеечной монеты; если она туда провалится, то это 2 копейки, если нет (значит это 3 или 5 копеек) - покатится дальше, и так далее. Таким образом, мы построили дерево классификации. Решающее правило, реализованное в этом дереве классификации, позволяет эффективно рассортировать горсть монет, а в общем случае применимо к широкому спектру задач классификации Андронов А.М., Копытов Е.А., Гринглаз Л.Я. Теория вероятностей и математическая методика, и методология обработки информации. СПб., 2004.

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

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

1. ОСНОВНЫЕ ИДЕИ

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

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

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

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

2. ХАРАКТЕРИСТИКИ ДЕРЕВЬЕВ КЛАССИФИКАЦИИ

2.1 Иерархическая природа деревьев классификации

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

Иерархическую структуру дерева классификации легко себе уяснить, сравнив используемую там процедуру принятия решения с тем, что происходит при проведении Дискриминантного анализа. Классический линейный дискриминантный анализ данных по сердечной недостаточности выдал бы набор коэффициентов, задающих одну, вполне определенную линейную комбинацию показателей кровяного давления, возраста и данных о синусовой тахикардии, которая наилучшим образом отделяет пациентов с высоким уровнем риска от остальных. Значение дискриминантной функции для каждого пациента будет вычисляться как комбинация результатов измерений трех предикторных переменных с весами, которые задаются соответствующими коэффициентами дискриминантной функции. При классификации данного пациента как имеющего высокий (низкий) уровень риска принимаются в расчет одновременно значения всех трех предикторных переменных. Пусть, например, предикторные переменные обозначаются через P (минимальное за последние сутки систолическое кровяное давление), A (возраст) и T (наличие синусоидальной тахикардии: 0 = нет; 1 = есть), p, a и t - соответствующие им весовые коэффициенты в дискриминантной функции, а c - "пороговое значение" дискриминантной функции, разделяющее пациентов на два класса. Решающее правило будет тогда иметь вид "если для данного пациента pP + aA + tT - c меньше или равно нулю, то у него низкий уровень риска, иначе - высокий уровень риска "

В случае же с решающим деревом, построенным в Breiman et al. (1984), процедура будет иметь следующий, иерархический, вид: пусть значения p, a и t равны соответственно -91, -62.5 и 0, тогда правило формулируется так: "Если p + P меньше или равно нулю, то у пациента низкий уровень риска, иначе если a + A меньше или равно нулю, то у пациента низкий уровень риска, иначе если t + T меньше или равно нулю, то у пациента низкий уровень риска, иначе у пациента высокий уровень риска." На первый взгляд, процедуры принятия решения Дискриминантного анализа и деревьев классификации выглядят похожими, так в обеих участвуют решающие уравнения и коэффициенты. Однако имеется принципиальное различие между одновременным принятием решения в Дискриминантном анализе и последовательным (иерархическим) в деревьях классификации.

Различие между этими двумя подходами станет яснее, если посмотреть, как в том и другом случае выполняется Регрессия. В рассматриваемом примере риск представляет собой дихотомическую зависимую переменную, и прогнозирование с помощью Дискриминантного анализа осуществляется путем одновременной множественной регрессии риска на три предикторных переменных для всех пациентов. С другой стороны, прогнозирование методом деревьев классификации состоит из трех отдельных этапов простого регрессионного анализа: сначала берется регрессия риска на переменную P для всех пациентов, затем - на переменную A для тех пациентов, которые не были классифицированы как низкорисковые на первом шаге регрессии, и, наконец - на переменную T для пациентов, не отнесенных к низкорисковым на втором шаге. Здесь отчетливо проявляются различие одновременного принятия решения в Дискриминантном анализе и последовательного (рекурсивного, иерархического) в деревьях классификации. Эта характеристика деревьев классификации имеет далеко идущие последствия.

2.2 Гибкость метода деревьев классификации

Другая отличительная черта метода деревьев классификации - это присущая ему гибкость. Мы уже сказали о способности деревьев классификации последовательно изучать эффект влияния отдельных переменных. Есть еще целый ряд причин, делающих деревья классификации более гибким средством, чем традиционные методы анализа. Способность деревьев классификации выполнять одномерное ветвление для анализа вклада отдельных переменных дает возможность работать с предикторными переменными различных типов. В примере с сердечными приступами, рассмотренном в работе Breiman et al. (1984), давление и возраст являются непрерывными, а наличие/отсутствие синусоидальной тахикардии - категориальной (двухуровневой) предикторной переменной. Простое разветвление предиктора можно было бы выполнить, даже если бы тахикардия измерялась по трехуровневой категориальной шкале (например: 0 = отсутствует; 1 = присутствует; 3 = неизвестно или показания неясны). Если новая категория содержит какую-то дополнительную информацию о риске, то к дереву решений можно добавить новые узлы, учитывающие и использующие эту информацию. Таким образом, при построении одномерных ветвлений деревья классификации позволяют использовать для ветвления как непрерывные, так и категориальные переменные.

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

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

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

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

Реализованные в модуле Деревья классификации методы дискриминантного Одномерного ветвления по категориальным и порядковым предикторам и дискриминантного Многомерного ветвления по линейным комбинациям порядковых предикторов представляют собой адаптацию соответствующих алгоритмов пакета QUEST (Quick, Unbiased, Efficient Statistical Trees). QUEST - это программа деревьев классификации, разработанная Loh и Shih (1997), в которой используются улучшенные варианты метода рекурсивного квадратичного дискриминантного анализа и которая содержит ряд новых средств для повышения надежности и эффективности деревьев классификации, которые она строит.

Алгоритмы пакета QUEST довольно сложны (ссылки на источники, где имеются описания алгоритмов, см. в разделе Замечания о вычислительных алгоритмах), однако в модуле Деревья классификации имеется опция Тип ветвления, предоставляющая пользователю другой, концептуально более простой подход. Реализованный здесь алгоритм Одномерного ветвления по методу CART является адаптацией алгоритмов пакета CART, см. Breiman и др. (1984). CART (Classification And Regression Trees) - это программа деревьев классификации, которая при построении дерева осуществляет полный перебор всех возможных вариантов одномерного ветвления.

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

Метод QUEST - быстрый и несмещенный. Его преимущество в скорости перед методом CART становится особенно заметным, когда предикторные переменные имеют десятки уровней (см. Loh & Shih, 1997, где приводится пример, когда метод QUEST потребовал 1 секунды времени процессора, а CART - 30.5 часов). Отсутствие у метода QUEST смещения в выборе переменных для ветвления также является его существенным преимуществом в случаях, когда одни предикторные переменные имеют мало уровней, а другие - много (предикторы со многими уровнями часто порождают "методы тыка", которые хорошо согласуются с данными, но дают плохую точность прогноза, см. Doyle, 1973, и Quinlan & Cameron-Jones, 1995). Наконец, метод QUEST не жертвует точностью прогноза ради скорости вычислений (Lim, Loh, & Shih, 1997). Сочетание опций QUEST и CART позволяет полностью использовать всю гибкость аппарата деревьев классификации.

3. ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ

Процесс построения дерева классификации состоит из четырех основных шагов:

- Выбор критерия точности прогноза

- Выбор типа ветвления

- Определение момента прекращения ветвлений

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

3.1 Выбор критерия точности прогноза

В конечном счете, цель анализа с помощью деревьев классификации состоит в том, чтобы получить максимально точный прогноз. К сожалению, очень сложно четко сформулировать, что такое точный прогноз. Эта проблема решается "переворачиванием с ног на голову": наиболее точным прогнозом считается такой, который связан с наименьшей ценой. Термин цена не содержит в себе ничего загадочного. В большинстве приложений Необходимость минимизировать не просто долю неправильно классифицированных наблюдений, а именно потери, возникает тогда, когда некоторые ошибки прогноза ведут к более катастрофическим последствиям, чем другие, или же когда ошибки некоторого типа встречаются чаще других. Цена ошибки классификации для игрока, поставившего все свое состояние на одну ставку, несоизмеримо больше, чем от проигрыша нескольких ставок, на которые были поставлены мелкие суммы. Может случиться и наоборот, что потери от проигрыша большого количества мелких ставок будут больше, чем от проигрыша небольшого числа крупных. Усилия, которые следует уделять для минимизации убытков от ошибок прогноза, должны быть тем больше, чем больше возможный размер этих убытков.

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

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

Веса наблюдений. На менее концептуальном уровне, использование весов для весовой переменной в качестве множителей наблюдений для агрегированных данных также имеет отношение к минимизации потерь. Любопытно, что вместо того, чтобы использовать веса наблюдений для агрегированных данных, можно ввести подходящие априорные вероятности и/или цены ошибки классификации и получить те же самые результаты, не тратя времени на обработку множества наблюдений, имеющих одинаковые значения всех переменных. Предположим, например, что в агрегированном множестве данных с двумя равновеликими классами веса наблюдений из первого класса равны 2, а наблюдений из второго класса - 3. Если положить априорные вероятности равными соответственно 0.4 и 0.6, цены ошибки классификации взять одинаковыми и проанализировать данные без весов наблюдений, то доля неправильных классификаций получится такой же, как если бы мы оценили априорные вероятности по размерам классов, цены ошибки классификации взяли бы одинаковыми и анализировали агрегированные данные с использованием весов наблюдений. Точно такая же доля ошибок классификации получилась бы и в том случае, если бы мы положили все априорные вероятности одинаковыми, цену ошибочной классификации объекта из 1-го класса как принадлежащего ко 2-му классу взяли равной 2/3 от цены неправильной классификации объекта 2-го класса как принадлежащего 1-му классу, и анализировали бы данные без весов наблюдений.

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

3.2 Выбор типа ветвления

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

Дискриминантное одномерное ветвление. Если выбрано Одномерное ветвление, прежде всего нужно решить вопрос, какую из терминальных вершин дерева, построенного к данному моменту, следует расщепить на данном шаге и какую из предикторных переменных при этом использовать. Для каждой терминальной вершины вычисляются p-уровни для проверки значимости зависимостей между принадлежностью объектов к классам и уровнями каждой из предикторных переменных. В случае категориальных предикторов p-уровни вычисляются для проверки критерия Хи-квадрат для гипотезы независимости принадлежности классам от уровня категориального предиктора в данном узле дерева. В случае порядковых предикторов p-уровни вычисляются для анализа ANOVA взаимосвязи классовой принадлежности и значений порядкового предиктора в данном узле. Если наименьший из вычисленных p-уровней оказался меньше p-уровня Бонферони для множественных 0.05-сравнений, принимаемого по умолчанию, или иного порогового значения, установленного пользователем, то для разветвления этого узла выбирается та предикторная переменная, которая и дала этот наименьший. Если среди p-уровней не оказалось ни одного, меньшего чем заданное пороговое значение, то p-уровни вычисляются по статистическим критериям, устойчивым к виду распределения, например F Левена.

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

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

Полный перебор деревьев с одномерным ветвлением по методу CART. Третий метод выбора варианта ветвления, реализованный в данном модуле - Полный перебор деревьев с одномерным ветвлением по методу CART для категоризующих и порядковых предикторных переменных. В этом методе перебираются все возможные варианты ветвления по каждой предикторной переменной, и находится тот из них, который дает наибольший рост для критерия согласия (или, что то же самое, наибольшее уменьшение отсутствия согласия). Что определяет набор возможных ветвлений в некотором узле? Для категоризующей предикторной переменной, принимающей в данном узле k значений, имеется ровно 2(k-1) - 1 вариантов разбиения множества ее значений на две части. Для порядкового предиктора, имеющего в данном узле k различных уровней, имеется k -1 точек, разделяющих разные уровни. Мы видим, что количество различных вариантов ветвления, которые необходимо просмотреть, будет очень большим, если в задаче много предикторов, у них много уровней значений и в дереве много терминальных вершин.

3.3 Определение момента прекращения ветвлений

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