Может кто-нибудь объяснить мне разницу между ID3 и алгоритмом CART?

Question

Я должен создать деревья решений с помощью программного обеспечения R и пакета rpart. В моей статье я должен сначала определить алгоритм ID3, а затем реализовать различные деревья решений.

Я обнаружил, что пакет rpart не работает с алгоритмом ID3. Он использует алгоритм CART. Я хотел бы понять разницу и, возможно, объяснить разницу в моей статье, но я не нашел никакой литературы, которая сравнивает обе стороны.

Вы можете мне помочь? Знаете ли вы статью, где сравниваются оба, или вы можете объяснить мне разницу?

Answer 1

У меня нет доступа к исходным текстам ^1,2, но, используя некоторые вторичные источники, ключевые различия между этими рекурсивными ("жадными") алгоритмами разбиения ("древовидными") кажутся:

1. Тип обучения:

   • ID3, как "итеративный дихотомизатор", предназначен только для двоичной классификации
   • CART, или "Деревья классификации и регрессии", - это семейство алгоритмов (включая, но не ограничиваясь, бинарное изучение дерева классификации). С rpart()Вы можете указать method='class' или же method='anova', но rpart можно вывести это из типа зависимой переменной (т. е. факторной или числовой).

2. Функции потери, используемые для выбора разделения.

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

В свое время, как практик, я почти не слышал используемый термин ID3, в то время как CART часто используется в качестве универсального термина для деревьев решений. CART имеет очень популярную реализацию в R's rpart пакет. ?rpart отмечает, что "в большинстве деталей это следует за Брейманом и др. (1984) довольно близко".

Тем не менее, вы можете пройти rpart(..., parms=list(split='information')) переопределить поведение по умолчанию и разделить на получение информации вместо этого.

¹ Quinlan, JR 1986. Индукция деревьев решений. Мах. Учить. 1, 1 (март 1986 г.), 81–106

² Брейман, Лев; Фридман, JH; Ольшен, РА; Стоун, CJ (1984). Деревья классификации и регрессии. Монтерей, Калифорния: Wadsworth & Brooks/Cole Advanced Books & Software.

Answer 2

http://www.cs.umd.edu/~samir/498/10Algorithms-08.pdf

Прочтите 1 C4.5 и далее. Это прояснит все ваши сомнения, помогло мне с моими. Не расстраивайтесь из-за названия, о различиях в разных древовидных алгоритмах. В любом случае, хорошая статья для чтения

Answer 3

Алгоритм ID3 можно использовать для категориальной функции и категориальной метки. Принимая во внимание, что CART используется для непрерывных функций и непрерывной этикетки.