什么是决策树？
分类决策树模型是一种描述对实例进行分类的树形结构。 决策树由结点和有向边组成。结点有两种类型：内部结点和叶 节点。内部结点表示一个特征或属性，叶节点表示一个类。
基本流程：
决策过程中提出的每个判定问题都是对某个属性的“测试” 。
每个测试的结果或是导出最终结论，或者导出进一步的判定问题，其考虑范围是在上次决策结果的限定范围之内 。
从根结点到每个叶结点的路径对应了一个判定测试序列。
目的：
决策树学习的目的是为了产生一棵泛化能力强， 即处理未见示例能力强的决策树。
信息增益：
“信息熵”是度量样本集合纯度最常用的一种指标，假定
当前样本集合D中第k类样本所占的比例为 pk (K=1, 2, ..., |y|)
，则D的信息熵定义为
Ent(D)的值越小，则D的纯度越高
计算给定数据集的香农熵：
点击查看代码
from math import *
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 shannonEnt
点击查看代码
def createDataSet() :
def createDataSet() :
dataSet=[[1, 1, 1,'no'],
[1, 1, 0,'no'],
[1, 0, 1,'yes'],
[1, 0, 0,'yes'],
[0, 1, 0,'no'],
[0, 1, 1,'yes'],
[0, 0, 1,'yes'],
[0, 0, 1,'yes'] ]
labels = ['hot weather','lesson','rain']
return dataSet, labels
点击查看代码
def splitDataSet(dataSet, axis, value) :
retDataSet =[]
featVec =[]
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.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 majorityCnt(classList):
classCount={}
for vote in classList:
if vote not in classCount.keys(): classCount[vote]= 0
classCount[vote]+=1
sortedClassCount =sorted( classCount.iteritems()，key=operator.itemgetter(1)，reverse=True)
return sortedClassCount[0][0]
点击查看代码
def createTree(dataSet, labels):
classList=[examp1e[-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]
uniqueValue = set(featValues) # 该属性所有可能取值
for value in uniqueValue: #对每个分支，递归构建树
subLabels = labels[:]
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
return myTree