决策树定义
-
概念：决策树可以近似于一个流程图，长方形代表判断模块，椭圆形代表终止模块，表示已经得出结论，可以终止运行。从判断模块引出的左右箭头称作分支，它可以到达另一个判断模块或者终止模块。
决策树 优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据
缺点：可能会产生过度匹配问题
应用难点：很难确定特征
适用数据类型：数值型和标称型
如何创建树的分支？
Function createBranch():
检测数据集中的每个子集是否属于同一分类
If so return 类标签;
Else
寻找划分数据集的最好特征
划分数据集
创建分支节点
for 每个划分的子集
调用函数createBranch()并增加返回结果到分支节点中
return 分支节点
- 信息增益：划分数据之前之后的变化称为信息增益，通过计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。香农提出的了熵用于计算信息增益，信息增益=原来的熵-变化后的熵
- 信息的定义：l(xi)=-log2p(xi),p(xi)表示选择xi类别的概率
- 熵：信息的期望值，计算一个样本集合中的数据是纯洁的还是不纯洁的，公式(n是分类的数目)：
H=-\sum_{i=1}^{n}p(x_i)log_2p(x_i)
决策树的程序实现
- 计算给定数据集的香农熵的实现代码：
from math import log
def calcShannonEnt(dataset):
numEntries = len(dataset)
labelCounts ={}
# 求出各个类别的样本总数，用来计算p(xi)
for featVec in dataset:
currentLabel = featVec[-1]
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
shannoEnt = 0.0
#利用公式计算熵
for key in labelCounts:
prob = float(labelCounts[key])/numEntries
shannoEnt -= prob*log(prob,2)
return shannoEnt
- 信息熵、信息增益与信息增益率的区别
- 划分数据集：对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式：
#按照给定特征划分数据集
#extend() 函数用于在列表末尾一次性追加另一个序列中的多个值
#输入：待划分的数据集，划分数据集的特征，需要返回的特征的值
#a[i:j]:表示取从第i+1位到第j个元素
def splitDataSet(dataSet,axis,value):
retDataSet =[]
for featVec in dataSet:
if featVec[axis] == value:
# 从数据元组去掉该特征值
reduceFeatVec =featVec[:axis]
reduceFeatVec.extend(featVec[axis+1:])
retDataSet.append(reduceFeatVec)
return retDataSet
- 选择最好的数据集划分方法
#选择最好的数据集划分方式
def chooseBestFeatureToSplit(dataSet):
#计算列数得到特征数
numFeatures = len(dataSet) - 1
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0.0
bestFeatures = -1
for i in range(numFeatures):
#循环取出dataset的元组，然后取出元组中的第i列的所有取值
featList = [example[i] for example in dataSet]
uniqueVals = set(featList)
#计算每个特征的所有特征值作为划分子节点时的熵
for values 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
bestFeatures = i
return bestFeatures
- 数据具有多个标签时如何处理？
- 采用多数表决的方法决定该子节点的分类
#当出现多个类标签结果时，采用投票表决的方法决定最终类标签
def majorityCnt(classList):
classCount = {}
for vote in classList:
if vote not in classCount.keys():
classCount[vote]=0
classCount[vote] += 1
sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(i),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
- 使用前面构造好的算法得到决策树，对测试数据执行分类：
#使用决策树执行分类
#输入：决策树，特征表，测试数据
def classify(inputTree, feaLabels, testVec):
#取出第一个键值，即根
firstStr = inputTree.keys()[0]
#获得根对应的子节点
secondDict = inputTree[firstStr]
#找到第一个键值在实际数据存储中的列位置
featIndex = feaLabels.index(firstStr)
for key in secondDict.keys():
#找到下一步要到达的节点
if testVec[featIndex]==key:
if type(secondDict[key])._name_== 'dict':
classLabel=classify(secondDict[key],feaLabels,testVec)
else:
classLabel=secondDict[key]
return classLabel
- 如何存储决策树？使用pickle包，pickle提供了一个简单的持久化功能。可以将对象以文件的形式存放在磁盘上。
def storeTree(inputTree, filename):
import pickle
fw = open(filename, 'w')
pickle.dump(inputTree, fw)
fw.close()
def grabTree(filename):
import pickle
fr = open(filename)
return pickle.load(fr)
