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

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

Реализованные в модуле Деревья классификации методы дискриминантного Одномерного ветвления по категориальным и порядковым предикторам и дискриминантного Многомерного ветвления по линейным комбинациям порядковых предикторов  представляют собой адаптацию соответствующих алгоритмов пакета 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 Определение момента прекращения ветвлений

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