数据挖掘导论第5章分类其他技术课件.ppt_163文库

资源描述

1、数据挖掘导论数据挖掘导论Pang-ning Tan,Michael Stieinbach,and Vipin Kumar著著Pearson Education LTD.范明范明等译等译人民邮电出版社人民邮电出版社第第5章章分类分类:其他技术其他技术基于规则的分类基于规则的分类最近邻分类最近邻分类贝叶斯分类贝叶斯分类神经网络神经网络支持向量机支持向量机组合方法组合方法不平衡类问题不平衡类问题多类问题多类问题5.1 基于规则的分类器基于规则的分类器2022年8月3日星期三数据挖掘导论4基于规则的分类器基于规则的分类器n使用一组使用一组“ifthen”规则进行分类规则进行分类n规则规则:(Co

2、ndition)yn其中其中 n Condition 是属性测试的合取是属性测试的合取n y 是类标号是类标号n左部左部:规则的前件或前提规则的前件或前提n右部右部:规则的结论规则的结论n分类规则的例子分类规则的例子:n(Blood Type=Warm)(Lay Eggs=Yes)Birdsn(Taxable Income 鸟类鸟类n规则规则r3 覆盖覆盖“灰熊灰熊”=哺乳类哺乳类名称体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号鹰灰熊恒温恒温羽毛软毛否是否否是否是是否是？2022年8月3日星期三数据挖掘导论7规则的质量规则的质量 n用覆盖率和准确率度量用覆盖率和准确率度量n规则的覆盖率规则

3、的覆盖率（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 70K No 4 Yes Married 120K No 5 No D

4、ivorced 95K Yes 6 No Married 60K No 7 Yes Divorced 220K No 8 No Single 85K Yes 9No Married 75K No 10NoSingle90K Yes10 2022年8月3日星期三数据挖掘导论8如何用规则分类如何用规则分类n一组规则一组规则r1：（胎生：（胎生=否）否）（飞行动物（飞行动物=是）是）鸟类鸟类r2：（胎生：（胎生=否）否）（水生动物（水生动物=是）是）鱼类鱼类r3：（胎生：（胎生=是）是）（体温（体温=恒温）恒温）哺乳类哺乳类r4：（胎生：（胎生=否）否）（飞行动物（飞行动物=否）否）爬行类爬行类r5

5、：（水生动物：（水生动物=半）半）两栖类两栖类n待分类记录待分类记录n狐猴狐猴触发规则触发规则 r3,它分到它分到哺乳类哺乳类n海龟触发规则海龟触发规则r4和和 r5-冲突冲突n狗鲨未触发任何规则狗鲨未触发任何规则名称名称体温体温胎生胎生飞行动物飞行动物水生动物水生动物类类狐猴恒温是否否?海龟冷血否否半水生?狗鲨冷血是否是?2022年8月3日星期三数据挖掘导论9规则的分类器的特征规则的分类器的特征n互斥规则集互斥规则集n每个记录最多被一个规则覆盖每个记录最多被一个规则覆盖n如果规则都是相互独立的，分类器包含互斥规则如果规则都是相互独立的，分类器包含互斥规则n如果规则集不是互斥的如果规则集不是互

6、斥的n一个记录可能被多个规则触发一个记录可能被多个规则触发n如何处理如何处理?n 有序规则集有序规则集n基于规则的序基于规则的序 vs 基于类的序基于类的序n 无序规则集无序规则集使用投票策略使用投票策略2022年8月3日星期三数据挖掘导论10规则的分类器的特征规则的分类器的特征(续续)n穷举规则集穷举规则集n每个记录至少被一个规则覆盖每个记录至少被一个规则覆盖n如果规则集涵盖了属性值的所有可能组合，则规则集具有穷举覆盖如果规则集涵盖了属性值的所有可能组合，则规则集具有穷举覆盖n如果规则集不是穷举的如果规则集不是穷举的n一个记录可能不被任何规则触发一个记录可能不被任何规则触发n如何处理如何处

7、理?n 使用缺省类使用缺省类2022年8月3日星期三数据挖掘导论11有序规则集有序规则集n根据规则优先权将规则排序定秩（根据规则优先权将规则排序定秩（rank）n有序规则集又成决策表（有序规则集又成决策表（decision list）n对记录进行分类时对记录进行分类时n由被触发的，具有最高秩的规则确定记录的类标号由被触发的，具有最高秩的规则确定记录的类标号n如果没有规则被触发，则指派到缺省类如果没有规则被触发，则指派到缺省类r1：（胎生：（胎生=否）否）（飞行动物（飞行动物=是）是）鸟类鸟类r2：（胎生：（胎生=否）否）（水生动物（水生动物=是）是）鱼类鱼类r3：（胎生：（胎生=是）是）（体温

8、（体温=恒温）恒温）哺乳类哺乳类r4：（胎生：（胎生=否）否）（飞行动物（飞行动物=否）否）爬行类爬行类r5：（水生动物：（水生动物=半）半）两栖类两栖类名称名称体温体温胎生胎生飞行动物飞行动物水生动物水生动物类类海龟冷血否否半水生?2022年8月3日星期三数据挖掘导论12规则定序方案规则定序方案n基于规则的序基于规则的序n根据规则的质量排序根据规则的质量排序n基于类的序基于类的序n属于同一类的规则放在一起属于同一类的规则放在一起n基于类信息（如类的分布、重要性）对每类规则排序基于类信息（如类的分布、重要性）对每类规则排序基于规则的排序基于规则的排序（表皮覆盖（表皮覆盖=羽毛羽毛,飞行动物飞行

9、动物=是）是）鸟类鸟类（体温（体温=恒温恒温,胎生胎生=是）是）哺乳类哺乳类（体温（体温=恒温恒温,胎生胎生=否）否）鸟类鸟类（水生动物（水生动物=半）半）两栖类两栖类（表皮覆盖（表皮覆盖=鳞片鳞片,水生动物水生动物=否）否）爬行类爬行类（表皮覆盖（表皮覆盖=鳞片鳞片,水生动物水生动物=是）是）鱼类鱼类（表皮覆盖（表皮覆盖=无）无）两栖类两栖类基于类的排序基于类的排序（表皮覆盖（表皮覆盖=羽毛羽毛,飞行动物飞行动物=是）是）鸟类鸟类（体温（体温=恒温恒温,胎生胎生=否）否）鸟类鸟类（体温（体温=恒温恒温,胎生胎生=是）是）哺乳类哺乳类（水生动物（水生动物=半）半）两栖类两栖类（表皮覆盖（表皮

10、覆盖=无）无）=两栖类两栖类（表皮覆盖（表皮覆盖=鳞片鳞片,水生动物水生动物=否）否）爬行类爬行类（表皮覆盖（表皮覆盖=鳞片鳞片,水生动物水生动物=是）是）鱼类鱼类 2022年8月3日星期三数据挖掘导论13如何建立基于规则的分类器如何建立基于规则的分类器n直接方法直接方法:n直接由数据提取规则直接由数据提取规则n例如例如:RIPPER,CN2,Holtes 1Rn间接方法间接方法:n由其他分类模型提取规则由其他分类模型提取规则(例如，从决策树、神经网络等例如，从决策树、神经网络等).n例如例如:C4.5rules2022年8月3日星期三数据挖掘导论14直接方法直接方法:顺序覆盖顺序覆盖n基本思

11、想基本思想n依次对每个类建立一个或多个规则依次对每个类建立一个或多个规则n对第对第i类建立规则类建立规则n第第i类记录为正例，其余为负例类记录为正例，其余为负例n建立一个第建立一个第i类的规则类的规则r，尽可能地覆盖正例，而不覆盖负例，尽可能地覆盖正例，而不覆盖负例n删除删除r覆盖的所有记录，在剩余数据集上学习下一个规则，直到覆盖的所有记录，在剩余数据集上学习下一个规则，直到所有第所有第i类记录都被删除类记录都被删除2022年8月3日星期三数据挖掘导论15直接方法直接方法:顺序覆盖顺序覆盖n顺序覆盖（顺序覆盖（sequential covering）算法）算法 1：令：令E是训练记录，是训练记

12、录，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尾部尾部 2022年8月3日星期三数据挖掘导论16顺序覆盖顺序覆盖:例例(a)

13、Original data(b)Step 1(c)Step 2(c)Step 32022年8月3日星期三数据挖掘导论17删除实例删除实例n为什么要删除实例为什么要删除实例?n否则否则,下一个规则将与前面的下一个规则将与前面的规则相同规则相同n为什么删除正实例为什么删除正实例?n确保下一个规则不同确保下一个规则不同n为什么删除负实例为什么删除负实例?n防止低估规则的准确率防止低估规则的准确率n比较图中的规则比较图中的规则 R2 和和 R32022年8月3日星期三数据挖掘导论18Learn-One-Rulen规则增长规则增长n实例删除实例删除n规则评估规则评估n停止准则停止准则n规则剪枝规则剪枝2

14、022年8月3日星期三数据挖掘导论19规则增长规则增长n两种策略两种策略n一般到特殊一般到特殊n从初始规则从初始规则r:y开始开始n反复加入合取项，得到更特殊的规则，直到不能再加入反复加入合取项，得到更特殊的规则，直到不能再加入n 特殊到一般特殊到一般n随机地选择一个正例作为初始规则随机地选择一个正例作为初始规则n反复删除合取项，得到更一般的规则，直到不能再删除反复删除合取项，得到更一般的规则，直到不能再删除n问题问题n加入加入/删除合取项有多种选择，如何选择？删除合取项有多种选择，如何选择？n何时停止加入何时停止加入/删除合取项？删除合取项？需要评估标准需要评估标准2022年8月3日星期三数

15、据挖掘导论20规则增长规则增长:例例n一般到特殊一般到特殊体温=恒温，表皮覆盖=毛发，胎生=是，水生动物=否，飞行动物=否，有腿=是，冬眠=否=哺乳类表皮覆盖=毛发，胎生=是，水生动物=否，飞行动物=否，有腿=是，冬眠=否=哺乳类体温=恒温，表皮覆盖=毛发，胎生=是，水生动物=否，飞行动物=否，有腿=是=哺乳类=哺乳类表皮覆盖=毛发=哺乳类体温=恒温=哺乳类有腿=否=哺乳类体温=恒温，有腿=是=哺乳类体温=恒温，胎生=是=哺乳类n 特殊到一般特殊到一般2022年8月3日星期三数据挖掘导论21规则评估规则评估n常用的度量常用的度量n准确率准确率n似然比似然比nLaplacenM-estimate

16、nFOIL信息增益信息增益 2022年8月3日星期三数据挖掘导论22规则评估规则评估(续续)n准确率准确率nAccuracynn:被规则覆盖的实例数被规则覆盖的实例数nnc:被规则正确分类的实例数被规则正确分类的实例数n问题：准确率高的规则可能覆盖率太低问题：准确率高的规则可能覆盖率太低n似然比似然比（越高越好）（越高越好）nk是类的个数是类的个数nfi是被规则覆盖的类是被规则覆盖的类i的样本的观测频度的样本的观测频度nei是规则作随机猜测的期望频度是规则作随机猜测的期望频度nnckiiii)/e(ffR1log22022年8月3日星期三数据挖掘导论23规则评估规则评估:例例n例例:60个正例

17、和个正例和100个反例个反例规则规则r1：覆盖：覆盖50个正例和个正例和5个反例（个反例（acc=90.9%）规则规则r2：覆盖：覆盖2个正例和个正例和0个反例个反例（acc=100%）n使用准确率使用准确率,r2好好n使用似然比使用似然比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 l

18、og2(5/34.375)=99.9 nR(r2)=2 2 log2(2/0.75)+0 log2(0/1.25)=5.66 nr1比比r2好好 2022年8月3日星期三数据挖掘导论24规则评估规则评估(续续)n考虑规则覆盖率的评估度量考虑规则覆盖率的评估度量 nn是规则覆盖的样例数，是规则覆盖的样例数，f+是规则覆盖的正例数，是规则覆盖的正例数，k是类的总数，是类的总数，p+是正类的先验概率是正类的先验概率 n当规则的覆盖率很高时，两个度量都渐近地趋向于规则的准确率当规则的覆盖率很高时，两个度量都渐近地趋向于规则的准确率f+/n n继续前例继续前例nr1的的Laplace度量为度量为51/5

19、7=89.47%，很接近它的准确率，很接近它的准确率nr2的的Laplace度量（度量（75%）比它的准确率小很多）比它的准确率小很多 knfLaplace1-fkpM estimatenk2022年8月3日星期三数据挖掘导论25规则评估规则评估(续续)n考虑规则的支持度计数的评估度量考虑规则的支持度计数的评估度量n规则的支持度计数对应于它所覆盖的正例数规则的支持度计数对应于它所覆盖的正例数 nFOIL信息增益（信息增益（First Order Inductive Leaner information gain）n设规则设规则r:A+覆盖覆盖p0个正例和个正例和n0个反例个反例;n规则规则r:

20、A B+覆盖覆盖p1个正例和个正例和n1个反例个反例.扩展后规则的扩展后规则的FOIL信息信息增益定义为增益定义为 n该度量与该度量与p1和和p1/(p1+n1)成正比，所以它更倾向于选择那些高支持度成正比，所以它更倾向于选择那些高支持度计数和高准确率的规则计数和高准确率的规则 n继续前例继续前例nr1和和r2的的FOIL信息增益分别为信息增益分别为43.12和和2，因此规则，因此规则r1比比r2好好 000211121loglognppnpppnFOILinfGai2022年8月3日星期三数据挖掘导论26停止条件与规则剪枝停止条件与规则剪枝n停止条件停止条件n计算增益计算增益n如果增益不显著

21、如果增益不显著,则丢弃新规则则丢弃新规则n规则剪枝规则剪枝n类似于决策树后剪枝类似于决策树后剪枝n降低错误剪枝降低错误剪枝:n 删除规则中的合取项删除规则中的合取项n 比较剪枝前后的错误率比较剪枝前后的错误率 n 如果降低了错误率如果降低了错误率,则剪掉该合取项则剪掉该合取项2022年8月3日星期三数据挖掘导论27直接方法直接方法:RIPPERn对于对于2类问题类问题,选定一个类为正类，另一个为负类选定一个类为正类，另一个为负类n从正类学习规则从正类学习规则n负类时缺省类负类时缺省类n多类问题多类问题n按类的大小（属于特定类的实例所占的比例）对诸类排序按类的大小（属于特定类的实例所占的比例）对

22、诸类排序n从最小的类开始学习规则，其余类都看做负类从最小的类开始学习规则，其余类都看做负类n对次小类学习规则，如此下去对次小类学习规则，如此下去2022年8月3日星期三数据挖掘导论28直接方法直接方法:RIPPER(续续)n规则增长规则增长:n由空规则开始由空规则开始n只要能够提高只要能够提高FOIL信息增益就增加一个合取项信息增益就增加一个合取项n当规则不再覆盖负实例时就停止当规则不再覆盖负实例时就停止n剪枝剪枝n剪枝度量剪枝度量:v=(p n)/(p+n)n p:验证集中被规则覆盖的正实例数验证集中被规则覆盖的正实例数n n:验证集中被规则覆盖的负实例数验证集中被规则覆盖的负实例数n剪枝方

23、法剪枝方法:n如果剪掉合取项可以提高如果剪掉合取项可以提高v就剪就剪2022年8月3日星期三数据挖掘导论29直接方法直接方法:RIPPER(续续)n建立规则集建立规则集:n使用顺序覆盖算使用顺序覆盖算n找出覆盖当前正实例的最佳规则找出覆盖当前正实例的最佳规则n删除被规则覆盖的所有正实例和负实例删除被规则覆盖的所有正实例和负实例n当一个规则加入规则集时，计算新的描述长度当一个规则加入规则集时，计算新的描述长度n当新的描述长度比已经得到的描述长度多当新的描述长度比已经得到的描述长度多d位时，就停止增加新位时，就停止增加新规则规则2022年8月3日星期三数据挖掘导论30直接方法直接方法:RIPPER

24、(续续)n优化规则集优化规则集:n对规则集对规则集R中的每个规则中的每个规则 rn考虑考虑2个替换的规则个替换的规则:n替换规则替换规则(r*):重新增长新规则重新增长新规则n编辑的规则编辑的规则(r):把一个新的合取项增加到规则把一个新的合取项增加到规则 r n比较替换前后的规则集比较替换前后的规则集 n选择最小化选择最小化MDL的规则集的规则集n对剩下的正实例，重复规则产生和优化对剩下的正实例，重复规则产生和优化2022年8月3日星期三数据挖掘导论31规则提取的间接方法规则提取的间接方法n决策树从根结点到叶结点的每一条路径都可以表示为一个分类规则决策树从根结点到叶结点的每一条路径都可以表示

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

26、3日星期三数据挖掘导论33间接方法间接方法:C4.5rulesn规则定序规则定序n不是对规则定序，而是对规则的子集定序不是对规则定序，而是对规则的子集定序(class ordering)n每个规则子集是一组具有相同规则后件每个规则子集是一组具有相同规则后件(class)的规则的规则n计算每个子集的描述长度计算每个子集的描述长度n描述长度描述长度=L(error)+g L(model)ng 是参数，考虑规则集中冗余属性是参数，考虑规则集中冗余属性(缺省值缺省值g=0.5)2022年8月3日星期三数据挖掘导论34C4.5 vs C4.5rules vs RIPPERC4.5rules:（胎生（胎生

27、=否，飞行动物否，飞行动物=是）是）=鸟类鸟类（胎生（胎生=否，水生动物否，水生动物=是）是）=鱼类鱼类（胎生（胎生=是）是）=哺乳类哺乳类（胎生（胎生=否，飞行动物否，飞行动物=否，水生动物否，水生动物=否）否）=爬行类爬行类（）（）=两栖类两栖类胎生胎生水生水生?飞行飞行?哺乳类哺乳类鱼类鱼类两栖类两栖类鸟类鸟类爬行类爬行类YesNoYesSometimesNoYesNo2022年8月3日星期三数据挖掘导论35基于规则的分类器的特征基于规则的分类器的特征 n表达能力与决策树一样高表达能力与决策树一样高n容易解释容易解释n容易产生容易产生n能够快速对新实例分类能够快速对新实例分类n性能可与

28、决策树相媲美性能可与决策树相媲美5.2 最近邻分类器最近邻分类器 2022年8月3日星期三数据挖掘导论37急切学习急切学习 vs 惰性学习惰性学习n急切学习（急切学习（Eager Learner）n两步过程两步过程:(1)归纳归纳(2)演绎演绎n惰性学习（惰性学习（lazy learner）n把训练数据建模过程推迟到需要对样本分类时把训练数据建模过程推迟到需要对样本分类时n例子例子nRote-learner（死记硬背）（死记硬背）n记住所有的训练数据，仅当记录的属性值与一个训练记录完全记住所有的训练数据，仅当记录的属性值与一个训练记录完全匹配才对它分类匹配才对它分类n最近邻（最近邻（Neare

29、st neighbor）n使用使用“最近最近”的的 k 个点个点(最近邻最近邻)进行分类进行分类2022年8月3日星期三数据挖掘导论38最近邻分类器最近邻分类器n基本思想基本思想:nIf it walks like a duck,quacks like a duck,then its probably a duck训练记录训练记录待分类记录待分类记录计算距离计算距离选择选择k 个个“最近最近”的记录的记录2022年8月3日星期三数据挖掘导论39最近邻分类器最近邻分类器 n要求要求n存放训练记录存放训练记录n计算记录间距离的度量计算记录间距离的度量nk值值,最近邻数最近邻数n对未知记录分类对未知

30、记录分类:n计算域各训练记录的距离计算域各训练记录的距离n找出找出 k 个最近邻个最近邻 n使用最近邻的类标号决定未知记使用最近邻的类标号决定未知记录的类标号录的类标号(例如例如,多数表决多数表决)2022年8月3日星期三数据挖掘导论40最近邻定义最近邻定义XXX(a)1-nearest neighbor(b)2-nearest neighbor(c)3-nearest neighbor 记录记录x的的k-最近邻是与最近邻是与x之间距离最小的之间距离最小的k个训练数据点个训练数据点2022年8月3日星期三数据挖掘导论411 nearest-neighborVoronoi Diagram2022

31、年8月3日星期三数据挖掘导论42 k-最近邻分类算法最近邻分类算法 nk-最近邻分类算法最近邻分类算法1：令：令k是最近邻数目，是最近邻数目，D是训练样例的集合是训练样例的集合2：for 每个测试样例每个测试样例 z=(x,y)do3：计算计算z和每个样例和每个样例(x,y)D之间的距离之间的距离d(x,x)4：选择离选择离z最近的最近的k个训练样例的集合个训练样例的集合Dz D5：6：end for n距离加权表决距离加权表决(,)argmax()iizivyDyI vy x(,)argmax()iiziivyDywI vy x2022年8月3日星期三数据挖掘导论43k-最近邻最近邻nk值的

32、选择值的选择:n如果如果 k 太小太小,则对噪声点敏感则对噪声点敏感n如果如果 k 太大太大,邻域可能包含很邻域可能包含很多其他类的点多其他类的点n定标问题（规范化）定标问题（规范化）n属性可能需要规范化，防止距属性可能需要规范化，防止距离度量被具有很大值域的属性离度量被具有很大值域的属性所左右所左右2022年8月3日星期三数据挖掘导论44k-NN的特点的特点nk-NN的特点的特点n是一种是一种基于实例的学习基于实例的学习 n需要一个邻近性度量来确定实例间的相似性或距离需要一个邻近性度量来确定实例间的相似性或距离 n不需要建立模型，但分类一个测试样例开销很大不需要建立模型，但分类一个测试

33、样例开销很大n需要计算域所有训练实例之间的距离需要计算域所有训练实例之间的距离 n基于局部信息进行预测，对噪声非常敏感基于局部信息进行预测，对噪声非常敏感 n最近邻分类器可以生成任意形状的决策边界最近邻分类器可以生成任意形状的决策边界 n决策树和基于规则的分类器通常是直线决策边界决策树和基于规则的分类器通常是直线决策边界 n需要需要适当的邻近性度量和数据预处理适当的邻近性度量和数据预处理 n防止防止邻近性度量被某个属性左右邻近性度量被某个属性左右5.3 贝叶斯分类器贝叶斯分类器 2022年8月3日星期三数据挖掘导论46贝叶斯定理贝叶斯定理n每个记录用一个每个记录用一个d维特征向量维特征向量X=

34、(x1,x2,xd)表示表示n假定有假定有k个类个类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)最大的类最大的类yj)()()|()|(XPjyPjyXPXjyP2022年8月3日星期三数据挖掘导论47朴素贝叶斯分类朴素贝叶斯分类n朴素贝叶斯分类朴素贝叶斯分类(Nave Bayes Clas

35、sifier)工作原理工作原理n给定一个未知的数据样本给定一个未知的数据样本X,分类法将预测分类法将预测X属于具有最高后验概率的类属于具有最高后验概率的类.即即,未知的样本分配给类未知的样本分配给类yj,当且仅当当且仅当根据贝叶斯定理根据贝叶斯定理,我们有我们有n由于由于P(X)对于所有类为常数对于所有类为常数,只需要最大化只需要最大化P(X|yj)P(yj)即可即可.jikiyPyPij,1),|()|(XX)()()|()|(XXXPyPyPyPjjj2022年8月3日星期三数据挖掘导论48朴素贝叶斯分类朴素贝叶斯分类(续续)n估计估计P(yj)n类类yj的先验概率可以用下式估计的先验概率

37、是分类属性是分类属性,则则 P(xi|yj)=nij/nj其中其中nij是在属性是在属性Ai上具有值上具有值xi的的yj类的训练样本数类的训练样本数,而而nj是是yj类的训练类的训练样本数样本数 n设第设第i个属性个属性Ai是连续值属性是连续值属性n把把Ai离散化离散化n假定假定Ai服从高斯分布服从高斯分布 n其中其中,ij,ij分别为给定分别为给定yj类的训练样本在属性类的训练样本在属性Ai上的均值和标准上的均值和标准差差 222)(21)|(ijijixijjieyxP2022年8月3日星期三数据挖掘导论50朴素贝叶斯分类朴素贝叶斯分类n朴素贝叶斯分类器所需要的信息朴素贝叶斯分类器所需要的

38、信息n计算每个类的先验概率计算每个类的先验概率P(yj)P(yj)=nj/n 其中其中,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类样本的均值类样本的

40、入拖欠贷款拖欠贷款12345678910是是否否否否是是否否否否是是否否否否否否单身单身已婚已婚单身单身已婚已婚离婚离婚已婚已婚离婚离婚单身单身已婚已婚单身单身125K100K70K120K95K60K220K85K75K90KNoNoNoNoYesNoNoYesNoYes2022年8月3日星期三数据挖掘导论52贝叶斯分类器贝叶斯分类器:例例(续续)nX=（有房（有房=否，婚姻状况否，婚姻状况=已婚，年收入已婚，年收入=$120K）n计算计算P(X|No)和和P(X|Yes)P(X|No)=P(有房有房=否否|No)P(婚姻状况婚姻状况=已婚已婚|No)P(年收入年收入=$120K|No)=4

42、为中的一个为0，则它们的乘积（计算，则它们的乘积（计算P(X|Y=yj)的表达式）为的表达式）为0n很可能每个很可能每个P(X|Y=yj)都为都为0n解决方法解决方法n使用使用Laplace 估计估计:原估计原估计:P(Xi=xi|Y=yj)=nij/njknnyYxXPjijiii1)|(:Laplace2022年8月3日星期三数据挖掘导论54贝叶斯分类器的特点贝叶斯分类器的特点n对孤立的噪声点的鲁棒性对孤立的噪声点的鲁棒性n个别点对概率估计的影响很小个别点对概率估计的影响很小n容易处理缺失值容易处理缺失值n在估计概率时忽略缺失值的训练实例在估计概率时忽略缺失值的训练实例n对不相关属性的鲁棒

43、性对不相关属性的鲁棒性n各类在不相关属性上具有类似分布各类在不相关属性上具有类似分布n类条件独立假设可能不成立类条件独立假设可能不成立 n使用其他技术，如贝叶斯信念网络（使用其他技术，如贝叶斯信念网络（Bayesian Belief Networks，BBN）2022年8月3日星期三数据挖掘导论55贝叶斯信念网络贝叶斯信念网络n贝叶斯信念网络贝叶斯信念网络(Bayesian belief network)允许在变量的子集间定义类条允许在变量的子集间定义类条件独立性件独立性 n因果关系图模型因果关系图模型 n表示变量之间的依赖表示变量之间的依赖n给出联合概率分布的说明给出联合概率分布的说明n图示

44、图示n节点节点:随机变量随机变量n边边:依赖依赖nX,Y 是是Z的父节点的父节点/前驱前驱,并且并且Y 是是P的父节点的父节点/前驱前驱nZ 和和P之间没有依赖关系之间没有依赖关系n图中没有环图中没有环XYZP2022年8月3日星期三数据挖掘导论56贝叶斯信念网络贝叶斯信念网络:例例n变量变量LungCance(LC)值的条件概率表值的条件概率表(CPT),给出其双亲结点给出其双亲结点FamilyHistory和和Smoke的每个可能值的组合的条件概率的每个可能值的组合的条件概率2022年8月3日星期三数据挖掘导论57贝叶斯信念网络贝叶斯信念网络:例例(续续)n给出了给出了LungCancer

45、的的CPT.对于其双亲值的每个可能组合对于其双亲值的每个可能组合,表中给出了表中给出了LungCancer的每个值的条件概率的每个值的条件概率.例如例如,由左上角和右下角由左上角和右下角,我们分别看我们分别看到到 P(LungCancer=“yes”|FamilyHistory=“yes”,Smoker=“yes”)=0.8 P(LungCancer=“no”|FamilyHistory=“no”,Smoker=“no”)=0.9 n对应于属性或变量对应于属性或变量Z1,Zn的任意元组的任意元组(z1,zn)的联合概率由下式计算的联合概率由下式计算其中其中,P(zi|parents(zi)的值

46、对应于的值对应于Zi的的CPT中的表目中的表目ninZParentsiziPzzP11)(|(),.,(2022年8月3日星期三数据挖掘导论58训练贝叶斯信念网络训练贝叶斯信念网络n若干情况若干情况n给定网络结构和所有可观测变量给定网络结构和所有可观测变量n只需要学习只需要学习CPTn网络结构已知网络结构已知,而某些变量是隐藏的而某些变量是隐藏的n使用梯度下降法或类似于神经网络的方法训练信念网络使用梯度下降法或类似于神经网络的方法训练信念网络n网络结构未知网络结构未知,所有的变量可以观测所有的变量可以观测n搜索模型空间搜索模型空间,构造网络拓扑结构构造网络拓扑结构n网络结构未知网络结构未知,所

47、有变量是隐藏的所有变量是隐藏的n没有已知的好算法没有已知的好算法nD.Heckerman,Bayesian networks for data mining2022年8月3日星期三数据挖掘导论59训练贝叶斯信念网络训练贝叶斯信念网络n梯度下降法梯度下降法n设设S是是s个训练样本个训练样本X1,X2,.,Xs的集合的集合,wijk是具有双亲是具有双亲Ui=uik的变量的变量Y=yij的的CPT项项 nwijk可以看作权可以看作权,类似于神经网络中隐藏单元的权类似于神经网络中隐藏单元的权.权的集合记作权的集合记作w n这些权被初始化为随机概率值这些权被初始化为随机概率值.n梯度下降策略采用贪心爬山

48、法梯度下降策略采用贪心爬山法.在每次迭代中在每次迭代中,修改这些权修改这些权,并最终收并最终收敛到一个局部最优解敛到一个局部最优解 n基于基于w的每个可能设置都等可能的假定的每个可能设置都等可能的假定,该方法搜索能最好地对数据建模该方法搜索能最好地对数据建模wijk值值.目标是最大化目标是最大化 sddwwXPSp1)()(2022年8月3日星期三数据挖掘导论60训练贝叶斯信念网络训练贝叶斯信念网络:梯度下降法梯度下降法n给定网络结构和给定网络结构和wijk的初值的初值,该算法按以下步骤处理该算法按以下步骤处理 1.计算梯度：对每个计算梯度：对每个i,j,k，计算，计算 2.沿梯度方向前进一小

49、步沿梯度方向前进一小步:用下式更新权值用下式更新权值 l是表示步长的学习率是表示步长的学习率,设置为一个小常数设置为一个小常数 3.重新规格化权值：由于权值重新规格化权值：由于权值wijk是概率值是概率值,它们必须在它们必须在0.0和和1.0之间之间,并且并且对于所有的对于所有的i,k，必须有，必须有 sdijkdikiijiijkwwXuUyYPwSP1)|,()(lnijkwijkijkwSPlww)(ln)(1jijkw2022年8月3日星期三数据挖掘导论61BBN的特点的特点nBBN提供了一种用图形模型来捕获特定领域的先验知识的方法。网络还提供了一种用图形模型来捕获特定领域的先验知识的

50、方法。网络还可以用来对变量间的因果依赖关系进行编码可以用来对变量间的因果依赖关系进行编码n构造网络可能既费时又费力。然而，一旦网络结构确定下来，添加新变构造网络可能既费时又费力。然而，一旦网络结构确定下来，添加新变量就十分容易量就十分容易n贝叶斯网络很适合处理不完整的数据。对有属性遗漏的实例可以通过对贝叶斯网络很适合处理不完整的数据。对有属性遗漏的实例可以通过对该属性的所有可能取值的概率求和或求积分来加以处理该属性的所有可能取值的概率求和或求积分来加以处理n因为数据和先验知识以概率的方式结合起来了，所以该方法对模型的过因为数据和先验知识以概率的方式结合起来了，所以该方法对模型的过分拟合问题是分

展开阅读全文