第4章 贝叶斯分类器.pptx

1、第四章 贝叶斯分类器 问题的提出 KNN ？ 决策树？ 概率方法？ 贝叶斯 贝叶斯(约1701-1761) Thomas Bayes，英国数学家。 约1701年出生于伦敦，做过神甫。1742年成为英国 皇家学会会员。1761年4月7日逝世。贝叶斯在数学 方面主要研究概率论。他首先将归纳推理法用于概 率论基础理论，并创立了贝叶斯统计理论，对于统 计决策函数、统计推断、统计的估算等做出了贡献。 他死后，理查德 普莱斯(Richard Price)于1763年将他 的著作机会问题的解法(An essay towards solving a problem in the doctrine of cha

2、nces)寄给了英国皇家 学会，对于现代概率论和数理统计产生了重要的影 响 贝叶斯决策就是在不完全情报下，对部分未知的状 态用主观概率估计，然后用贝叶斯公式对发生概率 进行修正，最后再利用期望值和修正概率做出最优 决策。 贝叶斯决策理论方法是统计模型决策中的一个基本 方法，其基本思想是： 1、已知类条件概率密度参数表达式和先验概率。 2、利用贝叶斯公式转换成后验概率。 3、根据后验概率大小进行决策分类。 贝叶斯 最早的PathFinder系统，该系统是淋巴疾病诊断的医学系统，它 可以诊断60多种疾病，涉及100多种症状;后来发展起来的Internist I系统，也是一种医学诊断系统，但它可以诊

3、断多达600多种常 见的疾病。 1995年，微软推出了第一个基于贝叶斯网的专家系统，一个用于 幼儿保健的网站OnParent ()，使父母们 可以自行诊断。 贝叶斯网络的应用 (1)故障诊断(diagnose) (2)专家系统(expert system) (3)规划(planning) (4)学习(learning) (5)分类(classifying) 贝叶斯网络的应用 12 0 0 12 12 , , 1, ,1,2, ; 2, ,. n ij n n EB BB E B Bi jn BBB B BB 定义设为试验 的样本空间 为的一组事件 若 则称为样本空间的一个划分 样本空间的划分样

4、本空间的划分 1 B 2 B 3 B n B 1n B 概率(回顾) 全概率公式 12 1122 1 , ,()0 (1,2, ), ( )(|) ()(|) () (|) () ( ) (|) ni nn n i i EAE B BBP B in P AP A B P BP A B P B P A B P B P B P A B 定义 设 为试验 的样本空间为 的事件 为 的一个划分 且 则 概率(回顾) 训练数据集： 由X和Y的联合概率分布P(X,Y)独立同分布产生 朴素贝叶斯通过训练数据集学习联合概率分布P(X,Y) ， 即先验概率分布： 及条件概率分布： 注意：条件概率为指数级别的参数

5、： 基本方法 条件独立性假设： “朴素”贝叶斯名字由来，牺牲分类准确性。 贝叶斯定理： 代入上式： 基本方法 贝叶斯分类器： 分母对所有ck都相同： 基本方法 朴素贝叶斯法将实例分到后验概率最大的类中，等价于期望风险 最小化， 假设选择0-1损失函数：f(X)为决策函数 期望风险函数： 取条件期望： 后验概率最大化的含义： 只需对X=x逐个极小化，得： 推导出后验概率最大化准则： 后验概率最大化的含义： 应用极大似然估计法估计相应的概率： 先验概率P(Y=ck)的极大似然估计是： 设第j个特征x(j)可能取值的集合为： 条件概率的极大似然估计： 朴素贝叶斯法的参数估 学习与分类算法Na ve

6、Bayes Algorithm： 输入： 训练数据集 第i个样本的第j个特征 第j个特征可能取的第l个值 输出： x的分类 朴素贝叶斯法的参数估 步骤 1、计算先验概率和条件概率 朴素贝叶斯法的参数估 步骤 2、对于给定的实例 计算 3、确定x的类别 朴素贝叶斯法的参数估 例子 测试 例子 例子 考虑：用极大似然估计可能会出现所要估计的概率值为0的情况， 这时会影响到后 验概率的计算结果，使分类产生偏差.解决这一 问题的方法是采用贝叶斯估计。 条件概率的贝叶斯估计： 先验概率的贝叶斯估计： 贝叶斯估计 考虑几个问题： 1、如果属性之间不相互独立？ 2、如果属性A和属性B都很重要，但是相关？ 3

7、、如果属性A，属性B之间独立，但是在属性C下有关？ 4、属性之间的条件概率究竟有多少个？ 5、条件概率谬论？ 朴素贝叶斯网络的缺陷 条件概率的谬论 假设 P(A|B) 大致等于 P(B|A) 例子： P(disease) = 1% = 0.01 P(well) = 99% = 0.99 P(negative | disease) = 1% P(positive | disease) = 99% P(positive | well) = 1% P(negative | well) = 99% ? P(disease|positive) = ? = () + () = 0.99 0.01 0.01

8、 0.99 + 0.99 0.01 = 50% Problem: if P(d)=0.1% , P(d|P)=? 贝叶斯分类器 阻塞:一条路径被结点集 F 阻塞，是指在路径上存在一个结点 Z 满 足下面三种情形之一： (1) Z F，并且路径中有一条有向弧指向 Z，另一条有向弧源自 Z； (2 )Z F，并且路径中有两条有向弧源自 Z； (3) Z 及 Z 的所有后继结点都不在 F 中，并且路径中有两条有向弧指 Z。 信息论相关概念 阻塞: X = X2和Y = X3被Z = X1所分割。 路径X2X1 X3被X1 Z阻塞; 同 时路径X2 X4 X3也被阻塞,因为 X4及它的所有子孙都不在Z

9、中。因 此成立d(X2,X1,X3)。 然而，X和Y没有被Z= X1, X5所d 分割，因为路径X2 X4 X3由于 X5的作用而成为活跃，X5在Z 中， 是X4的子孙 信息论相关概念 d-separation：令 X，Y 和 Z 是一个有向无环图 G 中三个不相交节点 的子集，如果在集合 X 和 Y 中所有节点间的所有路径都被集合 Z 所 阻塞，则称集合 X 和 Y 被 Z 集合 d-separation，表示为G，也 称 Z为 A 和 B 的切割集。否则，称在给定集合 Z 下集合 X 和 Y 图形 依赖。 I-map： 假设 G 是以随机变量 Y1,Y2,Yn 为节点的一个有向无环图， P

10、 是随机变量 Y1,Y2,Yn的联合概率函数，如果从图 G 中得到的每 一个独立性假设(Yi在给定其父母节点变量的情况下独立于它的非后 代节点)在联合概率 P 的计算中都成立，则称 G 是该概率分布 P 的 一个独立映射(Independence-map, I-map)。 信息论相关概念 朴素贝叶斯网络分类器 半朴素贝叶斯分类器 (SNBC：Semi-Naive Bayesian Classifier) 选择贝叶斯分类器(SBC: Selective Bayesian Classifier) 树增广朴素贝叶斯网络分类器(TAN: Tree Augmented Naive Bayes) 平均一依

11、赖估测器( AODE：averaged one dependence estimators)学 习算法 加权平均的一依赖估测器(WAODE：weightily averaged one dependence estimators)学习算法 无约束贝叶斯网络分类器(GBN：General Baynes Network) 隐藏扩展的朴素贝叶斯分类算法(HANB) 朴素贝叶斯网络分类器的改进算法 SNBC：Semi-Naive Bayesian Classifier) ， SNBC在模型构建过程中，依照一定的标准将关联程度较大的特征属性合 并在一起组合成新属性。 SNBC的各个组合属性之间相对于类别

12、属性也是相互独立。 SNBC除了结构上的差别之外，计算推导过程与朴素贝叶斯相同。 半朴素贝叶斯网络分类器 SBC: Selective Bayesian Classifier) SBC设计目标是为了提高朴素贝叶斯在属性冗余情况下的分类精 度。 SBC只使用属性集的子集作为决策过程中的属性结点，即选择贝 叶斯分类器选择初始特征的子集作为属性结点。 SBC通过搜索特征空间，去掉特征间具有较强依赖关系的属性。 前向（空集到全集），后向（全集到空集） 可能的搜索子集2m 选择贝叶斯分类器 属性的相互独立性？ 如何测量？ 信息论相关概念 设有随机变量(X,Y),其联合概率分布为： 条件熵H(Y|X)：表

13、示在己知随机变量X的条件下随机变 量Y的不确定性，定义为X给定条件下Y的条件概率分布 的熵对X的数学期望： 信息增益（回顾） 定义 (信息增益):特征A对训练数据集D的信息增益，g(D,A), 定义为 集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差， 即 g(D,A)=H(D)-H(D|A) (Information gain)表示得知特征X的信息而使得类Y的信息的不确定 性减少的程度. 般地，熵H(Y)与条件熵H(Y|X)之差称为互信息（mutual information) 决策树学习中的信息增益等价于训练数据集中类与特征的互信息. 信息增益（回顾） 设信源X为离散

14、随机变量，则用来度量X的不确定性的信息熵H(X) 为 设(X,Y )均为离散随机变量，用来度量二元随机变量的不确定性联 合信息熵H(X,Y )为 信息论相关概念 条件信息熵H(X|Y )用来度量在收到随机变量Y 提供的信息后，随 机变量X仍然存在的不确定性 互信息I(X;Y )用来描述随机变量Y 提供的关于X的信息量的大小。 信息论相关概念 在已知Y 的前提下，随机变量X和Z之间的条件互信息定义为 信息论相关概念 条件独立：对概率模式 M，A，B 和 C 是 U 的三个互不相交的变 量子集，如果对 x A， y B和 z C都有 p ( x|y,z)= p(x|z)， 其中 p(y,z)0，称

15、给定 C 时 A 和 B 条件独立，记为 I(A,C,B)M。 或：p(x,y|z)=p(x|z)p(y|z) 信息论相关概念 贝叶斯网络是由图论和概率论结合而成的描述多元统计关系的模 型，它为多个变量之间复杂依赖关系的表示提供了统一的框架， 具有紧凑有效、简洁直观的特点。 由于贝叶斯网络对大规模复杂系统简约而紧凑的表示能力，使得 其成为人工智能、专家系统、模式识别、数据挖掘和软件测试等 领域的研究热点。 贝叶斯网络基本模型 父节点pa(Vi) 子节点ch(Vi) 邻居节点nb(Vi) 祖先an(vi) 有向环 有向无环（directed acyclic Graph） BN二元组 贝叶斯网络基

16、本模型 贝叶斯网络基本模型 N个变量的BN， 变量xi有ri个取值 父节点pa(xi)的取值qi 网络参数： 贝叶斯网络基本模型 表示所有参数组成的向量 ij* 表示 子向量 i* 表示 子向量 贝叶斯估计 P()的三个假设： （全局独立）关于不同变量xi的参数相互独立。 （局部独立）给定一个变量xi对应于pa(xi) 的不同取值的参数相互独立。 贝叶斯估计 给定数据集D的条件下， 即： 的后验概率分布 P (|D)服从 Dirichlet 分布 结合贝叶斯网络的可分解性得到参数估计值 贝叶斯估计 Beta distribution 在,两个值的控制下x的概率分布，即控制Beta分布的性质 阶

17、乘在实数域和复数域的扩展 贝叶斯估计 BN 结构学习就是在给定一个数据样本集合 D 的前提下，寻找一 个与训练样本集D匹配最好的网络结构，而搜索最优的网络结构 是一个 NP 难问题，因此，从数据中学习贝叶斯网络结构一直是 研究的热点。 基于评分搜索的方法 Robinson 等证明了包含n个节点可能的 BN 结构数目 K2 评分（又称 CH 评分），BD 评分，MDL（Minimum Description Length） 评分，BIC（Bayesian Information Criterion）评分，AIC（Akaike Information Criterion）评分 贝叶斯网络结构学习

18、基于信息理论的评分函数主要是利用编码理论和信息论中的最小 描述长度（Minimum Description Length，MDL）原理来实现的 其基本思想源自对数据的存储假设D是一组给定的实例数据， 如果要对其进行保存，为了节省存储空间，一般采用某种模型对 其进行编码压缩，然后再保存压缩后的数据； 为了在需要的时候可以完全恢复这些实例数据，要求对所使用的 模型进行保存；因此，需要保存的数据长度等于压缩后的数据长 度加上模型的描述长度，该长度称为总的描述长度。 基于信息理论的评分函数 MDL评分准则趋向于寻找一个结构较简单的网络，实现网络精度与复 杂度之间的均衡。 利用参数个数作为网络结构复杂度

19、的惩罚函数 采用海明码表示压缩后的数据长度，即就是关于数据D和模型的对数 似然 得MDL得分 基于信息理论的评分函数 简化： 基于信息理论的评分函数 树增广朴素贝叶斯网络分类器(TAN: Tree Augmented Naive Bayes) 在属性之间增添连接弧，以消除朴素贝叶斯分类器关于条件独立的假设， 称为扩展弧。 从结点Xi到Xj的扩展弧表示属性Xj对分类的影响也取决于Xi的取值。 可能有这样的情况: 待分类样本的属性值Xi和Xj对分类的影响都不大， P(xi|c)和P(xj|c)的值比较低，但是P(xj|xi, c)的值却很高，这时朴素贝叶斯 分类器会过度降低样本属于类c概率，而扩展

20、的朴素贝叶斯网络分类器却 可以避免这一点。 树增广朴素贝叶斯网络分类器 树增广朴素贝叶斯网络分类器 TAN的构造过程： 步骤1. 通过训练集计算属性对之间的条件互信息I(Xi,Xj|C) (i j)。 步骤2. 建立一个以X1, X2, , Xn为结点的加权完全无向图，结点 Xi, Xj之间的权重为I(Xi,Xj|C)(i j)。 步骤3. 利用求最大权生成树算法，建立该无向图最大权重跨度树。 首先把边按权重由大到小排序，之后遵照被选择的边不能构成回 路的原则，按照边的权重由大到小的顺序选择边，这样由所选择 的边构成的树便是最大权重跨度树。 树增广朴素贝叶斯网络分类器 步骤4. 指定一个属性结

21、点作为根结点，将所有边的方向设置成由 根结点指向外，把无向图转换成有向图。 步骤5. 加入类结点C，并添加从C指向每个属性结点Xi的弧。 树增广朴素贝叶斯网络分类器 平均一依赖估测器(averaged one dependence estimators,简记为 AODE)的学习算法。 AODE首先针对每一个属性结点学习一个“特殊”的树扩展的朴素 贝叶斯分类器,之所以特殊,是因为它直接把该属性结点当成是其 他所有属性结点的父亲结点。然后,把这些树扩展的朴素贝叶斯分 类器进行平均。 平均一依赖估测器 平均一依赖估测器 在AODE模型中,所有的树扩展的朴素贝叶斯分类器对最终分类的 贡献是一样的,这似

22、乎不太合理 平均依赖估测器 加权平均的一依赖估测器(weightily averaged one dependence estimators,简记WAODE） 加权平均一依赖估测器 加权平均的一依赖估测器(weightily averaged one dependence estimators,简记WAODE） 加权平均-依赖估测器 贝叶斯算法处理流程： def loadDataSet(): postingList=my, dog, has, flea, problems, help, please, maybe, not, take, him, to, dog, park, stupid,

23、my, dalmation, is, so, cute, I, love, him, stop, posting, stupid, worthless, garbage, mr, licks, ate, my, steak, how, to, stop, him, quit, buying, worthless, dog, food, stupid classVec = 0,1,0,1,0,1 #1 is abusive, 0 not return postingList,classVec 使用Python 进行文本分类 def createVocabList(dataSet): vocabS

24、et = set() #create empty set for document in dataSet: vocabSet = vocabSet | set(document) #union of the two sets return list(vocabSet) 使用Python 进行文本分类 def trainNB0(trainMatrix,trainCategory): numTrainDocs = len(trainMatrix) numWords = len(trainMatrix0) pAbusive = sum(trainCategory)/float(numTrainDoc

25、s) p0Num = ones(numWords); p1Num = ones(numWords) #change to ones() p0Denom = 2.0; p1Denom = 2.0 #change to 2.0 训练算法：从词向量计算概率 for i in range(numTrainDocs): if trainCategoryi = 1: p1Num += trainMatrixi p1Denom += sum(trainMatrixi) else: p0Num += trainMatrixi p0Denom += sum(trainMatrixi) p1Vect = log(

26、p1Num/p1Denom) #change to log() p0Vect = log(p0Num/p0Denom) #change to log() return p0Vect,p1Vect,pAbusive 训练算法：从词向量计算概率 def classifyNB(vec2Classify, p0Vec, p1Vec, pClass1): p1 = sum(vec2Classify * p1Vec) + log(pClass1) #element-wise mult p0 = sum(vec2Classify * p0Vec) + log(1.0 - pClass1) if p1 p0:

27、 return 1 else: return 0 测试和使用算法 def classifyNB(vec2Classify, p0Vec, p1Vec, pClass1): p1 = sum(vec2Classify * p1Vec) + log(pClass1) #element-wise mult p0 = sum(vec2Classify * p0Vec) + log(1.0 - pClass1) if p1 p0: return 1 else: return 0 测试算法和修改分类器 def testingNB(): listOPosts,listClasses = loadDataSe

28、t() myVocabList = createVocabList(listOPosts) trainMat= for postinDoc in listOPosts: trainMat.append(setOfWords2Vec(myVocabList, postinDoc) p0V,p1V,pAb = trainNB0(array(trainMat),array(listClasses) testEntry = love, my, dalmation thisDoc = array(setOfWords2Vec(myVocabList, testEntry) print testEntry

29、,classified as: ,classifyNB(thisDoc,p0V,p1V,pAb) testEntry = stupid, garbage thisDoc = array(setOfWords2Vec(myVocabList, testEntry) print testEntry,classified as: ,classifyNB(thisDoc,p0V,p1V,pAb) 测试算法和修改分类器 文档词袋模型 切分文本 Def spamTest(): docList=; classList = ; fullText = for i in range(1,26): wordList

30、 = textParse(open(email/spam/%d.txt % i).read() docList.append(wordList) fullText.extend(wordList) classList.append(1) wordList = textParse(open(email/ham/%d.txt % i).read() docList.append(wordList) fullText.extend(wordList) classList.append(0) vocabList = createVocabList(docList)#create vocabulary

31、trainingSet = range(50); testSet= #create test set 使用朴素贝叶斯方法进行交叉验证 使用朴素贝叶斯方法进行交叉验证 Feedparser的安装 下载 网络学堂 安装：python setup.py install RSS的使用：从RSS源收集数据 高频词去除 RSS的使用：从RSS源收集数据 两个RSS源作为参数 RSS的使用：从RSS源收集数据 RSS的使用：从RSS源收集数据 RSS的使用：从RSS源收集数据 问题： 高频次设定的阈值对正确率的影响 消除各种语言的高频词 RSS的使用：从RSS源收集数据 分析数据：显示地域相关的用词 见参考文献。 实验作业三 Q&A