CART(Деревья классификации и регрессии, классификационное дерево регрессии), CART — это алгоритм, независимый от других классических алгоритмов дерева решений, поэтому CART относительно сложен. Потому что его можно использовать не только как дерево классификации, но и как дерево регрессии. Индекс Джини (выберите признаки с наименьшим индексом Джини) используется в качестве критерия расщепления, а также включает операции постобрезки. Хотя алгоритм ID3 и алгоритм C4.5 могут добывать как можно больше информации при обучении набора обучающей выборки, сгенерированное ими дерево решений имеет более крупные ветви и более крупные масштабы. С целью упрощения масштаба дерева решений и повышения эффективности формирования дерева решений появляется алгоритм дерева решений CART, выбирающий признаки теста по коэффициенту Джини.
1. Индекс Джини
- определение: Индекс Джини (примесь Джини): Указывает вероятность того, что случайно выбранная выборка будет неправильно классифицирована в наборе выборок.
- Уведомление: Чем меньше индекс Джини, тем меньше вероятность того, что выбранные образцы в наборе будут неправильно классифицированы, то есть чем выше чистота набора, и наоборот, тем более нечистым будет набор.
- которыйИндекс Джини (примесь Джини) = вероятность того, что образец будет выбран * вероятность того, что образец будет неправильно классифицирован
- pk представляет вероятность того, что выбранная выборка принадлежит к категории k, тогда вероятность того, что эта выборка будет неправильно классифицирована, равна (1-pk)
- В выборке есть K категорий, и случайно выбранная выборка может принадлежать любой из k категорий, поэтому суммируется сумма категорий.
- При бинарной сегментации Джини (P) = 2p (1-p) легко настроить процесс построения дерева для обработки непрерывных функций.
2. Индекс Джини после разделения выборки D по признаку A
Следует отметить, что CART является бинарным деревом, т. е. при использовании определенного признака для разделения выборочного набора существует только два набора: 1. Выборочный набор D1, равный заданному собственному значению, 2. Выборочный набор D2. не равно заданному собственному значению
По сути, это бинарная обработка признаков с несколькими значениями.
Возьми каштан ?:
Если предположить наличие признака «образование», то этот признак имеет три значения признака: «бакалавриат», «магистр», «доктор»,
При использовании признака «образовательного образования» для разделения выборки D существует три значения деления, поэтому есть три возможных множества деления, а разделенные подмножества следующие:
1. Точка разделения: «Бакалавриат», подмножество после подразделения: {Бакалавриат}, {Магистр, доктор философии}
2. Точка деления: «Магистр», подмножество после деления: {магистр}, {бакалавриат, доктор философии}
3. Точка деления: «Магистр», подгруппа после деления: {доктор философии}, {бакалавриат, магистр}
Для каждого из вышеперечисленных подразделений она может быть рассчитана на основеРазделить функцию = некоторое значение функцииЧистота разделения выборки D на два подмножества:
Следовательно, для признака с несколькими значениями (более 2) необходимо вычислить чистоту Gini(D, Ai) подмножества после деления выборки D с каждым значением в качестве точки разделения (где Ai представляет собой возможное значение), а затем найти деление с наименьшим индексом Джини из всех возможных делений Джини (D, Ai). Точка деления этого деления является наилучшей точкой деления, которая использует признак A для разделения выборки D.
Найдите значение коэффициента Джини.: Коэффициент Джини макроскопически выражает степень путаницы в описании набора.
Чем больше индекс Джини, тем более хаотичной является выборка D. Это чем-то похоже на роль энтропии, но это всего лишь показатель, который может определять размер, но не может количественно определять степень хаоса в множестве так же линейно, как энтропия.
————
3. Алгоритм генерации классификации CART
Вход: обучающий набор данных D, условие остановки расчета;
Выход: дерево решений CART;
Согласно набору обучающих данных, начиная с корневого узла, рекурсивно выполните следующие операции на каждом узле, чтобы построить бинарное дерево решений:
- Пусть набор обучающих данных узла равен D, и вычислите индекс Джини существующих функций для этого набора данных. В это время для каждого признака A, для каждого возможного значения a, в соответствии с проверкой точки выборки A=a как «да» или «нет», D делится на две части D1 и D2, а затем индекс Джини вычислено. .
- Среди всех возможных признаков А и всех их возможных точек сегментации а в качестве наиболее характерной и оптимальной точки сегментации выбирается признак с наименьшим индексом Джини и соответствующая ему точка сегментации. В соответствии с оптимальными функциями и оптимальными точками разделения из существующих узлов генерируются два подузла, а набор обучающих данных распределяется между двумя подузлами в соответствии с функциями.
- Рекурсивно вызовите два подузла для двух подузлов и назначьте набор обучающих данных для двух подузлов в соответствии с функциями.
- Создайте дерево решений CART.
Давайте используем пример, чтобы понять процесс расчета:
Алгоритм CART для создания дерева регрессии используется для создания дерева регрессии на основе существующих данных.Конкретный алгоритм выглядит следующим образом:
Этот алгоритм немного сложнее предыдущих, с большим количеством формул. Чтобы понять, что делает алгоритм, мы должны сначала понять, что алгоритм делает перцептивно.
Мы рассматриваем простейшую регрессию методом наименьших квадратов, CART требует, чтобы мы рассматривали все входные данные как ряд точек данных на двумерной плоскости. Разделение основано на оси x (то есть разделительной линией итогового дерева регрессии является значение x, о чем будет судить, если x больше или меньше определенного значения).
1. Сначала самостоятельно определите набор точек разреза (обычно считается средней точкой значений x двух точек). Затем вычислите среднеквадратичную ошибку, соответствующую каждой точке разделения в этой группе точек разделения, и найдите точку разделения с наименьшей среднеквадратичной ошибкой в качестве узла;
2. Эта точка разбиения разделила все пространство на две части (мы рассматриваем только самую простую двухмерную, поэтому одна точка представляет собой линию, перпендикулярную оси абсцисс), продолжаем вычислять среднеквадратичную ошибку для этих двух частей, и находим следующий узел;
3. До тех пор, пока суммарная среднеквадратическая ошибка не будет соответствовать требованиям.
Возьми каштан ?:
научно-популярный
1. Получение информации (алгоритм ID3)
определение: разница энтропии до и после деления набора данных на функцию.
Как упоминалось в понимании энтропии, энтропия может представлять собой неопределенность выборки.Чем больше энтропия, тем больше неопределенность выборки. Следовательно, разницу заданной энтропии до и после деления можно использовать для измерения качества эффекта деления выборочного набора D с использованием текущего признака.
Энтропия выборочного множества D до деления есть некоторая , entroy (до),
Используйте определенную функцию A, чтобы разделить набор данных D, и вычислите энтропию разделенного подмножества данных. вход (после)
Прирост информации = вход (спереди) - вход (сзади)
формула:
упражняться: Вычислите и используйте все функции для разделения набора данных D, чтобы получить прирост информации из множества наборов данных разделения функций D, и выберите наибольший прирост информации из этих приростов информации, чтобы функция разделения текущего узла была функцией, используемой для разделение, которое максимизирует прирост информации.
понимание получения информации:
Для набора данных D, который нужно разделить, его вход (до) определен, но вход (после) после разделения неопределен.Чем меньше вход (после), тем более неопределенно делится подмножество, полученное с использованием этого признака. , Чем меньше (то есть, чем выше чистота), тем больше разница между входом (спереди) и входом (сзади), что указывает на то, что если текущий признак используется для разделения набора данных D, его чистота будет расти быстрее. Когда мы строим оптимальное дерево решений, мы всегда надеемся быстрее достичь множества более высокой чистоты.Для этого мы можем обратиться к алгоритму градиентного спуска в алгоритме оптимизации.Причина минимизации функции потерь по методу отрицательного градиента на каждом Шаг отрицательный. Направление градиента — это направление, в котором значение функции уменьшается быстрее всего. То же самое: в процессе построения дерева решений мы всегда надеемся, что множество будет развиваться в направлении подмножества с большей чистотой как можно скорее, поэтому мы всегда выбираем признак, который максимизирует прирост информации для разделения текущего набор данных Д.
недостаток: получение информации смещает функции с большим количеством значений.
причина: Когда имеется много значений признака, легче получить подмножество с более высокой чистотой в соответствии с этим делением признака, поэтому энтропия после деления ниже, поскольку энтропия до деления постоянна, прирост информации равен больше, поэтому информативность сравнивается с предвзятыми признаками с большим количеством значений.
2. Коэффициент усиления информации (алгоритм С4.5)
формула:
Уведомление: Среди них HA(D), для выборки D текущий признак A используется в качестве случайной величины (значением является каждое собственное значение признака A), и получается эмпирическая энтропия.
(Раньше в качестве случайной величины использовалась категория набора, а теперь в качестве случайной величины используется признак, и множество D делится в соответствии со значением признака этого признака, и вычисляется энтропия HA(D))
Сущность коэффициента усиления информации: прирост информации, умноженный на параметр штрафа. Когда число признаков велико, параметр штрафа мал, когда число признаков мало, параметр штрафа велик.
штрафной параметр: набор данных D использует признак A как обратную величину энтропии случайной величины, то есть: делит выборки с одинаковым значением признака A на одно и то же подмножество (энтропия упомянутого ранее набора данных делится в соответствии с категорией )
недостаток: Коэффициент прироста информации отдает предпочтение функциям с меньшей ценностью.
причина: Когда значение признака мало, значение HA(D) мало, поэтому его обратное значение велико, поэтому прирост информации относительно велик. Следовательно, он смещен в сторону функций с меньшим количеством значений.
Используйте коэффициент прироста информации: Основываясь на вышеуказанных недостатках, вместо прямого выбора функции с наибольшей скоростью прироста информации мы теперь находим функцию с приростом информации выше среднего уровня среди признаков-кандидатов, а затем выбираем функцию с самой высокой скоростью прироста информации. среди этих особенностей.