柚子快報(bào)激活碼778899分享：機(jī)器學(xué)習(xí)——決策樹

http://yzkb.51969.com/

前言

? ? ? ? 跟著b站補(bǔ)基礎(chǔ)，視頻鏈接：第一章：決策樹原理 1-決策樹算法概述_嗶哩嗶哩_bilibili

一、原理篇

1、樹模型

?????????· 決策樹:從根節(jié)點(diǎn)開始一步步走到葉子節(jié)點(diǎn)(決策 )。

????????· 所有的數(shù)據(jù)最終都會(huì)落到葉子節(jié)點(diǎn)，既可以做分類也可以做回歸。

? ? ? ? 如上圖根據(jù)不同的特征：年齡以及性別進(jìn)行決策?，5個(gè)人（數(shù)據(jù)）落到了三個(gè)葉子節(jié)點(diǎn)。

????????分類問題是從不同類型的數(shù)據(jù)中學(xué)習(xí)到這些數(shù)據(jù)間的邊界，比如通過魚的體長、重量、魚鱗色澤等維度來分類鯰魚和鯉魚，這是一個(gè)定性問題。

????????回歸問題則是從同一類型的數(shù)據(jù)中學(xué)習(xí)到這種數(shù)據(jù)中不同維度間的規(guī)律，去擬合真實(shí)規(guī)律，比如通過數(shù)據(jù)學(xué)習(xí)到面積、房間數(shù)、房價(jià)幾個(gè)維度的關(guān)系，用于根據(jù)面積和房間數(shù)預(yù)測房價(jià)，這是一個(gè)定量問題。

[以上分類與回歸問題的文章：ML科普系列（二）分類與回歸 - 北島知寒 - 博客園 (cnblogs.com)]

? ? ? ? 在決策樹當(dāng)中，選擇特征進(jìn)行決策的順序是很重要的，不同的決策順序出來的結(jié)果可能會(huì)受影響而不同，所以把握決策的順序是很重要的。?

2、樹的組成

????????· 根節(jié)點(diǎn)：第一個(gè)選擇點(diǎn)（沒有前驅(qū)的節(jié)點(diǎn)，上圖中的根節(jié)點(diǎn)就是“age<15”）

????????· 非葉子節(jié)點(diǎn)與分支：中間過程

? ? ? ? · 葉子節(jié)點(diǎn)：最終的決策結(jié)果（沒有后繼的節(jié)點(diǎn)，上圖的葉子節(jié)點(diǎn)就是最后的三個(gè)?）

3、決策樹的訓(xùn)練與測試

? ? ? ? · 訓(xùn)練階段：從給定的訓(xùn)練集構(gòu)造出來一棵樹（從根節(jié)點(diǎn)開始選擇特征，如何進(jìn)行特征切分）

? ? ? ? · 測試階段：根據(jù)構(gòu)造出來的樹模型從上到下走一遍就好了

? ? ? ? 這里的難點(diǎn)在于如何進(jìn)行訓(xùn)練，特征的選擇順序應(yīng)該怎么排。

? ? ? ? 對(duì)于根節(jié)點(diǎn)的選擇，我們的目標(biāo)應(yīng)該是根節(jié)點(diǎn)就像一個(gè)老大似的能更好的切分?jǐn)?shù)據(jù)(分類的效果更好)，根節(jié)點(diǎn)下面的節(jié)點(diǎn)自然就是二當(dāng)家了，以此類推，數(shù)據(jù)能很快就完成了分類。

????????所以這就相當(dāng)于，通過一種衡量標(biāo)準(zhǔn)，來計(jì)算通過不同特征進(jìn)行分支選擇后的分類情況，找出來最好的那個(gè)當(dāng)成根節(jié)點(diǎn)，以此類推。

4、衡量標(biāo)準(zhǔn)-熵

? ? ? ? 熵：表示隨機(jī)變量不確定的度量（說白了就是混亂程度，商場買的類別越多就越混亂，專賣店只買一種類別就越穩(wěn)定）

????????公式：

? ? ? ? pi表示概率，我們都知道屬于某一類的概率只會(huì)在[0,1]，使用log的時(shí)候就在（-∞，0]區(qū)間內(nèi)，前面有-號(hào)，也就是[0，∞），再乘以pi，最終結(jié)果還是正值，然后將所有的情況進(jìn)行累加。

? ? ? ? 舉個(gè)例子：A集合[1，1，1，1，1，1，1，2，2]、B集合[1，2，3，4，5，6，7，8，9]

顯然A的類別少熵值小，B的類別多熵值大。

import math

def calculate_entropy(data):

frequency = {} # 計(jì)算每個(gè)元素出現(xiàn)的次數(shù)

for item in data:

if item in frequency:

frequency[item] += 1

else:

frequency[item] = 1

total_elements = len(data) # 計(jì)算總元素?cái)?shù)量

entropy = 0 # 計(jì)算熵

for item, count in frequency.items():

p = count / total_elements # 計(jì)算當(dāng)前元素出現(xiàn)的概率

entropy -= p * math.log2(p) # 累加熵

return entropy

A = [1, 1, 1, 1, 1, 1, 1, 2, 2]

B = [1, 2, 3, 4, 5, 6, 7, 8, 9]

entropy_A = calculate_entropy(A)

print(f"集合A的熵為: {entropy_A}")

entropy_B = calculate_entropy(B)

print(f"集合B的熵為: {entropy_B}")

? ? ? ? 因此可以知道，我們要想分類效果越好，就要熵值越小越好。也就是說，接下來要做的是讓分類更好，就是讓熵值越來越小，也就是要讓熵值下降，且選擇熵值下降越多的。

? ? ? ? 計(jì)算可知，當(dāng)p=0.5的時(shí)候，H(p)=1，此時(shí)的隨機(jī)變量不確定值最大；p=0或p=1時(shí)，H(p)=0，此時(shí)的隨機(jī)變量不確定值最小。

? ? ? ? 在選擇決策節(jié)點(diǎn)的時(shí)候，要考慮信息增益：表示特征X使得類Y的不確定性減少的程度。?

5、決策樹構(gòu)造實(shí)例

? ? ? ? 有以下數(shù)據(jù)，一共14條數(shù)據(jù)、4個(gè)特征。

? ? ? ? 在進(jìn)行決策選擇的時(shí)候，根據(jù)不同的特征有不同的結(jié)果：

? ? ? ? ?這時(shí)候就可以計(jì)算信息增益，來選擇決策節(jié)點(diǎn)。在歷史數(shù)據(jù)中，14天有9天打球，據(jù)此計(jì)算此時(shí)的熵值：

? ? ? ? 4個(gè)特征逐一分析：

????????根據(jù)數(shù)據(jù)統(tǒng)計(jì)，outlook取值分別為sunny、overcast、rainy的概率分別為：5/14、4/14、5/14 ????????熵值計(jì)算：5/14*0.971 + 4/14*0 + 5/14*0.971 = 0.693 ????????信息增益：系統(tǒng)的熵值從原始的0.940下降到了0.693，增益為0.247 ????????同樣的方式可以計(jì)算出其他特征的信息增益，選擇增益最多的就好了。

? ? ? ? 計(jì)算得到：gain(temperature)=0.029 ????????gain(humidity)=0.152 ????????gain(windy)=0.048?

? ? ? ? 所以最終選的的是outlook該特征進(jìn)行決策。接下來就繼續(xù)再現(xiàn)在分出來的3個(gè)類種，繼續(xù)分別進(jìn)行決策劃分，選擇二當(dāng)家，以此類推。

6、ID3、C4.5、CART

1）特征選擇準(zhǔn)則

ID3：使用信息增益作為選擇特征的準(zhǔn)則。信息增益是類別信息熵與某個(gè)屬性狀態(tài)下不同特征的信息熵（條件概率）的差值，它衡量了一個(gè)特征對(duì)于分類結(jié)果的影響程度。然而，ID3算法傾向于選擇取值較多的特征，這可能會(huì)導(dǎo)致過擬合。C4.5：在ID3的基礎(chǔ)上進(jìn)行了改進(jìn)，使用信息增益比作為選擇特征的準(zhǔn)則。信息增益比通過引入一個(gè)懲罰項(xiàng)（特征的固有值），來克服ID3算法中信息增益偏向選擇取值較多特征的不足。CART：對(duì)于分類樹，CART使用基尼指數(shù)作為選擇特征的準(zhǔn)則。基尼指數(shù)反映了從數(shù)據(jù)集D中隨機(jī)抽取兩個(gè)樣本，其類別標(biāo)記不一致的概率?；嶂笖?shù)越小，說明數(shù)據(jù)集D的純度越高。CART算法總是將當(dāng)前樣本集分割為兩個(gè)子樣本集，使得生成的決策樹的每個(gè)非葉結(jié)點(diǎn)都只有兩個(gè)分枝。

2）樹的結(jié)構(gòu)

ID3和C4.5：生成的決策樹可能包含多叉樹結(jié)構(gòu)，即每個(gè)內(nèi)部節(jié)點(diǎn)可能對(duì)應(yīng)多個(gè)分支。CART：生成的決策樹是二叉樹結(jié)構(gòu)，即每次分裂只產(chǎn)生兩個(gè)子節(jié)點(diǎn)。這使得CART算法生成的決策樹結(jié)構(gòu)更為簡潔。

3）剪枝策略

ID3：原始的ID3算法并沒有明確的剪枝策略，這可能導(dǎo)致生成的決策樹過擬合。但在實(shí)際應(yīng)用中，通常會(huì)結(jié)合剪枝策略來提高模型的泛化能力。C4.5：在樹構(gòu)造過程中進(jìn)行剪枝，通過預(yù)剪枝或后剪枝來減少模型的復(fù)雜度，防止過擬合。C4.5還提供了對(duì)連續(xù)屬性的離散化處理，以及對(duì)不完整數(shù)據(jù)的處理能力。CART：同樣需要進(jìn)行剪枝來防止過擬合。CART剪枝分為兩部分：生成子樹序列和交叉驗(yàn)證。通過選擇最優(yōu)的子樹來平衡模型的復(fù)雜度和預(yù)測性能。

4）其他差異

處理數(shù)據(jù)類型：ID3和C4.5可以同時(shí)處理標(biāo)稱型和數(shù)值型數(shù)據(jù)，而CART在分類任務(wù)中主要針對(duì)標(biāo)稱型數(shù)據(jù)進(jìn)行處理。應(yīng)用場景：ID3和C4.5主要用于分類任務(wù)，而CART既可以用于分類任務(wù)也可以用于回歸任務(wù)（當(dāng)CART用作回歸樹時(shí)，使用平方誤差作為劃分準(zhǔn)則）。

注：這部分是AI生成的，參考的文章：決策樹三種算法比較(ID3、C4.5、CART)_三種決策樹算法的區(qū)別-CSDN博客

ID3、C4.5、CART三種決策樹的區(qū)別_id3決策樹和c4.5決策樹的區(qū)別-CSDN博客

7、離散值與連續(xù)值

? ? ? ? 對(duì)于離散值，也就是類似于前面這種，可以根據(jù)特征進(jìn)行選擇，對(duì)于連續(xù)值也是類似的，選擇一個(gè)值將數(shù)據(jù)進(jìn)行離散化就好了。

8、剪枝策略

?????????決策樹隨著劃分的越來越細(xì)，在訓(xùn)練的時(shí)候效果會(huì)越來越好，但是在別的數(shù)據(jù)集上的泛化能力可能比較差效果不好，這就是過擬合情況，為了減少過擬合程度，因此要進(jìn)行剪枝操作。

（1）預(yù)剪枝：

? ? ? ? 預(yù)剪枝是邊建立決策樹邊進(jìn)行剪枝的操作。比如限制深度、葉子節(jié)點(diǎn)個(gè)數(shù)、葉子節(jié)點(diǎn)樣本數(shù)、信息增益量等。

（2）后剪枝：

? ? ? ? 后剪枝是當(dāng)建立完決策樹后來進(jìn)行剪枝操作。需要通過一定的衡量標(biāo)準(zhǔn)。C(T)是基尼系數(shù)，α是自己設(shè)置的，T_leaf是葉子節(jié)點(diǎn)數(shù)

? ? ? ? 如下是一個(gè)決策樹圖，X[]表示對(duì)應(yīng)數(shù)據(jù)集種的哪個(gè)特征，gini是基尼系數(shù)，samples是當(dāng)前節(jié)點(diǎn)所有樣本數(shù)量，value是不同類別的數(shù)量，例如第一個(gè)框中，[49,50,50]表示的是a類有49個(gè)b類有50個(gè)c類有50個(gè)。

?????????基尼系數(shù)表示在全部居民收入中，用于進(jìn)行不平均分配的那部分收入占總收入的百分比。社會(huì)中每個(gè)人的收入都一樣、收入分配絕對(duì)平均時(shí)，基尼系數(shù)是 0； 全社會(huì)的收入都集中于一個(gè)人、收入分配絕對(duì)不平均時(shí)，基尼系數(shù)是 1?，F(xiàn)實(shí)生活中，兩種情況都不可能發(fā)生，基尼系數(shù)的實(shí)際數(shù)值只能介于 0 ～ 1 之間?！緟⒖迹菏裁词腔嵯禂?shù) - 國家統(tǒng)計(jì)局 (stats.gov.cn)】

????????例如上圖第一個(gè)節(jié)點(diǎn)的左孩子節(jié)點(diǎn)，gini為0，因?yàn)樗袛?shù)據(jù)都屬于a類，此時(shí)達(dá)到了純化。

? ? ? ? ?某個(gè)節(jié)點(diǎn)要不要分裂，需要按照公式計(jì)算，如果新的C值比較大，就說明損失嚴(yán)重，需要分裂。

9、回歸問題

? ? ? ? 對(duì)于分類問題可以根據(jù)熵值進(jìn)行劃分，而回歸問題則根據(jù)方差結(jié)果（離散程度），預(yù)測結(jié)果是取該節(jié)點(diǎn)中所有數(shù)的平均數(shù)。

二、代碼篇

1、基于sklearn實(shí)現(xiàn)

? ? ? ? 這里使用的是iris數(shù)據(jù)集

from sklearn.datasets import load_iris

from sklearn.model_selection import train_test_split

from sklearn.tree import DecisionTreeClassifier

from sklearn import tree

import matplotlib.pyplot as plt

iris = load_iris() # 加載示例數(shù)據(jù)集

X = iris.data # 特征

y = iris.target # 標(biāo)簽

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

# 創(chuàng)建決策樹分類器

clf = DecisionTreeClassifier(criterion='entropy', max_depth=3, random_state=42)

clf.fit(X_train, y_train) # 訓(xùn)練模型

y_pred = clf.predict(X_test) # 預(yù)測

accuracy = clf.score(X_test, y_test) # 模型準(zhǔn)確率

print(f"模型準(zhǔn)確率: {accuracy:.2f}")

plt.figure(figsize=(6, 4)) # 可視化決策樹

tree.plot_tree(clf, feature_names=iris.feature_names, class_names=iris.target_names, filled=True)

plt.show()

? ? ? ? ?生成的決策樹如下所示：

? ? ? ? 輸出結(jié)果：

模型準(zhǔn)確率: 0.98?

2、基于python實(shí)現(xiàn)

import matplotlib.pyplot as plt

from math import log

import operator

# part1：定義數(shù)據(jù)集

def creatDataSet():

DataSet = [

[0, 0, 0, 0, 'no'],

[0, 0, 0, 1, 'no'],

[0, 1, 0, 1, 'yes'],

[0, 1, 1, 0, 'yes'],

[0, 0, 0, 0, 'no'],

[1, 0, 0, 0, 'no'],

[1, 1, 1, 1, 'yes'],

[1, 0, 1, 2, 'yes'],

[1, 0, 1, 2, 'yes'],

[2, 0, 1, 2, 'yes'],

[2, 0, 1, 1, 'yes'],

[2, 1, 0, 1, 'yes'],

[2, 1, 0, 2, 'yes'],

[2, 0, 0, 0, 'no']]

labels = ['F1-AGE', 'F2-WORK', 'F3-HOME', 'F4-LOAN']

return DataSet, labels

# part2：創(chuàng)建樹

def createTree(DataSet, labels, featLabels):

# 其實(shí)就是labels-classList：['no', 'no', 'yes', 'yes', 'no', 'no', 'yes', 'yes', 'yes', 'yes', 'yes', 'yes', 'yes', 'no']

classList = [example[-1] for example in DataSet]

# 判斷是否只屬于一類，所有數(shù)據(jù)均屬于同一類則返回該類別

if classList.count(classList[0]) == len(classList):

return classList[0]

# 判斷特征是否刪除完畢，返回最多的類

if len(DataSet[0]) == 1:

return majorityCnt(classList)

# 得到最佳收益的特征

bestFeat = chooseBestFeatureTosplit(DataSet)

# 得到最佳收益的label

bestFeatLabel = labels[bestFeat]

# 添加最佳label

featLabels.append(bestFeatLabel)

myTree = {bestFeatLabel: {}}

# 刪除特征

del(labels[bestFeat])

# 得到最佳特征的所有值

featValue = [example[bestFeat] for example in DataSet]

uniqueVals = set(featValue)

# 自調(diào)用創(chuàng)建樹

for value in uniqueVals:

sublabels = labels[:]

myTree[bestFeatLabel][value] = createTree(splitDataSet(DataSet, bestFeat, value), sublabels, featLabels)

return myTree

# 決策完成之后，統(tǒng)計(jì)類別最多的類

def majorityCnt(classList):

classCount = {}

for vote in classList:

if vote not in classCount.keys():

classCount[vote] = 0

classCount[vote] += 1

sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)

return sortedClassCount[0][0]

# 得到使得增益最高的特征

def chooseBestFeatureTosplit(DataSet):

numFeatures = len(DataSet[0]) - 1 # 統(tǒng)計(jì)特征個(gè)數(shù)

baseEntropy = calcshannonEnt(DataSet) # 計(jì)算最右邊特征的熵值，也就是還沒進(jìn)行決策的初始熵

bestInfoGain = 0.0

bestFeature = -1

for i in range(numFeatures):

featList = [example[i] for example in DataSet] # 存儲(chǔ)第i個(gè)特征的所有數(shù)據(jù)

uniqueVals = set(featList) # 只保留唯一數(shù)據(jù)

newEntropy = 0.0

for value in uniqueVals: # 計(jì)算根據(jù)某標(biāo)簽進(jìn)行劃分后的熵

subDataSet = splitDataSet(DataSet, i, value)

prob = len(subDataSet) / float(len(DataSet))

newEntropy += prob * calcshannonEnt(subDataSet)

infoGain = baseEntropy - newEntropy # 計(jì)算增益

if infoGain > bestInfoGain: # 判斷是否是最佳特征及最佳增益

bestInfoGain = infoGain

bestFeature = i

return bestFeature

# 按照第i個(gè)特征劃分不同值的數(shù)量（value在前面是循環(huán)的，所以會(huì)統(tǒng)計(jì)到每一類），并刪掉該特征

def splitDataSet(DataSet, axis, value):

retDataSet = []

for featVec in DataSet:

if featVec[axis] == value:

reducedFeatVec = featVec[:axis]

reducedFeatVec.extend(featVec[axis + 1:])

retDataSet.append(reducedFeatVec)

return retDataSet

# 計(jì)算某個(gè)特征的熵值

def calcshannonEnt(DataSet):

numExamples = len(DataSet) # 統(tǒng)計(jì)數(shù)據(jù)量

labelCounts = {}

for featVec in DataSet: # labelCounts：存儲(chǔ)最后一個(gè)特征的類別及數(shù)量

currentLabel = featVec[-1]

if currentLabel not in labelCounts.keys():

labelCounts[currentLabel] = 0

labelCounts[currentLabel] += 1

shannonEnt = 0.0

for key in labelCounts: # 計(jì)算某個(gè)特征的熵值

prob = float(labelCounts[key]) / numExamples

shannonEnt -= prob * log(prob, 2)

return shannonEnt

# 定義節(jié)點(diǎn)的格式

decisionNode = dict(box, fc="0.8")

leafNode = dict(box, fc="0.8")

arrow_args = dict(arrow)

def plotTree(myTree, parentPt, nodeTxt):

# 如果 myTree 是一個(gè)葉節(jié)點(diǎn)，直接返回

if type(myTree).__name__ != 'dict':

plotNode(myTree, parentPt, parentPt, leafNode)

return

numLeafs = getNumLeafs(myTree)

depth = getTreeDepth(myTree)

firstStr = list(myTree.keys())[0]

cntrPt = (plotTree.xOff + (1.0 + float(numLeafs)) / 2.0 / plotTree.totalW, plotTree.yOff)

plotMidText(cntrPt, parentPt, nodeTxt)

plotNode(firstStr, cntrPt, parentPt, decisionNode)

secondDict = myTree[firstStr]

plotTree.yOff = plotTree.yOff - 1.0 / plotTree.totalD

for key in secondDict.keys():

if type(secondDict[key]).__name__ == 'dict':

plotTree(secondDict[key], cntrPt, str(key))

else:

plotTree.xOff = plotTree.xOff + 1.0 / plotTree.totalW

plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)

plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))

plotTree.yOff = plotTree.yOff + 1.0 / plotTree.totalD

def plotMidText(cntrPt, parentPt, txtString):

xMid = (parentPt[0] - cntrPt[0]) / 2.0 + cntrPt[0]

yMid = (parentPt[1] - cntrPt[1]) / 2.0 + cntrPt[1]

plt.text(xMid, yMid, txtString)

def plotNode(nodeTxt, centerPt, parentPt, nodeType):

plt.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction', xytext=centerPt, textcoords='axes fraction',

va="center", ha="center", bbox=nodeType, arrowprops=arrow_args)

def createPlot(inTree):

fig = plt.figure(1, facecolor='white')

fig.clf()

axprops = dict(xticks=[], yticks=[])

createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)

plotTree.totalW = float(getNumLeafs(inTree))

plotTree.totalD = float(getTreeDepth(inTree))

plotTree.xOff = -0.5 / plotTree.totalW

plotTree.yOff = 1.0

plotTree(inTree, (0.5, 1.0), '')

plt.show()

def getNumLeafs(myTree):

numLeafs = 0

# 如果 myTree 是一個(gè)葉子節(jié)點(diǎn)，直接返回1

if type(myTree).__name__ != 'dict':

return 1

firstStr = list(myTree.keys())[0]

secondDict = myTree[firstStr]

for key in secondDict.keys():

if type(secondDict[key]).__name__ == 'dict':

numLeafs += getNumLeafs(secondDict[key])

else:

numLeafs += 1

return numLeafs

def getTreeDepth(myTree):

maxDepth = 0

# 如果 myTree 是一個(gè)葉子節(jié)點(diǎn)，深度為1

if type(myTree).__name__ != 'dict':

return 1

firstStr = list(myTree.keys())[0]

secondDict = myTree[firstStr]

for key in secondDict.keys():

if type(secondDict[key]).__name__ == 'dict':

thisDepth = 1 + getTreeDepth(secondDict[key])

else:

thisDepth = 1

if thisDepth > maxDepth:

maxDepth = thisDepth

return maxDepth

if __name__ == '__main__':

DataSet, labels = creatDataSet()

featLabels = []

myTree = createTree(DataSet, labels, featLabels)

createPlot(myTree)

? ? ? ? ?輸出結(jié)果：

柚子快報(bào)激活碼778899分享：機(jī)器學(xué)習(xí)——決策樹

http://yzkb.51969.com/

好文鏈接