文章原創(chuàng),最近更新：2018-08-16
學(xué)習(xí)參考鏈接:
1.機器學(xué)習(xí)(9)之ID3算法詳解及python實現(xiàn)
2.機器學(xué)習(xí)實戰(zhàn)-第3章《決策樹》
本章節(jié)的主要內(nèi)容是:
重點介紹項目案例1:判定魚類和非魚類遞歸構(gòu)建決策樹的函數(shù)代碼。
1.決策樹項目案例介紹:
項目案例1:
判定魚類和非魚類
項目概述:
- 根據(jù)以下 2 個特征，將動物分成兩類：魚類和非魚類篡九。
- 特征： 1. 不浮出水面是否可以生存 2. 是否有腳蹼
開發(fā)流程：
- 收集數(shù)據(jù)：可以使用任何方法
- 準備數(shù)據(jù)：樹構(gòu)造算法只適用于標稱型數(shù)據(jù)忧换，因此數(shù)值型數(shù)據(jù)必須離散化
- 分析數(shù)據(jù)：可以使用任何方法杨拐，構(gòu)造樹完成之后欣簇，我們應(yīng)該檢查圖形是否符合預(yù)期
- 訓(xùn)練算法：構(gòu)造樹的數(shù)據(jù)結(jié)構(gòu)
- 測試算法：使用決策樹執(zhí)行分類
- 使用算法：此步驟可以適用于任何監(jiān)督學(xué)習(xí)算法，而使用決策樹可以更好地理解數(shù)據(jù)的內(nèi)在含義
數(shù)據(jù)集介紹
2.遞歸構(gòu)建決策樹的函數(shù)代碼
2.1篩選出現(xiàn)次數(shù)最多的分類標簽名稱
如果數(shù)據(jù)集已經(jīng)處理了所有的屬性,但是類標簽依然不是唯一的,此時我們需要決定如何定義該葉子節(jié)點,在這種情況下,我們通常會采用多數(shù)表決的方法決定該葉子節(jié)點的分類.
在trees.py文件頂部增加一行代碼:import operator,然后添加下面的代碼到trees.py文件中.
#篩選出現(xiàn)次數(shù)最多的分類標簽名稱
def majorityCnt(classList):
"""
majorityCnt(篩選出現(xiàn)次數(shù)最多的分類標簽名稱)
Args:
classList 類別標簽的列表
Returns:
sortedClassCount[0][0] 出現(xiàn)次數(shù)最多的分類標簽名稱
假設(shè)classList=['yes', 'yes', 'no', 'no', 'no']
"""
classCount={}
for vote in classList:
if vote not in classCount.keys():classCount[vote]= 0
classCount[vote] += 1
"""
print(classCount[vote])的結(jié)果為:
{'yes': 1}
{'yes': 2}
{'yes': 2, 'no': 1}
{'yes': 2, 'no': 2}
{'yes': 2, 'no': 3}
"""
sortedClassCount =sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
"""
print(sortedClassCount)的結(jié)果為:
[('no', 3), ('yes', 2)]
"""
return sortedClassCount[0][0]
測試代碼及其結(jié)果如下:
import trees
classList=['yes', 'yes', 'no', 'no', 'no']
majorityCnt(classList)
Out[45]: 'no'
2.3遞歸構(gòu)建決策樹
所以決策樹是一個遞歸算法预麸，偽代碼如下：
def createBranch():
檢測數(shù)據(jù)集中的所有數(shù)據(jù)的分類標簽是否相同:
If so return 類標簽
Else:
尋找劃分數(shù)據(jù)集的最好特征（劃分之后信息熵最小侣姆，也就是信息增益最大的特征）
劃分數(shù)據(jù)集
創(chuàng)建分支節(jié)點
for 每個劃分的子集
調(diào)用函數(shù) createBranch （創(chuàng)建分支的函數(shù)）并增加返回結(jié)果到分支節(jié)點中
return 分支節(jié)點
構(gòu)建決策樹的算法流程如下：
- 得到原始數(shù)據(jù)集生真，
- 基于最好的屬性值劃分數(shù)據(jù)集，由于特征值可能多于兩個捺宗，因此可能存在大于兩個分支的數(shù)據(jù)集劃分柱蟀。
- 第一次劃分之后，數(shù)據(jù)將被向下傳遞到樹分支的下一個節(jié)點蚜厉，在這個節(jié)點上长已，我們可以再次劃分數(shù)據(jù)。我們可以采用遞歸的原則處理數(shù)據(jù)集昼牛。
- 遞歸結(jié)束的條件是术瓮，程序遍歷完所有劃分數(shù)據(jù)集的屬性，或者每個分支下的所有實例都具有相同的分類匾嘱。
參見如下圖所示:
決策樹一般使用遞歸的方法生成斤斧。
編寫遞歸函數(shù)有一個好習(xí)慣，就是先考慮結(jié)束條件霎烙。生成決策樹結(jié)束的條件有兩個：其一是劃分的數(shù)據(jù)都屬于一個類，其二是所有的特征都已經(jīng)使用了蕊连。在第二種結(jié)束情況中悬垃，劃分的數(shù)據(jù)有可能不全屬于一個類，這個時候需要根據(jù)多數(shù)表決準則確定這個子數(shù)據(jù)集的分類甘苍。
在非結(jié)束的條件下尝蠕，首先選擇出信息增益最大的特征，然后根據(jù)其分類载庭。分類開始時看彼，記錄分類的特征到?jīng)Q策樹中廊佩，然后在特征標簽集中刪除該特征，表示已經(jīng)使用過該特征靖榕。根據(jù)選中的特征將數(shù)據(jù)集分為若干個子數(shù)據(jù)集标锄，然后將子數(shù)據(jù)集作為參數(shù)遞歸創(chuàng)建決策樹，最終生成一棵完整的決策樹
# 創(chuàng)建樹的函數(shù)代碼
def createTree(dataSet, labels):
"""
createTree(創(chuàng)建樹)
Args:
dataSet 數(shù)據(jù)集
labels 標簽列表:標簽列表包含了數(shù)據(jù)集中所有特征的標簽茁计。最后代碼遍歷當前選擇
Returns:
myTree 標簽樹:特征包含的所有屬性值料皇，在每個數(shù)據(jù)集劃分上遞歸待用函數(shù)createTree()，
得到的返回值將被插入到字典變量myTree中星压，因此函數(shù)終止執(zhí)行時践剂，字典中將會嵌套很多代
表葉子節(jié)點信息的字典數(shù)據(jù)。
"""
#取得dataSet的最后一列數(shù)據(jù)保存在列表classList中
classList = [example[-1] for example in dataSet]
#如果classList中的第一個值在classList中的總數(shù)等于長度,也就是說classList中所有的值都一樣
#也就等價于當所有的類別只有一個時停止
if classList.count(classList[0])==len(classList):
return classList[0]
#當數(shù)據(jù)集中沒有特征可分時也停止
if len(dataSet[0])==1:
#通過majorityCnt()函數(shù)返回列表中最多的分類
return majorityCnt(classList)
#通過chooseBestFeatTopSplit()函數(shù)選出劃分數(shù)據(jù)集最佳的特癥
bestFeat = chooseBestFeatTopSplit(dataSet)
#最佳特征名 = 特征名列表中下標為bestFeat的元素
bestFeatLabel=labels[bestFeat]
# 構(gòu)造樹的根節(jié)點娜膘，多級字典的形式展現(xiàn)樹逊脯，類似多層json結(jié)構(gòu)
myTree={bestFeatLabel:{}}
# 刪除del列表labels中的最佳特征(就在labels變量上操作)
del(labels[bestFeat])
#取出所有訓(xùn)練樣本最佳特征的值形成一個list
featValues = [example[bestFeat] for example in dataSet]
# 通過set函數(shù)將featValues列表變成集合,去掉重復(fù)的值
uniqueVals = set(featValues)
for value in uniqueVals:
#復(fù)制類標簽并將其存儲在新列表subLabels中
subLabels = labels[:]
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
return myTree
測試代碼及其結(jié)果如下:
import trees
myDat,labels=createDataSet()
myTree =createTree(myDat,labels)
myTree
Out[55]: {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
3.決策樹相關(guān)知識點補充
3.1決策樹算法的過程
算法的過程為：
- 初始化信息增益的閾值?
- 判斷樣本是否為同一類輸出Di，如果是則返回單節(jié)點樹T竣贪。標記類別為Di
- 判斷特征是否為空军洼，如果是則返回單節(jié)點樹T，標記類別為樣本中輸出類別D實例數(shù)最多的類別贾富。
- 計算A中的各個特征（一共n個）對輸出D的信息增益歉眷，選擇信息增益最大的特征Ag
- 如果Ag的信息增益小于閾值?，則返回單節(jié)點樹T颤枪，標記類別為樣本中輸出類別D實例數(shù)最多的類別汗捡。
- 否則，按特征Ag的不同取值A(chǔ)gi將對應(yīng)的樣本輸出D分成不同的類別Di畏纲。每個類別產(chǎn)生一個子節(jié)點扇住。對應(yīng)特征值為Agi。返回增加了節(jié)點的數(shù)T盗胀。
- 對于所有的子節(jié)點艘蹋，令D=Di,A=A?{Ag}遞歸調(diào)用2-6步，得到子樹Ti并返回票灰。
3.2 ID3算法的不足
ID3算法雖然提出了新思路女阀，但是還是有很多值得改進的地方。
- ID3沒有考慮連續(xù)特征屑迂，比如長度浸策，密度都是連續(xù)值，無法在ID3運用惹盼。這大大限制了ID3的用途庸汗。
- ID3采用信息增益大的特征優(yōu)先建立決策樹的節(jié)點。很快就被人發(fā)現(xiàn)手报，在相同條件下蚯舱，取值比較多的特征比取值少的特征信息增益大改化。比如一個變量有2個值，各為1/2枉昏，另一個變量為3個值陈肛，各為1/3，其實他們都是完全不確定的變量凶掰，但是取3個值的比取2個值的信息增益大燥爷。如果校正這個問題呢？
- ID3算法對于缺失值的情況沒有做考慮
- 沒有考慮過擬合的問題
ID3 算法的作者昆蘭基于上述不足懦窘，對ID3算法做了改進前翎，這就是C4.5算法。
