用python實現cart算法的簡單介紹

本文目錄一覽：

1、用python實現紅酒數據集的ID3,C4.5和CART算法？
2、python中的sklearn中決策樹使用的是哪一種算法
3、如何用python實現巴斯卡三角形算法
4、如何利用python語言實現機器學習算法

用python實現紅酒數據集的ID3,C4.5和CART算法？

ID3算法介紹

ID3算法全稱為迭代二叉樹3代算法（Iterative Dichotomiser 3）

該算法要先進行特徵選擇，再生成決策樹，其中特徵選擇是基於“信息增益”最大的原則進行的。

但由於決策樹完全基於訓練集生成的，有可能對訓練集過於“依賴”，即產生過擬合現象。因此在生成決策樹後，需要對決策樹進行剪枝。剪枝有兩種形式，分別為前剪枝（Pre-Pruning）和後剪枝（Post-Pruning），一般採用後剪枝。

信息熵、條件熵和信息增益

信息熵：來自於香農定理，表示信息集合所含信息的平均不確定性。信息熵越大，表示不確定性越大，所含的信息量也就越大。

設x 1 , x 2 , x 3 , . . . x n {x_1, x_2, x_3, …x_n}x

,…x

為信息集合X的n個取值，則x i x_ix

的概率：

P ( X = i ) = p i , i = 1 , 2 , 3 , . . . , n P(X=i) = p_i, i=1,2,3,…,n

P(X=i)=p

,i=1,2,3,…,n

信息集合X的信息熵為：

H ( X ) = − ∑ i = 1 n p i log ⁡ p i H(X) =- \sum_{i=1}^{n}{p_i}\log{p_i}

H(X)=−

i=1

∑

logp

條件熵：指已知某個隨機變量的情況下，信息集合的信息熵。

設信息集合X中有y 1 , y 2 , y 3 , . . . y m {y_1, y_2, y_3, …y_m}y

,…y

組成的隨機變量集合Y，則隨機變量（X，Y）的聯合概率分布為

P ( x = i , y = j ) = p i j P(x=i,y=j) = p_{ij}

P(x=i,y=j)=p

條件熵：

H ( X ∣ Y ) = ∑ j = 1 m p ( y j ) H ( X ∣ y j ) H(X|Y) = \sum_{j=1}^m{p(y_j)H(X|y_j)}

H(X∣Y)=

j=1

∑

p(y

)H(X∣y

)

由

H ( X ∣ y j ) = − ∑ j = 1 m p ( y j ) ∑ i = 1 n p ( x i ∣ y j ) log ⁡ p ( x i ∣ y j ) H(X|y_j) = – \sum_{j=1}^m{p(y_j)}\sum_{i=1}^n{p(x_i|y_j)}\log{p(x_i|y_j)}

H(X∣y

)=−

j=1

∑

p(y

)

i=1

∑

p(x

∣y

)logp(x

∣y

)

和貝葉斯公式：

p ( x i y j ) = p ( x i ∣ y j ) p ( y j ) p(x_iy_j) = p(x_i|y_j)p(y_j)

p(x

)=p(x

∣y

)p(y

)

可以化簡條件熵的計算公式為:

H ( X ∣ Y ) = ∑ j = 1 m ∑ i = 1 n p ( x i , y j ) log ⁡ p ( x i ) p ( x i , y j ) H(X|Y) = \sum_{j=1}^m \sum_{i=1}^n{p(x_i, y_j)\log\frac{p(x_i)}{p(x_i, y_j)}}

H(X∣Y)=

j=1

∑

i=1

∑

p(x

)log

p(x

)

p(x

)

信息增益：信息熵-條件熵，用于衡量在知道已知隨機變量後，信息不確定性減小越大。

d ( X , Y ) = H ( X ) − H ( X ∣ Y ) d(X,Y) = H(X) – H(X|Y)

d(X,Y)=H(X)−H(X∣Y)

python代碼實現

import numpy as np

import math

def calShannonEnt(dataSet):

“”” 計算信息熵 “””

labelCountDict = {}

for d in dataSet:

label = d[-1]

if label not in labelCountDict.keys():

labelCountDict[label] = 1

else:

labelCountDict[label] += 1

entropy = 0.0

for l, c in labelCountDict.items():

p = 1.0 * c / len(dataSet)

entropy -= p * math.log(p, 2)

return entropy

def filterSubDataSet(dataSet, colIndex, value):

“””返回colIndex特徵列label等於value，並且過濾掉改特徵列的數據集”””

subDataSetList = []

for r in dataSet:

if r[colIndex] == value:

newR = r[:colIndex]

newR = np.append(newR, (r[colIndex + 1:]))

subDataSetList.append(newR)

return np.array(subDataSetList)

def chooseFeature(dataSet):

“”” 通過計算信息增益選擇最合適的特徵”””

featureNum = dataSet.shape[1] – 1

entropy = calShannonEnt(dataSet)

bestInfoGain = 0.0

bestFeatureIndex = -1

for i in range(featureNum):

uniqueValues = np.unique(dataSet[:, i])

condition_entropy = 0.0

for v in uniqueValues: #計算條件熵

subDataSet = filterSubDataSet(dataSet, i, v)

p = 1.0 * len(subDataSet) / len(dataSet)

condition_entropy += p * calShannonEnt(subDataSet)

infoGain = entropy – condition_entropy #計算信息增益

if infoGain = bestInfoGain: #選擇最大信息增益

bestInfoGain = infoGain

bestFeatureIndex = i

return bestFeatureIndex

def creatDecisionTree(dataSet, featNames):

“”” 通過訓練集生成決策樹 “””

featureName = featNames[:] # 拷貝featNames，此處不能直接用賦值操作，否則新變量會指向舊變量的地址

classList = list(dataSet[:, -1])

if len(set(classList)) == 1: # 只有一個類別

return classList[0]

if dataSet.shape[1] == 1: #當所有特徵屬性都利用完仍然無法判斷樣本屬於哪一類，此時歸為該數據集中數量最多的那一類

return max(set(classList), key=classList.count)

bestFeatureIndex = chooseFeature(dataSet) #選擇特徵

bestFeatureName = featNames[bestFeatureIndex]

del featureName[bestFeatureIndex] #移除已選特徵列

decisionTree = {bestFeatureName: {}}

featureValueUnique = sorted(set(dataSet[:, bestFeatureIndex])) #已選特徵列所包含的類別，通過遞歸生成決策樹

for v in featureValueUnique:

copyFeatureName = featureName[:]

subDataSet = filterSubDataSet(dataSet, bestFeatureIndex, v)

decisionTree[bestFeatureName][v] = creatDecisionTree(subDataSet, copyFeatureName)

return decisionTree

def classify(decisionTree, featnames, featList):

“”” 使用訓練所得的決策樹進行分類 “””

classLabel = None

root = decisionTree.keys()[0]

firstGenDict = decisionTree[root]

featIndex = featnames.index(root)

for k in firstGenDict.keys():

if featList[featIndex] == k:

if isinstance(firstGenDict[k], dict): #若子節點仍是樹，則遞歸查找

classLabel = classify(firstGenDict[k], featnames, featList)

else:

classLabel = firstGenDict[k]

return classLabel

下面用鳶尾花數據集對該算法進行測試。由於ID3算法只能用於標稱型數據，因此用在對連續型的數值數據上時，還需要對數據進行離散化，離散化的方法稍後說明，此處為了簡化，先使用每一種特徵所有連續性數值的中值作為分界點，小於中值的標記為1，大於中值的標記為0。訓練1000次，統計準確率均值。

from sklearn import datasets

from sklearn.model_selection import train_test_split

iris = datasets.load_iris()

data = np.c_[iris.data, iris.target]

scoreL = []

for i in range(1000): #對該過程進行10000次

trainData, testData = train_test_split(data) #區分測試集和訓練集

featNames = iris.feature_names[:]

for i in range(trainData.shape[1] – 1): #對訓練集每個特徵，以中值為分界點進行離散化

splitPoint = np.mean(trainData[:, i])

featNames[i] = featNames[i]+’=’+'{:.3f}’.format(splitPoint)

trainData[:, i] = [1 if x = splitPoint else 0 for x in trainData[:, i]]

testData[:, i] = [1 if x = splitPoint else 0 for x in testData[:, i]]

decisionTree = creatDecisionTree(trainData, featNames)

classifyLable = [classify(decisionTree, featNames, td) for td in testData]

scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))

print ‘score: ‘, np.mean(scoreL)

輸出結果為：score: 0.7335，即準確率有73%。每次訓練和預測的準確率分布如下：

數據離散化

然而，在上例中對特徵值離散化的劃分點實際上過於“野蠻”，此處介紹一種通過信息增益最大的標準來對數據進行離散化。原理很簡單，當信息增益最大時，說明用該點劃分能最大程度降低數據集的不確定性。

具體步驟如下：

對每個特徵所包含的數值型特徵值排序

對相鄰兩個特徵值取均值，這些均值就是待選的劃分點

用每一個待選點把該特徵的特徵值劃分成兩類，小於該特徵點置為1，大於該特徵點置為0，計算此時的條件熵，並計算出信息增益

選擇信息使信息增益最大的劃分點進行特徵離散化

實現代碼如下：

def filterRawData(dataSet, colIndex, value, tag):

“”” 用於把每個特徵的連續值按照區分點分成兩類，加入tag參數，可用於標記篩選的是哪一部分數據”””

filterDataList = []

for r in dataSet:

if (tag and r[colIndex] = value) or ((not tag) and r[colIndex] value):

newR = r[:colIndex]

newR = np.append(newR, (r[colIndex + 1:]))

filterDataList.append(newR)

return np.array(filterDataList)

def dataDiscretization(dataSet, featName):

“”” 對數據每個特徵的數值型特徵值進行離散化 “””

featureNum = dataSet.shape[1] – 1

entropy = calShannonEnt(dataSet)

for featIndex in range(featureNum): #對於每一個特徵

uniqueValues = sorted(np.unique(dataSet[:, featIndex]))

meanPoint = []

for i in range(len(uniqueValues) – 1): # 求出相鄰兩個值的平均值

meanPoint.append(float(uniqueValues[i+1] + uniqueValues[i]) / 2.0)

bestInfoGain = 0.0

bestMeanPoint = -1

for mp in meanPoint: #對於每個劃分點

subEntropy = 0.0 #計算該劃分點的信息熵

for tag in range(2): #分別劃分為兩類

subDataSet = filterRawData(dataSet, featIndex, mp, tag)

p = 1.0 * len(subDataSet) / len(dataSet)

subEntropy += p * calShannonEnt(subDataSet)

## 計算信息增益

infoGain = entropy – subEntropy

## 選擇最大信息增益

if infoGain = bestInfoGain:

bestInfoGain = infoGain

bestMeanPoint = mp

featName[featIndex] = featName[featIndex] + “=” + “{:.3f}”.format(bestMeanPoint)

dataSet[:, featIndex] = [1 if x = bestMeanPoint else 0 for x in dataSet[:, featIndex]]

return dataSet, featName

重新對數據進行離散化，並重複該步驟1000次，同時用sklearn中的DecisionTreeClassifier對相同數據進行分類，分別統計平均準確率。運行代碼如下:

from sklearn.tree import DecisionTreeClassifier

import matplotlib.pyplot as plt

scoreL = []

scoreL_sk = []

for i in range(1000): #對該過程進行1000次

featNames = iris.feature_names[:]

trainData, testData = train_test_split(data) #區分測試集和訓練集

trainData_tmp = copy.copy(trainData)

testData_tmp = copy.copy(testData)

discritizationData, discritizationFeatName= dataDiscretization(trainData, featNames) #根據信息增益離散化

for i in range(testData.shape[1]-1): #根據測試集的區分點離散化訓練集

splitPoint = float(discritizationFeatName[i].split(‘=’)[-1])

testData[:, i] = [1 if x=splitPoint else 0 for x in testData[:, i]]

decisionTree = creatDecisionTree(trainData, featNames)

classifyLable = [classify(decisionTree, featNames, td) for td in testData]

scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))

clf = DecisionTreeClassifier(‘entropy’)

clf.fit(trainData[:, :-1], trainData[:, -1])

clf.predict(testData[:, :-1])

scoreL_sk.append(clf.score(testData[:, :-1], testData[:, -1]))

print ‘score: ‘, np.mean(scoreL)

print ‘score-sk: ‘, np.mean(scoreL_sk)

fig = plt.figure(figsize=(10, 4))

plt.subplot(1,2,1)

pd.Series(scoreL).hist(grid=False, bins=10)

plt.subplot(1,2,2)

pd.Series(scoreL_sk).hist(grid=False, bins=10)

plt.show()

兩者準確率分別為：

score: 0.7037894736842105

score-sk: 0.7044736842105263

準確率分布如下：

兩者的結果非常一樣。

（但是。。為什麼根據信息熵離散化得到的準確率比直接用均值離散化的準確率還要低啊？？哇的哭出聲。。）

最後一次決策樹圖形如下：

決策樹剪枝

由於決策樹是完全依照訓練集生成的，有可能會有過擬合現象，因此一般會對生成的決策樹進行剪枝。常用的是通過決策樹損失函數剪枝，決策樹損失函數表示為:

C a ( T ) = ∑ t = 1 T N t H t ( T ) + α ∣ T ∣ C_a(T) = \sum_{t=1}^TN_tH_t(T) +\alpha|T|

(T)=

t=1

∑

(T)+α∣T∣

其中，H t ( T ) H_t(T)H

(T)表示葉子節點t的熵值，T表示決策樹的深度。前項∑ t = 1 T N t H t ( T ) \sum_{t=1}^TN_tH_t(T)∑

t=1

(T)是決策樹的經驗損失函數當隨着T的增加，該節點被不停的劃分的時候，熵值可以達到最小，然而T的增加會使後項的值增大。決策樹損失函數要做的就是在兩者之間進行平衡，使得該值最小。

對於決策樹損失函數的理解，如何理解決策樹的損失函數? – 陶輕鬆的回答 – 知乎這個回答寫得挺好，可以按照答主的思路理解一下

C4.5算法

ID3算法通過信息增益來進行特徵選擇會有一個比較明顯的缺點：即在選擇的過程中該算法會優先選擇類別較多的屬性（這些屬性的不確定性小，條件熵小，因此信息增益會大），另外，ID3算法無法解決當每個特徵屬性中每個分類都只有一個樣本的情況（此時每個屬性的條件熵都為0）。

C4.5算法ID3算法的改進，它不是依據信息增益進行特徵選擇，而是依據信息增益率，它添加了特徵分裂信息作為懲罰項。定義分裂信息：

S p l i t I n f o ( X , Y ) = − ∑ i n ∣ X i ∣ ∣ X ∣ log ⁡ ∣ X i ∣ ∣ X ∣ SplitInfo(X, Y) =-\sum_i^n\frac{|X_i|}{|X|}\log\frac{|X_i|}{|X|}

SplitInfo(X,Y)=−

∑

∣X∣

∣X

∣

log

∣X∣

∣X

∣

則信息增益率為：

G a i n R a t i o ( X , Y ) = d ( X , Y ) S p l i t I n f o ( X , Y ) GainRatio(X,Y)=\frac{d(X,Y)}{SplitInfo(X, Y)}

GainRatio(X,Y)=

SplitInfo(X,Y)

d(X,Y)

關於ID3和C4.5算法

在學習分類回歸決策樹算法時，看了不少的資料和博客。關於這兩個算法，ID3算法是最早的分類算法，這個算法剛出生的時候其實帶有很多缺陷：

無法處理連續性特徵數據

特徵選取會傾向於分類較多的特徵

沒有解決過擬合的問題

沒有解決缺失值的問題

即該算法出生時是沒有帶有連續特徵離散化、剪枝等步驟的。C4.5作為ID3的改進版本彌補列ID3算法不少的缺陷：

通過信息最大增益的標準離散化連續的特徵數據

在選擇特徵是標準從“最大信息增益”改為“最大信息增益率”

通過加入正則項係數對決策樹進行剪枝

對缺失值的處理體現在兩個方面：特徵選擇和生成決策樹。初始條件下對每個樣本的權重置為1。

特徵選擇：在選取最優特徵時，計算出每個特徵的信息增益後，需要乘以一個**“非缺失值樣本權重佔總樣本權重的比例”**作為係數來對比每個特徵信息增益的大小

生成決策樹：在生成決策樹時，對於缺失的樣本我們按照一定比例把它歸屬到每個特徵值中，比例為該特徵每一個特徵值占非缺失數據的比重

關於C4.5和CART回歸樹

作為ID3的改進版本，C4.5克服了許多缺陷，但是它自身還是存在不少問題：

C4.5的熵運算中涉及了對數運算，在數據量大的時候效率非常低。

C4.5的剪枝過於簡單

C4.5隻能用於分類運算不能用於回歸

當特徵有多個特徵值是C4.5生成多叉樹會使樹的深度加深

————————————————

原文鏈接：

python中的sklearn中決策樹使用的是哪一種算法

要弄清楚這個問題，首先要弄懂決策樹三大流行算法ID3、C4.5和CART的原理，以及sklearn框架下DecisionTreeClassifier的幫助文檔。

3個算法的主要區別在於度量信息方法、選擇節點特徵還有分支數量的不同。

ID3，採用熵（entropy）來度量信息不確定度，選擇“信息增益”最大的作為節點特徵，它是多叉樹，即一個節點可以有多個分支。

C4.5，同樣採用熵（entropy）來度量信息不確定度，選擇“信息增益比”最大的作為節點特徵，同樣是多叉樹，即一個節點可以有多個分支。

CART，採用基尼指數（Gini index）來度量信息不純度，選擇基尼指數最小的作為節點特徵，它是二叉樹，即一個節點只分兩支。

然後你認真閱讀sklearn的DecisionTreeClassifier的幫助文檔，可以發現，度量信息的方法默認是Gini，但可以改成entropy，請按需選擇；構建的樹是二叉樹；可以通過設置max_deepth、max_leaf等來實現“剪枝”，這是根據CART的損失函數減少的理論進行的。

所以總結說，如果信息度量方法按照默認的設置，那麼sklearn所用的決策樹分類器就是CART，如果改成了entropy，那麼只是使用了別的度量方法而已。其實兩者差不多。

如何用python實現巴斯卡三角形算法

1、何為帕斯卡三角形（巴斯卡三角形）

其實，帕斯卡三角形就是楊輝三角形，是二項式係數的一種寫法，從第0層開始，依次類推，如圖所示：

比如第2層中的1 2 1 對應的是冪指數為2的二項式運算(a+b)^2=a^2+2ab+b^2的係數

2、如何用python實現該算法

在碰到難的題目，一時不知道如何下手解決的時候，不要慌，首先分析該問題，然後找出規律，最後一步步地細化問題，捉住重點，代碼分塊實現，問題就會迎刃而解，同樣對於巴斯卡三角形的問題分析如下：

1）、每一層的第一個元素和最後一個元素都是為1

2）、從第二層開始，除了每層的第一個元素和最後一個元素外，其他的每個元素都是等於該元素的左上角和右上角的元素之和

3）、可以看出第0層元素個數為1個，第1層元素個數為2個，第2層元素個數為3個，依次類推，第N層元素的個數為N+1

4）、假設總共有三層，那麼第0層第一個元素的前面的空格數就是2個，第1層空格數就是1，第2層空格數就是0個，可以推出如果有N層，那麼第0層的第一個元素前面的空格數為N-1，以此類推

代碼實現：

運行該模塊，調用pascal函數，得到結果：

注意：可能有的同學會將layerList列表定義為全局變量，如果你真的這麼做了，後果很嚴重，你會為你的行為付出慘痛的代價；最好定義為函數中的局部變量。

到這裡已經結束，如果你有更好的想法，歡迎交流，我們共同成長，如果有錯的地方或寫的不好的地方請指出，我們共同進步，謝謝你們，我們下次再見！

如何利用python語言實現機器學習算法

基於以下三個原因，我們選擇Python作為實現機器學習算法的編程語言：(一) Python的語法清晰；(二) 易於操作純文本文件；(三) 使用廣泛，存在大量的開發文檔。可執行偽代碼 Python具有清晰的語法結構，大家也把它稱作可執行偽代碼（executable pseudo-code）。默認安裝的Python開發環境已經附帶了很多高級數據類型，如列表、元組、字典、集合、隊列等，無需進一步編程就可以使用這些數據類型的操作。使用這些數據類型使得實現抽象的數學概念非常簡單。此外，讀者還可以使用自己熟悉的編程風格，如面向對象編程、面向過程編程、或者函數式編程。不熟悉Python的讀者可以參閱附錄A，該附錄詳細介紹了Python語言、Python使用的數據類型以及安裝指南。 Python語言處理和操作文本文件非常簡單，非常易於處理非數值型數據。Python語言提供了豐富的正則表達式函數以及很多訪問Web頁面的函數庫，使得從HTML中提取數據變得非常簡單直觀。 Python比較流行 Python語言使用廣泛，代碼範例也很多，便於讀者快速學習和掌握。此外，在開發實際應用程序時，也可以利用豐富的模塊庫縮短開發周期。在科學和金融領域，Python語言得到了廣泛應用。SciPy和NumPy等許多科學函數庫都實現了向量和矩陣操作，這些函數庫增加了代碼的可讀性，學過線性代數的人都可以看懂代碼的實際功能。另外，科學函數庫SciPy和NumPy使用底層語言（C和Fortran）編寫，提高了相關應用程序的計算性能。本書將大量使用Python的NumPy。 Python的科學工具可以與繪圖工具Matplotlib協同工作。Matplotlib可以繪製二D、三D圖形，也可以處理科學研究中經常使用到的圖形，所以本書也將大量使用Matplotlib。 Python開發環境還提供了交互式shell環境，允許用戶開發程序時查看和檢測程序內容。 Python開發環境將來還會集成Pylab模塊，它將NumPy、SciPy和Matplotlib合併為一個開發環境。在本書寫作時，Pylab還沒有併入Python環境，但是不遠的將來我們肯定可以在Python開發環境找到它。 Python語言的特色諸如MATLAB和Mathematica等高級程序語言也允許用戶執行矩陣操作，MATLAB甚至還有許多內嵌的特徵可以輕鬆地構造機器學習應用，而且MATLAB的運算速度也很快。然而MATLAB的不足之處是軟件費用太高，單個軟件授權就要花費數千美元。雖然也有適合MATLAB的第三方插件，但是沒有一個有影響力的大型開源項目。 Java和C等強類型程序設計語言也有矩陣數學庫，然而對於這些程序設計語言來說，最大的問題是即使完成簡單的操作也要編寫大量的代碼。程序員首先需要定義變量的類型，對於Java來說，每次封裝屬性時還需要實現getter和setter方法。另外還要記着實現子類，即使並不想使用子類，也必須實現子類方法。為了完成一個簡單的工作，我們必須花費大量時間編寫了很多無用冗長的代碼。Python語言則與Java和C完全不同，它清晰簡練，而且易於理解，即使不是編程人員也能夠理解程序的含義，而Java和C對於非編程人員則像天書一樣難於理解。所有人在小學二年級已經學會了寫作，然而大多數人必須從事其他更重要的工作。 ——鮑比·奈特也許某一天，我們可以在這句話中將“寫作”替代為“編寫代碼”，雖然有些人對於編寫代碼很感興趣，但是對於大多數人來說，編程僅是完成其他任務的工具而已。Python語言是高級編程語言，我們可以花費更多的時間處理數據的內在含義，而無須花費太多精力解決計算機如何得到數據結果。Python語言使得我們很容易表達自己的目的。 Python語言的缺點 Python語言唯一的不足是性能問題。Python程序運行的效率不如Java或者C代碼高，但是我們可以使用Python調用C編譯的代碼。這樣，我們就可以同時利用C和Python的優點，逐步地開發機器學習應用程序。我們可以首先使用Python編寫實驗程序，如果進一步想要在產品中實現機器學習，轉換成C代碼也不困難。如果程序是按照模塊化原則組織的，我們可以先構造可運行的Python程序，然後再逐步使用C代碼替換核心代碼以改進程序的性能。C++ Boost庫就適合完成這個任務，其他類似於Cython和PyPy的工具也可以編寫強類型的Python代碼，改進一般Python程序的性能。如果程序的算法或者思想有缺陷，則無論程序的性能如何，都無法得到正確的結果。如果解決問題的思想存在問題，那麼單純通過提高程序的運行效率，擴展用戶規模都無法解決這個核心問題。從這個角度來看，Python快速實現系統的優勢就更加明顯了，我們可以快速地檢驗算法或者思想是否正確，如果需要，再進一步優化代碼

原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-hant/n/219982.html