北京大学：《大数据分析与挖掘》课程教学资源（讲义）第五章自动分类.pdf_大学文库

北京大学信息管理系数据挖掘导论第五章自动分类第五章自动分类分类问题是一个普遍存在的问题。在图书情报领域，文献信息就有很多种分类方法，美国的杜威十进制图书分类法、美国国会图书馆图书分类法，以及我国的中国图书馆分类法等等。以中图法为例，它包括5个大类（马列主义和毛泽东思想、哲学、社会科学、自然科学、综合性图书），22个小类（政治、法律、军事、经济、文化、语言.....），假设图书馆引进一本新书，馆员就需要将该书分类到一个具体的类别中，从而方便用户查阅。网络文本同样需要分类，但由于其数量庞大，人工分类显然效率较低。文档自动分类可解决这个问题，它是指在给定的分类体系下，根据文本的内容用计算机程序确定文本所属类别，一般采用机器学习的方法进行自动文本分类。本章介绍分类的基本概念，然后我们将学习四种分类的基本方法（Rocchio方法、k-近邻法、决策树、以及贝叶斯），最后通过探讨分类结果的度量指标，以求评估和比较不同的分类方法。5.1概述分类是一种重要的数据分析形式，通过提取刻画数据类的模型，从而预测分类的类标号。例如银行贷款员通过分析数据，将贷款申请者分为“安全”和“风险”两类；超市经理通过对购物篮和客户基本信息的分析，猜测具有某些特征的顾客是否会购买新的计算机：医学研究人员通过分析乳腺癌数据，以便预测病人应当接受三种具体治疗方案中的哪一种。本节首先介绍分类的概念，然后描述该方法实施的一般步骤。5.1.1什么是分类在介绍分类的概念之前，首先应明确什么是类。类是指一组具有某一共同属性的事物对象的集合。分类（classification）就是通过学习得到一个目标函数（targetfunction）J，把每个属性集x映射到一个预先定义的类标号y。目标函数也称为分类模型（classificationmodel)，或分类器（classifier）。类标号是如前文所述预测病人应当接受三种具体治疗方案中对应的“治疗方案A”、“治疗方案B”或“治疗方案C"。这些类别可以用离散值表示，其中值之间的次序没有意义。例如，可以使用值1、2和3表示上面的治疗方案A、B和C，其中这组治疗方案之间并不存在蕴含的序。例5.1分类。表5-1说明了哪些特征决定一种脊椎动物究竞是哺乳类、爬行类、鸟类、鱼类还是两栖类。通过对该数据建立分类模型，可以预测未知记录的类标号。例如，假设有-种叫做毒蜥的生物，其特征如表5-2，便可根据表5-1中数据集建立的分类模型确定该生物所属的类。分类模型可以看做是一个黑箱，因为有时候我们并不知道该模型究竞具体是依据输入属性的哪些方面。2

北京大学信息管理系数据挖掘导论第五章自动分类 2 第五章自动分类分类问题是一个普遍存在的问题。在图书情报领域，文献信息就有很多种分类方法，美国的杜威十进制图书分类法、美国国会图书馆图书分类法，以及我国的中国图书馆分类法等等。以中图法为例，它包括 5 个大类（马列主义和毛泽东思想、哲学、社会科学、自然科学、综合性图书），22 个小类（政治、法律、军事、经济、文化、语言.），假设图书馆引进一本新书，馆员就需要将该书分类到一个具体的类别中，从而方便用户查阅。网络文本同样需要分类，但由于其数量庞大，人工分类显然效率较低。文档自动分类可解决这个问题，它是指在给定的分类体系下，根据文本的内容用计算机程序确定文本所属类别，一般采用机器学习的方法进行自动文本分类。本章介绍分类的基本概念，然后我们将学习四种分类的基本方法（Rocchio 方法、k-近邻法、决策树、以及贝叶斯），最后通过探讨分类结果的度量指标，以求评估和比较不同的分类方法。 5.1 概述分类是一种重要的数据分析形式，通过提取刻画数据类的模型，从而预测分类的类标号。例如银行贷款员通过分析数据，将贷款申请者分为“安全”和“风险”两类；超市经理通过对购物篮和客户基本信息的分析，猜测具有某些特征的顾客是否会购买新的计算机；医学研究人员通过分析乳腺癌数据，以便预测病人应当接受三种具体治疗方案中的哪一种。本节首先介绍分类的概念，然后描述该方法实施的一般步骤。 5.1.1 什么是分类在介绍分类的概念之前，首先应明确什么是类。类是指一组具有某一共同属性的事物对象的集合。分类（classification）就是通过学习得到一个目标函数（target function）f，把每个属性集 x 映射到一个预先定义的类标号 y。目标函数也称为分类模型（classification model），或分类器（classifier）。类标号是如前文所述预测病人应当接受三种具体治疗方案中对应的 “治疗方案 A”、“治疗方案 B”或“治疗方案 C”。这些类别可以用离散值表示，其中值之间的次序没有意义。例如，可以使用值 1、2 和 3 表示上面的治疗方案 A、B 和 C，其中这组治疗方案之间并不存在蕴含的序。例 5.1 分类。表 5-1 说明了哪些特征决定一种脊椎动物究竟是哺乳类、爬行类、鸟类、鱼类还是两栖类。通过对该数据建立分类模型，可以预测未知记录的类标号。例如，假设有一种叫做毒蜥的生物，其特征如表 5-2，便可根据表 5-1 中数据集建立的分类模型确定该生物所属的类。分类模型可以看做是一个黑箱，因为有时候我们并不知道该模型究竟具体是依据输入属性的哪些方面

北京大学信息管理系数据挖掘导论第五章自动分类表5-1脊椎动物的数据集有腿冬眠类标号胎生水生动物飞行动物表皮覆盖名字体温否是否哺乳类香是人类毛发恒温是否香否爬行类否鳞蛇冷血鳞片否否鱼类香鳞片否是鲑鱼冷血香哺乳类是是香否鲸恒温毛发半香是是两栖类无香冷血青蛙否否否是爬行类鳞片否冷血巨蜥否是是是哺乳类是蝙蝠恒温毛发是否鸟类是羽毛否否鸽子恒温是否香是否哺乳类猫恒温软毛否否否鱼类是是冷血鳞片豹纹蟹否半否是爬行类鳞片否海龟冷血是香鸟类否半否企鹅恒温羽毛是是否哺乳类恒温刚毛是否豪猪鳗鳞片香是否否香鱼类冷血香半否是是两栖类无蛛螺冷血毒蜥的数据集表 5-2胎生飞行动物有冬眠类标号名字体湿表皮暖箭水生动物否是是?寿斯冷血续片香否5.1.2分类的一般步骤数据分类是一个两阶段过程，包括学习阶段（即构建分类模型）和分类阶段（即使用模型预测给定数据的类标号）。在第一阶段，首先需要一个训练集（trainingset），它由数据库元组和与它们相关联的类标号记录组成，我们使用训练集来建立分类模型。由于提供了每个训练元组的类标号，这阶段也称为监督学习（supervised learning），即分类器的学习在被告知每个训练元组属于哪个类的"监督”下进行的。它不同于无监督学习（unsupervised learning），即上一章提到过的聚类，每个训练元组的类标号未知，并且要学习的类的个数或集合也可能事先不知道。接下来的第二阶段，我们就可以使用得到的分类模型进行分类，但首先需要评估分类器的预测准确率。如果我们使用训练集来度量分类器的准确率，则评估可能过于乐观，因为分类器趋向于过分拟合（overfit）该数据（即在学习期间，它可能包含了训练数据中的某些特定的异常，这些异常并不已定会在一般数据集中出现）。因此，需要使用检验集（testset）来验证所得分类模型的准确率。所谓检验集是指独立于训练元组（即不使用它们构造分类器），同样具有类标号的集合。需要注意的是，分类适合预测二元或名称类型的数据集，对于序数分类（例如把人分成高收入、中收入和低收入），分类不太有效，因为它不考虑隐含在目标类中的序关系。图5-1为自动文本分类的一般过程。3

数据挖掘导论第五章自动分类北京大学信息管理系待分类中分类算法预处理向量表示文网页+特征选候选类列表训练集实取算法预处理例特征项向+量表示每个类的阈值诚值策略→校验集训练测试结果类别表分类过程训练过程图5-1自动文本分类的一般过程5.2Rocchio方法Rocchio算法是20世纪70年代左右在Salton的SMART系统中引入并广泛流传的一种相关反馈算法。其文本分类的原理为：每一类确定一个中心点（或代表元），计算待分类的文档与各类代表元间的距离，并作为判定是否属于该类的判据。具体的构造方法如下：给定一个类，训练集中所有属于这个类的文档对应向量的分量用正数表示，所有不属于这个类的文档对应向量的分量用负数表示，然后把所有的向量加起来，得到的和向量就是这个类的原型向量。Wkjwi=B.IPOSI(d,ePOS,]WkjMYNEGI[d,eNEG]定义两个向量的相似度为这两个向量夹角的余弦，然后逐一计算训练集中所有文档和原型向量的相似度，按一定的算法从中挑选某个相似度作为界。当给定一篇新的文档时，如果这篇文档与原型向量的相似度比界大，则这篇文档属于这个类，否则这篇文档就不属于这个类。简单来说，对于一个词集和一个分类，总有某些词，这些词一日出现属于这个分类的可能性就会增加；而另一些词一旦出现属于这个分类的可能性就会降低，那么累计这些正面和负面的影响因素，最后由文档分离出的词向量可以得到对于每个类的一个打分，打分越高属于该类的可能性就越大。Rocchio算法的突出优点是容易实现，计算（训练和分类）特别简单，通常用来实现衡量分类系统性能的基准系统，而实用的分类系统很少采用这种算法解决具体的分类问题，因为该算法做了两个致命的假设：1、它认为一个类别的文档仅仅聚集在一个中心的周围，而实际情况往往不是如此；2、它假设训练数据是绝对正确的，因为它没有任何定量衡量样本是否含有噪声的机制，因而也就对错误数据毫无抵抗力。4

北京大学信息管理系数据挖掘导论第五章自动分类 4 图 5-1 自动文本分类的一般过程 5.2 Rocchio 方法 Rocchio 算法是 20 世纪 70 年代左右在 Salton 的 SMART 系统中引入并广泛流传的一种相关反馈算法。其文本分类的原理为：每一类确定一个中心点（或代表元），计算待分类的文档与各类代表元间的距离，并作为判定是否属于该类的判据。具体的构造方法如下：给定一个类，训练集中所有属于这个类的文档对应向量的分量用正数表示，所有不属于这个类的文档对应向量的分量用负数表示，然后把所有的向量加起来，得到的和向量就是这个类的原型向量。定义两个向量的相似度为这两个向量夹角的余弦，然后逐一计算训练集中所有文档和原型向量的相似度，按一定的算法从中挑选某个相似度作为界。当给定一篇新的文档时，如果这篇文档与原型向量的相似度比界大，则这篇文档属于这个类，否则这篇文档就不属于这个类。简单来说，对于一个词集和一个分类，总有某些词，这些词一旦出现属于这个分类的可能性就会增加；而另一些词一旦出现属于这个分类的可能性就会降低，那么累计这些正面和负面的影响因素，最后由文档分离出的词向量可以得到对于每个类的一个打分，打分越高属于该类的可能性就越大。 Rocchio 算法的突出优点是容易实现，计算（训练和分类）特别简单，通常用来实现衡量分类系统性能的基准系统，而实用的分类系统很少采用这种算法解决具体的分类问题，因为该算法做了两个致命的假设： 1、它认为一个类别的文档仅仅聚集在一个中心的周围，而实际情况往往不是如此； 2、它假设训练数据是绝对正确的，因为它没有任何定量衡量样本是否含有噪声的机制，因而也就对错误数据毫无抵抗力。待分类中文网页预处理向量表示训练集实例预处理特征选取算法分类算法校验集测试每个类的阈值训练结果类别表阈值策略候选类列表特征项向量表示训练过程分类过程

北京大学信息管理系数据挖掘导论第五章自动分类另外，Rocchio算法还可用于查询扩展。假设这样一个情景，用户在搜索引擎里搜索“苹果”。当用户最开始搜索这个词时，搜索引擎并不知道用户需要的是属于水果的“苹果”，还是和“苹果”公司相关的“苹果”，所以它往往会尽量呈现出各种结果。当用户看到这些结果后，会点一些觉得相关的结果（即所谓的相关反馈）。然后搜索引擎可根据刚才的相关反馈，修改用户最初的查询向量取值，重新计算网页得分，把与刚才点击结果相似的页面排前面。例如，最开始搜索“苹果"时，对应的查询向量是(“苹果”：1)，当点击了一些与mac、iphone相关的结果后，搜索引擎会把初始查询向量修改为“苹果”：1“Mac”：0.8，“iPhone”：0.7}，通过这个新的查询向量，搜索引擎就能比较明确地知道用户要找的并不是属于水果的苹果了。5.3k-近邻法k-近邻法（k-nearestneighbor，kNN）是一种传统的基于统计的模式识别方法，距今已经有四十多年的历史。kNN分类算法思想很简单：如果一个样本在特征空间中的k个最相似（即特征空间中最邻近）的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。如图5-2所示，W1、W2和W3为已经知道分类的数据，对于新数据X来说，先跟已知数据里的每个点求距离，然后挑选离这个训练数据最近的k个点，用少数服从多数的原则给新数据归类，最后可得X属于wl类。0-人4图5-2kNN算法示例该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的k个邻居中大容量类的样本占多数。无论怎样，样本的数量并不能影响运行结果。我们可以采用权值的方法（和该样本距离小的邻居权值大）来改进。把邻居文档和测试文档的相似度作为邻居文档所在类的类权重。如果这k个邻居中的部分文档属于同一个类，则该分类中的每个邻居的类权重之和作为该类别和测试文档的相似度。通过对候选类评分的排序，然后给出一个阈值，就可以判定5

北京大学信息管理系数据挖掘导论第五章自动分类 5 另外，Rocchio 算法还可用于查询扩展。假设这样一个情景，用户在搜索引擎里搜索“苹果”。当用户最开始搜索这个词时，搜索引擎并不知道用户需要的是属于水果的“苹果”，还是和“苹果”公司相关的“苹果”，所以它往往会尽量呈现出各种结果。当用户看到这些结果后，会点一些觉得相关的结果（即所谓的相关反馈）。然后搜索引擎可根据刚才的相关反馈，修改用户最初的查询向量取值，重新计算网页得分，把与刚才点击结果相似的页面排前面。例如，最开始搜索“苹果”时，对应的查询向量是{“苹果”：1}，当点击了一些与 mac、iphone 相关的结果后，搜索引擎会把初始查询向量修改为{“苹果” : 1, “Mac” : 0.8, “iPhone” : 0.7}，通过这个新的查询向量，搜索引擎就能比较明确地知道用户要找的并不是属于水果的苹果了。 5.3 k-近邻法 k-近邻法（k-nearest neighbor，kNN）是一种传统的基于统计的模式识别方法，距今已经有四十多年的历史。 kNN 分类算法思想很简单：如果一个样本在特征空间中的 k 个最相似（即特征空间中最邻近）的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。如图 5-2 所示，w1、 w2 和 w3 为已经知道分类的数据，对于新数据 X 来说，先跟已知数据里的每个点求距离，然后挑选离这个训练数据最近的 k 个点，用少数服从多数的原则给新数据归类，最后可得 X 属于 w1 类。图 5-2 kNN 算法示例该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的 k 个邻居中大容量类的样本占多数。无论怎样，样本的数量并不能影响运行结果。我们可以采用权值的方法（和该样本距离小的邻居权值大）来改进。把邻居文档和测试文档的相似度作为邻居文档所在类的类权重。如果这 k 个邻居中的部分文档属于同一个类，则该分类中的每个邻居的类权重之和作为该类别和测试文档的相似度。通过对候选类评分的排序，然后给出一个阈值，就可以判定

北京大学信息管理系数据挖掘导论第五章自动分类测试文档的类别。KNN算法本身简单有效，它是一种情性学习算法，分类器不需要使用训练集进行训练训练时间复杂度为0。KkNN分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为n，那么kNN的分类时间复杂度为O(n)。5.4决策树方法决策树既可以做分类问题，也可以做回归。本节介绍决策树分类法，这是一种简单但却广泛使用的分类方法。5.4.1决策树的概念决策树（decisiontree）是一种类似于流程图的树结构，一般包含以下三种结点：根结点（rootnode）：没有入边，但有零条或多条出边；内部结点（internalnode）：恰有一条入边和两条或多条出边：·：叶结点（leafnode）：恰有一条入边，但没有出版。其中，每个内部结点（非树叶结点）表示在一个属性上的测试，每个分枝代表该测试的一个输出，而每个树叶结点存放一个类标号。树的最项层结点是根结点。内部结点用矩形表示，而叶结点用椭圆表示。决策树可以是二叉的，也可以是非二叉的（根据不同的决策树算法而定）。一棵典型的决策树如下图：age?senioryouthmiddie_agedstudent?credit_rating?yesfairexcellentnoyesnoyesyes图5-3买/不买电脑的决策树示意图一日构造了决策树，对检验记录进行分类就是直截了当的。从树的根结点开始，将测试条件用于检验记录，根据测试结果选择适当的分支。沿着该分支或者到达另一个内部结点，使用新的测试条件，或者到达一个叶结点。到达叶结点之后，叶结点的类称号就被赋值给该检验记录。5.4.2属性选择度量属性选择度量是一种选择分裂准则，把给定类标记的训练元组的数据分区D最好地"划分成单独类的启发式方法。理想情况下，D划分后的每个小分区都是纯的（即落在一个给定分区的所有元组都属于相同的类）。“最好的”分类准则是最接近这种情况的划分。常见的三种属性选择度量为一一信息增益、增益率和基尼指数。（1）信息增益介绍信息增益之前，首先应明确信息摘（entropy）的概念。摘用于量化一个随机变量的6

北京大学信息管理系数据挖掘导论第五章自动分类 6 测试文档的类别。 kNN 算法本身简单有效，它是一种惰性学习算法，分类器不需要使用训练集进行训练，训练时间复杂度为 0。kNN 分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为 n，那么 kNN 的分类时间复杂度为 O(n)。 5.4 决策树方法决策树既可以做分类问题，也可以做回归。本节介绍决策树分类法，这是一种简单但却广泛使用的分类方法。 5.4.1 决策树的概念决策树（decision tree）是一种类似于流程图的树结构，一般包含以下三种结点： • 根结点（root node）：没有入边，但有零条或多条出边； • 内部结点（internal node）：恰有一条入边和两条或多条出边； • 叶结点（leaf node）：恰有一条入边，但没有出版。其中，每个内部结点（非树叶结点）表示在一个属性上的测试，每个分枝代表该测试的一个输出，而每个树叶结点存放一个类标号。树的最顶层结点是根结点。内部结点用矩形表示，而叶结点用椭圆表示。决策树可以是二叉的，也可以是非二叉的（根据不同的决策树算法而定）。一棵典型的决策树如下图：图 5-3 买/不买电脑的决策树示意图一旦构造了决策树，对检验记录进行分类就是直截了当的。从树的根结点开始，将测试条件用于检验记录，根据测试结果选择适当的分支。沿着该分支或者到达另一个内部结点，使用新的测试条件，或者到达一个叶结点。到达叶结点之后，叶结点的类称号就被赋值给该检验记录。 5.4.2 属性选择度量属性选择度量是一种选择分裂准则，把给定类标记的训练元组的数据分区 D“最好地”划分成单独类的启发式方法。理想情况下，D 划分后的每个小分区都是纯的（即落在一个给定分区的所有元组都属于相同的类）。“最好的”分类准则是最接近这种情况的划分。常见的三种属性选择度量为——信息增益、增益率和基尼指数。（1）信息增益介绍信息增益之前，首先应明确信息熵（entropy）的概念。熵用于量化一个随机变量的

北京大学信息管理系数据挖掘导论第五章自动分类 7 不确定程度；信息熵可理解为某种特定信息的出现概率（离散随机事件的出现概率）。对于二元变量，其计算公式为： H=-p×log(p)-(1-p)×log(1-p) 例 5.2 信息熵。假设我们需要预测某个班随机抽出一名同学的性别，该班级共有 10 名同学。当该班级全部为男生时（即抽出男生的比例 p 为 1），可计算出此时的熵 H0=0；当该班级的男女生比例为 9:1 时（即抽出男生的比例 p 为 0.9），可计算出此时的熵 H1=0.14；当该班级的男女生比例为 5:5 时（即抽出男生的比例 p 为 0.5），可计算出此时的熵 H5=0.3；当该班级全部为女生时（即抽出男生的比例 p 为 0），可计算出此时的熵 H10=0。据此，可大致绘出随抽出男生比例变化的熵变化曲线（图 5-4）。图 5-4 熵的变化曲线图从上面的例子可看出，信息熵是用来衡量一个随机变量出现的期望值，一个变量的信息熵越大，那么他出现的各种情况也就越多，也就是包含的内容多，我们要描述他就需要更多的信息才能确定这个变量。推广到多个变量的情况也同样，例如在考虑中英文语言的模型时，只考虑字频的话英文是 4.46 比特/字符的信息熵，汉字是 9.6 比特/字符，直观上很容易理解，英文字母只有 26 个，所以描述一个字母所需要的信息表示不多，而中文字却很多，就需要更多的信息量才能表示。对于多个变量，信息熵的公式如下：信息增益（information gain）就是当我们得知某个相关条件后信息熵的差。对数据集 D 来说，pi为 D 中属于类 Ci的概率，其信息熵可表示为 ( ) log2( ) 1 i m i Info D  pi p    当我们得知某个条件 A，用 A 将 D 分为了 v 个部分后，此时的信息熵为 ( ) | | | | ( ) 1 j v j j A I D D D Info D     则已知条件 A 后该数据的信息增益为

北京大学信息管理系数据挖掘导论第五章自动分类有两个改进策略，一个是限制测试条件只能是二元划分；另一个是修改评估划分的标准，把属性测试条件的输出数量考虑进去。增益率就使用了后者。增益率（gainratio）的公式为Grain(A)GrianRate(A)SplitInfo^(D)其中Splitlnfo为分裂信息（splitinformation）值，被用来衡量属性分裂数据的广度和均匀。它代表由训练数据集D划分成对应于属性A测试的v个输出的个分区产生的信息。D×10g2=一Splitlr(D D在决策树中，我们选择具有最大增益率的属性作为分裂属性。然而需要注意的是，随着划分信息趋向于0，该比率变得不稳定。为了避免这种情况，增加一个约束：选取的测试的信息增益必须较大，至少与考察的所有测试的平均增益一样大。比如我们可以先计算每个属性的增益，然后仅对那些增益高过平均值的属性应用增益率测试。例5.4增益率。例5.3中提到的属性income将数据划分成了3个分区，即low、medium和high，分别包含4、6和4个元组。为了计算income的增益率，首先算出其分裂信息值：446644= 1.557×log214-14×10g2 14~ 14× log2 14Splitlnfoa(D) =-14由例5.3得到Gain（income）=0.029，因此可得到它的增益率为GainRatio（income）=0.029/1.557=0.019。（3）基尼指数基尼指数（Giniindex）是一种不等性度量，由意大利统计学家CorradoGini提出，并于1912年发表在他的文章"Variabilitaemutabilita"中。它通常用来度量收入不平衡，但是它可以用来度量任何不均匀分布。Gini指数是一个0一1之间的数。其中0对应于完全相等（其中每个人都具有相同的收入），而1对应于完全不相等（其中一个人具有所有收入，而其他人收入都为零）。基尼指数度量数据分区或训练元组集D的不纯度，定义为：mGn(D) =1-2n其中p是D中元组属于C类的概率，对m个类计算和。考虑A是离散值属性的情况，其中A具有v个不同值出现在D中。如果A具有v个可能的值，则存在2v个可能的子集。例如，如果income具有3个可能的值(low,medium,high)，则可能的子集具有8个。不考虑幂集（low,medium,high））和空集（），因为从概念上讲，它不代表任何分裂。因此，基于A的二元划分，存在2v-2中形成数据集D的两个分区的可能方法。当考虑二元划分裂时，计算每个结果分区的不纯度的加权和。例如，如果A的二元划分将D划分成D和D2，则给定该划分，D的基尼指数为9

北京大学信息管理系数据挖掘导论第五章自动分类 9 有两个改进策略，一个是限制测试条件只能是二元划分；另一个是修改评估划分的标准，把属性测试条件的输出数量考虑进去。增益率就使用了后者。增益率（gain ratio）的公式为其中 SplitInfo 为分裂信息（split information）值，被用来衡量属性分裂数据的广度和均匀。它代表由训练数据集 D 划分成对应于属性 A 测试的 v 个输出的 v 个分区产生的信息。在决策树中，我们选择具有最大增益率的属性作为分裂属性。然而需要注意的是，随着划分信息趋向于 0，该比率变得不稳定。为了避免这种情况，增加一个约束：选取的测试的信息增益必须较大，至少与考察的所有测试的平均增益一样大。比如我们可以先计算每个属性的增益，然后仅对那些增益高过平均值的属性应用增益率测试。例 5.4 增益率。例 5.3 中提到的属性 income 将数据划分成了 3 个分区，即 low、medium 和 high，分别包含 4、6 和 4 个元组。为了计算 income 的增益率，首先算出其分裂信息值：由例 5.3 得到 Gain（income）=0.029，因此可得到它的增益率为 GainRatio（income） =0.029/1.557=0.019。（3）基尼指数基尼指数（Gini index）是一种不等性度量，由意大利统计学家 Corrado Gini 提出，并于 1912 年发表在他的文章“Variabilita e mutabilita”中。它通常用来度量收入不平衡，但是它可以用来度量任何不均匀分布。Gini 指数是一个 0—1 之间的数。其中 0 对应于完全相等（其中每个人都具有相同的收入），而 1 对应于完全不相等（其中一个人具有所有收入，而其他人收入都为零）。基尼指数度量数据分区或训练元组集 D 的不纯度，定义为：其中 pi 是 D 中元组属于 Ci类的概率，对 m 个类计算和。考虑 A 是离散值属性的情况，其中 A 具有 v 个不同值出现在 D 中。如果 A 具有 v 个可能的值，则存在 2v 个可能的子集。例如，如果 income 具有 3 个可能的值{low, medium, high}，则可能的子集具有 8 个。不考虑幂集（{ low, medium, high}）和空集（{ }），因为从概念上讲，它不代表任何分裂。因此，基于 A 的二元划分，存在 2 v -2 中形成数据集 D 的两个分区的可能方法。当考虑二元划分裂时，计算每个结果分区的不纯度的加权和。例如，如果 A 的二元划分将 D 划分成 D1 和 D2，则给定该划分，D 的基尼指数为

北京大学：《大数据分析与挖掘》课程教学资源（讲义）第五章 自动分类

北京大学：《大数据分析与挖掘》课程教学资源（讲义）第五章自动分类