python机器学习笔记 ID3决策树算法实战

前面学习了决策树的算法原理,这里继续对代码进行深入学习,并掌握ID3的算法实践过程。ID3算法是一种贪心算法,用来构造决策树,ID3算法起源于概念学习系统(CLS),以信息熵的下降速度为选取测试属性的标准,即在每一个节点选取还尚未被用来划分的具有最高信息增益的属性作为划分标准,然后继续这个过程,直到生成的决策树能完美的分类训练样例。ID3算法的背景知识ID3算法最早是由罗斯昆(J.RossQuin...

python机器学习笔记 ID3决策树算法实战

  前面学习了决策树的算法原理,这里继续对代码进行深入学习,并掌握ID3的算法实践过程。

  ID3算法是一种贪心算法,用来构造决策树,ID3算法起源于概念学习系统(CLS),以信息熵的下降速度为选取测试属性的标准,即在每一个节点选取还尚未被用来划分的具有最高信息增益的属性作为划分标准,然后继续这个过程,直到生成的决策树能完美的分类训练样例。

ID3算法的背景知识

  ID3算法最早是由罗斯昆(J. Ross Quinlan)于1975年在悉尼大学提出的一种分类预测算法,算法的核心是“信息熵”。ID3算法通过计算每个属性的信息增益,认为信息增益高的是好属性,每次划分选取信息增益最高的属性为划分标准,重复这个过程,直至生成一个能完美分类训练样例的决策树。

  决策树是对数据进行分类,以此达到预测的目的。该决策树方法先根据训练集数据形成决策树,如果该树不能对所有对象给出正确的分类,那么选择一些例外加入到训练集数据中,重复该过程一直到形成正确的决策集。决策树代表着决策集的树形结构。
  决策树由决策结点、分支和叶子组成。决策树中最上面的结点为根结点,每个分支是一个新的决策结点,或者是树的叶子。每个决策结点代表一个问题或决策,通常对应于待分类对象的属性。每一个叶子结点代表一种可能的分类结果。沿决策树从上到下遍历的过程中,在每个结点都会遇到一个测试,对每个结点上问题的不同的测试输出导致不同的分支,最后会到达一个叶子结点,这个过程就是利用决策树进行分类的过程,利用若干个变量来判断所属的类别。

ID3算法数据描述

所使用的样本数据有一定的要求,ID3是:

  描述-属性-值相同的属性必须描述每个例子和有固定数量的价值观。
  预定义类-实例的属性必须已经定义的,也就是说,他们不是学习的ID3。
  离散类-类必须是尖锐的鲜明。连续类分解成模糊范畴(如金属被“努力,很困难的,灵活的,温柔的,很软”都是不可信的。
  足够的例子——因为归纳概括用于(即不可查明)必须选择足够多的测试用例来区分有效模式并消除特殊巧合因素的影响。
  ID3决定哪些属性如何是最好的。一个统计特性,被称为信息增益,使用熵得到给定属性衡量培训例子带入目标类分开。信息增益最高的信息(信息是最有益的分类)被选择。为了明确增益,我们首先从信息论借用一个定义,叫做熵。每个属性都有一个熵。

ID3决策树概述

  ID3决策树是一种非常重要的用来处理分类问题的结构,它形似一个嵌套N层的IF…ELSE结构,但是它的判断标准不再是一个关系表达式,而是对应的模块的信息增益。它通过信息增益的大小,从根节点开始,选择一个分支,如同进入一个IF结构的statement,通过属性值的取值不同进入新的IF结构的statement,直到到达叶子节点,找到它所属的“分类”标签。

  它的流程图是一颗无法保证平衡的多叉树,每一个父节点都是一个判断模块,通过判断,当前的向量会进入它的某一个子节点中,这个子节点是判断模块或者终止模块(叶子节点),当且仅当这个向量到达叶子节点,它也就找到了它的“分类”标签。

  ID3决策树通过一个固定的训练集是可以形成一颗永久的“树”的,这课树可以进行保存并且运用到不同的测试集中,唯一的要求就是测试集和训练集需要是结构等价的。这个训练过程就是根据训练集创建规则的过程,这也是机器学习的过程。

  ID3决策树的一个巨大缺陷是:它将产生过度匹配问题。这里在不讨论信息增益的前提下,有这样一个例子:人的属性中有性别和年龄两个属性,由于人的性别只有男和女两种,年龄有很多种分支,当它有超过两个分支的时候,在用信息增益选择新的属性的时候,会选择年龄而不是性别,因为ID3决策树在使用信息增益来划分数据集的时候会倾向于选择属性分支更多的一个;另外一个缺陷是,人的年龄假定为1~100,如果不进行离散化,即区间的划分,那么在选择年龄这个属性的时候,这棵决策树会产生最多100个分支,这是非常可怕而且浪费空间和效率的,考虑这 样一种情况:两个人的其他所有属性完全相同,他们的分类都是"A",然而在年龄这一个树节点中分支了,而这个年龄下有一个跟这两个人很像,却不属于“A”类别的人,由于ID3决策树无法处理连续性数据,那么这两个人很有可能被划分到两个分类中,这是不合理的,这也是C4.5决策树考虑的问题。

ID3决策树算法推导

  如果以前没有接触过决策树,完全不用担心,它的概念非常简单,即使不知道它也可以通过简单的图像了解其工作原理,下图就是一个决策树,正方形代表判断模型(decision block),椭圆形代表终止模块(terminating block),表示已经得出结论,可以终止运行。从判断模块引出的左右箭头称作分支(branch),它首先检测发送邮件域名地址。如果地址为myEmployer.com,则将其分类“无聊时需要阅读的邮件”中。如果邮件不是来自这个域名,则检查邮件内容里是否包含单词曲棍球,如果包含则将邮件归类到“需要及时处理的盆友邮件”,如果不包含则将邮件归类到“无需阅读的垃圾邮件”。

  决策树很多任务都是为了数据中蕴含的知识信息,因此决策树可以使用不熟悉的数据集合,并从中提取出一系列的规则,机器学习算法最终将使用这些机器从数据及中创造的规则。专家系统中经常使用决策树,而且决策树给出结果往往可以匹敌在当前领域具有几十年工作经验的人类专家。

  现在我们已经大致了解了决策树可以完成哪些任务,接下来我们将学习如何从一堆原始数据中构造决策树,首先我们讨论构造决策树的方法,以及如何编写决策树的Python代码;接着剔除一些度量算法成功率的方法;最后使用递归建立分类器,并且使用Matplotlib绘制决策树图,构造完成决策树分类器之后,我们将输入一些隐形眼镜的处方数据,并由决策树分类器预测需要的镜片类型。

1,决策树的构造

  在一步步地构造决策树算法的时候,首先我们讨论数学上如何使用信息论划分数据集,然后编写代码将理论应用到具体的数据集上,最后编写代码构建决策树。

  在构造决策树时,我们需要解决的第一个问题就是,当前数据集上哪个特征在划分数据分类时起决定性作用。为了找到决定性的特征,划分出最好的结果,我们必须评估每个特征。完成测试之后,原始数据集就被划分为几个数据子集,这些数据子集会分布在第一个决策点的所有分支上,如果某个分支下的数据属于同一类型,则当前无需阅读的垃圾邮件已经正确的划分数据分类,无需进一步对数据集进行分割,如果数据子集内的数据不属于同一类型,则需要重复划分数据子集的过程,如何划分数据子集的算法和划分原始数据集的方法相同,知道所有具有相同类型的数据均在一个数据子集内。

  创建分支的伪代码函数createBranch() 如下所示:

检测数据集中的每个子项是否属于同一分类: If  so  retrun类标签; Else寻找划分数据集的最好特征划分数据集创建分支节点 for  每个划分的子集  调用函数createBranch并增加返回结果到分支节点中  return  分支节点

  上面的伪代码createBranch是一个递归函数,在倒数第二行直接调用了它自己,后面我们将把上面的伪代码转换为Python代码,这里我们需要了解一下算法是如何划分数据集的。

1.1 决策树的一般流程

  • (1) 收集数据:可以使用任何方法
  • (2) 准备数据:树构造算法只适用于标称型数据,因此数值型数据必须离散化
  • (3) 分析数据:可以使用任何方法,构造树完成之后,我们应该检查图像是否符合预期
  • (4) 训练算法:构造树的数据结构
  • (5) 测试算法:使用经验树计算错误率
  • (6)使用算法:此步骤可以适用于任何监督学习算法,而使用决策树可以更好的理解数据的内在含义

1.2 划分特征

  一些决策树算法采用二分法划分数据,此处不采用这种方法,本次将使用ID3算法划分数据集,该算法处理如何划分数据集,何时停止划分数据集。如果依据某个属性划分数据将会产生4个可能的值,我们将数据划分为四块,并创建四个不同的分支,每次划分数据集时我们只选取一个特征属性,如果训练集中存在20个特征,第一次我们选择哪个特征作为划分的参考属性呢?

  下表的数据包含5个海洋动物,特征包括:不浮出水面是否可以生存,以及是否有脚趾。我们可以将这些动物划分为两类:鱼类和非鱼类,现在我们想要决定依据第一个特征还是第二个特征划分数据

1.3 信息增益

  划分数据集的大原则是:将无序的数据变得更加有序。我们可以使用多种方法划分数据集,但是每种方法都有各自的优缺点。组织杂乱无章数据的一种方法就是使用信息论度量信息,信息论是量化处理信息的分支科学。我们可以在划分数据之前使用信息论量化度量信息的内容。

  在划分数据集之前之后信息发生的变化成为信息增益,知道如何计算信息增益,我们就可以计算每个特征值划分数据集获得的信息增益,获得信息增益最高的特征就是最好的选择。

  在可以评测哪种数据划分方式是最好的数据划分之前,我们必须学习如何计算信息增益。集合信息的度量方式称为香农熵或者简称为熵(这名字来源于信息论之父克劳德*香农)

  熵定义为信息的期望值,在明白这个概念之前,我们必须知道信息的定义,如果待分类的事务可能划分在多个分类之中,则符号Xi的信息定义为:

  其中P(Xi)是选择该分类的概率。

  为了计算熵,我们需要计算所有类别所有可能值包含的信息期望值,通过下面的公式得到:

  其中n是分类的数目。

代码如下:

  此代码是使用Python计算给定数据集的信息熵。

from math import log# 计算数据的熵(entropy)def calcShannonRnt(dataSet): # 数据条数,计算数据集中实例的总数 numEntries = len(dataSet) labelCounts = {} for featVec in dataSet:  # 每行数据的最后一个类别(也就是标签)  currentLable = featVec[-1]  if currentLable not in labelCounts.keys():labelCounts[currentLable] = 0  # 统计有多少个类以及每个类的数量  labelCounts[currentLable]= 1 shannonEnt = 0.0 for key in labelCounts:  # 计算单个类的熵值  prob = float(labelCounts[key]) / numEntries  # 累加每个类的熵值  shannonEnt -= prob * log(prob , 2) return shannonEnt

  下面我们创建一个简单的数据集(此处我们使用机器学习实战中的简单鱼鉴定数据集):

# 创建数据集def createDataSet(): dataSet = [[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']] labels = ['no surfacing','flippers'] return dataSet,labels

  代码执行结果:

myData,labels = createDataSet()print(myData)print(labels)shannonEnt = calcShannonRnt(myData)print(shannonEnt)'''[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]['no surfacing', 'flippers']0.9709505944546686'''

  从结果来看,熵为0.97,熵越高,则混合的数据也越多,随机变量的不确定性越大,我们可以在数据集中添加更多的分类,观察熵是如何变化的。

2,划分数据集

  上面我们学习了如何度量数据集的无序程度,分类算法除了需要测量信息熵,还需要划分数据集,度量划分数据集的熵,以便判断当前是否正确地划分了数据集,我们将对每个特征划分数据集的结果计算一次信息熵,然后判断按照哪个特征划分数据集是最好的划分方式。想象一个分布在二维空间的数据散点图,需要在数据之间画条线,将他们分成两部分,我们应该按照x轴还是y轴划分呢?

  按照给定特征划分数据集代码:

# 按照给定特征划分数据集def splitDataSet(dataSet,axis,value): ''' :param dataSet: 待划分的数据集 :param axis: 划分数据集的特征 :param value: 特征的返回值 :return: ''' retDataSet = [] for featVec in dataSet:  # 如果发现符合要求的特征,将其添加到新创建的列表中  if featVec[axis] == value:reduceFeatVec = featVec[:axis]reduceFeatVec.extend(featVec[axis 1:])retDataSet.append(reduceFeatVec) return retDataSet

  我们使用划分数据集测试一下,可以看到划分数据集结果如下:

myData,labels = createDataSet()print(myData)print(labels)splitDataSetVal = splitDataSet(myData,0,1)print(splitDataSetVal)splitDataSetVal = splitDataSet(myData,0,0)print(splitDataSetVal)'''[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]['no surfacing', 'flippers'][[1, 'yes'], [1, 'yes'], [0, 'no']][[1, 'no'], [1, 'no']]'''

  接下来,我们将遍历整个数据集,循环计算香农熵和splitDataSet()函数,找到最好

源文地址:https://www.guoxiongfei.cn/cntech/8273.html