Причина, по которой я отделяю CART от других классических алгоритмов дерева решений, заключается в том, что CART относительно сложен. Потому что его можно использовать не только как дерево классификации, но и как дерево регрессии.
Алгоритм дерева классификации CART
Для дерева классификации CART это очень похоже на ID3 и C4.5 в «классическом алгоритме дерева решений», о котором мы говорили ранее, но, в отличие от них, мы не используем прирост информации или прирост информации в CART. Индекс Джини использовался в качестве условия для принятия решений. Здесь мы должны упомянуть новый способ измерения качества характеристик: индекс Джини.
Индекс Джини
Формула индекса Джини выражает вероятность того, что две выборки будут взяты случайным образом и эти две выборки будут разными. Выражение макроса описывает, насколько хаотичен набор. Чем больше индекс Джини, тем более хаотичной является выборка D. Это чем-то похоже на роль энтропии, но это всего лишь показатель, который может определять размер, но не может количественно определять степень хаоса в множестве так же линейно, как энтропия. Мы также можем легко обнаружить, что индекс Джини представляет собой число (0, 1). У нас также есть определение совокупного индекса Джини при характерных условиях:
Алгоритм генерации классификации CART
Алгоритм останавливается, когда количество выборок узлов становится меньше порога, или индекс Джини меньше порога (выборки в основном принадлежат к одному классу), или признаков больше нет. Алгоритм генерации дерева классификации CART относительно прост. То есть принцип распределения установлен по индексу Джини. Конечно, мы по-прежнему в основном сосредоточены на процессе расчета индекса Джини. Я привожу пример, чтобы помочь понять процесс расчета.
Алгоритм дерева регрессии CART
Алгоритм CART для создания дерева регрессии используется для создания дерева регрессии на основе существующих данных.Конкретный алгоритм выглядит следующим образом:
Этот алгоритм немного сложнее предыдущих, с большим количеством формул. Чтобы понять, что делает алгоритм, мы должны сначала понять, что алгоритм делает перцептивно. Мы рассматриваем простейшую регрессию методом наименьших квадратов, CART требует, чтобы мы рассматривали все входные данные как ряд точек данных на двумерной плоскости. Разделение основано на оси x (то есть разделительной линией итогового дерева регрессии является значение x, о чем будет судить, если x больше или меньше определенного значения).
- Сначала самостоятельно определите набор точек разделения (обычно считается средней точкой значений x двух точек). Затем вычислите среднеквадратичную ошибку, соответствующую каждой точке разделения в этом наборе точек разделения, и найдите точку разделения с наименьшей среднеквадратической ошибкой в качестве узла.
- Эта точка разбиения разделила все пространство на две части (мы рассматриваем только самую простую двухмерную, поэтому одна точка представляет собой линию, перпендикулярную оси абсцисс), продолжаем вычислять среднеквадратичную ошибку для этих двух частей, и находим следующий узел;
- пока не будет известна общая среднеквадратическая ошибка.
Приведите пример, чтобы помочь понять:
использованная литература:
Ли Ханг "Статистические методы обучения" Чжоу Чжихуа «Машинное обучение».