机器学习实战之 决策树——ID3算法
决策树的含义
所谓决策树，顾名思义，是一种树，一种依托于策略抉择而建立起来的树。机器学习中，决策树是一个预测模型；它代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的是某个可能的属性值，而每个叶子节点则对应根节点到该叶子节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同的输出。
从数据产生决策树的机器学习技术叫做决策树学习，通俗点就是决策树，是一种依托于分类、训练上的预测树，根据已知预测、归类未来。
二、ID3算法
ID3算法是一个由RossQuinlan发明的用于决策树的算法。这个算法便是建立在奥卡姆剃刀的基础上：越是小型的决策树越优于大的决策树。尽管如此，该算法也不是总是生成最小的树形结构，而是一个启发式算法。
汤姆米歇尔《机器学习》中对ID3算法的描述：
ID3算法思想描述：
1) 对当前例子集合，计算属性的信息增益；
2) 选择信息增益大的属性A
3) 把在A处取值相同的例子归于同意子集，A取几个值就得几个子集
4) 依次对每种取值情况下的子集，返回1）递归调用建树算法，
5) 若子集中只含有单个属性，则分支为叶子节点，判断其属性值并标上相应的符号，然后返回调用处。
二、如何确定最佳分类属性
1、信息增益的度量标准：熵
在ID3算法中，是通过信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。在ID3算法中，核心问题就是选取在树的每个结点要测试的属性。为了精确的定义信息增益，我们先定义信息论中广发使用的一个度量标准，称为熵，它刻画了任意样例集合的纯度。计算公式为
其中， 是样例集合中的样例， 是样例 出现的概率。python语言计算信息熵如下：
def calcShannonEnt(dataSet):#输入训练数据集
numEntries = len(dataSet)#计算训练数据集中样例的数量
labelCounts = {}
for featVec in dataSet:
currentLabel = featVec[-1]#获取数据集的标签
if currentLabel notin labelCounts.keys():
labelCounts[currentLabel]=0
labelCounts[currentLabel]+=1 #当前标签实例数+1
shannonEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key])/numEntries
shannonEnt -= prob *log(prob,2)#计算信息熵
return shannonEnt
信息论中对熵的一种解释，熵确定了要编码集合S中任意成员的分类所需要的最少二进制位数。更一般的，如果目标属性具有n个不同的值，那么S相对于n个状态的熵定义为：
Pi为子集合中不同性的样例的比例。
根据上述公式，我们可以得到：S的所有成员属于同一类，H=0；S的正反样例数量相等，H=1；S的正反样例的数量不相等，正处于0/1之间，如下图所示：
2、信息增益度量期望的熵降低
信息熵Gain(S,A)定义
已经有了熵作为衡量训练样例集合纯度的标准，现在可以定义属性分类训练数据的效力度量标准。这个标准称为“信息增益”。简单的说，一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低。更精确的讲，一个属性A相对于样本集合S的信息增益Gain(S,A)被定义为：
其中Values(A)是属性A所有可能
ID3，算法就是每次找信息增益最大的属性，然后进行划分。
def splitDataSet(dataSet,axis,value):#划分属性，获得去掉axis位置的属性value剩下的样本
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value :
reduceFeatVec = featVec[:axis]
reduceFeatVec.extend(featVec[axis+1:])#extend()方法接受一个列表作为参数，并将该参数的每个元素都添加到原有的列表中
retDataSet.append(reduceFeatVec)#append()方法向列表的尾部添加一个新的元素，只接受一个参数。
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 mahorityCnt(classList):#计算最大所属类别
classCount = {}
for vote in classList:
if vote not in classCount.keys():
classCount[vote]=0
classCount[vote]+=1
sortedClassCount = sorted(classCount.items(),key=operator.getitem(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]
if len(dataSet[0])==1:#只有类别列，没有属性列
return mahorityCnt(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 classify(myTree,featLabels,testVec):#对未分类数据进行分类
firstStr = list(myTree.keys())[0]#获得key
secodDict = myTree[firstStr]
featIndex = featLabels.index(firstStr)
for key in secodDict.keys():
if testVec[featIndex] == key:
if str(type(secodDict[key])) == "<class 'dict'>":
classLabel = classify(secodDict[key],featLabels,testVec)
else:
classLabel = secodDict[key]
return classLabel