《数据挖掘7章分类和预测.ppt》由会员分享，可在线阅读，更多相关《数据挖掘7章分类和预测.ppt（37页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、分类和预测（1）主讲人：蔡伟杰Chttp:/2022/12/51Data Mining:Concepts and Techniques第七章：分类和预测n什么是分类？什么是预测n关于分类和预测的一些问题n使用决策树进行分类n贝叶斯分类n带回馈的分类n基于关联规则的分类n其他分类方法n预测n分类的准确率n总结2022/12/52Data Mining:Concepts and Techniquesn分类 n预测种类字段n基于训练集形成一个模型，训练集中的类标签是已知的。使用该模型对新的数据进行分类Prediction:n对连续性字段进行建模和预测。n典型应用n信用评分nDirect Market
2、ingn医疗诊断n分类和预测2022/12/53Data Mining:Concepts and Techniques分类的两个步骤n模型创建:对一个类别已经确定的模型创建模型n没一条记录都属于一个确定的类别，我们使用类标签属性记录类别。n用于创建模型的数据集叫:训练集n模型可以用分类规则，决策树，或者数学方程的形式来表达。n模型使用:用创建的模型预测未来或者类别未知的记录n估计模型的准确率n使用创建的模型在一个测试集上进行预测，并将结果和实际值进行比较n准确率：n测试集和训练集是独立的。2022/12/54Data Mining:Concepts and Techniques分类过程：模型创
3、建训练集分类算法IFrank=professorORyears6THENtenured=yes模型2022/12/55Data Mining:Concepts and Techniques分类过程(2):使用模型模型测试集未知数据(Jeff,Professor,4)Tenured?2022/12/56Data Mining:Concepts and Techniques有监督和无监督学习n有监督学习(分类)n训练集是带有类标签的n新的数据是基于训练集进行分类的。n无监督学习(聚集)n训练集是没有类标签的。n提供一组属性，然后寻找出训练集中存在类别或者聚集。2022/12/57Data Mini
4、ng:Concepts and Techniques分类和预测n什么是分类？什么是预测n关于分类和预测的一些问题n使用决策树进行分类n贝叶斯分类n带回馈的分类n基于关联规则的分类n其他分类方法n预测n分类的准确率n总结2022/12/58Data Mining:Concepts and Techniques关于分类和预测的一些问题(1):数据准备n数据清洗n对数据进行预处理，消除噪音和丢失值。n相关性分析(属性选择)n去掉不相关或者冗余的属性n数据转换n泛化或者对数据进行标准化2022/12/59Data Mining:Concepts and Techniques关于分类和预测的问题(2):
5、评估分类方法n预测准确率n速度n创建速度n使用速度n强壮性n处理噪音和丢失值n伸缩性n对磁盘驻留数据的处理能力n可解释性:n对模型的可理解程度。n规则好坏的评价n决策树的大小n分类规则的简明性2022/12/510Data Mining:Concepts and Techniques分类和预测n什么是分类？什么是预测n关于分类和预测的一些问题n使用决策树进行分类n贝叶斯分类n带回馈的分类n基于关联规则的分类n其他分类方法n预测n分类的准确率n总结2022/12/511Data Mining:Concepts and Techniques使用决策树进行分类n决策树 n一个树性的结构n内部节点上选
6、用一个属性进行分割n每个分叉都是分割的一个部分n叶子节点表示一个分布n决策树生成算法分成两个步骤n树的生成n开始，数据都在根节点n递归的进行数据分片n树的修剪n去掉一些可能是噪音或者异常的数据n决策树使用:对未知数据进行分割n按照决策树上采用的分割属性逐层往下，直到一个叶子节点2022/12/512Data Mining:Concepts and Techniques训练集ID3算法2022/12/513Data Mining:Concepts and TechniquesOutput:A Decision Tree for“buys_computer”age?overcaststudent?
7、creditrating?noyesfairexcellent40nonoyesyesyes30.402022/12/514Data Mining:Concepts and Techniques决策树算法n基本算法（贪心算法）n自上而下分而治之的方法n开始时，所有的数据都在根节点n属性都是种类字段(如果是连续的，将其离散化)n所有记录用所选属性递归的进行分割n属性的选择是基于一个启发式规则或者一个统计的度量(如,information gain)n停止分割的条件n一个节点上的数据都是属于同一个类别n没有属性可以再用于对数据进行分割2022/12/515Data Mining:Concepts
8、and Techniques属性选择的统计度量nInformation gain(ID3/C4.5)n所有属性假设都是种类字段n经过修改之后可以适用于数值字段nGini index(IBM IntelligentMiner)n能够适用于种类和数值字段2022/12/516Data Mining:Concepts and TechniquesInformation Gain(ID3/C4.5)n选择属性的标准：具有最高Information Gainn假设有两个类,P 和 Nn假设集合S中含有p个类别P的记录,n个类别N的记录n决定任意一个记录属于类别P或者N所需要的information.20
9、22/12/517Data Mining:Concepts and TechniquesInformation Gain 在决策树中的使用n假设使用属性A将把集合S分成 V份 S1,S2,Sv n如果 Si 中包含 pi 个类别为 P的记录,ni 个类别为 N,的记录。那么熵就是(entropy),n从而这个信息增益就是2022/12/518Data Mining:Concepts and Techniques使用信息增益进行属性选择gClass P:buys_computer=“yes”gClass N:buys_computer=“no”gI(p,n)=I(9,5)=0.940gCompu
10、te the entropy for age:HenceSimilarly2022/12/519Data Mining:Concepts and TechniquesGini Index(IBM IntelligentMiner)n集合T包含N个类别的记录，那么其Gini指标就是pj 类别j出现的频率n如果集合T分成两部分 N1 and N2。那么这个分割的Gini就是n提供最小Ginisplit 就被选择作为分割的标准(对于每个属性都要遍历所有可以的分割方法).2022/12/520Data Mining:Concepts and Techniques几种经典算法介绍nCARTmin(P(c
11、1),P(c2)2P(c1)P(c2)P(c1)logP(c1)+P(c2)logP(c2)C4.5(ID3)nC4.5(ID3)n对种类字段处理时，缺省是对每个值作为一个分割nGain和Gain RationCHAIDn在Overfitting前停止树的生成n必须都是种类字段n选择分割。X2检验 2022/12/521Data Mining:Concepts and Techniques从树中生成分类规则n用 IF-THEN 这种形式来表现规则n每个叶子节点都创建一条规则n每个分割都成为一个规则中的一个条件n叶子节点中的类别就是Then的内容n规则对于人来说更容易理解n例子IF age=“=
12、30”AND student=“no”THEN buys_computer=“no”IF age=“40”AND credit_rating=“excellent”THEN buys_computer=“yes”IF age=“=30”AND credit_rating=“fair”THEN buys_computer=“no”2022/12/522Data Mining:Concepts and Techniques在分类中避免过度适应(Overfit)n在训练集中生成的会可能会 Overfitn太多的分支,有些可能是对异常例外的反映n在进行预测的时候准确率比较差n两种 n预修剪:n难点：选
13、择一个域值比较困难n后修建:先生成完整的树，然后进行修剪n使用另外一个的一个测试集来决定哪个树最好2022/12/523Data Mining:Concepts and Techniques决定最终树大小的方法n使用部分数据：n使用全部数据：n使用一个统计测试(e.g.,chi-square)来估计保留或者修剪掉一个分支的影响n使用最小描述长度(MDL)原则:n当树的Coding最小的时候最佳。2022/12/524Data Mining:Concepts and Techniques对基本决策树的提高n加入对连续字段的支持n采用 A=V的形式n处理空值n用最常见的值代替n每个可能的值都给一个
14、概率n属性构造n在现有属性上创建新的属性,主要是针对一些稀疏属性n从而降低 fragmentation,repetition,and replication2022/12/525Data Mining:Concepts and Techniques在大型数据库中进行分类n分类在统计和机器学习中有广泛的研究n伸缩性:对几百万记录和几百个属性进行训练的时候，能够达到一定的速度。n在数据挖掘中为什么使用决策树?n相对比较快的学习速度(和其它学习方法比较来说)n能够转换成容易理解的分类规则n能够使用SQL语句查询数据库n分类的准确率也不差2022/12/526Data Mining:Concepts
15、and TechniquesScalable Decision Tree Induction 数据挖掘中提出的方法nSLIQ(EDBT96 Mehta et al.)nSPRINT(VLDB96 J.Shafer et al.)nPUBLIC(VLDB98 Rastogi&Shim)nRainForest (VLDB98 Gehrke,Ramakrishnan&Ganti)nbuilds an AVC-list(attribute,value,class label)2022/12/527Data Mining:Concepts and Techniques SLIQ算法介绍n总揽：预排序、广
16、度优先、种类字段快速分割、MDL修剪方法n预排序：减少对数值字段进行排序消耗的时间n属性列表（attribute list）：n属性值n索引n类列表（class list）：n类标签n指向树中的节点2022/12/528Data Mining:Concepts and TechniquesSliq分类算法2022/12/529Data Mining:Concepts and TechniquesSliq分类算法n进行节点的分割：广度优先n对当前树中所有叶子节点分割的计算都是在同一遍中完成的。n引进的数据结构：类分布表n数值字段：类标签、频率n种类字段：属性值、类标签、频率n对数值字段进行分割计
17、算：2022/12/530Data Mining:Concepts and TechniquesSliq分类算法2022/12/531Data Mining:Concepts and TechniquesSliq分类算法n对种类字段进行分割：n通过对数据的扫描生成类分布表n寻找分割集合n如果不同字段的值少于预定值，进行完全搜索n如果不同字段的值大于预定值，使用贪心算法2022/12/532Data Mining:Concepts and TechniquesSliq分类算法n树的修剪：采用了MDL策略nCost(M,D)=cost(D|M)+cost(M)n整个算法包括两个部分：n编码方法n不
18、同子树的比较方法2022/12/533Data Mining:Concepts and Techniques基于数据立方体的决策树nIntegration of generalization with decision-tree induction(Kamber et al97).n在最低概念层上进行分类n例如,precise temperature,humidity,outlook,etc.n低的层次，分散的类别，过多的叶子节点n模型解释的问题.n基于Cube的多层分类n在多个层次上进行相关性分析.n在多个层次上进行Information Gain的计算.2022/12/534Data Mining:Concepts and Techniques 结果显示(一)2022/12/535Data Mining:Concepts and Techniques 结 果 显 示(二)2022/12/536Data Mining:Concepts and Techniqueshttp:/ Any Question?2022/12/537Data Mining:Concepts and Techniques