python 决策树 字符型_[4] python: 决策树
在构造决策树时，我们需要解决的第一个问题是，当前数据集上哪个特征在划分数据类型时起决定性作用。为了找到决定性的特征，划分出最好的结果，我们必须评估每个特征。完成测试之后，原始数据集就被划分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上。如果某个分支下的数据属于同一类型，则无需进一步对数据集进行分割。如果数据子集内的数据不属于同一类型，则需要重复划分数据子集的过程。如何划分子集的算法和划分原始数据集相同，直到所有具有相同类型的数据均在一个数据子集内。
创建分支createBranch()的伪代码如下：
检测数据集中每个子项是否属于同一分类：
If so return 类标签；
Else
寻找划分数据集的最好特疼
划分数据集
创建分支节点
for 每个划分的子集
调用函数creatBranch并增加返回结果到分支节点中
return 分支节点
这里我们需要进一步了解算法是如何划分数据集的
决策树的一般流程：
(1)收集数据
(2)准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化。
(3)分析数据
(4)训练算法：构造树的数据结构
(5)测试算法：使用经验树计算错误率
(6)使用算法：更好地理解数据的内在含义
这里使用ID3算法划分数据集。
1. 信息增益
熵定义为信息的期望值，如果待分类的事务可能划分在多个分类中，则符号xi的信息定义为：
其中
是选择该分类的概率
熵就是所有类别所有可能值包含的信息期望值，定义为
from math importlogdefcalcShannonEnt(dataSet):
numEnt=len(dataSet)
labelCount={} #用字典类型统计所有分类的情况，包括分类的标签和数目
for featVec indataSet:
currentLabel=featVec[-1]if currentLabel not inlabelCount.keys():
labelCount[currentLabel]=0
labelCount[currentLabel]+=1shannonEnt=0.0
for key in labelCount: #计算熵的公式
prob=float(labelCount[key])/numEnt
shanonEnt-=prob*log(prob,2)return shannonEnt
计算数据集的香农熵
2. 划分数据集
按照给定特征划分数据集：当我们按照某个特征划分数据集时，就需要把所有符合要求的都拿出来
defsplitDataSet(dataSet,axis,value):
retDataSet=[]for featVec indataSet:if featVec[axis] ==value:
reducedFeatVec=featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)return retDataSet
划分数据集
然后遍历整个数据集，循环计算熵，找到最好的特征划分方式
#不断地划分数据集，计算香农熵，选择最好的数据集划分方式
defchooseBestFeatureToSplit(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=ireturn bestFeature
选择最好的数据集划分方式
3.递归构建决策树
递归结束的条件是：程序遍历完所有划分数据的属性或者每个分支下的所有实例都有相同的分类。
如果数据集已经处理了所有的属性，但是类标签依然不是唯一的，此时需要决定如何定义该叶子节点，在这种情况下，我们通常会采用多数表决的方法决定该叶子节点的分类。
defmajorityCnt(classList):
classCount={}for vote inclassList:if vote not in classCount.keys(): classCount[vote] =0
classCount[vote]+= 1sortedClassCount= sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)returnsortedClassCount[0][0]
多数表决
创建树：利用递归实现，退出递归的条件一是类别完全相同，二是数据遍历结束。
defcreateTree(dataSet,labels):
classList= [example[-1] for example indataSet]if classList.count(classList[0]) == len(classList): #类别相同，停止划分
returnclassList[0]if len(dataSet[0]) == 1: #遍历完所有特征，返回出现次数最多的
returnmajorityCnt(classList)
bestFeat=chooseBestFeatureToSplit(dataSet)
bestFeatLabel=labels[bestFeat]
myTree={bestFeatLabel:{}}del(labels[bestFeat])
featValues= [example[bestFeat] for example indataSet]
uniqueVals=set(featValues)for value inuniqueVals:
subLabels= labels[:] #复制类标签
myTree[bestFeatLabel][value] =createTree(splitDataSet(dataSet, bestFeat, value),subLabels)returnmyTree
View Code
其中，count() 方法用于统计字符串里某个字符出现的次数。可选参数为在字符串搜索的开始与结束位置。
ID3算法：
ID3算法是决策树的一种，它是基于奥卡姆剃刀原理的，即用尽量用较少的东西做更多的事。
在决策树的每一个非叶子结点划分之前，先计算每一个属性所带来的信息增益，选择最大信息增益的属性来划
分，因为信息增益越大，区分样本的能力就越强，越具有代表性，很显然这是一种自顶向下的贪心策略。以上
就是ID3算法的核心思想。
但是，信息增益准则会对可取值数目较多的属性有所偏好。
C4.5算法是机器学习中的一个重要的决策树算法，它是对ID3算法的改进，相对于ID3算法主要有以下几个改进
(1)用信息增益率来选择属性
但是增益率对可取数目较少的属性有偏好，因此C4.5算法使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
(2)在决策树的构造过程中对树进行剪枝
(3)对非离散数据也能处理
(4)能够对不完整数据进行处理