贝叶斯方法在聚类中的应用
- 格式:doc
- 大小:633.50 KB
- 文档页数:11
1 算法介绍
1.1 贝叶斯方法的基本观点
托马斯·贝叶斯(ThomasBayes)是英国数学家,他对贝叶斯方法奠基性的工作是他的论文“关于几率性问题求解的评论”。由于当时贝叶斯方法在理论和应用中还存在很多不完善的地方,因此在很长一段时间并未被普遍接受。后来随着统计决策理论、信息论和经验贝叶斯方法等理论和方法的创立和应用,贝叶斯方法很快显示出它的优点,成为十分活跃的一个方向。随着人工智能的发展尤其是机器学习、数据挖掘的兴起,贝叶斯理论的发展和应用也获得了更为广阔的空间。近年来,贝叶斯学习理论方面的文章更是层出不穷,内容涉及到人工智能的大部分领域,如因果推理、不确定性知识表达、模式识别和聚类分析等,同时出现了专门研究贝叶斯理论的组织ISBA(IntemationalSoeietyofBayesianAnalysis)。
贝叶斯方法的特点是使用概率去表示所有形式的不确定性,学习或其他形式的推理都用概率规则来实现。贝叶斯理论在数据挖掘中的应用主要包括贝叶斯方法用于分类及回归分析、因果推理和不确定知识表达以及聚类模式发现等。贝叶斯方法正在以其独特的不确定性知识表达形式、丰富的概率表达能力、综合先验知识的增量学习特性等成为当前数据挖掘众多方法中最为引人注目的焦点之一。
贝叶斯统计是贝叶斯理论和方法的应用之一,其基本思想是:假定对所研究的对象在抽样前已有一定的认识,常用先验分布来描述这种认识,然后基于抽取的样本再对先验认识作修正,得到后验分布,而各种统计推断都基于后验分布进行。经典统计学的出发点是根据样本,在一定的统计模型下做出统计推断。在取得样本观测值X之前,往往对参数统计模型中的参数θ有某些先验知识,关于θ的先验知识的数学描述就是先验分布。贝叶斯统计的主要特点是使用先验分布,而在得到样本观测值TnxxxX),...,,(21后,由X与先验分布提供的信息,经过计算和处理,组成较完整的后验信息。这一后验分布是贝叶斯统计推断的基础。
1.2 贝叶斯统计模型
1.2.1 概率论中的贝叶斯公式
设事件A1,A2,„,Ak构成互不相容的完备事件组,则Bayes公式是
(1)
在上式中,先验信息以{P(Aj), j=1,2,…,k}这一概率分布的形式给出,即先验分布。由于事件B的发生,可以对A1,A2,„,Ak发生的概率提供新的信息。根据这些信息以及先验分布,可得出后验分布{P(Ai|B), i=1,2,..,k}.可以看出,Bayes公式反映了从先验分布向后验分布的转化。
1.2.2 数据挖掘中常用的贝叶斯公式
将(1)式中的随机变量的形式改写,引入随机变量θ,它的取值是θ1,θ2,…,θk,其中θj=θ(Aj),即当Aj发生时,θ取值θj,θ是离散型的(取有限值),具有先验分布π(θ):
B是另一随机事件,定义一个随机变量x,使得x=x(B)
式(l)中的P(B|Aj)可以表示为
它代表一种样本分布。这样式(l)可改写为
…(2)
2 算法实现
2.1 使用贝叶斯方法的数据挖掘算法综述
贝叶斯方法的一个显著特点是它可以通过看结果来了解假设,也就是说,在对先验知识知之甚少,或者毫不知情的情况下,贝叶斯方法具有其它方法不可比拟的长处。而数据挖掘技术的一个重要应用就是挖掘先前未知的知识,数据挖掘与传统的数据分析(如查询、报表、联机应用分析)的本质区别之一是数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的知识应具有先前未知,有效和实用三个特征。其中先前未知的信息是指该信息是预先未曾预料到的,即数据挖掘是要发现那些不能靠直觉发现的信息或知识,甚至是违背直觉的信息或知识,挖掘出的信息越是出乎意料,就可能越有价值。在商业应用中最典型的例子就是一家连锁店通过数据挖掘发现了小孩尿布和啤酒之间有着惊人的联系。正因为此,本文提出将贝叶斯方法应用于数据挖掘的算法,并对提出的算法进行了验证和讨论。
贝叶斯理论及方法在数据挖掘领域已有很多应用,且已有多种实现算法。其中,比较著名的算法有以下几类:
在把贝叶斯方法用于分类规则的挖掘算法中,比较著名的是贝叶斯信念构造算法。贝叶斯信念网络就是给定一个随机变量集χ={X1,X2,…,Xn},其中Xi是一个m维向量。贝叶斯信念网络了说明χ上的一条联合条件概率分布。贝叶斯信念网络定义如下:
B=
其中G是一个有向无环图,其顶点对应于有限集χ中的随机变量X1,X2,…,Xn.其弧代表一个函数依赖关系;θ代表用于量化网络的一组参数。实际上一个贝叶斯信念网络给定了变量集合χ上的联合条件概率分布:
贝叶斯信念网络构造算法可以表示如下:给定一组训练样本D={x1,x2,..,xn},xi是Xi的实例,寻找一个最匹配该样本的贝叶斯信念网络。常用的学习算法通常是引入一个评估函数S(B|D)(常用的评估函数如贝叶斯权矩阵及最小描述长度函数等),使用该函数来评估每一个可能的网络结构与样本之间的契合度,并从所有这些可能的网络结构中寻找一个最优解。
聚类分析的基本思想是在样品之间定义距离,在变量之间定义相似系数,距离或相似系数代表样品或变量之间的相似程度,按相似程度的大小,将样品或变量逐一归类,关系密切的类聚集到一个小的分类单位,然后逐步扩大,使得关系疏远的聚合到一个大的分类单位,直到所有的样品或变量都聚集完毕,形成一个表示亲属关系的谱系图,依次按照某些要求对某些样品或变量进行分类。聚类和分类的主要区别是,在进行聚类分析以前,对总体到底有几种类型并不知道,对已知数据分几类需在聚类的过程中探索调整,而分类是在事前已知道分为哪些类。贝叶斯方法用于聚类的挖掘算法目前并不广泛,目前主要是用简单贝叶斯学习模型来进行聚类。简单贝叶斯学习模型将训练实例I分解成特征向量X和决策类别变量C。简单贝叶斯模型假定特征向量的分量间相对于决策变量是相对独立的,也就是说各分量独立的作用于决策变量。尽管这一假定一定程度上限制了简单贝叶斯模型的适用范围,然而在实际应用中,不仅以指数级降低了贝叶斯网络构建的复杂性,而且在许多领域,在违背这种假定的条件下,简单贝叶斯也表现出相当的健壮性和高效性,它已经成功地应用到分类、聚类及模型选择等数据挖掘的任务中。简单贝叶斯学习模型:贝叶斯定理的应用之一就是如何通过给定的训练样本集预测未知样本的类别,预测依据就是取后验概率
最大的类别。设E是测试样本,P(Y|X)是在给定X情况下Y的条件概率。等式右侧的概率都是从样本数据中估计得到的。设样本表示成属性向量,如果属性对于给定的类别独立,那么P(A|Ci)分解成几个分量的积,即P(a1|Ci)·P(a2|Ci)···P(am|Ci),其中ai是样本E的第I个属性。从而后验概率的计算公式为
这个过程称为简单贝叶斯分类。
3 算法评价
3.1 各类方法的比较
3.1.1 决策树
决策树一般都是自上而下的来生成的。选择分割的方法有好几种,但是目的都是一致的:对目标类尝试进行最佳的分割。从根到叶子节点都有一条路径,这条路径就是一条“规则”。有些规则的效果可以比其他的一些规则要好。决策数方法最突出的优点是:
(1) 可以生成可以理解的规则;
(2) 计算量相对来说不是很大;
(3) 可以处理连续和种类字段;
(4) 决策树可以清晰的显示哪些字段比较重要。
分析不同的影响因素对分析目标的影响,找到关键的影响因素。决策树法的优点是直观,但随着数据复杂性的提高,其分支树也会增多,管理困难。而且很难基于多个变量组合发现规则。不同决策树分支之间的分裂也不平滑。另外,对连续性的字段比较难预测,而且当类别太多时,错误可能就会增加的比较快。一般的算法分类的时候,只是根据一个属性来分类。
3.1.2 关联分析方法
关联规则分析的优点是,可以产生清晰有用的结果,而且它的处理过程可以看到,处理起来相对也比较简单,因此它有一个其它方法不具有的长处是,到目前为止,用于发现关联规则的算法和应用都比较成熟。
关联规则本身也存在一些问题:
(1)支持度仅以出现次数为评价对象,可能忽略销售额大而次数很少的项目。
(2)分析出来的关系可能是随机的。
(3)置信度低的数据可能反映很重要的市场信息,可能是替代品或竞争产品。
3.1.3 神经网络
神经网络较贝叶斯方法及其它方法的优点是:大规模的并行处理和分布式的信息存储,良好的自适应、自组织性,以及很强的学习功能、联想功能和容错功能。与当今的冯.诺依曼式计算机相比,更加接近人脑的信息处理模式。主要表现如下:
(1)神经网络能够处理连续的模拟信号。例如连续灰度变化的图像信号。
(2)能够处理混沌的、不完全的、模糊的信息。
(3)传统的计算机能给出精确的解答,神经网络给出的是次最优的逼近解答
(4)神经网络并行分布工作,各组成部分同时参与运算,单个神经元的动作速度不高,但总体的处理速度极快。
(5)神经网络信息存储分布于全网络各个权重变换之中,某些单元障碍并不影响信息的完整,具有鲁棒性。
(6)传统计算机要求有准确的输入条件,才能给出精确解。神经网络只要求部分条件,甚至对于包含有部分错误的输入,也能得出较好的解答,具有容错性。
(7)神经网络在处理自然语言理解、图像模式识别、景物理解、不完整信息的处理、智能机器人控制等方面有优势。神经网络也有其不足之处。首先,神经网络对分类模型比较适合,但是,神经网络的隐藏层可以说是一个黑盒子,得出结论的因素并不十分明显。同时其输出结果也没有任何解释,这将影响结果的可信度及可接受程度。其次,神经网络需要较长的学习时间,因此当数据量很大时,性能可能会出现问题。
3.1.4 距离法进行分类和聚类
由于分类或聚类体系中的类别不是完全互斥的,存在这样一些既属于其中一个类别,又同时属于其它类别的数据,对于这种数据,分类或聚类算法无法确定数据所属的所有类别。因此,需要对每个类别确定闭值,当数据在该类的阈值之上时,就将数据归于该类中。
阈值的确定是十分困难的,理论上,没有很好的解决方法,一般采用预定初始值,然后给出测试数据,使用分类器进行分类或聚类,再根据分类或聚类的准确程度调整初始值,这样的方法有两个缺点:首先,初始值的确定不容易,完全是根据经验或简单的测试而定;其次,调整的幅度无法确定,当初始值过高或过低需要增减时,增减的幅度无法很好的确定,只能反复测试,反复调整,这样就大大地增加了工作量。
3.2 各方法的比较分析 但是,在运用贝叶斯方法之后,与未用贝叶斯方法而直接运用以上技术时,比较结果如下表。选择训练集和测试集的方法如下:选用大小为216K字节的以文本格式存储的一组数据,作为一个测试集,运行各类算法,分别执行几次分类操作,计算其效率和准确率,实验结果如表3.1所示:
表3.1 贝叶斯方法与其它方法的比较
(注:(l)和(2)对效率只考虑时间因素,而未考虑空间因素;(3)是由于所用的实验数据不是激光扫描仪测得的数据,因此与其它方法没有可比性,所以未在表中列出)
表3.1中,对于时间的计算是,在实现算法的程序运行之前和运行之后分别加一个取时间函数,所取得时间值相减即可得到算法执行的时间效率。对于准确率,采用下面公式计算:
由实验结果比较和分析可知,当用贝叶斯方法对小量数据进行分析时,比不用贝叶斯方法在执行时间上要多消耗一些,但是其准确率要高的多。
3.3 贝叶斯方法的不足
(1) 贝叶斯方法最有争议之处就是先验信息的使用。先验信息来源于经验或者以前的实验结论,没有确定的理论依据作支持,因此在很多方面颇有争议。由于很多工作都是基于先验信息的,如果先验信息不正确,或者存在误差,那么最后导致的结论就会是不可想象的。尤其是在数据挖掘中,挖掘出的知识也是不可预知的,就是说不知道挖掘出的知识是有用的还是无用的,甚至是错误的。虽然知识发现中有一步是进行知识评估,但是这种评估并不能总是知识的可用性和有效性,特别不能确定先验信息是否正确时,这种评估更带有不确定性。
(2) 处理数据复杂性高,因此时间和空间消耗也比较大。贝叶斯方法要进行后验概率的计算、区间估计、假设检验等,大量的计算是不可避免的。
4 算法应用
4.1 聚类算法
聚类分析的基本思想是认为所研究的数据集中的数据或者属性之间存在着程度不同的相似性。于是从数据集中取出一批数据,具体找出一些能够度量数据