《数据挖掘》课程PPT-分类和预测资料.ppt

《《数据挖掘》课程PPT-分类和预测资料.ppt》由会员分享，可在线阅读，更多相关《《数据挖掘》课程PPT-分类和预测资料.ppt（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、分类 VS. 预测n分类和预测是两种数据分析形式，用于提取描述重要数据类或预测未来的数据趋势 的模型q分类：n预测类对象的分类标号（或离散值）n根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据q预测：n建立连续函数值模型n比如预测空缺值，或者预测顾客在计算机设备上的花费n典型应用q欺诈检测、市场定位、性能预测、医疗诊断分类和预测-示例n分类q银行贷款员需要分析数据，来弄清哪些贷款申请者是安全的，哪些是有风险的（将贷款申请者分为“安全”和“有风险”两类）n我们需要构造一个分类器来预测类属编号，比如预测顾客属类n预测q银行贷款员需要预测贷给某个顾客多少钱是安全的n构造一个预测器

2、，预测一个连续值函数或有序值，常用方法是回归分析数据分类一个两步过程 (1)n第一步，也成为学习步学习步，目标是建立描述预先定义的数据类或概念集的分类器q分类算法通过分析或从训练集“学习”来构造分类器。q训练集由数据库元组（用n维属性向量表示）和他们相对应的类编号组成；假定每个元组属于一个预定义的类n训练元组训练元组：训练数据集中的单个元组q学习模型可以用分类规则、决策树或数学公式的形式提供数据分类一个两步过程 (2)n第二步，使用模型，对将来的或未知的对象进行分类q首先评估模型的预测准确率n对每个测试样本，将已知的类标号和该样本的学习模型类预测比较n模型在给定测试集上的准确率是正确被模型分类

3、的测试样本的百分比n测试集要独立于训练样本集，否则会出现“过分拟合”的情况第一步建立模型训练数据集NAME RANKYEARS TENUREDMikeAssistant Prof3noMaryAssistant Prof7yesBill Professor2yesJimAssociate Prof7yesDaveAssistant Prof6noAnneAssociate Prof3no分类算法IF rank = professorOR years 6THEN tenured = yes 分类规则第二步用模型进行分类分类规则测试集NAMERANKYEARS TENUREDTomAssistan

4、t Prof2noMerlisa Associate Prof7noGeorge Professor5yesJoseph Assistant Prof7yes未知数据(Jeff, Professor, 4)Tenured?监督学习 VS. 无监督学习n监督学习（用于分类）q模型的学习在被告知每个训练样本属于哪个类的“指导”下进行q新数据使用训练数据集中得到的规则进行分类n无监督学习（用于聚类）q每个训练样本的类编号是未知的，要学习的类集合或数量也可能是事先未知的q通过一系列的度量、观察来建立数据中的类编号或进行聚类数据预测的两步过程n数据预测也是一个两步的过程，类似于前面描述的数据分类q对于预

5、测，没有“类标号属性”q要预测的属性是连续值，而不是离散值，该属性可简称“预测属性”nE.g. 银行贷款员需要预测贷给某个顾客多少钱是安全的n预测器可以看作一个映射或函数y=f(X)q其中X是输入；y是输出，是一个连续或有序的值q与分类类似，准确率的预测，也要使用单独的测试集准备分类和预测的数据n通过对数据进行预处理，可以提高分类和预测过程的准确性、有效性和可伸缩性q数据清理n消除或减少噪声，处理空缺值，从而减少学习时的混乱q相关分析n数据中的有些属性可能与当前任务不相关；也有些属性可能是冗余的；删除这些属性可以加快学习步骤，使学习结果更精确q数据变换与归约n数据可以通过规范化进行变换，将所给

6、属性的所有值按比例进行缩放，使其落入一个较小的指定区间，例 0.0, 1.0（ANN和设计距离的度量方法中常用）n可以将数据概化到较高层概念比较分类方法n使用下列标准比较分类和预测方法q预测的准确率：模型正确预测新数据的类编号的能力q速度：产生和使用模型的计算花销q健壮性：给定噪声数据或有空缺值的数据，模型正确预测的能力q可伸缩性：对大量数据，有效的构建分类器或预测可伸缩性：对大量数据，有效的构建分类器或预测器的能力器的能力q可解释性：学习模型提供的理解和洞察的层次用决策树归纳分类 (1)n什么是决策树？q类似于流程图的树结构q每个内部节点表示在一个属性上的测试q每个分枝代表一个测试输出q每个

7、树叶节点存放一个类编号age?student?credit rating?noyesfairexcellentyouthseniornonoyesyesyesMiddleaged决策树：决策树：Buys_computer用决策树归纳分类 (2)n使用决策树分类q给定一个类标号未知的元组X，在决策树上测试元组的属性值，跟踪一条由根到叶节点的路径，叶节点存放该元组的类预测。q决策树容易转换为分类规则n决策树的生成由两个阶段组成q决策树构建n使用属性选择度量来选择将元组最好的划分为不同的类的属性n递归的通过选定的属性，来划分样本 （必须是离散值）q树剪枝n决策树建立时，许多分枝反映的是训练数据中的噪

8、声和离群点点，树剪枝试图识别并剪去这种分枝，以提高对未知数据分类的准确性决策树归纳策略 (1)n输入q数据划分D是训练元组和对应类标号的集合qattribute_list,候选属性的集合qAttribute_selection_method，指定选择属性的启发性过程算法步骤q树以代表训练样本的单个节点（N）开始q如果样本都在同一个类，则该节点成为树叶，并用该类标记1.否则，算法调用Attribute_selection_method，选择能够最好的将样本分类的属性；确定“分裂准则”，指出“分裂点”或“分裂子集”。决策树归纳策略 (2)n对测试属性每个已知的值，创建一个分支，并以此划分元组n算法

9、使用同样的过程，递归的形成每个划分上的元组决策树。一旦一个属性出现在一个节点上，就不在该节点的任何子节点上出现n递归划分步骤停止的条件划分D（在N节点提供）的所有元组属于同一类没有剩余属性可以用来进一步划分元组使用多数表决没有剩余的样本给定分支没有元组，则以D中多数类创建一个树叶属性选择度量n属性选择度量是一种选择分裂准则，将给定类标号的训练元组最好的进行划分的方法q理想情况，每个划分都是“纯”的，即落在给定划分内的元组都属于相同的类q属性选择度量又称为分裂准则n常用的属性选择度量q信息增益q增益率qGini指标信息增益 (1)nS是一个训练样本训练样本的集合，该样本中每个集合的类编号类编号已

10、知。每个样本为一个元组元组。有个属性用来判定某个训练样本的类编号n假设S中有m个类，总共s个训练样本，每个类Ci有si个样本(i1,2,3.m)，那么任意一个样本属于类Ci的概率是si / s，那么用来分类一个给定样本的期望信息期望信息是：sssssssInfoimiim2121log),.,(信息增益 (2)n一个有v个值的属性Aa1,a2,.,av可以将S分成v个子集S1,S2,.,Sv，其中Sj包含S中属性A上的值为aj的样本。假设Sj包含类Ci的sij个样本。根据A的这种划分的期望信息称为A的熵熵nA上该划分的获得的信息增益定义为：n具有高信息增益的属性，是给定集合中具有高区分度的属性

11、。所以可以通过计算S中样本的每个属性的信息增益，来得到一个属性的相关性的排序。),.,(.)(111mjjvjmjjssIsssAE)(),.,()(21AEsssIAGainmageincomestudentcredit_ratingbuys_computeryouthhighnofairnoyouthhighnoexcellentnomiddle_agedhighnofairyesseniormediumnofairyesseniorlowyesfairyesseniorlowyesexcellentnomiddle_agedlowyesexcellentyesyouthmediumnof

12、airnoyouthlowyesfairyesseniormediumyesfairyesyouthmediumyesexcellentyesmiddle_agedmediumnoexcellentyesmiddle_agedhighyesfairyesseniormediumnoexcellentno判定归纳树算法示例 (1)n对于上述数据，可以略过步骤1，2n步骤3，计算基于熵的度量信息增益，作为样本划分的根据qGain(age)=0.246qGain(income)=0.029qGain(student)=0.151qGain(credit_rating)=0.048n然后，对测试属性每

13、个已知的值，创建一个分支，并以此划分样本，得到第一次划分判定归纳树算法示例 (2)判定归纳树算法示例 (3)age?overcaststudent?credit rating?noyesfairexcellentyouthseniornonoyesyesyesMiddle aged防止分类中的过分适应n产生的决策树会出现过分适应数据的问题q由于数据中的噪声和孤立点，许多分枝反应的是训练数据中的异常q对新样本的判定很不精确n防止过分适应的两种方法q先剪枝：通过提前停止树的构造如果在一个节点划分样本将导致低于预定义临界值的分裂（e.g. 使用信息增益度量）n选择一个合适的临界值往往很困难q后剪枝：

14、由“完全生长”的树剪去分枝对于树中的每个非树叶节点，计算该节点上的子树被剪枝可能出现的期望错误率n使用一个独立的测试集来评估每颗树的准确率，就能得到具有最小期望错误率的决策树由决策树提取分类规则n可以提取决策树表示的知识，并以IF-THEN形式的分类规则表示n对从根到树叶的每条路径创建一个规则n沿着给定路径上的每个属性-值对形成规则前件（IF部分）的一个合取项n叶节点包含类预测，形成规则后件（THEN部分）nIF-THEN规则易于理解，尤其树很大时n示例：nIF age = “youth” AND student = “no” THEN buys_computer = “no”nIF age

15、= “youth” AND student = “yes” THEN buys_computer = “yes”nIF age = “middle_aged” THEN buys_computer = “yes”nIF age = “senior” AND credit_rating = “excellent” THEN buys_computer = “yes”nIF age = “senior” AND credit_rating = “fair” THEN buys_computer = “no”可伸缩性与决策归纳树n分类挖掘是一个在统计学和机器学习的领域也被广为研究的问题，并提出了很多

16、算法，但是这些算法都是内存驻留的n可伸缩性问题：要求以合理的速度对数以百万要求以合理的速度对数以百万计的样本和数以百计的属性的进行分类挖掘计的样本和数以百计的属性的进行分类挖掘n由大型数据库构造决策树q首先将样本划分为子集，每个子集可以放在内存中q然后由每个自己构造一颗决策树q输出的分类法将每个子集的分类法组合在一起q（其他方法包括SLIQ, SPRINT,RainForest等等）贝叶斯分类n贝叶斯分类利用统计学中的贝叶斯定理，来预测类成员的概率，即给定一个样本，计算该样本属于一个特定的类的概率。n朴素贝叶斯分类：假设每个属性之间都是相互独立的，并且每个属性对非类问题产生的影响都是一样的。)

17、()()|()|(DPhPhDPDhP后向传播分类n后向传播是一种神经网络学习算法；神经网络是一组连接的输入/输出单元，每个连接都与一个权相连。在学习阶段，通过调整神经网络的权，使得能够预测输入样本的正确标号来学习。n优点q预测精度总的来说较高q健壮性好，训练样本中包含错误时也可正常工作q输出可能是离散值、连续值或者是离散或量化属性的向量值q对目标进行分类较快n缺点q训练（学习）时间长q蕴涵在学习的权中的符号含义很难理解q很难根专业领域知识相整合SVM支持向量机n使用一种非线性的映射，将原训练数据映射到较高的维n一个数据被认为是p维向量，数据在这个p维向量空间中被分为两类；SVM的目的是找到一

18、个p-1维的超平面，来划分p维向量空间的数据q在新的维上，它搜索线性最佳分离超平面 (即将一类的元组与其他类分离的“决策边界”)。n使用一个适当的对足够高维的非线性映射，两类的数据总可以被超平面分开。nSVM 使用支持向量（“基本”训练元组）和边缘（由支持向量定义）发现该超平面。SVM-特点和应用n特点: 训练时间非常长，但对复杂的非线性决策边界的建模能力是高度准确的（使用最大边缘）q可以用来预测和分类n应用: q手写数字识别，对象识别，语音识别, 以及基准时间序列预测检验SVM一般原理支持向量小边缘大边缘August 11, 2022Data Mining: Concepts and Tec

19、hniques31SVM当数据是线性可分的时候m设给定的数据集 D 为 (X1, y1), , (X|D|, y|D|), 其中Xi是训练元组，具有相关联的类标号yi。可以画出无限多条分离直线（或超平面）将类+1的元组与类-1的元组分开，我们想找出“最好的”那一条 (对先前未见到的元组具有最小分类误差的那一条）。SVM 要搜索具有最大边缘的超平面，即最大边缘超平面最大边缘超平面 (MMH)其他分类方法nk-最临近分类q给定一个未知样本，k-最临近分类法搜索模式空间，找出最接近未知样本的k个训练样本；然后使用k个最临近者中最公共的类来预测当前样本的类标号n基于案例的推理q样本或案例使用复杂的符号

20、表示，对于新案例，先检测是否存在同样的训练案例；如果找不到，则搜索类似的训练案例n遗传算法q结合生物进化思想的算法n粗糙集方法n模糊集方法q允许在分类规则中定义“模糊的”临界值或边界什么是预测？n预测是构造和使用模型评估无样本类，或评估给定样本可能具有的属性或值空间。n预测和分类的异同n相同点q两者都需要构建模型q都用模型来估计未知值n预测当中主要的估计方法是回归分析q线性回归和多元回归q非线性回归n不同点q分类法主要是用来预测类标号（分类属性值）q预测法主要是用来估计连续值（量化属性值）线性回归、多元回归和非线性回归n线性回归：Y = + Xq其中和是回归系数，可以根据给定的数据点，通过最小

21、二乘法来求得n多元回归：Y = + 1X1 + 2 X2q线性回归的扩展，设计多个预测变量，可以用最小二乘法求得上式中的，1 和2n非线性回归：Y = + 1X1 + 2 X22+ 3 X33q对不呈线性依赖的数据建模q使用多项式回归建模方法，然后进行变量变换，将非线性模型转换为线性模型，然后用最小二乘法求解211)()(SiiiSiixxyyxxxy评估分类法的准确性n导出分类法后，再使用训练数据评估分类法，可能错误的导致乐观的估计n保持方法q给定数据随机划分为两个集合：训练集(2/3)和测试集(1/3)q训练集导出分类法，测试集对其准确性进行评估q随机子选样随机子选样：保持方法的一个变形，

22、将保持方法重复k次，然后取准确率的平均值nk-折交叉确认q初始数据被划分为k个不相交的，大小大致相同的子集S1,S2Skq进行k次训练和测试，第i次时，以Si做测试集，其他做训练集q准确率为k次迭代正确分类数除以初始数据集样本总数提高分类法的准确性nBagging技术和boosting技术都通过将T个学习得到的分类法C1,C2CT组合起来，从而创造一个改进的分类法C*nBagging技术q对训练集S进行T次迭代，每次通过放回取样选取样本集St，通过学习St得到分类法Ctq对于未知样本X，每个分类法返回其类预测，作为一票qC*统计得票，并将得票最高的预测赋予XnBoosting技术q每个训练样本赋予一个权值qCt的权值取决于其错误率结束结束