北京大学信息管理系《数据挖掘导论》讲义第五章自动分类北京大学信息管理系2016年秋
北京大学信息管理系 《数据挖掘导论》讲义 第五章 自动分类 北京大学信息管理系 2016 年秋
北京大学信息管理系数据挖掘导论第五章自动分类目录第五章自动分类5.1概述：25.1.1什么是分类..5.1.2分类的一般步骤35.2Rocchio方法45.3k-近邻法.55.4决策树方法65.4.1决策树的概念.65.4.2属性选择度量...65.4.3决策树的常用算法....105.5贝叶斯方法..115.5.1贝叶斯原理....115.5.2朴素贝叶斯分类115.6分类结果评估，135.6.1常用评估度量..135.6.2文本分类的评估.145.7自动分类的案例与软件操作.155.7.1决策树案例（SPSSModeler）.155.7.2决策树案例（R语言）...19参考文献..191
北京大学信息管理系 数据挖掘导论 第五章自动分类 1 目录 第五章 自动分类. 2 5.1 概述. 2 5.1.1 什么是分类.2 5.1.2 分类的一般步骤.3 5.2 Rocchio 方法. 4 5.3 k-近邻法. 5 5.4 决策树方法. 6 5.4.1 决策树的概念.6 5.4.2 属性选择度量.6 5.4.3 决策树的常用算法.10 5.5 贝叶斯方法. 11 5.5.1 贝叶斯原理.11 5.5.2 朴素贝叶斯分类.11 5.6 分类结果评估. 13 5.6.1 常用评估度量.13 5.6.2 文本分类的评估.14 5.7 自动分类的案例与软件操作. 15 5.7.1 决策树案例（SPSS Modeler） .15 5.7.2 决策树案例（R 语言）.19 参考文献. 19
北京大学信息管理系数据挖掘导论第五章自动分类第五章自动分类分类问题是一个普遍存在的问题。在图书情报领域，文献信息就有很多种分类方法，美国的杜威十进制图书分类法、美国国会图书馆图书分类法，以及我国的中国图书馆分类法等等。以中图法为例，它包括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
北京大学信息管理系 数据挖掘导论 第五章自动分类 3 表 5-1 脊椎动物的数据集 表 5-2 毒蜥的数据集 5.1.2 分类的一般步骤 数据分类是一个两阶段过程，包括学习阶段（即构建分类模型）和分类阶段（即使用模 型预测给定数据的类标号）。 在第一阶段，首先需要一个训练集（training set），它由数据库元组和与它们相关联的类 标号记录组成，我们使用训练集来建立分类模型。由于提供了每个训练元组的类标号，这一 阶段也称为监督学习（supervised learning），即分类器的学习在被告知每个训练元组属于哪 个类的“监督”下进行的。它不同于无监督学习（unsupervised learning），即上一章提到过的聚 类，每个训练元组的类标号未知，并且要学习的类的个数或集合也可能事先不知道。 接下来的第二阶段，我们就可以使用得到的分类模型进行分类，但首先需要评估分类器 的预测准确率。如果我们使用训练集来度量分类器的准确率，则评估可能过于乐观，因为分 类器趋向于过分拟合（over fit）该数据（即在学习期间，它可能包含了训练数据中的某些特 定的异常，这些异常并不已定会在一般数据集中出现）。因此，需要使用检验集（test set）来 验证所得分类模型的准确率。所谓检验集是指独立于训练元组（即不使用它们构造分类器）， 同样具有类标号的集合。 需要注意的是，分类适合预测二元或名称类型的数据集，对于序数分类（例如把人分成 高收入、中收入和低收入），分类不太有效，因为它不考虑隐含在目标类中的序关系。 图 5-1 为自动文本分类的一般过程
数据挖掘导论第五章自动分类北京大学信息管理系待分类中分类算法预处理向量表示文网页+特征选候选类列表训练集实取算法预处理例特征项向+量表示每个类的阈值诚值策略→校验集训练测试结果类别表分类过程训练过程图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、它假设训练数据是绝对正确的，因为它没有任何定量衡量样本是否含有噪声的机制， 因而也就对错误数据毫无抵抗力。 待分类中 文网页 预处理 向量表示 训练集实 例 预处理 特征选 取算法 分类算法 校验集 测试 每个类的阈值 训练 结果类别表 阈值 策略 候选类列表 特征项向 量表示 训练过程 分类过程