目錄

一.決策樹

二.西瓜挑選問題描述

三.利用信息增益選擇最優劃分屬性

?四.用Python求解

五.用sk-learn庫對西瓜數據集，分別進行ID3、C4.5和CART的算法代碼實現

1.ID3算法

2.C4.5算法

3.CART算法

六.總結

---

一.決策樹

決策樹是一種基于樹結構來進行決策的分類算法，我們希望從給定的訓練數據集學得一個模型（即決策樹），用該模型對新樣本分類。決策樹可以非常直觀展現分類的過程和結果，一旦模型構建成功，對新樣本的分類效率也相當高。最經典的決策樹算法有ID3、C4.5、CART，其中ID3算法是最早被提出的，它可以處理離散屬性樣本的分類，C4.5和CART算法則可以處理更加復雜的分類問題.

二.西瓜挑選問題描述

舉個例子：夏天買西瓜時，我一般先選瓜皮有光澤的（新鮮），再拍一拍選聲音清脆的（成熟），這樣挑出來的好瓜的可能就比較大了。那么我挑西瓜的決策樹是這樣的：

下面，我們就對以下表格中的西瓜樣本構建決策樹模型。

三.利用信息增益選擇最優劃分屬性

樣本有多個屬性，該先選哪個樣本來劃分數據集呢？原則是隨著劃分不斷進行，我們希望決策樹的分支節點所包含的樣本盡可能屬于同一分類，即“純度”越來越高。先來學習一下“信息熵”和“信息增益”。

信息熵（information entropy）
樣本集合D中第k類樣本所占的比例（k=1,2,...,|Y|），|Y|為樣本分類的個數，則D的信息熵為：

Ent(D)的值越小，則D的純度越高。直觀理解一下：假設樣本集合有2個分類，每類樣本的比例為1/2，Ent(D)=1；只有一個分類，Ent（D）= 0，顯然后者比前者的純度高。

在西瓜樣本集中，共有17個樣本，其中正樣本8個，負樣本9個，樣本集的信息熵為：

信息增益（information gain）
使用屬性a對樣本集D進行劃分所獲得的“信息增益”的計算方法是，用樣本集的總信息熵減去屬性a的每個分支的信息熵與權重（該分支的樣本數除以總樣本數）的乘積，通常，信息增益越大，意味著用屬性a進行劃分所獲得的“純度提升”越大。因此，優先選擇信息增益最大的屬性來劃分。設屬性a有V個可能的取值，則屬性a的信息增益為：

西瓜樣本集中，以屬性“色澤”為例，它有3個取值{青綠、烏黑、淺白}，對應的子集（色澤=青綠）中有6個樣本，其中正負樣本各3個，（色澤=烏黑）中有6個樣本，正樣本4個，負樣本2個，（色澤=淺白）中有5個樣本，正樣本1個，fuya負樣本4個。

?

?四.用Python求解

代碼

#導入模塊 import pandas as pd import numpy as np from collections import Counter from math import log2#數據獲取與處理 def getData(filePath):data = pd.read_excel(filePath)return datadef dataDeal(data):dataList = np.array(data).tolist()dataSet = [element[1:] for element in dataList]return dataSet#獲取屬性名稱 def getLabels(data):labels = list(data.columns)[1:-1]return labels#獲取類別標記 def targetClass(dataSet):classification = set([element[-1] for element in dataSet])return classification#將分支結點標記為葉結點，選擇樣本數最多的類作為類標記 def majorityRule(dataSet):mostKind = Counter([element[-1] for element in dataSet]).most_common(1)majorityKind = mostKind[0][0]return majorityKind#計算信息熵 def infoEntropy(dataSet):classColumnCnt = Counter([element[-1] for element in dataSet])Ent = 0for symbol in classColumnCnt:p_k = classColumnCnt[symbol]/len(dataSet)Ent = Ent-p_k*log2(p_k)return Ent#子數據集構建 def makeAttributeData(dataSet,value,iColumn):attributeData = []for element in dataSet:if element[iColumn]==value:row = element[:iColumn]row.extend(element[iColumn+1:])attributeData.append(row)return attributeData#計算信息增益 def infoGain(dataSet,iColumn):Ent = infoEntropy(dataSet)tempGain = 0.0attribute = set([element[iColumn] for element in dataSet])for value in attribute:attributeData = makeAttributeData(dataSet,value,iColumn)tempGain = tempGain+len(attributeData)/len(dataSet)*infoEntropy(attributeData)Gain = Ent-tempGainreturn Gain#選擇最優屬性 def selectOptimalAttribute(dataSet,labels):bestGain = 0sequence = 0for iColumn in range(0,len(labels)):#不計最后的類別列Gain = infoGain(dataSet,iColumn)if Gain>bestGain:bestGain = Gainsequence = iColumnprint(labels[iColumn],Gain)return sequence#建立決策樹 def createTree(dataSet,labels):classification = targetClass(dataSet) #獲取類別種類（集合去重）if len(classification) == 1:return list(classification)[0]if len(labels) == 1:return majorityRule(dataSet)#返回樣本種類較多的類別sequence = selectOptimalAttribute(dataSet,labels)print(labels)optimalAttribute = labels[sequence]del(labels[sequence])myTree = {optimalAttribute:{}}attribute = set([element[sequence] for element in dataSet])for value in attribute:print(myTree)print(value)subLabels = labels[:]myTree[optimalAttribute][value] = \createTree(makeAttributeData(dataSet,value,sequence),subLabels)return myTreedef main():filePath = 'D:/watermelondata.xls'data = getData(filePath)dataSet = dataDeal(data)labels = getLabels(data)myTree = createTree(dataSet,labels)return myTreeif __name__ == '__main__':myTree = main()

輸出

色澤 0.10812516526536531 根蒂 0.14267495956679277 敲聲 0.14078143361499584 紋理 0.3805918973682686 臍部 0.28915878284167895 觸感 0.006046489176565584 ['色澤', '根蒂', '敲聲', '紋理', '臍部', '觸感'] {'紋理': {}} 稍糊 色澤 0.3219280948873623 根蒂 0.07290559532005603 敲聲 0.3219280948873623 臍部 0.17095059445466865 觸感 0.7219280948873623 ['色澤', '根蒂', '敲聲', '臍部', '觸感'] {'觸感': {}} 硬滑 {'觸感': {'硬滑': '否'}} 軟粘 {'紋理': {'稍糊': {'觸感': {'硬滑': '否', '軟粘': '是'}}}} 模糊 {'紋理': {'稍糊': {'觸感': {'硬滑': '否', '軟粘': '是'}}, '模糊': '否'}} 清晰 色澤 0.04306839587828004 根蒂 0.45810589515712374 敲聲 0.33085622540971754 臍部 0.45810589515712374 觸感 0.45810589515712374 ['色澤', '根蒂', '敲聲', '臍部', '觸感'] {'根蒂': {}} 硬挺 {'根蒂': {'硬挺': '否'}} 稍蜷 色澤 0.2516291673878229 敲聲 0.0 臍部 0.0 觸感 0.2516291673878229 ['色澤', '敲聲', '臍部', '觸感'] {'色澤': {}} 烏黑 敲聲 0.0 臍部 0.0 觸感 1.0 ['敲聲', '臍部', '觸感'] {'觸感': {}} 硬滑 {'觸感': {'硬滑': '是'}} 軟粘 {'色澤': {'烏黑': {'觸感': {'硬滑': '是', '軟粘': '否'}}}} 青綠 {'根蒂': {'硬挺': '否', '稍蜷': {'色澤': {'烏黑': {'觸感': {'硬滑': '是', '軟粘': '否'}}, '青綠': '是'}}}} 蜷縮

五.用sk-learn庫對西瓜數據集，分別進行ID3、C4.5和CART的算法代碼實現

1.ID3算法

熵和信息增益
設S是訓練樣本集，它包括n個類別的樣本，這些方法用Ci表示，那么熵和信息增益用下面公式表示：
信息熵：

?其中pi表示Ci的概率
樣本熵：

?其中Si表示根據屬性A劃分的S的第i個子集，S和Si表示樣本數目
信息增益：

?代碼

# 讀取西瓜數據集 import numpy as np import pandas as pd df = pd.read_table(r'D:/watermelon.txt',encoding='utf8',delimiter=',',index_col=0) df.head() # 由于上面的數據中包含了中文漢字，所以需要對數據進一步處理 ''' 屬性： 色澤 1-3代表 淺白 青綠 烏黑 根蒂 1-3代表 稍蜷 蜷縮 硬挺 敲聲 1-3代表 清脆 濁響 沉悶 紋理 1-3代表 清晰 稍糊 模糊 臍部 1-3代表 平坦 稍凹 凹陷 觸感 1-2代表 硬滑 軟粘 標簽： 好瓜 1代表 是 0 代表 不是 ''' df['色澤']=df['色澤'].map({'淺白':1,'青綠':2,'烏黑':3}) df['根蒂']=df['根蒂'].map({'稍蜷':1,'蜷縮':2,'硬挺':3}) df['敲聲']=df['敲聲'].map({'清脆':1,'濁響':2,'沉悶':3}) df['紋理']=df['紋理'].map({'清晰':1,'稍糊':2,'模糊':3}) df['臍部']=df['臍部'].map({'平坦':1,'稍凹':2,'凹陷':3}) df['觸感'] = np.where(df['觸感']=="硬滑",1,2) df['好瓜'] = np.where(df['好瓜']=="是",1,0) #由于西瓜數據集樣本比較少，所以不劃分數據集，將所有的西瓜數據用來訓練模型 Xtrain = df.iloc[:,:-1] Xtrain = np.array(Xtrain) Ytrain = df.iloc[:,-1] # 調用sklearn內置的決策樹的庫和畫圖工具 from sklearn import tree import graphviz # 采用ID3算法，利用信息熵構建決策樹模型 clf = tree.DecisionTreeClassifier(criterion="entropy") clf = clf.fit(Xtrain,Ytrain) # 繪制決策樹的圖形 feature_names = ["色澤","根蒂","敲聲","紋理","臍部","觸感"] dot_data = tree.export_graphviz(clf ,feature_names=feature_names ,class_names=["好瓜","壞瓜"] ,filled=True ,rounded=True ) graph = graphviz.Source(dot_data) graph

2.C4.5算法

（一）對比ID3的改進點
C4.5算法是用于生成決策樹的一種經典算法，是ID3算法的一種延伸和優化。C4.5算法對ID3算法進行了改進 ，改進點主要有：

用信息增益率來選擇劃分特征，克服了用信息增益選擇的不足，
信息增益率對可取值數目較少的屬性有所偏好；
能夠處理離散型和連續型的屬性類型，即將連續型的屬性進行離散化處理；
能夠處理具有缺失屬性值的訓練數據；
在構造樹的過程中進行剪枝；
（二）特征選擇
特征選擇也即選擇最優劃分屬性，從當前數據的特征中選擇一個特征作為當前節點的劃分標準。 隨著劃分過程不斷進行，希望決策樹的分支節點所包含的樣本盡可能屬于同一類別，即節點的“純度”越來越高。

（三）信息增益率
信息增益準則對可取值數目較多的屬性有所偏好，為減少這種偏好可能帶來的不利影響，C4.5算法采用信息增益率來選擇最優劃分屬性。增益率公式
?

3.CART算法

只需要將DecisionTreeClassifier函數的參數criterion的值改為gini：

clf = tree.DecisionTreeClassifier(criterion="gini") ?#實例化?
clf = clf.fit(x_train, y_train)?
score = clf.score(x_test, y_test)
print(score)

?畫決策樹

# 加上Graphviz2.38絕對路徑 import os os.environ["PATH"] += os.pathsep + 'D:/Some_App_Use/Anaconda/Anaconda3/Library/bin/graphviz'feature_name = ["色澤","根蒂","敲聲","紋理","臍部","觸感"] dot_data = tree.export_graphviz(clf ,feature_names= feature_name,class_names=["好瓜","壞瓜"],filled=True,rounded=True,out_file =None) graph = graphviz.Source(dot_data) graph # 加上Graphviz2.38絕對路徑 import os os.environ["PATH"] += os.pathsep + 'D:/Some_App_Use/Anaconda/Anaconda3/Library/bin/graphviz'feature_name = ["色澤","根蒂","敲聲","紋理","臍部","觸感"] dot_data = tree.export_graphviz(clf ,feature_names= feature_name,class_names=["好瓜","壞瓜"],filled=True,rounded=True,out_file =None) graph = graphviz.Source(dot_data) graph

六.總結

通過對決策樹的了解，以及相關的算法的代碼實現，讓我更深刻了解人工智能挑選過程.

參考鏈接：
https://blog.csdn.net/leaf_zizi/article/details/82848682
https://www.cnblogs.com/dennis-liucd/p/7905793.html
https://blog.csdn.net/keyue123/article/details/82253538
https://blog.csdn.net/qq_41775769/article/details/110822101
?

總結

以上是生活随笔為你收集整理的决策树之挑选西瓜的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。