1 决策树
在机器学习这个层面，将所要处理的数据看做是树的根，相应的选取数据的特征作为一个个节点（决策点），每次选取一个节点将数据集分为不同的数据子集，可以看成对树进行分支，这里体现出了决策，直到最后无法可分停止，也就是分支上的数据为同一类型，可以想象一次 次划分之后由根延伸出了许多分支，形象的说就是一棵树。
在机器学习中，决策树是一个预测模型，它代表的是对象属性与对象值之间的一种映射关系，我们可以利用决策树发现数据内部所蕴含的知识，比如在本文的最后我们选取隐形眼镜数据集根据决策树学习到眼科医生是如何判断患者佩戴眼镜片的过程，而 K 近邻算法虽与决策树同属分类，却无从得知数据的内在形式。
2 构建决策树
在构造决策树首先需要选取特征将原始数据划分为几个数据集，那么第一个问题就是当前数据的哪个特征在划分数据分类时起决定性作用，所以必须评估每个特征。进而通过特征将原始数据就被划分为几个数据子集，这些数据子集分布在第一个决策点的所有分支上，如果分支上的所有数据为同一类型，则划分停止，若分支上的所有数据不是同一类型，则还需要继续划分，直到所有具有相同类型的数据均在一个数据子集中。在用决策树进行划分时，关键是每次划分时选取哪个特征进行划分，在划分数据时，我们必须采用 量化的方法判断如何划分数据。
划分数据时是根据某一原则进行划分，使得划分在同一集合中的数据具有共同的特征， 据此，我们可以理解为划分数据的原则就是是无序的数据变得有序。当然划分数据有很多种 方法，在此选用信息论度量信息，划分组织杂乱无章的数据。 信息论是量化处理信息的分支科学，可以在数据划分之前或之后使用信息论量化度量信 息的内容。其中在划分数据集之前之后信息发生的变化称为信息增益，计算每个特征值划分 数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。
首先我们需要知道怎么计算信息增益，集合信息的度量方式称为香农熵或者简称为熵， 熵定义为信息的期望值，那么信息是什么？ xi的信息可定义为：L(xi) = -log(p(xi)),其中 p(xi)是选择该分类的概率。熵指的是所有类别所有可能值包含的信息期望值，可表示为：
熵越高，表明混合的数据越多，则可以在数据集中添加更多的分类。基于上述的分析， 编程计算给定数据集的香农熵，代码如下：
代码语言：javascript复制 from math import log
###计算香农熵(为 float 类型）
def calShang(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 creatDataSet():
dataSet = [[1,1,'yes'],
[1,1,'yes'],
[1,0,'no'],
[0,1,'no'],
[0,1,'no']]
labels = ['no surfacing','flippers']
return dataSet,labels ''' #测试
myData,labels = creatDataSet()
print("原数据为：",myData)
print("标签为：",labels)
shang = calShang(myData)
print("香农熵为：",shang) '''
得到熵之后，我们就可以按照获取最大增益的办法划分数据集。
基于之前的分析，信息增益表示的是信息的变化，而信息可以用熵来度量，所以我们可 以用熵的变化来表示信息增益。而获得最高信息增益的特征就是最好的选择，故此，我们可以对所有特征遍历，得到最高信息增益的特征加以选择。 首先，我们按照给定特征划分数据集并进行简单的测试：
代码语言：javascript复制 ###划分数据集（以指定特征将数据进行划分）
def splitDataSet(dataSet,feature,value):##传入待划分的数据集、划分数据集的特征以及需 要返回的特征的值
newDataSet = []
for featVec in dataSet:
if featVec[feature] == value:
reducedFeatVec = featVec[:feature] reducedFeatVec.extend(featVec[feature 1:]) newDataSet.append(reducedFeatVec)
return newDataSet''' #测试
myData,labels = creatDataSet()
print("原数据为：",myData)
print("标签为：",labels)
split = splitDataSet(myData,0,1)
print("划分后的结果为:",split) '''
接下来我们遍历整个数据集，循环计算香农熵和 splitDataSet()函数，找到最好的划分方 式并简单测试：
代码语言：javascript复制 ##选择最好的划分方式(选取每个特征划分数据集，从中选取信息增益最大的作为最优 划分)在这里体现了信息增益的概念 def chooseBest(dataSet):
featNum = len(dataSet[0]) - 1
baseEntropy = calShang(dataSet)
bestInforGain = 0.0
bestFeat = -1##表示最好划分特征的下标
for i in range(featNum):
featList = [example[i] for example in dataSet] #列表
uniqueFeat = set(featList)##得到每个特征中所含的不同元素
newEntropy = 0.0
for value in uniqueFeat:
subDataSet = splitDataSet(dataSet,i,value)
prob = len(subDataSet) / len(dataSet)
newEntropy = prob * calShang(subDataSet)
inforGain = baseEntropy - newEntropy
if (inforGain > bestInforGain):
bestInforGain = inforGain
bestFeature = i#第 i 个特征是最有利于划分的特征
return bestFeature ''' ##测试
myData,labels = creatDataSet()
best = chooseBest(myData) print(best) '''
3 递归构建决策树
基于之前的分析，我们选取划分结果最好的特征划分数据集，由于特征很可能多与两个， 因此可能存在大于两个分支的数据集划分，第一次划分之后，可以将划分的数据继续向下传递，如果将每一个划分的数据看成是原数据集，那么之后的每一次划分都可以看成是和第一 次划分相同的过程，据此我们可以采用递归的原则处理数据集。递归结束的条件是：程序遍 历完所有划分数据集的属性，或者每个分支下的所有实例都有相同的分类。编程实现：
代码语言：javascript复制 ##递归构建决策树 import operator #返回出现次数最多的分类名称 def majorClass(classList):
classCount = {}
for vote in classList:
if vote not in classCount.keys():
classCount[vote] = 0
classCount[vote] = 1 #降序排序，可以指定 reverse = true
sortedClassCount = sorted(classcount.iteritems(),key = operator.itemgetter(1),reverse = true)
return sortedClassCount[0][0]
#创建树 def creatTree(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 majorClass(classList)
bestFeat = chooseBest(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] = creatTree(splitDataSet(dataSet,bestFeat,value),subLabels)
return myTree
''' #测试 myData,labels = creatDataSet() mytree = creatTree(myData,labels) print(mytree) '''
