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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПЛАН

 

Введение

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). Поэтому дерево классификации на основе одномерного ветвления можно строить независимо от того, соответствует ли единичное изменение непрерывного предиктора единичному изменению лежащей в его основе величины или нет, достаточно, чтобы предикторы были измерены в порядковой шкале. Иными словами, на способ измерения предикторной переменной накладываются гораздо более слабые ограничения.

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

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