第08章分类：其他技术

1、数据仓库与数据挖掘数据仓库与数据挖掘第第8 8章章 分类：其他技术分类：其他技术n基于规则的分类器基于规则的分类器n最邻近分类器最邻近分类器n贝叶斯分类器贝叶斯分类器n人工神经网络人工神经网络n支持向量机支持向量机n组合方法组合方法n不平衡类问题不平衡类问题n多类问题多类问题2使用一组使用一组 “ifthen” 规则来分类记录规则来分类记录规则规则: (Condition) yn其中其中 n Condition 是属性测试的合取是属性测试的合取 n y 是类标记是类标记nLHS: 规则前件或前提规则前件或前提nRHS: 规则后件规则后件n分类规则的例子分类规则的例子:n (Blood Type

2、=Warm) (Lay Eggs=Yes) Birdsn (Taxable Income Bird规则规则 R3 覆盖覆盖 grizzly bear = MammalNameBlood TypeGive BirthCan FlyLive in WaterClasshawkwarmnoyesno?grizzly bearwarmyesnono?6覆盖率覆盖率:n满足规则前件的记录的比例满足规则前件的记录的比例准确率准确率:n满足规则前件和后件的记录的比例满足规则前件和后件的记录的比例(Status=Single) No Coverage = 40% Accuracy = 50%7R1: (Giv

3、e 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 = no) ReptilesR5: (Live in Water = sometimes) Amphibians lemur 触发规则触发规则 R3， 所以分类为所以分类为 mammal turtle 触发规则触发规则 R4 和和 R5 dogfish shark 没

4、有触发任何规则没有触发任何规则NameBlood TypeGive BirthCan FlyLive in WaterClasslemurwarmyesnono?turtlecoldnonosometimes?dogfish sharkcoldyesnoyes?8互斥规则互斥规则n如果规则彼此独立那么分类器中的规则是互斥的如果规则彼此独立那么分类器中的规则是互斥的n每个记录最多被一条规则覆盖每个记录最多被一条规则覆盖穷举规则穷举规则n如果规则覆盖所有可能的属性值组合如果规则覆盖所有可能的属性值组合， 则分类器中的规则是穷举的则分类器中的规则是穷举的n每个记录至少被一条规则覆盖每个记录至少被一条

5、规则覆盖9YESYESNONONONONONOYesNoMarriedSingle, Divorced 80KTaxable IncomeMarital StatusRefundClassification Rules(Refund=Yes) = No(Refund=No, Marital Status=Single,Divorced,Taxable Income No(Refund=No, Marital Status=Single,Divorced,Taxable Income80K) = Yes(Refund=No, Marital Status=Married) = No规则是互斥和穷

6、举的规则是互斥和穷举的规则集包含信息与树一致规则集包含信息与树一致10YESYESNONONONONONOYesNoMarriedSingle, Divorced 80KTaxable IncomeMarital StatusRefundTid Refund Marital Status Taxable Income Cheat 1 Yes Single 125K No 2 No Married 100K No 3 No Single 70K No 4 Yes Married 120K No 5 No Divorced 95K Yes 6 No Married 60K No 7 Yes Div

7、orced 220K No 8 No Single 85K Yes 9 No Married 75K No 10 No Single 90K Yes 10 初始规则初始规则: (Refund=No) (Status=Married) No简化规则简化规则: (Status=Married) No11规则不再互斥规则不再互斥n一个记录可能会触发多于一条规则一个记录可能会触发多于一条规则 n如何解决如何解决?n 有序规则有序规则n 无序规则无序规则 使用投票模式使用投票模式规则不再穷举规则不再穷举n一个记录可能不再触发任何规则一个记录可能不再触发任何规则n解决办法解决办法?n 使用缺省类使用缺省类

8、12规则按照优先级排列规则按照优先级排列n一个有序的规则集也称为决策表一个有序的规则集也称为决策表当一个测试记录交给分类器时当一个测试记录交给分类器时 n由它所触发的最高优先级的规则来分类由它所触发的最高优先级的规则来分类n如果没有触发任何规则如果没有触发任何规则， 则分配到缺省类则分配到缺省类R1: (Give Birth = no) (Can Fly = yes) BirdsR2: (Give Birth = no) (Live in Water = yes) FishesR3: (Give Birth = yes) (Blood Type = warm) MammalsR4: (Give

9、 Birth = no) (Can Fly = no) ReptilesR5: (Live in Water = sometimes) Amphibians NameBlood TypeGive BirthCan FlyLive in WaterClassturtlecoldnonosometimes?13基于规则的排序基于规则的排序n每个规则根据规则质量排序每个规则根据规则质量排序基于类的排序基于类的排序n属于同一个类的规则一起出现属于同一个类的规则一起出现14直接方法直接方法: n 直接从数据中抽取规则直接从数据中抽取规则n 如如.: RIPPER， CN2， Holtes 1R间接方法间

10、接方法:n 从其它的分类模型中抽取规则从其它的分类模型中抽取规则 (如决策树如决策树， 神经网络等神经网络等).n 如如: C4.5rules15n从空规则集开始从空规则集开始n使用使用一次学习一条规则一次学习一条规则的方法实现规则增长的方法实现规则增长n删除被规则覆盖的训练数据删除被规则覆盖的训练数据n重复步骤重复步骤 (2) 和和 (3) 直至遇到终止条件直至遇到终止条件16(ii) Step 117(iii) Step 2R1(iv) Step 3R1R218u规则增长规则增长u实例删除实例删除u规则评估规则评估u停止标准停止标准u规则剪枝规则剪枝19两种普遍策略两种普遍策略n从一般到特

11、殊从一般到特殊n从特殊到一般从特殊到一般 20为何要删除正例为何要删除正例?n确保下一条规则不同于前确保下一条规则不同于前n防止高估了规则的准确率防止高估了规则的准确率为何要删除反例为何要删除反例?n防止低估了规则的准确率防止低估了规则的准确率n比较图中规则比较图中规则 R2 和和 R321度量度量:nAccuracynLaplacenM-estimateknnc1knkpncn : 规则覆盖的实例数规则覆盖的实例数nc : 规则覆盖的正例数规则覆盖的正例数k : 类数目类数目p : 先验概率先验概率nnc22停止标准停止标准n计算收益计算收益n如果收益不显著如果收益不显著， 放弃新规则放弃新

12、规则规则剪枝规则剪枝n类似决策树的后剪枝类似决策树的后剪枝n降低错误剪枝降低错误剪枝: n 删除一个规则中的合取删除一个规则中的合取n 比较剪枝前后的验证集的错误率比较剪枝前后的验证集的错误率n 如果错误率得到改善如果错误率得到改善， 剪枝这个合取剪枝这个合取23u增长一个规则增长一个规则u从规则中删除实例从规则中删除实例u剪枝规则剪枝规则 (如果必要的话如果必要的话)u增加规则到当前规则集中增加规则到当前规则集中u重复重复24对于对于 2-class 问题问题， 选择其中一个为正类选择其中一个为正类， 另一个为反类另一个为反类n从正类中学习规则从正类中学习规则n反类为缺省类反类为缺省类对于对

13、于 multi-class 问题问题n根据根据类的频率类的频率对类进行排序对类进行排序 (实例属于某个特定类的比例实例属于某个特定类的比例)n从最小的类开始学习规则集从最小的类开始学习规则集， 其余类作为反类其余类作为反类n继续从下一个最小的类作为正类开始继续从下一个最小的类作为正类开始， 不断重复不断重复25增加一个规则增加一个规则:n从空规则开始从空规则开始n只要改善了只要改善了 FOIL 的信息增益的信息增益， 就增加合取就增加合取n当规则不再覆盖反例就停止增加合取当规则不再覆盖反例就停止增加合取n新规则根据其在新规则根据其在确认集确认集上的性能进行剪枝上的性能进行剪枝n剪枝度量剪枝度量

14、: v = (p-n)/(p+n)n p: 验证集中规则覆盖的正例数验证集中规则覆盖的正例数n n: 验证集中规则覆盖的负例数验证集中规则覆盖的负例数n剪枝方法剪枝方法: 删除使删除使v增加的任何增加的任何最后添加最后添加的条件序列的条件序列(合取合取)，26建立规则集建立规则集:n使用顺序覆盖算法使用顺序覆盖算法n 找出覆盖当前正例集的最佳规则找出覆盖当前正例集的最佳规则n 删除规则覆盖的正例和反例删除规则覆盖的正例和反例n每次一条规则加入规则集每次一条规则加入规则集， 计算新的描述长度计算新的描述长度n 当新规则描述长度比当新规则描述长度比最小描述长度（见最小描述长度（见P112）增加增加

15、 d 个比特位个比特位就停止增加新的规则就停止增加新的规则2728从未剪枝的决策树中抽取规则从未剪枝的决策树中抽取规则对每条规则对每条规则， r: A y， n考查可替换规则考查可替换规则 r: A y 其中其中 A 是从是从 A 中删除一个合取的结果中删除一个合取的结果n比较比较 r 与所有与所有 r 的悲观误差率的悲观误差率n如果如果 r 中存在某一规则有较低的中存在某一规则有较低的悲观误差率（悲观误差率（P111）则剪枝则剪枝n重复上述过程直至不再能改善整体错误率重复上述过程直至不再能改善整体错误率29排序规则：不对规则排序排序规则：不对规则排序， 对规则子集排序对规则子集排序 (类排序

16、类排序)n每个子集都是具有相同类的规则集合每个子集都是具有相同类的规则集合n计算每个子集的描述长度，进行升序排列。具有最小描述长度的类优计算每个子集的描述长度，进行升序排列。具有最小描述长度的类优先级最高。先级最高。n 描述长度描述长度 = L(error) + g*L(model)n L(error)是对误分类样例编码长度，是对误分类样例编码长度，L(model)是对模型编码长是对模型编码长度。度。g是调节参数是调节参数(default value = 0.5)，取决于模型中冗余属性，取决于模型中冗余属性的数量，冗余越多则的数量，冗余越多则g越小。越小。30NameGive BirthLay

17、 EggsCan FlyLive in WaterHave LegsClasshumanyesnononoyesmammalspythonnoyesnononoreptilessalmonnoyesnoyesnofisheswhaleyesnonoyesnomammalsfrognoyesnosometimes yesamphibianskomodonoyesnonoyesreptilesbatyesnoyesnoyesmammalspigeonnoyesyesnoyesbirdscatyesnononoyesmammalsleopard sharkyesnonoyesnofishesturt

18、lenoyesnosometimes yesreptilespenguinnoyesnosometimes yesbirdsporcupineyesnononoyesmammalseelnoyesnoyesnofishessalamandernoyesnosometimes yesamphibiansgila monsternoyesnonoyesreptilesplatypusnoyesnonoyesmammalsowlnoyesyesnoyesbirdsdolphinyesnonoyesnomammalseaglenoyesyesnoyesbirds31C4.5rules:(Give Bi

19、rth=No， Can Fly=Yes) Birds(Give Birth=No， Live in Water=Yes) Fishes(Give Birth=Yes) Mammals(Give Birth=No， Can Fly=No， Live in Water=No) Reptiles( ) AmphibiansGiveBirth?Live InWater?CanFly?MammalsFishesAmphibiansBirdsReptilesYesNoYesSometimesNoYesNoRIPPER:(Live in Water=Yes) Fishes(Have Legs=No) Rep

20、tiles(Give Birth=No， Can Fly=No， Live In Water=No) Reptiles(Can Fly=Yes，Give Birth=No) Birds() Mammals32u表达能力几乎等价于决策树表达能力几乎等价于决策树u生产更容易解释的描述性模型生产更容易解释的描述性模型u适宜处理类分布不平衡的数据集适宜处理类分布不平衡的数据集33n基于规则的分类器基于规则的分类器n最邻近分类器最邻近分类器n贝叶斯分类器贝叶斯分类器n人工神经网络人工神经网络n支持向量机支持向量机n组合方法组合方法n不平衡类问题不平衡类问题n多类问题多类问题34Basic idea:nI

21、f it walks like a duck， quacks like a duck， then its probably a duckTraining RecordsTest RecordCompute DistanceChoose k of the “nearest” records353637XXX(a) 1-nearest neighbor(b) 2-nearest neighbor(c) 3-nearest neighbor38Choosing the value of k:nIf k is too small， sensitive to noise pointsnIf k is t

22、oo large， neighborhood may include points from other classes3940第 41 页 k-最近邻最近邻(k-Nearest Neighbour， kNN)分类法是一种基于距分类法是一种基于距离的分类算法，它离的分类算法，它既既不需要事先建立分类模型不需要事先建立分类模型，也无需对也无需对分类分类模型进行评估，而仅利用有类别标号的样本集，直接对没有类模型进行评估，而仅利用有类别标号的样本集，直接对没有类别标号的数据对象别标号的数据对象Zu进行分类，即确定其类别标号。进行分类，即确定其类别标号。 假定样本集假定样本集S中每个数据点都有一个唯一

23、的类别标号，每个中每个数据点都有一个唯一的类别标号，每个类别标识类别标识Cj中都有多个数据对象。对于一个没有标识的数据点中都有多个数据对象。对于一个没有标识的数据点Zu，k-最近邻分类法遍历搜索样本集最近邻分类法遍历搜索样本集S，找出距离，找出距离Zu最近的最近的k个个样本点，即样本点，即k-最近邻集最近邻集N，并将其中多数样本的类别标号分配给，并将其中多数样本的类别标号分配给Zu。第 42 页第 43 页 例例 设某公司现有设某公司现有15名员工的基本信息名员工的基本信息，包括其，包括其个子为高个、中等、矮个子为高个、中等、矮个的分类标识。个的分类标识。 公司现刚招进一位名叫刘萍的新员工公司

24、现刚招进一位名叫刘萍的新员工Z1，令令k=5，试采用，试采用k-最近邻分类最近邻分类算法判断员工刘萍的个子属于哪一类算法判断员工刘萍的个子属于哪一类？ 第 44 页解：只有身高才是与个子高矮相关的属性，解：只有身高才是与个子高矮相关的属性，因此因此用用Xi表示第表示第i个员工的身高。个员工的身高。 首先从首先从X中选择中选择5个员工作为初始个员工作为初始k-最近邻集最近邻集N。不失一般性，取。不失一般性，取 N=X1=1.60，X2=2.00，X3=1.90，X4=1.88，X5=1.70(1) 对对S的的X6=1.85，身高，身高X2=2.00是是N中与身高中与身高Z1=1.62差距最大的员

25、工，且有差距最大的员工，且有d(Z1，X2)d(Z1，X6)，因此，在，因此，在N中用中用X6替换替换X2得到得到N=X1=1.60，X6=1.85，X3=1.90，X4=1.88，X5=1.70(2) 同理，用同理，用S中中X7=1.59替换替换N中身高距离中身高距离Z1=1.65最大的员工最大的员工X3=1.90，得到，得到N=X1=1.60，X6=1.85，X7=1.59，X4=1.88，X5=1.70 (3) 用用X8=1.70替换替换N中距离中距离Z1最大的员工最大的员工X6=1.85，得到，得到N=X1=1.60，X8=1.70，X7=1.59，X4=1.88，X5=1.70 (4

26、) 因为因为S中的中的X9=2.20和和X10=2.10，故根据算法，故根据算法，N不需要改变。不需要改变。第 45 页(5) 用用X11=1.8替换替换N中中X11=1.88得得N=X1=1.60，X8=1.70，X7=1.59，X11=1.80，X5=1.70； (6) 因为因为S中的中的X12=1.95，X13=1.90，X14=1.80，故，故N不需要改变。不需要改变。(7) 用用X15=1.75替换替换N中中X11=1.8得得N=X1=1.60，X8=1.70，X7=1.59，X15=1.75，X5=1.70； (8) 在第在第(7)步所得步所得N中，有中，有5个身高最接近个身高最接

27、近Z1=1.62的员工，且其的员工，且其X1=1.60，X8=1.70，X7=1.59， X5=1.70这这4个员工的类别都是个员工的类别都是“矮个矮个”，仅有，仅有X15=1.75的类别是的类别是“中等中等”；因此，新员工；因此，新员工Z1=刘萍的个子为矮个。刘萍的个子为矮个。 n基于规则的分类器基于规则的分类器n最邻近分类器最邻近分类器n贝叶斯分类器贝叶斯分类器n人工神经网络人工神经网络n支持向量机支持向量机n组合方法组合方法n不平衡类问题不平衡类问题n多类问题多类问题46解决分类问题的概率框架解决分类问题的概率框架联合概率：联合概率：P(A，C) = P(C|A)P(A) = P(A|C

28、)P(C)条件概率条件概率: 贝叶斯理论贝叶斯理论:)()()|()|(APCPCAPACP)(),()|()(),()|(CPCAPCAPAPCAPACP47给定给定: n病人患有脑膜炎的先验概率是病人患有脑膜炎的先验概率是 1/50，000 P(M)n病人患有颈部僵硬的先验概率是病人患有颈部僵硬的先验概率是 1/20 P(S)n患脑膜炎的人有患脑膜炎的人有50%的人会发生颈部僵硬的人会发生颈部僵硬 P(S|M) 如果病人患有颈部僵硬如果病人患有颈部僵硬， 那么他那么他/她患有脑膜炎的概率有多大她患有脑膜炎的概率有多大?如果缺课如果缺课5次以上的比率是次以上的比率是30%，补考率是，补考率是

29、20%，补考中的，补考中的60%都是缺课都是缺课5次以上，问：缺课次以上，问：缺课5次以上的学生补考的概率次以上的学生补考的概率是多少？是多少？0002.020/150000/15 .0)()()|()|(SPMPMSPSMP48每个属性和类标签作为随机变量每个属性和类标签作为随机变量给定一个记录属性给定一个记录属性 (A1， A2，An) n目标是预测类目标是预测类 Cn特别地特别地， 我们想找到使得我们想找到使得 P(C| A1， A2，An ) 最大化的最大化的 C 值值我们能直接从数据中预测我们能直接从数据中预测 P(C| A1， A2，An ) 吗吗?49方法方法:n使用贝叶斯理论计

30、算所有使用贝叶斯理论计算所有 C 值的后验概率值的后验概率 P(C | A1， A2， ， An)n选择选择 C 值值， 使最大化使最大化 P(C | A1， A2， ， An)n等价的等价的， 选择选择 C 值值， 使最大化使最大化 P(A1， A2， ， An|C) P(C)如何估算如何估算 P(A1， A2， ， An | C )?)()()|()|(212121nnnAAAPCPCAAAPAAACP50假设属性假设属性 Ai 是独立的是独立的， 给定类给定类Cj: nP(A1， A2， ， An |C) = P(A1| Cj) P(A2| Cj) P(An| Cj) n对于所有对于所有

31、Ai 和和 Cj可估算可估算 P(Ai| Cj) n如果如果 P(Cj) P(Ai| Cj) 是最大的，那么新的点分类为是最大的，那么新的点分类为 Cj 。51类类: P(C) = Nc/Nn如：如： P(No) = 7/10， P(Yes) = 3/10离散属性离散属性: P(Ai | Ck) = |Aik|/ Nc n其中其中， |Aik| 是属性是属性Ai 且属于类且属于类 Ck 的实例数的实例数n例如例如:P(Status=Married|No) = 4/7P(Refund=Yes|Yes)=0Tid Refund Marital Status Taxable Income Evade

32、 1 Yes Single 125K No 2 No Married 100K No 3 No Single 70K 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 9 No Married 75K No 10 No Single 90K Yes 10 categoricalcategoricalcontinuousclass52针对连续属性针对连续属性: n离散化离散化 区间至桶中区间至桶中 n 每个桶一个序数属性每个桶一

33、个序数属性n双向划分双向划分: (A v)n 选择两种分裂中的一种作为新的属性选择两种分裂中的一种作为新的属性n概率密度估算概率密度估算:n 假设属性有正态分布假设属性有正态分布n 使用数据估算分布参数使用数据估算分布参数 (如：均值和标准差如：均值和标准差)n 一旦概率分布已知，一旦概率分布已知， 可以用来估算条件概率可以用来估算条件概率 P(Ai|c)53正态分布正态分布:n每个对应一对每个对应一对 (Ai，ci) For (Income， Class=No):nIf Class=Non sample mean = 110n sample variance = 2975Tid Refund

34、 Marital Status Taxable Income Evade 1 Yes Single 125K No 2 No Married 100K No 3 No Single 70K 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 9 No Married 75K No 10 No Single 90K Yes 10 categoricalcategoricalcontinuousclass222)(221)|(iji

35、jiAijjiecAP0072. 0)54.54(21)|120()2975(2)110120(2eNoIncomeP5455P(Refund=Yes|No) = 3/7P(Refund=No|No) = 4/7P(Refund=Yes|Yes) = 0P(Refund=No|Yes) = 1P(Marital Status=Single|No) = 2/7P(Marital Status=Divorced|No)=1/7P(Marital Status=Married|No) = 4/7P(Marital Status=Single|Yes) = 2/7P(Marital Status=Di

36、vorced|Yes)=1/7P(Marital Status=Married|Yes) = 0For taxable income:If class=No:sample mean=110sample variance=2975If class=Yes:sample mean=90sample variance=25naive Bayes Classifier:120K)IncomeMarried,No,Refund(XlP(X|Class=No) = P(Refund=No|Class=No) P(Married| Class=No) P(Income=120K| Class=No) = 4

37、/7 4/7 0.0072 = 0.0024lP(X|Class=Yes) = P(Refund=No| Class=Yes) P(Married| Class=Yes) P(Income=120K| Class=Yes) = 1 0 1.2 10-9 = 0由于 P(X|No)P(No) P(X|Yes)P(Yes)因此 P(No|X) P(Yes|X) = Class = No给定测试数据:5657（1 1）使用朴素贝叶斯方法预测样本）使用朴素贝叶斯方法预测样本(A A=0,=0,B B=1,=1,C C=1)=1)的类标号。的类标号。（2 2）比较）比较P P( (A A=1)=1)，P

38、 P( (B B=1)=1)和和 P P( (A A=1,=1,B B=1)=1)，判断，判断A A、B B之间有否有关系。之间有否有关系。58P(P(X X|+) = P(A=1|+) |+) = P(A=1|+) P(B=1|+) P(B=1|+) P(C=1|+) = 0.1 P(C=1|+) = 0.12828P(P(X X| |) = P(A=1|) = P(A=1|) ) P(B=1| P(B=1|) ) P(C=1| P(C=1|) = 0.0) = 0.04848P(+)=P(-)=0.5P(+)=P(-)=0.5因为因为P(P(X X|+)|+)P(+)P(+)P(P(X X

39、| |- -) )P(-)P(-)，所以此样本的，所以此样本的类标号为：类标号为：+ +P(A=1)=0.5P(A=1)=0.5，P(B=1)=0.4P(B=1)=0.4，P(A=1,B=1)=0.2P(A=1,B=1)=0.2P(A)P(A)P(B)=0.2 P(B)=0.2 因为因为P(A=1,B=1)P(A=1,B=1)= =P(A)P(A)P(B)P(B)，所以，所以A A、B B无关无关X:(A = 0,B = 1, C = 1)P(A = 0|+) = 0.4P(B = 1|+) = 0.4P(C = 1|+) = 0.8P(A =0|) = 0.6P(B = 1|) = 0.4P

40、(C = 1|) = 0.2如果一个条件概率为如果一个条件概率为 0， 则整个表达式为则整个表达式为 0概率估计概率估计:mNmpNCAPcNNCAPNNCAPcicicicicici)|(:estimate-m1)|(:Laplace)|( :Originalc: 类数目p: 先验概率m: 参数59NameGive BirthCan FlyLive in WaterHave LegsClasshumanyesnonoyesmammalspythonnononononon-mammalssalmonnonoyesnonon-mammalswhaleyesnoyesnomammalsfrogno

41、nosometimes yesnon-mammalskomodonononoyesnon-mammalsbatyesyesnoyesmammalspigeonnoyesnoyesnon-mammalscatyesnonoyesmammalsleopard sharkyesnoyesnonon-mammalsturtlenonosometimes yesnon-mammalspenguinnonosometimes yesnon-mammalsporcupineyesnonoyesmammalseelnonoyesnonon-mammalssalamandernonosometimes yesn

42、on-mammalsgila monsternononoyesnon-mammalsplatypusnononoyesmammalsowlnoyesnoyesnon-mammalsdolphinyesnoyesnomammalseaglenoyesnoyesnon-mammalsGive BirthCan FlyLive in WaterHave LegsClassyesnoyesno?0027. 02013004. 0)()|(021. 020706. 0)()|(0042. 01341331310131)|(06. 072727676)|(NPNAPMPMAPNAPMAPA: attrib

43、utesM: mammalsN: non-mammalsP(A|M)P(M) P(A|N)P(N)= Mammals60对对孤孤立立噪噪声声点点的的鲁鲁棒棒性性n平平均均了了噪噪声声点点的的数数据据n在在概概率率估估计计计计算算中中通通过过忽忽略略实实例例处处理理丢丢失失的的值值不不相相关关属属性性的的鲁鲁棒棒性性n无无关关属属性性xi，P(Xi|Y)几几乎乎成成了了均均匀匀分分布布一一些些属属性性的的独独立立性性假假设设可可能能不不成成立立n使使用用其其他他的的技技术术，如如贝贝叶叶斯斯信信念念网网络络 (BBN)61如果三个输入中至少有两个等于如果三个输入中至少有两个等于1，Y输出为输出为

44、1.62otherwise0 trueis if1)( where)04 .03 .03 .03 .0(321zzIXXXIY63模型由相互连接的节点和加模型由相互连接的节点和加权链路构成权链路构成输出节点根据各链路的权值输出节点根据各链路的权值，对每个输入值进行统计，对每个输入值进行统计对比输出节点与阈值对比输出节点与阈值 t)(tXwIYiiiPerceptron Model)(tXwsignYiiior64训练神经网络意味着学习神经元的权值65初始化权重初始化权重 (w0， w1， ， wk)以下列方式调整权重，使人工神经网络的输出与训练样本的类以下列方式调整权重，使人工神经网络的输出与

45、训练样本的类标签一致标签一致n目标函数目标函数:n找出找出 wi的权重使得目标函数的值最小的权重使得目标函数的值最小n例如，反向传播算法（见讲义）例如，反向传播算法（见讲义）2),(iiiiXwfYE66找到一个线性超平面（决策边界）划分数据找到一个线性超平面（决策边界）划分数据67One Possible Solution68Another possible solution69Other possible solutions70Which one is better? B1 or B2?How do you define better?71找出最大超平面的边缘，找出最大超平面的边缘， B1 比比 B2 好好720bxw1bxw1bxw1bxw if11bxw if1)(xf2|2 Marginw73最大化最大化:n相当于最小化相当于最小化:n但受到以下约束但受到以下约束:n这是一个约束优化问题这是一个约束优化问题n可采用数值方法解决（例如，二次规划）可采用数值方法解决（例如，二次规划）2|2 Marginw1bxw if11bxw if1)(iiixf2|)(2wwL74如果这个问题不是线性可分的如果