決策樹（Decision Tree）是什么東西呢？它是怎么用于分類的呢？它其實很簡單，請看下圖。

上圖就是一顆決策樹，橢圓是判斷模塊（特征屬性），從判斷模塊引出的左右箭頭稱作分支，它可以到達另一個判斷模塊或終止模塊（類別值）。上圖構(gòu)造的決策樹，根據(jù)顏色、價格、大小來判斷是否喜歡所選擇的禮物。從上圖可以看出決策樹的數(shù)據(jù)形式及分類過程很好理解，不像其他分類算法，比如SVM、K最近鄰，無法給出數(shù)據(jù)的內(nèi)在形式。

決策樹構(gòu)造

決策樹用樣本的屬性作為節(jié)點，用屬性的取值作為分支的樹結(jié)構(gòu)。

決策樹方法最早產(chǎn)生于上世紀60年代，到70年代末。由J RossQuinlan提出了ID3算法，此算法的目的在于減少樹的深度。但是忽略了葉子數(shù)目的研究。C4.5算法在ID3算法的基礎(chǔ)上進行了改進，對于預(yù)測變量的缺值處理、剪枝技術(shù)、派生規(guī)則等方面作了較大改進，既適合于分類問題，又適合于回歸問題。

決策樹算法用構(gòu)造決策樹來發(fā)現(xiàn)數(shù)據(jù)中蘊涵的分類規(guī)則。如何構(gòu)造精度高、規(guī)模小的決策樹是決策樹算法的核心內(nèi)容。決策樹構(gòu)造可以分兩步進行：第一步，決策樹的生成，由訓(xùn)練樣本集生成決策樹的過程；第二步，決策樹的剪技，決策樹的剪枝是對上一階段生成的決策樹進行檢驗、校正和修下的過程，主要是用測試數(shù)據(jù)集校驗決策樹生成過程中產(chǎn)生的初步規(guī)則，將那些影響預(yù)衡準確性的分枝剪除。

那么決策樹生成過程哪些節(jié)點作為根節(jié)點，哪些節(jié)點作為中間節(jié)點呢？中間節(jié)點是信息量最大的屬性，中間節(jié)點是子樹所包含樣本子集中信息量最大的屬性，葉節(jié)點是類別值。

ID3算法：（1）計算每個屬性的信息增益。將信息增益最大的點作為根節(jié)點。

C4.5算法：ID3算法的改進，用信息增益率來選擇屬性。

用信息增益來選擇屬性存在一個問題：假設(shè)某個屬性存在大量的不同值，如ID編號（在上面例子中加一列為ID，編號為a ~ n），在劃分時將每個值成為一個結(jié)點。那么用這個屬性劃分后的熵會很小，因為每個概率變小了。就導(dǎo)致信息增益很大。就傾向于選擇該屬性作為節(jié)點。就會導(dǎo)致過擬合。

確定遞歸建樹的停止條件：否則會使節(jié)點過多，導(dǎo)致過擬合。

1. 每個子節(jié)點只有一種類型的記錄時停止，這樣會使得節(jié)點過多，導(dǎo)致過擬合。

2. 可行方法：當前節(jié)點中的記錄數(shù)低于一個閾值時，那就停止分割。

過擬合原因：

（1）噪音數(shù)據(jù)，某些節(jié)點用噪音數(shù)據(jù)作為了分割標準。

（2）缺少代表性的數(shù)據(jù)，訓(xùn)練數(shù)據(jù)沒有包含所有具有代表性的數(shù)據(jù)，導(dǎo)致某類數(shù)據(jù)無法很好匹配。

（3）還就是上面的停止條件設(shè)置不好。

優(yōu)化方案：剪枝，cross-alidation，randomforest

#######下面是使用方法#######

Python版：

使用的類：

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”)是計算屬性的gini(基尼不純度)還是entropy(信息增益)，來選擇最合適的節(jié)點。

splitter: ”best” or “random”(default=”best”)隨機選擇屬性還是選擇不純度最大的屬性，建議用默認。

max_features: 選擇最適屬性時劃分的特征不能超過此值。

當為整數(shù)時，即最大特征數(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è)置樹的最大深度，默認為None，這樣建樹時，會使每一個葉節(jié)點只有一個類別，或是達到min_samples_split。

min_samples_split:根據(jù)屬性劃分節(jié)點時，每個劃分最少的樣本數(shù)。

min_samples_leaf:葉子節(jié)點最少的樣本數(shù)。

max_leaf_nodes: (default=None)葉子樹的最大樣本數(shù)。

min_weight_fraction_leaf : (default=0) Theminimum weighted fraction of the input samples required to be at a leaf node.

類中方法：

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ù)測。

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]) 返回測試數(shù)據(jù)的準確率。

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.

使用實例：

###########################

R語言版：

（1）使用rpart包

> library(rpart)

#這里還是使用之前的數(shù)據(jù)集

#iris3是R自帶的數(shù)據(jù)，是一個三維數(shù)組存儲的三個地區(qū)的數(shù)據(jù)

#訓(xùn)練數(shù)據(jù)，我們?nèi)?/span>iris3前類數(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ù)添加上分類屬性

> label = factor(c(rep(0,40),rep(1,40),rep(2,40)))

> train$label = label

#測試數(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)建樹

> fit = rpart(label ~.,method='class',data = train)

#打印出樹的信息

> printcp(fit)

#查看此樹信息

> summary(fit)

#畫出此樹

> plot(fit,uniform=TRUE,main='DecisionTree')

> text(fit,use.n=T,all=T,cex=0.8)

#畫出此樹，一種更好看的方式

> post(fit, file = 'c:/tree.ps', title = 'Classification Tree foriris')

#剪枝

> pfit = prune(fit,cp =fit$cptable[which.min(fit$cptable[,'xerror']),'CP'])

#畫出修剪后的樹

> plot(pfit, uniform=TRUE, main='PrunedClassification Tree for iris')

> text(pfit, use.n=TRUE, all=TRUE, cex=.8)

#畫到ps格式，更好看些

> post(pfit, file = 'c:/ptree.ps', title= 'Pruned Classification Tree for Kyphosis')

#用測試數(shù)據(jù)集合測試

> p_class =predict(fit,test,type='class')

> table(p_class, true_class)

（2）使用party包

> library(party)

> fit2 = ctree(label ~ .,data=train)

#畫出的圖好看很多（如下圖）

> plot(fit2,main='Classification Tree foriris')

#測試數(shù)據(jù)

> p_class2 = predict(fit2,test,type='response')

> table(p_class2, true_class)

#可以看到這個包和上面一個包的準確率是一樣的。

參考文章：

[1] http://baike.haosou.com/doc/6986193.html

[2] http://www.cnblogs.com/bourneli/archive/2013/03/15/2961568.html

[3] http://www./advstats/cart.html