機器學習筆記（二）決策樹

05-08

零、摘要

本文討論決策樹的構建、最佳劃分的選擇、剪枝處理以及缺失值處理。

主要參考資料：

《機器學習》周志華
《機器學習實戰》 Peter Harrington
維基百科 C4.5_algorithm
維基百科熵（資訊理論）

一、構建決策樹

本文引用周志華《機器學習》中西瓜的例子。

假設你是河海大學大四老阿姨，有整整三的在教育超市的買西瓜經驗，閱瓜無數，積累了一個數據集，包括買過的西瓜的各種特性（色澤、根蒂、敲聲、紋理等等）以及吃瓜後這個瓜是否是好瓜的判斷。

現在，你要教急缺買瓜經驗的大一萌新陳德龍如何在超市選出好瓜。

作為前輩的你，是一個經驗豐富的買瓜老手，挑瓜時有獨到的套路：

比如說，首先看瓜的色澤，如果是青綠色的，就觀察它的根蒂，如果根蒂是蜷縮著的，就輕敲西瓜聽聲音，如果是濁響，非常好，這是一個好瓜。

這就是決策樹的基本思想。

但是顯然在剛才的判斷過程中，色澤不只有青綠色一種，其他顏色的瓜中也有好瓜的存在。另外一方面，對於一個瓜，怎樣知道先判斷色澤更好還是先判斷根蒂更好呢？這就是尋找最優劃分屬性的問題。這一問題我們將在下一部分里講述，而接下來，我們來試圖用偽代碼構建一棵決策樹。

函數生成決策樹（訓練集、屬性集）：如果（訓練集中的樣本都屬於同一類別）：#比如：都是好瓜則return 這一類別的標籤；如果（訓練集中樣本在屬性集上的取值相同）：#比如：屬性集包含色澤和根蒂，訓練集中的瓜色澤和根蒂都相同則return 最多類別的標籤； #比如：這些色澤和根蒂都相同的瓜裡面好瓜占多數，則返回好瓜。上面兩個條件都不滿足，則尋找最優化分屬性a；# 比如：找到屬性——敲聲根據屬性a劃分訓練集，得到幾個訓練子集。循環，對於a中每一個值ai： #比如：a1=濁響， a2=沉悶， a3=清脆生成決策樹（ai的訓練子集、屬性集/a）

上面，訓練集相當於高維坐標中的點（x，y）。其中x是一個向量，分量xi是這個瓜在第i個屬性上的取值，y代表是不是好瓜。屬性集包括買瓜時要考慮的各個因素：色澤、根蒂、敲聲、紋理等等。

我們看到，這是一個遞歸函數，他在前兩個「如果」中各有一個停止條件，在最後一行遞歸地調用自己。

接下來，我們就要討論，代碼中部「尋找最優化分屬性」這一步是如何進行的。

二、尋找最優劃分屬性

1.信息、信息熵和信息增益

首先，如果一件事情有i種可能的結果，每種結果xi發生的概率為 $p(x_i)$ ，則要確定這件事的結果為 $x_i$ 所需的信息為 $I(x_i) = - log_2 p(x_i)$ 。

我們來理解一下這個公式。針對拋硬幣這個事件，一共有兩個結果 $x_1$ =正面和 $x_2$ =反面。他們各自的概率 $p(x_1) = p(x_2) = 0.5$ 。帶入上面的公式中，得到：

確定拋硬幣結果所需的信息 $= I(x_i) = - log_2 p(x_i) = -log_2(0.5) = 1(bit)$ ，即，我們需要1比特的信息來知道拋硬幣得到的是正面還是反面。我們知道，1比特代表1或0，所以這信息的定義也是符合我們的直觀感受的。

之所以這裡的信息單位為比特，是因為我們在上面的式子里用了以2為底取對數。如果是 $log_e p(x_i)$ 即 $ln p(x_i)$ ,那信息的單位就是nat；如果是以10為底的 $lg p(x_i)$ ，那單位就是Hart。在本文中，我們使用以2為底取對數。

接下來我們要討論信息熵的概念。在1948年，香農將熱力學的熵（entropy）引入到資訊理論，因此信息熵又被稱為香農熵。有趣的是，最開始當香農寫完資訊理論時，實際上是馮諾依曼對香農建議用「熵」這個術語，因為大家都不知道香農說的是什麼意思。

我們可以這樣理解：信息熵是度量一個集合中，樣本混亂度的一種指標。越複雜，信息熵的值越大。

信息熵的定義為 $Ent(D) = sum p(x_i)I(x_i)= - sum p(x_i)log_2 p(x_i)$ ，即對於樣本集合D，他的信息熵（混亂度）等於所有結果的概率乘上信息再求和。

直觀地理解信息熵：

我們知道 $p(x_i)$ 的值在0和1之間，那麼信息 $I(xi) = -log_2 p(x_i)$ 取非負值，故信息熵的最小值為0。這時即意味著混亂度為零——樣本集合很純粹。比如說一枚硬幣兩面都是正面，求「拋硬幣結果為正面的信息熵」，那 $p(x_i)$ 恆等於1，帶入後得到信息熵為0。這符合我們的直觀感受——結果只可能是正面，一點也不混亂。再關注信息熵的最大值。已知所有概率之和為1，求關於他們的函數的極值。這是一個多元函數條件極值問題，可以藉助拉格朗日乘數法解決。限於篇幅這裡省略詳細過程。結果是當所有符號有同等機會出現的情況下，熵達到最大值（所有可能的事件同等概率時不確定性最高）。所以說，如果一個事件一共有n種結果，那麼他的信息熵介於0和 $log_2(n)$ 之間。

最後我們引入信息增益。在有了信息和信息熵的概念之後，信息增益的概念就很好理解了。為了說明，我們用D表示已有的樣本集合，他的信息熵為Ent(D)，現在我們通過某一個屬性a對他進行劃分（色澤），其中取第i個特性的所有樣本組成的集合（所有青綠色的瓜）記作Di。此時，用屬性a對樣本集合D進行劃分所獲得的信息增益（information gain）為：

$Gain(D,a) = Ent(D) - sum (|D_i|/|D|)Ent(D_i)$

我們說，信息增益越大，則意味著使用屬性a來進行劃分所獲得的純度提升越大。

2.ID3

ID3演算法的原理很簡單，即迭代地選擇信息增益最大的屬性進行劃分。其中ID是Iterative Dichotomiser（迭代二分器）的簡稱。這一演算法是由澳大利亞計算機科學家昆蘭在1979年發表的。1986年machine learning 雜誌創刊，昆蘭應邀在創刊號重新發表了ID3演算法，掀起了決策樹研究的熱潮。

下面給出的代碼是ID3構建決策樹的簡單實現（python）。

def calcShannonEnt(dataSet): #計算信息熵 numEntries = len(dataSet) #獲得樣本總數 labelCounts = {} for featVec in dataSet: #計算不同標籤的個數，dataset的每一行是（x,y）,最後一個數據是y，即標籤 currentLabel = featVec[-1] #Label——標籤（好瓜/壞瓜） if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0 labelCounts[currentLabel] += 1 #如果是未見標籤，則計數器加一 shannonEnt = 0.0 for key in labelCounts: prob = float(labelCounts[key])/numEntries #計算p(xi) shannonEnt -= prob * log(prob,2) #計算-p(xi)*log_2(p(xi)) return shannonEntdef splitDataSet(dataSet, axis, value): #用於分割數據集， axis是用來分割的屬性（回憶dataset的每一行是（x,y）），value是屬性的取值（如色澤=青綠） retDataSet = [] for featVec in dataSet: if featVec[axis] == value: reducedFeatVec = featVec[:axis] reducedFeatVec.extend(featVec[axis+1:]) retDataSet.append(reducedFeatVec) return retDataSetdef chooseBestFeatureToSplit(dataSet): #用ID3演算法來選擇最優分劃屬性 numFeatures = len(dataSet[0]) - 1 #獲得屬性總個數（dataset最後一列是標籤，前面是屬性） baseEntropy = calcShannonEnt(dataSet) #計算Ent（D） bestInfoGain = 0.0; bestFeature = -1 #初始化 for i in range(numFeatures): #遍歷所有屬性 featList = [example[i] for example in dataSet] #取出第i列的所有屬性值 uniqueVals = set(featList) #計算這列有幾個不同的可能取值 newEntropy = 0.0 for value in uniqueVals: #分別計算他們的信息增益 subDataSet = splitDataSet(dataSet, i, value) prob = len(subDataSet)/float(len(dataSet)) newEntropy += prob * calcShannonEnt(subDataSet) infoGain = baseEntropy - newEntropy if (infoGain > bestInfoGain): #選出信息增益最大的屬性 bestInfoGain = infoGain bestFeature = i return bestFeature def createTree(dataSet,labels): #生成決策樹 classList = [example[-1] for example in dataSet] if classList.count(classList[0]) == len(classList): #如果（訓練集中的樣本都屬於同一類別），則return 這一類別的標籤； return classList[0] if len(dataSet[0]) == 1: #如果（訓練集中樣本在屬性集上的取值相同），則return 最多類別的標籤； return majorityCnt(classList) bestFeat = chooseBestFeatureToSplit(dataSet) #上面兩個條件都不滿足，則尋找最優化分屬性a bestFeatLabel = labels[bestFeat] myTree = {bestFeatLabel:{}} del(labels[bestFeat]) featValues = [example[bestFeat] for example in dataSet] uniqueVals = set(featValues) for value in uniqueVals:#循環，對於a中每一個值ai，遞歸地調用生成決策樹（ai的訓練子集、屬性集/a） subLabels = labels[:] myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels) return myTree

3.C4.5

C4.5演算法也是昆蘭提出的。在他machine learning上發表的ID3演算法掀起決策樹研究的熱潮之後，短短几年時間，眾多決策樹演算法問世。ID4，ID5等名字迅速被其他研究者提出的演算法佔用。昆蘭只好將自己的ID3後繼演算法命名為C4.0（C代表Classifier）。在此基礎上，昆蘭又提出了C4.5。（昆蘭自稱C4.5僅是對C4.0做了些小改進，因此不是C5.0，而真正的C5.0是後續的商業化版本）

C4.5演算法使用「增益率」而不是之前的信息增益來選擇最優劃分。要指出的是，C4.5的改進不只有這一處，實際上，關於C4.5演算法，昆蘭寫了整整一本書：C4.5: Programs for Machine Learning。

回想之前的數據集：

如果我們把第一列編號也當作一種屬性來看的話，回想之前對信息熵最大值的介紹，用編號這一屬性來劃分數據集，得到的信息增益是最大的。但是顯然，這一個屬性沒有泛化能力。事實上，ID3演算法對於可能取值數目較多的屬性有偏好。為了減少這種偏好，我們不妨嘗試對於可能取值數目較多的屬性進行懲罰。最簡單的懲罰方法就是將信息增益除以一個函數，這個函數關於屬性的可能取值數目單調遞增。昆蘭選擇了這樣一個單調遞增函數，他把這函數稱作屬性a的固有值（IV——intrinsic value）：

$IV(a) = -sum(|D_i|/|D|)log_2(|D_i|/|D|)$

懲罰後的信息增益稱作信息增益率（gain ratio）:

$Gain\_ratio(D,a) = Gain(D,a)/IV(a)$

但是信息增益率有矯枉過正的問題，即他對於可能取值較少的屬性有偏好。因此C4.5的解決方法是這樣的：先選出信息增益高於平均水平的屬性，再從這些屬性裡面選出信息增益率最高的那個作為最優劃分屬性。

值得一提的是，C4.5每次只做二元切分。

4.CART決策樹

Breiman等人在1984年提出的CART（Classification and Regression Tree）演算法引入了基尼指數（Gini index）作為確定劃分的依據。同樣，要指出的是，CART演算法的內容絕不僅僅為基尼指數的引入。回憶ID3在確定分劃後將該屬性的所有值都分開來，這就可能會造成過於「貪心」而切分操之過急的問題。CART演算法則與C4.5同樣每一次只做二元切分，即分為左子樹及又子樹。同時，從他的名字中就可以看出，CART決策樹還可以用於回歸任務。

基尼指數是要反映從樣本集合D中隨機地抽取兩個樣本，他們標籤不一樣的概率。概率越小就意味著純度越高。我們希望劃分後每個樣本子集的純度越高越好，那麼我們就選擇劃分後那概率最小的屬性作為最優劃分屬性。

$Gini(D) = sum_ksum_{k} p(k)p(k)$ 其中k不等於k『

$Gini\_index(D,a) = sum(|D_i|/|D|)Gini(D)$

這裡我們可以將基尼指數於之前的信息熵與信息增益的公式做對比，很容易發現他們之間的相似性。

$Ent(D) = sum p(x_i)I(x_i)= - sum p(x_i)log2 p(x_i)$

$Gain(D,a) = Ent(D) - sum (|D_i|/|D|)Ent(D_i)$

注意，這兩組公式在使用時，前者選取基尼指數最小的，後者選取信息增益最大的。

至此，我們介紹完了三種選取最優劃分屬性的方法。

三、剪枝

對於之前的決策樹構建方法，存在這樣一個問題：對噪音十分敏感，即容易發生過擬合。舉例來說，如果有一個基因突變的好瓜，他不符合一般好瓜的各種性質，即他按理來說應該是壞瓜。那對於這個瓜，決策樹也會為他單獨伸出一根樹榦。顯然，這根樹榦沒有泛化能力。這時，我們就要對我們的決策樹進行剪枝了。

1.預剪枝

預剪枝的思想就是：

在構建決策樹過程中，如果劃分後決策樹性能沒有提升（或提升不大）則不進行劃分。

回想之前構建決策樹的代碼，要實現預剪枝，只需要在選出最優劃分之後，試探性地劃分一下，拿劃分之後的決策樹在測試集（驗證集）上跑一下，算出錯誤率。如果錯誤率沒有下降或下降的幅度比較小（小於某個事先給定的超參數），則放棄此次劃分，將這些樣本標記為最多的那一種標籤。

但是預剪枝也存在著矯枉過正的問題，即解決了過擬合，卻帶來了欠擬合的風險。預剪枝基於他「貪心」的本質禁止了很多分支的展開，有可能導致泛化性能的下降。

2.後剪枝

為了敘述的方便，我們把所有決策樹末端能確定標籤的節點稱作葉節點，其餘的節點稱作分支節點。

同時，我們還要把訓練數據的一部分移出來作為驗證集。

後剪枝有兩種，一種是將兩個末端葉節點合併，一種是令末端葉節點的上一級分支節點不展開。

後剪枝的過程是這樣的：

嘗試進行上述兩種後剪枝之中的一種，如果剪枝後的決策樹在驗證集上的精度有提升，則確認剪枝，否則不剪枝。

我們發現，後剪枝的第二種和預剪枝比較相似，本質都是禁止展開。但不要混淆：兩個方法的方向相反：預剪枝是構建決策樹時從樹根開始進行的，而後剪枝時構建完成決策樹之後從樹葉開始進行的，這也使得後剪枝能保留更多有用的分支，從而迴避了欠擬合的風險。

四、缺失值處理

作為大四老阿姨的你，隨著年紀不斷增加，關於買瓜的記憶逐漸開始遺忘，很多時候記不清曾經買過的瓜所有的屬性值。造成的後果就是，首先，當我們進行「選擇最優劃分屬性」的時候，有缺失值的樣本不好處理，還有一種情況，如果確定了某個劃分屬性，而有樣本在這個屬性上的值缺失。換成人話來講，就是1）有的西瓜的性狀忘記了，買瓜時鑒別屬性的順序不好確定。2）當你知道要按敲聲往下分類時，有個瓜的敲聲你忘記了，那這個樣本怎麼處理。直接放棄這些樣本是對數據的浪費，我們不妨嘗試把這些帶有缺失值的數據也能利用起來。

下面我們介紹C4.5中的處理方法，為了便於理解，我們舉例來說。