3.1決策樹構造

#3-1計算給定資料集的香農熵
from math import log
def calcShannonEnt(dataSet):
    numEntries = len(dataSet):
    labelCounts = {}
    for featVec in dataSet:
        currentLabel = featVec[-1]#選取最後一列資料作為标簽
        if currentLabel not in labelCounts.keys():
            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 createDataSet():
    dataSet = [[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]
    labels = ['no surfacing','flippers']
    return dataSet,labels
#3-2按照給定特征劃分資料集
def splitDataSet(dataSet, axis, value):#待劃分的資料集、劃分資料集的特征、需要傳回的特征值
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reduceFeatVec = featVec[:axis]  #這一行和下一行整體的功能就是删除這一行
            reduceFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reduceFeatVec)#将這些特征值加到建立的list中
    return retDataSet
           

keys()函數：将字典轉化為清單函數。建立一個資料字典，它的鍵值是最後一列的數值。

在第二個函數中，python語言在函數中傳遞的是清單的引用，在函數内部對清單對象的修改，将會影響該清單對象的整個生存周期。為了消除這個不良影響，我們需要在函數的開始聲明一個新清單的對象。

#3-3選擇最好的資料集劃分方式
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
           

在函數中調用的資料需要滿足一定的要求：1.資料必須是一種由清單元素組成的清單，而且所有的清單元素都要具有相同的資料長度。

2.資料的最後一列或者每個執行個體的最後一個元素是目前執行個體的類别标簽。

資料集一旦滿足上述要求，我們就可以在函數的第一行判定目前資料集包含多少類别标簽。

[example[i] for example in  dataSet]是什麼意思？

https://blog.csdn.net/jiangsujiangjiang/article/details/84313227

我的了解：在dataSet中逐行周遊，example[i]中的i就是提取每一個行中第i+1個元素。

set()函數：用來建立集合。建立空集合，必須使用set()而不是{}，{}用于建立空字典。

#挑選次數最多的類别
def majorituCnt(classList):
    classCount = {}
    for vote in classList:
        if vote in classCount.keys():classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]
#3-4建立樹的函數代碼
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:# 如果資料集隻有1列，那麼最初出現label次數最多的一類，作為結果
        return majorituCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)#傳回的是數字
    bestFeatLabel = labels[bestFeat]
    mytree = {bestFeatLabel:{}}
    del(labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]# 取出最優列，然後它的branch做分類
    uniqueVals = set(featValues)#将清單變為元組
    for value in uniqueVals:
        subLabels = labels[:]# 求出剩餘的标簽label
        mytree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
        # 周遊目前選擇特征包含的所有屬性值，在每個資料集劃分上遞歸調用函數createTree()
    return  mytree
           

count()函數：計算某個元素在清單中出現的次數

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
           

上面是需要分類的各個類别，下面進行測試：

myDat,labels = createDataSet()
Tree = createTree(myDat,labels)
print(Tree)
           

顯示出我們需要的樹結構。