摘要:本篇內(nèi)容為機(jī)器學(xué)習(xí)實(shí)戰(zhàn)第章決策樹部分程序清單。適用數(shù)據(jù)類型數(shù)值型和標(biāo)稱型在構(gòu)造決策樹時(shí),我們需要解決的第一個(gè)問題就是,當(dāng)前數(shù)據(jù)集上哪個(gè)特征在劃分?jǐn)?shù)據(jù)分類時(shí)起決定性作用。下面我們會(huì)介紹如何將上述實(shí)現(xiàn)的函數(shù)功能放在一起,構(gòu)建決策樹。
本篇內(nèi)容為《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》第 3 章決策樹部分程序清單。所用代碼為 python3。
決策樹
優(yōu)點(diǎn):計(jì)算復(fù)雜度不高,輸出結(jié)果易于理解,對(duì)中間值的缺失不敏感,可以處理不相關(guān)特征數(shù)據(jù)。
缺點(diǎn):可能會(huì)產(chǎn)生過度匹配問題。
適用數(shù)據(jù)類型:數(shù)值型和標(biāo)稱型
在構(gòu)造決策樹時(shí),我們需要解決的第一個(gè)問題就是,當(dāng)前數(shù)據(jù)集上哪個(gè)特征在劃分?jǐn)?shù)據(jù)分類時(shí)起決定性作用。為了找到?jīng)Q定性的特征,劃分出最好的結(jié)果,我們必須評(píng)估每個(gè)特征。完成測試之后,原始數(shù)據(jù)集就被劃分為幾個(gè)數(shù)據(jù)子集。這些數(shù)據(jù)子集會(huì)分布在第一個(gè)決策點(diǎn)的所有分支上。如果某個(gè)分支下的數(shù)據(jù)屬于同一類型,則無需進(jìn)一步對(duì)數(shù)據(jù)集進(jìn)行分割。如果數(shù)據(jù)子集內(nèi)的數(shù)據(jù)不屬于同一類型,則需要重復(fù)劃分?jǐn)?shù)據(jù)子集的過程。劃分?jǐn)?shù)據(jù)子集的算法和劃分原始數(shù)據(jù)集的方法相同,直到所有具有相同類型的數(shù)據(jù)均在一個(gè)數(shù)據(jù)子集內(nèi)。
創(chuàng)建分支的偽代碼函數(shù)createBranch()如下所示:
檢測數(shù)據(jù)集中的每個(gè)子項(xiàng)是否屬于同一分類: If so return 類標(biāo)簽 Else 尋找劃分?jǐn)?shù)據(jù)集的最好特征 劃分?jǐn)?shù)據(jù)集 創(chuàng)建分支節(jié)點(diǎn) for 每個(gè)劃分的子集 調(diào)整函數(shù)createBranch()并增加返回結(jié)果到分支節(jié)點(diǎn)中 return 分支節(jié)點(diǎn)
下面我們采用量化的方法來判定如何劃分?jǐn)?shù)據(jù),我們以下圖所示的數(shù)據(jù)集為例:
程序清單 3-1 計(jì)算給定數(shù)據(jù)集的香農(nóng)熵""" Created on Sep 16, 2018 @author: yufei """ # coding=utf-8 """ 計(jì)算給定數(shù)據(jù)的香農(nóng)熵 """ from math import log def calcShannonEnt(dataSet): numEntries = len(dataSet) labelCounts = {} # 為所有可能的分類創(chuàng)建字典 for featVec in dataSet: currentLabel = featVec[-1] if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0 labelCounts[currentLabel] += 1 shannonEnt = 0.0 # 以 2 為底求對(duì)數(shù) for key in labelCounts: prob = float(labelCounts[key])/numEntries shannonEnt -= prob * log(prob, 2) return shannonEnt """ 得到數(shù)據(jù)集 """ def createDataSet(): dataSet = [[1, 1, "yes"], [1, 1, "yes"], [1, 0, "no"], [0, 1, "no"], [0, 1, "no"],] labels = ["no surfacing", "flippers"] return dataSet, labels
在 python 提示符下,執(zhí)行代碼并得到結(jié)果:
>>> import trees >>> myDat, labels = trees.createDataSet() >>> myDat [[1, 1, "yes"], [1, 1, "yes"], [1, 0, "no"], [0, 1, "no"], [0, 1, "no"]] >>> trees.calcShannonEnt(myDat) 0.9709505944546686程序清單 3-2 按照給定特征劃分?jǐn)?shù)據(jù)集
# 參數(shù):待劃分的數(shù)據(jù)集、劃分?jǐn)?shù)據(jù)集的特征、需要返回的特征的值 def splitDataSet(dataSet, axis, value): # 為了不修改原始數(shù)據(jù)集,創(chuàng)建一個(gè)新的列表對(duì)象 retDataSet = [] for featVec in dataSet: # 將符合特征的數(shù)據(jù)抽取出來 # 當(dāng)我們按照某個(gè)特征劃分?jǐn)?shù)據(jù)集時(shí),就需要將所有符合要求的元素抽取出來 if featVec[axis] == value: reducedFeatVec = featVec[:axis] reducedFeatVec.extend(featVec[axis+1:]) retDataSet.append(reducedFeatVec) return retDataSet
測試函數(shù)splitDataSet(),在 python 提示符下,執(zhí)行代碼并得到結(jié)果:
>>> myDat, labels = trees.createDataSet() >>> myDat [[1, 1, "yes"], [1, 1, "yes"], [1, 0, "no"], [0, 1, "no"], [0, 1, "no"]] >>> trees.splitDataSet(myDat, 0, 0) [[1, "no"], [1, "no"]]程序清單 3-3 選擇最好的數(shù)據(jù)集劃分方式
""" 函數(shù)功能:選擇特征,劃分?jǐn)?shù)據(jù)集,計(jì)算得出最好的劃分?jǐn)?shù)據(jù)集的特征 數(shù)據(jù)集需滿足: 1、數(shù)據(jù)是一種由列表元素組成的列表,且所有的列表元素都要具有相同的數(shù)據(jù)長度 2、數(shù)據(jù)的最后一列或每個(gè)實(shí)例的最后一個(gè)元素是當(dāng)前實(shí)例的類別標(biāo)簽 """ def chooseBestFeatureToSplit(dataSet): # 判定當(dāng)前數(shù)據(jù)集包含多少特征屬性 numFeatures = len(dataSet[0]) - 1 # 計(jì)算整個(gè)數(shù)據(jù)集的原始香農(nóng)熵,即最初的無序度量值 baseEntropy = calcShannonEnt(dataSet) bestInfoGain = 0.0 bestFeatures = -1 # 遍歷數(shù)據(jù)集中的所有特征 for i in range(numFeatures): # 創(chuàng)建唯一的分類標(biāo)簽列表,將數(shù)據(jù)集中所有第 i 個(gè)特征值寫入這個(gè) list 中 featList = [example[i] for example in dataSet] # 從列表中創(chuàng)建集合來得到列表中唯一元素值 uniqueVals = set(featList) newEntropy = 0.0 # 遍歷當(dāng)前特征中的所有唯一屬性值,對(duì)每個(gè)唯一屬性值劃分一次數(shù)據(jù)集,計(jì)算數(shù)據(jù)集的新熵值 # 即計(jì)算每種劃分方式的信息熵 for value in uniqueVals: subDataSet = splitDataSet(dataSet, i, value) prob = len(subDataSet) / float(len(dataSet)) newEntropy += prob * calcShannonEnt(subDataSet) # 計(jì)算信息增益 infoGain = baseEntropy - newEntropy # 比較所有特征中的信息增益,返回最好特征劃分的索引值 if(infoGain > bestInfoGain): bestInfoGain = infoGain bestFeatures = i return bestFeatures
在 python 提示符下,執(zhí)行代碼并得到結(jié)果:
>>> myDat, labels = trees.createDataSet() >>> trees.chooseBestFeatureToSplit(myDat) 0 >>> myDat [[1, 1, "yes"], [1, 1, "yes"], [1, 0, "no"], [0, 1, "no"], [0, 1, "no"]]
代碼運(yùn)行結(jié)果告訴我們,第 0 個(gè)特征是最好的用于劃分?jǐn)?shù)據(jù)集的特征。也就是說第一個(gè)特征是 1 的放在一個(gè)組,第一個(gè)特征是 0 的放在另一個(gè)組。因?yàn)檫@個(gè)數(shù)據(jù)集比較簡單,我們直接觀察可以看到第一種劃分更好地處理了相關(guān)數(shù)據(jù)。
下面我們會(huì)介紹如何將上述實(shí)現(xiàn)的函數(shù)功能放在一起,構(gòu)建決策樹。
""" 使用分類名稱的列表,創(chuàng)建數(shù)據(jù)字典 返回出現(xiàn)次數(shù)最多的分類名稱 """ import operator def majorityCnt(classList): classCount = {} for vote in classList: if vote in classList: classCount[vote] = 0 classCount[vote] += 1 sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True) return sortedClassCount[0][0] # 參數(shù):數(shù)據(jù)集,標(biāo)簽列表 def createTree(dataSet, labels): # 創(chuàng)建名為 classList 的列表變量,包含了數(shù)據(jù)集的所有類標(biāo)簽 classList = [example[-1] for example in dataSet] # 遞歸函數(shù)的第一個(gè)停止條件:所有類標(biāo)簽完全相同,則直接返回該類標(biāo)簽 if classList.count(classList[0]) == len(classList): return classList[0] # 遞歸函數(shù)的第二個(gè)停止條件:使用完所有特征,仍然不能將數(shù)據(jù)集劃分成僅包含唯一類別的分組 # 由于無法簡單地返回唯一的類標(biāo)簽,這里遍歷完所有特征時(shí)使用 majorityCnt 函數(shù)返回出現(xiàn)次數(shù)最多的類別 if len(dataSet[0]) == 1: return majorityCnt(classList) # 當(dāng)前數(shù)據(jù)集選取的最好特征存儲(chǔ)在變量 bestFeat 中,得到列表包含的所有屬性值 bestFeat = chooseBestFeatureToSplit(dataSet) bestFeatLabel = labels[bestFeat] # 字典變量 myTree 存儲(chǔ)了樹的所有信息 myTree = {bestFeatLabel:{}} del(labels[bestFeat]) featValues = [example[bestFeat] for example in dataSet] uniqueVals = set(featValues) # 遍歷當(dāng)前選擇特征包含的所有屬性值 for value in uniqueVals: # 復(fù)制類標(biāo)簽,將其存儲(chǔ)在新列表變量 subLabels 中 # 在python語言中,函數(shù)參數(shù)是列表類型時(shí),參數(shù)是按照引用方式傳遞的 # 為了保證每次調(diào)用函數(shù) createTree 時(shí)不改變?cè)剂斜淼膬?nèi)容 subLabels = labels[:] # 在每個(gè)數(shù)據(jù)集劃分上遞歸的調(diào)用函數(shù) createTree() # 得到的返回值被插入字典變量 myTree 中 myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels) return myTree
在 python 提示符下,執(zhí)行代碼并得到結(jié)果:
>>> myDat, labels = trees.createDataSet() >>> myTree = trees.createTree(myDat, labels) >>> myTree {"no surfacing": {0: "no", 1: {"flippers": {0: "no", 1: "yes"}}}}
最后得到的變量myTree包含了很多代表樹結(jié)構(gòu)信息的嵌套字典。這棵樹包含了 3 個(gè)葉子節(jié)點(diǎn)以及 2 個(gè)判斷節(jié)點(diǎn),形狀如下圖所示:
不足之處,歡迎指正。
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/42450.html
摘要:本篇內(nèi)容為機(jī)器學(xué)習(xí)實(shí)戰(zhàn)第章利用元算法提高分類性能程序清單。將當(dāng)前錯(cuò)誤率與已有的最小錯(cuò)誤率進(jìn)行對(duì)比后,如果當(dāng)前的值較小,那么就在字典中保存該單層決策樹。上述,我們已經(jīng)構(gòu)建了單層決策樹,得到了弱學(xué)習(xí)器。 本篇內(nèi)容為《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》第 7 章利用 AdaBoost 元算法提高分類性能程序清單。所用代碼為 python3。 AdaBoost優(yōu)點(diǎn):泛化錯(cuò)誤率低,易編碼,可以應(yīng)用在大部分分類器上...
閱讀 2621·2021-11-25 09:43
閱讀 2724·2021-11-04 16:09
閱讀 1634·2021-10-12 10:13
閱讀 880·2021-09-29 09:35
閱讀 880·2021-08-03 14:03
閱讀 1777·2019-08-30 15:55
閱讀 2988·2019-08-28 18:14
閱讀 3489·2019-08-26 13:43