决策树
3.1决策树的构造
决策树
优点:计算复杂度较低,输出易于理解,对中间值的缺失不敏感,可以处理不相关数据
缺点:可能会产生过度匹配的问题
适用数据类型:数值型和标称型
构造决策树的第一个问题,找出当前数据集上对数据划分取决定性因素的特征,这时原始数据被划分成几个数据子集.这些子集分布在各个节点上,如果该节点的数据都是同类型,则结束,如果不是同一类型,继续进行决策树.
3.1.1信息增益
在划分数据集之后信息发生的变化称为信息增益.获得信息增益最高的特征就是最好的选择
信息熵概念:一个系统越有序,信息熵就越低,反之一个系统越是胡乱,信息熵就越高.信息熵被认为是信息有序化程度的一个度量.
信息量的定义:如果一个消息x出现的概率为p,则这一个消息所含的信息量是
信息熵:
计算给定数据的信息熵:
from math import log
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
for key in labelCounts:
prob = float(labelCounts[key])/numEntries
shannonEnt -= prob*log(prob,2)
return shannoEnt
3.1.2划分数据集
基本思路:
遍历列表,将特征值符合value的值提出来,并将对应特征值抽掉,得到抽取后的数据子集,计算该数据子集的信息熵
def spiltDataSet(dataSet,axis,value):
#创建新的list对象,Python传入的是引用,如果直接使用dataSet会造成全局的dataSet改变
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
#以下三行抽取
reduceFeatVec = featVec[: axis]
reduceFeatVec.extend(featVec[axis+1:]) #分辨extend函数和append函数的区别
retDataSet.append(reduceFeatVec)
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) #取set
newEntropy = 0.0
#(以下五行) 计算每种划分方式的信息熵
for value in uniqueVals:
subDataSet = spiltDataSet(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
3.1.3递归构建决策树
原理:得到原始数据集,然后基于最好的属性值划分数据集,由于特征值可能多于两个,因此可能存在大于两个分支的数据集划分.第一次划分之后,数据将被向下传递到树分支的下一个节点,在这个节点上,我们可以再次划分数据.因此我们可以采用递归的原则来处理数据集
递归结束的条件是:程序遍历完所有划分数据集的属性,或者每个分支下的所有实例都具有相同的分类.如果所有实例具有相同的分类,则得到一个叶子节点或者终止块,任何到达叶子节点的数据必然属于叶子节点的分类
决策树
import opeator
def majorityCnt(classList):
classCount = {}
for vote in classList:
if vote not in classCount.keys():
classCount[vote] +=1
sortedClassCount = sorted(classCount.iteritems(),key = operator.itemgetter(1),reversed = True)
return sortedClassCount[0][0]
以上代码:使用分类名称的列表,创建classList中唯一值的数据字典,字典对象存储了classList中每个类的名称和标签出现的次数,返回出现最多次的标签名称和次数
