CART означает «Дерево классификации и регрессии», которое представляет собой хорошо известный алгоритм дерева решений, применимый как к классификации, так и к регрессии. CART использует индекс Джини для выбора признаков разделения. Пусть pₖ обозначает долю k-го класса в текущем наборе данных D, где k = 1, 2,…,|Y |. Тогда значение Джини набора данных D определяется как
Интуитивно понятно, что Gini(D) представляет вероятность того, что две выборки, которые мы случайно выбрали из набора данных D, принадлежат разным классам. Чем ниже Gini(D), тем выше чистота набора данных D.
Предположим, что дискретный признак a имеет V возможных значений {a¹, a²,…, aᵛ }. Затем разделение набора данных D по признаку a дает V дочерних узлов, где v-й дочерний узел Dᵛ включает все выборки в D, принимая значение aᵛ для признака a. Затем Джини Dᵛ можно рассчитать с помощью приведенного выше уравнения. Поскольку в дочерних узлах разное количество выборок, вес |Dᵛ| / |Д| назначается для отражения важности каждого узла, то есть чем больше количество выборок, тем больше влияние узла ветвления. Затем индекс Джини разделения набора данных D с признаком a рассчитывается как
Учитывая набор объектов-кандидатов A, мы выбираем объект с наименьшим индексом Джини в качестве объекта разделения.
