最近刚把《机器学习实战》中的决策树过了一遍，接下来通过书中的实例，来温习决策树构造算法中的ID3算法。
海洋生物数据：
| 不浮出水面是否可以生存 | 是否有脚蹼 | 属于鱼类 | |
| 1 | 是 | 是 | 是 |
| 2 | 是 | 是 | 是 |
| 3 | 是 | 否 | 否 |
| 4 | 否 | 是 | 否 |
| 5 | 否 | 是 | 否 |
转换成数据集：
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
一、基础知识
1、熵
我把它简单的理解为用来度量数据的无序程度。数据越有序，熵值越低；数据越混乱或者分散，熵值越高。所以数据集分类后标签越统一，熵越低；标签越分散，熵越高。
更理论一点的解释：
熵被定义为信息的期望值，而如何理解信息？如果待分类的事物可能划分在多个分类中，则符号的信息定义为：
其中xi是选择该分类的概率，即 该类别个数 / 总个数。
为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，公式如下：
计算给定数据集的香农熵：
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
运行代码，数据集myDat1只有两个类别，myDat2有三个类别：
>>> myDat1
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
>>> trees.calcShannonEnt(myDat1)
0.9709505944546686
>>> myDat2
[[1, 1, 'maybe'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
>>> trees.calcShannonEnt(myDat2)
1.3709505944546687
2、信息增益
信息增益可以衡量划分数据集前后数据（标签）向有序性发展的程度。
信息增益=原数据香农熵-划分数据集之后的新数据香农熵
二、按给定特征划分数据集
三个输入参数：待划分的数据集、划分数据集的特征位置、需要满足的当前特征的值
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
运行结果：
>>> myDat
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
>>> trees.splitDataSet(myDat,0,1)
[[1, 'yes'], [1, 'yes'], [0, 'no']]
>>> trees.splitDataSet(myDat,0,0)
[[1, 'no'], [1, 'no']]
三、选择最好的数据集划分方式，即选择出最合适的特征用于划分数据集
def chooseBestFeatureToSplit(dataSet): # 计算出数据集的特征个数 numFeatures = len(dataSet[0]) – 1 # 算出原始数据集的香农熵 baseEntropy = calcShannonEnt(dataSet) bestInfoGain = 0.0; bestFeature = -1 for i in range(numFeatures): # 抽取出数据集中所有第i个特征 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 sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True) return sortedClassCount[0][0]
五、创建决策树
接下来我们将利用上面学习的单元模块创建决策树。
def createTree(dataSet,labels): classList = [example[-1] for example in dataSet] # 如果划分的数据集只有一个类别，则返回此类别 if classList.count(classList[0]) == len(classList): return classList[0] # 如果使用完所有特征属性之后，类别标签仍不唯一，则使用majorityCnt函数，多数表决法，哪种类别标签多，则分为此类别 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
每次遇到递归问题总会头脑发昏，为了便于理解，我把一个创建决策树的处理过程重头到尾梳理了一遍。
原始数据集:
dataset: [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
labels: [no surfacing, flippers]
在调用createTree(dataSet,labels)函数之后，数据操作如下（每一个色块代表一次完整的createTree调用过程）：
| 1、 dataset: [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']] labels: [no surfacing, flippers]
classList=['yes', 'yes', 'no', 'no', 'no'] 选择最好的特征来分类：bestFeat= 0 bestFeatLabel =no surfacing
构造树：myTree {'no surfacing': {}}
去除这个特征后，label=['flippers']
这个特征（no surfacing）的值：featValues= [1, 1, 1, 0, 0] 特征类别 uniqueVals=[0, 1]
（1）类别值为0的时候： 子标签=['flippers'] 分出的子集 splitDataSet(dataSet, bestFeat, value) = [[1, 'no'], [1, 'no']] myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
myTree[bestFeatLabel][0] =’no’ myTree[bestFeatLabel] {0: 'no'} 也就是myTree {'no surfacing': {0: 'no'}}
（2）类别值为1的时候： 子标签=['flippers'] 分出的子集 splitDataSet(dataSet, bestFeat, value) = [[1, 'yes'], [1, 'yes'], [0, 'no']] myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
myTree[bestFeatLabel][1] ={'flippers': {0: 'no', 1: 'yes'}} myTree[bestFeatLabel] {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}} 也就是myTree: {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}} |
例子中的决策树可视化图：
六、使用决策树做分类
def classify(inputTree, featLabels, testVec): firstStr = inputTree.keys()[0] secondDict = inputTree[firstStr] featIndex = featLabels.index(firstStr) for key in secondDict.keys(): if testVec[featIndex] == key: if type(secondDict[key]).__name__=='dict': classLabel = classify(secondDict[key], featLabels, testVec) else: classLabel = secondDict[key] return classLabel
输出结果：
>>> myTree
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
>>> labels
['no surfacing', 'flippers']
>>> trees.classify(myTree,labels,[1,0])
'no'
>>> trees.classify(myTree,labels,[1,1])
'yes'
七、 决策树的存储
构造决策树是很耗时的任务，然而用创建好的决策树解决分类问题，则可以很快的完成，可以通过使用pickle模块存储决策树。
def storeTree(inputTree, filename): import pickle fw = open(filename,'w') pickle.dump(inputTree,fw) fw.close() def grabTree(filename): import pickle fr = open(filename) return pickle.load(fr)
参考资料：
[1] 《机器学习实战》
[2] 《机器学习实战》笔记——决策树（ID3）https://www.cnblogs.com/DianeSoHungry/p/7059104.html