第08章 分类：其他技术.ppt

1、数据仓库与数据挖掘,第8章 分类：其他技术,第8章 分类：其他技术,基于规则的分类器 最邻近分类器 贝叶斯分类器 人工神经网络 支持向量机 组合方法 不平衡类问题 多类问题,2,基于规则的分类器,使用一组 “ifthen” 规则来分类记录 规则: (Condition) y 其中 Condition 是属性测试的合取 y 是类标记 LHS: 规则前件或前提 RHS: 规则后件 分类规则的例子: (Blood Type=Warm) (Lay Eggs=Yes) Birds (Taxable Income 50K) (Refund=Yes) Evade=No,3,基于规则的分类器 (范例),4,基

2、于规则的分类器 (范例),R1: (Give Birth = no) (Can Fly = yes) Birds R2: (Give Birth = no) (Live in Water = yes) Fishes R3: (Give Birth = yes) (Blood Type = warm) Mammals(哺乳类) R4: (Give Birth = no) (Can Fly = no) Reptiles (爬行类) R5: (Live in Water = sometimes) Amphibians (两栖类),5,基于规则的分类器的应用,如果实例的属性满足了规则的条件， 则称规则

3、 r 覆盖 实例 x,R1: (Give Birth = no) (Can Fly = yes) Birds R2: (Give Birth = no) (Live in Water = yes) Fishes R3: (Give Birth = yes) (Blood Type = warm) Mammals R4: (Give Birth = no) (Can Fly = no) Reptiles R5: (Live in Water = sometimes) Amphibians,规则 R1 覆盖 hawk = Bird 规则 R3 覆盖 grizzly bear = Mammal,6,

4、规则的覆盖率和准确率,覆盖率: 满足规则前件的记录的比例 准确率: 满足规则前件和后件的记录的比例,(Status=Single) No Coverage = 40% Accuracy = 50%,7,基于规则的分类器的工作原理,R1: (Give Birth = no) (Can Fly = yes) Birds R2: (Give Birth = no) (Live in Water = yes) Fishes R3: (Give Birth = yes) (Blood Type = warm) Mammals R4: (Give Birth = no) (Can Fly = no) Re

5、ptiles R5: (Live in Water = sometimes) Amphibians,lemur 触发规则 R3， 所以分类为 mammal turtle 触发规则 R4 和 R5 dogfish shark 没有触发任何规则,8,基于规则的分类器的特点,互斥规则 如果规则彼此独立那么分类器中的规则是互斥的 每个记录最多被一条规则覆盖 穷举规则 如果规则覆盖所有可能的属性值组合， 则分类器中的规则是穷举的 每个记录至少被一条规则覆盖,9,从决策树到规则,规则是互斥和穷举的 规则集包含信息与树一致,10,规则可以简化,初始规则: (Refund=No) (Status=Marrie

6、d) No 简化规则: (Status=Married) No,11,规则简化的影响,规则不再互斥 一个记录可能会触发多于一条规则 如何解决? 有序规则 无序规则 使用投票模式 规则不再穷举 一个记录可能不再触发任何规则 解决办法? 使用缺省类,12,有序规则集,规则按照优先级排列 一个有序的规则集也称为决策表 当一个测试记录交给分类器时 由它所触发的最高优先级的规则来分类 如果没有触发任何规则， 则分配到缺省类,R1: (Give Birth = no) (Can Fly = yes) Birds R2: (Give Birth = no) (Live in Water = yes) Fis

7、hes R3: (Give Birth = yes) (Blood Type = warm) Mammals R4: (Give Birth = no) (Can Fly = no) Reptiles R5: (Live in Water = sometimes) Amphibians,13,规则排序方案,基于规则的排序 每个规则根据规则质量排序 基于类的排序 属于同一个类的规则一起出现,14,构建分类规则,直接方法: 直接从数据中抽取规则 如.: RIPPER， CN2， Holtes 1R 间接方法: 从其它的分类模型中抽取规则 (如决策树， 神经网络等). 如: C4.5rules,15

8、,直接方法: 顺序覆盖,从空规则集开始 使用一次学习一条规则的方法实现规则增长 删除被规则覆盖的训练数据 重复步骤 (2) 和 (3) 直至遇到终止条件,16,顺序覆盖的例子,17,顺序覆盖的例子,18,顺序覆盖的方方面面,规则增长 实例删除 规则评估 停止标准 规则剪枝,19,规则增长,两种普遍策略 从一般到特殊 从特殊到一般,20,删除实例,为何要删除正例? 确保下一条规则不同于前 防止高估了规则的准确率 为何要删除反例? 防止低估了规则的准确率 比较图中规则 R2 和 R3,21,规则评估,度量: Accuracy Laplace M-estimate,n : 规则覆盖的实例数 nc :

9、 规则覆盖的正例数 k : 类数目 p : 先验概率,22,停止标准和规则剪枝,停止标准 计算收益 如果收益不显著， 放弃新规则 规则剪枝 类似决策树的后剪枝 降低错误剪枝: 删除一个规则中的合取 比较剪枝前后的验证集的错误率 如果错误率得到改善， 剪枝这个合取,23,直接方法总结,增长一个规则 从规则中删除实例 剪枝规则 (如果必要的话) 增加规则到当前规则集中 重复,24,直接方法: RIPPER,对于 2-class 问题， 选择其中一个为正类， 另一个为反类 从正类中学习规则 反类为缺省类 对于 multi-class 问题 根据类的频率对类进行排序 (实例属于某个特定类的比例) 从最

10、小的类开始学习规则集， 其余类作为反类 继续从下一个最小的类作为正类开始， 不断重复,25,直接方法: RIPPER,增加一个规则: 从空规则开始 只要改善了 FOIL 的信息增益， 就增加合取 当规则不再覆盖反例就停止增加合取 新规则根据其在确认集上的性能进行剪枝 剪枝度量: v = (p-n)/(p+n) p: 验证集中规则覆盖的正例数 n: 验证集中规则覆盖的负例数 剪枝方法: 删除使v增加的任何最后添加的条件序列(合取)，,26,直接方法: RIPPER,建立规则集: 使用顺序覆盖算法 找出覆盖当前正例集的最佳规则 删除规则覆盖的正例和反例 每次一条规则加入规则集， 计算新的描述长度

11、当新规则描述长度比最小描述长度（见P112）增加 d 个比特位就停止增加新的规则,27,间接方法,28,间接方法: C4.5rules,从未剪枝的决策树中抽取规则 对每条规则， r: A y， 考查可替换规则 r: A y 其中 A 是从 A 中删除一个合取的结果 比较 r 与所有 r 的悲观误差率 如果 r 中存在某一规则有较低的悲观误差率（P111）则剪枝 重复上述过程直至不再能改善整体错误率,29,间接方法: C4.5rules,排序规则：不对规则排序， 对规则子集排序 (类排序) 每个子集都是具有相同类的规则集合 计算每个子集的描述长度，进行升序排列。具有最小描述长度的类优先级最高。

12、描述长度 = L(error) + g*L(model) L(error)是对误分类样例编码长度，L(model)是对模型编码长度。g是调节参数(default value = 0.5)，取决于模型中冗余属性的数量，冗余越多则g越小。,30,Example,31,C4.5 versus RIPPER,C4.5rules: (Give Birth=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

13、Water=No) Reptiles ( ) Amphibians,RIPPER: (Live in Water=Yes) Fishes (Have Legs=No) Reptiles (Give Birth=No， Can Fly=No， Live In Water=No) Reptiles (Can Fly=Yes，Give Birth=No) Birds () Mammals,32,基于规则分类器的优点,表达能力几乎等价于决策树 生产更容易解释的描述性模型 适宜处理类分布不平衡的数据集,33,第8章 分类：其他技术,基于规则的分类器 最邻近分类器 贝叶斯分类器 人工神经网络 支持向量机

14、组合方法 不平衡类问题 多类问题,34,最近邻分类法,Basic idea: If it walks like a duck， quacks like a duck， then its probably a duck,35,最近邻分类法,36,最近邻分类法,37,最近邻分类法,38,最近邻分类法,Choosing the value of k: If k is too small， sensitive to noise points If k is too large， neighborhood may include points from other classes,39,最近邻分类法,4

15、0,第 41 页,最近邻分类法,k-最近邻(k-Nearest Neighbour， kNN)分类法是一种基于距离的分类算法，它既不需要事先建立分类模型，也无需对分类模型进行评估，而仅利用有类别标号的样本集，直接对没有类别标号的数据对象Zu进行分类，即确定其类别标号。 假定样本集S中每个数据点都有一个唯一的类别标号，每个类别标识Cj中都有多个数据对象。对于一个没有标识的数据点Zu，k-最近邻分类法遍历搜索样本集S，找出距离Zu最近的k个样本点，即k-最近邻集N，并将其中多数样本的类别标号分配给Zu。,第 42 页,最近邻分类法,第 43 页,最近邻分类法,例 设某公司现有15名员工的基本信息，

16、包括其个子为高个、中等、矮个的分类标识。 公司现刚招进一位名叫刘萍的新员工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差距最大的员工，且有d(Z1，X2)d(Z1，X6)，因此，在N中用X6替换X2得到 N=X1=1.60，X6=1.85，X3=1.9

17、0，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) 因为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

18、，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个身高最接近Z1=1.62的员工，且其X1=1.60，X8=1.70，X7=1.59， X5=1.70这4个员工的类别都是“矮个”，仅有X15=1.75的类别是“中等”；因此，新员工Z1=刘萍的个子为矮个。,第8章 分类：其他技术,基于规则的分类器 最邻近分类器 贝叶斯分类器 人工神经网络 支持向量机 组合方法 不

19、平衡类问题 多类问题,46,贝叶斯分类器,解决分类问题的概率框架 联合概率：P(A，C) = P(C|A)P(A) = P(A|C)P(C) 条件概率: 贝叶斯理论:,47,贝叶斯理论举例,给定: 病人患有脑膜炎的先验概率是 1/50，000 P(M) 病人患有颈部僵硬的先验概率是 1/20 P(S) 患脑膜炎的人有50%的人会发生颈部僵硬 P(S|M) 如果病人患有颈部僵硬， 那么他/她患有脑膜炎的概率有多大? 如果缺课5次以上的比率是30%，补考率是20%，补考中的60%都是缺课5次以上，问：缺课5次以上的学生补考的概率是多少？,48,贝叶斯分类器,每个属性和类标签作为随机变量 给定一个记

20、录属性 (A1， A2，An) 目标是预测类 C 特别地， 我们想找到使得 P(C| A1， A2，An ) 最大化的 C 值 我们能直接从数据中预测 P(C| A1， A2，An ) 吗?,49,贝叶斯分类器,方法: 使用贝叶斯理论计算所有 C 值的后验概率 P(C | A1， A2， ， An) 选择 C 值， 使最大化 P(C | A1， A2， ， An) 等价的， 选择 C 值， 使最大化 P(A1， A2， ， An|C) P(C) 如何估算 P(A1， A2， ， An | C )?,50,朴素贝叶斯分类器,假设属性 Ai 是独立的， 给定类Cj: P(A1， A2， ， An

21、|C) = P(A1| Cj) P(A2| Cj) P(An| Cj) 对于所有Ai 和 Cj可估算 P(Ai| Cj) 如果 P(Cj) P(Ai| Cj) 是最大的，那么新的点分类为 Cj 。,51,如何从数据中估算概率,类: P(C) = Nc/N 如： P(No) = 7/10， P(Yes) = 3/10 离散属性: P(Ai | Ck) = |Aik|/ Nc 其中， |Aik| 是属性Ai 且属于类 Ck 的实例数 例如: P(Status=Married|No) = 4/7P(Refund=Yes|Yes)=0,52,如何从数据中估算概率,针对连续属性: 离散化 区间至桶中 每

22、个桶一个序数属性 双向划分: (A v) 选择两种分裂中的一种作为新的属性 概率密度估算: 假设属性有正态分布 使用数据估算分布参数 (如：均值和标准差) 一旦概率分布已知， 可以用来估算条件概率 P(Ai|c),53,如何从数据中估算概率,正态分布: 每个对应一对 (Ai，ci) For (Income， Class=No): If Class=No sample mean = 110 sample variance = 2975,54,朴素贝叶斯分类器举例,55,朴素贝叶斯分类器举例,P(X|Class=No) = P(Refund=No|Class=No) P(Married| Clas

23、s=No) P(Income=120K| Class=No) = 4/7 4/7 0.0072 = 0.0024 P(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,给定测试数据:,56,课堂练习,57,（1）使用朴素贝叶斯方法预测样本(A=0,B=1,C=1)的类标号。 （2）比较P(A=1)，P(B=1

24、)和 P(A=1,B=1)，判断A、B之间有否有关系。,课堂练习,58,P(X|+) = P(A=1|+) P(B=1|+) P(C=1|+) = 0.128 P(X|) = P(A=1|) P(B=1|) P(C=1|) = 0.048 P(+)=P(-)=0.5 因为P(X|+)P(+)P(X|-)P(-)，所以此样本的类标号为：+ P(A=1)=0.5，P(B=1)=0.4， P(A=1,B=1)=0.2 P(A)P(B)=0.2 因为P(A=1,B=1)=P(A)P(B)，所以A、B无关,X:(A = 0,B = 1, C = 1) P(A = 0|+) = 0.4 P(B = 1|+

25、) = 0.4 P(C = 1|+) = 0.8 P(A =0|) = 0.6 P(B = 1|) = 0.4 P(C = 1|) = 0.2,朴素贝叶斯分类器,如果一个条件概率为 0， 则整个表达式为 0 概率估计:,c: 类数目 p: 先验概率 m: 参数,59,朴素贝叶斯分类器举例,A: attributes M: mammals N: non-mammals,P(A|M)P(M) P(A|N)P(N) = Mammals,60,朴素贝叶斯(总结),对孤立噪声点的鲁棒性 平均了噪声点的数据 在概率估计计算中通过忽略实例处理丢失的值 不相关属性的鲁棒性 无关属性xi，P(Xi|Y)几乎成了

26、均匀分布 一些属性的独立性假设可能不成立 使用其他的技术，如贝叶斯信念网络 (BBN),61,人工神经网络 (ANN),如果三个输入中至少有两个等于1，Y输出为1.,62,人工神经网络 (ANN),63,人工神经网络 (ANN),模型由相互连接的节点和加权链路构成 输出节点根据各链路的权值，对每个输入值进行统计 对比输出节点与阈值 t,Perceptron Model,or,64,人工神经网络的一般结构,训练神经网络意味着学习神经元的权值,65,人工神经网络学习算法,初始化权重 (w0， w1， ， wk) 以下列方式调整权重，使人工神经网络的输出与训练样本的类标签一致 目标函数: 找出 wi的权重使得目标函数的值最小 例如，反向传播算法（见讲义）,66,支持向量机,找到一个线性超平面（决策边界）划分数据,67,支持向量机,One Possible Solution,68,支持向量机,Another possible solution,69,支持向量机,Other possible solutions,70,支持向量机,Which one is better? B1 or B2? How do you define better?,71,支持向量机