关键词:
决策树概念:
分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型:内部节点和叶节点,内部节点表示一个特征或属性,叶节点表示一个类。
分类的时候,从根节点开始,对实例的某一个特征进行测试,根据测试结果,将实例分配到其子结点;此时,每一个子结点对应着该特征的一个取值。如此递归向下移动,直至达到叶结点,最后将实例分配到叶结点的类中。
例如判断某款物品的潜在买家:
决策树可以看成一个if-then规则的集合:由决策树的根结点到叶结点的每一条路径构建一条规则;路径上的内部结点的特征对应着规则的条件,而叶结点对应着分类的结论。决策树的路径和其对应的if-then规则集合是等效的,它们具有一个重要的性质:互斥并且完备。这里的意思是说:每一个实例都被一条路径或一条规则所覆盖,而且只被一条规则所覆盖。
几个基本概念
特征选择问题希望选取对训练数据具有良好分类能力的特征,这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别,则称这个特征是没有分类能力的(对象是否喜欢打游戏应该不会成为关键特征吧,也许也会……)。为了解决特征选择问题,找出最优特征,先要介绍一些信息论里面的概念。
1.信息熵(香农熵)
熵是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量,其概率分布为:
随机变量的熵为:
熵越大,随机变量的不确定性就越大。
数据集熵值计算函数:
from math import log
def calcShannonEnt(dataSet): """dataSet 为前n-1列为特征,最后一列为类别的数据集 """ 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) # 以2为底的对数 return shannonEnt
2.条件熵
设有随机变量(X,Y),其联合概率分布为
条件熵H(Y|X)表示在已知随机变量XX的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵H(Y|X),定义为X给定条件下Y的条件概率分布的熵对X的数学期望:
这里,pi=P(X=xi),i=1,2,?,n.pi=P(X=xi),i=1,2,?,n.
3.信息熵
信息增益表示得知特征XX的信息而使得类Y的信息的不确定性减少的程度。特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差,即
这个差又称为互信息。信息增益大的特征具有更强的分类能力。
根据信息增益准则的特征选择方法是:对训练数据集(或子集)计算其每个特征的信息增益,选择信息增益最大的特征。
计算信息增益的算法如下:
通过划分数据集,并计算信息增益
def splitDataSet(dataSet, axis, value): ‘‘‘ 按照给定特征划分数据集 :param dataSet:待划分的数据集 :param axis:划分数据集的特征 :param value: 需要返回的特征的值 :return: 划分结果列表 ‘‘‘ retDataSet = [] for featVec in dataSet: if featVec[axis] == value: reducedFeatVec = featVec[:axis] #chop out axis used for splitting reducedFeatVec.extend(featVec[axis+1:]) retDataSet.append(reducedFeatVec) return retDataSet def calcConditionalEntropy(dataSet, i, featList, uniqueVals): ‘‘‘ 计算X_i给定的条件下,Y的条件熵 :param dataSet:数据集 :param i:维度i :param featList: 数据集特征列表 :param uniqueVals: 数据集特征集合 :return: 条件熵 ‘‘‘ conditionEnt = 0.0 for value in uniqueVals: subDataSet = splitDataSet(dataSet, i, value) prob = len(subDataSet) / float(len(dataSet)) # 极大似然估计概率 conditionEnt += prob * calcShannonEnt(subDataSet) # 条件熵的计算 return conditionEnt def calcInformationGain(dataSet, baseEntropy, i): ‘‘‘ 计算信息增益 :param dataSet:数据集 :param baseEntropy:数据集的信息熵 :param i: 特征维度i :return: 特征i对数据集的信息增益g(D|X_i) ‘‘‘ featList = [example[i] for example in dataSet] # 第i维特征列表 uniqueVals = set(featList) # 转换成集合 newEntropy = calcConditionalEntropy(dataSet, i, featList, uniqueVals) infoGain = baseEntropy - newEntropy # 信息增益,就yes熵的减少,也就yes不确定性的减少 return infoGain
两种算法
1,ID3算法
ID3算法由Ross Quinlan发明,建立在“奥卡姆剃刀”的基础上:越是小型的决策树越优于大的决策树(be simple简单理论)。ID3算法中根据信息增益评估和选择特征,每次选择信息增益最大的特征作为判断模块建立子结点。ID3算法可用于划分标称型数据集,没有剪枝的过程,为了去除过度数据匹配的问题,可通过裁剪合并相邻的无法产生大量信息增益的叶子节点(例如设置信息增益阀值)。使用信息增益的话其实是有一个缺点,那就是它偏向于具有大量值的属性。就是说在训练集中,某个属性所取的不同值的个数越多,那么越有可能拿它来作为分裂属性,而这样做有时候是没有意义的,另外ID3不能处理连续分布的数据特征,于是就有了C4.5算法。CART算法也支持连续分布的数据特征。
步骤:
ID3算法思想描述:
a.对当前例子集合,计算属性的信息增益;
b.选择信息增益最大的属性Ai(关于信息增益后面会有详细叙述)
c.把在Ai处取值相同的例子归于同于子集,Ai取几个值就得几个子集
d.对依次对每种取值情况下的子集,递归调用建树算法,即返回a,
e.若子集只含有单个属性,则分支为叶子节点,判断其属性值并标上相应的符号,然后返回调用处。
寻找最优划分方式代码
def chooseBestFeatureToSplitByID3(dataSet): ‘‘‘ 选择最好的数据集划分方式 :param dataSet:数据集 :return: 划分结果 ‘‘‘ numFeatures = len(dataSet[0]) - 1 # 最后一列yes分类标签,不属于特征向量 baseEntropy = calcShannonEnt(dataSet) bestInfoGain = 0.0 bestFeature = -1 for i in range(numFeatures): # 遍历所有特征 infoGain = calcInformationGain(dataSet, baseEntropy, i) # 计算信息增益 if (infoGain > bestInfoGain): # 选择最大的信息增益 bestInfoGain = infoGain bestFeature = i return bestFeature # 返回最优特征对应的维度
2.C4.5算法
C4.5算法是用于生成决策树的一种经典算法,是ID3算法的一种延伸和优化。C4.5算法对ID3算法主要做了一下几点改进:
??(1)通过信息增益率选择分裂属性,克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足;
??(2)能够处理离散型和连续型的属性类型,即将连续型的属性进行离散化处理;
??(3)构造决策树之后进行剪枝操作;
??(4)能够处理具有缺失属性值的训练数据。
- 优点:
(1)通过信息增益率选择分裂属性,克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足;
(2)能够处理离散型和连续型的属性类型,即将连续型的属性进行离散化处理;
(3)构造决策树之后进行剪枝操作;
(4)能够处理具有缺失属性值的训练数据。 - 缺点:
(1)算法的计算效率较低,特别是针对含有连续属性值的训练样本时表现的尤为突出。
(2)算法在选择分裂属性时没有考虑到条件属性间的相关性,只计算数据集中每一个条件属性与决策属性之间的期望信息,有可能影响到属性选择的正确性。
步骤:
代码:
创建树
def majorityCnt(classList): ‘‘‘ 采用多数表决的方法决定叶结点的分类 :param: 所有的类标签列表 :return: 出现次数最多的类 ‘‘‘ 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): ‘‘‘ 创建决策树 :param: dataSet:训练数据集 :return: 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 = chooseBestFeatureToSplitByID3(dataSet) # 最优划分特征 bestFeat = chooseBestFeatureToSplitByC45(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,featLabels,testVec): ‘‘‘ 利用决策树进行分类 :param: inputTree:构造好的决策树模型 :param: featLabels:所有的类标签 :param: testVec:测试数据 :return: 分类决策结果 ‘‘‘ firstStr = inputTree.keys()[0] secondDict = inputTree[firstStr] featIndex = featLabels.index(firstStr) key = testVec[featIndex] valueOfFeat = secondDict[key] if isinstance(valueOfFeat, dict): classLabel = classify(valueOfFeat, featLabels, testVec) else: classLabel = valueOfFeat return classLabel
可视化树
import matplotlib.pyplot as plt import tree # 定义文本框和箭头格式 decisionNode = dict(boxstyle="round4", color=‘#3366FF‘) # 定义判断结点形态 leafNode = dict(boxstyle="circle", color=‘#FF6633‘) # 定义叶结点形态 arrow_args = dict(arrowstyle="<-", color=‘g‘) # 定义箭头 #计算叶结点数 def getNumLeafs(myTree): numLeafs = 0 firstStr = list(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 = list(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 # 绘制带箭头的注释 def plotNode(nodeTxt, centerPt, parentPt, nodeType): createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords=‘axes fraction‘, xytext=centerPt, textcoords=‘axes fraction‘, va="center", ha="center", bbox=nodeType, arrowprops=arrow_args ) # 在父子结点间填充文本信息 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 = list(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 # 减少y偏移 for key in secondDict.keys(): if type(secondDict[key]).__name__==‘dict‘: plotTree(secondDict[key],cntrPt,str(key)) #recursion else: #it‘s a leaf node print the leaf node 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 #if you do get a dictonary you know it‘s a tree, and the first element will be another dict 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()
两个测试用例
1.
myDat = [[‘youth‘, ‘no‘, ‘no‘, ‘1‘, ‘refuse‘], [‘youth‘, ‘no‘, ‘no‘, ‘2‘, ‘refuse‘], [‘youth‘, ‘yes‘, ‘no‘, ‘2‘, ‘agree‘], [‘youth‘, ‘yes‘, ‘yes‘, ‘1‘, ‘agree‘], [‘youth‘, ‘no‘, ‘no‘, ‘1‘, ‘refuse‘], [‘mid‘, ‘no‘, ‘no‘, ‘1‘, ‘refuse‘], [‘mid‘, ‘no‘, ‘no‘, ‘2‘, ‘refuse‘], [‘mid‘, ‘yes‘, ‘yes‘, ‘2‘, ‘agree‘], [‘mid‘, ‘no‘, ‘yes‘, ‘3‘, ‘agree‘], [‘mid‘, ‘no‘, ‘yes‘, ‘3‘, ‘agree‘], [‘elder‘, ‘no‘, ‘yes‘, ‘3‘, ‘agree‘], [‘elder‘, ‘no‘, ‘yes‘, ‘2‘, ‘agree‘], [‘elder‘, ‘yes‘, ‘no‘, ‘2‘, ‘agree‘], [‘elder‘, ‘yes‘, ‘no‘, ‘3‘, ‘agree‘], [‘elder‘, ‘no‘, ‘no‘, ‘1‘, ‘refuse‘], ] labels = [‘age‘, ‘working?‘, ‘house?‘, ‘credit_situation‘] myTree = createTree(myDat, labels) createPlot(myTree) labels = [‘age‘, ‘working?‘, ‘house?‘, ‘credit_situation‘] print(classify(myTree,labels ,[‘youth‘,‘no‘,‘no‘,1]))
###结果为refuse
2.网上数据
import pandas as pd import numpy as np name_c=[‘sample code number‘,‘clump thickness‘, ‘uniformity of cell size‘, ‘uniformity of cell shape‘,‘marginal adhesion‘,‘single epithelial cell‘, ‘bare nuclei‘,‘bland chromatin‘,‘normal nucleoli‘,‘mitoses‘,‘class‘ ] data=pd.read_csv(‘http://archive.ics.uci.edu/ml/machine-learning-databases/breast-cancer-wisconsin/breast-cancer-wisconsin.data‘,names=name_c) data=data.replace(to_replace=‘?‘,value=np.nan) data=data.dropna(how=‘any‘) myDat=data[name_c[1:]].values[:].tolist() myTree = createTree(myDat, name_c[1:]) createPlot(myTree) print( classify(myTree,name_c[1:],[5,3,2,1,3,‘1‘,1,1,1]))
###结果为2
《机器学习实战》-决策树(代码片段)
目录决策树决策树简介决策树的构造信息增益划分数据集递归构建决策树在Python中使用Matplotlib注解绘制树形图Matplotlib注解构造注解树测试和存储分类器测试算法:使用决策树执行分类使用算法:决策树的存储示例:使用决策树... 查看详情
机器学习之路--决策树(代码片段)
...使用不熟悉的数据集合,并从中提取一系列规则,在这些机器根据数据集创建规则是,就是机器学习的过程。二,相关知识1决 查看详情
机器学习—决策树(代码片段)
一、原理部分:还是图片显示~ 二、sklearn实现1、回归树importpandasaspdimportnumpyasnpimportmatplotlib.pyplotaspltimportmatplotlibasmplimportseabornassnsmpl.rcParams[‘font.sans-serif‘]=[u‘SimHei‘]mpl.rcParams[‘axe 查看详情
机器学习-决策树(代码片段)
最近在看周志华的《机器学习》,感觉讲的还是条理清晰,循序渐进的。但是只是看了很快概念就混淆,导致脑子里一片混乱,所以准备将看过的内容及学到的东西放在这里和大家相互学习交流。 本文转自:http://blog.csdn.net/... 查看详情
机器学习实战教程:决策树实战篇(代码片段)
一、前言上篇文章机器学习实战教程(二):决策树基础篇_M_Q_T的博客-CSDN博客讲述了机器学习决策树的原理,以及如何选择最优特征作为分类特征。本篇文章将在此基础上进行介绍。主要包括:决策树构建决... 查看详情
机器学习——决策树(代码片段)
1、介绍决策树是一种依托决策而建立起来的一种树。在机器学习中,决策树是一种预测模型,代表的是一种对象属性与对象值之间的一种映射关系,每一个节点代表某个对象/分类,树中的每一个分叉路径代表某个可能的属性值... 查看详情
机器学习实战之一---简单讲解决策树(代码片段)
机器学习实战之一---简单讲解决策树https://blog.csdn.net/class_brick/article/details/78855510 前言:本文基于《机器学习实战》一书,采用python语言,对于机器学习当中的常用算法进行说明。 一、综述定义:首先来对决策树进... 查看详情
机器学习算法学习02:决策树的学习以及应用决策树解决cora数据集论文分类问题(代码片段)
机器学习算法学习02:决策树的学习以及应用决策树解决Cora数据集论文分类问题文章目录机器学习算法学习02:决策树的学习以及应用决策树解决Cora数据集论文分类问题1.前言2.算法分析2.1算法概述2.2算法优化3.算法代码3.... 查看详情
机器学习-决策树(代码片段)
...n_report,confusion_matrixfromsklearn.model_selectionimporttrain_test_split#我的例子主要是以代码实现和对其中的说明为主#如果想了解具体的算法原理网上有很多,我也不想复制粘贴了#这里还是用iris花作为例子iris_data=load_iris()[‘data‘]iris_label=l... 查看详情
机器学习回归决策树(代码片段)
回归决策树1.原理概述2.算法描述3.简单实例3.1实例计算过程3.2回归决策树和线性回归对比4.小结1.原理概述上篇文章已经讲到,关于数据类型,我们主要可以把其分为两类,连续型数据和离散型数据。在面对不同数据... 查看详情
机器学习实战基础(二十八):决策树概述(代码片段)
概述决策树是如何工作的 决策树(DecisionTree)是一种非参数的有监督学习方法,它能够从一系列有特征和标签的数据中总结出决策规则,并用树状图的结构来呈现这些规则,以解决分类和回归问题。决策树算法容易理解,适... 查看详情
机器学习_决策树python代码详解(代码片段)
决策树优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据;决策树缺点:可能会产生过度匹配问题。决策树的一般步骤:(1)代码中def1,计算给定数据集的香农熵: &nbs... 查看详情
机器学习决策树分类原理(代码片段)
决策树分类原理1.熵1.1概念1.2案例2.决策树的划分依据2.1信息增益2.1.1概念2.1.2案例2.2信息增益率2.2.1概念2.2.2案例案例一案例二2.2.3为什么使用C4.5要好?2.3基尼值和基尼指数2.3.1概念2.3.2案例3.小结3.1常见决策树的启发函数比较3.1.1ID3... 查看详情
机器学习回归决策树算法(代码片段)
目录1原理概述2算法描述3简单实例3.1实例计算过程3.2回归决策树和线性回归对比4小结1原理概述前面已经讲到,关于数据类型,我们主要可以把其分为两类,连续型数据和离散型数据。在面对不同数据时,决策树... 查看详情
机器学习sklearn监督学习分类算法决策树decisiontree(代码片段)
#导入鸢尾花数据集、决策树分类器、计算交叉验证值的函数cross_val_scorefromsklearn.datasetsimportload_irisfromsklearn.treeimportDecisionTreeClassifierfromsklearn.model_selectionimportcross_val_score#使用默认参数,创建一颗基于基尼系数的决策树 查看详情
机器学习决策树算法泰坦尼克号乘客生存预测(代码片段)
目录1决策树算法api2泰坦尼克号乘客案例背景2.1步骤分析2.2代码实现2.3决策树可视化2.3.1保存树的结构到dot文件2.3.2网站显示结构3决策树总结4小结1决策树算法apiclasssklearn.tree.DecisionTreeClassifier(criterion=’gini’,max_depth=None,rando... 查看详情
机器学习决策树算法泰坦尼克号乘客生存预测(代码片段)
目录1决策树算法api2泰坦尼克号乘客案例背景2.1步骤分析2.2代码实现2.3决策树可视化2.3.1保存树的结构到dot文件2.3.2网站显示结构3决策树总结4小结1决策树算法apiclasssklearn.tree.DecisionTreeClassifier(criterion=’gini’,max_depth=None,rando... 查看详情
机器学习算法:决策树算法简介以及分类原理(代码片段)
学习目标知道什么是决策树知道如何求解信息熵知道信息增益的求解过程知道信息增益率的求解过程知道基尼系数的求解过程知道信息增益、信息增益率和基尼系数三者之间的区别、联系决策树思想的来源非常朴素,程序设... 查看详情