数据挖掘5分类

1、数据挖掘发现知识的类型,广义知识 关联知识 分类知识 预测型知识 偏差型知识,Outline： 5.1 一般概念 (classification 的处理过程、现有的常用算法、分类和回归的预报指标） 5.2 分类和回归的预报评价 5.3 分类方法 基于距离空间的KNN方法及其衍生方法 基于归纳的决策树分类方法 基于最优判别平面或多面体的分类方法 基于模糊理论的分类方法 基于概率统计的Bayes Net分类算法 5.4 回归方法,第五章 分类与回归,5.1 一般概念,分析已知的数据，构造模型（创建分类器分类器），该模型可以用来对未知的数据做预测，判定其目标值（类别或连续值）。 统称为预报：描述某类

2、数据集的模型或预测数据的变化趋势。只是 分类预测的是分类标号（离散的，有限的数值）分类器 回归预测的是连续值 连续的函数模型,E.g. 同一组数据，就有可能存在这两种预报,分类： 回归：,1.分类的处理过程：,First, 通过分类算法对数据的分析和学习，建立一个可用分类规则表示的模型或分类器。 表现形式有：（1）规则 ifthen （2）判别平面 g(x) = wT(x) then，用上述分类规则对测试样本进行分类，求分类准确率，如果分类准确率达到可接受的程度，该规则就可以用于新数据的分类。 对于回归，训练样本与目标之间的关系，建立相关的函数模型,具体步骤1,建立一个模型，描述给定的数据类集

3、或概念集（简称训练集） 通过分析由属性描述的数据库元组来构造模型。每个元组属于一个预定义的类，由类标号属性确定。用于建立模型的元组集称为训练数据集，其中每个元组称为训练样本。由于给出了类标号属性，因此该步骤又称为有监督的学习（supervised）。如果训练样本的类标号是未知的，则称为无监督的学习（unsupervised）。学习模型可用分类规则、决策树和数学公式的形式给出。,具体步骤2,使用模型进行分类 首先对模型分类准确率进行估计 如果一个学习所获模型的准确率经测试被认为是可以接受的，那么就可以使用这一模型对未知数据或对象（其类别未知）进行分类。,2现有的常用算法,分类： 基于概率统计的

4、Bayes Net 基于归纳学习的 Decision Tree 基于向量空间模型的 KNN，NN，Case-based reasoning，rough set 基于模糊集的Fuzzy theory,FMMNN 基于统计学习理论的SVM 基于超平面或超多面体的 Fisher，PCA，PLS，LMap 回归： 一元（多元）线性（非线性）回归，核，SVR,5.2 分类和回归的预报评价,包括对得到的模型、求解该模型的过程以及用该模型预报未知等一系列工作的评价。,分类/回归的准确率 速度，包括建模和测试花费的时间 稳健性，对各种类型的data都适用 可升级性，易于改进与升级 可理解性，所建立的规则模型要

5、易于理解，便于用户或专家解释(在理论和实际应用中都可以解释),.分类/回归的准确率,评价一个模型的准确率：一般是把已知样本分成两个子集（训练集和测试集）。模型是通过分析训练集得到，评价的是该模型用于预报测试集样本的准确率（预报误差） 分类：误报率 回归：均方误差、平均误差、相对误差,预报准确率的测试方法,根据训练集、测试集的不同划分，可分为不同的测试方法： （1）Holdout method 任意划分两个子集（只规定好数目，至于哪个样本划到哪里是随机的）。可以做多次，然后取平均值。 （2）Kfold cross-validation （k-交叉验证方法） 所给初始样本任意地分成样本数大致相等的

6、k个子集（s1,s2,sk），并做k次训练与测试：第一次，以s1为Test Sample Set，其它的（S2s3,sk）为training sample，第i次，以si为Test Sample Set，其它的为training sample set。最后，准确率就是k次的测试结果之和。 （3）留n法 固定每次有n个样本做测试集，重复做一直到所有样本都被测试过。n1时，就是留一法（Jackknife检验）。留一法也是k-交叉验证方法的特例（kNs）有几个样本就分成几个子集） （4）Self-consistency检验 用训练集数据进行学习，并对训练集数据进行检验,分类准确率的其他表示方法,对于

7、分类问题，评价准确性还要更复杂一些，因为关系到各类别数据的分布情况。例如，对于一个样本集，如果其中样本的分类：其中的某类样本数10，那么分类器的准确率再高，也只是对另一类样本有意义，而对该类样本没有意义。样本的不平衡性问题，小样本问题 为解决这个问题，提出了分类准确率的另外一些度量方式：,5.3 几种分类方法,基于距离空间的KNN方法及其衍生方法 基于归纳的决策树分类方法 基于概率统计的Bayes分类算法 基于模糊理论的FMMNN分类方法 基于最优判别平面或多面体的分类方法,基于距离空间的KNN及其衍生方法,1.美国的E.Fix 和J.L.Hodges在1951年提出来的KNN方法 KNN是一

8、种最经典的模式识别方法，该方法可用于线性不可分的多类样本的识别。K为最近邻个数。 基本原理： “物以类聚”、“少数服从多数”。即如果未知样本的K个近邻样本都是一种类型，那么该未知样本就和它们同类；若这K个类型不一致，将该样本归入其中具有最多数样本的那一类，所以K 值常为奇数。,KNN方法存在的三个问题：,(1) K值选取。K值的选择会直接影响到分类结果。针对某一问题应该如何确定K值,目前为止还没有统一定律。 (2)计算量。因为每判断一个样本都需要重新计算它与所有其它样本的距离，所以计算量非常大。 (3) 最近邻规则。近邻规则包括采用何种距离、求得距离后又以哪种标准判别未知样本的属类等等。,2A

9、LKNN法（改进近邻匹配规则）,ALKNN法根据每类样本的数目和分散程度，对不同的类可以选取不同的K值。各类的Ki值选定后，用一定的算法对类中的样本的概率进行估算，并根据概率大小对它们进行类的划分。 在ALKNN法中，以xi与类C i的K i个近邻中最远一个样本的距离r为半径，以x为中心，计算相应的超球的体积。并认为超球体积越小，类C i在xi处的概率密度越大，这一概率密度可由下式计算 P(x/Ci)= (Ki-1)/v(x/Ci) 此处v(x/Ci)为Ci的超球体积。 对于未知样本，哪一类计算的P(x/gi)最大， 即归入哪一类。,3Fast k-Nearest Neighbor Class

10、ification Using Cluster_Based Trees （改进速度）,First, The Cluster Tree Algorithm Cluster-Based Tree Generation Classification Then, Evaluation （NIST/MNIST) Condensation-based tree algorithm,Cluster-Based Tree Generation,给定一个数据集T，设定三个局部特性参数：,样本z与最近邻的非同类样本之间的非相似度（距离）,与z的距离小于等于上述的最近距离的所有同类样本点的集合,上述样本点集合中的包

11、含的样本个数,Step0：初始化聚类树（一个样本作为一个节点）Bottom Level。 Step1：计算T中每个样本的三个参数，然后根据,进行降序排列。,Step2：把具有最大l值的样本（z1）作为一个Hypernode，做好z1与,集合中的样本的链接，并在bottom level中去除这些样本。,Step3：对bottom level中的样本重复step1和step2的操作，直至为空。,Step4：设定一个阈值,，对hyper level中的样本进行聚类：每一聚类的半,径小于或等于,。形成了p level。,Step5：增加,的值，重复step4的操作，直到最后一层的节点数为1。,阈值,R

12、esult：,生成的树：,top level 只有一个节点 bottom level 的节点个数样本数 每个节点都链接了好多样本，但只有hyper level的每个节点所对应的样本集是保证属于同类别的。,Classification：,For an unknown sample X, will be classified as follows:,Step0:计算X与top level中每个节点的非相似度，并选定k个最相似的节点记录到Lx集合。 Step1：计算X和Lx中的节点所对应的各子节点之间的非相似度，然后选取k个最相似的节点，更新Lx集合。 Step2：重复step1，一直到Lx 集合包

13、括的是hyper level nodes。 Step3：对Lx中的节点（Y）求,，并建立新的集合,Step4：计算X和Lx中的节点所对应的各子节点之间的非相似度，然后选取k个最相似的节点，用投票法来分类。,类别的，X就属于该类别，完成分类。否则转向Step4。,如果Lh中的所有节点是同一,优点：,可以事先确定分类模型，大大减少test的时间,基于距离空间的KNN方法及其衍生方法 基于归纳的决策树分类方法 基于模糊理论的FMMNN分类方法 基于最优判别平面或多面体的分类方法 基于概率统计的Bayes分类算法,基于归纳的决策树分类方法,用于分类和预测。决策树学习是以样本为基础的归纳学习方法。基本算

14、法是贪心算法，采用自顶向下的递归方式构造决策树。,Descion Tree （DT）包括： 内部节点（非叶节点，对属性的描述）：根节点，支节点，用方框表示。每个内部节点都对应一个用于分割数据集的属性。 叶节点（末节点，对类别的描述）：用圈表示，每个叶节点都对应一个类别标识C的值，说明上面属性取值情况下的子样本集都属于同一类,构建和剪枝,Example： 汽车保险案例,训练集,决策树,决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。若要对一个实体分类，从树根开始进行测试，按特征的取值分枝向下进入下层节点，对该节点进行测试，过程一直进行到叶节点，实体被判为属于该叶节点所标记的类别。

15、,决策树算法,基本算法（贪心算法） 自上而下分而治之的方法 开始时，所有的数据都在根节点 属性都是种类字段 (如果是连续的，将其离散化) 所有记录用所选属性递归的进行分割 属性的选择是基于一个启发式规则或者一个统计的度量 停止分割的条件 一个节点上的数据都是属于同一个类别 没有属性可以再用于对数据进行分割,DT的任务： 在DT内部节点进行属性值的比较，根据不同的属性值判断从该节点向下的分支，并在叶节点处得出结论。（通过训练已知数据集，构造DT）。 从根节点到叶节点的路径：对应着要寻找的分类规律。（一条路径一条规律） 测定一个新样本的类别：根据各属性值，由上到下遍历决策数。,关键：寻找合适的内部

16、节点。（根据某准则选择适当的属性作为内部节点）,根据准则的不同，决策树算法可以分为多类，常见的有： 基于信息论的： ID3、 C4.5、 基于最小GINI指标的：CART、SLIQ、SPIRINT,1、信息增益（准则）,假定S为训练样本集，每个训练样本的类别已知 N：样本总数 m ：类别总数 Ni ：属于第i(i=1,2,m)类的样本数， Then，判定某个样本属于哪一类的期望信息定义为:,一个属性A有v个取值：a1,a2,av 。则能把样本集S划分为v个子集：S1,S2,Sv, 即Sj 内包含的样本其属性A的取值皆为aj。假设Sj中包含的第i类样本的样本数为Nij，则定义 属性A的熵为:,关

17、于属性A的信息增益就是：,2、基尼指数 （ Gini Index ）（准则）,集合T包含N个类别的记录，那么其Gini指标就是 pj ：类别j出现的频率 如果集合T分成两部分 N1 and N2 。那么这个分割的Gini就是 提供最小Ginisplit 就被选择作为分割的标准(对于每个属性都要遍历所有可以的分割方法).,2. ID3 (Interactive Dichotomizer 3)决策树算法的递归描述 Quinlan J.R，“Induction of Decision Trees”， Machine Learning， 1986 1：81-106,设有训练样本集为S Step1. 如

18、果样本集中所有的样本属于同类（或没有属性集可供分类，或其它终止条件），则该样本集不再划分，生成一个叶节点。并根据该样本集中的所有样本的类别赋予该叶节点一个类别标记，转step3。否则转step2 Step2. 根据某属性生成一个非叶节点对S进行划分，得到n（该属性值个数）个子集样本，记为Si，对每个Si执行step1。 Step3. 提取规则析取式，输出结果。,在ID3算法中，采用了一种基于信息的启发式的方法来决定如何选取属性。启发式方法选取具有最高互信息即最高信息增量（information gain）的属性，也就是说，生成最少分支决策树的那个属性。,2.1 Example,已知一个训练集，

19、4个属性，14个样本，用DT法判定第15号样本属于哪一类。,表51,处理步骤： Step1. 检验样本集S中的类别。（因为S中并不是所有样本都属于同类，所以转向step2。） Step2.确定S根据哪个属性进行划分： 求天气、温度、湿度、风力这四个属性的信息增益，以确定划分标准。,Step2.1 共有2类，so， Step2.2 求每个属性的信息增益 （1）属性“天气” ，有3个不同值 所以，有,（2）温度 有3个不同值,（3）湿度 有2个不同值,（4）风力 有2个不同值,即，第一次运算得到的Gain结果为,所以，选取天气作为划分数据样本的标准（作为节点）。,Step3. 根据“天气”的不同值

20、个数，分成3个子空间（S1，S2，S3），并对每个子空间进行类别检验。可见S2中的样本的所有类别属性相同（都为1类），可以得到一个叶节点（叶节点1）。,S1（天气：晴）： 1、2、8、9、11（有1类和2类） S2 （天气：阴） ：3、7、12、13 （皆为1类） S3 （天气：雨） ： 4、5、6、10、14（有1类和2类）,Step4. 另外的两个子集样本S1，S3做类似于S的递归处理。最后得到如图所示的决策树。,对于S1（1、2、8、9、11）有 对于S3（4、5、6、10、14）有,Step5. 从决策树获得规则析取式。,得到的规则析取式： IF 天气晴 AND 湿度高 THEN cl

21、ass“2” IF 天气晴 AND 湿度正常 THEN class“1” IF 天气阴 THEN class“1” IF 天气雨 AND 风力有 THEN class“2” IF 天气雨 AND 风力无 THEN class“1”,决策树递归算法的步骤2中的划分形式可分为两类：单变量划分和多变量划分，对应的决策树称为单变量决策树和多变量决策树。 单变量划分根据样本某一个属性值大于或者小于某个阈值，将其分配到不同的子集中去，如ID3和由它派生的C4.5【Quinlan J.R，“Programs for Machine Learning”， Morgan Kaufmann 1993；Quinla

22、n J.R，Improved use of Continuous Attributes in C4.5，Journal of Artificial Intelligence Research，1996，4：77-90】。 多变量划分根据样本所有属性值的加权和大于或者小于某个阈值，将其分配到不同的子集中去，如OC1(Oblique Classifier) 【Sreeramma K.Murthy，Simon Kasif， Steven Salzberg，“A System for Induction of Oblique Decision Trees ”， Journal of Artificia

23、l Intelligence Research， 1994， 2：1-32】。,事实上这两类划分形式都采用了超平面划分样本集合，不同的是前者的超平面必须与对应属性所在的坐标垂直，而后者则没有这一限制。下图显示了二维情况下它们的区别。,3连续型属性的处理(C4.5) （1）离散化 （2）寻找一个确定的值，把该属性划分成2部分 （3）按连续属性值的置信度大小来划分区间 例如，连续值X，设其标准方差为Xs，下限值为XL，上限值为XR a求置信度表示 b根据置信度划分区间 e.g. 根据CF值划分为5个区间 CF 0,0.2 (0.2,0.4 (0.4,0.6 (0.6,0.8 (0.8,1 表示值

24、1 2 3 4 5,剪枝常常利用统计学方法，去掉最不可靠、可能是噪声的一些枝条，同时它也能使树得到简化而变得更容易理解。 目的： 消除决策树的过适应(OverFitting)问题 实质：消除训练集中的异常和噪声 两种剪枝策略： 先剪枝（预剪枝）限制决策树的过度生长； 后剪枝：待决策树生成后再进行剪枝。,4. 树剪枝,1.先剪枝 事先限定最大生长高度，使决策树不能过度生长。 采用x2检验、信息增益等度量，评估每次节点分裂对系统性能的增量，如果节点分裂的增量小于预先给定的阈值，则不对该节点进行扩展。 2.后剪枝 允许决策树过度生长，然后根据一定的规则，剪去那些不具有一般代表性的节点和分枝。可以采用

25、自上而下的顺序或自下而上的顺序进行剪枝。 代价复杂性剪枝算法：对于树中每个非树叶节点计算该子树被剪枝会出现的期望错误率，如果剪去该节点导致较高的期望错误率，则保留该子树；否则剪去该子树。,5. 树的评价标准,误报率 决策树的节点数 获得的决策规则数 决策规则前提条件的总数 每条规则覆盖例子的平均数（泛化能力） 获取决策规则的效率,基于距离空间的KNN方法及其衍生方法 基于归纳的决策树分类方法 基于最优判别平面或超平面的分类方法 基于模糊理论的分类方法 基于概率统计的Bayes分类算法,基于最优判别平面或超平面的LMap方法 (白化变化线性降维方法),前面提到的DT、KNN等方法只是利用了样本的

26、分布信息，没有经过空间变换，没有增加样本的可分离性。 LMap引入了白化变换，利用样本分类的信息，设法增强样本的可分离性。,1白化变换,设样本矩阵X的协方差矩阵为DX，且P是协方差阵的本征矢量，是协方差阵本征值矩阵。 若令AP1/2 则称YXA 为白化变换 （1）数学意义上，经白化变换后，Y的协方差矩阵变成单位矩阵I （证明：DYYTY=(XA)T(XA)=ATXTXA=ATDXA=(P1/2)TDXP1/2 =1/2PTDXP1/21/2 = 1/2PTP1/2 = 1/21/2=I） （2）几何意义上，经白化变换后，样本分布形式发生变化，坐标轴被压缩或膨胀。对于多类情况，若对第k类样本实施

27、白化变换，则该类样本的分布成为球形，其他类的分布也随之相应规整化。,2LMap的算法描述 LMap是在白化变换基础上改善多类样本中特定类别样本的分布情况。,基本步骤： 设样本矩阵XMN，有c类,3LMap的处理结果,（1）加强了分类效果，在Y投影图上的可分性比在原始变量X上的可分性有提高。给出的优类样本与其它样本的分界线是一组原始变量经线性组合后的变换方程。 （2）对包容性数据尤其有效。,偏置型数据 包容型数据,LMap PCA,基于距离空间的KNN方法及其衍生方法 基于归纳的决策树分类方法 基于最优判别平面或多面体的分类方法 基于模糊理论的分类方法 基于概率统计的Bayes分类算法,基于模糊

28、理论的模糊极小极大网络方法 (Fuzzy Min-Max Neural Network，FMMNN),Simpson在1992年提出，并将它用于有监督的分类和无监督的聚类. Simpson Patric K.， “Fuzzy Min-Max Neural Networks-Part 1：Classification”, IEEE Trans. on Neural Networks， 1992, 3(5)：776-786 Simpson Patric K.，“Fuzzy Min-Max Neural Networks-Part 2：Clustering”， IEEE Trans. on Fuzz

29、y Systems， 1993, 1(1)：32-45,概述,FMMNN的训练算法：,Step1 超盒形成与扩张,Step2 重叠检测,Step3 超盒收缩 按照以上4种情况对应作以下处理,超盒收缩的的图表示,以上3步执行完成后，训练过程即告结束。生成的超盒构成了一个模糊分类器。 下图显示了两维问题中超盒的分布和对应的分类界面。值得注意的是，虽然超盒的边界必定与坐标轴垂直，而它们及其模糊外延形成的分类边界却是不规则的。对于类别未知样本，FMMNN根据(5-1)式计算它到所有超盒的隶属度，取隶属度最大的超盒的类别作为该样本的类别。,二维空间中超盒的分布情况 对应的分类界面 (“*”表示“1”类样

30、本，“O”表示“2”类样本),基于距离空间的KNN方法及其衍生方法 基于归纳的决策树分类方法 基于最优判别平面或多面体的分类方法 基于模糊理论的分类方法 基于概率统计的Bayes分类算法,基于概率统计的Bayes分类算法,贝叶斯分类是一个统计学分类方法。它们能够预测一个要进行分类判断的数据对象属于某个类别的概率。 贝叶斯分类是基于贝叶斯定理（以下将会介绍）构造出来的。 朴素贝叶斯分类（Nave Bayesian classification）假设一个指定类别中各属性的取值是相互独立的。这一假设也被称为：类别条件独立，它可以帮助有效减少在构造贝叶斯分类时所需要进行的计算量。 对分类方法进行比较的

31、有关研究结果表明：基本贝叶斯分类在分类性能上与决策树和神经网络相媲美。在处理大型数据库时，贝叶斯分类法已表现出较高的分类准确性和运算性能。,背景知识：Bayes theorem,e.g. 用color和shape描述水果,假定，（相关的假设）H：x是apple 则 P(x)：所有训练样本中，colorred，shaperound的水果的概率 P(H)：所有训练样本中，fruitapple的概率 P(x|H)：已知训练样本中，fruitapple情况下，colorred，shaperound的概率 P(H|x)：测试记录为（colorred，shaperound）时，该样本属于apple的概率

32、P(x)，P(H)，P(x|H)皆为可计算项，所以可由这三项计算出x属于某一类的概率大小P(H|x). Bayes公式的实质：从先验概率P(Ci)到后验概率P(Ci|x),2. Nave Bayes classification method (基于最小错误率的Bayes方法),按照Bayes理论求后验概率P(Ci|x)，到时哪个概率大，就被归到哪一类。,Example: 已知一个训练集，4个属性，14个样本，用Bayes方法判定第15号样本属于哪一类。,3. 贝叶斯信念网络,朴素贝叶斯分类是基于各类别相互独立这一假设来进行分类计算的，也就是要求若给定一个数据样本类别，其样本属性的取值应是相互独立的。这一假设简化了分类计算复杂性。若这一假设成立，则与其它分类方法相比，基本贝叶斯分类是最准确的