分类其他技术PPT讲稿.ppt

《分类其他技术PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《分类其他技术PPT讲稿.ppt（134页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、分类其他技术分类其他技术第1页，共134页，编辑于2022年，星期五2023/1/91数据挖掘：概念与技术第第5章章 分类分类:其他技术其他技术 基于规则的分类基于规则的分类最近邻分类最近邻分类贝叶斯分类贝叶斯分类神经网络神经网络支持向量机支持向量机组合方法组合方法不平衡类问题不平衡类问题多类问题多类问题第2页，共134页，编辑于2022年，星期五2023/1/92数据挖掘：概念与技术5.1 基于规则的分类器基于规则的分类器第3页，共134页，编辑于2022年，星期五2023/1/93数据挖掘：概念与技术基于规则的分类器基于规则的分类器n使用一组使用一组“ifthen”规则进行分类规则进行分类

2、n规则规则:(Condition)yn其中其中 n Condition 是属性测试的合取是属性测试的合取n y 是类标号是类标号n左部左部:规则的前件或前提规则的前件或前提n右部右部:规则的结论规则的结论n分类规则的例子分类规则的例子:n(Blood Type=Warm)(Lay Eggs=Yes)Birdsn(Taxable Income 鸟类鸟类n规则规则r3 覆盖覆盖“灰熊灰熊”=哺乳类哺乳类名称体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号鹰灰熊 恒温恒温羽毛软毛否是否否是否是是否是？2023/1/96数据挖掘：概念与技术第6页，共134页，编辑于2022年，星期五规则的质量规则的质量

3、 n用覆盖率和准确率度量用覆盖率和准确率度量n规则的覆盖率（规则的覆盖率（coverage）:n满足规则前件的记录所占的比满足规则前件的记录所占的比例例n规则的准确率（规则的准确率（accuracy）:n在满足规则前件的记录中，满足规在满足规则前件的记录中，满足规则后件的记录所占的比例则后件的记录所占的比例n规则规则:(Status=Single)No Coverage=40%,Accuracy=50%Tid Refund Marital Status Taxable Income Class 1Yes Single 125KNo2No Married 100K No3No Single 70

4、K No 4 Yes Married 120K No 5 No Divorced 95K Yes 6 No Married 60K No 7 Yes Divorced 220K No 8 No Single 85K Yes 9No Married 75K No 10NoSingle90K Yes10 2023/1/97数据挖掘：概念与技术第7页，共134页，编辑于2022年，星期五如何用规则分类如何用规则分类n一组规则一组规则r1：（胎生：（胎生=否）否）（飞行动物（飞行动物=是）是）鸟类鸟类r2：（胎生：（胎生=否）否）（水生动物（水生动物=是）是）鱼类鱼类r3：（胎生：（胎生=是）是）（体

5、温（体温=恒温）恒温）哺乳类哺乳类r4：（胎生：（胎生=否）否）（飞行动物（飞行动物=否）否）爬行类爬行类r5：（水生动物：（水生动物=半）半）两栖类两栖类n待分类记录待分类记录n狐猴触发规则狐猴触发规则 r3,它分到哺乳类它分到哺乳类n海龟触发规则海龟触发规则r4和和 r5-冲突冲突n狗鲨未触发任何规则狗鲨未触发任何规则名称名称体温体温胎生胎生飞行动物飞行动物水生动物水生动物类类狐猴恒温是否否?海龟冷血否否半水生?狗鲨冷血是否是?2023/1/98数据挖掘：概念与技术第8页，共134页，编辑于2022年，星期五规则的分类器的特征规则的分类器的特征n互斥规则集互斥规则集n每个记录最多被一个规则

6、覆盖每个记录最多被一个规则覆盖n如果规则都是相互独立的，分类器包含互斥规则如果规则都是相互独立的，分类器包含互斥规则n如果规则集不是互斥的如果规则集不是互斥的n一个记录可能被多个规则触发一个记录可能被多个规则触发n如何处理如何处理?n 有序规则集有序规则集n基于规则的序基于规则的序 vs 基于类的序基于类的序n 无序规则集无序规则集 使用投票策略使用投票策略2023/1/99数据挖掘：概念与技术第9页，共134页，编辑于2022年，星期五规则的分类器的特征规则的分类器的特征(续续)n穷举规则集穷举规则集n每个记录至少被一个规则覆盖每个记录至少被一个规则覆盖n如果规则集涵盖了属性值的所有可能组合

7、，则规则集具有穷举覆盖如果规则集涵盖了属性值的所有可能组合，则规则集具有穷举覆盖n如果规则集不是穷举的如果规则集不是穷举的n一个记录可能不被任何规则触发一个记录可能不被任何规则触发n如何处理如何处理?n 使用缺省类使用缺省类2023/1/910数据挖掘：概念与技术第10页，共134页，编辑于2022年，星期五有序规则集有序规则集n根据规则优先权将规则排序定秩（根据规则优先权将规则排序定秩（rank）n有序规则集又成决策表（有序规则集又成决策表（decision list）n对记录进行分类时对记录进行分类时n由被触发的，具有最高秩的规则确定记录的类标号由被触发的，具有最高秩的规则确定记录的类标号

8、n如果没有规则被触发，则指派到缺省类如果没有规则被触发，则指派到缺省类r1：（胎生：（胎生=否）否）（飞行动物（飞行动物=是）是）鸟类鸟类r2：（胎生：（胎生=否）否）（水生动物（水生动物=是）是）鱼类鱼类r3：（胎生：（胎生=是）是）（体温（体温=恒温）恒温）哺乳类哺乳类r4：（胎生：（胎生=否）否）（飞行动物（飞行动物=否）否）爬行类爬行类r5：（水生动物：（水生动物=半）半）两栖类两栖类名称名称体温体温胎生胎生飞行动物飞行动物水生动物水生动物类类海龟冷血否否半水生?2023/1/911数据挖掘：概念与技术第11页，共134页，编辑于2022年，星期五规则定序方案规则定序方案n基于规则的序

9、基于规则的序n根据规则的质量排序根据规则的质量排序n基于类的序基于类的序n属于同一类的规则放在一起属于同一类的规则放在一起n基于类信息（如类的分布、重要性）对每类规则排序基于类信息（如类的分布、重要性）对每类规则排序基于规则的排序（表皮覆盖=羽毛,飞行动物=是）鸟类（体温=恒温,胎生=是）哺乳类（体温=恒温,胎生=否）鸟类（水生动物=半）两栖类（表皮覆盖=鳞片,水生动物=否）爬行类（表皮覆盖=鳞片,水生动物=是）鱼类（表皮覆盖=无）两栖类 基于类的排序（表皮覆盖=羽毛,飞行动物=是）鸟类（体温=恒温,胎生=否）鸟类（体温=恒温,胎生=是）哺乳类（水生动物=半）两栖类（表皮覆盖=无）=两栖类（表

10、皮覆盖=鳞片,水生动物=否）爬行类（表皮覆盖=鳞片,水生动物=是）鱼类 2023/1/912数据挖掘：概念与技术第12页，共134页，编辑于2022年，星期五如何建立基于规则的分类器如何建立基于规则的分类器n直接方法直接方法:n直接由数据提取规则直接由数据提取规则n例如例如:RIPPER,CN2,Holtes 1Rn间接方法间接方法:n由其他分类模型提取规则由其他分类模型提取规则(例如，从决策树、神经网络等例如，从决策树、神经网络等).n例如例如:C4.5rules2023/1/913数据挖掘：概念与技术第13页，共134页，编辑于2022年，星期五直接方法直接方法:顺序覆盖顺序覆盖n基本思想

11、基本思想n依次对每个类建立一个或多个规则依次对每个类建立一个或多个规则n对第对第i类建立规则类建立规则n第第i类记录为正例，其余为负例类记录为正例，其余为负例n建立一个第建立一个第i类的规则类的规则r，尽可能地覆盖正例，而不覆盖负例，尽可能地覆盖正例，而不覆盖负例n删除删除r覆盖的所有记录，在剩余数据集上学习下一个规则，直到覆盖的所有记录，在剩余数据集上学习下一个规则，直到所有第所有第i类记录都被删除类记录都被删除2023/1/914数据挖掘：概念与技术第14页，共134页，编辑于2022年，星期五直接方法直接方法:顺序覆盖顺序覆盖n顺序覆盖（顺序覆盖（sequential covering）

12、算法）算法 1：令：令E是训练记录，是训练记录，A是属性是属性值对的集合值对的集合(Aj,vj)2：令：令Yo是类的有序集是类的有序集y1,y2,.,yk 3：令：令R=是初始规则列表是初始规则列表 4：for 每个类每个类 yYo yk do 5：while 终止条件不满足终止条件不满足 do 6：r Learn-One-Rule(E,A,y)7：从从E中删除被中删除被r覆盖的训练记录覆盖的训练记录 8：追加追加r到规则列表尾部：到规则列表尾部：RR r 9：end while10：end for11：把默认规则：把默认规则yk插入到规则列表插入到规则列表R尾部尾部 2023/1/915数据

13、挖掘：概念与技术第15页，共134页，编辑于2022年，星期五顺序覆盖顺序覆盖:例例(a)Original data(b)Step 1(c)Step 2(c)Step 32023/1/916数据挖掘：概念与技术第16页，共134页，编辑于2022年，星期五删除实例删除实例n为什么要删除实例为什么要删除实例?n否则否则,下一个规则将与前面的规则下一个规则将与前面的规则相同相同n为什么删除正实例为什么删除正实例?n确保下一个规则不同确保下一个规则不同n为什么删除负实例为什么删除负实例?n防止低估规则的准确率防止低估规则的准确率n比较图中的规则比较图中的规则 R2 和和 R32023/1/917数据

14、挖掘：概念与技术第17页，共134页，编辑于2022年，星期五Learn-One-Rulen规则增长规则增长n实例删除实例删除n规则评估规则评估n停止准则停止准则n规则剪枝规则剪枝2023/1/918数据挖掘：概念与技术第18页，共134页，编辑于2022年，星期五规则增长规则增长n两种策略两种策略n一般到特殊一般到特殊n从初始规则从初始规则r:y开始开始n反复加入合取项，得到更特殊的规则，直到不能再加入反复加入合取项，得到更特殊的规则，直到不能再加入n 特殊到一般特殊到一般n随机地选择一个正例作为初始规则随机地选择一个正例作为初始规则n反复删除合取项，得到更一般的规则，直到不能再删除反复删除

15、合取项，得到更一般的规则，直到不能再删除n问题问题n加入加入/删除合取项有多种选择，如何选择？删除合取项有多种选择，如何选择？n何时停止加入何时停止加入/删除合取项？删除合取项？需要评估标准需要评估标准2023/1/919数据挖掘：概念与技术第19页，共134页，编辑于2022年，星期五规则增长规则增长:例例n一般到特殊一般到特殊体温=恒温，表皮覆盖=毛发，胎生=是，水生动物=否，飞行动物=否，有腿=是，冬眠=否=哺乳类表皮覆盖=毛发，胎生=是，水生动物=否，飞行动物=否，有腿=是，冬眠=否=哺乳类体温=恒温，表皮覆盖=毛发，胎生=是，水生动物=否，飞行动物=否，有腿=是=哺乳类=哺乳类表皮覆

16、盖=毛发=哺乳类体温=恒温=哺乳类有腿=否=哺乳类体温=恒温，有腿=是=哺乳类体温=恒温，胎生=是=哺乳类n 特殊到一般特殊到一般2023/1/920数据挖掘：概念与技术第20页，共134页，编辑于2022年，星期五规则评估规则评估n常用的度量常用的度量n准确率准确率n似然比似然比nLaplacenM-estimatenFOIL信息增益信息增益 2023/1/921数据挖掘：概念与技术第21页，共134页，编辑于2022年，星期五规则评估规则评估(续续)n准确率准确率nAccuracynn:被规则覆盖的实例数被规则覆盖的实例数nnc:被规则正确分类的实例数被规则正确分类的实例数n问题：准确率高

17、的规则可能覆盖率太低问题：准确率高的规则可能覆盖率太低n似然比似然比（越高越好）（越高越好）nk是类的个数是类的个数nfi是被规则覆盖的类是被规则覆盖的类i的样本的观测频度的样本的观测频度nei是规则作随机猜测的期望频度是规则作随机猜测的期望频度2023/1/922数据挖掘：概念与技术第22页，共134页，编辑于2022年，星期五规则评估规则评估:例例n例例:60个正例和个正例和100个反例个反例 规则规则r1：覆盖：覆盖50个正例和个正例和5个反例（个反例（acc=90.9%）规则规则r2：覆盖：覆盖2个正例和个正例和0个反例个反例（acc=100%）n使用准确率使用准确率,r2好好n使用似

18、然比使用似然比nr1:正类的期望频度为正类的期望频度为e+=55 60/160=20.625 负类的期望频度为负类的期望频度为e =55 100/160=34.375 nr2:正类的期望频度为正类的期望频度为e+=2 60/160=0.75 负类的期望频度为负类的期望频度为e =2 100/160=1.25 nR(r1)=2 50 log2(50/20.625)+5 log2(5/34.375)=99.9 nR(r2)=2 2 log2(2/0.75)+0 log2(0/1.25)=5.66 nr1比比r2好好 2023/1/923数据挖掘：概念与技术第23页，共134页，编辑于2022年，星

19、期五规则评估规则评估(续续)n考虑规则覆盖率的评估度量考虑规则覆盖率的评估度量 nn是规则覆盖的样例数，是规则覆盖的样例数，f+是规则覆盖的正例数，是规则覆盖的正例数，k是类的总数，是类的总数，p+是是正类的先验概率正类的先验概率 n当规则的覆盖率很高时，两个度量都渐近地趋向于规则的准确率当规则的覆盖率很高时，两个度量都渐近地趋向于规则的准确率f+/n n继续前例继续前例nr1的的Laplace度量为度量为51/57=89.47%，很接近它的准确率，很接近它的准确率nr2的的Laplace度量（度量（75%）比它的准确率小很多）比它的准确率小很多 2023/1/924数据挖掘：概念与技术第24

20、页，共134页，编辑于2022年，星期五规则评估规则评估(续续)n考虑规则的支持度计数的评估度量考虑规则的支持度计数的评估度量n规则的支持度计数对应于它所覆盖的正例数规则的支持度计数对应于它所覆盖的正例数 nFOIL信息增益（信息增益（First Order Inductive Leaner information gain）n设规则设规则r:A+覆盖覆盖p0个正例和个正例和n0个反例个反例;n规则规则r:A B+覆盖覆盖p1个正例和个正例和n1个反例个反例.扩展后规则的扩展后规则的FOIL信息信息增益定义为增益定义为 n该度量与该度量与p1和和p1/(p1+n1)成正比，所以它更倾向于选择那

21、些高支持度成正比，所以它更倾向于选择那些高支持度计数和高准确率的规则计数和高准确率的规则 n继续前例继续前例nr1和和r2的的FOIL信息增益分别为信息增益分别为43.12和和2，因此规则，因此规则r1比比r2好好 2023/1/925数据挖掘：概念与技术第25页，共134页，编辑于2022年，星期五停止条件与规则剪枝停止条件与规则剪枝n停止条件停止条件n计算增益计算增益n如果增益不显著如果增益不显著,则丢弃新规则则丢弃新规则n规则剪枝规则剪枝n类似于决策树后剪枝类似于决策树后剪枝n降低错误剪枝降低错误剪枝:n 删除规则中的合取项删除规则中的合取项n 比较剪枝前后的错误率比较剪枝前后的错误率

22、n 如果降低了错误率如果降低了错误率,则剪掉该合取项则剪掉该合取项2023/1/926数据挖掘：概念与技术第26页，共134页，编辑于2022年，星期五直接方法直接方法:RIPPERn对于对于2类问题类问题,选定一个类为正类，另一个为负类选定一个类为正类，另一个为负类n从正类学习规则从正类学习规则n负类时缺省类负类时缺省类n多类问题多类问题n按类的大小（属于特定类的实例所占的比例）对诸类排序按类的大小（属于特定类的实例所占的比例）对诸类排序n从最小的类开始学习规则，其余类都看做负类从最小的类开始学习规则，其余类都看做负类n对次小类学习规则，如此下去对次小类学习规则，如此下去2023/1/927

23、数据挖掘：概念与技术第27页，共134页，编辑于2022年，星期五直接方法直接方法:RIPPER(续续)n规则增长规则增长:n由空规则开始由空规则开始n只要能够提高只要能够提高FOIL信息增益就增加一个合取项信息增益就增加一个合取项n当规则不再覆盖负实例时就停止当规则不再覆盖负实例时就停止n剪枝剪枝n剪枝度量剪枝度量:v=(p n)/(p+n)n p:验证集中被规则覆盖的正实例数验证集中被规则覆盖的正实例数n n:验证集中被规则覆盖的负实例数验证集中被规则覆盖的负实例数n剪枝方法剪枝方法:n如果剪掉合取项可以提高如果剪掉合取项可以提高v就剪就剪2023/1/928数据挖掘：概念与技术第28页，

24、共134页，编辑于2022年，星期五直接方法直接方法:RIPPER(续续)n建立规则集建立规则集:n使用顺序覆盖算使用顺序覆盖算n找出覆盖当前正实例的最佳规则找出覆盖当前正实例的最佳规则n删除被规则覆盖的所有正实例和负实例删除被规则覆盖的所有正实例和负实例n当一个规则加入规则集时，计算新的描述长度当一个规则加入规则集时，计算新的描述长度n当新的描述长度比已经得到的描述长度多当新的描述长度比已经得到的描述长度多d位时，就停止增加新位时，就停止增加新规则规则2023/1/929数据挖掘：概念与技术第29页，共134页，编辑于2022年，星期五直接方法直接方法:RIPPER(续续)n优化规则集优化规

25、则集:n对规则集对规则集R中的每个规则中的每个规则 rn考虑考虑2个替换的规则个替换的规则:n替换规则替换规则(r*):重新增长新规则重新增长新规则n编辑的规则编辑的规则(r):把一个新的合取项增加到规则把一个新的合取项增加到规则 r n比较替换前后的规则集比较替换前后的规则集 n选择最小化选择最小化MDL的规则集的规则集n对剩下的正实例，重复规则产生和优化对剩下的正实例，重复规则产生和优化2023/1/930数据挖掘：概念与技术第30页，共134页，编辑于2022年，星期五规则提取的间接方法规则提取的间接方法n决策树从根结点到叶结点的每一条路径都可以表示为一个分类规则决策树从根结点到叶结点的

26、每一条路径都可以表示为一个分类规则 n路径中的测试条件构成规则前件的合取项，叶结点的类标号赋给规则后路径中的测试条件构成规则前件的合取项，叶结点的类标号赋给规则后件件 2023/1/931数据挖掘：概念与技术第31页，共134页，编辑于2022年，星期五间接方法间接方法:C4.5rules(续续)n从未剪枝的决策树提取规则从未剪枝的决策树提取规则n规则产生规则产生n对每个规则对每个规则 r:A y,n考虑替换规则考虑替换规则 r:A y n其中其中 A 由删除由删除A的一个合取项得到的一个合取项得到n比较比较r与所有与所有r的悲观误差的悲观误差n如果如果r的悲观误差小，则剪枝的悲观误差小，则剪

27、枝n重复该过程，直到不能改进重复该过程，直到不能改进2023/1/932数据挖掘：概念与技术第32页，共134页，编辑于2022年，星期五间接方法间接方法:C4.5rulesn规则定序规则定序n不是对规则定序，而是对规则的子集定序不是对规则定序，而是对规则的子集定序(class ordering)n每个规则子集是一组具有相同规则后件每个规则子集是一组具有相同规则后件(class)的规则的规则n计算每个子集的描述长度计算每个子集的描述长度n描述长度描述长度=L(error)+g L(model)ng 是参数，考虑规则集中冗余属性是参数，考虑规则集中冗余属性(缺省值缺省值g=0.5)2023/1/

28、933数据挖掘：概念与技术第33页，共134页，编辑于2022年，星期五C4.5 vs C4.5rules vs RIPPERC4.5rules:（胎生（胎生=否，飞行动物否，飞行动物=是）是）=鸟类鸟类（胎生（胎生=否，水生动物否，水生动物=是）是）=鱼类鱼类（胎生（胎生=是）是）=哺乳类哺乳类（胎生（胎生=否，飞行动物否，飞行动物=否，水生动物否，水生动物=否）否）=爬行类爬行类（）（）=两栖类两栖类 胎生胎生水生水生?飞行飞行?哺乳类哺乳类鱼类鱼类两栖类两栖类鸟类鸟类爬行类爬行类YesNoYesSometimesNoYesNo2023/1/934数据挖掘：概念与技术第34页，共134页，

29、编辑于2022年，星期五基于规则的分类器的特征基于规则的分类器的特征 n表达能力与决策树一样高表达能力与决策树一样高n容易解释容易解释n容易产生容易产生n能够快速对新实例分类能够快速对新实例分类n性能可与决策树相媲美性能可与决策树相媲美2023/1/935数据挖掘：概念与技术第35页，共134页，编辑于2022年，星期五5.2 最近邻分类器最近邻分类器 第36页，共134页，编辑于2022年，星期五2023/1/936数据挖掘：概念与技术急切学习急切学习 vs 惰性学习惰性学习n急切学习（急切学习（Eager Learner）n两步过程两步过程:(1)归纳归纳(2)演绎演绎n惰性学习（惰性学习

30、（lazy learner）n把训练数据建模过程推迟到需要对样本分类时把训练数据建模过程推迟到需要对样本分类时n例子例子nRote-learner（死记硬背）（死记硬背）n记住所有的训练数据，仅当记录的属性值与一个训练记录完全匹记住所有的训练数据，仅当记录的属性值与一个训练记录完全匹配才对它分类配才对它分类n最近邻（最近邻（Nearest neighbor）n使用使用“最近最近”的的 k 个点个点(最近邻最近邻)进行分类进行分类2023/1/937数据挖掘：概念与技术第37页，共134页，编辑于2022年，星期五最近邻分类器最近邻分类器n基本思想基本思想:nIf it walks like a

31、 duck,quacks like a duck,then its probably a duck训练记录训练记录待分类记录待分类记录计算距离计算距离选择选择k 个个“最近最近”的记录的记录2023/1/938数据挖掘：概念与技术第38页，共134页，编辑于2022年，星期五最近邻分类器最近邻分类器 n要求要求n存放训练记录存放训练记录n计算记录间距离的度量计算记录间距离的度量nk值值,最近邻数最近邻数n对未知记录分类对未知记录分类:n计算域各训练记录的距离计算域各训练记录的距离n找出找出 k 个最近邻个最近邻 n使用最近邻的类标号决定未知记录使用最近邻的类标号决定未知记录的类标号的类标号(例

32、如例如,多数表决多数表决)2023/1/939数据挖掘：概念与技术第39页，共134页，编辑于2022年，星期五最近邻定义最近邻定义 记录记录x的的k-最近邻是与最近邻是与x之间距离最小的之间距离最小的k个训练数据点个训练数据点2023/1/940数据挖掘：概念与技术第40页，共134页，编辑于2022年，星期五1 nearest-neighborVoronoi Diagram2023/1/941数据挖掘：概念与技术第41页，共134页，编辑于2022年，星期五 k-最近邻分类算法最近邻分类算法 nk-最近邻分类算法最近邻分类算法1：令：令k是最近邻数目，是最近邻数目，D是训练样例的集合是训练

33、样例的集合2：for 每个测试样例每个测试样例 z=(x,y)do3：计算计算z和每个样例和每个样例(x,y)D之间的距离之间的距离d(x,x)4：选择离选择离z最近的最近的k个训练样例的集合个训练样例的集合Dz D5：6：end for n距离加权表决距离加权表决 2023/1/942数据挖掘：概念与技术第42页，共134页，编辑于2022年，星期五k-最近邻最近邻nk值的选择值的选择:n如果如果 k 太小太小,则对噪声点敏感则对噪声点敏感n如果如果 k 太大太大,邻域可能包含很邻域可能包含很 多其他类的点多其他类的点n定标问题（规范化）定标问题（规范化）n属性可能需要规范化，防止距属性可能

34、需要规范化，防止距 离度量被具有很大值域的属性离度量被具有很大值域的属性 所左右所左右2023/1/943数据挖掘：概念与技术第43页，共134页，编辑于2022年，星期五k-NN的特点的特点nk-NN的特点的特点n是一种基于实例的学习是一种基于实例的学习 n需要一个邻近性度量来确定实例间的相似性或距离需要一个邻近性度量来确定实例间的相似性或距离 n不需要建立模型，但分类一个测试样例开销很大不需要建立模型，但分类一个测试样例开销很大n需要计算域所有训练实例之间的距离需要计算域所有训练实例之间的距离 n基于局部信息进行预测，对噪声非常敏感基于局部信息进行预测，对噪声非常敏感 n最近邻分类器可以生

35、成任意形状的决策边界最近邻分类器可以生成任意形状的决策边界 n决策树和基于规则的分类器通常是直线决策边界决策树和基于规则的分类器通常是直线决策边界 n需要适当的邻近性度量和数据预处理需要适当的邻近性度量和数据预处理 n防止邻近性度量被某个属性左右防止邻近性度量被某个属性左右2023/1/944数据挖掘：概念与技术第44页，共134页，编辑于2022年，星期五5.3 贝叶斯分类器贝叶斯分类器 第45页，共134页，编辑于2022年，星期五2023/1/945数据挖掘：概念与技术贝叶斯定理贝叶斯定理n每个记录用一个每个记录用一个d维特征向量维特征向量X=(x1,x2,xd)表示表示n假定有假定有k

36、个类个类y1,y2,yk.n给定给定X,X属于属于yj类的后验概率类的后验概率P(yj|X)满足贝叶斯满足贝叶斯(Bayes)定理定理nMAP(maximum posteriori hypothesis,最大后验假设最大后验假设)n将将X指派到具有最大后验概率指派到具有最大后验概率P(yj|X)的类的类yj，即，即n将将X指派到指派到P(X|yj)P(yj)最大的类最大的类yj2023/1/946数据挖掘：概念与技术第46页，共134页，编辑于2022年，星期五朴素贝叶斯分类朴素贝叶斯分类n朴素贝叶斯分类朴素贝叶斯分类(Nave Bayes Classifier)工作原理工作原理n给定一个未知

37、的数据样本给定一个未知的数据样本X,分类法将预测分类法将预测X属于具有最高后验概率的类属于具有最高后验概率的类.即即,未知的样本分配给类未知的样本分配给类yj,当且仅当当且仅当根据贝叶斯定理根据贝叶斯定理,我们有我们有n由于由于P(X)对于所有类为常数对于所有类为常数,只需要最大化只需要最大化P(X|yj)P(yj)即可即可.2023/1/947数据挖掘：概念与技术第47页，共134页，编辑于2022年，星期五朴素贝叶斯分类朴素贝叶斯分类(续续)n估计估计P(yj)n类类yj的先验概率可以用下式估计的先验概率可以用下式估计 P(yj)=nj/nn 其中其中,nj是类是类yj中的训练样本数中的训

38、练样本数,而而n是训练样本总数是训练样本总数 n估计估计P(X|yj)n为便于估计为便于估计P(X|yj),假定类条件独立假定类条件独立-给定样本的类标号给定样本的类标号,假定属性假定属性值条件地相互独立值条件地相互独立.n于是于是,P(X|Y=yj)可以用下式估计可以用下式估计 n其中其中,P(xi|yj)可以由训练样本估值可以由训练样本估值 2023/1/948数据挖掘：概念与技术第48页，共134页，编辑于2022年，星期五朴素贝叶斯分类朴素贝叶斯分类(续续)n估计估计P(xi|yj)n设第设第i个属性个属性Ai是分类属性是分类属性,则则 P(xi|yj)=nij/nj其中其中nij是在

39、属性是在属性Ai上具有值上具有值xi的的yj类的训练样本数类的训练样本数,而而nj是是yj类的训练类的训练样本数样本数 n设第设第i个属性个属性Ai是连续值属性是连续值属性n把把Ai离散化离散化n假定假定Ai服从高斯分布服从高斯分布 n其中其中,ij,ij分别为给定分别为给定yj类的训练样本在属性类的训练样本在属性Ai上的均值和标准上的均值和标准差差 2023/1/949数据挖掘：概念与技术第49页，共134页，编辑于2022年，星期五朴素贝叶斯分类朴素贝叶斯分类n朴素贝叶斯分类器所需要的信息朴素贝叶斯分类器所需要的信息n计算每个类的先验概率计算每个类的先验概率P(yj)P(yj)=nj/n

40、其中其中,nj是是yi类的训练样本数类的训练样本数,而而n是训练样本总数是训练样本总数 n对于离散属性对于离散属性Ai，设的不同值为，设的不同值为ai1,ai2,ail，n对于每个类对于每个类yj，计算后验概率，计算后验概率P(aik|yj),1 k lP(aik|yj)=nikj/nj其中其中nikj 是在属性是在属性Ai上具有值上具有值aik 的的yj类的训练样本数类的训练样本数,而而nj是是yj类的训类的训练样本数练样本数 n对于连续属性对于连续属性Ai 和每个类和每个类yj，计算，计算yj类样本的均值类样本的均值 ij,标准差标准差 ij2023/1/950数据挖掘：概念与技术第50页

41、，共134页，编辑于2022年，星期五贝叶斯分类器贝叶斯分类器:例例n例例:P(Yes)=3/10P(No)=7/10P(有房=是|No)=3/7P(有房=否|No)=4/7P(有房=是|Yes)=0P(有房=否|Yes)=1P(婚姻状况=单身|No)=2/7P(婚姻状况=离婚|No)=1/7P(婚姻状况=已婚|No)=4/7P(婚姻状况=单身|Yes)=2/3P(婚姻状况=离婚|Yes)=1/3P(婚姻状况=已婚|Yes)=0年收入：类=No：样本均值=110 样本方差=2975类=Yes：样本均值=90 样本方差=25Tid有房婚姻状况年收入拖欠贷款12345678910是否否是否否是否否

42、否单身已婚单身已婚离婚已婚离婚单身已婚单身125K100K70K120K95K60K220K85K75K90KNoNoNoNoYesNoNoYesNoYes2023/1/951数据挖掘：概念与技术第51页，共134页，编辑于2022年，星期五贝叶斯分类器贝叶斯分类器:例例(续续)nX=（有房（有房=否，婚姻状况否，婚姻状况=已婚，年收入已婚，年收入=$120K）n计算计算P(X|No)和和P(X|Yes)P(X|No)=P(有房有房=否否|No)P(婚姻状况婚姻状况=已婚已婚|No)P(年收入年收入=$120K|No)=4/7 4/7 0.0072=0.0024 P(X|Yes)=P(有房有房

43、=否否|Yes)P(婚姻状况婚姻状况=已婚已婚|Yes)P(年收入年收入=$120K|Yes)=1 0 1.2 10 9=0 n计算计算P(X|No)P(No)和和P(X|Yes)P(Yes)P(X|No)P(No)=0.0024 0.7=0.00168P(X|Yes)P(Yes)=0 0.3=0n因为因为P(X|No)P(No)P(X|Yes)P(Yes),所以所以X分类为分类为No 2023/1/952数据挖掘：概念与技术第52页，共134页，编辑于2022年，星期五贝叶斯分类器贝叶斯分类器n问题问题n如果诸条件概率如果诸条件概率P(Xi=xi|Y=yj)中的一个为中的一个为0，则它们的乘

44、积（计算，则它们的乘积（计算P(X|Y=yj)的表达式）为的表达式）为0n很可能每个很可能每个P(X|Y=yj)都为都为0n解决方法解决方法n使用使用Laplace 估计估计:原估计原估计:P(Xi=xi|Y=yj)=nij/nj2023/1/953数据挖掘：概念与技术第53页，共134页，编辑于2022年，星期五贝叶斯分类器的特点贝叶斯分类器的特点n对孤立的噪声点的鲁棒性对孤立的噪声点的鲁棒性n个别点对概率估计的影响很小个别点对概率估计的影响很小n容易处理缺失值容易处理缺失值n在估计概率时忽略缺失值的训练实例在估计概率时忽略缺失值的训练实例n对不相关属性的鲁棒性对不相关属性的鲁棒性n各类在不

45、相关属性上具有类似分布各类在不相关属性上具有类似分布n类条件独立假设可能不成立类条件独立假设可能不成立 n使用其他技术，如贝叶斯信念网络（使用其他技术，如贝叶斯信念网络（Bayesian Belief Networks，BBN）2023/1/954数据挖掘：概念与技术第54页，共134页，编辑于2022年，星期五贝叶斯信念网络贝叶斯信念网络n贝叶斯信念网络贝叶斯信念网络(Bayesian belief network)允许在变量的子集间定义类条允许在变量的子集间定义类条件独立性件独立性 n因果关系图模型因果关系图模型 n表示变量之间的依赖表示变量之间的依赖n给出联合概率分布的说明给出联合概率分

46、布的说明n图示图示n节点节点:随机变量随机变量n边边:依赖依赖nX,Y 是是Z的父节点的父节点/前驱前驱,并且并且Y 是是P的父节点的父节点/前驱前驱nZ 和和P之间没有依赖关系之间没有依赖关系n图中没有环图中没有环XYZP2023/1/955数据挖掘：概念与技术第55页，共134页，编辑于2022年，星期五贝叶斯信念网络贝叶斯信念网络:例例n变量变量LungCance(LC)值的条件概率表值的条件概率表(CPT),给出其双亲结点给出其双亲结点FamilyHistory和和Smoke的每个可能值的组合的条件概率的每个可能值的组合的条件概率2023/1/956数据挖掘：概念与技术第56页，共13

47、4页，编辑于2022年，星期五贝叶斯信念网络贝叶斯信念网络:例例(续续)n给出了给出了LungCancer的的CPT.对于其双亲值的每个可能组合对于其双亲值的每个可能组合,表中给出了表中给出了LungCancer的每个值的条件概率的每个值的条件概率.例如例如,由左上角和右下角由左上角和右下角,我们分别看我们分别看到到 P(LungCancer=“yes”|FamilyHistory=“yes”,Smoker=“yes”)=0.8 P(LungCancer=“no”|FamilyHistory=“no”,Smoker=“no”)=0.9 n对应于属性或变量对应于属性或变量Z1,Zn的任意元组的任

48、意元组(z1,zn)的联合概率由下式计算的联合概率由下式计算其中其中,P(zi|parents(zi)的值对应于的值对应于Zi的的CPT中的表目中的表目2023/1/957数据挖掘：概念与技术第57页，共134页，编辑于2022年，星期五训练贝叶斯信念网络训练贝叶斯信念网络n若干情况若干情况n给定网络结构和所有可观测变量给定网络结构和所有可观测变量n只需要学习只需要学习CPTn网络结构已知网络结构已知,而某些变量是隐藏的而某些变量是隐藏的n使用梯度下降法或类似于神经网络的方法训练信念网络使用梯度下降法或类似于神经网络的方法训练信念网络n网络结构未知网络结构未知,所有的变量可以观测所有的变量可以

49、观测n搜索模型空间搜索模型空间,构造网络拓扑结构构造网络拓扑结构n网络结构未知网络结构未知,所有变量是隐藏的所有变量是隐藏的n没有已知的好算法没有已知的好算法nD.Heckerman,Bayesian networks for data mining2023/1/958数据挖掘：概念与技术第58页，共134页，编辑于2022年，星期五训练贝叶斯信念网络训练贝叶斯信念网络n梯度下降法梯度下降法n设设S是是s个训练样本个训练样本X1,X2,.,Xs的集合的集合,wijk是具有双亲是具有双亲Ui=uik的变量的变量Y=yij的的CPT项项 nwijk可以看作权可以看作权,类似于神经网络中隐藏单元的权

50、类似于神经网络中隐藏单元的权.权的集合记作权的集合记作w n这些权被初始化为随机概率值这些权被初始化为随机概率值.n梯度下降策略采用贪心爬山法梯度下降策略采用贪心爬山法.在每次迭代中在每次迭代中,修改这些权修改这些权,并最终收并最终收敛到一个局部最优解敛到一个局部最优解 n基于基于w的每个可能设置都等可能的假定的每个可能设置都等可能的假定,该方法搜索能最好地对数据建模该方法搜索能最好地对数据建模wijk值值.目标是最大化目标是最大化 2023/1/959数据挖掘：概念与技术第59页，共134页，编辑于2022年，星期五训练贝叶斯信念网络训练贝叶斯信念网络:梯度下降法梯度下降法n给定网络结构和给