决策树 -- 简介
决策树(decision tree)一般都是自上而下的来生成的。每个决策或事件（即自然状态）都可能引出两个或多个事件，导致不同的结果，把这种决策分支画成图形很像一棵树的枝干，故称决策树。
决策树是一种有监管学习的分类方法。决策树的生成算法有 ID3 、C4.5 和 CART（Classification And Regression Tree）等，CART的分类效果一般优于其他决策树。
决策树的决策过程需要从决策树的根节点开始，待测数据与决策树中的特征节点进行比较，并按照比较结果选择选择下一比较分支，直到叶子节点作为最终的决策结果。
决策树一般流程
1、收集数据
2、准备数据（数值型数据必须离散化）
3、分析数据
4、训练数据
5、学习数据，使用经验树计算错误率
构建决策树由以下三部分所构成
1、特征选择
2、决策树生成
3、决策树剪枝
特征选择阶段
为了解释清楚各个数学概念，引入例子
上表有15个样本数据表。数据包括贷款申请人的4个特征：年龄、有工作与否、有房子与否、信贷情况，其中最后一列类别的意思是：是否同意发放贷款，这个就是决策树最后要给出的结论，即目标属性——是否发放贷款，即决策树最末端的叶子节点只分成2类：同意发放贷款与不同意发放贷款。
信息熵（entropy）
其中，S为所有事件集合，p为发生概率，c为特征总数。
注意：熵是以2进制位的个数来度量编码长度的，因此熵的最大值是log2C。
其中pi表示第i个类别在整个训练数据中出现的概率，可以用属于此类别元素的数量除以训练数据（即样本数据）总数量作为估计。
具体问题具体分析：是否发放贷款，将9个发放归为一类，剩余6个不发放归为一类，这样进行分类的信息熵为：
信息增益（information gain）
其中，第二项为属性A对S划分的期望信息。
具体问题具体分析
以年龄为条件的信息增益为
有工作的信息增益
有房子的信息增益
信贷情况的信息增益
最后比较各特征的信息增益值，对于特征A3有自己房子的信息增益值最大，所以选择特征A3作为最优特征。
由于特征A3(有自己房子)的信息增益值最大，所以选择特征A3作为根节点的特征。它将训练数据集划分为两个子集D1(A3取值为是)和D2(A3取值为否)。由于D1只有同一类样本点，可以明确要贷款给D1，所以它成为一个叶节点，节点类标记为“是”。
对于D2则需要从特征A1(年龄)，A2(有工作)和A4(信贷情况)中选择新的特征。计算各个特征的信息增益:
选择信息增益最大的特征A2(有工作)作为节点特征。A2有2个取值，一个对应“是”(有工作)的子节点，包含3个样本，他们属于同一类，所以这是一个叶节点，类标记为“是”；另一个对应“否”(无工作)的子节点，包含6个样本，属于同一类，这也是一个叶节点，类标记为“否”。
换句话有15个贷款人，经过是否有房这一筛选条件，有房子的6个人能够贷款。剩余9个人需要进一步筛选，以是否有工作为筛选条件，有工作的3个人可以贷款，无工作的6个人不能够贷款。
该决策树只用了两个特征(有两个内部结点)，以有自己的房子作为首要判决条件，然后以有工作作为判决条件是否可以贷款。
决策树生成阶段
决策树学习比较典型的有三种算法：ID3算法、 C4.5算法和CART算法。
一、ID3算法
ID3算法由Ross Quinlan发明，建立在“奥卡姆剃刀”的基础上：越是小型的决策树越优于大的决策树（be simple简单理论）。
ID3算法中根据信息增益评估和选择特征，每次选择信息增益最大的特征作为判断模块建立子结点。
ID3算法可用于划分标称型数据集，没有剪枝的过程，为了去除过度数据匹配的问题，可通过裁剪合并相邻的无法产生大量信息增益的叶子节点（例如设置信息增益阀值）。
使用信息增益的话其实是有一个缺点，那就是它偏向于具有大量值的属性。就是说在训练集中，某个属性所取的不同值的个数越多，那么越有可能拿它来作为分裂属性，而这样做有时候是没有意义的。
ID3算法步骤：
二、C4.5算法
C4.5算法用信息增益率来选择属性，继承了ID3算法的优点。并在以下几方面对ID3算法进行了改进：
- 用信息增益率来选择属性，克服了用信息增益选择属性偏向选择多值属性的不足；
- 在构造树的过程中进行剪枝；
- 能够完成对连续属性进行离散化；
- 能够对不完整的数据进行处理。
C4.5算法产生的分类规则易于理解、准确率较高；但效率低，因树构造过程中，需要对数据集进行多次的顺序扫描和排序。也是因为必须多次数据集扫描，C4.5只适合于能够驻留于内存的数据集。
在实现过程中，C4.5算法在结构与递归上与ID3完全相同，区别只在于选取决决策特征时的决策依据不同，二者都有贪心性质：即通过局部最优构造全局最优。
C4.5算法步骤：
三、CART算法
CART，即分类和回归树（classification and regression tree），也是一种应用很广泛的决策树学习方法。这是一种可以处理离散特征值和连续特征值的决策树，处理离散特征值使用分类决策树，处理连续特征值使用回归决策树。
作为分类树时，其本质与ID3、C4.5并有多大区别，只是选择特征的依据不同而已。另外，CART算法建立的决策树一般是二叉树，即特征值只有yes or no的情况（个人认为并不是绝对的，只是看实际需要）。当CART用作回归树时，以最小平方误差作为划分样本的依据。
基尼指数 （Gini）
分类树采用基尼指数选择最优特征。 假设有K个类，样本点属于第k类的概率为pk，则概率分布的基尼指数定义为：
对于给定的样本集合D，其基尼指数为：
CART分类树的算法步骤：
决策树剪枝阶段
它由完全生长的树剪去子树，通过删除节点的分支，并用树叶替换它而剪掉给定节点的子树，树叶用被替换的子树中最频繁的类标记。
其中C4.5算法使用悲观剪枝方法，CART算法则为代价复杂度剪枝算法（后剪枝）。
悲观剪枝法的基本思路是：设训练集生成的决策树是T，用T来分类训练集中的N的元组，设K为到达某个叶子节点的元组个数，其中分类错误地个数为J。由于树T是由训练集生成的，是适合训练集的，因此J/K不能可信地估计错误率。所以用(J+0.5)/K来表示。设S为T的子树，其叶节点个数为L(s)
为到达此子树的叶节点的元组个数总和
为此子树中被错误分类的元组个数之和。在分类新的元组时，则其错误分类个数为
当用此树分类训练集时，设E为分类错误个数，当下面的式子成立时，则删掉子树S，用叶节点代替，且S的子树不必再计算。
ID3算法 -- 实例
根据头发和声音怎么判断一位同学的性别。
| 头发 | 声音 | 性别 |
|---|---|---|
| 长 | 粗 | 男 |
| 短 | 粗 | 男 |
| 短 | 粗 | 男 |
| 长 | 细 | 女 |
| 短 | 细 | 女 |
| 短 | 粗 | 女 |
| 长 | 粗 | 女 |
| 长 | 粗 | 女 |
from math import log
import operator
def calcShannonEnt(dataSet): # 计算数据的熵(entropy)
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
for key in labelCounts:
prob=float(labelCounts[key])/numEntries # 计算单个类的熵值
shannonEnt-=prob*log(prob,2) # 累加每个类的熵值
return shannonEnt
def createDataSet(): # 创造示例数据
dataSet = [[\'长\', \'粗\', \'男\'],
[\'短\', \'粗\', \'男\'],
[\'短\', \'粗\', \'男\'],
[\'长\', \'细\', \'女\'],
[\'短\', \'细\', \'女\'],
[\'短\', \'粗\', \'女\'],
[\'长\', \'粗\', \'女\'],
[\'长\', \'粗\', \'女\']]
labels = [\'头发\',\'声音\'] #两个特征
return dataSet,labels
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
def chooseBestFeatureToSplit(dataSet): # 选择最优的分类特征
numFeatures = len(dataSet[0])-1
baseEntropy = calcShannonEnt(dataSet) # 原始的熵
bestInfoGain = 0
bestFeature = -1
for i in range(numFeatures):
featList = [example[i] for example in dataSet]
uniqueVals = set(featList)
newEntropy = 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): #按分类后类别数量排序，比如：最后分类为2男1女，则判定为男；
classCount={}
for vote in classList:
if vote not in classCount.keys():
classCount[vote]=0
classCount[vote]+=1
sortedClassCount = sorted(classCount.items(),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]
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
if __name__==\'__main__\':
dataSet, labels=createDataSet() # 创造示列数据
print(createTree(dataSet, labels)) # 输出决策树模型结果输出结果为：
{\'声音\': {\'细\': \'女\', \'粗\': {\'头发\': {\'短\': \'男\', \'长\': \'女\'}}}}