分类与预测(武汉大学-李春葆)

第7章分类与预测2分类的任务是通过分析由已知类别数据对象组成的训练数据集，建立描述并区分数据对象类别的分类函数或分类模型（也常常称作分类器）。分类的目的是利用分类模型预测未知类别数据对象的所属类别。3分类和聚类是两个容易混淆的概念，事实上它们具有显著区别。在分类中，为了建立分类模型而分析的数据对象的类别是已知的，然而，在聚类时处理的所有数据对象的类别都是未知的。因此，分类是有指导的，而聚类是无指导的。4数据分类与数值预测都是预测问题，都是首先通过分析训练数据集建立模型，然后利用模型预测数据对象。在数据挖掘中，如果预测目标是数据对象在类别属性（离散属性）上的取值（类别），则称为分类；如果预测目标是数据对象在预测属性（连续属性）上的取值或取值区间，则称为预测。例如，对100名男女进行体检，测量了身高和体重，但是事后发现，a和b两人忘了填写性别，c和d两人漏了记录体重。现在根据其他96人的情况，推断a和b两人的性别是分类，而估计c和d两人的体重是预测。57.1分类过程分类过程分为两个阶段：学习阶段与分类阶段，如图7.1所示，图中左边是学习阶段，右边是分类阶段。训练样本输入分类模型测试样本输入新样本分类算法学习阶段分类阶段61.学习阶段（1）建立分类模型：通过分类算法分析训练数据集建立分类模型。训练数据集S中的元组或记录称为训练样本，每个训练样本由m+1个属性描述，其中有且仅有一个属性称为类别属性，表示训练样本所属的类别。属性集合可用矢量X=（A1，…，Am，C）表示，其中Ai（1≤i≤m）对应描述属性，可以具有不同的值域，当一个属性的值域为连续域时，该属性称为连续属性（NumericalAttribute），否则称为离散属性（DiscreteAttribute）；C表示类别属性，C=（c1，c2，…，ck），即训练数据集有k个不同的类别。7分类算法有决策树分类算法、神经网络分类算法、贝叶斯分类算法、k-最近邻分类算法、遗传分类算法、粗糙集分类算法、模糊集分类算法等。分类算法可以根据下列标准进行比较和评估。1）准确率。涉及分类模型正确地预测新样本所属类别的能力。2）速度。涉及建立和使用分类模型的计算开销。3）强壮性。涉及给定噪声数据或具有空缺值的数据，分类模型正确地预测的能力。4）可伸缩性。涉及给定大量数据，有效地建立分类模型的能力。5）可解释性。涉及分类模型提供的理解和洞察的层次。分类模型有分类规则、判定树等。8（2）评估分类模型的准确率：利用测试数据集评估分类模型的准确率。测试数据集中的元组或记录称为测试样本。分类模型正确分类的测试样本数占总测试样本数的百分比称为该分类模型的准确率。如果分类模型的准确率可以接受，就可以利用该分类模型对新样本进行分类。否则，需要重新建立分类模型。9评估分类模型准确率的方法有保持（holdout）、k-折交叉确认等。保持方法将已知类别的样本随机地划分为训练数据集与测试数据集两个集合，一般，训练数据集占2/3，测试数据集占1/3。分类模型的建立在训练数据集上进行，分类模型准确率的评估在测试数据集上进行。k-折交叉确认方法将已知类别的样本随机地划分为大小大致相等的k个子集S1，…，Sk，并进行k次训练与测试。第i次，子集Si作为测试数据集，分类模型准确率的评估在其上进行，其余子集的并集作为训练数据集，分类模型的建立在其上进行。进行k次训练得到k个分类模型，当利用分类模型对测试样本或者新样本进行分类时，可以综合考虑k个分类模型的分类结果，将出现次数最多的分类结果作为最终的分类结果。102.分类阶段分类阶段就是利用分类模型对未知类别的新样本进行分类。数值预测过程：与数据分类过程相似。首先通过分析由预测属性取值已知的数据对象组成的训练数据集，建立描述数据对象特征与预测属性之间的相关关系的预测模型，然后利用预测模型对预测属性取值未知的数据对象进行预测。数值预测技术主要采用回归统计技术，例如，一元线性回归、多元线性回归、非线性回归等。117.2决策树分类决策树：一棵决策树由一个根节点，一组内部节点和一组叶节点组成。每个内部节点（包括根节点）表示在一个属性上的测试，每个分枝表示一个测试输出，每个叶节点表示一个类，有时不同的叶节点可以表示相同的类。7.2.1决策树12一棵决策树年龄？是≤3031..40≥41否是否是否是优中学生？信誉？13建立一棵决策树，需要解决的问题主要有：1）如何选择测试属性？测试属性的选择顺序影响决策树的结构甚至决策树的准确率，一般使用信息增益度量来选择测试属性。2）如何停止划分样本？从根节点测试属性开始，每个内部节点测试属性都把样本空间划分为若干个（子）区域，一般当某个（子）区域的样本同类时，就停止划分样本，有时也通过阈值提前停止划分样本。141.算法思想及描述首先，在整个训练数据集S、所有描述属性A1，A2，…，Am上递归地建立决策树。即将S作为根节点；如果S中的样本属于同一类别，则将S作为叶节点并用其中的类别标识，决策树建立完成（递归出口）；否则在S上计算当给定Ak（1≤k≤m）时类别属性C的信息增益G(C，Ak)，选择信息增益最大的Ai作为根节点的测试属性；如果Ai的取值个数为v（取值记为a1，a2，…，av），则Ai将S划分为v个子集S1，S2，…，Sv（Sj（1≤j≤v）为S中Ai=aj的样本集合），同时根节点产生v个分枝与之对应。其次，分别在训练数据子集S1，S2，…，Sv、剩余描述属性A1，…，Ai-1，Ai+1，…，Am上采用相同方法递归地建立决策树子树（递归）。7.2.2建立决策树15可能出现如下情况，需要停止建立决策（子）树的递归过程。1）某节点对应的训练数据（子）集为空。此时，该节点作为叶节点并用父节点中占多数的样本类别标识。2）某节点没有对应的（剩余）描述属性。此时，该节点作为叶节点并用该节点中占多数的样本类别标识。16算法：决策树分类算法Generate_decision_tree（S，A）输入：训练数据集S，描述属性集合A输出：决策树步骤：（1）创建对应S的节点Node;（2）ifS中的样本属于同一类别cthen以c标识Node并将Node作为叶节点返回;（3）ifA为空then以S中占多数的样本类别c标识Node并将Node作为叶节点返回;决策树ID3算法17（4）从A中选择对S而言信息增益最大的描述属性Ai作为Node的测试属性;（5）forAi的每个可能取值aj（1≤j≤v）//设Ai的可能取值为a1，a2，…，av（5.1）产生S的一个子集Sj//Sj（1≤j≤v）为S中Ai=aj的样本集合;（5.2）ifSj为空then创建对应Sj的节点Nj，以S中占多数的样本类别c标识Nj，并将Nj作为叶节点形成Node的一个分枝（5.3）else由Generate_decision_tree（Sj，A-{Ai}）创建子树形成Node的一个分枝;182.信息增益在决策树分类算法中使用信息增益度量来选择测试属性。从信息论角度看，通过描述属性可以减少类别属性的不确定性。假设有蕃茄、茄子、黄瓜三种蔬菜，现在对某蔬菜分类。在不给任何描述时，该蔬菜可能是蕃茄、茄子、黄瓜三种之一，不确定性大。在给出该蔬菜是“长的”形状描述时，该蔬菜可能是茄子、黄瓜两种之一，不确定性减小。在给出该蔬菜是“紫的”颜色描述时，该蔬菜只可能是茄子了，不确定性为零。19离散型随机变量X的无条件熵定义为式中，p(xi)为X=xi的概率；u为X的可能取值个数。根据H(X)的极值性，当时，即当不确定性最大时，H(X)最大。根据H(X)的确定性，当时，即当不确定性为零时，H(X)=0。所以，H(X)反映X的不确定性。uii2ixplogxpXH1)()()(uxpxii1)()(1)()(iixpx20给定离散型随机变量Y，离散型随机变量X的条件熵定义为式中，p(xiyj)为X=xi，Y=yj的联合概率；p(xi/yj)为已知Y=yj时，X=xi的条件概率；u、v分别为X、Y的可能取值个数。可以证明，H(X/Y)≤H(X)。所以，通过Y可以减少X的不确定性。uivjji2jiyxplogyxpYXH11)/()()/(21假设训练数据集是关系数据表r1，r2，…，rn，其中描述属性为A1，A2，…，Am、类别属性为C，类别属性C的无条件熵定义为式中，u为C的可能取值个数，即类别个数，类别记为c1，c2，…，cu；si为属于类别ci的记录集合，|si|即为属于类别ci的记录总数。uii2inslognsCE1||||)(22给定描述属性Ak（1≤k≤m），类别属性C的条件熵定义为式中，v为Ak的可能取值个数，取值记为a1，a2，…，av；sj为Ak=aj的记录集合，|sj|即为Ak=aj的记录数目；sij为Ak=aj且属于类别ci的记录集合，|sij|即为Ak=aj且属于类别ci的记录数目。)||||||||(||),(11jij2vjuijijjksslogssnsACE23不同描述属性减少类别属性不确定性的程度不同，即不同描述属性对减少类别属性不确定性的贡献不同。例如，假设有蕃茄、茄子、黄瓜三种蔬菜，现在对某蔬菜分类，形状描述与颜色描述的贡献是不同的。在给出该蔬菜的颜色描述时，如果颜色是红的，则该蔬菜是蕃茄；如果颜色是紫的，则该蔬菜是茄子；如果颜色是绿的，则该蔬菜是黄瓜，不确定性减少为0。而在给出该蔬菜的形状描述时，如果形状是圆的，则该蔬菜是蕃茄；如果形状是长的，则该蔬菜可能是茄子，也可能是黄瓜，不确定性还是存在。24采用类别属性的无条件熵与条件熵的差（信息增益）来度量描述属性减少类别属性不确定性的程度。给定描述属性Ak（1≤k≤m），类别属性C的信息增益定义为：G(C，Ak)=E(C)-E(C，Ak)可以看出，G(C，Ak)反映Ak减少C不确定性的程度，G(C，Ak)越大，Ak对减少C不确定性的贡献越大。25例如，假设蔬菜数据表如表7.1所示，“颜色”、“形状”是描述属性，“蔬菜”是类别属性，分别求给定“颜色”、“形状”属性时，“蔬菜”属性的信息增益。表7.1蔬菜数据表颜色形状蔬菜红圆蕃茄紫长茄子绿长黄瓜结论属性条件属性265850.1)31log3131log3131log31()(222蔬菜E解：颜色形状蔬菜红圆蕃茄紫长茄子绿长黄瓜共有3个记录，蕃茄、茄子和黄瓜各计一个记录。结论或分类属性270)1log1(31)1log1(31)1log1(31)(222蔬菜，颜色E颜色形状蔬菜红圆蕃茄紫长茄子绿长黄瓜按颜色分类，再按蔬菜分类，每种蔬菜只有一种颜色。属性颜色的条件熵286667.0)21log2121log21(32)1log1(31)(222蔬菜，形状E颜色形状蔬菜红圆蕃茄紫长茄子绿长黄瓜按形状分类，再按蔬菜分类，圆形状只有一种蔬菜，而长形状有两种蔬菜。属性形状的条件熵29则有：G(蔬菜，颜色)＝1.5850-0=1.5850G(蔬菜，形状)＝1.5850-0.6667=0.9183说明颜色对蔬菜分类的不确定性小，而形状对蔬菜分类的不确定性大。信息熵E(C)反映分类属性C不确定的程度，为1时表示最大不确定性，为0时表示最小不确定性。E(C，A)表示分类属性C相对于属性A的条件熵。信息增益G(C，A)=E(C)-E(C，A)反映属性A减少C不确定性的程度，G(C，A)越大，属性A对减少C不确定性的贡献越大。各条件属性对分类属性的信息增益30例如，建立上例的决策树。因为G(蔬菜，颜色)G(蔬菜，形状)，所以选择“颜色”属性作为根节点的测试属性，得到的决策树如下图所示。颜色？蕃茄茄子黄瓜红紫绿31例如，假设顾客数据表如下表所示，“购买计算机”属性是类别属性，其余属性是描述属性，建立决策树。年龄收入学生信誉购买计算机≤30高否中否≤30高否优否31..4