数据挖掘5分类

数据挖掘发现知识的类型广义知识关联知识分类知识预测型知识偏差型知识Outline：§5.1一般概念(classification的处理过程、现有的常用算法、分类和回归的预报指标）§5.2分类和回归的预报评价§5.3分类方法基于距离空间的KNN方法及其衍生方法基于归纳的决策树分类方法基于最优判别平面或多面体的分类方法基于模糊理论的分类方法基于概率统计的BayesNet分类算法§5.4回归方法第五章分类与回归§5.1一般概念分析已知的数据，构造模型（创建分类器分类器），该模型可以用来对未知的数据做预测，判定其目标值（类别或连续值）。统称为预报：描述某类数据集的模型或预测数据的变化趋势。只是分类预测的是分类标号（离散的，有限的数值）——分类器回归预测的是连续值——连续的函数模型E.g.同一组数据，就有可能存在这两种预报温度压力流量产品合格与否产量T1P1I1C1Y1T2P2I2C2Y2T3P3I3C2Y3...............2211),,(cthenconditioncthenconditionIPTfif满足),,(IPTfY分类：回归：1.分类的处理过程：First,通过分类算法对数据的分析和学习，建立一个可用分类规则表示的模型或分类器。表现形式有：（1）规则if…then（2）判别平面g(x)=wT(x)then，用上述分类规则对测试样本进行分类，求分类准确率，如果分类准确率达到可接受的程度，该规则就可以用于新数据的分类。对于回归，训练样本与目标之间的关系，建立相关的函数模型),,(IPTfY具体步骤1建立一个模型，描述给定的数据类集或概念集（简称训练集）通过分析由属性描述的数据库元组来构造模型。每个元组属于一个预定义的类，由类标号属性确定。用于建立模型的元组集称为训练数据集，其中每个元组称为训练样本。由于给出了类标号属性，因此该步骤又称为有监督的学习（supervised）。如果训练样本的类标号是未知的，则称为无监督的学习（unsupervised）。学习模型可用分类规则、决策树和数学公式的形式给出。具体步骤2使用模型进行分类首先对模型分类准确率进行估计如果一个学习所获模型的准确率经测试被认为是可以接受的，那么就可以使用这一模型对未知数据或对象（其类别未知）进行分类。2．现有的常用算法分类：基于概率统计的BayesNet基于归纳学习的DecisionTree基于向量空间模型的KNN，NN，Case-basedreasoning，roughset基于模糊集的Fuzzytheory,FMMNN基于统计学习理论的SVM基于超平面或超多面体的Fisher，PCA，PLS，LMap回归：一元（多元）线性（非线性）回归，核，SVR§5.2分类和回归的预报评价包括对得到的模型、求解该模型的过程以及用该模型预报未知等一系列工作的评价。①分类/回归的准确率②速度，包括建模和测试花费的时间③稳健性，对各种类型的data都适用④可升级性，易于改进与升级⑤可理解性，所建立的规则模型要易于理解，便于用户或专家解释(在理论和实际应用中都可以解释)①.分类/回归的准确率评价一个模型的准确率：一般是把已知样本分成两个子集（训练集和测试集）。模型是通过分析训练集得到，评价的是该模型用于预报测试集样本的准确率（预报误差）分类：误报率回归：均方误差、平均误差、相对误差…预报准确率的测试方法根据训练集、测试集的不同划分，可分为不同的测试方法：（1）．Holdoutmethod任意划分两个子集（只规定好数目，至于哪个样本划到哪里是随机的）。可以做多次，然后取平均值。（2）．K－foldcross-validation（k-交叉验证方法）所给初始样本任意地分成样本数大致相等的k个子集（s1,s2,…sk），并做k次训练与测试：第一次，以s1为TestSampleSet，其它的（S2s3,…sk）为trainingsample，…，第i次，以si为TestSampleSet，其它的为trainingsampleset。最后，准确率就是k次的测试结果之和。（3）．留n法固定每次有n个样本做测试集，重复做一直到所有样本都被测试过。n＝1时，就是留一法（Jackknife检验）。留一法也是k-交叉验证方法的特例（k＝Ns）有几个样本就分成几个子集）（4）．Self-consistency检验用训练集数据进行学习，并对训练集数据进行检验分类准确率的其他表示方法对于分类问题，评价准确性还要更复杂一些，因为关系到各类别数据的分布情况。例如，对于一个样本集，如果其中样本的分类：其中的某类样本数10％，那么分类器的准确率再高，也只是对另一类样本有意义，而对该类样本没有意义。——样本的不平衡性问题，小样本问题为解决这个问题，提出了分类准确率的另外一些度量方式：§5.3几种分类方法基于距离空间的KNN方法及其衍生方法基于归纳的决策树分类方法基于概率统计的Bayes分类算法基于模糊理论的FMMNN分类方法基于最优判别平面或多面体的分类方法基于距离空间的KNN及其衍生方法1.美国的E.Fix和J.L.Hodges在1951年提出来的KNN方法KNN是一种最经典的模式识别方法，该方法可用于线性不可分的多类样本的识别。K为最近邻个数。基本原理：“物以类聚”、“少数服从多数”。即如果未知样本的K个近邻样本都是一种类型，那么该未知样本就和它们同类；若这K个类型不一致，将该样本归入其中具有最多数样本的那一类，所以K值常为奇数。KNN方法存在的三个问题：(1)K值选取。K值的选择会直接影响到分类结果。针对某一问题应该如何确定K值,目前为止还没有统一定律。(2)计算量。因为每判断一个样本都需要重新计算它与所有其它样本的距离，所以计算量非常大。(3)最近邻规则。近邻规则包括采用何种距离、求得距离后又以哪种标准判别未知样本的属类等等。2．ALKNN法（改进近邻匹配规则）ALKNN法根据每类样本的数目和分散程度，对不同的类可以选取不同的K值。各类的Ki值选定后，用一定的算法对类中的样本的概率进行估算，并根据概率大小对它们进行类的划分。在ALKNN法中，以xi与类Ci的Ki个近邻中最远一个样本的距离r为半径，以x为中心，计算相应的超球的体积。并认为超球体积越小，类Ci在xi处的概率密度越大，这一概率密度可由下式计算P(x/Ci)=(Ki-1)/v(x/Ci)此处v(x/Ci)为Ci的超球体积。对于未知样本，哪一类计算的P(x/gi)最大，即归入哪一类。3．Fastk-NearestNeighborClassificationUsingCluster_BasedTrees（改进速度）First,TheClusterTreeAlgorithmCluster-BasedTreeGenerationClassificationThen,Evaluation（NIST/MNIST)Condensation-basedtreealgorithmCluster-BasedTreeGeneration)(z)(z)(zl给定一个数据集T，设定三个局部特性参数：样本z与最近邻的非同类样本之间的非相似度（距离）与z的距离小于等于上述的最近距离的所有同类样本点的集合上述样本点集合中的包含的样本个数Step0：初始化聚类树（一个样本作为一个节点）——BottomLevel。Step1：计算T中每个样本的三个参数，然后根据进行降序排列。)(zlStep2：把具有最大l值的样本（z1）作为一个Hypernode，做好z1与)(1z集合中的样本的链接，并在bottomlevel中去除这些样本。Step3：对bottomlevel中的样本重复step1和step2的操作，直至为空。Step4：设定一个阈值，对hyperlevel中的样本进行聚类：每一聚类的半径小于或等于。形成了plevel。Step5：增加的值，重复step4的操作，直到最后一层的节点数为1。阈值Result：生成的树：•toplevel只有一个节点•bottomlevel的节点个数＝样本数•每个节点都链接了好多样本，但只有hyperlevel的每个节点所对应的样本集是保证属于同类别的。Classification：ForanunknownsampleX,willbeclassifiedasfollows:Step0:计算X与toplevel中每个节点的非相似度，并选定k个最相似的节点记录到Lx集合。Step1：计算X和Lx中的节点所对应的各子节点之间的非相似度，然后选取k个最相似的节点，更新Lx集合。Step2：重复step1，一直到Lx集合包括的是hyperlevelnodes。Step3：对Lx中的节点（Y）求)(Y，并建立新的集合LxYYXYdYLh),(),(|Step4：计算X和Lx中的节点所对应的各子节点之间的非相似度，然后选取k个最相似的节点，用投票法来分类。类别的，X就属于该类别，完成分类。否则转向Step4。如果Lh中的所有节点是同一优点：可以事先确定分类模型，大大减少test的时间基于距离空间的KNN方法及其衍生方法基于归纳的决策树分类方法基于模糊理论的FMMNN分类方法基于最优判别平面或多面体的分类方法基于概率统计的Bayes分类算法基于归纳的决策树分类方法用于分类和预测。决策树学习是以样本为基础的归纳学习方法。基本算法是贪心算法，采用自顶向下的递归方式构造决策树。DescionTree（DT）包括：内部节点（非叶节点，对属性的描述）：根节点，支节点，用方框表示。每个内部节点都对应一个用于分割数据集的属性。叶节点（末节点，对类别的描述）：用圈表示，每个叶节点都对应一个类别标识C的值，说明上面属性取值情况下的子样本集都属于同一类构建和剪枝记录年龄汽车类型风险023FamilyHigh117SportsHigh243SportsHigh368FamilyLow432truckLow520FamilyhighExample：汽车保险案例训练集决策树决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。若要对一个实体分类，从树根开始进行测试，按特征的取值分枝向下进入下层节点，对该节点进行测试，过程一直进行到叶节点，实体被判为属于该叶节点所标记的类别。决策树算法基本算法（贪心算法）自上而下分而治之的方法开始时，所有的数据都在根节点属性都是种类字段(如果是连续的，将其离散化)所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割DT的任务：•在DT内部节点进行属性值的比较，根据不同的属性值判断从该节点向下的分支，并在叶节点处得出结论。（通过训练已知数据集，构造DT）。•从根节点到叶节点的路径：对应着要寻找的分类规律。（一条路径一条规律）测定一个新样本的类别：根据各属性值，由上到下遍历决策数。关键：寻找合适的内部节点。（根据某准则选择适当的属性作为内部节点）根据准则的不同，决策树算法可以分为多类，常见的有：基于信息论的：ID3、C4.5、基于最小GINI指标的：CART、SLIQ、SPIRINT1、信息增益（准则）假定S为训练样本集，每个训练样本的类别已知N：样本总数m：类别总数Ni：属于第i(i=1,2,…,m)类的样本数，Then，判定某个样本属于哪一类的期望信息定义为:imiiimiimppNNNNNNNI122121loglog),,(NNimi,1),,()()(1121mjjvjmjjjNNINNNNAE一个属性A有v个取值：{a1,a2,…,av}。则能把样本集S划分为v个子集：{S1,S2,…,Sv},即Sj内包含的样本其属性A的取值皆为aj。假设Sj中包含的第i类样本的样本数为Nij，则定义属性A的熵