ID3

ID3決策樹可以有多個分支，但是不能處理特征值為連續(xù)的情況。在ID3中，每次根據(jù)“最大信息熵增益”選取當前最佳的特征來分割數(shù)據(jù)，并按照該特征的所有取值來切分，也就是說如果一個特征有4種取值，數(shù)據(jù)將被切分4份，一旦按某特征切分后，該特征在之后的算法執(zhí)行中，將不再起作用。ID3算法十分簡單，核心是根據(jù)“最大信息熵增益”原則選擇劃分當前數(shù)據(jù)集的最好特征，信息熵是信息論里面的概念，是信息的度量方式，不確定度越大或者說越混亂，熵就越大。

C4.5

ID3采用的信息增益度量存在一個缺點，它一般會優(yōu)先選擇有較多屬性值的Feature,因為屬性值多的Feature會有相對較大的信息增益，信息增益反映的給定一個條件以后不確定性減少的程度,必然是分得越細的數(shù)據(jù)集確定性更高,也就是條件熵越小,信息增益越大。為了避免這個不足，C4.5中是用信息增益比率來作為選擇分支的準則。信息增益比率通過引入一個被稱作分裂信息的項來懲罰取值較多的Feature。

CART

CART是一棵二叉樹，采用二元切分法，每次把數(shù)據(jù)切成兩份，分別進入左子樹、右子樹。而且每個非葉子節(jié)點都有兩個孩子，所以CART的葉子節(jié)點比非葉子多1。相比ID3和C4.5，CART應(yīng)用要多一些，既可以用于分類也可以用于回歸。CART分類時，使用GINI指數(shù)來選擇最好的數(shù)據(jù)分割的特征，gini描述的是純度，與信息熵的含義相似。CART中每一次迭代都會降低GINI系數(shù)。