《华中科技大学谭毅华_数据挖掘4-分类》由会员分享，可在线阅读，更多相关《华中科技大学谭毅华_数据挖掘4-分类（113页珍藏版）》请在金锄头文库上搜索。
1、Data Mining Yihua Tan 2024/9/3数据挖掘：分类数据挖掘：分类 谭谭 毅毅 华华 Y华中科技大学图像识别与人工智能研究所华中科技大学图像识别与人工智能研究所 Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p2内内 容容C分类和预测的基本概念C关于分类和预测的问题C分类的方法C决策树分类器CBayesian分类器C后向传播分类器CSVM分类器C惰性学习法分类C其它分类方法C预测的方法C分类和预测方法的评估Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 3分类VS.预测C分类: E预测类标号E基
2、于训练集和值（类标号）构造数据分类模型 ，并对新的数据进行分类C预测: E对连续函数建模, i.e., 预测未知或丢失的数据 C典型应用E信用证明E客户市场E医学诊断E目标识别Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 4分类：两步骤C模型构造: 描述预定类别的样本E每个样本属于预定义的类，由类标号属性确定 E模型构造的元组称为训练集E模型表达为分类规则 、决策树或数学公式C模型使用: 用于对未来或未知的对象分类E模型的估计精度H测试样本的已知标号和模型的分类结果进行对比H准确率为测试样本由模型正确分类的百分比H测试集独立于训练集, 否则会产生过拟合
3、现象E若准确率可接受, 以该模型对未知类标号的数据元组分类Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 5分类过程1:模型构造训练数据分类算法IF rank = professorOR years 6THEN tenured = yes 分类器(模型)Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 6分类过程2:应用模型分类器测试数据未知数据(Jeff, Professor, 4)Tenured?Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p7内内 容容C分类和预测的基本概
4、念C关于分类和预测的问题C分类的方法C决策树分类器CBayesian分类器C后向传播分类器CSVM分类器C惰性学习法分类C其它分类方法C预测的方法C分类和预测方法的评估Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 8数据预处理和准备C数据清理E消除或减少数据噪声，处理缺失值。C相关分析E去除不相关或冗余属性C数据变换E规范化或归一化数据Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 9分类和预测方法的评价C精度E分类器精度: 正确地预测数据类标号的能力E预测器精度: 猜测数据的预测属性值 C速度E构造模型的时间
5、(训练时间)E应用模型的时间 (分类/预测时间)C鲁棒性: 对存在噪声或缺失值的数据，分类器或预测器正确分类的能力C可伸缩性: 大容量数据库，分类器或预测器的效率C可解释性E模型提供的理解和领悟能力C其它度量, e.g., 规则的好坏, 决策树大小 或分类规则的紧致度Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p10内内 容容C分类和预测的基本概念C关于分类和预测的问题C分类的方法C决策树分类器CBayesian分类器C后向传播分类器CSVM分类器C惰性学习法分类C其它分类方法C预测的方法C分类和预测方法的评估Data Mining Yihua Tan
6、IPRAI-HUST 2024/9/3 p 11决策树归纳分类C算法种类多EHunts Algorithm (one of the earliest)ECARTEID3, C4.5ESLIQ,SPRINT训练样本：购买计算机的统计表Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 12决策树的构造age?31.40student?credit rating?40fairexcellentyesnonoyesyesyesnoData Mining Yihua Tan IPRAI-HUST 2024/9/3 p 13基本决策树算法C基本算法 (贪婪算法)E自顶
7、向下的分治算法构造树E开始, 所有的训练样本和树根相连E属性为分类属性 (若是连续值，则离散化)E根据选定的属性递归地划分样本?如何选择H基于启发式或统计度量选取测试属性 (e.g., 信息增益)C停止划分的准则E所有样本均和属于同一类的节点连接E无剩下的属性用于继续划分样本 叶节点分类应用多数表决法E无剩余的样本Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 14划分示例C令 Dt 为到达节点 t，与之相连的所有样本集C一般过程:E若Dt 包含的样本属于同一类 yt, 则t 标记为叶节点，其标号为 ytE若 Dt 为空, 则t 是标号为 yd的叶节点E
8、若Dt 包含的样本超过一类, 以属性测试将样本进一步划分. 递归地应用此过程划分样本数据。Dt?Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 15划分示例Dont CheatRefundDont CheatDont CheatYesNoRefundDont CheatYesNoMaritalStatusDont CheatCheatSingle,DivorcedMarriedTaxableIncomeDont Cheat= 80KRefundDont CheatYesNoMaritalStatusDont CheatCheatSingle,Divorc
9、edMarried类标号Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 16决策树方法的关键问题C贪婪策略下的问题E如何划分数据H怎样指定属性的测试条件怎样指定属性的测试条件,区分为几类区分为几类?H怎样确定”最佳”划分?E何时停止划分?DtData Mining Yihua Tan IPRAI-HUST 2024/9/3 p 17属性的测试条件C和属性的类型有关CarType?FamilySportsLuxuryA?A1A2A3A?AThAThIncome?LowMediumHighIncome?20002000AS?yesnoCarType Fami
10、ly,Sportsyesno测试条件例子离散值连续值离散值Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 18决策树方法的关键问题C贪婪策略下的问题E如何划分数据H怎样指定属性的测试条件,区分为几类?H怎样确定怎样确定”最佳最佳”划分划分?E何时停止划分?DtData Mining Yihua Tan IPRAI-HUST 2024/9/3 p 19怎样确定最佳划分非同质性非同质性, ,不纯度高不纯度高同质性同质性, ,不纯度低不纯度低划分前划分前: : 类类 0 0有有1010个样本个样本, , 类类 1 1有有1010样本样本类同质分布优先需度量属性
11、节点的impurity 哪个测试条件最优？哪个测试条件最优？Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 20属性选择度量C属性选择度量划分规则E划分属性：度量得分高的属性C流行的属性选择度量E信息增益(ID3， C4.5)H选取时，偏向于多值属性E增益率(C4.5)H偏向不平衡划分EGini指标(IBM IntelligentMiner)H偏向于多值属性H类的数量很大时，计算较困难Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 21信息增益(Information Gain)C基于信息论“熵”，选取具有最大信息
12、增益的属性划分C在属性节点A处，样本集D所具有的熵 (p( j | D) 为类 j 在节点 t处的概率).C度量节点的均质性E当所有的类均匀分布时，最大为 (log nc)，具有 最多信息E当只有所有样本属于一类时，最小为 (0.0) ，具有最少信息C在属性A处，将样本分为v类的信息量C通过在属性A，形成v个分支后，信息增益为,增益最大的选为划分属性Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 22信息增益例子类 P: buys_computer = “yes”类 N: buys_computer = “no” 指 14个样本中有5个“age =30”
13、, 两个属于类p，2个属于类N ,因此Similarly,Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 23决策树首层age?4030.40Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 24增益率(Gain Ratio)CC4.5 (ID3的后继算法) 应用增益率克服信息增益的偏斜性 (信息增益的规范化)CEx.EGainRatio(income) = 0.029/0.926 = 0.031C具有最大增益率的属性选为划分属性Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p
14、25Gini指数CGini指数:节点属性 A划分样本的不纯度，设样本集为D(NOTE: p( j | D) 类 j 在样本D中的概率).E当所有样本均匀分布在不同类时，最大为(1 - 1/nc), 表示最小兴趣信息E当所有的样本属于一类时，最小 为(0.0)，表示最大兴趣信息Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 26基于Gini指数的划分C用于CART算法C在节点A，将训练集D划分为k个子集(子节点Di )，则以划分的不纯度加权和度量其优劣 ni = 子树 的训练样本个数i, n = 节点p处训练样本个数.Data Mining Yihua T
15、an IPRAI-HUST 2024/9/3 p 27Gini例子P(C1) = 0/6 = 0 P(C2) = 6/6 = 1Gini = 1 P(C1)2 P(C2)2 = 1 0 1 = 0 P(C1) = 1/6 P(C2) = 5/6Gini = 1 (1/6)2 (5/6)2 = 0.278P(C1) = 2/6 P(C2) = 4/6Gini = 1 (2/6)2 (4/6)2 = 0.444Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 28二值属性的Gini指数C划分为两个子集C带权划分的效果: Gini指数越小越好E寻求更大和更纯的划
16、分B?YesNoNode N1Node N2Gini(D1) = 1 (5/7)2 (2/7)2 = 0.174 Gini(D2) = 1 (1/5)2 (4/5)2 = 0.32Gini(Children) = 7/12 * 0.174 + 5/12 * 0.32= 0.204Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 29决策树方法的关键问题C贪婪策略下的问题E如何划分数据H怎样指定属性的测试条件,区分为几类?H怎样确定”最佳”划分?E何时停止划分何时停止划分H所有样本属于同一类，则中止H所有的样本具有相同的属性H其它的提前中止法Data Min
17、ing Yihua Tan IPRAI-HUST 2024/9/3 p 30ID3算法CID3(Examples, Class_no, Attributes) C创建树的根节点C如果样本属同一类C,返回该根结点，创建单节点树，并以C作为类标号C如果Attributes为空，那么返回根节点，其类标号为样本集中的多数类C否则开始EAAttributes中分类样本能力最好的属性（最大信息增益）中分类样本能力最好的属性（最大信息增益）E以A作为节点分类属性E对于A的每个可能值viH在节点下加一个新的分支对应测试A=viH令样本vi为样本集中中满足A属性值为vi的子集H如果Examplevi为空在这个新
18、分支下加一个叶子节点，节点的标号为样本中的多数类否则在新分支下加一个子树ID3（ Examplesvi,Class_no,Attributes-A）C结束C返回rootData Mining Yihua Tan IPRAI-HUST 2024/9/3 p 31决策树方法分类实践时存在的问题C确定决策树增长的深度C处理连续值的属性C处理属性值不完整的训练数据C处理不同代价的属性C提高计算效率Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 32过拟合现象噪声引起分类面扭曲噪声引起分类面扭曲数据缺失，使得决策树使用其数据缺失，使得决策树使用其它分类任务的预测值
19、进行分类它分类任务的预测值进行分类C分支太多，由噪声或野值点产生异常C分类未见数据时精度低Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 33剪枝方法处理过拟合C前剪枝 (Early Stopping Rule)E在生成完全树之前中止E典型的中止条件:H 所有的样本属于同一类H 所有的属性值相同E更严格的条件:H 样本数少于用户指定的数量H 样本的类分布独立于已知特征 (e.g., using 2 test)H 如果继续划分当前节点并不会改善不纯度 (e.g., Gini or information gain).Data Mining Yihua Ta
20、n IPRAI-HUST 2024/9/3 p 34剪枝方法处理过拟合C后剪枝E在生成完全树之后处理E以自底向上的方式修剪节点E如果修建后改善了泛化误差，则以叶节点代替子树E叶节点的类标号以子树中大多数样本的标号代替E可以使用 MDL 实现后剪枝Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 35错误率的估计C重置换错误率: 训练错误率 ( e(t) )C泛化错误率: 测试错误率 ( e(t)C泛化错误率估计方法:E乐观方法: e(t) = e(t)E悲观方法: H 对每个叶节点: e(t) = (e(t)+0.5) H 总错误率: e(T) = e(T
21、) + N 0.5 (N: 节点个数)H 对树有 30 叶节点， 训练集有10个错误 (共1000个样本): 训练错误率 = 10/1000 = 1% 泛化错误率 = (10 + 300.5)/1000 = 2.5%E减少错误率的剪枝 :H 使用验证数据集估计泛化错误Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 36后剪枝方法实例Class = Yes20Class = No10Error = 10/30训练错误率训练错误率( (划分前划分前) = 10/30) = 10/30悲观错误率悲观错误率( (划分前划分前) ) = (10 + 0.5)/30
22、 = 10.5/30= (10 + 0.5)/30 = 10.5/30训练错误率训练错误率 ( (划分后划分后) = 9/30) = 9/30悲观错误率悲观错误率( (划分后划分后) ) = (9 + 4 = (9 + 4 0.5)/30 = 11/30 0.5)/30 = 11/30剪枝剪枝! !Class = Yes8Class = No4Class = Yes3Class = No4Class = Yes4Class = No1Class = Yes5Class = No1Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 37最短描述长度剪枝算法CL
23、(Model,Data) = L(Data|Model) + L(Model)EL为用于编码的比特数.E搜索具有最短长度比特树的模型.CL(Data|Model) 对错分率编码.CL(Model) 对节点编码 (分支数) 和划分条件编码Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 38ID3的扩展C4.5C简单的深度优先构造树C合并具有连续值的属性C可处理缺失属性值的样本E未知值用常用值代替C使用不同的剪枝技术以避免树的不平衡E基于误分率的树叶节点代替子树C使用增益比选取属性C产生规则产生规则(if-then)CK次迭代交叉验证次迭代交叉验证C可从以下
24、网址下载:http:/www.cse.unsw.edu.au/quinlan/c4.5r8.tar.gzData Mining Yihua Tan IPRAI-HUST 2024/9/3 p 39分类树的增强C可使用连续值属性E通过将连续值分为若干离散区间集，动态地定义新的离散属性C处理缺失属性值E赋以最常用的值E给每个值赋以概率C属性构造E基于已有的属性，构造新的属性实现稀疏表达E减少重复（多次测试）和复制（同样的子树）Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p40内内 容容C分类和预测的基本概念C关于分类和预测的问题C分类的方法C决策树分类器CB
25、ayesian分类器C后向传播分类器CSVM分类器C惰性学习法分类C其它分类方法C预测的方法C分类和预测方法的评估Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 41Bayesian ClassifierC统计分类器: 实现概率预测, i.e., 预测类成员的概率C理论基础: Bayes定理 C性能: 简单的贝页斯分类器, nave Bayesian classifier, 和决策树及神经网络性能相当C可增量的: 在假设正确的前提下，每个训练样本可增加或减少其概率 先验知识和数据混合使用C标准: 尽管贝页斯方法计算上难以处理，但可提供标准的模型最优选择D
26、ata Mining Yihua Tan IPRAI-HUST 2024/9/3 p 42贝页斯定理C给定训练样本 X, 假设H的后验概率, P(H|X), 服从贝页斯定理C形式上可写为posteriori = likelihood x prior/evidenceC若P(Ci|X) 的概率高于所有的其它k类P(Ck|X)，则预测 X 属于 Ci 类C实际困难: 需要知道许多概率的先验知识, 这是很大的计算代价Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 43朴素贝页斯分类的预备知识C令 D 为训练元组集及其类标号, 每个元组可表示为n维向量 X =
27、(x1, x2, , xn)C假定 共有m 类 C1, C2, , Cm.C分类过程是后验概率的求解过程, i.e., 令 P(Ci|X)最大C从贝页斯定理C由于P(X) 为常数, 故计算 需令其最大化Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 44贝页斯分类器的推导C简单假设: 属性条件独立 (i.e., 属性间无依赖关系):C大大降低了计算量: 只计算类内的分布C若Ak 为分类属性, P(xk|Ci) 是D中属性Ak的值为 xk类属Ci 类的元组数除以D中Ci类的元组数|Ci, D| C若Ak 为连续值, P(xk|Ci) 通常假定服从均值为 和
28、标准差为 的高斯分布而Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 45分类实例：训练样本Class:C1:buys_computer = yesC2:buys_computer = noData sample X = (age =30,Income = medium,Student = yesCredit_rating = Fair)Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 46朴素贝页斯分类过程C计算先验概率P(Ci): P(buys_computer = “yes”) = 9/14 = 0.643 P
29、(buys_computer = “no”) = 5/14= 0.357C计算条件概率Compute P(X|Ci) for each class P(age = “=30” | buys_computer = “yes”) = 2/9 = 0.222 P(age = “= 30” | buys_computer = “no”) = 3/5 = 0.6 P(income = “medium” | buys_computer = “yes”) = 4/9 = 0.444 P(income = “medium” | buys_computer = “no”) = 2/5 = 0.4 P(stude
30、nt = “yes” | buys_computer = “yes) = 6/9 = 0.667 P(student = “yes” | buys_computer = “no”) = 1/5 = 0.2 P(credit_rating = “fair” | buys_computer = “yes”) = 6/9 = 0.667 P(credit_rating = “fair” | buys_computer = “no”) = 2/5 = 0.4C计算后验概率计算后验概率 X = (age = 30 , income = medium, student = yes, credit_rati
31、ng = fair) P(X|Ci) : P(X|buys_computer = “yes”) = 0.222 x 0.444 x 0.667 x 0.667 = 0.044 P(X|buys_computer = “no”) = 0.6 x 0.4 x 0.2 x 0.4 = 0.019P(X|Ci)*P(Ci) : P(X|buys_computer = “yes”) * P(buys_computer = “yes”) = 0.028 P(X|buys_computer = “no”) * P(buys_computer = “no”) = 0.007Therefore, X belon
32、gs to class (“buys_computer = yes”)Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 47零概率问题C朴素贝页斯预测需要每个条件概率非零， 否则整个预测概率为零 C假设数据有1000个数据集, income=low (0), income= medium (990), and income = high (10), CLaplacian 校准 (or Laplacian估计器)E每个计数都加上1Prob(income = low) = 1/1003Prob(income = medium) = 991/1003Prob(i
33、ncome = high) = 11/1003E “校准” 概率估计非常接近 “未校准”概率估计Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 48朴素贝页斯分类器的评价C优点 E容易实现 E大多数情况下结果令人满意C缺点E满足假设: 类条件独立，对实际分布的描述不准确E实际上，不同的属性间是相关联的 HE.g., 医院: 病人: 档案: 年龄, 家族史, etc. 症状: 发烧, 咳嗽等., 疾病: 肺癌, 糖尿病, etc. H这些属性间的关联无法由朴素贝页斯分类器建模C如何处理这种相关性?EBayesian Belief Networks Data
34、 Mining Yihua Tan IPRAI-HUST 2024/9/3 p 49Bayesian Belief NetworksC贝页斯证据网络允许 属性变量的子集条件独立 C因果关系的图模型E表达变量间的依赖性 E给出了联合概率的完全表示YZPXq 节点: 随机变量q 连接箭头: 依赖性q X 和 Y 为 Z的父节点, 而 Y 为 P的父节点qZ 和P间无依赖性q 是一个无环图Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 50简单的贝页斯证据网络实例FamilyHistoryLungCancerPositiveXRaySmokerEmphysem
35、aDyspneaLCLC(FH, S)(FH, S) (FH, S) (FH, S)0.80.20.50.50.70.30.10.9Bayesian Belief Networks变量 LungCancer 的条件概率表 (CPT) CPT 表示每个父节点不同组合的条件概率数据元组数据元组X由属性由属性Y1,Yn描述描述的联合概率表示为Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 51BPN的训练C几种情况:E给定网络结构和所有的观测变量 : 学习 CPTsE网络结构已知, 存在一些隐变量: 梯度下降法, 和神经网络的学习类似E网络结构未知, 所有观测
36、变量已知: 通过模型空间搜索构造网络拓扑E结构未知, 所有都是隐变量: 没有办法学习？！Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p52内内 容容C分类和预测的基本概念C关于分类和预测的问题C分类的方法C决策树分类器CBayesian分类器C基于规则的分类C后向传播分类器CSVM分类器C惰性学习法分类C其它分类方法C预测的方法C分类和预测方法的评估Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 53基于规则的分类器C使用一系列“ifthen” 对数据集分类C规则: (Condition) yE此处 H Condi
37、tion 为多个属性值 H y 为类标号ELHS(IF 部分): 规则前件或前提ERHS(then 部分): 规则结论E分类规则例子:H (血的类型=温血) (下蛋=Yes) 鸟H (税收收入 Bird规则 R3 覆盖 grizzly bear = MammalData Mining Yihua Tan IPRAI-HUST 2024/9/3 p 55规则的评价ncovers = 规则R覆盖的样本数ncorrect = 规则 R正确分类的样本数 D: 数据样本集C规则覆盖率:Coverage(R)= ncovers /|D|C规则准确率:Accuracy(R) = ncorrect / nco
38、vers(Status=Single) No Coverage = 40%, Accuracy = 50%Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 56规则的冲突C触发：规则被满足C激活：该规则为唯一满足的R1: (Give Birth = no) (Can Fly = yes) BirdsR2: (Give Birth = no) (Live in Water = yes) FishesR3: (Give Birth = yes) (Blood Type = warm) MammalsR4: (Give Birth = no) (Can Fly
39、= no) ReptilesR5: (Live in Water = sometimes) Amphibians A lemur triggers rule R3, so it is classified as a mammalA turtle triggers both R4 and R5A dogfish shark triggers none of the rulesData Mining Yihua Tan IPRAI-HUST 2024/9/3 p 57冲突解决C规模序(size ording): 要求最严格的规则赋予最高优先级 (i.e., 最多属性测试)C基于类的序: 按照类的频
40、繁性或错分代价的降序排列C基于规则的序 (决策表决策表): 根据规则的质量度量或专家意见，规则组织为长的优先级列表Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 58从决策树提取规则C规则易于理解C从根到树的叶节点的每条路径创建一个规则C沿每个划分准则的逻辑AND形成规则的前提，存放类预测的叶节点形成规则后件C规则间是互斥或穷举的 Example: 从 buys_computer 决策树提取的规则IF age = young AND student = no THEN buys_computer = noIF age = young AND studen
41、t = yes THEN buys_computer = yesIF age = mid-age THEN buys_computer = yesIF age = old AND credit_rating = excellent THEN buys_computer = yesIF age = young AND credit_rating = fair THEN buys_computer = noage?student?credit rating?40noyesyesyes31.40nofairexcellentyesnoData Mining Yihua Tan IPRAI-HUST
42、2024/9/3 p 59规则归纳：序贯覆盖算法CSequential covering : 直接从数据抽取规则C典型的序贯覆盖算法: FOIL, AQ, CN2, RIPPERC序贯地学习规则, 对每个给定的类 Ci 希望覆盖该类的许多元组，但不包括其它类的元组(或很少) C步骤: E一次学习一个规则E每次学习规则时, 删除规则覆盖到的元组E对剩余的元组重复此过程，直到满足中止条件.如无训练样本或规则质量低于用户指定的门限C决策树归纳: 同时学习一组规则Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 60顺序覆盖算法 while (还有足够的元组)E产
43、生一条规则E删除满足规则的元组规则3覆盖的样本规则覆盖的样本2规则1覆盖的样本Positive examplesData Mining Yihua Tan IPRAI-HUST 2024/9/3 p 61Learn One Rule算法C从空规则开始: 条件= 空C深度优先贪婪算法增加新的变量E选择提高规则质量最多的变量C规则质量度量: E覆盖率和准确率EFoil信息增益 (in FOIL & RIPPER): 扩展前提来估计 info_gain H适合于有较高准确率，并且覆盖很多正元组的规则C基于独立测试集的规则剪枝HPos/neg 为规则R覆盖的正/负元组数H若规则R剪枝后的 FOIL_P
44、rune更高, 则对 R剪枝Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 62产生规则Positive examplesNegative examplesA3=1A3=1&A1=2A3=1&A1=2&A8=5C产生规则Ewhile(true)E搜索最优预测 pE若若 FOIL_Gain(p) threshold 则 将 p 加入当前规则E否则否则 breakData Mining Yihua Tan IPRAI-HUST 2024/9/3 p63内内 容容C分类和预测的基本概念C关于分类和预测的问题C分类的方法C决策树分类器CBayesian分类器C基
45、于规则的分类C后向传播分类器CSVM分类器C惰性学习法分类C其它分类方法C预测的方法C分类和预测方法的评估Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 64Back PropagationC一种神经网络学习算法：对多层前馈神经网络的学习C人工神经网络E心理学家和神经学家开创，用于测试神经元的计算模拟E神经网络：一组连接的输入/输出单元，每个连接和一个权系数关联E学习阶段：调整权系数，使其正确预测输入元组的类标号E又称为连接者学习Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 65Neuro (Perceptron
46、)C由多个互连的节点和权系数连接C输出节点为输入节点的加权和C根据输入的门限，定义相应的函数fC最后，n维输入矢量X映射为变量yPerceptron ModelorData Mining Yihua Tan IPRAI-HUST 2024/9/3 p 66多层前馈神经网络将类预测作为输入的非线性组合将类预测作为输入的非线性组合给定足够多的隐藏单元和训练样给定足够多的隐藏单元和训练样本，多层神经网络可逼近任意函数本，多层神经网络可逼近任意函数若权系数不返回到前一层，则称若权系数不返回到前一层，则称前馈神经网络前馈神经网络Data Mining Yihua Tan IPRAI-HUST 2024/
47、9/3 p 67定义神经网络拓扑C设计网络拓扑: 输入层单元数, 隐藏层单元数 (若多于 1层), 每个隐藏层的单元数, 输出层的单元数C将训练元组中每个属性的观测值进行归一化，如：使其落入 0.01.0C每个域值一个输入单元, 初始化为 0C输出输出, 若分类时有两类以上, 每类一个输出单元C若神经网络经训练后发现准确度不高, 以不同的神经网络拓扑或不同的初始权系数集训练Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 68后向传播算法学习C迭代地处理训练元组数据集，比较器网络预测值和已知的目标值(类标号或连续预测值)C对每个训练元组, 权系数对网络预测
48、值和实际目标值之间的MSE最小C后向进行修正 : 从输出层, 经每个隐藏层,最后到首层C 步骤E初始化权系数 (赋以很小的随机数) ，每个单元一个偏差度E前向传播输入 (应用激励函数) E后向传播误差 (通过更新权系数和偏差度)E中止条件 (当误差很小时, etc.)Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 69后向传播和可解释性C后向传播的效率: 给定|D|个元组和w个权系数，每个周期 (对训练集的一次迭代) 需要化的时间为O(|D| * w), 在最坏的情况下，周期数为可能是输入数n的指数C 从网络抽取规则: 网络剪枝E删除对训练后的网络影响最
49、小的加权连接以简化网络结构E对连接 、单元或活跃值聚类E对输入值和活跃值进行学习，导出描述输入和隐藏单元层的关系C灵敏度分析: 评估给定的输入变量对网络输出的影响。. 这种形式的分析得到的知识可用“IF x 减少5% THEN Y增加8%”的规则表达Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p70内内 容容C分类和预测的基本概念C关于分类和预测的问题C分类的方法C决策树分类器CBayesian分类器C基于规则的分类C后向传播分类器CSVM分类器C惰性学习法分类C其它分类方法C预测的方法C分类和预测方法的评估Data Mining Yihua Tan I
50、PRAI-HUST 2024/9/3 p 71一个简单的例子C哪个分类更优? B1 or B2?C怎样定义更优?Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 72SVM的简介C适用于线性和非线性可分数据的新分类方法C通过非线性映射，将原始训练数据变换到更高维空间C在新的维度下, 搜索线性可分的超平面 (i.e., “决策边界”)C通过合适的高维映射, 来自两类的数据总可被超平面分开 CSVM 以支持向量搜索超平面 (“基本” 训练元组) 和边缘 (由支持向量定义)Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 7
51、3SVM的基本思想支持向量小边缘大边缘Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 74边缘和支持向量Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 75SVM-线性可分情况m令 D 为数据集 (X1, y1), , (X|D|, y|D|), 此处Xi 为 和类标号 yi相关联的训练元组存在无数条线 (超平面) 分开两类，但我们期望找出最佳的分类 (对未见数据具有最小的分类误差)SVM 搜索最大的边缘, i.e., maximum marginal hyperplane (MMH)Data Mining Yih
52、ua Tan IPRAI-HUST 2024/9/3 p 76SVM-线性可分Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 77SVM-线性可分C目标是最大化:E等价于最小化:E满足以下约束:C 约束的二次优化问题E数值方法求解 (e.g., 二次规划)C训练后的决策边界Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 78SVM-问题线性不可分C问题是线性不可分，怎么办？E引入松弛变量H 最小化:H 约束条件下: Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 79SVM-
53、决策面分线性C将原始输入数据变换到高维的空间E例6-10C在新的空间搜索线性可分平面Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 80SVM-核函数映射C利用核函数K(Xi, Xj)对原始数据映射，如K(Xi, Xj) = (Xi) (Xj) C典型的核函数CSVM 可用于多类分类 ( 2两类) 和回归分析 (使用附加的用户参数)Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 81SVM相关链接CSVM WebsiteEhttp:/www.kernel-machines.org/C实现的代码ELIBSVM: SV
54、M的高效实现, 多类分类, 两类分类等ESVM-light: 简单但性能劣于 LIBSVM, 只支持两类分类， c语言ESVM-torch: 用 C语言实现.Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 82Lazy VS. Eager LearningCLazy vs. eager learningELazy learning (e.g., 基于实例的学习): 简单地存储样本 (或小的预处理) ，一直等到给定测试元组EEager learning (前面提到的方法): 给定训练集, 在检验元组到来之前，构造泛化的分类模型CLazy: 训练时间少，但在
55、预测时需花费更多时间C准确率ELazy learning : 更有效地利用假设空间，因为使用很多的局部函数隐式地逼近全局函数EEager: 必须归结于单个假设，覆盖整个实例空间Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 83K-最近邻法C基本思想：类比学习E走路像鸭子，叫声像鸭子，则该动物是鸭子训练集训练集测试集测试集计算距离计算距离选择选择k k个最近的记录个最近的记录 Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 84K-最近邻法算法C所有的实例对应 n-维空间C根据欧式距离定义邻近性, dist(X1,
56、 X2)C目标函数可为离散或实值函数C对离散值, k-NN 返回未知元组xq k个最近邻训练集中的最普遍的值 CVoronoi 图: 对训练样本的典型集，1-NN的决策面Voronoi DiagramData Mining Yihua Tan IPRAI-HUST 2024/9/3 p 85关于k-NN算法Ck-NN 是对给定的未知元组，预测其实值E返回 k 最近邻的均值C权距离最近邻算法E根据k近邻对未知元组xq的距离贡献，计算预测值 H距离近，则权系数大，w = 1/d2Ck近邻平均后，对噪声鲁棒C维数灾难: 相邻的距离可能由不相关的属性主导 E通过轴拉伸删除最不相关的属性Data Min
57、ing Yihua Tan IPRAI-HUST 2024/9/3 p 86K-NN例ClassMarital StatusSingleMarriedDivorcedYes201No241名词属性的距离:d(Single,Married) = | 2/4 0/4 | + | 2/4 4/4 | = 1d(Single,Divorced) = | 2/4 1/2 | + | 2/4 1/2 | = 0d(Married,Divorced) = | 0/4 1/2 | + | 4/4 1/2 | = 1d(Refund=Yes,Refund=No)= | 0/3 3/7 | + | 3/3 4/7
58、 | = 6/7ClassRefundYesNoYes03No34Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 87K-NN例续元组 X 和 Y的距离: 其中: 若X 大多数情况下预测准确，wX 1 若X 预测不可靠，则wX 1 Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 88Case-based reasoning 储存案例储存案例 使用训练数据预测未见数据的类使用训练数据预测未见数据的类 标号标号 Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p89内内 容容C分类和
59、预测的基本概念C关于分类和预测的问题C分类的方法C决策树分类器CBayesian分类器C基于规则的分类C后向传播分类器CSVM分类器C惰性学习法分类C其它分类方法C预测的方法C分类和预测方法的评估Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 90Case-based reasoningCCBR: 使用问题解数据库解决新问题C储存 符号描述 (元组 or案例)而不是欧式空间中的点C应用: 客户-服务 (产品故障诊断), 法律裁决C方法E案例表达为符号描述 (e.g., 函数图)E搜索相似空间, 多个搜索到的案例可综合E案例搜索, 基于知识的推理和问题求解
60、的紧耦合C挑战E寻找最优相似度 E基于句法相似度的索引，当搜索失效时，回溯或自适应地附加案例Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p91内内 容容C分类和预测的基本概念C关于分类和预测的问题C分类的方法C决策树分类器CBayesian分类器C基于规则的分类C后向传播分类器CSVM分类器C惰性学习法分类C其它分类方法C预测的方法C分类和预测方法的评估Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 92Genetic algorithmC遗传算法: 模拟生物进化C创建由初始规则组成的初始种群E每个规则由一个二进位
61、串表示EE.g., if A1 and NOT A2 then C2 可编码为 100 E若属性有k个值( k 2 ), 则可用k比特对该属性编码 C基于“适者生存”的原则, 形成由当前种群中最适合的规则及其后代组成新的种群C规则的适应度由其对训练样本的分类精度表示 C后代通过交叉和变异产生C该过程继续，直到种群进化到每个规则均满足预先指定的适应度C速度较慢，但易于并行Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 93Rough Set ApproachC用于“近似的”或“粗糙的”定义等价类C给定类 C的粗糙集由两个集合逼近: a lower appr
62、oximation (一定属于 C) 和 an upper approximation (不可能认为不属于C) C寻找属性的最小子集(特征简化）是NP难题，但识别矩阵(discernibility matrix )存放每对数据元组的属性值之间的差别，降低计算强度Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 94模糊集方法C模糊逻辑使用 0.0 和 1.0 间的真值表示成员的隶属度 (如 模糊隶属度图)C属性值转换为模糊值Ee.g., 通过计算模糊值，将收入映射到离散类别 low, medium, highC给定新的样本, 可给出多个模糊值C每个可适用的
63、规则为类成员贡献一票C典型地, 对每个预测类的真值求和 ，并组合这些和Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p95内内 容容C分类和预测的基本概念C关于分类和预测的问题C分类的方法C决策树分类器CBayesian分类器C基于规则的分类C后向传播分类器CSVM分类器C惰性学习法分类C其它分类方法C预测的方法C分类和预测方法的评估Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 96什么是预测C(数值) 预测和分类类似E构建模型E针对给定的输入，使用模型预测连续或顺序值C预测和分类的不同点E分类指预测分类标号 E预
64、测模型使用连续函数C预测的主要方法: regressionE对一个或多个独立变量（或预测变量）和一个因变量(或响应变量）之间的关系建模C回归分析E线性回归和多元线性回归E非线性回归E其它的回归方法: 广义线性模型, Poisson 回归, 对数线性模型, 回归树Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 97Linear RegressionC线性回归: 单个因变量 y 和单个预测变量 xy = w0 + w1 xw0 (y斜距) 和 w1 (斜率) 为回归系数 C最小二乘方法: 估计最佳拟合直线C多元线性回归: 包含多个预测变量E训练数据形如 (X
65、1, y1), (X2, y2), (X|D|, y|D|) EEx. 对2D数据, 可形如: y = w0 + w1 x1+ w2 x2E扩展最小二乘法求解，或使用 SAS, S-Plus等软件系统求解Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 98Nonlinear RegressionC一些非线性模型可用多项式建模 C多项式回归模型可变成线性模型y = w0 + w1 x + w2 x2 + w3 x3可转换成新的模型，通过: x2 = x2, x3= x3y = w0 + w1 x + w2 x2 + w3 x3 C其它函数, 如幂函数, 也
66、可变成线性模型C有的模型是难以处理的非线性 (e.g., 指数项和的形式)E可通过更复杂的公式进行综合计算，得到最小二乘估计Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 99其它的回归方法C广义线性模型: E提供了用于分类因变量建模的理论基础E因变量 y的方差是 y均值的函数, 而非常数ELogistic 回归: 某个事件的发生概率为预测变量集的线性函数E Poisson 回归: 对数据建模为Poisson分布C对数线性模型: (对分类数据)E逼近离散的多维概率分布 E对数据平滑和压缩有用C回归树和模型树E用于预测连续值而非类标号Data Mining
67、 Yihua Tan IPRAI-HUST 2024/9/3 p 100回归树和模型树C回归树: 作为 CART 学习系统的一部分 (Breiman et al. 1984)ECART: Classification And Regression TreesE树叶存放连续值预测E到达该树叶的训练元组的预测属性的平均值C模型树: Quinlan 提出(1992)E每个树叶存放一个回归模型预测属性的多元线性方程E比回归树更普遍C简单的线性模型不能很好地表达数据时，回归和模型树比线性模型更准确 Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p101内内 容容C分
68、类和预测的基本概念C关于分类和预测的问题C分类的方法C决策树分类器CBayesian分类器C基于规则的分类C后向传播分类器CSVM分类器C惰性学习法分类C其它分类方法C预测的方法C分类和预测方法的评估Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 102分类器的准确率C分类器 M的准确率, acc(M): 模型 M对测试元组分类正确的百分比EM的误差率 (误分率) = 1 acc(M)E给定 m 类,混淆矩阵的元素CMi,j, 表示分类器将类 i 误分为类 j的个数C其它的准确率度量 (e.g.,对癌症诊断)sensitivity = t-pos/pos
69、 /* 阳性识别的准确率 */specificity = t-neg/neg /* 阴性识别的准确率 */precision = t-pos/(t-pos + f-pos)accuracy = sensitivity * pos/(pos + neg) + specificity * neg/(pos + neg) E该模型可用于成本收益分析Real classPredicted classbuy_computer = yesbuy_computer = nototalrecognition(%)buy_computer = yes695446700099.34buy_computer = n
70、o4122588300086.27total736626341000095.52Real classPredicted classC1C1C1True positiveFalse negativeC1False positiveTrue negativeData Mining Yihua Tan IPRAI-HUST 2024/9/3 p 103预测误差C预测器的准确度: 预测值偏离真实值的程度CLoss function: 度量 yi 和预测值 yi之间的误差E绝对误差: | yi yi| E平方误差: (yi yi)2 C测试误差 (泛化误差): 测试集上的平均误差E平均绝对误差: 均方误
71、差:E相对绝对误差: 相对平方误差:E均方误差放大了野值点的存在 E常用相对平方根误差 或均方根误差Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 104评估方法CHoldout methodE数据被随机划分为两个独立集合H用于模型构造的训练集 (e.g., 2/3) H估计准确率的测试集 (e.g., 1/3)E随机抽样: 保持法的变形H重复保持法 k次, accuracy = 多次准确率的均值CCross-validation (k-fold, k = 10最常用)E将数据划分为 k 个互不相交的子集, 每个子集大小相等E第 i-次迭代, 使用 Di
72、 作测试集，其它作训练集ELeave-one-out: 对小数据集，k 为样本数，即每次的测试集只有一个样本EStratified cross-validation:fold被分层，使得每个fold中元组的类分布与在初始数据中的大致相同Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 105评估方法BootstrapCBootstrapE适用于小数据集E从给定数据集中有放回的均匀采样Hi.e., 每次元组选取后, 该元组仍可等概率的抽样并添加至训练集C最常用的 .632 boostrapE非定 d 个元组. 有放回的采样 d 次, 形成d个训练集. 未4进
73、入训练集的元组构成测试集. 大约 63.2% 的原始数据将出现在训练集中，剩下的 36.8% 将形成测试集 ( (1 1/d)d e-1 = 0.368)E重复k次采样过程, 模型的总体准确率为:Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 106提高准确率的方法集成学习CEnsemble LearningE使用混合模型提高准确率E从学习到的k个分类器M1, M2, , Mk，混合成准确率改进的分类器M*C常用方法EBagging: 对分类器预测结果平均EBoosting: 加权平均预测结果C例： 设有25个基本分类器，彼此独立，分类错误率 = 0.3
74、5，则集成分类器的错分率为Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 107Bagging: Boostrap AggregationC例: 基于多个医生投票的诊断C训练E给定有 d 个元组的训练样本D, 在每个迭代 i, d个原则的训练样本 Di 采用有放回的抽样 (i.e., boostrap)E对每个训练样本集Di学习其模型 Mi C分类: 对未知样本 X 分类E每个分类器 Mi 返回类预测E装袋分类器 M* 对分类结果计数，并将类标号赋为票数最多的标号C预测: 使用平均方法，计算预测的连续值C准确率E通常优于直接从 D得到的分类器E对噪声数据
75、: 不会更差, 而是更鲁棒 E理论上证明，可改进预测的准确率Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 108BoostingC例: 咨询多个医生, 基于带权的诊断综合基于之前的诊断准确性，赋予权系数C工作过程?E每个训练元组赋以权重E迭代地学习k个分类器E学习得到 Mi 后, 更新权重, 使得其后的分类器Mi+1, 更关注Mi误分类 的元组E最终 M* 组合这k个分类器, 每个分类器投票的权重是其准确率的函数CBoosting算法可扩展用于预测连续值C和 bagging比较: 获得更高的准确率, 对错分数据过拟合模型Data Mining Yihu
76、a Tan IPRAI-HUST 2024/9/3 p 109Adaboost (Freund and Schapire, 1997)C给定 d 个带类标号的训练样本, (X1, y1), , (Xd, yd)C初始，每个样本的权系数均为 (1/d)CK次迭代产生k个分类器. 每次迭代 i,E同样大小的训练集 Di 从样本集D 采样（有放回采样）E每个样本被选到的机会和其权重成正比E从 Di得到分类器 MiE以 Di 作测试集计算其误差E若样本被错分, 其权系数增加, 否则减小 C误差率: err(Xj) 为样本 Xj的错分率的错分率. 分类器 Mi 的误差率为 其错分样本的权系数和: C分类
77、器 Mi投票的权系数为C分类Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 110Adaboost的解释Data points for trainingInitial weights for each data pointData Mining Yihua Tan IPRAI-HUST 2024/9/3 p 111Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 112模型选择CROC (Receiver Operating Characteristics) 曲线: 分类模型的可视化比较工具C来自信号检测理论C表示在
78、检出率和虚检率之间的平衡CROC 曲线之下的区域表示模型的准确率 C对测试样本按降序排列: 最可能属于正确分类的样本置于列表顶部C越靠近斜线 (i.e., 如靠近 0.5), 模型的准确率越低C纵轴表示检出率 C横轴表示虚检率C图中显示出斜线C模型完全准确则其区域面积为 1.0Data Mining Yihua Tan IPRAI-HUST 2024/9/3 p 113总结C分类和预测用于抽取描述重要数据类或预测未来数据趋势的模型 C多种有效和可伸缩的方法： 决策树, 朴素贝页斯分类, 贝页斯证据网络, 基于规则的分类, 后向传播, 支持向量机 (SVM), 基于模式的分类, 最近邻分类器, 和基于案例的推理, 以及其它的方法 遗传算法, 粗糙集和模糊集 C用于预测的有线性、非线性和广义线性回归模型。通过变换预测变量，许多非线性问题可转化为线性问题。C分层的 k-fold 交叉验证推荐为准确率估计的方法. 通过学习和混合多个独立的分类器，Bagging 和 boosting 可提高整体的准确率 C模型选择时，ROC曲线非常重要C没有一个方法在所有数据集上都优于其它方法C在设计算法时，必须考虑准确率、训练时间、鲁棒性、可解释性和可伸缩性等。算法是这些因素的折衷
