數(shù)據(jù)挖掘入門與實戰(zhàn)  公眾號： datadw

1 決策樹/判定樹（decision tree)

1 決策樹（Dicision Tree）是機器學習有監(jiān)督算法中分類算法的一種，有關機器學習中分類和預測算法的評估主要體現(xiàn)在：

1. 準確率：預測的準確與否是本算法的核心問題,，其在征信系統(tǒng)，商品購買預測等都有應用,。

2. 速度：一個好的算法不僅要求具備準確性，其運行速度也是衡量重要標準之一。

3. 強壯行：具備容錯等功能和擴展性等。

4. 可規(guī)模性：能夠應對現(xiàn)實生活中的實際案例

5. 可解釋性：運行結果能夠說明其含義,。

   
   

2 判定樹是一個類似于流程圖的樹結構：其中，每個內(nèi)部結點表示在一個屬性上的測試，每個分支代表一個屬性輸出,，而每個樹葉結點代表類或類分布。樹的最頂層是根結點,。

如上案例判斷是否去打球,？根節(jié)點顯示14天中9天適合打球，其中5天不適合打球,。這里面沒有全部一致的情況,，說明還需要細分：

1 晴天：晴天中有2天適合打球，3天不適合打球,，還需細分①濕度小于等于70時候有2天都適合打球,，停止劃分；②濕度大于70有3天都不適合打球,，停止劃分,。

2 陰天：共4天都適合打球，停止劃分,。

3 雨天：3天適合打球,，2天不適合打球，繼續(xù)劃分,。①沒有風的有3天且都適合打球,，停止劃分；②有風的2天且都不適合打球,，停止劃分,。

注意：有的時候不易太細的劃分，特征過多過細的話反而會影響預測的準確率,。把大多數(shù)歸為一類,，極少數(shù)的可以歸到大多數(shù)之中。

案例：如上決策樹,，如果某天是：晴天,，濕度90 判定是否適合打球，可以由圖知是不適合打球的,。

3 官方文檔： http:///stable/modules/tree.html

2 構造決策樹的基本算法：判定顧客對商品購買能力

2.1 算法結果圖：

根據(jù)決策樹分析如下客戶數(shù)據(jù),，判定新客戶購買力。其中

客戶年齡age：青年,、中年,、老年

客戶收入income：低、中,、高

客戶身份student：是學生,，不是學生

客戶信用credit_rating：信用一般，信用好

是否購買電腦buy_computer：購買、不購買

2.2 在介紹決策樹算法之前,，我們引入熵的概念,。熵的（entropy）概念：信息和抽象，如何度量,？

1948年,，香農(nóng)提出了 ”信息熵(entropy)“的概念，一條信息的信息量大小和它的不確定性有直接的關系,，要搞清楚一件非常非常不確定的事情,，或者是我們一無所知的事情，需要了解大量信息==>信息量的度量就等于不確定性的多少,。

例子：猜世界杯冠軍,，假如一無所知，猜多少次,？每個隊奪冠的幾率不是相等的,，比特(bit)來衡量信息的多少。

采用如下方式求信息熵：

1 當每個球隊奪冠概率相等時候,，32支參加世界杯奪冠球隊的信息熵是5,，計算是2^5=32，也就是你5次可以猜對那支球隊奪冠,。

2 當球隊奪冠概率不相等,，比如巴西、德國,、荷蘭是強隊概率較大,，信息熵就小于5，也就是你用不到5次就可以猜出哪個球隊奪冠,。

注：變量的不確定性越大,，熵也就越大

2.3 決策樹歸納算法 （ID3）

1970-1980， J.Ross. Quinlan首先提出ID3算法,，第一步是選擇屬性判斷結點,，我們采用信息熵的比較。第二步是信息獲取量(Information Gain)：Gain(A) = Info(D) - Infor_A(D)通過A來作為節(jié)點分類獲取了多少信息

詳解：

信息獲取量/信息增益(Information Gain)：Gain(A) = Info(D) - Infor_A(D),，例如age的信息增益,，Gain(age) = Info(buys_computer) - Infor_age(buys_computer)。

Info(buys_computer)是這14個記錄中,，購買的概率9/14,，不購買的5/14，帶入到信息熵公式,。

Infor_age(buys_computer)是age屬性中,，青年5/14購買概率是2/5,不購買3/5;中年4/14購買概率是1,不購買概率是0,老年5/14購買概率3/5,，不購買概率是2/5.分別代入信息熵公式

Info(buys_computer)與Infor_age(buys_computer)做差，即是age的信息增益,，具體如下：

類似,，Gain(income) = 0.029, Gain(student) = 0.151, Gain(credit_rating)=0.048

所以，選擇信息增益最大的作為根節(jié)點即age作為第一個根節(jié)點

重復計算即可

2.4 決策樹算法：

決策樹算法的形式化描述如下：

• 樹以代表訓練樣本的單個結點開始（步驟1）,。

• 如果樣本都在同一個類,，則該結點成為樹葉，并用該類標號（步驟2 和3）,。

• 否則，算法使用稱為信息增益的基于熵的度量作為啟發(fā)信息,，選擇能夠最好地將樣本分類的屬性（步驟6）,。該屬性成為該結點的“測試”或“判定”屬性（步驟7）。在算法的該版本中,，

• 所有的屬性都是分類的,，即離散值。連續(xù)屬性必須離散化,。

• 對測試屬性的每個已知的值,，創(chuàng)建一個分枝，并據(jù)此劃分樣本（步驟8-10）,。

• 算法使用同樣的過程,，遞歸地形成每個劃分上的樣本判定樹。一旦一個屬性出現(xiàn)在一個結點上,，就不必該結點的任何后代上考慮它（步驟13）,。

• 遞歸劃分步驟僅當下列條件之一成立停止：

• (a) 給定結點的所有樣本屬于同一類（步驟2 和3）。

• (b) 沒有剩余屬性可以用來進一步劃分樣本（步驟4）,。在此情況下,，使用多數(shù)表決（步驟5）。

• 這涉及將給定的結點轉(zhuǎn)換成樹葉,，并用樣本中的多數(shù)所在的類標記它,。替換地，可以存放結

• 點樣本的類分布,。

• (c) 分枝

• test_attribute = a i 沒有樣本（步驟11）,。在這種情況下，以 samples 中的多數(shù)類

• 創(chuàng)建一個樹葉（步驟12）

在決策樹ID3基礎上,，又進行了算法改進,，衍生出 其他算法如：C4.5: （Quinlan） 和Classification and Regression Trees (CART): (L. Breiman, J. Friedman, R. Olshen, C. Stone)。這些算法

共同點：都是貪心算法,，自上而下(Top-down approach)

區(qū)別：屬性選擇度量方法不同： C4.5 （gain ratio,，增益比), CART(gini index，基尼指數(shù)), ID3 (Information Gain，信息增益)

2.5 如何處理連續(xù)性變量的屬性,？ 

有些數(shù)據(jù)是連續(xù)性的,，其不像如上實驗數(shù)據(jù)可以離散化表示。諸如根據(jù)天氣情況預測打球案例中,，其濕度是一個連續(xù)值,，我們的做法是將濕度70作為一個分界點，這里就是連續(xù)變量離散化的體現(xiàn),。

2.6 補充知識

樹剪枝葉 （避免overfitting)：為了避免擬合問題,，我們可以對歸于繁瑣的樹進行剪枝（就是降低樹的高度），可以分為先剪枝和后剪枝,。

決策樹的優(yōu)點：直觀,，便于理解，小規(guī)模數(shù)據(jù)集有效     

決策樹的缺點：處理連續(xù)變量不好,、類別較多時,，錯誤增加的比較快、可規(guī)模性一般

3 基于python代碼的決策樹算法實現(xiàn)：預測顧客購買商品的能力

3.1 機器學習的庫：scikit-learnPython

scikit-learnPython,，其特性簡單高效的數(shù)據(jù)挖掘和機器學習分析,，簡單高效的數(shù)據(jù)挖掘和機器學習分析，對所有用戶開放,，根據(jù)不同需求高度可重用性,，基于Numpy, SciPy和matplotlib，開源,，商用級別：獲得 BSD許可,。scikit-learn覆蓋分類（classification), 回歸（regression), 聚類（clustering), 降維(dimensionality reduction)，模型選擇(model selection), 預處理(preprocessing)等領域,。

3.2 scikit-learn的使用：Anaconda集成了如下包,，不需要安裝即可使用

• 安裝scikit-learn: pip, easy_install, windows installer，安裝必要package：numpy,， SciPy和matplotlib,， 可使用Anaconda (包含numpy, scipy等科學計算常用package）

• 安裝注意問題：Python解釋器版本（2.7 or 3.4？）, 32-bit or 64-bit系統(tǒng)

商品購買例子：

轉(zhuǎn)化為csv文件如下：

3.3 運行效果如下：

其中,，datafile存放模型訓練數(shù)據(jù)集和測試數(shù)據(jù)集,，TarFile是算法生成文本形式的dot文件和轉(zhuǎn)化后的pdf圖像文件，兩個py文件,，一個是訓練算法一個是測試訓練結果,。右側(cè)預測值【0 1 1】代表三條測試數(shù)據(jù)，其中后兩條具備購買能力,。具體算法和細節(jié)下節(jié)詳解,。

3.4 具體算法和細節(jié)

python中導入決策樹相關包文件,，然后通過對csv格式轉(zhuǎn)化為sklearn工具包中可以識別的數(shù)據(jù)格式，再調(diào)用決策樹算法,，最后將模型訓練的結果以圖形形式展示,。

包的導入：

運行結果：

存儲特征數(shù)列和目標數(shù)列

運行結果：

運行結果：

運行結果：

將其轉(zhuǎn)化為圖像形式展示,，需要下載插件：安裝 下載Graphviz：

一路安裝下來,，然后打開cmd進入dos環(huán)境下，并進入../Tarfile/Tname.dot路徑下;#2 輸入dot -Tname.dot -o name.pdf命令,，將dos轉(zhuǎn)化為pdf格式

打開文件可見：

源碼和數(shù)據(jù)：

回復“決策樹”獲取。

 新浪微博名稱：大數(shù)據(jù)_機器學習

數(shù)據(jù)挖掘入門與實戰(zhàn)