贝叶斯方法在聚类中的应用

1 算法介绍

1.1 贝叶斯方法的基本观点

托马斯·贝叶斯(ThomasBayes)是英国数学家，他对贝叶斯方法奠基性的工作是他的论文“关于几率性问题求解的评论”。由于当时贝叶斯方法在理论和应用中还存在很多不完善的地方，因此在很长一段时间并未被普遍接受。后来随着统计决策理论、信息论和经验贝叶斯方法等理论和方法的创立和应用，贝叶斯方法很快显示出它的优点，成为十分活跃的一个方向。随着人工智能的发展尤其是机器学习、数据挖掘的兴起，贝叶斯理论的发展和应用也获得了更为广阔的空间。近年来，贝叶斯学习理论方面的文章更是层出不穷，内容涉及到人工智能的大部分领域，如因果推理、不确定性知识表达、模式识别和聚类分析等，同时出现了专门研究贝叶斯理论的组织ISBA(IntemationalSoeietyofBayesianAnalysis)。

贝叶斯方法的特点是使用概率去表示所有形式的不确定性，学习或其他形式的推理都用概率规则来实现。贝叶斯理论在数据挖掘中的应用主要包括贝叶斯方法用于分类及回归分析、因果推理和不确定知识表达以及聚类模式发现等。贝叶斯方法正在以其独特的不确定性知识表达形式、丰富的概率表达能力、综合先验知识的增量学习特性等成为当前数据挖掘众多方法中最为引人注目的焦点之一。

贝叶斯统计是贝叶斯理论和方法的应用之一，其基本思想是：假定对所研究的对象在抽样前已有一定的认识，常用先验分布来描述这种认识，然后基于抽取的样本再对先验认识作修正，得到后验分布，而各种统计推断都基于后验分布进行。经典统计学的出发点是根据样本，在一定的统计模型下做出统计推断。在取得样本观测值X之前，往往对参数统计模型中的参数θ有某些先验知识，关于θ的先验知识的数学描述就是先验分布。贝叶斯统计的主要特点是使用先验分布，而在得到样本观测值X (x1,x2,...,xn)T后，由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,θ>

其中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 聚类算法

聚类分析的基本思想是认为所研究的数据集中的数据或者属性之间存在着程度不同的相似性。于是从数据集中取出一批数据，具体找出一些能够度量数据

贝叶斯方法在聚类中的应用

值之间或者属性之间相似程度的量，以这些量为中心作为划分类型的依据，把一些相似程度较大的数据或属性聚合为一类，把另外一些彼此之间相似程度较大的样品又聚合为另一类，关系密切的聚合到一个小的分类单位，关系疏远的聚合到一个大的分类单位，直到所有数据或属性都聚合完毕，把不同的类型一一划分出来。

聚类的实质就是使属于同一类别的个体之间的距离尽可能地小，而不同类别的个体间的距离尽可能地大。因此需要用到各种不同的距离度量测度来判定类别。有多种距离公式，比较常用的距离有：

绝对值距离

欧氏距离

明斯基距离

聚类分析通常根据类对象的不同分为Q型和R型两大类。Q型是对数据集中的数据值进行分类处理，R型是属性进行分类处理。Q型聚类分析的优点主要是：

(1)可以综合多个属性的信息对数据值进行分类；

(2) 分类结果是直观的，用一个分类谱系图就能非常清楚的表现其数值分类结果；

(3) 聚类分析所得到的结果比传统的分类方法更细致、全面、合理。

本文也主要讨论Q型聚类问题，即直接对数据值进行聚类。

下图是一个简单的聚类直观的图形表示，其中聚类中心分别为(l，2)和(5，

3)

图4.1.1 以(1，2)和(5，3)为中心的两类

贝叶斯方法在聚类中的应用

由于贝叶斯方法的主要特点是通过先验信息来推得后验知识，如果将贝叶斯方法进行聚类，其基本思想就是：

首先根据先验信息假定数据集中可能要聚为一类的数据服从某种分布，再用某种距离测度检验先验信息给出的这种分布是否符合聚为一类的要求。如果达不到聚类的要求，则根据计算概率找出不符合要求的原因，重新确定其分布，或修正此分布的参数，以获得更准确的分布。

具体分析一下与聚类相关的问题：给定数据集，它满足以下两个条件

(1) 类的数目是未知的；

(2) 有哪些类是未知的。

与这两个条件相对应，聚类的目的是：

(1) 确定一些合适的聚类中心；

(2) 弄清类的数目k；

(3) 发现合理的聚类方法；

(4) 把数据分类到k个类别中。

针对聚类的问题及其目的，设计完整的算法如下：

STEP1：确定聚类中心数据，即围绕哪些数据进行聚类；

STEP2：对每一确定的以聚类中心数据为聚类依据的类，根据先验信息假定其分布π(θ)，作为贝叶斯公式的先验概率：

STEP3：调用聚类算法进行聚类；对于每一类i和数据，根据下面公式来计算聚类后的后验概率；

STEP4：用贝叶斯公式的后验概率检验聚类结果。如果结果符合用户要求，则算法结束；否则，重新确定其分布，或修正其参数。

其中上面算法的STEP3的聚类算法如下：

(1) 给定集合C=φ，设某一聚类中心数据为x，则C={x}；

(2) 对数据集中每一数据t进行距离计算，所得值记为d。

IF d ≤聚类阀值 THEN

C=C∪{t}

ENDIF

(3) 转(2)。

算法流程如下图

贝叶斯方法在聚类中的应用

图4.1.2聚类算法流程图

4.2 算法应用

数据来源于激光扫描仪扫描物体获得的数据。用车载激光扫描仪扫描建筑物，汽车向前行进过程中，扫描仪不断旋转，并且每隔一段时间把扫描获取的数据通过传感器传送到计算机，计算机把数据以某种格式存储起来。然后对这些数据进行格式转换，转换为ASCII格式，以方便程序处理。这样数据就以文本方式存储。

在应用此算法之前，先取存储容量为26.1MB的一个数据文件来验证此聚类算法。

聚类的要求：由于扫描仪扫描时以与地面垂直的方向旋转，要把水平方向上的点聚为一类，也就是要对同一横面上的点聚类。这里的横面并不是整个建筑物的同一水平面上的完整的一条直线，而是根据建筑物表面的凹凸不同来聚类。

如下图，激光扫描仪位于相距建筑物一定距离处，旋转扫描建筑物的表面，由于扫描是以垂直于地面的方向扫描，而要求找出平行于地面的横面点，因此就需要对扫描所得的数据进行聚类。

图4.2.1激光扫描仪扫描建筑物示意图

贝叶斯方法在聚类中的应用

下面四个表是激光扫描仪扫描一建筑物时旋转四次所测得数据的一部分，每一部分分别取10个点。运用上述算法聚类出结果。

表4.2.1 表

4.2.2

表4.2.3 表4.2.4

下面的图即为上述四个表中数据的模拟图：图4.2.2表示处理之前的各点分 布图；图4.2.3表示由算法处理之后所获取的点。

图4.2.2处理之前的各节点

贝叶斯方法在聚类中的应用

要取得同一截面上的点，按下面公式进行聚类

t=Cos(距离*(角度*0.9*π/180))

d=|ti-ti+1|

取阈值f=0.007，则当d≤f时的点聚为一类。

执行聚类算法后各类中的图示如下图：

图4.2.3处理之前的各节点

5 朴素贝叶斯分类模型的改进方法

朴素贝叶斯分类器是基于一个简单的假定:在给定分类特征条件下属性值之间是相互条件独立的。在现实世界中，它的属性独立性假设使其无法表示实际应用中各属性之间的依赖关系，影响了它的分类性能。因此需要针对实际应用对朴素贝叶斯分类器模型进行改进，使之在属性独立性假设不满足的情况下依然具有较高的分类精确度。

通过分析，朴素贝叶斯分类器的本质是一种具有很强限制条件的贝叶斯网络分类器，由于它限制条件太强，不适于现实应用。然而完全无限制条件的贝叶斯网络也是不现实的，因为这样的网络在学习时非常耗时，其时间复杂度为属性变量的指数级，并且空间复杂度也非常高。因此，许多学者从事于研究朴素贝叶斯分类器的改进模型，大多数研究具有较宽松条件限制的贝叶斯网络分类器。众多的研究策略可归纳为以下几个方面：

5.1基于属性间的关系

(1)属性分组技术

Kononcnko提出一种采用穷尽搜索的属性分组技术假定同个组内的属性之间可能是相互依赖的，但是组与组之间是满足独立性假设的属性集合。也就是说，独立性假设弱化为这些属性组之间的独立性。但是，这种算法的复杂性远远高于朴索贝叶斯分类器，而且在现实世界中，属性可以完全被分成独立的子集合只是少数情况。

(2)属性删除技术

贝叶斯方法在聚类中的应用

适用于存在冗余属性的情况。

Langley和Sage提出了种基于属性删除的选择性贝叶斯分类器。当存在一些属性依赖于其他属性，特别是存在冗余属性时，属性删除方法确实能够改善朴素贝叶斯分类器的预测精确度。

(3)局部朴素贝叶斯分类器

适用于属性之间依赖的情形比较复杂的情况。

这种方法是为属性变量的每种取值(或某个范围)建立一个朴索贝叶斯分类器。也就是说，单一的全局朴素贝叶斯分类器被许多局部朴索贝叶斯分类器所代替，将属性独立性假设放宽到只要局部属性独立就可以了。Kohavi将朴素贝叶斯分类器和决策树相结合，用一棵决策树来分割实例空间，在每个叶子结点上建立局部朴索贝叶斯分类器。Zhang和Webb等利用懒惰式学习策略提出了一种懒隋式贝叶斯规则(LazyBayasian Rule, LBR)和学习技术，该方法将懒惰式技术应用到局部朴素贝叶斯规则的归纳中。该算法虽然较大地提高了分类精确度，但是效率很低。为了提高LBR的效率，Wang和Webb给出了一种启发式LBR算法HLBR,可以有效地提高学习效率。LBR和HLBR是目前该方向上的最新研究成果之一。

(4)构造新属性或概率调整技术

适用于某些属性依赖于其他属性的情形。

Pazzani等提出了通过相互依赖的属性构造一个新属性，并用新属性取代原来相互依赖的那些属性的方法这种方法也可以视作为事先的条件概率调整技术。Wang和Webb等提出了一种准懒隋式(Semi- Lazy)的限制性贝叶斯网络分类器的条件概率调整方法，在某些情况下可以减小误分类率。

(5)建立依赖关系技术

适用于属性之间相互依赖的情形比较复杂的情况。

Friedman等提出了一种树扩张型贝叶斯方法(Tree-Augmented Baycsian Classifier,TAN)。这种方法的基本思路是放宽朴素贝叶斯的独立性假设条件，扩展朴素贝叶斯的结构，使其能够容纳属性间存在具有某种特征的依赖关系。Friedman利用条件相互信息(Conditional Mutual Information)建立属性之间的依赖关系矩阵，构造一棵最大权生成树作为个分类器。由于TAN限制每个属性结点最多有一个非类变量(类标)的父结点，也就是说每个属性结点最多仅依赖于一个非类标结点，使其表示依赖关系的能力受到限制。

5.2整体分类技术

(1)懒惰式学习策略

懒惰式(Lazy)学习策略相对于急切式(Eager)学习策略的不同之处在于，前者是在分类时间，对于每个来分类的实例，临时建立起个分类器来进行分类;后者是在训练时间就先行建立了分类器，在分类时间上分类所有要分类的实例。

一般而言，对于同种模型技术，懒惰式学习策略在分类精度上优于急切式学习策略，但是在学习效率上却大大劣于急切式学习策略。

(2) 显现模式技术

显现模式技术（emerging patterns）是指在数据集合中表现活跃的部分属性值组合序列，将显现模式技术到分类器的构造中是一种新的研究方法。 结束语