決策樹(shù)（Decision Tree）是什么東西呢？它是怎么用于分類(lèi)的呢？它其實(shí)很簡(jiǎn)單，請(qǐng)看下圖。
上圖就是一顆決策樹(shù)，橢圓是判斷模塊（特征屬性），從判斷模塊引出的左右箭頭稱(chēng)作分支，它可以到達(dá)另一個(gè)判斷模塊或終止模塊（類(lèi)別值）。上圖構(gòu)造的決策樹(shù)，根據(jù)顏色、價(jià)格、大小來(lái)判斷是否喜歡所選擇的禮物。從上圖可以看出決策樹(shù)的數(shù)據(jù)形式及分類(lèi)過(guò)程很好理解，不像其他分類(lèi)算法，比如SVM、K最近鄰，無(wú)法給出數(shù)據(jù)的內(nèi)在形式。
決策樹(shù)構(gòu)造
決策樹(shù)用樣本的屬性作為節(jié)點(diǎn)，用屬性的取值作為分支的樹(shù)結(jié)構(gòu)。
決策樹(shù)方法最早產(chǎn)生于上世紀(jì)60年代，到70年代末。由J RossQuinlan提出了ID3算法，此算法的目的在于減少樹(shù)的深度。但是忽略了葉子數(shù)目的研究。C4.5算法在ID3算法的基礎(chǔ)上進(jìn)行了改進(jìn)，對(duì)于預(yù)測(cè)變量的缺值處理、剪枝技術(shù)、派生規(guī)則等方面作了較大改進(jìn)，既適合于分類(lèi)問(wèn)題，又適合于回歸問(wèn)題。
決策樹(shù)算法用構(gòu)造決策樹(shù)來(lái)發(fā)現(xiàn)數(shù)據(jù)中蘊(yùn)涵的分類(lèi)規(guī)則。如何構(gòu)造精度高、規(guī)模小的決策樹(shù)是決策樹(shù)算法的核心內(nèi)容。決策樹(shù)構(gòu)造可以分兩步進(jìn)行：第一步，決策樹(shù)的生成，由訓(xùn)練樣本集生成決策樹(shù)的過(guò)程；第二步，決策樹(shù)的剪技，決策樹(shù)的剪枝是對(duì)上一階段生成的決策樹(shù)進(jìn)行檢驗(yàn)、校正和修下的過(guò)程，主要是用測(cè)試數(shù)據(jù)集校驗(yàn)決策樹(shù)生成過(guò)程中產(chǎn)生的初步規(guī)則，將那些影響預(yù)衡準(zhǔn)確性的分枝剪除。
那么決策樹(shù)生成過(guò)程哪些節(jié)點(diǎn)作為根節(jié)點(diǎn)，哪些節(jié)點(diǎn)作為中間節(jié)點(diǎn)呢？中間節(jié)點(diǎn)是信息量最大的屬性，中間節(jié)點(diǎn)是子樹(shù)所包含樣本子集中信息量最大的屬性，葉節(jié)點(diǎn)是類(lèi)別值。
ID3算法：（1）計(jì)算每個(gè)屬性的信息增益。將信息增益最大的點(diǎn)作為根節(jié)點(diǎn)。
C4.5算法：ID3算法的改進(jìn)，用信息增益率來(lái)選擇屬性。
用信息增益來(lái)選擇屬性存在一個(gè)問(wèn)題：假設(shè)某個(gè)屬性存在大量的不同值，如ID編號(hào)（在上面例子中加一列為ID，編號(hào)為a ~ n），在劃分時(shí)將每個(gè)值成為一個(gè)結(jié)點(diǎn)。那么用這個(gè)屬性劃分后的熵會(huì)很小，因?yàn)槊總€(gè)概率變小了。就導(dǎo)致信息增益很大。就傾向于選擇該屬性作為節(jié)點(diǎn)。就會(huì)導(dǎo)致過(guò)擬合。
確定遞歸建樹(shù)的停止條件：否則會(huì)使節(jié)點(diǎn)過(guò)多，導(dǎo)致過(guò)擬合。
1. 每個(gè)子節(jié)點(diǎn)只有一種類(lèi)型的記錄時(shí)停止，這樣會(huì)使得節(jié)點(diǎn)過(guò)多，導(dǎo)致過(guò)擬合。
2. 可行方法：當(dāng)前節(jié)點(diǎn)中的記錄數(shù)低于一個(gè)閾值時(shí)，那就停止分割。
過(guò)擬合原因：
（1）噪音數(shù)據(jù)，某些節(jié)點(diǎn)用噪音數(shù)據(jù)作為了分割標(biāo)準(zhǔn)。
（2）缺少代表性的數(shù)據(jù)，訓(xùn)練數(shù)據(jù)沒(méi)有包含所有具有代表性的數(shù)據(jù)，導(dǎo)致某類(lèi)數(shù)據(jù)無(wú)法很好匹配。
（3）還就是上面的停止條件設(shè)置不好。
優(yōu)化方案：剪枝，cross-alidation，randomforest
#######下面是使用方法#######
Python版：
使用的類(lèi)：
class sklearn.tree.DecisionTreeClassifier(criterion='gini',splitter='best', max_depth=None, min_samples_split=2, min_samples_leaf=1,min_weight_fraction_leaf=0.0, max_features=None, random_state=None,max_leaf_nodes=None, class_weight=None, presort=False)
參數(shù)介紹：
criterion: ”gini” or “entropy”(default=”gini”)是計(jì)算屬性的gini(基尼不純度)還是entropy(信息增益)，來(lái)選擇最合適的節(jié)點(diǎn)。
splitter: ”best” or “random”(default=”best”)隨機(jī)選擇屬性還是選擇不純度最大的屬性，建議用默認(rèn)。
max_features: 選擇最適屬性時(shí)劃分的特征不能超過(guò)此值。
當(dāng)為整數(shù)時(shí)，即最大特征數(shù)；當(dāng)為小數(shù)時(shí)，訓(xùn)練集特征數(shù)*小數(shù)；
if “auto”, then max_features=sqrt(n_features).
If “sqrt”, thenmax_features=sqrt(n_features).
If “l(fā)og2”, thenmax_features=log2(n_features).
If None, then max_features=n_features.
max_depth: (default=None)設(shè)置樹(shù)的最大深度，默認(rèn)為None，這樣建樹(shù)時(shí)，會(huì)使每一個(gè)葉節(jié)點(diǎn)只有一個(gè)類(lèi)別，或是達(dá)到min_samples_split。
min_samples_split:根據(jù)屬性劃分節(jié)點(diǎn)時(shí)，每個(gè)劃分最少的樣本數(shù)。
min_samples_leaf:葉子節(jié)點(diǎn)最少的樣本數(shù)。
max_leaf_nodes: (default=None)葉子樹(shù)的最大樣本數(shù)。
min_weight_fraction_leaf : (default=0) Theminimum weighted fraction of the input samples required to be at a leaf node.
類(lèi)中方法：
apply(X[,check_input]) Returnsthe index of the leaf that each sample is predicted as.
fit(X,y[, sample_weight, check_input, ...]) 擬合訓(xùn)練數(shù)據(jù)，建立模型。
fit_transform(X[,y]) Fit to data, then transform it.
predict(X[,check_input]) 做預(yù)測(cè)。
predict_proba(X[,check_input]) Predictclass probabilities of the input samples X.
predict_log_proba(X) Predict class log-probabilities of the input samples X.
score(X,y[, sample_weight]) 返回測(cè)試數(shù)據(jù)的準(zhǔn)確率。
get_params([deep]) Get parameters for this estimator.
set_params(**params) Set the parameters of this estimator.
transform(*args, **kwargs) DEPRECATED: Support to use estimators asfeature selectors will be removed in version 0.19.
使用實(shí)例：
###########################
R語(yǔ)言版：
（1）使用rpart包
> library(rpart)
#這里還是使用之前的數(shù)據(jù)集
#iris3是R自帶的數(shù)據(jù)，是一個(gè)三維數(shù)組存儲(chǔ)的三個(gè)地區(qū)的數(shù)據(jù)
#訓(xùn)練數(shù)據(jù)，我們?nèi)?/span>iris3前類(lèi)數(shù)據(jù)的特征數(shù)據(jù)
> train =rbind(iris3[1:40,,1],iris3[1:40,,2],iris3[1:40,,3])
#將矩陣轉(zhuǎn)化成數(shù)據(jù)框
> train = as.data.frame(train)
#為訓(xùn)練數(shù)據(jù)添加上分類(lèi)屬性
> label = factor(c(rep(0,40),rep(1,40),rep(2,40)))
> train$label = label
#測(cè)試數(shù)據(jù)集
> test =rbind(iris3[41:50,,1],iris3[41:50,,2],iris3[41:50,,3])
> test = as.data.frame(test)
> true_class = c(rep(0,10),rep(1,10),rep(2,10))
#擬合數(shù)據(jù)構(gòu)建樹(shù)
> fit = rpart(label ~.,method='class',data = train)
#打印出樹(shù)的信息
> printcp(fit)
#查看此樹(shù)信息
> summary(fit)
#畫(huà)出此樹(shù)
> plot(fit,uniform=TRUE,main='DecisionTree')
> text(fit,use.n=T,all=T,cex=0.8)
#畫(huà)出此樹(shù)，一種更好看的方式
> post(fit, file = 'c:/tree.ps', title = 'Classification Tree foriris')
#剪枝
> pfit = prune(fit,cp =fit$cptable[which.min(fit$cptable[,'xerror']),'CP'])
#畫(huà)出修剪后的樹(shù)
> plot(pfit, uniform=TRUE, main='PrunedClassification Tree for iris')
> text(pfit, use.n=TRUE, all=TRUE, cex=.8)
#畫(huà)到ps格式，更好看些
> post(pfit, file = 'c:/ptree.ps', title= 'Pruned Classification Tree for Kyphosis')
#用測(cè)試數(shù)據(jù)集合測(cè)試
> p_class =predict(fit,test,type='class')
> table(p_class, true_class)
（2）使用party包
> library(party)
> fit2 = ctree(label ~ .,data=train)
#畫(huà)出的圖好看很多（如下圖）
> plot(fit2,main='Classification Tree foriris')
#測(cè)試數(shù)據(jù)
> p_class2 = predict(fit2,test,type='response')
> table(p_class2, true_class)
#可以看到這個(gè)包和上面一個(gè)包的準(zhǔn)確率是一樣的。
參考文章：
[1] http://baike.haosou.com/doc/6986193.html
[2] http://www.cnblogs.com/bourneli/archive/2013/03/15/2961568.html
[3] http://www.statmethods.net/advstats/cart.html
聯(lián)系客服
