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

http://yzkb.51969.com/

前言

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

一、原理篇

1、樹模型

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

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

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

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

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

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

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

2、樹的組成

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

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

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

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

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

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

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

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

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

4、衡量標準-熵

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

????????公式：

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

? ? ? ? 舉個例子：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 = {} # 計算每個元素出現(xiàn)的次數(shù)

for item in data:

if item in frequency:

frequency[item] += 1

else:

frequency[item] = 1

total_elements = len(data) # 計算總元素數(shù)量

entropy = 0 # 計算熵

for item, count in frequency.items():

p = count / total_elements # 計算當(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}")

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

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

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

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

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

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

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

? ? ? ? 4個特征逐一分析：

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

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

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

6、ID3、C4.5、CART

1）特征選擇準則

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

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

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

3）剪枝策略

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

4）其他差異

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

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

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

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

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

8、剪枝策略

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

（1）預(yù)剪枝：

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

（2）后剪枝：

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

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

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

????????例如上圖第一個節(jié)點的左孩子節(jié)點，gini為0，因為它所有數(shù)據(jù)都屬于a類，此時達到了純化。

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

9、回歸問題

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

二、代碼篇

1、基于sklearn實現(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 # 標簽

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) # 模型準確率

print(f"模型準確率: {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é)果：

模型準確率: 0.98?

2、基于python實現(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):

# 其實就是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)計類別最多的類

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)計特征個數(shù)

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

bestInfoGain = 0.0

bestFeature = -1

for i in range(numFeatures):

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

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

newEntropy = 0.0

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

subDataSet = splitDataSet(DataSet, i, value)

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

newEntropy += prob * calcshannonEnt(subDataSet)

infoGain = baseEntropy - newEntropy # 計算增益

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

bestInfoGain = infoGain

bestFeature = i

return bestFeature

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

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

# 計算某個特征的熵值

def calcshannonEnt(DataSet):

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

labelCounts = {}

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

currentLabel = featVec[-1]

if currentLabel not in labelCounts.keys():

labelCounts[currentLabel] = 0

labelCounts[currentLabel] += 1

shannonEnt = 0.0

for key in labelCounts: # 計算某個特征的熵值

prob = float(labelCounts[key]) / numExamples

shannonEnt -= prob * log(prob, 2)

return shannonEnt

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

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

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

arrow_args = dict(arrow)

def plotTree(myTree, parentPt, nodeTxt):

# 如果 myTree 是一個葉節(jié)點，直接返回

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 是一個葉子節(jié)點，直接返回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 是一個葉子節(jié)點，深度為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é)果：

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

http://yzkb.51969.com/

好文鏈接