一.决策树的构造

image.png

image.png

  1. from __future__ import print_function
  2. print(__doc__)
  3. import operator
  4. from math import log
  5. import decisionTreePlot as dtPlot
  6. from collections import Counter
  8. def createDataSet():
  9.     labels = ['no surfacing', 'flippers']
  10.     return dataSet, labels
  11. def calcShannonEnt(dataSet):
  12.     numEntries = len(dataSet)
  13.     labelCounts = {}
  14.     for featVec in dataSet:
  15.         currentLabel = featVec[-1]
  16.         if currentLabel not in labelCounts.keys():
  17.             labelCounts[currentLabel] = 0
  18.         labelCounts[currentLabel] += 1
  19.     # 对于label标签的占比，求出label标签的香农熵
  20.     shannonEnt = 0.0
  21.     for key in labelCounts:
  22.         prob = float(labelCounts[key])/numEntries
  23.         shannonEnt -= prob * log(prob, 2)
  24.     return shannonEnt
  27. def splitDataSet(dataSet, index, value):
  28.     retDataSet = []
  29.     for featVec in dataSet: 
  30.         if featVec[index] == value:
  31.             reducedFeatVec = featVec[:index]
  32.             reducedFeatVec.extend(featVec[index+1:])
  33.             retDataSet.append(reducedFeatVec)
  34.     return retDataSet
  37. def chooseBestFeatureToSplit(dataSet):
  38.     numFeatures = len(dataSet[0]) - 1
  39.     baseEntropy = calcShannonEnt(dataSet)
  40.     bestInfoGain, bestFeature = 0.0, -1
  41.     for i in range(numFeatures):
  42.         featList = [example[i] for example in dataSet]
  43.         uniqueVals = set(featList)
  44.         newEntropy = 0.0
  45.         for value in uniqueVals:
  46.             subDataSet = splitDataSet(dataSet, i, value)
  47.             prob = len(subDataSet)/float(len(dataSet))
  48.             newEntropy += prob * calcShannonEnt(subDataSet)
  49.         infoGain = baseEntropy - newEntropy
  50.         print('infoGain=', infoGain, 'bestFeature=', i, baseEntropy, newEntropy)
  51.         if (infoGain > bestInfoGain):
  52.             bestInfoGain = infoGain
  53.             bestFeature = i
  54.     return bestFeature
  55. def majorityCnt(classList):
  56.     classCount = {}
  57.     for vote in classList:
  58.         if vote not in classCount.keys():
  59.             classCount[vote] = 0
  60.         classCount[vote] += 1
  61.     sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
  62.     return sortedClassCount[0][0]
  63. def createTree(dataSet, labels):
  64.     classList = [example[-1] for example in dataSet]
  65.     if classList.count(classList[0]) == len(classList):
  66.         return classList[0]
  67.     if len(dataSet[0]) == 1:
  68.         return majorityCnt(classList)
  69.     bestFeat = chooseBestFeatureToSplit(dataSet)
  70.     bestFeatLabel = labels[bestFeat]
  71.     myTree = {bestFeatLabel: {}}
  72.     del(labels[bestFeat])
  73.     featValues = [example[bestFeat] for example in dataSet]
  74.     uniqueVals = set(featValues)
  75.     for value in uniqueVals:
  76.         subLabels = labels[:]
  77.         myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
  78.     return myTree
  79. def classify(inputTree, featLabels, testVec):
  80.     firstStr = inputTree.keys()[0]
  81.     secondDict = inputTree[firstStr]
  82.     featIndex = featLabels.index(firstStr)
  83.     key = testVec[featIndex]
  84.     valueOfFeat = secondDict[key]
  85.     print('+++', firstStr, 'xxx', secondDict, '---', key, '>>>', valueOfFeat)
  86.     if isinstance(valueOfFeat, dict):
  87.         classLabel = classify(valueOfFeat, featLabels, testVec)
  88.     else:
  89.         classLabel = valueOfFeat
  90.     return classLabel
  93. def storeTree(inputTree, filename):
  94.     import pickle
  95.     fw = open(filename, 'wb')
  96.     pickle.dump(inputTree, fw)
  97.     fw.close()
  98.     with open(filename, 'wb') as fw:
  99.         pickle.dump(inputTree, fw)
  102. def grabTree(filename):
  103.     import pickle
  104.     fr = open(filename,'rb')
  105.     return pickle.load(fr)
  108. def fishTest():
  109.     import copy
  110.     myTree = createTree(myDat, copy.deepcopy(labels))
  111.     print(myTree)
  112.     print(classify(myTree, labels, [1, 1]))
  114.     # 获得树的高度
  115.     print(get_tree_height(myTree))
  117.     # 画图可视化展现
  118.     dtPlot.createPlot(myTree)
  121. def ContactLensesTest():
  122.     fr = open('data/3.DecisionTree/lenses.txt')
  123.     lenses = [inst.strip().split('\t') for inst in fr.readlines()]
  124.     lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']
  125.     lensesTree = createTree(lenses, lensesLabels)
  126.     print(lensesTree)
  127.     # 画图可视化展现
  128.     dtPlot.createPlot(lensesTree)
  131. def get_tree_height(tree):
  132.     if not isinstance(tree, dict):
  133.         return 1
  135.     child_trees = tree.values()[0].values()
  137.     # 遍历子树, 获得子树的最大高度
  138.     max_height = 0
  139.     for child_tree in child_trees:
  140.         child_tree_height = get_tree_height(child_tree)
  142.         if child_tree_height > max_height:
  143.             max_height = child_tree_height
  145.     return max_height + 1
  148. if __name__ == "__main__":
  149.     fishTest()
  150.     # ContactLensesTest()