基于贝叶斯方法的Q型聚类算法研究.doc

3基于贝叶斯方法的 q 型聚类算法研究余丽(武汉理工大学信息工程学院 武汉430070)摘 要 聚类分析根据类对象划分为 q 型聚类和 r 型聚类 ,基于贝叶斯方法的 q 型聚类算法 ,详细说明该算法的基本思想和具体实现过程 。实验结果表明算法的可行性 ,该算法对于数据挖掘具有一定的参考价值 。关键词 数据挖掘 聚类分析 贝叶斯中图分类号tp274 +. 2mk1 / k( 3 )汉明距离 : dk ( x i , x j ) = | xit - xjt |1 引言数据挖掘中常用的聚类方法有划分聚类算法 、 层次聚类算法 、基于密度的聚类算法 、基于网格的 聚类算法 、基于模型 的聚 类 算法 以及 模 糊聚 类算 法 ,贝叶斯方法的显著特点是它可以通过结果来了 解假设 ,在对先验知识知之甚少的情况下 ,贝叶斯 方法具有以上聚类方法不可比拟的长处 。而数据 挖掘就是要挖掘先前未知的知识 ,具有先前未知 、 有效和实用三个特征 。因此 ,本文介绍将贝叶斯方 法应用于数据挖掘的聚类分析中 。t = 1( 3 )3 数据挖掘中常用的贝叶斯公式设事件 a1 , a2 , a3 ak 构成互不相容的完备事件组 , p (a j ) , j = 1, 2k 表示先验分布 , 由于事件 b 的发生 , 可以对 a1 , a2 , a3ak 发生的概率提供新的信息 , p (a i | b ) , i = 1, 2k 表示后 验分布 。则概率论中的贝叶斯公式为 :p (b | a i ) p (a i )p (a |b ) =( 4 )ikp (b |a j ) p (a j )2 聚类分析聚类分析的基本思想是认为所研究的数据集 中的数据或者属性之间存在着程度不同的相似性 。 从数据集中取出一批数据 ,具体找出一些能够度量 数值之间或者属性之间的相似程度的量 ,以这些量 为中心作为划分类型的依据 ,把一些相似程度较大 的数据或属性聚为一类 ,把另外一些彼此之间相似 程度较大的样品又聚合为另一类 ,关系密切的聚合 到一个小的分类单位 ,关系疏远的聚合到一个大的 分类单位 ,直到所有的数据或者属性都聚合完毕 。聚类的实质是使属于同一类别的个体之间的 距离尽可能小 ,而不同类别的个体之间距离尽可能大 。因此需要用到各种不同的距离度量来判定类 别 。比较常用的距离公式有 :( 1 )绝对值距离 :j = 1用随机变量的形式改写公式 ( 4 ) 并引入离散型随机变量 , 它的取值是 1 , 2 ,k , 其中 ,3j=( a , 表示的是当 a 发生时 ,的取值为 j )j , 先j验分布 ()为 : () = p (=) = p (a )jjjb 是另外一个随机变量 , 定义一个随机变量 x, x= x (b ) ,则公式 ( 4)中的 p (b |a j )表示为 p ( x |j ) ,即 :p (b |a j ) = p ( x |j ) = p ( x |=j ) j = 1, 2那么 , 根据公式 ( 4 ) , 可以得到 : p (i | x ) = p (=i | x ) p ( x |i ) (i ) k。= kp ( x |j ) (j )j = 1i = 1, 2( 5 )k4 基于贝叶斯方法的聚类算法聚类分析通常根据类对象的不同分为 q 型和 r 型两大类 , q 型是对数据集中的数据值进行分类 处理 , r 型是对属性进行分类处理 。本文研究的是p( 1 )dij = xik- xjkk = 1p21 / 2( 2 )欧氏距离 : dij = ( xik- xjk )( 2 )k = 13 收到本文时间 : 2006年 9月 11日作者简介 :余丽 ,女 ,硕士研究生 ,研究方向 :信息系统理论与技术q 型聚类 。根据贝叶斯方法和 q 型聚类的基本思想设计 如下算法 :第一步 :确立聚类中心数据值 ;第二步 :以聚类中心数据为聚类依据 , 根据先 验信息假定出分布 () , () 即为先验分布 , 并作为贝叶斯公式的先验概率 ;第三步 :调用聚类算法进行聚类 ,具体算法如下 :的数据 ,从每组数据中抽取十条记录得到表 1、表 2。由于建筑物表面凹凸不平 ,被测量的点位于不 同的平面 ,聚类的要求是把位于同一垂直平面上的 点聚为一类 。6结束语实 验 结 果 表明算法是可行的 。设聚类中心对应的类为聚类的数据样本为 t1 , t2 , t3c1 , c2 , c3cm , 需要在对 先 验 知 识 知之甚少的情况下 ,贝叶 斯 方 法 具 有 其他 聚 类 方 法 不可比拟的长处 。在该算法中 , 需要确定阈值 ,本 文采 用 的 方 法 是先预定初始值 ,然 后给出测试数据 , 再根 据 算 法 进 行 聚 类 。这 种 方 法 根据 经 验 或 者 简单的测试而定 ,调 整的 幅 度 不 好 确 定 ,需要反复测试 调整 ,工作量比较 大 ,进一步的工作 是研 究 高 效 率 的( m , n 均为正整tn ,数 ) c1 , c2 , c3cm 均为集合 。( 1 ) 设 某 一 聚 类 中 心 数 据 为c1 , 则 c1 = t1 。( 2 )对样本数据中的任一数据t1 , 相 应 的 类 为ti ( 1 i n ) , 按照公式 ( 1 ) 、( 2 ) 或 ( 3 ) 进行距离的运算 , 设所得到的距离值为 d,ifd 聚类阈值f, th enc1 = c1 ti = t1 , ti end if( 3 )转到第 ( 2 )步 。第四步 :根据公式 (5)计算出聚类后的后验概率 。 第五步 :用第四步得到的后验概率作为检验聚类结果的标准 。若符合用户的要求 , 则整个算法过 程结束 ; 否则就需要修改先验分布的部分参数或重 新确立新的先验分布 , 直到所得到后验概率符合用户的要求 。5 实验结果确定阈值的方法 。表 1:第一组表 2:第二组所以 在 恰 当 选 择阈值的条件下 ,本 文提 出 的 贝 叶 斯图 1 表 示的是处理之前 各 点 的 分 布图 。在执行算法 的 过 程 中 , 阈值表示的是 两个测量点之间 的 欧 氏 距 离 , 取阈值 f = 0. 0007, 当 d f 时点聚为一类 。执 行聚类算法后 , 得到的聚类结果如图 2。多次测量某点到一建筑物的距离 ,得到两组距离图 2 聚类结果聚类算法 ,对数据挖掘算法的研究具有一定的参考价值 。参 考 文 献 1 史忠植 . 知识发现 m . 北京 :清华大学出版社 , 2002. 2 吕 锋 ,陈华胜 . 关联算法的改进及其在审计数据挖掘 中的应用 j . 武汉理工大学学报 . 2004 , 26 , 59. 3 冀俊忠 ,刘椿年 ,沙志强 . 贝叶斯网模型的学习 、推理和应用 j . 计算机工程与应用 , 2003, 513, 2428. 4 宫秀 军 , 刘 少 辉 , 史 忠 植 . 一 种 增 量 贝 叶 斯 分 类 模 型 j . 计算机学报 , 2002, 256 , 645650.re sea rch on the a da p t ive a lgor ithm for non un iform ityc orrec t ion of in fra red foca l p lan e a rra y ba sed on tem 2svd , p ro po s ing a n ew w a te rm a rk a lgo rithm ba se d o nw ave le t an d s in gu la r va lu e d e com p o s itio n (w - svd ) , n am e ly ca rrie s o n th e s in gu la r va lu e d e com p o s itio n in th e fo un da tio n o f th e w a ve le t de com po se s. the e xp e rim e n t p ro ve d th a t, th e im p ro ve d w a te rm a rk a lgo rithm no t o n ly m a in ta in s the s tro n g a n ti - g eom e try d is to rtio n ab ility b u t a lso g re a tly e nh a nc e s th e ro bu s tne s s to th e a tta ck s suc ha s sa lt, ga u s s , f ilte r a n d e tc.pora l h igh pa ss f ilterby s h i changchenga b stra c t it w a s th e m o s t im p o rta n t go a l fo r a n inf ra re dd e te c t in g sy s tem to re a lize a dap t ive no n un ifo rm ity co r2 re c t io n o f in f ra re d fo ca l p la ne a rra y ( ir fpa ) w h ic h is a l2 so s ign if ica n t to im p ro ve sp a tia l re so lu tio n , tem p e ra tu re re so lu tio n , d e te c t in g d is ta nc e a nd rad iom e tric a c cu ra cy. the v isua l n e u ra l m e c ha n ism an d f re q ue nc y c h a ra c te ris2 tic o f th e tem po ra l h igh p a s s f ilte r no n un ifo rm ity co rre c2 tio n te c h n iqu e fo r inf ra re d fo c a l p la ne a rra y w e re s tu d2 ie d. the e xp e rim e n ts w ith re a l in f ra re d im ag e show e d th a t the m o s t im p o rta n t fa c to r o f th is no nu n ifo rm ity co r2 re c t io n a lgo rithm w a r the tim e co n s ta n t.key word s in f ra re d fo ca l p la ne a rray, no nu n ifo rm ity, a2d ap tive co rre c tio n a lgo rithm , tem po ra l h igh p a s s f ilte r( pa ge : 1)key word sw a ve le t; s ing u la r va lue de com po s it io n( svd ) ; ro bu s t; w a te rm a rk in g a lgo rithm( pa ge : 10 )pa ra lle l hybr id gen e t ic s im u la ted ann ea l in g a lgor ithmba sed on n ich in gby w ang w eichuna b stra c t a n ew p a ra lle l o p tim iza tio n m e tho d b a se d o nn ic h ing h yb rid ge ne tic s im u la te d a n ne a lin g a lgo rithm is p rop o se d in th is p ap e r. a nd th e n ew m e tho d s fe a tu re s a re d isc u s se d. the n it is ap p lie d to th e s hu be rt fu nc tio n ,a rep re se n ta tive m u lti - m o d e l o p tim iza tio n p ro b lem . th e e xp e rim e n ta l re su lts ve rify tha t th e p ro po se d p a ra lle l m e tho d im p ro ve s the co n ve rge nc e e ff ic ie n cy, e n ha nc e s th e a b ility o f g lo ba l se a rc h ing.key word s p a ra lle l e vo lu tio n a ry a lgo rithm , n ic h ing , g e 2d na sequen ce d e s ign ba sed on hybr id ized s im u la ted an 2n ea l in g gen e t ic a lgor ithmby cu i guangzhaoa b stra c t f irs tly, th is p ap e r se t s up th e m a th em a t ic sm o d e l by an a lyz in g the o b je c tive o f th e dna se q ue nc e d e s ig n p ro b lem an d the re s tric tio n s tha t sho u ld be sa tis2 f ie d a nd p re se n t a n ew se q ue nc e d e s ig n m e tho d - h y2 b rid ize d s im u la te d an ne a lin g an d ge ne tic a lgo rithm( h sa ga ) . th e h yb rid a lgo rithm ho ld s the se rie s - p a ra l2le l s truc tu re , tha t e nh a nc e its ab ility to o b ta in th e o p tim a l so lu tio n in th e w ho le so lu tio n sp a ce. w e d e s ig n th e d e 2 ta il o f th e a lgo rithm a nd g e t a se t o f se q ue nc e s w ith h ig he r qu a lity.key word s e n co d in g p ro b lem , hyb rid ize d s im u la te d a n2( pa ge : 13 )n e tic a n ne a lin g , s im u la te d a nn e a lin gs tudy on ba ye s ian m e thod in q - type c lu ster in g a lgo2r ithmby yu l ia b stra c t a cco rd in g to th e o b je c t d a ta , c lu s te rin g a na ly2s is c an be ca te go rize d in to tw o g ro up s: r - typ e an d q- typ e. th is p ap e r s tu d ie s o n q - typ e c lu s te rin g a lgo 2 rithm s ba se d o n b a ye s ia n m e tho d , p a rtic u la rly in tro 2 d uc e s th e b a s ic id e a s an d d e ta ile d im p lem e n t co u rse o f th is a lgo rithm . exp e rim e n ta l re su lts show th e a va ila b ility o f the a lgo rithm , an d it h a s som e re fe re n c e va lu e fo r th es tud y o f d a ta m in in g.key word s da ta m in in g , c lu s te rin g a na ly s is , b a ye s ia nh am m ing d is tan ce , s im i2( pa ge : 4)n e a ling a nd g e ne t ic a lgo rithm ,la rityre sea rch in gjpeg2000ro i en cod in ga r ithm e t ic ba sed onby peng h a i( pa ge : 16 )m e tho da b stra c t j p eg2000 is the la te s t com p re s s io n s ta nd a rd ,a nd th e ro i( r e g io n o f in te re s t) is a n ew c ha ra c te r o f it. th is p ap e r in tro d uc e s th e g e n e ra l sc a lin g m e tho d an d th e m ax im um sh if t m e tho d w h ich a re de f in e d in th ej peg2000 s tan da rd. b u t th e s t tw o m e tho d s ha ve d e 2fe c t s. so th e p ap e r a g a in d e sc rib e s th e m e n de d a rithm e 2tic the p a rt b ac k g ro u nd co e ff ic ie n t p la n t sh if t m e tho d a nd th e p a rt ro i co e ff ic ie n t p la n t sh if t m e tho d , a n d a tla s t th e a rithm e tic va lida te an d th e com p a riso n re su lt a reg ive n.a pp l ica t ion of a r t if ic ia l imm un e a lgor ithm in robo t pa thp lann in gby yan l ilia b stra c t a rt if ic ia l im m un e a lgo rithm is a no ve l o p tim iza2tio n a lgo rithm , it is ap p lie dcom p u ta t io n a nd co n t ro .l inin d iffe re n t f ie ld s suc h a sth is p ap e r, th e im m un e a l2go rithm is app lie d in ro bo t p a th p la nn in g , a n a rtif ic ia l im 2 m un e a lgo rithm is p ro po se d fo r m o b ile ro bo t s p a th p la n2 n in g in the com p le x la yo u ts e n v iro nm e n ts w ith a rb it ra ry p o lygo n o b s ta c le s. b y s im u la tio n s tu d ie s , it is dem o n2 s tra te d tha t th e p ro po se d a lgo rithm ca n f in d a g lo ba l op ti2 m a l p a th an d c a n be u se d to d iffe re n t com p le x e n v iro n2 m e n ts.key word s m o b ile ro bo t, p a th p