基于Python實現(xiàn)的ID3決策樹功能示例
本文實例講述了基于Python實現(xiàn)的ID3決策樹功能。分享給大家供大家參考,具體如下:
ID3算法是決策樹的一種,它是基于奧卡姆剃刀原理的,即用盡量用較少的東西做更多的事。ID3算法,即Iterative Dichotomiser 3,迭代二叉樹3代,是Ross Quinlan發(fā)明的一種決策樹算法,這個算法的基礎(chǔ)就是上面提到的奧卡姆剃刀原理,越是小型的決策樹越優(yōu)于大的決策樹,盡管如此,也不總是生成最小的樹型結(jié)構(gòu),而是一個啟發(fā)式算法。
如下示例是一個判斷海洋生物數(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 # 計算香農(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 # 因為數(shù)據(jù)集的最后一項是標簽 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 # 因為我們遞歸構(gòu)建決策樹是根據(jù)屬性的消耗進行計算的,所以可能會存在最后屬性用完了,但是分類 # 還是沒有算完,這時候就會采用多數(shù)表決的方式計算節(jié)點分類 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()
運行結(jié)果如下:
{'no surfaceing': {0: {'flippers': {0: 'maybe', 1: 'no'}}, 1: {'flippers': {0: 'no', 1: 'yes'}}}} execute for 0.0103958394532
最后我們測試一下這個腳本即可,如果想把這個生成的決策樹用圖像畫出來,也只是在需要在腳本里面定義一個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īng)典教程》
希望本文所述對大家Python程序設(shè)計有所幫助。
相關(guān)文章
python里使用正則的findall函數(shù)的實例詳解
這篇文章主要介紹了python里使用正則的findall函數(shù)的實例詳解的相關(guān)資料,希望通過本文能幫助到大家,需要的朋友可以參考下2017-10-10Python可變參數(shù)會自動填充前面的默認同名參數(shù)實例
今天小編就為大家分享一篇Python可變參數(shù)會自動填充前面的默認同名參數(shù)實例,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2019-11-11