本文實例講述了決策樹的python實現方法。分享給大家供大家參考。具體實現方法如下：
決策樹算法優缺點：
優點：計算復雜度不高，輸出結果易于理解，對中間值缺失不敏感，可以處理不相關的特征數據
缺點：可能會產生過度匹配的問題
適用數據類型：數值型和標稱型
算法思想：
1.決策樹構造的整體思想：
決策樹說白了就好像是if-else結構一樣，它的結果就是你要生成這個一個可以從根開始不斷判斷選擇到葉子節點的樹，但是呢這里的if-else必然不會是讓我們認為去設置的，我們要做的是提供一種方法，計算機可以根據這種方法得到我們所需要的決策樹。這個方法的重點就在于如何從這么多的特征中選擇出有價值的，并且按照最好的順序由根到葉選擇。完成了這個我們也就可以遞歸構造一個決策樹了
2.信息增益
劃分數據集的最大原則是將無序的數據變得更加有序。既然這又牽涉到信息的有序無序問題，自然要想到想弄的信息熵了。這里我們計算用的也是信息熵（另一種方法是基尼不純度）。公式如下：
數據需要滿足的要求：
① 數據必須是由列表元素組成的列表，而且所有的列白哦元素都要具有相同的數據長度
② 數據的最后一列或者每個實例的最后一個元素應是當前實例的類別標簽
函數：
calcShannonEnt(dataSet)
計算數據集的香農熵，分兩步，第一步計算頻率，第二部根據公式計算香農熵
splitDataSet(dataSet, aixs, value)
劃分數據集，將滿足X[aixs]==value的值都劃分到一起，返回一個劃分好的集合（不包括用來劃分的aixs屬性，因為不需要）
chooseBestFeature(dataSet)
選擇最好的屬性進行劃分，思路很簡單就是對每個屬性都劃分下，看哪個好。這里使用到了一個set來選取列表中唯一的元素，這是一中很快的方法
majorityCnt(classList)
因為我們遞歸構建決策樹是根據屬性的消耗進行計算的，所以可能會存在最后屬性用完了，但是分類還是沒有算完，這時候就會采用多數表決的方式計算節點分類
createTree(dataSet, labels)
基于遞歸構建決策樹。這里的label更多是對于分類特征的名字，為了更好看和后面的理解。
#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']]
??? labels = ['no surfaceing','flippers']
??? return dataSet, labels
#計算香農熵
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#因為數據集的最后一項是標簽
??? 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
???????????
#因為我們遞歸構建決策樹是根據屬性的消耗進行計算的，所以可能會存在最后屬性用完了，但是分類
#還是沒有算完，這時候就會采用多數表決的方式計算節點分類
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:#所有特征已經用完
??????? 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[:]#為了不改變原始列表的內容復制了一下
??????? 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()
希望本文所述對大家的Python程序設計有所幫助。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
