决策树-原理与Sklearn库实现（1）机器学习实战_logp(xi)的底

    我们经常使用决策树处理分类问题，相比于其他分类算法，决策树算法的实现更加简单明了，而绘制出的决策树也能够轻松的看出数据隐含的内在信息，常用的决策树有CART树，ID3树，还有C4.5树，决策树的优点在于计算复杂度不高，输出结果易于理解，可以处理不相关特征数据，缺点是可能会产生过度匹配问题，因此建模完成后还经常需要剪枝或者在建模时对节点，深度进行一些限制，不过一般数据量不是很大时，这个问题暂时可以不考虑。

    

决策树解决分类问题的步骤主要是以下几步：

（1）根据数据的不同特征，将数据集依据特征划分

（2）根据不同算法，计算信息增益（ID3树），信息增益率（C4.5树）或基尼系数（CART树），选择最优数据集划分

（3）递归构建决策树，第一次划分后，数据将向下传递到树分支的下一个节点，在这个节点我们依旧根据之前的算法，对数据集划分，计算，不断递归，最终构建出决策树

这里先对几种特征划分方式做几个简单了解：

信息增益：

信息增益是特征选择的一个重要指标，定义一个特征为分类系统带来了多少信息，带来的信息越多，则特征越重要，对于一个特征而言，系统有它和没它时信息量发生的变化，差值就是特征为系统带来的信息，其实就是熵，要了解信息增益，首先要了解一下熵（entropy）的概念，熵定义为信息的期望值，如果待分类的事务可能划分在多个分类中，则符号Xi的信息定义为：

                                                L(Xi) = -logP(Xi)      底数为2

熵是表示随机变量不确定性的度量。设是一个取有限个值的离散随机变量，其概率分布为

                                                P（X=xi）=pi   i=1,2,3，···，n

则随机变量的熵定义为:

                                                H(xi) = -∑p(xi)logP(xi)

GINI系数：

又叫基尼不纯度，表示在集合样本中一个随机选中的样本被分错的概率，也就是说，GINI系数越小就代表着集合被选中样本被分错的概率越小，也就意味着集合的纯度越高，反之，集合纯度越低。

假设有k个类，样本点属于第k类的概率为pk，则概率分布的基尼指数定义为：   

                                                     Gini(p)=∑pk(1-pk)    k∈(1,K)

那么在给定特征A的条件下，集合D的基尼系数定义为：

基尼指数 表示集合D的不确定性，基尼指数  表示经T=t分割后集合D的不确定性。基尼指数越大，样本的不确定性也越大。

信息增益比：

信息增益比 = 惩罚系数 x 信息增益

信息增益比的是指就是在信息增益的基础上乘上一个惩罚系数，特征个数较多时，惩罚系数较小，特征个数较少时，惩罚系数较大，这就相当于给予特征个数一定比例权重，消除一些个数差异造成的熵信息不准。

特征T对训练数据集的信息增益比定义为其信息增益与训练数据集关于特征T的值的熵HA(D)之比：

                                                               gR(D,T) = g(D,T)/HT(D)

其中，HT(D) = -∑|Di|/|D|log2⁡(|Di|/|D|)    i ∈(1,n) N为特征T取值的个数。

几种算法的特点：

信息增益（ID3）：偏向取值较多的特征，特征取值多，划分更容易得到纯度高的子集，因此划分后熵低，所以信息增益大。

信息增益比（C4.5）：偏向取值较少的特征，特征值小，HA(D)的取值小，倒数大，所以信息增益大。

GINI系数（CART）：比较适合二叉树，多余二叉效果会下降。

接下来看一下书上的决策树实现过程，针对书上的代码，这里就简单的了解一下决策树的实现过程

ps：由于书中的代码是Python2.7版本，我这里是Anoconda python3.6版本，所以一部分代码与书上有小的改动。

from math import log
import operator
 
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
	#计算P(Xi) 以及求信息熵
	for key in labelCounts:
		prob = float(labelCounts[key])/numEntries
		ShannonEnt -= prob * log(prob,2)
 
	return ShannonEnt#信息熵

这里主要是计算给定数据集的熵信息，通过不同分类的数量除以总的分类数量得到概率P。

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

这里是将书中判断是否为鱼类的信息进行了处理，得到决策树的数据集和标签分类。

def splitDataSet(dataSet,axis,value):
	"""
	:params:
	:dataSet:待划分数据集
	:axis:特征行
	:value:特征值
	"""
	retDateSet = []
	for featVec in dataSet:
		if featVec[axis] == value:
			reducedFeatVec = featVec[:axis]#取特征前的数据
			reducedFeatVec.extend(featVec[axis+1:])#取特征后的数据
			retDateSet.append(reducedFeatVec)
 
	return retDateSet#得到去掉特征的数据集

这里按照给定的特征划分数据集，这里注意List append()和extend()函数的不同用法。

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):       #if语句寻找最优的信息增益
            bestInfoGain = infoGain         
            bestFeature = i
    return bestFeature                      #得到最佳特征分类的索引

这一步通过信息增益的比较选择数据集的最优划分形式。

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 majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)#得到最佳分类
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}}
    del(labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]#获取特征对应的value
    uniqueVals = set(featValues)
    for value in uniqueVals:#通过递归构造整个树
        subLabels = labels[:]       
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
    return myTree

根据之前函数的不同分工，构造递归函数，实现最终决策树的实现。

[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
[[1, 'yes'], [1, 'yes'], [0, 'no']]#数据集
0#最佳特征分类
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}#决策树字典形表达

运行上面的全部代码，就可以得到书上的结果了。除此之外，书上还给出了使用Matplotlib注解绘制树形图，书上已经有详细的解释，网上也有前辈做了详细的解释，这里就不多赘述了，只是将运行得到的决策树看一下。

pps：书中绘制决策树的代码中可能出现这个错误

TypeError: 'dict_keys' object does not support indexing

字典的键值不支持索引，这里将对应部分添加list即可。

    firstStr = myTree.keys()[0] ---> firstStr = list(myTree.keys())[0]

总结：

sklearn的调用库就像是黑盒子，编程中总是会出现会调用却不知道原理的情况，这篇文章主要对决策树的划分原理以及原理编码进行了 的最基础的了解，下一篇文章将主要介绍sklearn训练决策树和绘制决策树两个方面。ppps：有哪里不清楚或者不对，欢迎大家批评指正~