《北方工业大学_数据仓库挖掘7Bayes分类方法精编版》由会员分享，可在线阅读，更多相关《北方工业大学_数据仓库挖掘7Bayes分类方法精编版（51页珍藏版）》请在金锄头文库上搜索。
1、数据仓库与数据挖掘技术 第7章 其它分类方法,主要内容,Bayes分类 基于实例的分类 集成方法,Bayes分类器,一个用于解决分类问题的概率框架 条件概率: Bayes定理:,Bayes定理举例,给定: 50%的脑膜炎患者脖子僵硬 人得脑膜炎的概率是1/50,000 脖子僵硬的人的概率是 1/20 若某个患者脖子僵硬,则他患脑膜炎的概率是多少?,Bayes分类器,将每个属性及类别标记视为随机变量 给定一个具有属性集合(A1, A2,An)的记录 目标是预测类别属性C 具体而言，要寻找使得P(C| A1, A2,An )最大的类别C,Bayes分类器,方法: 利用Bayes定理计算所有类别C的
2、后验概率P(C | A1, A2, , An) 选择使如下概率值最大的类别C P(C | A1, A2, , An) 等价于使如下概率值最大 P(A1, A2, , An|C) P(C),朴素Bayes分类器,假定给定类别的条件下属性Ai之间是独立的: P(A1, A2, , An |C) = P(A1| C) P(A2| C) P(An| C) 可以从Ai和C中估算出P(Ai| C) 类别为使P(Cj) P(Ai| Cj)最大的类Cj,如何从数据中估算概率,类: P(C) = Nc/N e.g., P(No) = 7/10, P(Yes) = 3/10 对离散属性k: P(Ai | Ck)
3、= |Aik|/ Nc 其中|Aik|是属于类Ck，并具有属性值Ai的记录数量 如:P(Status=Married|No) = 4/7P(Refund=Yes|Yes)=0,如何从数据中估算概率,对连续属性: 将区间离散化至不同的桶 违背了独立性假设 2路分割: (A v) 或 (A v) 概率密度估计: 假设属性的取值服从正态分布 使用已有数据来估算分布的参数(如, 均值和方差) 若概率分布已知，则使用其来估算条件概率P(Ai|c),如何从数据中估算概率,正态分布: 对(Income, Class=No): 若Class=No sample mean = 110 sample varian
4、ce = 2975,朴素Bayes分类举例,P(X|Class=No) = P(Refund=No|Class=No) P(Married| Class=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 Since P(X|No)P(No) P(X|Yes)P(Yes) Therefore P(No|X) P(Yes|X)
5、 = Class = No,给定一条测试记录:,朴素Bayes分类举例,A: attributes M: mammals N: non-mammals,P(A|M)P(M) P(A|N)P(N) = Mammals,朴素Bayes分类器小结,抗噪声能力强 在概率估算阶段，通过忽略整条记录来处理缺失值 抗无关属性的能力强 属性独立的假设可能对某些属性不成立 可以使用Bayes信度网络(Bayesian Belief Networks, BBN),Bayes网络,20世纪80年代，Bayes网络(Bayes Network)成功应用于专家系统，成为表示不确定性专家知识和推理的一种流行的方法。 在不
6、确定性表示、可信度计算上还是使用概率方法。 实现时，要根据应用背景采用近似计算方法。,事件的独立性,独立：如果X与Y相互独立，则 P(X,Y) = P(X)P(Y) P(X|Y) = P(X) 条件独立：如果在给定Z的条件下，X与Y相互独立，则 P(X|Y, Z) = P(X|Z) 实际中，条件独立比完全独立更普遍,联合概率,联合概率：P(X1, X2, , XN) 如果相互独立： P(X1, X2, , XN) = P(X1) P(X2) P(XN) 条件概率： P(X1, X2, , XN) = P(X1|X2, , XN) P(X2, , XN) 迭代表示： P(X1, X2, , XN
7、) = P(X1) P(X2| X1) P(X3| X2X1)P(XN|XN-1, , X1) = P(XN) P(XN-1| XN) P(XN-2| XN-1XN)P(X1|X2, , XN) 实际应用中就是利用条件独立来简化网络。,Bayes网络,一系列变量的联合概率分布的图形表示。 一个表示变量之间相互依赖关系的数据结构，图论与概率论的结合。,Bayes网络（续）,两部分 结构图，有向无环图(Directed Acyclic Graph, DAG)，每个节点代表相应的变量。 条件概率表(Conditional Probability Table, CPT)，一系列的概率值，表示局部条件概
8、率分布，即P(node|parents) 。,Bayes网络的构造,选择变量，生成节点 从左至右（从上到下），排列节点 填充网络连接弧，表示节点之间的关系 得到条件概率关系表 条件概率表示的概率网络有时叫“Belief Nets”,由Bayes网络计算概率,简单的联合概率可以直接从网络关系上得到，如： P(X, Y, Z) = P(X)P(Y)P(Z|X, Y),Bayes网络举例,假设： 命题S(Smoker)：该患者是一个吸烟者 命题C(Coal Miner)：该患者是一个煤矿矿井工人 命题L(Lung Cancer)：他患了肺癌 命题E(Emphysema)：他患了肺气肿 已知：S对L和
9、E有因果影响，C对E也有因果影响。 命题间的关系可以描绘成Bayes网络。 每个节点代表一个证据 每一条弧代表一条规则（假设） 弧表达了由规则给出的、节点间的直接因果关系。,Bayes网络举例,CPT表为： P(S) = 0.4 P(C) = 0.3 P(E|S, C) = 0.9 P(E|S, C) = 0.3 P(E|S, C) = 0.5 P(E|S, C) = 0.1,Bayes网络举例（续）,上图例中的联合概率密度为 变量与它在图中的非继承节点在是概率独立的。 P(E|S,C,L) P(E|S,C) (E与L在S条件下独立) P(L|S,C)= P(L|S) (L与C在S, E条件下
10、独立) P(C|S)=P(C) (C与S在E条件下独立) 简化后的联合概率密度为:,Bayes网络的推理,主要用于因果推理和诊断推理 由因导果，P(肺癌|吸烟) 执果索因，P(吸烟|肺癌) 一般情况下是很困难的，原因 不是所有的CPT表都能够得到 网络结构大且复杂，NP-hard问题,Bayes网络的因果推理,已知父节点，计算子节点的条件概率。 主要操作： 重新表达所求的条件概率。 直到所有的概率值可从CPT中得到，推理完成。,因果推理举例,给定患者是一个吸烟者(S)，计算他患肺气肿(E)的概率P(E|S)。,首先，引入E的另一个父节点(C)，P(E|S)=P(E,C|S)+P(E,C|S)
11、右边的第一项 ， P(E,C|S)P(E,C,S)/P(S)P(E|C,S)*P(C,S)/P(S)P(E|C,S)*P(C) 同理可得右边的第二项为：P(E,C|S) = P(E|C,S)*P(C)。 由此可得：P(E|S) = P(E| C,S)*P(C)+P(E|C,S)*P(C) P(C) = 1 P(C)，则有： P(E|S)0.9*0.3+0.3*(1-0.3)=0.48,Bayes网络的诊断推理,在Bayes网中，从一个子节点出发计算父节点的条件概率，即从结果推测起因。 主要操作：使用Bayes公式把诊断推理转换成因果推理。,诊断推理举例,计算在不得肺气肿的人中，不是矿工的概率，
12、即P(C|E)。,P(C|E) = P(E|C)*P(C)/P(E) 由因果推理可知： P(E|C) = P(E, S|C)+P(E, S|C) = P (E|S,C)P(S)+P (E|S,C)P(S) = (10.3)*0.4+(10.1)* (10.4)=0.82 由此得：P(C|E) = P(E|C)*P(C) / P(E) = 0.82*(10.3) / P(E)=0.574/ P(E) 同样， P(C|E) = P(E|C)*P(C) / P(E)=0.102 / P(E) 由于全概率公式， P(C|E)+ P(C|E)=1 代入得， P(E)=0.676 所以， P(C|E) =
13、 0.849,Bayes方法预测2010世界杯,World Cup Group C,England beating Argentina,2012图灵奖得主Judea Pearl,1937- 加州大学洛杉矶分校（UCLA）的计算机科学教授 将贝叶斯网络和概率方法引入人工智能的先驱之一 数学化因果模型的先驱之一 iPhone的Siri语音识别 Google的无人驾驶汽车,主要内容,Bayes分类 基于实例的分类 集成方法,基于实例的分类（1）,存储训练记录 使用训练记录来预测未知记录的类别,基于实例的分类（2）,例子: 机械学习(Rote-learner) 记住所有训练数据，只有当类别未知的记录与
14、某训练记录的所有属性的值都匹配时，才对其分类。 最近邻居(Nearest neighbor) 用k个最临近点执行分类。,最近邻居分类（1）,基本思想: If it walks like a duck, quacks like a duck, then its probably a duck,最近邻居分类（2）,基本条件 存储的训练实例 实例间距离的度量方法 确定K值, 即邻居的数量 对未知记录分类: 计算与训练记录的距离 确定最近的k个邻居 使用k个邻居的类别对类别未知的数据进行分类 (如投票),最近邻居的定义,记录x的k-最近邻居是指与x距离最近的k个数据点,距离的度量,计算两点间的距离:
15、欧式距离(Euclidean distance) 从最近邻居中确定类别 从k个最近邻居中做投票，取多数 根据距离确定不同点的权重 w = 1/d2,K值的确定,选择K的值: 若K太小，则对噪声点敏感； 若K太大，可能类别比较分散。,K-NN分类的特点,k-NN分类器是lazy learner 与eager learner，如决策树、基于规则的分类，不同。 不明确的构建分类模型。 对类别未知的记录的分类代价较高。,PEBLS,PEBLS: Parallel Examplar-Based Learning System (Cost & Salzberg, Machine Learning, 199
16、3) 既适用于连续属性，也适用于名词性属性 对名词性属性，其距离使用(Modified Value Difference Metric, MVDM) 每条属性都被赋予一个权重 最近邻居数量, k = 1,Example: PEBLS,Distance between nominal attribute values: d(Single,Married) = | 2/4 0/4 | + | 2/4 4/4 | = 1 d(Single,Divorced) = | 2/4 1/2 | + | 2/4 1/2 | = 0 d(Married,Divorced) = | 0/4 1/2 | + | 4/4 1/2 | = 1 d(Refund=Yes,Refund=No) = | 0/3 3/7 | + | 3/3 4/7 | = 6/7,Example: PEBLS,Distance between record X
