機器學習中分類演算法之決策樹

本期和大家共同學習五種常見機器學習分類演算法之決策樹(Decision tree)，能力有限，可能只涉及其表面，有待感興趣的童鞋深入挖掘。

顧名思義，決策樹學習演算法以樹形結構建立模型，類似於流程圖，該模型本身包含一系列邏輯決策，帶有根據某一屬性特徵作出決定的決策節點(如下圖中的橢圓形)，從這些決策節點引出的分枝表示可作出的選擇，數據中每一條記錄都會彙集到葉節點(如下圖中的矩形)終止，並在葉節點被分配一個預測類。

從代表整個數據集的根節點開始，決策樹演算法選擇最能預測目標類的特徵，也即對分類貢獻最大的變數特徵，然後訓練案例將被劃分到這一特徵的不同取值組中，這一決定形成了第一組樹枝；該演算法繼續分而治之其他決策節點，每次選擇最佳的候選特徵，直至達到停止的標準：

節點上幾乎所有的案例都屬於同一類

沒有剩餘的特徵來分辨案例之間的區別

決策樹已經達到預先定義的大小限制

那麼，怎麼在每個決策節點選取到最佳的候選特徵呢？別怕，有構建決策樹的行業標準——C5.0演算法來幫你自動完成這個聽起來很頭大的過程，害怕看原理的童鞋可以直接拉到最後看實例演練。

C5.0演算法的原理是利用熵度量包含不同分類的一組數據的純度，最小值0表示的樣本是完全同質的，而1表示樣本最凌亂。定義公式如下：

對於給定的數據分割S，常數c代表類的水平數，pi代表落入類的水平i中的特徵值的比例。舉個例子！比如現在有1000個體檢者的血清檢查數據，其中乙肝表面抗原(HBsAg)陽性者佔比8%，陰性者佔比92%，則該數據的熵為：(-0.08*log2(0.08)-0.92*log2(0.92))=0.4021792。假如，現在根據體檢者的血小板壓積的閾值將體檢人群分為兩大類，那麼每一類中都包括HBsAg陽性和陰性，分別計算兩大類的熵值並加和，得到按照血小板壓積這個特徵分割後的數據分區S1的熵值，那麼特徵「血小板壓積」的信息增益InfoGain=Entropy(S1)-Entropy(S)。每次選取信息增益最大的特徵進行決策節點的再次分割依據即可。

顯然，只要可用於分割的特徵足夠多，一棵決策樹可以無限制地增長，分割成越來越小的分區直到每一個案例完全歸類。然而，如果決策樹增長過大，將會使許多決策過於具體，模型將會過度擬合訓練數據，而修剪一棵決策樹的過程涉及減小它的大小，以使決策樹能更好地推廣到未知的數據。兩種修剪策略：①預剪枝：一旦決策樹達到一定數量的決策或者決策節點僅含有少量的案例，就提前停止樹的增長；②後剪枝：生成一棵決策樹後，根據節點處的錯誤率使用修剪準則將決策樹減小到更合適的大小。後剪枝通常更有效，因為如果沒有事先生成決策樹，要決定一棵決策樹生長的最佳程度是相當困難的，而事後修剪肯定可以使演算法查到所有重要的數據結構。C5.0演算法可以採用事後修剪策略進行自動修剪。

實例演練

數據包含1000名體檢者的人口學和血常規、尿常規及乙肝表面抗原血清學檢查結果，共35個特徵變數，最後一列為HBsAg陰性陽性的標識。

#設置工作目錄

setwd("D:\學海拾貝之統計\數據源")

#讀取數據

data=read.csv("decision tree.csv")

#隨機排序

set.seed(20180606)

data=small[order(rnorm(1000)),]

#選取900例為訓練數據，100例為測試數據

train=small[1:900,]

test=small[901:1000,]

install.packages("C50")

library(C50)

#構建決策樹模型

model=C5.0(train[,-35],train$HBsAg)

model

summary(model)

plot(model)

prediction=predict(model,test)

install.packages("gmodels")

library(gmodels)

CrossTable(test$HBsAg,prediction,prop.chisq = F,prop.c =F,prop.r = F,

dnn=c("actual","predicted"))

這裡我們可以看到，相較於上期分享的樸素貝葉斯分類演算法，決策樹演算法可以同時處理數值型、名義特徵及缺失，且準確度達87%也是不錯的表現。後期模型性能的提升可通過boosting演算法，設置trials=10嘗試採用自助法，綜合10棵樹的表現來預測分類；或者設置代價矩陣costs，比如臨床上普遍認為假陰性的損失較假陽性慘重10倍，令costs=matrix(c(0,1,10,0),nrow=2)等。

本期分享到這裡結束，請讀者朋友們批評指正！

參考文獻：BrettLantz, 蘭茲, 李洪成,等. 機器學習與R語言[M].機械工業出版社, 2015.

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！