Decision Trees
正如我們可以通過在 SVM 中選擇非線性核來完成非線性可分?jǐn)?shù)據(jù)的分類，Decision Tree 可以在每一步采用線性分割的方式將非線性可分的數(shù)據(jù)分類分解成一系列的子任務(wù)。
在決策樹的建立過程中，一個(gè)很重要的概念是熵，其數(shù)學(xué)定義為：
- Entropy = -Σp(i)log2p(i)，其中 p(i) 代表第 i 個(gè)分類在樣本集中的比例
在熵的定義中之所以取對(duì)數(shù)是由于對(duì)于多個(gè)概率乘積，很容易造成下溢，因此可以通過取對(duì)數(shù)的方式將其進(jìn)行規(guī)整，進(jìn)一步地，公式前面的負(fù)號(hào)是為了使得最終的結(jié)果為一個(gè)正數(shù)值。
這個(gè)概念衡量的是數(shù)據(jù)的摻雜程度 Level of impurity，在物理和化學(xué)中這個(gè)概念衡量的是混亂的程度。當(dāng)一個(gè)數(shù)據(jù)集的熵為 0 時(shí)，代表其中所包含的數(shù)據(jù)的信息是確定的。
相對(duì)應(yīng)的還可以定義信息增益:
- Information Gain = Change in Entropy = entropy(parent) - weighted_average(entropy(children))
在建立決策樹時(shí)選擇 Information Gain 最大的特征作為每一層的決策基礎(chǔ)，在此基礎(chǔ)上進(jìn)行分割。在樣本特征較多時(shí)決策樹算法容易過擬合，因此在使用時(shí)需要特別注意。
決策樹的超參數(shù)包括：
樹的最大深度 Maximum depth
每一個(gè)分支包含的最小樣本數(shù) Minimum samples per leaf
每一個(gè)待拆分節(jié)點(diǎn)所包含的最少樣本的數(shù)量 Minimum samples to split
最大特征數(shù)：當(dāng)樣本中包含的特征過多時(shí)，如果每一步分裂都檢查每一個(gè)特征，那么決策樹的建立將非常耗時(shí)，此時(shí)可以限制每一次分裂過程中需要檢查的特征數(shù)量
Random Forest
鑒于決策樹對(duì)于過擬合的傾向性，在實(shí)際使用中可以選擇在每一次的決策樹建立時(shí)，隨機(jī)的選擇樣本集中的多個(gè)特征建立決策樹（這里實(shí)際采用的是 Bagging 的思想），此時(shí)由于樣本部分特征的選擇可以有多種組合形式，因此會(huì)構(gòu)建多個(gè)決策樹。此后在對(duì)新的樣本進(jìn)行分類時(shí)，可以用這多個(gè)樹對(duì)其進(jìn)行投票，選擇票數(shù)最多的分類作為最終的結(jié)果。這種基于隨機(jī)特征選擇的多個(gè)決策樹的分類方法稱為隨機(jī)森林 Random Forest。
在 scikit-learn 中使用決策樹分類器的方法如下：
from sklearn import tree
X = [[0, 0], [1, 1]]
Y = [0, 1]
classifier = tree.DecisionTreeClassifier()
classifier = classifier.fit(X, Y)
classifier.predict([[2., 2.]])
