第5章 分类 其他技术.ppt

1、数据挖掘导论,Pang-ning Tan, Michael Stieinbach, and Vipin Kumar著 Pearson Education LTD. 范明 等译 人民邮电出版社,第5章 分类: 其他技术,基于规则的分类 最近邻分类 贝叶斯分类 神经网络 支持向量机 组合方法 不平衡类问题 多类问题,5.1 基于规则的分类器,2020年7月22日星期三,数据挖掘导论,4,基于规则的分类器,使用一组 “ifthen” 规则进行分类 规则: (Condition) y 其中 Condition 是属性测试的合取 y 是类标号 左部: 规则的前件或前提 右部: 规则的结论 分类规则的例子

2、: (Blood Type=Warm) (Lay Eggs=Yes) Birds (Taxable Income 50K) (Refund=Yes) Evade =No,2020年7月22日星期三,数据挖掘导论,5,基于规则的分类器: 例,脊椎动物数据集,2020年7月22日星期三,数据挖掘导论,6,基于规则的分类器的使用,规则 r 覆盖 实例 x，如果该实例的属性满足规则r的条件 r1：（胎生 = 否）（飞行动物 = 是） 鸟类 r2：（胎生 = 否）（水生动物 = 是） 鱼类 r3：（胎生 = 是）（体温 = 恒温） 哺乳类 r4：（胎生 = 否）（飞行动物 = 否） 爬行类 r5：（水生

3、动物 = 半） 两栖类 规则r1覆盖“鹰” = 鸟类 规则r3 覆盖“灰熊” = 哺乳类,2020年7月22日星期三,数据挖掘导论,7,规则的质量,用覆盖率和准确率度量 规则的覆盖率（coverage） : 满足规则前件的记录所占的比例 规则的准确率（accuracy） : 在满足规则前件的记录中，满足规则后件的记录所占的比例 规则: (Status=Single) No Coverage = 40%, Accuracy = 50%,Tid,Refund,Marital,Status,Taxable,Income,Class,1,Yes,Single,125K,No,2,No,Married,

4、100K,No,3,No,Single,8,No,Single,85K,Yes,9,No,Married,75K,No,10,No,Singl,e,90K,Yes,10,2020年7月22日星期三,数据挖掘导论,8,如何用规则分类,一组规则 r1：（胎生 = 否）（飞行动物 = 是） 鸟类 r2：（胎生 = 否）（水生动物 = 是） 鱼类 r3：（胎生 = 是）（体温 = 恒温） 哺乳类 r4：（胎生 = 否）（飞行动物 = 否） 爬行类 r5：（水生动物 = 半） 两栖类 待分类记录 狐猴触发规则 r3, 它分到哺乳类 海龟触发规则r4和 r5-冲突 狗鲨未触发任何规则,2020年7月22日

5、星期三,数据挖掘导论,9,规则的分类器的特征,互斥规则集 每个记录最多被一个规则覆盖 如果规则都是相互独立的，分类器包含互斥规则 如果规则集不是互斥的 一个记录可能被多个规则触发 如何处理? 有序规则集 基于规则的序 vs 基于类的序 无序规则集 使用投票策略,2020年7月22日星期三,数据挖掘导论,10,规则的分类器的特征(续),穷举规则集 每个记录至少被一个规则覆盖 如果规则集涵盖了属性值的所有可能组合，则规则集具有穷举覆盖 如果规则集不是穷举的 一个记录可能不被任何规则触发 如何处理? 使用缺省类,2020年7月22日星期三,数据挖掘导论,11,有序规则集,根据规则优先权将规则排序定秩

6、（rank） 有序规则集又成决策表（decision list） 对记录进行分类时 由被触发的，具有最高秩的规则确定记录的类标号 如果没有规则被触发，则指派到缺省类,2020年7月22日星期三,数据挖掘导论,12,规则定序方案,基于规则的序 根据规则的质量排序 基于类的序 属于同一类的规则放在一起 基于类信息（如类的分布、重要性）对每类规则排序,2020年7月22日星期三,数据挖掘导论,13,如何建立基于规则的分类器,直接方法: 直接由数据提取规则 例如: RIPPER, CN2, Holtes 1R 间接方法: 由其他分类模型提取规则 (例如，从决策树、神经网络等). 例如: C4.5rul

7、es,2020年7月22日星期三,数据挖掘导论,14,直接方法: 顺序覆盖,基本思想 依次对每个类建立一个或多个规则 对第i类建立规则 第i类记录为正例，其余为负例 建立一个第i类的规则r，尽可能地覆盖正例，而不覆盖负例 删除r覆盖的所有记录，在剩余数据集上学习下一个规则，直到所有第i类记录都被删除,2020年7月22日星期三,数据挖掘导论,15,直接方法: 顺序覆盖,顺序覆盖（sequential covering）算法 1：令E是训练记录，A是属性值对的集合(Aj, vj) 2：令Yo是类的有序集y1, y2,., yk 3：令R = 是初始规则列表 4：for 每个类 yYo yk do

8、 5： while 终止条件不满足 do 6： r Learn-One-Rule (E, A, y) 7： 从E中删除被r覆盖的训练记录 8： 追加r到规则列表尾部：RR r 9： end while 10：end for 11：把默认规则yk插入到规则列表R尾部,2020年7月22日星期三,数据挖掘导论,16,顺序覆盖: 例,(a) Original data,(b) Step 1,(c) Step 2,(c) Step 3,2020年7月22日星期三,数据挖掘导论,17,删除实例,为什么要删除实例? 否则, 下一个规则将与前面的规则相同 为什么删除正实例? 确保下一个规则不同 为什么删除负

9、实例? 防止低估规则的准确率 比较图中的规则 R2 和 R3,2020年7月22日星期三,数据挖掘导论,18,Learn-One-Rule,规则增长 实例删除 规则评估 停止准则 规则剪枝,2020年7月22日星期三,数据挖掘导论,19,规则增长,两种策略 一般到特殊 从初始规则r: y开始 反复加入合取项，得到更特殊的规则，直到不能再加入 特殊到一般 随机地选择一个正例作为初始规则 反复删除合取项，得到更一般的规则，直到不能再删除 问题 加入/删除合取项有多种选择，如何选择？ 何时停止加入/删除合取项？ 需要评估标准,2020年7月22日星期三,数据挖掘导论,20,规则增长: 例,一般到特殊

10、,特殊到一般,2020年7月22日星期三,数据挖掘导论,21,规则评估,常用的度量 准确率 似然比 Laplace M-estimate FOIL信息增益,2020年7月22日星期三,数据挖掘导论,22,规则评估(续),准确率 Accuracy n : 被规则覆盖的实例数 nc : 被规则正确分类的实例数 问题：准确率高的规则可能覆盖率太低 似然比 （越高越好） k是类的个数 fi是被规则覆盖的类i的样本的观测频度 ei是规则作随机猜测的期望频度,2020年7月22日星期三,数据挖掘导论,23,规则评估:例,例: 60个正例和100个反例 规则r1：覆盖50个正例和5个反例（acc = 90.

11、9%） 规则r2：覆盖2个正例和0个反例 （acc = 100%） 使用准确率, r2好 使用似然比 r1 : 正类的期望频度为e+ = 5560/160 = 20.625 负类的期望频度为e = 55100/160 = 34.375 r2: 正类的期望频度为e+ = 260/160 = 0.75 负类的期望频度为e = 2100/160 = 1.25 R (r1) = 2 50log2(50/20.625)+5log2(5/34.375) = 99.9 R (r2) = 2 2log2(2/0.75)+0log2(0/1.25) = 5.66 r1比r2好,2020年7月22日星期三,数据挖

12、掘导论,24,规则评估(续),考虑规则覆盖率的评估度量 n是规则覆盖的样例数，f+是规则覆盖的正例数，k是类的总数，p+是正类的先验概率 当规则的覆盖率很高时，两个度量都渐近地趋向于规则的准确率f+/n 继续前例 r1的Laplace度量为51/57 = 89.47%，很接近它的准确率 r2的Laplace度量（75%）比它的准确率小很多,2020年7月22日星期三,数据挖掘导论,25,规则评估(续),考虑规则的支持度计数的评估度量 规则的支持度计数对应于它所覆盖的正例数 FOIL信息增益（First Order Inductive Leaner information gain） 设规则r

13、: A+覆盖p0个正例和n0个反例; 规则r: A B+覆盖p1个正例和n1个反例.扩展后规则的FOIL信息增益定义为 该度量与p1和p1/(p1 +n1)成正比，所以它更倾向于选择那些高支持度计数和高准确率的规则 继续前例 r1和r2的FOIL信息增益分别为43.12和2，因此规则r1比r2好,2020年7月22日星期三,数据挖掘导论,26,停止条件与规则剪枝,停止条件 计算增益 如果增益不显著, 则丢弃新规则 规则剪枝 类似于决策树后剪枝 降低错误剪枝 : 删除规则中的合取项 比较剪枝前后的错误率 如果降低了错误率, 则剪掉该合取项,2020年7月22日星期三,数据挖掘导论,27,直接方法

14、: RIPPER,对于2类问题, 选定一个类为正类，另一个为负类 从正类学习规则 负类时缺省类 多类问题 按类的大小（属于特定类的实例所占的比例）对诸类排序 从最小的类开始学习规则，其余类都看做负类 对次小类学习规则，如此下去,2020年7月22日星期三,数据挖掘导论,28,直接方法: RIPPER(续),规则增长: 由空规则开始 只要能够提高FOIL信息增益就增加一个合取项 当规则不再覆盖负实例时就停止 剪枝 剪枝度量: v = (pn)/(p+n) p: 验证集中被规则覆盖的正实例数 n: 验证集中被规则覆盖的负实例数 剪枝方法: 如果剪掉合取项可以提高v就剪,2020年7月22日星期三,

15、数据挖掘导论,29,直接方法: RIPPER(续),建立规则集: 使用顺序覆盖算 找出覆盖当前正实例的最佳规则 删除被规则覆盖的所有正实例和负实例 当一个规则加入规则集时，计算新的描述长度 当新的描述长度比已经得到的描述长度多d位时，就停止增加新规则,2020年7月22日星期三,数据挖掘导论,30,直接方法: RIPPER(续),优化规则集 : 对规则集R中的每个规则 r 考虑2个替换的规则 : 替换规则 (r*): 重新增长新规则 编辑的规则(r): 把一个新的合取项增加到规则 r 比较替换前后的规则集 选择最小化MDL的规则集 对剩下的正实例，重复规则产生和优化,2020年7月22日星期三

16、,数据挖掘导论,31,规则提取的间接方法,决策树从根结点到叶结点的每一条路径都可以表示为一个分类规则 路径中的测试条件构成规则前件的合取项，叶结点的类标号赋给规则后件,2020年7月22日星期三,数据挖掘导论,32,间接方法: C4.5rules(续),从未剪枝的决策树提取规则 规则产生 对每个规则 r: A y, 考虑替换规则 r: A y 其中 A 由删除A的一个合取项得到 比较r与所有r的悲观误差 如果r的悲观误差小，则剪枝 重复该过程，直到不能改进,2020年7月22日星期三,数据挖掘导论,33,间接方法: C4.5rules,规则定序 不是对规则定序，而是对规则的子集定序 (clas

17、s ordering) 每个规则子集是一组具有相同规则后件(class)的规则 计算每个子集的描述长度 描述长度 = L(error) + g L(model) g 是参数，考虑规则集中冗余属性 (缺省值g = 0.5),2020年7月22日星期三,数据挖掘导论,34,C4.5 vs C4.5rules vs RIPPER,2020年7月22日星期三,数据挖掘导论,35,基于规则的分类器的特征,表达能力与决策树一样高 容易解释 容易产生 能够快速对新实例分类 性能可与决策树相媲美,5.2 最近邻分类器,2020年7月22日星期三,数据挖掘导论,37,急切学习 vs 惰性学习,急切学习（Eage

18、r Learner） 两步过程: (1) 归纳 (2) 演绎 惰性学习（lazy learner） 把训练数据建模过程推迟到需要对样本分类时 例子 Rote-learner（死记硬背） 记住所有的训练数据，仅当记录的属性值与一个训练记录完全匹配才对它分类 最近邻（Nearest neighbor） 使用“最近”的 k 个点 (最近邻) 进行分类,2020年7月22日星期三,数据挖掘导论,38,最近邻分类器,基本思想: If it walks like a duck, quacks like a duck, then its probably a duck,2020年7月22日星期三,数据挖掘导

19、论,39,最近邻分类器,要求 存放训练记录 计算记录间距离的度量 k值, 最近邻数 对未知记录分类: 计算域各训练记录的距离 找出 k 个最近邻 使用最近邻的类标号决定未知记录的类标号 (例如, 多数表决),2020年7月22日星期三,数据挖掘导论,40,最近邻定义,记录x的k-最近邻是与x之间距离最小的k个训练数据点,2020年7月22日星期三,数据挖掘导论,41,1 nearest-neighbor,Voronoi Diagram,2020年7月22日星期三,数据挖掘导论,42,k-最近邻分类算法,k-最近邻分类算法 1：令k是最近邻数目，D是训练样例的集合 2：for 每个测试样例 z

20、= (x, y) do 3： 计算z和每个样例(x, y) D之间的距离d(x, x) 4： 选择离z最近的k个训练样例的集合Dz D 5： 6：end for 距离加权表决,2020年7月22日星期三,数据挖掘导论,43,k-最近邻,k值的选择 : 如果 k 太小, 则对噪声点敏感 如果 k 太大, 邻域可能包含很 多其他类的点 定标问题（规范化） 属性可能需要规范化，防止距 离度量被具有很大值域的属性 所左右,2020年7月22日星期三,数据挖掘导论,44,k-NN的特点,k-NN的特点 是一种基于实例的学习 需要一个邻近性度量来确定实例间的相似性或距离 不需要建立模型，但分类一个测试样例

21、开销很大 需要计算域所有训练实例之间的距离 基于局部信息进行预测，对噪声非常敏感 最近邻分类器可以生成任意形状的决策边界 决策树和基于规则的分类器通常是直线决策边界 需要适当的邻近性度量和数据预处理 防止邻近性度量被某个属性左右,5.3 贝叶斯分类器,2020年7月22日星期三,数据挖掘导论,46,贝叶斯定理,每个记录用一个d维特征向量X = (x1, x2, , xd)表示 假定有k个类y1, y2, , yk. 给定X, X属于yj类的后验概率P(yj|X) 满足贝叶斯( Bayes)定理 MAP (maximum posteriori hypothesis, 最大后验假设) 将X指派到具

22、有最大后验概率P(yj|X)的类yj，即 将X指派到P(X|yj)P(yj) 最大的类yj,2020年7月22日星期三,数据挖掘导论,47,朴素贝叶斯分类,朴素贝叶斯分类 (Nave Bayes Classifier)工作原理 给定一个未知的数据样本X, 分类法将预测X属于具有最高后验概率的类. 即, 未知的样本分配给类yj, 当且仅当 根据贝叶斯定理, 我们有 由于P(X) 对于所有类为常数, 只需要最大化P(X|yj)P(yj)即可.,2020年7月22日星期三,数据挖掘导论,48,朴素贝叶斯分类(续),估计P(yj) 类yj的先验概率可以用下式估计 P(yj)=nj/n 其中, nj是类

23、yj中的训练样本数,而n是训练样本总数 估计P(X|yj) 为便于估计P(X|yj), 假定类条件独立-给定样本的类标号, 假定属性值条件地相互独立. 于是, P(X|Y=yj)可以用下式估计 其中, P(xi |yj)可以由训练样本估值,2020年7月22日星期三,数据挖掘导论,49,朴素贝叶斯分类(续),估计P(xi |yj) 设第i个属性Ai是分类属性, 则 P(xi|yj) = nij/nj 其中nij是在属性Ai上具有值xi的yj类的训练样本数, 而nj是yj类的训练样本数 设第i个属性Ai是连续值属性 把Ai离散化 假定Ai服从高斯分布 其中, ij,ij分别为给定yj类的训练样本

24、在属性Ai上的均值和标准差,2020年7月22日星期三,数据挖掘导论,50,朴素贝叶斯分类,朴素贝叶斯分类器所需要的信息 计算每个类的先验概率P(yj) P(yj)=nj/n 其中, nj是yi类的训练样本数,而n是训练样本总数 对于离散属性Ai，设的不同值为ai1, ai2, ,ail ， 对于每个类yj，计算后验概率P(aik|yj), 1 k l P(aik|yj)= nikj/nj 其中nikj 是在属性Ai上具有值aik 的yj类的训练样本数, 而nj是yj类的训练样本数 对于连续属性Ai 和每个类yj，计算yj类样本的均值ij,标准差ij,2020年7月22日星期三,数据挖掘导论,

25、51,贝叶斯分类器: 例,例:,P(Yes)=3/10 P(No)=7/10 P(有房=是|No) =3/7 P(有房=否|No) =4/7 P(有房=是|Yes) =0 P(有房=否|Yes) =1 P(婚姻状况=单身|No) =2/7 P(婚姻状况=离婚|No) =1/7 P(婚姻状况=已婚|No) =4/7 P(婚姻状况=单身|Yes) =2/3 P(婚姻状况=离婚|Yes) =1/3 P(婚姻状况=已婚|Yes) =0 年收入： 类=No：样本均值=110 样本方差=2975 类=Yes：样本均值=90 样本方差=25,2020年7月22日星期三,数据挖掘导论,52,贝叶斯分类器: 例

26、(续),X=（有房=否，婚姻状况=已婚，年收入=$120K） 计算P(X| No)和P(X| Yes) P(X| No) = P(有房=否|No) P(婚姻状况=已婚|No) P(年收入= $120K|No) = 4/74/70.0072=0.0024 P(X|Yes) = P(有房=否|Yes) P(婚姻状况=已婚|Yes) P(年收入=$120K|Yes) =101.2109 = 0 计算P(X| No)P(No)和P(X| Yes)P(Yes) P(X| No)P(No)=0.0024 0.7=0.00168 P(X| Yes)P(Yes)=0 0.3=0 因为P(X| No)P(No)

27、P(X| Yes)P(Yes), 所以X分类为No,2020年7月22日星期三,数据挖掘导论,53,贝叶斯分类器,问题 如果诸条件概率P(Xi=xi |Y=yj) 中的一个为0，则它们的乘积（计算P(X |Y=yj)的表达式）为0 很可能每个P(X |Y=yj)都为0 解决方法 使用Laplace 估计: 原估计: P(Xi=xi |Y=yj) = nij/nj,2020年7月22日星期三,数据挖掘导论,54,贝叶斯分类器的特点,对孤立的噪声点的鲁棒性 个别点对概率估计的影响很小 容易处理缺失值 在估计概率时忽略缺失值的训练实例 对不相关属性的鲁棒性 各类在不相关属性上具有类似分布 类条件独立

28、假设可能不成立 使用其他技术，如贝叶斯信念网络（ Bayesian Belief Networks，BBN）,2020年7月22日星期三,数据挖掘导论,55,贝叶斯信念网络,贝叶斯信念网络(Bayesian belief network)允许在变量的子集间定义类条件独立性 因果关系图模型 表示变量之间的依赖 给出联合概率分布的说明 图示 节点: 随机变量 边: 依赖 X,Y 是Z的父节点/前驱, 并且Y 是P的父节点/前驱 Z 和P之间没有依赖关系 图中没有环,2020年7月22日星期三,数据挖掘导论,56,贝叶斯信念网络 : 例,变量LungCance(LC)值的条件概率表(CPT), 给出

29、其双亲结点FamilyHistory和Smoke的每个可能值的组合的条件概率,2020年7月22日星期三,数据挖掘导论,57,贝叶斯信念网络 : 例(续),给出了LungCancer的CPT. 对于其双亲值的每个可能组合, 表中给出了LungCancer的每个值的条件概率. 例如, 由左上角和右下角, 我们分别看到 P(LungCancer = “yes” | FamilyHistory = “yes”, Smoker = “yes”) = 0.8 P(LungCancer = “no” | FamilyHistory = “no”, Smoker = “no”) = 0.9 对应于属性或变量

30、Z1,Zn的任意元组(z1,zn)的联合概率由下式计算 其中,P(zi | parents(zi)的值对应于Zi的CPT中的表目,2020年7月22日星期三,数据挖掘导论,58,训练贝叶斯信念网络,若干情况 给定网络结构和所有可观测变量 只需要学习CPT 网络结构已知,而某些变量是隐藏的 使用梯度下降法或类似于神经网络的方法训练信念网络 网络结构未知, 所有的变量可以观测 搜索模型空间, 构造网络拓扑结构 网络结构未知, 所有变量是隐藏的 没有已知的好算法 D. Heckerman, Bayesian networks for data mining,2020年7月22日星期三,数据挖掘导论,

31、59,训练贝叶斯信念网络,梯度下降法 设S是s个训练样本X1 ,X2 ,.,Xs的集合, wijk是具有双亲Ui = uik的变量Y = yij的CPT项 wijk可以看作权,类似于神经网络中隐藏单元的权. 权的集合记作w 这些权被初始化为随机概率值. 梯度下降策略采用贪心爬山法. 在每次迭代中, 修改这些权, 并最终收敛到一个局部最优解 基于w的每个可能设置都等可能的假定,该方法搜索能最好地对数据建模wijk值.目标是最大化,2020年7月22日星期三,数据挖掘导论,60,训练贝叶斯信念网络:梯度下降法,给定网络结构和wijk的初值,该算法按以下步骤处理 计算梯度：对每个i, j, k，计算

32、 沿梯度方向前进一小步:用下式更新权值 l是表示步长的学习率,设置为一个小常数 重新规格化权值：由于权值wijk是概率值,它们必须在0.0和1.0之间,并且对于所有的i,k，必须有,2020年7月22日星期三,数据挖掘导论,61,BBN的特点,BBN提供了一种用图形模型来捕获特定领域的先验知识的方法。网络还可以用来对变量间的因果依赖关系进行编码 构造网络可能既费时又费力。然而，一旦网络结构确定下来，添加新变量就十分容易 贝叶斯网络很适合处理不完整的数据。对有属性遗漏的实例可以通过对该属性的所有可能取值的概率求和或求积分来加以处理 因为数据和先验知识以概率的方式结合起来了，所以该方法对模型的过分

33、拟合问题是 非常鲁棒的,2020年7月22日星期三,数据挖掘导论,62,使用BBN进行推理举例,E: 锻炼, D: 饮食, HD: 心脏病, Hb: 胸口痛, BP: 血压, CP: 胸痛,2020年7月22日星期三,数据挖掘导论,63,情况一：没有先验信息,通过计算先验概率P(HD=Yes)和P(HD=No)来确定一个人是否可能患心脏病 设Yes, No表示锻炼的两个值，健康, 不健康表示饮食的两个值，由全概率公式 P(HD=Yes) = = = 0.250.70.25 + 0.450.70.75 + 0.550.30.25 + 0.750.30.75 = 0.49 因为P(HD=No) =

34、1P(HD=Yes) = 0.51，所以，此人不得心脏病的机率略微大一点,2020年7月22日星期三,数据挖掘导论,64,情况二：高血压,如果一个人有高血压，可以通过比较后验概率P(HD=Yes|BP=高)和P(HD=No|BP=高)来诊断他是否患有心脏病 先用全概率公式，计算P(BP=高) P(BP =高) = = 0.850.49 +0.20.51 = 0.5185 其中Yes, No 用贝叶斯公式计算此人患心脏病的后验概率,2020年7月22日星期三,数据挖掘导论,65,情况三,情况三：高血压、饮食健康、经常锻炼身体 患心脏病的后验概率,5.4 人工神经网络,2020年7月22日星期三,

35、数据挖掘导论,67,神经网络,神经网络最早是由心理学家和神经学家提出的,旨在寻求开发和测试神经的计算模拟 神经网络是一组连接的输入/输出单元, 其中每个连接都与一个权相关联 在学习阶段, 通过调整神经网络的权, 使得能够预测输入样本的正确类标记 神经网络的优点 对噪音数据的高承受能力 对未知样本的分类能力 神经网络缺点 需要很长的训练时间, 因而对于有足够长训练时间的应用更合适 很难解释蕴涵在学习权之中的符号含义 它需要大量的参数, 这些通常主要靠经验确定,如网络拓扑或“结构”,2020年7月22日星期三,数据挖掘导论,68,多层前馈神经网络,后向传播是一种神经网络学习算法 后向传播算法在多层

36、前馈(multilayer feed-forward)神经网络上学习 例: 一个多层前馈神经网络 训练样本X = x1 ,x2 ,., xi馈入输入层.每层之间存在加权连接; 其中, wij表示由某层的单元j到前一层的单元i的权,2020年7月22日星期三,数据挖掘导论,69,多层前馈神经网络(续),输入同时提供给称作输入层的单元层 隐藏层的数量是任意的, 实践中通常只用一层 输出层发布给定样本的网络预测 隐藏层和输出层的单元, 有时称作neurodes (源于符号生物学), 或输出单元 包含n个隐藏层的网络称作n+1层神经网络 网络是前馈的, 如果其权都不回送到输入单元, 或前一层的输出单元

37、 网络是全连接的, 如果每个单元都向下一层的每个单元提供输入 给定足够多的隐藏单元, 线性阈值函数的多层前馈神经网络可以逼近任何函数,2020年7月22日星期三,数据挖掘导论,70,多层前馈神经网络(续),定义网络拓扑 用户必须说明输入层的单元数, 隐藏层数, 每一隐藏层的单元数和输出层的单元数 对于“最好的”隐藏层单元数没有明确的规则 网络设计是一个实验过程, 并可能影响结果训练网络的准确性. 权的初值也可能影响结果的准确性 一旦网络经过训练, 并且其准确率不能被接受, 则通常用不同的网络拓扑或使用不同的初始权值, 重复训练过程 对训练样本中每个属性的值进行规格化将有助于加快学习过程 通常,

38、 对输入值规格化, 使得它们落入0.0和1.0之间 离散值属性可以重新编码, 使得每个域值一个输入单元 例如, 如果属性A的定义域为(a0 ,a1 ,a2), 则可以分配三个输入单元I0 ,I1 ,I2表示A,2020年7月22日星期三,数据挖掘导论,71,后向传播,基本思想 迭代地处理一组训练样本, 将每个样本的网络预测与实际知道的类标号比较, 进行学习. 对于每个训练样本, 修改权值, 使得网络预测和实际类之间的均方误差最小 尽管不能保证, 一般地, 权将最终收敛, 学习过程停止 步骤解释 初始化权: 网络的权被初始化为很小的随机数 (例如, 由-1.0到1.0, 或由-0.5到0.5),

39、 每个单元有一个偏置, 也类似地初始化为小随机数 每个样本X按以下步骤处理 向前传播输入 后向传播误差 重复以上两步, 直至终止条件满足,2020年7月22日星期三,数据挖掘导论,72,后向传播(续),向前传播输入 计算隐藏层和输出层每个单元的净输入和输出 对于输入层的单元j, 它的输出等于它的输入; Oj = Ij. 给定隐藏层或输出层的单元j, 到单元j的净输入Ij是 其中, wij是由上一层的单元i到单元j的连接的权; Oi是上一层的单元i的输出; 而 j是单元j的偏差(用来改变单元的活性) 给定单元j的净输入Ij, 则单元j的输出Oj用下式(logistic函数)计算 该函数又称挤压函

40、数, 因为它将一个较大的输入值域映射到较小的区间0到1,2020年7月22日星期三,数据挖掘导论,73,一个神经元(Neuron),一个隐藏或输出单元j：j的输入是来自前一层的输出. 这些与对应的权相乘, 以形成加权和, 加权和加到与单元j相联的偏差上, 一个非线性的活化函数用于净输入,2020年7月22日星期三,数据挖掘导论,74,神经网络的激活函数,线性函数,S型函数,双曲正切函数,符号函数,2020年7月22日星期三,数据挖掘导论,75,后向传播(续),后向传播误差 通过更新权和反映网络预测误差的偏置, 向后传播误差 对于输出层单元j, 误差Errj用下式计算 其中, Oj是单元j的实际

41、输出, 而Tj是j基于给定训练样本的已知类标号的真正输出, Oj (1- Oj)是logistic函数的导数 隐藏层单元j的误差是 其中, wkj是由下一较高层中单元k到单元j的连接权, 而Errk是单元k的误差,2020年7月22日星期三,数据挖掘导论,76,后向传播(续),后向传播误差 (续) 更新权和偏置,以反映传播的误差 权由下式更新 其中,wij是权wij的改变; 变量l是学习率,通常取0和1之间的值. 学习率帮助避免陷入判定空间的局部最小 学习率调整规则: 将学习率设置为1/t. 其中t是已对训练样本集迭代的次数 偏置由下式更新 其中, j是偏置j的改变,2020年7月22日星期三

42、,数据挖掘导论,77,后向传播(续),实例更新VS.周期更新 实例更新(case update): 每处理一个样本就更新权值和偏置 周期更新(epoch update): 处理完训练集中的所有样本之后再更新权值和偏置 终止条件 前一周期所有的wij都小于某个指定的阈值, 或 前一周期未正确分类的样本百分比小于某个阈值, 或 超过预先指定的周期数 实践中, 权值收敛可能需要数十万个周期,2020年7月22日星期三,数据挖掘导论,78,后向传播算法,输入 D: 由训练元组和它们的相关联的目标值组成的数据集 l: 学习率 Network: 多层前馈网络 输出: 训练后的神经网络 方法: (1) 初始

43、化network的权和偏置 (2) while (终止条件不满足) (3) for (D中每个训练元组X) (4) / 向前传播输入 (5) for 每个输入层单元j (6) Oj = Ij ； / 输入单元的输出是它的实际输入值 (7) for (隐藏或输出层每个单元j) (8) / 相对于前一层i, 计算单元j的净输入 (9) / 计算单元j的输出,2020年7月22日星期三,数据挖掘导论,79,后向传播算法(续),(10) / 后向传播误差 (11) for 输出层每个单元j (12) Errj = Oj(1 Oj)(Tj Oj)； / 计算误差 (13) for (由最后一个到第一个隐

44、藏层, 对于隐藏层每个单元j ) (14) / 计算下一个较高层k的误差 (15) for networ中每个权wij (16) wij = (l)ErrjOi ； / 权值增量 (17) wij = wij + wij ； / 权值更新 (18) for networ中每个偏差 j (19) j = (l)Errj； / 偏置增量 (20) j = j +j； / 偏置更新 (21) ,2020年7月22日星期三,数据挖掘导论,80,后向传播:例,一个多层前馈神经网络 第一个训练样本X = 1,0,1（其类标号为1）,2020年7月22日星期三,数据挖掘导论,81,后向传播:例(续),初始输

45、入、权值和偏差值 净输入和输出的计算 计算每个结点的误差,2020年7月22日星期三,数据挖掘导论,82,后向传播:例(续),计算权和偏置的更新,2020年7月22日星期三,数据挖掘导论,83,神经网络的特点,至少含有一个隐藏层的多层神经网络是一种普适近似（universal approximator），即可以用来近似任何目标函数 ANN可以处理冗余特征 权值在训练过程中自动学习，冗余特征的权值非常小 神经网络对训练数据中的噪声非常敏感 使用确认集来确定模型的泛化误差 每次迭代把权值减少一个因子 使用的梯度下降方法经常会收敛到局部最小值 权值更新公式中加上一个动量项 训练ANN是一个很耗时的过

46、程，但分类非常快,5.5 支持向量机,2020年7月22日星期三,数据挖掘导论,85,支持向量机,支持向量机 (Support Vector Machines, SVM) 源于Vapnik和Chervonenkis的统计学习理论的早期工作 第一篇论文是Boser, Guyon和Vapnik BGV92的文章 优点 对复杂的非线性边界的建模能力 与其它模型相比, 它们不太容易过分拟合 支持向量机还提供了学习模型的紧凑表示 广泛的使用范围 SVM可以用来预测和分类 它们已经用在许多领域, 包括手写数字识别、对象识别、演说人识别, 以及基准时间序列预测检验,2020年7月22日星期三,数据挖掘导论,

47、86,支持向量机,两个线性可分的类 找到这样一个超平面，使得所有的方块位于这个超平面的一侧，而所有的圆圈位于它的另一侧 可能存在无穷多个那样的超平面,2020年7月22日星期三,数据挖掘导论,87,决策边界的边缘,找这样的超平面，它最大化边缘 B1比B2好,2020年7月22日星期三,数据挖掘导论,88,SVM的决策边界和边缘,一个线性分类器的决策边界可以写成如下形式： wx + b = 0 其中，w和b是模型的参数,2020年7月22日星期三,数据挖掘导论,89,边缘,方块的类标号为+1，圆圈的类标号为1 z的类标号y 调整决策边界的参数w和b，两个平行的超平面bi1和bi2可以表示如下 b

48、i1：w x + b = 1 bi2：w x + b = 1 可以证明, 边缘d,2020年7月22日星期三,数据挖掘导论,90,边缘推导,w的方向垂直于决策边界 如果xa和xb是任意两个位于决策边界上的点，则 wxa + b = 0, wxb + b = 0 于是w(xb xa) = 0. 由于xb xa是决策超平面中任意向量, 于是w的方向必然垂直于决策边界 令x1是bi1上的数据点，x2是bi2上的数据点. 代入bi1和bi2相减得到 w.(x1 x2) = 2 由 令u=w, v= x1 x2, 得到 |w| x1 x2 |cos(w, x1 x2)=2,2020年7月22日星期三,数

49、据挖掘导论,91,边缘推导(续),但| x1 x2 |cos(w, x1 x2)=d 于是|w|d=2，即,2020年7月22日星期三,数据挖掘导论,92,SVM,SVM的训练阶段从训练数据中估计决策边界的参数w和b 最大化边缘d，并满足 wxi + b1 如果yi = 1 wxi + b1 如果yi = 1 即 yi(wxi + b)1 最大化d等价于最小化 这是一个凸二次优化问题，可以通过标准的拉格朗日乘子（Lagrange multiplier）方法求解,2020年7月22日星期三,数据挖掘导论,93,SVM(续),拉格朗日算子 其中，参数i称为拉格朗日乘子 对Lp关于w和b求偏导，并令

50、它们等于零 因为拉格朗日乘子i是未知的，因此仍然不能得到w和b的解,(5-38),(5-39),(5-40),2020年7月22日星期三,数据挖掘导论,94,SVM(续),使用Karuch-Kuhn-Tucher（KKT）条件： i 0 i yi(wxi + b) 1 = 0 （5.42） 除非训练实例满足方程yi(wxi + b) = 1, 否则拉格朗日乘子i必须为零 i 0的训练实例位于超平面bi1或bi2上，称为支持向量 （5.39）和（5.40）代入到公式（5.38）中 这是Lp的对偶问题(最大化问题 ). 可以使用数值计算技术, 如二次规划来求解,(5-43),2020年7月22日星

51、期三,数据挖掘导论,95,SVM(续),解出i后, 用(5.39)求w, 再用(5.42)求b 决策边界为 z可以按以下的公式来分类 如果f(z) = 1，则检验实例z被分为到正类，否则分到负类,2020年7月22日星期三,数据挖掘导论,96,SVM: 例,例: 二维数据集包含8个训练实例 使用二次规划方法, 求解优化问题LD, 得到i. w1 = iyixi1 = 65.5261 1 0.3858 + 65.5261 (1) 0.4871 = 6.64 w2 = iyixi2 = 65.5261 1 0.4687 + 65.5261 (1) 0.611 = 9.32 b(1) = 1 wx1

52、 = 1 (6.64) (0.3858) (9.32)(0.4687) = 7.9300 b(2) = 1 wx2 = 1 (6.64)(0.4871) (9.32)(0.611) = 7.9289 b = (b(1) + b(2)/2 = 7.93,i,2020年7月22日星期三,数据挖掘导论,97,SVM: 不可分情况,如果不是线性可分的，怎么办？ 软边缘（soft margin） 允许一定训练误差 引入松驰变量i 其中C和k是用户指定的参数， 对误分训练实例加罚 取k=1， C根据模型在确认集上的性能选择,2020年7月22日星期三,数据挖掘导论,98,SVM: 不可分情况(续),拉格朗

53、日算子 其中，前面两项是需要最小化的目标函数，第三项表示与松弛变量相关的不等式约束，而最后一项是要求i的值非负的结果 KKT条件 i 0, i 0, i 0 i yi(wxi + b) 1 + i = 0 i i = 0,2020年7月22日星期三,数据挖掘导论,99,SVM: 不可分情况(续),令L关于w, b和i的一阶导数为零,2020年7月22日星期三,数据挖掘导论,100,SVM: 不可分情况(续),对偶拉格朗日问题 其形式与可分情况相同, 但是0iC,2020年7月22日星期三,数据挖掘导论,101,非线性 SVM,使用非线性变换 例:,2020年7月22日星期三,数据挖掘导论,10

54、2,非线性 SVM(续),非线性 SVM的优化问题 约束条件: yi(w(xi) + b)1, i = 1, 2, ., N 对偶拉格朗日问题 参数w和b,2020年7月22日星期三,数据挖掘导论,103,非线性 SVM(续),实例z分类 点积(xi)(xj) 计算问题 能否在原空间直接计算? 例:,2020年7月22日星期三,数据挖掘导论,104,核技术,Mercer定理: 核函数K可以表示为K(u, v) = (u)(v), 当且仅当对于任意满足g(x)2dx为有限值的函数g(x)，则K(x, y) g(x) g(y) dx dy0 满足定理5.1的核函数称为正定（positive def

55、inite）核函数 常用核函数,2020年7月22日星期三,数据挖掘导论,105,SVM的特点,SVM学习问题可以表示为凸优化问题，因此可以利用已知的有效算法发现目标函数的全局最小值 SVM通过最大化决策边界的边缘来控制模型的能力 需要提供其他参数，如使用的核函数类型、为了引入松弛变量所需的代价函数C等 分类属性处理 每个分类属性值引入一个哑变量, 转化为二元变量 可以推广到多类问题,2020年7月22日星期三,数据挖掘导论,106,多类问题,SVM是对二类问题设计的 还有一些方法也是针对二类问题的 如何处理多类问题? 训练 令Y = y1, y2,., yK是类标号的集合 1-r方法 : 分

56、解成K个二类问题 每一个类yiY创建一个二类问题, 其中所有属于yi的样本都被看作正类, 而其他样本作为负类 1-1方法 : 构建K(K 1)/2个二类分类器 每一个分类器用来区分一对类(yi, yj) 为类(yi, yj)构建二类分类器时, 不属于yi或yj的样本被忽略掉,2020年7月22日星期三,数据挖掘导论,107,多类问题(续),分类 投票表决 票的计算 1-r方法 如果一个样本被分为正类, 则正类得一票 如果一个样本被分为负类, 则除正类之外的所有类都得到一票 1-1方法 如果Cj把样本分到yi类, 则yi类得一票 冲突处理 分到多数类/少数类,2020年7月22日星期三,数据挖掘

57、导论,108,多类问题:例,例: Y = y1, y2, y3, y4 1-r方法建立4个分类器 设这4个分类器分别把检验实例x分类为+, , , 使用简单的多数表决, y1得到最高的票4，而其他类仅仅得到3票, 因此检验实例被分类为y1 1-1方法建立6个分类器 假设它们对x如下表 y1和y4都得到2票 , 而y2和y3仅仅得到1票,5.6 组合方法,2020年7月22日星期三,数据挖掘导论,110,一般思想,聚集多个分类器的预测来提高分类准确率 称为组合（ensemble）或分类器组合（classifier combination）方法,2020年7月22日星期三,数据挖掘导论,111,W

58、hy does it work?,假定有 25 基分类器 每个基分类器的误差均为 = 0.35 假定基分类器是独立的 组合分类器错误预测的概率为:,2020年7月22日星期三,数据挖掘导论,112,Bagging,Bagging又称自助聚集（boot strap aggregating） 训练阶段 使用自助抽样产生多个训练数据集 有放回、等概率、等容量抽样 在每个训练数据集上使用相同的分类算法建立基分类器 分类: x是待分类实例 每个基分类器独立地对x产生类预测, 算作一票 统计得票, 并将x指派到得票最高的类,2020年7月22日星期三,数据挖掘导论,113,Boosting,基本思想 训练 赋予每个训练记录一个权值wi 权值反映对元组分类的困难程度 迭代地学习k个分类器: 学习得到分类器Mi之后, 更新权值, 使得其后的分类器