机器学习实战（4）
机器学习实战之 决策树——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)
classLabel = secodDict[key]
return classLabel
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：175564次
积分：4087
积分：4087
排名：第5148名
原创：233篇
转载：175篇
评论：24条
(6)(18)(25)(8)(5)(17)(22)(20)(22)(7)(3)(8)(4)(16)(2)(2)(7)(4)(12)(1)(7)(8)(23)(2)(36)(23)(25)(77)&&&&&&&&&&&&&&&&&&
posts - 41,comments - 0,trackbacks - 0
决策树，设计到信息论知识，信息熵，信息增益率等概念
ID3算法、C4.5算法
决策树进程被用来来处理分类问题，最近也常用的数据挖掘算法
有点：计算复杂度不高，输出结果易于理解，对中间值缺失不敏感，可以处理不相关的特征数据
缺点：可能会产生过度匹配问题
适用数据类型：数值型和标称型
在机器学习中的决策树，首先要划分数据，但是一般数据中有很多个特征，从哪个特征开始分才是好的呢？
根据信息论知识，期望信息越小，信息增益越大，从而纯度越高。
ID3算法的核心思想就是以增益度量属性选择，选择划分后的信息增益。采用自顶向下的贪婪的搜索遍历可能的决策树空间。
&所以，ID3的思想便是：
自顶向下的贪婪搜索遍历可能的决策树空间构造决策树(此方法是ID3算法和C4.5算法的基础)；
从&哪一个属性将在树的根节点被测试&开始；
使用统计测试来确定每一个实例属性单独分类训练样例的能力，分类能力最好的属性作为树的根结点测试(如何定义或者评判一个属性是分类能力最好的呢？这便是下文将要介绍的信息增益，or 信息增益率)。
然后为根结点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支（也就是说，样例的该属性值对应的分支）之下。
重复这个过程，用每个分支结点关联的训练样例来选取在该点被测试的最佳属性。
这形成了对合格决策树的贪婪搜索，也就是算法从不回溯重新考虑以前的选择。
ID3算法使用的是信息熵
&C4.5算法使用的是增益比率gain ratio。增益度量Gain(S,A)和分裂信息度量Splitlnformation(S,A)
决策树使用于特征提取值离散情况，连续的特征一般也要处理成离散的。
阅读(...) 评论()君，已阅读到文档的结尾了呢~~
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
机器学习源码解析03
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口part 2 树、字典、递归
上一篇讲解了决策树算法的数学理论基础，接下来讲讲具体是怎么实现的。
首先，决策树是以一棵树的形式进行存储的。树是一种数据结构，它是若干结点的集合，是由唯一的根结点和若干互不相交的子树组成的（翻开《数据结构高分笔记》，念）。就像这样：
目前我们只要了解：最上面那个是根结点，紧跟在每个结点下面的结点是它的孩子结点，最下面那些没有孩子结点的结点是叶子结点就可以了。
既然树是结点的集合，那么首先要了解的是每个结点的结构。在树的链式存储结构中，每个结点用一个链结点存储。比如C语言中二叉树结点的定义（不知道没关系，这不是重点）：
（不要觉得把代码写在纸上是闲得蛋疼，你考试和面试的时候都要在纸上写的，平时不找手感，到时候你就知道什么是拙计）
放这个图是为了说明，树的一个结点需要包含两部分信息：一部分是结点本身的信息，另一部分是要找到它的下一个（或几个）孩子结点在哪里？这样，在有了根结点之后，我们就可以遍历整棵树，来得到树中每个结点的信息。
那么在python中，可以怎样存储一棵树呢？幸而我们不用像C语言那样写冗长的定义，python为我们准备好了一种数据结构：字典，非常适合用来构造一棵树~
我们在第二章里已经见识过字典了。简而言之就是由键值对构成的集合，像这样：{key1：value1，key2：value2，key3：value3，...}。由于键和值之间建立了映射（相当于c语言里的指针），可以通过字典的嵌套来构造一棵树。比如：
{'no surfacing': {0: 'no', 1: {'flippers': {0: {'head': {0: 'no', 1: 'yes'}}, 1: 'no'}}}}
用matplotlib画出来就是这样：
回到决策树。刚才画的那个就是一棵决策树啦，它的根结点是我们选择的第一个要进行分类的特征，分成的几类（如果可再分的话）需要进行下一次分类，那么根结点的孩子结点就是第二次分类时选择的特征；然后这个过程在以孩子结点为根的子树上循环往复，直到得到不可再分的样本集为止。叶子结点储存的是最终不可再分的样本集的标签。
书上那个给鱼分类的sample太不接地气了，接下来，我再给大家for一个sample：
这是一个决定是否要出去玩的决策树。第一次按天气这个特征进行分类，分为晴、阴、雨三类；其中阴这一类的样本集不可再分，因此它就是叶子结点，标签为“出去玩”。晴和雨分别按湿度和风力进行第二次分类，分类的结果均不可再分，因此湿度和风力的孩子结点均为叶子结点。
值得注意的是决策树算法中选择分类特征、划分样本集这两个过程是不断在循环的，树不断在生长，每个新结点继续生长的方式与根结点第一次生长的方式无异——这说明决策树生长的过程在调用它自身（生长的过程），每一次新的生长都是原来生长的一种重复。这种方法称为递归。
要理解什么是递归，你首先要理解什么是递归……【拖出去
递归并不是无限循环，否则就要发生栈溢出了（stackoverflow：你叫我？）。看看上面那句话，是不是有种眩晕的感觉？那就是你的大脑溢出了。顺便说一下，如果你的大脑溢出了，上stackoverflow看看是一种不错的选择。
扯远了，回来回来。递归要成立，需要两个条件：
1）递归的终止条件。必须要有一种情况能让递归结束，在决策树的例子里，“样本集不可再分”就是终止条件。
2）每次的递归调用过程中，必须要化归为一个更小规模的同类过程，以至于最终可以达到终止条件。比如决策树算法中，每次进行分类都要损失掉一个特征，最终所有特征都损失掉的时候自然就达到了终止条件。
树是由唯一的根结点和若干互不相交的子树组成的。这个树的定义也是递归的，它在定义自身的时候用到了自身的定义。
现在一切的原理都解释明白了，下一篇我们就讲最后一步~实现决策树算法——ID3（Iterative Dichotomiser 3）！
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：754次
排名：千里之外}