基于Python實(shí)現(xiàn)的ID3決策樹功能示例
本文實(shí)例講述了基于Python實(shí)現(xiàn)的ID3決策樹功能。分享給大家供大家參考,具體如下:
ID3算法是決策樹的一種,它是基于奧卡姆剃刀原理的,即用盡量用較少的東西做更多的事。ID3算法,即Iterative Dichotomiser 3,迭代二叉樹3代,是Ross Quinlan發(fā)明的一種決策樹算法,這個(gè)算法的基礎(chǔ)就是上面提到的奧卡姆剃刀原理,越是小型的決策樹越優(yōu)于大的決策樹,盡管如此,也不總是生成最小的樹型結(jié)構(gòu),而是一個(gè)啟發(fā)式算法。
如下示例是一個(gè)判斷海洋生物數(shù)據(jù)是否是魚類而構(gòu)建的基于ID3思想的決策樹
# coding=utf-8 import operator from math import log import time def createDataSet(): dataSet = [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no'], [0,0,'maybe']] labels = ['no surfaceing', 'flippers'] return dataSet, labels # 計(jì)算香農(nóng)熵 def calcShannonEnt(dataSet): numEntries = len(dataSet) labelCounts = {} for feaVec in dataSet: currentLabel = feaVec[-1] if currentLabel not in labelCounts: labelCounts[currentLabel] = 0 labelCounts[currentLabel] += 1 shannonEnt = 0.0 for key in labelCounts: prob = float(labelCounts[key]) / numEntries shannonEnt -= prob * log(prob, 2) return shannonEnt 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 chooseBestFeatureToSplit(dataSet): numFeatures = len(dataSet[0]) - 1 # 因?yàn)閿?shù)據(jù)集的最后一項(xiàng)是標(biāo)簽 baseEntropy = calcShannonEnt(dataSet) bestInfoGain = 0.0 bestFeature = -1 for i in range(numFeatures): featList = [example[i] for example in dataSet] uniqueVals = set(featList) newEntropy = 0.0 for value in uniqueVals: 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 # 因?yàn)槲覀冞f歸構(gòu)建決策樹是根據(jù)屬性的消耗進(jìn)行計(jì)算的,所以可能會(huì)存在最后屬性用完了,但是分類 # 還是沒有算完,這時(shí)候就會(huì)采用多數(shù)表決的方式計(jì)算節(jié)點(diǎn)分類 def majorityCnt(classList): classCount = {} for vote in classList: if vote not in classCount.keys(): classCount[vote] = 0 classCount[vote] += 1 return max(classCount) def createTree(dataSet, labels): classList = [example[-1] for example in dataSet] if classList.count(classList[0]) == len(classList): # 類別相同則停止劃分 return classList[0] if len(dataSet[0]) == 1: # 所有特征已經(jīng)用完 return majorityCnt(classList) bestFeat = chooseBestFeatureToSplit(dataSet) bestFeatLabel = labels[bestFeat] myTree = {bestFeatLabel: {}} del (labels[bestFeat]) featValues = [example[bestFeat] for example in dataSet] uniqueVals = set(featValues) for value in uniqueVals: subLabels = labels[:] # 為了不改變原始列表的內(nèi)容復(fù)制了一下 myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels) return myTree def main(): data, label = createDataSet() t1 = time.clock() myTree = createTree(data, label) t2 = time.clock() print myTree print 'execute for ', t2 - t1 if __name__ == '__main__': main()
運(yùn)行結(jié)果如下:
{'no surfaceing': {0: {'flippers': {0: 'maybe', 1: 'no'}}, 1: {'flippers': {0: 'no', 1: 'yes'}}}} execute for 0.0103958394532
最后我們測試一下這個(gè)腳本即可,如果想把這個(gè)生成的決策樹用圖像畫出來,也只是在需要在腳本里面定義一個(gè)plottree的函數(shù)即可。
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
python里使用正則的findall函數(shù)的實(shí)例詳解
這篇文章主要介紹了python里使用正則的findall函數(shù)的實(shí)例詳解的相關(guān)資料,希望通過本文能幫助到大家,需要的朋友可以參考下2017-10-10Python 繪制北上廣深的地鐵路線動(dòng)態(tài)圖
這篇文章主要介紹了用python制作北上廣深——地鐵線路動(dòng)態(tài)圖,文中的示例代碼講解詳細(xì),對(duì)我們的工作或?qū)W習(xí)都有一定的價(jià)值,感興趣的同學(xué)可以學(xué)習(xí)一下2021-12-12使用Python實(shí)現(xiàn)批量修改文件的修改日期功能
在日常的文件管理中,您可能需要批量修改文件的修改日期,比如,您可能希望將某個(gè)文件夾中的所有文件的修改日期隨機(jī)設(shè)置為6到8月份之間的日期,這在數(shù)據(jù)整理中可能非常有用,本文將詳細(xì)介紹如何使用Python實(shí)現(xiàn)這一功能,需要的朋友可以參考下2024-10-10Python可變參數(shù)會(huì)自動(dòng)填充前面的默認(rèn)同名參數(shù)實(shí)例
今天小編就為大家分享一篇Python可變參數(shù)會(huì)自動(dòng)填充前面的默認(rèn)同名參數(shù)實(shí)例,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-11-11