從這一章開始進入正式的算法學(xué)習(xí)。

首先我們學(xué)習(xí)經(jīng)典而有效的分類算法：決策樹分類算法。

1、決策樹算法

決策樹用樹形結(jié)構(gòu)對樣本的屬性進行分類，是最直觀的分類算法，而且也可以用于回歸。不過對于一些特殊的邏輯分類會有困難。典型的如異或（XOR）邏輯，決策樹并不擅長解決此類問題。
決策樹的構(gòu)建不是唯一的，遺憾的是最優(yōu)決策樹的構(gòu)建屬于NP問題。因此如何構(gòu)建一棵好的決策樹是研究的重點。
J. Ross Quinlan在1975提出將信息熵的概念引入決策樹的構(gòu)建，這就是鼎鼎大名的ID3算法。后續(xù)的C4.5, C5.0, CART等都是該方法的改進。

熵就是“無序，混亂”的程度。剛接觸這個概念可能會有些迷惑。想快速了解如何用信息熵增益劃分屬性，可以參考這位兄弟的文章：Python機器學(xué)習(xí)之決策樹算法

如果還不理解，請看下面這個例子。

假設(shè)要構(gòu)建這么一個自動選好蘋果的決策樹，簡單起見，我只讓他學(xué)習(xí)下面這4個樣本：
樣本    紅     大      好蘋果 
0         1        1         1 
1         1        0         1 
2         0        1         0 
3         0        0         0 

樣本中有2個屬性，A0表示是否紅蘋果。A1表示是否大蘋果。

那么這個樣本在分類前的信息熵就是S = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1。

信息熵為1表示當(dāng)前處于最混亂，最無序的狀態(tài)。

本例僅2個屬性。那么很自然一共就只可能有2棵決策樹，如下圖所示：

顯然左邊先使用A0（紅色）做劃分依據(jù)的決策樹要優(yōu)于右邊用A1（大?。┳鰟澐忠罁?jù)的決策樹。
當(dāng)然這是直覺的認(rèn)知。定量的考察，則需要計算每種劃分情況的信息熵增益。
先選A0作劃分，各子節(jié)點信息熵計算如下：
0，1葉子節(jié)點有2個正例，0個負(fù)例。信息熵為：e1 = -(2/2 * log(2/2) + 0/2 * log(0/2)) = 0。
2，3葉子節(jié)點有0個正例，2個負(fù)例。信息熵為：e2 = -(0/2 * log(0/2) + 2/2 * log(2/2)) = 0。

因此選擇A0劃分后的信息熵為每個子節(jié)點的信息熵所占比重的加權(quán)和：E = e1*2/4 + e2*2/4 = 0。
選擇A0做劃分的信息熵增益G（S, A0）=S - E = 1 - 0 = 1.

事實上，決策樹葉子節(jié)點表示已經(jīng)都屬于相同類別，因此信息熵一定為0。

同樣的，如果先選A1作劃分，各子節(jié)點信息熵計算如下：
0，2子節(jié)點有1個正例，1個負(fù)例。信息熵為：e1 = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1。
1，3子節(jié)點有1個正例，1個負(fù)例。信息熵為：e2 = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1。
因此選擇A1劃分后的信息熵為每個子節(jié)點的信息熵所占比重的加權(quán)和：E = e1*2/4 + e2*2/4 = 1。也就是說分了跟沒分一樣！
選擇A1做劃分的信息熵增益G（S, A1）=S - E = 1 - 1 = 0.
因此，每次劃分之前，我們只需要計算出信息熵增益最大的那種劃分即可。

2、數(shù)據(jù)集

為方便講解與理解，我們使用如下一個極其簡單的測試數(shù)據(jù)集：
1.5 50 thin 
1.5 60 fat 
1.6 40 thin 
1.6 60 fat 
1.7 60 thin 
1.7 80 fat 
1.8 60 thin 
1.8 90 fat 
1.9 70 thin 
1.9 80 fat 

這個數(shù)據(jù)一共有10個樣本，每個樣本有2個屬性，分別為身高和體重，第三列為類別標(biāo)簽，表示“胖”或“瘦”。該數(shù)據(jù)保存在1.txt中。

我們的任務(wù)就是訓(xùn)練一個決策樹分類器，輸入身高和體重，分類器能給出這個人是胖子還是瘦子。
（數(shù)據(jù)是作者主觀臆斷，具有一定邏輯性，但請無視其合理性）

決策樹對于“是非”的二值邏輯的分枝相當(dāng)自然。而在本數(shù)據(jù)集中，身高與體重是連續(xù)值怎么辦呢？

雖然麻煩一點，不過這也不是問題，只需要找到將這些連續(xù)值劃分為不同區(qū)間的中間點，就轉(zhuǎn)換成了二值邏輯問題。
本例決策樹的任務(wù)是找到身高、體重中的一些臨界值，按照大于或者小于這些臨界值的邏輯將其樣本兩兩分類，自頂向下構(gòu)建決策樹。

使用python的機器學(xué)習(xí)庫，實現(xiàn)起來相當(dāng)簡單和優(yōu)雅。

3、Python實現(xiàn)

Python代碼實現(xiàn)如下：

# -*- coding: utf-8 -*- 
import numpy as np 
import scipy as sp 
from sklearn import tree 
from sklearn.metrics import precision_recall_curve 
from sklearn.metrics import classification_report 
from sklearn.cross_validation import train_test_split 
 
 
''''' 數(shù)據(jù)讀入 ''' 
data  = [] 
labels = [] 
with open("data\\1.txt") as ifile: 
    for line in ifile: 
      tokens = line.strip().split(' ') 
      data.append([float(tk) for tk in tokens[:-1]]) 
      labels.append(tokens[-1]) 
x = np.array(data) 
labels = np.array(labels) 
y = np.zeros(labels.shape) 
 
 
''''' 標(biāo)簽轉(zhuǎn)換為0/1 ''' 
y[labels=='fat']=1 
 
''''' 拆分訓(xùn)練數(shù)據(jù)與測試數(shù)據(jù) ''' 
x_train, x_test, y_train, y_test = train_test_split(x, y, test_size = 0.2) 
 
''''' 使用信息熵作為劃分標(biāo)準(zhǔn)，對決策樹進行訓(xùn)練 ''' 
clf = tree.DecisionTreeClassifier(criterion='entropy') 
print(clf) 
clf.fit(x_train, y_train) 
 
''''' 把決策樹結(jié)構(gòu)寫入文件 ''' 
with open("tree.dot", 'w') as f: 
  f = tree.export_graphviz(clf, out_file=f) 
   
''''' 系數(shù)反映每個特征的影響力。越大表示該特征在分類中起到的作用越大 ''' 
print(clf.feature_importances_) 
 
'''''測試結(jié)果的打印''' 
answer = clf.predict(x_train) 
print(x_train) 
print(answer) 
print(y_train) 
print(np.mean( answer == y_train)) 
 
'''''準(zhǔn)確率與召回率''' 
precision, recall, thresholds = precision_recall_curve(y_train, clf.predict(x_train)) 
answer = clf.predict_proba(x)[:,1] 
print(classification_report(y, answer, target_names = ['thin', 'fat'])) 

輸出結(jié)果類似如下所示：
[ 0.2488562  0.7511438]
array([[  1.6,  60. ],
       [  1.7,  60. ],
       [  1.9,  80. ],
       [  1.5,  50. ],
       [  1.6,  40. ],
       [  1.7,  80. ],
       [  1.8,  90. ],
       [  1.5,  60. ]])
array([ 1.,  0.,  1.,  0.,  0.,  1.,  1.,  1.])
array([ 1.,  0.,  1.,  0.,  0.,  1.,  1.,  1.])
1.0
             precision    recall  f1-score   support
       thin       0.83      1.00      0.91         5
        fat        1.00      0.80      0.89         5
avg / total       1.00      1.00      1.00         8
array([ 0.,  1.,  0.,  1.,  0.,  1.,  0.,  1.,  0.,  0.])
array([ 0.,  1.,  0.,  1.,  0.,  1.,  0.,  1.,  0.,  1.])

可以看到，對訓(xùn)練過的數(shù)據(jù)做測試，準(zhǔn)確率是100%。但是最后將所有數(shù)據(jù)進行測試，會出現(xiàn)1個測試樣本分類錯誤。
說明本例的決策樹對訓(xùn)練集的規(guī)則吸收的很好，但是預(yù)測性稍微差點。
這里有3點需要說明，這在以后的機器學(xué)習(xí)中都會用到。

1、拆分訓(xùn)練數(shù)據(jù)與測試數(shù)據(jù)。

這樣做是為了方便做交叉檢驗。交叉檢驗是為了充分測試分類器的穩(wěn)定性。
代碼中的0.2表示隨機取20%的數(shù)據(jù)作為測試用。其余80%用于訓(xùn)練決策樹。
也就是說10個樣本中隨機取8個訓(xùn)練。本文數(shù)據(jù)集小，這里的目的是可以看到由于取的訓(xùn)練數(shù)據(jù)隨機，每次構(gòu)建的決策樹都不一樣。

2、特征的不同影響因子。

樣本的不同特征對分類的影響權(quán)重差異會很大。分類結(jié)束后看看每個樣本對分類的影響度也是很重要的。
在本例中，身高的權(quán)重為0.25，體重為0.75，可以看到重量的重要性遠(yuǎn)遠(yuǎn)高于身高。對于胖瘦的判定而言，這也是相當(dāng)符合邏輯的。

3、準(zhǔn)確率與召回率。

這2個值是評判分類準(zhǔn)確率的一個重要標(biāo)準(zhǔn)。比如代碼的最后將所有10個樣本輸入分類器進行測試的結(jié)果：
測試結(jié)果：array([ 0.,  1.,  0.,  1.,  0.,  1.,  0.,  1.,  0.,  0.])
真實結(jié)果：array([ 0.,  1.,  0.,  1.,  0.,  1.,  0.,  1.,  0.,  1.])
分為thin的準(zhǔn)確率為0.83。是因為分類器分出了6個thin，其中正確的有5個，因此分為thin的準(zhǔn)確率為5/6=0.83。
分為thin的召回率為1.00。是因為數(shù)據(jù)集中共有5個thin，而分類器把他們都分對了（雖然把一個fat分成了thin?。?，召回率5/5=1。
分為fat的準(zhǔn)確率為1.00。不再贅述。
分為fat的召回率為0.80。是因為數(shù)據(jù)集中共有5個fat，而分類器只分出了4個（把一個fat分成了thin?。?，召回率4/5=0.80。
很多時候，尤其是數(shù)據(jù)分類難度較大的情況，準(zhǔn)確率與召回率往往是矛盾的。你可能需要根據(jù)你的需要找到最佳的一個平衡點。
比如本例中，你的目標(biāo)是盡可能保證找出來的胖子是真胖子（準(zhǔn)確率），還是保證盡可能找到更多的胖子（召回率）。

代碼還把決策樹的結(jié)構(gòu)寫入了tree.dot中。打開該文件，很容易畫出決策樹，還可以看到?jīng)Q策樹的更多分類信息。
本文的tree.dot如下所示：

digraph Tree { 
0 [label="X[1] <= 55.0000\nentropy = 0.954434002925\nsamples = 8", shape="box"] ; 
1 [label="entropy = 0.0000\nsamples = 2\nvalue = [ 2. 0.]", shape="box"] ; 
0 -> 1 ; 
2 [label="X[1] <= 70.0000\nentropy = 0.650022421648\nsamples = 6", shape="box"] ; 
0 -> 2 ; 
3 [label="X[0] <= 1.6500\nentropy = 0.918295834054\nsamples = 3", shape="box"] ; 
2 -> 3 ; 
4 [label="entropy = 0.0000\nsamples = 2\nvalue = [ 0. 2.]", shape="box"] ; 
3 -> 4 ; 
5 [label="entropy = 0.0000\nsamples = 1\nvalue = [ 1. 0.]", shape="box"] ; 
3 -> 5 ; 
6 [label="entropy = 0.0000\nsamples = 3\nvalue = [ 0. 3.]", shape="box"] ; 
2 -> 6 ; 
} 

根據(jù)這個信息，決策樹應(yīng)該長的如下這個樣子：

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評論