机器学习实战之——决策树算法学习总结

小谢

机器学习实战之——决策树算法学习总结

前言：

k-近邻算法可以完成很多分类任务，但是它最大的缺点就是无法给出数据的内在含义，决策树的主要优势在于数据形式非常容易理解。决策树很多任务都是为了数据中所蕴含的知识信息，因此决策树可以使用不熟悉的数据集合，并从中提取一系列的规则，机器学习算法最终将使用这些机器从数据集中创造的规则。决策树经常使用在专家系统中，并且决策树给出的结果往往可以匹敌在当前领域具有几十年工作经验的人类专家。

决策树的形式如下：

1、构造决策树

当前数据集上哪些特征在划分数据分类时起决定作用？

a) 首先找到决定性的特征，然后评估每个特征，将原始数据集划分为几个子数据集，这些子数据集会分布在第一个决策点的所有分支上。

b) 如果当前分支下的数据属于同一类型，则当前数据已正确划分分类，如果数据内不属于同一类型，则需要重复划分数据子集，直到所有具有相同类型的数据均在一个数据子集内（划分数据子集的算法和划分原始数据集的方法相同——递归）。

划分数据集的大原则是：将无序的数据变得更加有序。划分数据集之前之后信息发生的变化称为信息增益。评测数据划分方式需要知道如何计算信息增益。集合信息的度量方式称为香农熵，知道如何计算信息增益后，就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。

以下是关于信息增益和熵的定义：

计算给定数据集的香农熵：

def calcShannonEnt(dataSet):

numEntries=len(dataSet)

       # 创建数据字典，key值记录当前类别出现的次数，如果当前key值不存在，则扩展字典并将当前key值加入字典

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 splitDataSet(dataSet,axis,value):

       # 为了不修改原始数据集，新建一个列表对象

retDataSet =[]

       # 遍历数据集

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 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

运行结果是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

运行结果：

2、使用Matplotlib注解绘制树形图

使用文本注解绘制树节点

import matplotlib.pyplot as plt

# 定义文本框和箭头格式

decisionNode = dict(boxstyle="sawtooth",fc="0.8")

leafNode = dict(boxstyle="round4",fc="0.8")

arrow_args = dict(arrowstyle="<-")

# 绘制带箭头的注解

def plotNode(nodeTxt,centerPt,parentPt,nodeType):

createPlot.axl.annotate(nodeTxt,xy=parentPt,xycoords='axes fraction',xytext=centerPt,textcoords='axes fraction',

va="center",ha="center",bbox=nodeType,arrowprops=arrow_args)

$ import treePlotter

$ treePlotter.createPlot0()

获取叶节点的数目和树的层数

# 获取叶节点的数目

def getNumLeafs(myTree):

numLeafs=0

firstStr=myTree.keys()[0]

secondDict=myTree[firstStr]

for key in secondDict.keys():

if type(secondDict[key]).__name__=='dict':

numLeafs +=getNumLeafs(secondDict[key])

else:         numLeafs +=1

return numLeafs

# 获取叶节点树层数

def getTreeDepth(myTree):

maxDepth = 0

firstStr=myTree.keys()[0]

secondDict = myTree[firstStr]

for key in secondDict.keys():

if type(secondDict[key]).__name__=='dict':

thisDepth=1+getTreeDepth(secondDict[key])

else:thisDepth =1

if thisDepth > maxDepth:maxDepth = thisDepth

return maxDepth

测试：

调用createPlot() 函数绘制树形图

$ myTree=treePlotter.retrieveTree(1)

$ treePlotter.createPlot(myTree)

使用决策树分类：

def classify(inputTree,featLabels,testVec):

firstStr=inputTree.keys()[0]

econdDict=inputTree[firstStr]

featIndex=featLabels.index(firstStr)

for key in secondDict.keys():

if testVec[featIndex] ==key:

if type(secondDict[key]).__name__=='dict':

classLabel= classify(secondDict[key],featLabels,testVec)

else: classLabel = secondDict[key]

return classLabel

运行结果：

决策树存储：

构造决策树是很耗时的任务，即使处理很小的数据集，也需要花费几秒的时间，如果数据集很大，将会耗费很多计算时间，然而用创建好的决策树解决分类问题，则可以很快完成。

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)

验证上述代码的效果如下：

通过上述代码可以将分类器存储在硬盘上，而不用每次对数据分类时重新学习一遍，这也是决策树的优点之一。

3、使用决策树预测隐形眼镜

使用python命令提示符运行效果如下：

>>> fr = open('lenses.txt')

>>> lenses=[inst.strip().split('\t') for inst in fr.readlines()]

>>> lensesLabels=['age','prescript','astigmatic','tearRate']

>>> lesesTree= trees.createTree(lenses,lensesLabels)

>>> lesesTree

{'tearRate': {'reduced': 'no lenses', 'normal': {'astigmatic': {'yes': {'prescript': {'hyper': {'age': {'pre': 'no lenses', 'presbyopic': 'no lenses', 'young': 'hard'}}, 'myope': 'hard'}}, 'no': {'age': {'pre': 'soft', 'presbyopic': {'prescript': {'hyper': 'soft', 'myope': 'no lenses'}}, 'young': 'soft'}}}}}}

>>> treePlotter.createPlot(lensesTree)

4、总结：

决策树分类器就像带有终止块的流程图，终止快表示分类结果。开始处理数据集时，我们先需要测量集合中数据的不一致行，也就是熵，然后寻找最优方案划分数据集，直到数据集中的所有数据属于同一分类。

使用Matplotlib的注解功能，我们可以将存储的树结构转化为容易理解的图形。隐形眼镜的例子表明决策树可能产生过多的数据集划分，从而产生过度匹配的数据集问题，可以通过裁剪决策树，合并相邻的无法产生大量信息增益的叶节点，消除过度匹配的问题。

morinson

有成果，水平真不是盖的，牛