第5章分类分类知识反映同类事物的共同特征和不同事物的差异特征。分类(classification)是人类认识世界的一种重要方法,对于事物的认识大多是通过分门别类进行的。在数据挖掘领域,分类是从一个已知类别的数据集到一组预先定义的、非交叠的类别的映射过程。其中映射关系的生成以及映射关系的应用是数据挖掘分类算法主要的研究内容。映射关系就是常说的分类器(也称分类模型或分类函数),映射关系的应用就是使用分类器将测试数据集中的数据划分到给定类别中的某个类别的过程。
分类从历史的特征数据中构造出特定对象的分类模型(分类器),用来对未来数据进行预测分析,属于数据挖掘中的预测任务挖掘。分类技术使用的历史训练样本数据有确定的类标号,所以分类属于机器学习中的有监督学习。分类技术具有非常广泛的应用领域,如医疗诊断、信用卡系统的信用分级、图像模式识别、网络数据分类等。机器学习、专家系统、统计学和神经网络等领域的研究人员已经提出了许多具体的分类方法。目前比较常用的分类方法有K近邻(KNN)分类、贝叶斯分类、决策树和神经网络等。本章介绍分类的基本概念和基本的分类算法,第6章将介绍一些高级的分类算法。
5.1基 本 概 念
分类的目的是得到一个分类器(也称作分类模型),通过得到的分类器能把测试集中的测试数据映射到给定类别中的某个类别,实现对该数据的预测性描述。分类可用于提取描述重要数据类的模型或预测未来的数据趋势。本节首先介绍分类的概念，然后介绍分类的过程、分类器常见的构造方法以及分类器的评价标准。
5.1.1什么是分类
对于餐饮企业而言,数据分析极为重要,如搞清楚不同时节菜品的历史销售情况,分析不同因素影响下顾客的增加、流失情况等。数据分析的一项任务就是分类。分类方法用于预测数据对象的离散类别。如顾客对菜品种类A、B、C的喜好,贷款申请的“安全”或“危险”。这些类别可以用离散值表示,这些值之间没有次序。例如,可以使用值1、2、3表示菜品种类A、B、C,这3个菜品种类之间并不存在次序。下面介绍与分类相关的几个重要概念。
1. 数据对象和属性
数据集由数据对象组成。数据集中的数据对象代表一个实体。
属性也称字段,表示数据对象的一个特征。每个数据对象都由若干个属性组成。
2. 分类器
分类的关键是找出一个合适的分类器，也就是分类函数或分类模型。分类的过程是依据已知的样本数据构造一个分类函数或者分类模型。该分类函数或分类模型能够把数据库中的数据对象映射到某个给定的类别中,从而确定数据对象的类别。
3. 训练集
分类的样本数据集合称为训练集,是构造分类器的基础。训练集由数据对象组成,每个数据对象的所属类别已知。在构造分类器时,需要输入包含一定样本数据的训练集。选取的训练集是否合适,直接影响到分类器性能的好坏。
数据挖掘算法与应用(Python实现)第5章分类4. 测试集
与训练集一样,测试集也是由类别属性已知的数据对象组成的。测试集用来测试基于训练集构造的分类器的性能。在分类器产生后,由分类器判定测试集对象的所属类别，再与测试集中已知的所属类别进行比较,得出分类器的正确率等一系列评价性能。
下面给出分类问题的形式化定义。给定一个数据集 D={t1,t2,…,tn}和一组类 C={C1,C2，…,Cm},分类问题是确定一个映射 f: D→C,使得每个数据对象ti被分配到某个类中。一个类Cj包含映射到该类中的所有数据对象,C构成数据集D的一个划分,即Cj={ti | f(ti)=Cj,1 ≤ i ≤ n, ti∈D},并且Cj∩Ci=。
分类问题的样本数据(训练集)是由一个个数据对象组成的。每一个数据对象包含若干个属性,组成一个特征向量。训练集中的每一个数据对象有一个特定的类别属性(类标号)。该类标号是分类系统的输入,通常是历史经验数据。分析样本数据,通过训练集中的样本数据表现出的特性,为每个类找到一种准确的描述或者模型。基于此模型对未来的测试数据进行分类,就是类别预测。
另外,如果上面介绍的过程所构造的模型预测的是连续值或有序值,而不是离散的类标号，这种模型通常叫预测器(predictor)。在通常情况下,将离散的类标号预测叫分类,将连续的数值预测叫回归分析(regression analysis)。分类和回归分析是预测问题的两种主要类型。例如,销售经理希望预测一位顾客在一次购物过程中将花多少钱，该数据分析任务就是数值预测,也叫回归分析。
5.1.2分类的过程
从例子中学习(learning from examples)是机器学习中最常用的方法。对于分类来说,就是根据带有类标号的样本例子建立分类模型,应用此分类模型对测试样本进行类标号预测。分类过程主要包含两个步骤: 建立模型和应用模型进行分类。
第一步: 建立模型。
建立模型就是通过分析由属性描述的数据集来构造分类器模型。每个样本数据都属于一个预定义的类,由一个称作类标号的属性确定。例如，对于样本数据X,x是该数据的常规属性,y是该数据的类标签属性,X就可以简单地表示为二维关系X(x,y)。其中，x往往包含多个特征值,是多维向量。由于训练集提供了每个训练样本的类标号,所以建模过程是有监督学习,即模型的学习过程是在被告知每个训练样本属于哪个类的监督下进行的。
分类模型的表示形式有分类规则、决策树以及等式、不等式、规则式等。分类模型对历史数据的分布进行了归纳,可以用于对测试数据样本进行分类,也有助于更好地理解数据集的内容或含义。
图5.1给出了利用某校教师情况数据库建立分类模型的过程。训练数据的常规属性有name(名字)、rank(职称)和years(工龄),类标号属性是tenured(是否获得终身职位)。分类模型以分类规则的形式提供。
图5.1建立分类模型示例
第二步: 应用分类模型进行分类。
首先根据特定领域对分类模型的性能要求,对第一步建立的分类模型的性能进行科学评估,具体评估方法在5.5节中详细描述。如果该分类模型满足研究领域的性能要求,就可以用该分类模型对类标号未知的数据或对象进行分类。例如,在图5.2中，通过分析现有教师数据得到的分类规则可以用来预测新入职的或未来招聘的教师是否能够获得终身职位。
图5.2用分类模型进行分类
简单地说,模型的建立就是使用训练数据进行学习的过程,模型的应用就是对类标号未知的数据进行分类的过程。
5.1.3分类器常见构造方法
从构造分类器依据的理论来源看,分类器常见的构造方法有数理统计方法、机器学习方法和神经网络方法等。
(1) 数理统计方法包括贝叶斯方法和非参数方法。常见的KNN算法就属于非参数方法。
(2) 机器学习方法包括决策树法和规则归纳法。
(3) 神经网络方法主要是BP算法。
(4) 其他方法包括粗糙集方法、遗传算法等。
从构造分类器使用的技术来分,可以将分类器构造方法分为4种类型: 
(1) 基于距离的分类方法，主要是KNN算法。
(2) 决策树分类方法，主要有ID3、C4.5等。
(3) 贝叶斯方法，主要包括朴素贝叶斯方法、最大期望算法。
(4) 规则归纳方法，主要包括AQ算法、CN2算法和FOIL算法。
5.2KNN 分 类
古语“物以类聚,人以群分”和“近朱者赤,近墨者黑”都解释了周围环境对人的巨大影响,对于一个人，可以从其朋友和亲属的品性作出大概的判断。同理,分类时也可以通过与测试数据最接近的训练样本的类别来进行判断。Cover和Hart于1968年提出了KNN算法。该算法通过计算每个训练数据到待分类数据的距离,选择与待分类数据距离最近的k个训练数据,k个训练数据中哪个类别的训练数据占多数,则待分类数据就属于哪个类别。所谓k最近邻,就是k个最近的邻居的意思。KNN算法的基本思想是每个样本都可以用与它最接近的k个邻居来代表。其中的k表示最接近待分类样本的k个训练数据,一般k取奇数,这是为了保证在投票的时候不会出现票数相同的情况。KNN分类算法是一种有监督的学习方法,是根据不同特征值之间的距离进行分类的一种简单的机器学习方法,是数据挖掘技术中比较常用的分类算法,其思路简单、直观。由于其实现的简单性及较高的分类准确性,因此该算法在很多领域得到了广泛应用。
如果一个样本在特征空间中的k个最相似(即在特征空间中最邻近)的样本中的大多数属于某个类别,则该样本也属于这个类别。在KNN算法中,待分类样本选择的邻居都是已经正确分类的对象。该方法在分类决策上只依据最邻近的k个样本的类别来决定待分样本所属的类别。由于KNN算法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样类本集来说,KNN算法较其他方法更为适合。
KNN算法中的基本要素有距离计算和k值确定。两个点的距离越近，意味着这两个点属于一个分类的可能性越大。距离计算方法包括欧几里得距离、曼哈顿距离、余弦距离等,表5.1给出了这3种距离计算方法的基本情况。当然，要根据具体的分类对象选择合适的距离度量方法。采用不同的距离度量方法,对最终的结果影响很大。在利用KNN算法判断类别时k的取值很重要。可以在测试数据集测试完毕后计算分类误差率,然后设定不同的k值重新进行训练,最后取分类误差率最小的k值作为以后分类使用的k值。表5.13种常用距离计算方法的基本情况距离计算方法说明公式欧几里得距离两点间的直线距离D(a,b)=∑i(ai-bi)2曼哈顿距离两点的横向距离加上纵向距离d(x,y)=∑ni=1|xi-yi|余弦距离特征向量夹角的余弦值,更适合解决异常值和数据稀疏问题cos<a,b>=a·b|a||b|KNN算法的步骤如下: 
(1) 计算距离。给定测试对象,计算它与训练集中的每个训练样本的距离。
(2) 寻找邻居。圈定距离最近的k个训练样本,作为测试对象的近邻。
(3) 进行分类。根据这k个近邻归属的主要类别,对测试对象进行分类。
在实际的算法实现中,可以维护一个大小为k的按距离由大到小排列的优先级队列,用于存储最近邻训练样本。随机从训练集中选取k个样本作为初始的最近邻样本,分别计算测试数据到这k个训练样本的距离,将训练样本标号和距离存入优先级队列;遍历训练集,计算当前训练样本与测试数据的距离,将所得距离L与优先级队列中的最大距离Lmax进行比较。若L≥Lmax,则舍弃该训练样本,遍历下一个训练样本;若L<Lmax,则删除优先级队列中距离最大的训练样本,将当前训练样本存入优先级队列。遍历完毕,计算优先级队列中k个样本的多数类,并将其作为测试数据的类别。
【例5.1】分析表5.2中学生的高度,“身高”用于计算距离,k=5,对<Pat,女,1.6>分类。续表表5.2学生身高信息表序号姓名性别身高/m高度1Kristina女1.6矮2Jim男2高3Maggie女1.9中等4Martha女1.88中等5Stephanie女1.7矮6Bob男1.85中等7Kathy女1.6矮8Dave男1.7矮9Worth男2.2高10Steven男2.1高11Debbie女1.8中等12Todd男1.95中等13Kim女1.9中等14Amy女1.8中等15Wynette女1.75中等对前k=5个记录,N={<Kristina,女, 1.6>,< Jim,男,2>,< Maggie,女,1.9>,< Martha,女,1.88>，< Stephanie,女,1.7>}。
对第6个记录< Bob,男,1.85>计算距离,得到N={<Kristina,女, 1.6>,< Bob,男,1.85>,< Maggie,女,1.9>,< Martha,女,1.88>，< Stephanie,女,1.7>}。
对第7个记录< Kathy,女,1.6>计算距离,得到N={<Kristina,女, 1.6>,< Bob,男,1.85>,< Kathy,女,1.6>,< Martha,女,1.88>，< Stephanie,女,1.7>}。
对第8个记录< Dave,男,1.7>计算距离,得到N={<Kristina,女, 1.6>,< Dave,男,1.7>,< Kathy,女,1.6>,< Martha,女,1.88>，< Stephanie,女,1.7>}。
对第9个和第10个记录计算距离,优先级队列没有变化。
对第11个记录< Debbie,女,1.8>计算距离,得到N={<Kristina,女, 1.6>,< Dave,男,1.7>,< Kathy,女,1.6>,< Debbie,女,1.8>，< Stephanie,女,1.7>}。
对第12～14个记录计算距离,优先级队列没有变化。
对第15个记录< Wynette,女,1.75>计算距离,得到N={<Kristina,女, 1.6>,< Dave,男,1.7>,< Kathy,女,1.6>,< Wynette,女,1.75>，< Stephanie,女,1.7>}。
最后的优先级队列是<Kristina,女, 1.6>,<Kathy,女,1.6>,<Stephanie,女,1.7>,<Dave,男,1.7>，<Wynette,女,1.75>。在这5个训练样本中,4个属于“矮”，1个属于“中等”。最终利用KNN算法认为Pat是“矮”类别。
KNN算法主要依据邻近的k个样本进行类别的判断。然后依据k个样本中出现次数最多的类别作为待分类样本的类别。
KNN算法的优点如下: 
(1) 简单,易于理解,易于实现,无须估计参数,无须训练。
(2) 适合对稀有事件进行分类。
(3) 特别适用于多分类问题。
KNN算法有如下缺点: 
(1) 对每一个待分类样本都要计算它到全体训练样本的距离,才能求得它的k个最近邻。对测试样本进行分类时计算量大,内存开销大。
(2) 可解释性较差,无法给出像决策树那样的规则。
(3) 当样本不平衡（例如，一个类的样本容量很大,而其他类的样本容量很小）时,有可能导致以下情况： 当输入一个新样本时,该样本的k个近邻中大容量类的样本占多数,影响分类结果。
5.3贝叶斯分类
贝叶斯分类是一种基于统计的分类方法,它利用概率统计知识进行分类。贝叶斯分类使用概率表示各种形式的不确定性。在先验概率与类条件概率已知的情况下,计算给定样本属于特定类的概率,并选定其中概率最大的一个类别作为该样本的最终类别。朴素贝叶斯分类算法逻辑简单,并在大型数据库中表现出高准确率和高计算速度等特点。贝叶斯定理是朴素贝叶斯分类算法的理论依据。
5.3.1贝叶斯定理
贝叶斯定理的基础是概率论中的乘法公式:P(AB)=P(A)P(B|A)=P(B)P(A|B)可以变形为P(B|A)=P(A|B)P(B)P(A)贝叶斯定理由英国数学家贝叶斯(Thomas Bayes,1702—1761)提出的,用来描述两个条件概率之间的确定关系。贝叶斯定理是乘法公式的变形。P(B|A)=P(AB)P(A)=P(A|B)P(B)P(A)A和B是独立的事件。P(B|A)称为后验概率或在条件A下B的后验概率，P(B)称为先验概率或B的先验概率。贝叶斯定理提供了一种由P(B)、P(A)和P(A|B)计算后验概率的方法。 
例如,假设数据样本是由属性age和income描述的顾客, X是一位25岁、收入为5000美元的顾客,即X的属性值为: age=25,income=$5000。对应的假设H是顾客X将购买计算机。
 P(H|X)表示在已知某顾客信息age=25、income=$5000的条件下,该顾客会买计算机的概率。
 P(H)表示任意顾客购买计算机的概率。
 P(X|H)表示已知顾客会购买计算机,那么该顾客属性为age=25、income=$5000的概率。
 P(X)表示在所有顾客信息的集合中, 顾客属性为age=25,income=$5000的概率。
【例5.2】现分别有A、B两个容器,在容器 A里有6个红球和4个黑球,在容器B里有2个红球和8个黑球。现从这两个容器之一里任意取了一个球,且是红球,这个红球来自容器A的概率是多少?
解: 假设取出红球为事件B,从容器A里取出一个球为事件A,则有P(B)=820=25,P(A)=12,P(B | A)=610=35根据贝叶斯定理,有P(A|B)=P(B|A)P(A)P(B)=35×1225=34【例5.3】表5.3是某医院近期门诊病人情况。一个头疼的学生被诊断为感冒的概率有多大？表5.3某医院近期门诊病人情况症状职业诊 断 结 果头疼学生感冒头疼农民过敏打喷嚏工人脑震荡打喷嚏工人感冒头疼护士感冒打喷嚏学生脑震荡令B={既头疼又是学生},B1={头疼},B2={学生},A={感冒},则问题转化为求P(A|B)。
由于“头疼”和“是学生”是两个独立的对象,贝叶斯定理就转化为P(A|B)=P(B|A)P(A)P(B)=P(B1|A)P(B2|A)P(A)P(B1)P(B2)=23×13×1212×26=23≈66.67%因此,这个头疼的学生有大约66.67%的概率被诊断为感冒。
请自己计算一下这个头疼的学生被诊断为脑震荡的概率是多少。
5.3.2朴素贝叶斯分类算法
朴素贝叶斯分类算法是一种十分简单的分类算法,它以对象各特征属性相互独立为假设,以贝叶斯定理为基础,对于给出的待分类对象,求解在此对象出现的条件下各个类别出现的概率,哪个概率最大,就认为此待分类对象属于哪个类别。例如,在街上看到一个黑人,猜他是从哪里来的,我们十有八九猜他来自非洲。这是因为黑人来自非洲的概率最高。当然他也可能是美洲人、欧洲人或亚洲人等,但在没有其他可用信息时,人们会选择条件概率最大的类别。
朴素贝叶斯分类算法如下: 
(1) 设x={a1,a2,…，am}为一个待分类项,而每个a为x的一个特征属性。
(2) 有类别集合C={y1,y2,…,yn}。
(3) 计算P(y1|x),P(y2|x),…,P(yn|x)。
(4) 如果P(yk|x)=max{P(y1|x),P(y2|x),…,P(yn|x)},则x∈yk。
第(3)步是朴素贝叶斯分类算法的关键。首先根据训练集,统计得到在各类别下各个特征属性的条件概率，如下所示:
P(a1|y1),P(a2|y1),…,P(am|y1)
P(a1|y2),P(a2|y2),…,P(am|y2)

P(a1|yn),P(a2|yn),…,P(am|yn)
因为各个特征属性是条件独立的,则根据贝叶斯定理有P(yi|x)=P(x|yi)P(yi)P(x)因为分母对于所有类别均为常数,所以只要将分子最大化即可。又因为各特征属性是条件独立的,所以有P(x|yi)P(yi)=P(a1|yi)P(a2|yi)…P(am|yi)P(yi)=P(yi)∏mj=1P(aj|yi)【例5.4】表5.4给出了一个顾客数据库标记类的训练集D。使用朴素贝叶斯分类算法预测待分类数据的类标号。数据元组用属性age、income、student、credit_rating和buys_comp来描述。类标号属性buys_comp具有两个不同的值no和yes。设C1对应于类buys_comp=yes,C2对应于类buys_comp=no。待分类数据为
X=(age≤25,income=medium,student=yes,credit_rating=fair)续表表5.4顾客数据库标记类的训练集IDageincomestudentcredit_ratingbuys_comp1≤25highnofairno2≤25highnoexcellentno326～35highnofairyes4>35mediumnofairyes5>35lowyesfairyes6>35lowyesexcellentno726～35lowyesexcellentyes8≤25mediumnofairno9≤25lowyesfairyes10>35mediumyesfairyes11≤25mediumyesexcellentyes1226～35mediumnoexcellentyes1326～35highyesfairyes14>35mediumnoexcellentno15<25mediumyesfairyes解: (1) 计算每个类的先验概率P(Ci)。P(C1)=1015=0.667P(C2)=515=0.333(2) 计算每个特征属性对于每个类别的条件概率。P(age≤25|buys_comp=yes)=310=0.3P(income≤medium|buys_comp=yes)=510=0.5P(student≤yes|buys_comp=yes)=710=0.7P(credit_rating≤fair|buys_comp=yes)=710=0.7P(age≤25|buys_comp=no)=35=0.6 P(income≤medium|buys_comp=no)=25=0.4P(student≤yes|buys_comp=no)=15=0.2P(credit_rating≤fair|buys_comp=no)=25=0.4(3) 计算条件概率P(X|Ci)。P(X|buys_comp=yes)=0.3×0.5×0.7×0.7=0.0735P(X|buys_comp=no)=0.6×0.4×0.2×0.4=0.0192(4) 计算对于每个类Ci的P(X|yi)P(yi)。P(X|buys_comp=yes)P(buys_comp=yes)=0.0735×0.667=0.049P(X|buys_comp=no)P(buys_comp=no)=0.0192×0.333=0.00639因此,对于样本X,朴素贝叶斯分类算法的预测为buys_comp=yes朴素贝叶斯分类算法有以下优点: