Алгоритм CART. Построение дерева классификации и регрессии.

Основными отличиями алгоритма CART от алгоритмов семейства ID3 являются:

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

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

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

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

· построение деревьев регрессии.

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

Этот алгоритм работает как с числовыми атрибутами, так и с категориями. если атрибут является числовым, то формируется правило x<c, где с в большинстве случаев выбирается как среднее арифметическое по всем примерам.

Если атрибут категориальный, то формируется правило, где V(xi) – это непустое подмножество множества значений x.

Функция оценки качества разбиения индекс Gini. Эта функция основана на уменьшении неопределенности.

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

 

 

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

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

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

 

Ансамбли деревьев решений. Алгоритм Random Forest.

Алгоритм наивный, исп-щий комитет из обуч. деревьев. Обуч. выборка состоит из N примеров и размера пространства M. Есть параметр

Все деревья комитета строятся независимо друг от друга по следующей процедуре:

· Сгенерируем случайную подвыборку с повторением размером N из обучающей выборки. (Таким образом, некоторые примеры попадут в неё несколько раз)

· Построим решающее дерево, классифицирующее примеры данной подвыборки, причём в ходе создания очередного узла дерева будем выбирать признак, на основе которого производится разбиение, не из всех M признаков, а лишь из m случайно выбранных. Выбор наилучшего из этих m признаков может осуществляться различными способами. В оригинальном коде Бреймана используется критерий Гини.

· Дерево строится до полного исчерпания подвыборки и не подвергается процедуре прунинга.

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

Все это требует O(N K(-количество деревьев)) памяти.

С множеством примеров можно связать весовые коэффициенты wi>=0 и если одно дерево классифицирует этот пример неправильно, то вес этого примера увеличивается, что отражает важность классификации этого примера на последующем дереве.

Оптимальное число деревьев подбирается таким образом, чтобы минимизировать ошибку классификатора на тестовой выборке. В случае её отсутствия, минимизируется оценка ошибки out-of-bag: доля примеров обучающей выборки, неправильно классифицируемых комитетом, если не учитывать голоса деревьев на примерах, входящих в их собственную обучающую подвыборку.

Достоинства

· Высокое качество получаемых моделей, сравнимое с SVM и бустингом, и лучшее, чем у нейронных сетей.[4]

· Способность эффективно обрабатывать данные с большим числом признаков и классов.

· Нечувствительность к масштабированию (и вообще к любым монотонным преобразованиям) значений признаков.

· Одинаково хорошо обрабатываются как непрерывные, так и дискретные признаки. Существуют методы построения деревьев по данным с пропущенными значениями признаков.

· Существует методы оценивания значимости отдельных признаков в модели.

· Внутренняя оценка способности модели к обобщению (тест out-of-bag).

· Высокая параллелизуемость и масштабируемость.

Недостатки

· Алгоритм склонен к переобучению на некоторых задачах, особенно на зашумленных задачах.[5]

· Большой размер получающихся моделей. Требуется O(NK) памяти для хранения модели, где K — число деревьев.

 

Индекс Gini.

Для множества А и свойства S имеющего s значений:

Gini=1-∑ [от 1 до s] (|Ai|/|A|)

Для набора А и атрибутов Q имеющих q значений и целевого свойства S имеющего s значений:

|Q|=q |S|=s

Gini(A,Q,S)=Gini(A,S) -∑ [от 1 до q] (|Ai|/|A|)Gini(Ai,S)