機器學習--決策樹分類算法及應用

2022-12-08 10:17:17 來源：51CTO博客

1. 決策樹分類算法原理

1.1 概述


(資料圖)

決策樹（decision tree）——是一種被廣泛使用的分類算法。

相比貝葉斯算法，決策樹的優勢在于構造過程不需要任何領域知識或參數設置

在實際應用中，對于探測式的知識發現，決策樹更加適用

1.2 算法思想

通俗來說，決策樹分類的思想類似于找對象。現想象一個女孩的母親要給這個女孩介紹男朋友，于是有了下面的對話：

女兒：多大年紀了？

母親：26。

女兒：長的帥不帥？

母親：挺帥的。

女兒：收入高不？

母親：不算很高，中等情況。

女兒：是公務員不？

母親：是，在稅務局上班呢。

女兒：那好，我去見見。

這個女孩的決策過程就是典型的分類樹決策。

實質：通過年齡、長相、收入和是否公務員對將男人分為兩個類別：見和不見

假設這個女孩對男人的要求是：30歲以下、長相中等以上并且是高收入者或中等以上收入的公務員，那么這個可以用下圖表示女孩的決策邏輯

上圖完整表達了這個女孩決定是否見一個約會對象的策略，其中：

綠色節點表示判斷條件

橙色節點表示決策結果

箭頭表示在一個判斷條件在不同情況下的決策路徑

圖中紅色箭頭表示了上面例子中女孩的決策過程。

這幅圖基本可以算是一顆決策樹，說它“基本可以算”是因為圖中的判定條件沒有量化，如收入高中低等等，還不能算是嚴格意義上的決策樹，如果將所有條件量化，則就變成真正的決策樹了。

決策樹分類算法的關鍵就是根據“先驗數據”構造一棵最佳的決策樹，用以預測未知數據的類別

決策樹：是一個樹結構（可以是二叉樹或非二叉樹）。其每個非葉節點表示一個特征屬性上的測試，每個分支代表這個特征屬性在某個值域上的輸出，而每個葉節點存放一個類別。使用決策樹進行決策的過程就是從根節點開始，測試待分類項中相應的特征屬性，并按照其值選擇輸出分支，直到到達葉子節點，將葉子節點存放的類別作為決策結果。

1.3 決策樹構造

1.3.1 決策樹構造樣例

假如有以下判斷蘋果好壞的數據樣本：

樣本 紅 大 好蘋果

0 1 1 1

1 1 0 1

2 0 1 0

3 0 0 0

樣本中有2個屬性，A0表示是否紅蘋果。A1表示是否大蘋果。假如要根據這個數據樣本構建一棵自動判斷蘋果好壞的決策樹。

由于本例中的數據只有2個屬性，因此，我們可以窮舉所有可能構造出來的決策樹，就2棵，如下圖所示：

顯然左邊先使用A0（紅色）做劃分依據的決策樹要優于右邊用A1（大小）做劃分依據的決策樹。

當然這是直覺的認知。而直覺顯然不適合轉化成程序的實現，所以需要有一種定量的考察來評價這兩棵樹的性能好壞。

決策樹的評價所用的定量考察方法為計算每種劃分情況的信息熵增益：

如果經過某個選定的屬性進行數據劃分后的信息熵下降最多，則這個劃分屬性是最優選擇

1.3.2 屬性劃分選擇（即構造決策樹）的依據

熵：信息論的奠基人香農定義的用來信息量的單位。簡單來說，熵就是“無序，混亂”的程度。

通過計算來理解：

1、原始樣本數據的熵：

樣例總數：4

好蘋果：2

壞蘋果：2

熵：-(1/2 * log(1/2) +1/2 * log(1/2)) = 1

信息熵為1表示當前處于最混亂，最無序的狀態。

2、兩顆決策樹的劃分結果熵增益計算

l樹1先選A0作劃分，各子節點信息熵計算如下：

0，1葉子節點有2個正例，0個負例。信息熵為：e1 = -(2/2 * log(2/2) + 0/2 * log(0/2)) = 0。

2，3葉子節點有0個正例，2個負例。信息熵為：e2 = -(0/2 * log(0/2) + 2/2 * log(2/2)) = 0。

因此選擇A0劃分后的信息熵為每個子節點的信息熵所 zhan bi zhong 的加權和：

選擇A0做劃分的信息熵增益G（S, A0）=S - E = 1 - 0 = 1.

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

l樹2先選A1作劃分，各子節點信息熵計算如下：

0，2子節點有1個正例，1個負例。信息熵為：e1 = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1。

1，3子節點有1個正例，1個負例。信息熵為：e2 = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1。

因此選擇A1劃分后的信息熵為每個子節點的信息熵所zhan bi zhong的加權和：

也就是說分了跟沒分一樣！

選擇A1做劃分的信息熵增益G（S, A1）=S - E = 1 - 1 = 0.

因此，每次劃分之前，我們只需要計算出信息熵增益最大的那種劃分即可。

1.4 算法要點

1.4.1、指導思想

經過決策屬性的劃分后，數據的無序度越來越低，也就是信息熵越來越小

1.4.2算法實現

梳理出數據中的屬性

比較按照某特定屬性劃分后的數據的信息熵增益，選擇信息熵增益最大的那個屬性作為第一劃分依據，然后繼續選擇第二屬性，以此類推

2. 決策樹分類算法Python實戰

2.1 案例需求

我們的任務就是訓練一個決策樹分類器，輸入身高和體重，分類器能給出這個人是胖子還是瘦子。

所用的訓練數據如下，這個數據一共有10個樣本，每個樣本有2個屬性，分別為身高和體重，第三列為類別標簽，表示“胖”或“瘦”。該數據保存在1.txt中。

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

2.2 模型分析

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

雖然麻煩一點，不過這也不是問題，只需要找到將這些連續值劃分為不同區間的中間點，就轉換成了二值邏輯問題。

本例決策樹的任務是找到身高、體重中的一些臨界值，按照大于或者小于這些臨界值的邏輯將其樣本兩兩分類，自頂向下構建決策樹。

2.3 python實現

使用python的機器學習庫，實現起來相當簡單和優雅

?# -*- 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

""" 數據讀入 """

data = []

labels = []

with open("d:\\python\\ml\\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)

""" 標簽轉換為0/1 """

y[labels=="fat"]=1

""" 拆分訓練數據與測試數據 """

x_train, x_test, y_train, y_test = train_test_split(x, y, test_size = 0.2)

""" 使用信息熵作為劃分標準，對決策樹進行訓練 """

clf = tree.DecisionTreeClassifier(criterion="entropy")

print(clf)

clf.fit(x_train, y_train)

""" 把決策樹結構寫入文件 """

with open("tree.dot", "w") as f:

f = tree.export_graphviz(clf, out_file=f)

""" 系數反映每個特征的影響力。越大表示該特征在分類中起到的作用越大 """

print(clf.feature_importances_)

"""測試結果的打印"""

answer = clf.predict(x_train)

print(x_train)

print(answer)

print(y_train)

print(np.mean( answer == y_train))

"""準確率與召回率"""

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"]))?

這時候會輸出

[ 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.000.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.])

可以看到，對訓練過的數據做測試，準確率是100%。但是最后將所有數據進行測試，會出現1個測試樣本分類錯誤。

說明本例的決策樹對訓練集的規則吸收的很好，但是預測性稍微差點。?

2.4 決策樹的保存

一棵決策樹的學習訓練是非常耗費運算時間的，因此，決策樹訓練出來后，可進行保存，以便在預測新數據時只需要直接加載訓練好的決策樹即可

本案例的代碼中已經決策樹的結構寫入了tree.dot中。打開該文件，很容易畫出決策樹，還可以看到決策樹的更多分類信息。

本例的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 ;

}?

根據這個信息，決策樹應該長的如下這個樣子：

標簽： 機器學習 二值邏輯 基本可以

上一篇：短訊！機器學習--Logistic回歸分類算法及應用
下一篇：全球觀速訊丨分布式實時日志：ELK 的部署架構方案