Python实现ID3【决策树】

糖逗

参考书籍：《机器学习实战》

1. import numpy as np
   
2. import operator
   
3. import matplotlib.pyplot as plt
   
4. from math import log
   
5. 
   
6. def calcShannonEnt(dataSet):
   
7.     numEntries = len(dataSet)
   
8.     labelCounts = {}
   
9.     for featVec in dataSet:
   
10.         currentLabel = featVec[-1]
    
11.         if currentLabel not in labelCounts.keys():
    
12.             labelCounts[currentLabel] = 0
    
13.         labelCounts[currentLabel] += 1
    
14.     shannonEnt = 0
    
15.     for key in labelCounts:
    
16.         prob = float(labelCounts[key]) / numEntries
    
17.         shannonEnt -= prob * log(prob, 2)#以2为底数
    
18.     return shannonEnt
    
19. 
    
20. #根据特征划分数据集
    
21. def splitDataSet(dataSet, axis, value):
    
22.     retDataSet = []
    
23.     for featVec in dataSet:
    
24.         if featVec[axis] == value:
    
25.             reduceFeatVec = featVec[:axis]#不包括axis
    
26.             reduceFeatVec.extend(featVec[axis + 1 :])
    
27.             retDataSet.append(reduceFeatVec)
    
28.     return retDataSet
    
29. 
    
30. #选择最好的数据集划分方式
    
31. def chooseBestFeatureToSplit(dataSet):
    
32.     numFeatures = len(dataSet[0]) - 1
    
33.     baseEntropy = calcShannonEnt(dataSet)
    
34.     bestInfoGain = 0
    
35.     bestFeature = -1
    
36.     for i in range(numFeatures):#每个特征单独计算
    
37.         featList = [example[i] for example in dataSet]
    
38.         uniqueVals = set(featList)
    
39.         newEntropy = 0
    
40.         for value in uniqueVals:
    
41.             subDataSet = splitDataSet(dataSet, i, value)
    
42.             prob = len(subDataSet) / float(len(dataSet))
    
43.             newEntropy += prob * calcShannonEnt(subDataSet)
    
44.         infoGain = baseEntropy - newEntropy
    
45.         if(infoGain > bestInfoGain):
    
46.             bestInfoGain = infoGain
    
47.             bestFeature = i
    
48.     return bestFeature
    
49. 
    
50. #数据集已经处理了所有特征，但类标签依然不是唯一的，采用多数表决的方法确定返回的类
    
51. def majorityCnt(classList):
    
52.     classCount = {}
    
53.     for vote in classList:
    
54.         if vote not in classCount.keys():
    
55.             classCount[vote] = 0
    
56.         classCount[vote] += 1
    
57.     sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1),
    
58.                               reverse = True)
    
59.     return sortedClassCount[0][0]
    
60. 
    
61. #创建树的代码（递归）
    
62. def createTree(dataSet, labels):
    
63.     classList = [example[-1] for example in dataSet]
    
64.     if classList.count(classList[0]) == len(classList):#count()方法用于统计某个元素在列表中出现的次数。
    
65.         return classList[0]
    
66.     if len(dataSet[0]) == 1:
    
67.         return majorityCnt(classList)
    
68.     bestFeat = chooseBestFeatureToSplit(dataSet)
    
69.     bestFeatLabel = labels[bestFeat]
    
70.     myTree = {bestFeatLabel:{}}
    
71.     del(labels[bestFeat])
    
72.     featValues = [example[bestFeat] for example in dataSet]
    
73.     uniqueVals = set(featValues)
    
74.     for value in uniqueVals:
    
75.         subLabels = labels[:]
    
76.         myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),
    
77.               subLabels)
    
78.     return myTree
    
79. 
    
80. def classify(inputTree, featLabels, testVec):
    
81.     firstStr = list(inputTree.keys())[0]
    
82.     secondDict = inputTree[firstStr]
    
83.     featIndex = featLabels.index(firstStr)
    
84.     for key in secondDict.keys():
    
85.         if testVec[featIndex] == key:
    
86.             if type(secondDict[key]).__name__ == "dict":#如果是字典的话，接着向下找
    
87.                 classLabel = classify(secondDict[key], featLabels, testVec)
    
88.             else:
    
89.                 classLabel = secondDict[key]
    
90.     return classLabel
    
91. 
    
92. if __name__ == '__main__':
    
93.     dataSet = [[1, 1, "yes"],     
    
94.                [1, 1, "yes"],
    
95.                [1, 0, "no"],
    
96.                [0, 1, "no"],
    
97.                [0, 1, "no"]]
    
98.     labels = ["no surfacing", "flippers"]
    
99.     tree = createTree(dataSet, labels)
    
100.     labels = ["no surfacing", "flippers"]#因为createTree阶段会删除labels中的值
     
101.     res = classify(tree, labels, [1, 1])
     
102.     print(res)
     

复制代码

糖逗

递归