分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型:内部结点和叶节点。内部结点表示一个特征或属性,叶节点表示一个类。
算法结构
决策树在逻辑上以树的形式存在,包含根节点、内部结点和叶节点。
根节点:包含数据集中的所有数据的集合
内部节点:每个内部节点为一个判断条件,并且包含数据集中满足从根节点到该节点所有条件的数据的集合。根据内部结点的判断条件测试结果,对应的数据的集合将分到两个或多个子节点中。
叶节点:最终的类别。
一般流程
信息增益
在建立决策树之前,我们需要先学习一个非常重要的概念,那就是信息熵。
一条信息的信息量大小和它的不确定性有直接的关系,要搞清楚一件非常非常不确定的事情,或者是我们一无所知的事情,需要了解大量信息==>信息量的度量就等于不确定性的多少。
熵定义为信息的期望值,如果待分类的事物可能划分在多个类之中,则符号xi的信息定义为:
为选择该分类的概率
为了计算熵,需要计算所有类别的可能值包含的信息期望值,通过以下公式得到
n为分类数目,随机数目的不确定性随熵增大而增大
代码实现
from math import log def createDataSet(): dataSet = [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']] labels = ['no surfacing','flippers'] #change to discrete values return dataSet, labels def calcShannonEnt(dataSet): numEntries = len(dataSet) labelCounts = {} for featVec in dataSet: #the the number of unique elements and their occurance 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) #log base 2 return shannonEnt
划分数据集
分类算法除了需要测量信息熵,还需要划分数据集,度量划分数据集的熵,以便判断当前是否正确的划分了数据集。得到每个特征划分数据集的结果计算出的信息熵后,我们将遍历整个数据集,循环计算香农熵和splitdataset()函数以找到最好的特征划分方式
代码实现
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[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 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
信息增益率
在信息增益中,若把“编号”也作为一个候选划分属性,则其信息增益一 般远大于其他属性。显然,这样的决策树不具有泛化能力 ,无法对新样本进行有效预测
此时可用信息增益率来解决这类问题
信息增益比 = 惩罚参数 * 信息增益
其中
称为属性a的“固有值” [Quinlan, 1993],属性a的可能取值数 目越多(即V越大),则IV(a)的值通常就越大
信息增益率原则可能对取值数目较少的属性更加偏爱,为了解决这个问题,可以先找出信息增益在平均值以上的属性,在从中选择信息增益率最高的。
基尼指数
分类问题中,假设D有K个类,样本点属于第k类的概率为, 则概率 分布的基尼值定义为:
Gini(D)越小,数据集D的纯度越高;
给定数据集D,属性a的基尼指数定义为:
在候选属性集合A中,选择那个使得划分后基尼指数最小的属性作为最有划分属性。
用Matplotlib注解绘制树形图
Matplotlib提供了一个注解工具:annotations,可以在数据图形上添加文本工具。
Matplotlib实际上是一套面向对象的绘图库,它所绘制的图表中的每个绘图元素,例如线条Line2D、文字Text、刻度等在内存中都有一个对象与之对应。
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): # annotate是关于一个数据点的文本 # nodeTxt为要显示的文本,centerPt为文本的中心点,箭头所在的点,parentPt为指向文本的点 createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction', xytext=centerPt, textcoords='axes fraction', va="center", ha="center", bbox=nodeType, arrowprops=arrow_args ) def createPlot(): fig = plt.figure(1,facecolor='white') # 定义一个画布,背景为白色 fig.clf() # 把画布清空 # createPlot.ax1为全局变量,绘制图像的句柄,subplot为定义了一个绘图, #111表示figure中的图有1行1列,即1个,最后的1代表第一个图 # frameon表示是否绘制坐标轴矩形 createPlot.ax1 = plt.subplot(111,frameon=False) plotNode('a decision node',(0.5,0.1),(0.1,0.5),decisionNode) plotNode('a leaf node',(0.8,0.1),(0.3,0.8),leafNode) plt.show()
构造注解树
树在python中用嵌套字典存储
例 :>>> myTree
{‘no surfacing’: {0: ‘no’, 1: {‘flippers’: {0: ‘no’, 1: ‘yes’}}}}
绘制一颗完整的树需要技巧,虽然我们有坐标,但是如何放置所有的树节点却是个问题。所以我们需要知道有多少个叶节点来确定x轴长度;还需要知道有多少层来确定y轴的高度。
def getNumLeafs(myTree): #获得叶节点数目 numLeafs = 0 firstStr = myTree.keys()[0] secondDict = myTree[firstStr] for key in secondDict.keys(): if type(secondDict[key]).__name__=='dict': #测试该节点value是否是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
测试中可以用函数retrieveTree()来输出预储存的树信息
def retrieveTree(i): listOfTrees =[{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}, {'no surfacing': {0: 'no', 1: {'flippers': {0: {'head': {0: 'no', 1: 'yes'}}, 1: 'no'}}}} ] return listOfTrees[i]
def plotMidText(cntrPt, parentPt, txtString): xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0] yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1] createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30) def plotTree(myTree, parentPt, nodeTxt): numLeafs = getNumLeafs(myTree) depth = getTreeDepth(myTree) firstStr = myTree.keys()[0] cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff) plotMidText(cntrPt, parentPt, nodeTxt) plotNode(firstStr, cntrPt, parentPt, decisionNode) secondDict = myTree[firstStr] plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD for key in secondDict.keys(): if type(secondDict[key]).__name__=='dict': plotTree(secondDict[key],cntrPt,str(key)) else: plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode) plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key)) plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD def createPlot(inTree): fig = plt.figure(1, facecolor='white') fig.clf() axprops = dict(xticks=[], yticks=[]) createPlot.ax1 = plt.subplot(111, frameon=False, **axprops) plotTree.totalW = float(getNumLeafs(inTree)) plotTree.totalD = float(getTreeDepth(inTree)) plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0; plotTree(inTree, (0.5,1.0), '') plt.show()
最终实现树的创建
实际应用
使用了教材提供的隐形眼镜数据集
隐形眼镜类型包括硬材质(hard)、软材质(soft)以及不适合佩戴隐形眼镜(no lenses)。
特征有四个:age(年龄)、prescript(症状)、astigmatic(是否散光)、tearRate(眼泪数量)
小结