基于貝葉斯方法的Q型聚類算法研究

1、3基于貝葉斯方法的 q 型聚類算法研究余麗(武漢理工大學信息工程學院 武漢430070)摘 要 聚類分析根據(jù)類對象劃分為 q 型聚類和 r 型聚類 ,基于貝葉斯方法的 q 型聚類算法 ,詳細說明該算法的基本思想和具體實現(xiàn)過程 。實驗結(jié)果表明算法的可行性 ,該算法對于數(shù)據(jù)挖掘具有一定的參考價值 。關鍵詞 數(shù)據(jù)挖掘 聚類分析 貝葉斯中圖分類號tp274 +. 2mk1 / k( 3 )漢明距離 : dk ( x i , x j ) = | xit - xjt |1 引言數(shù)據(jù)挖掘中常用的聚類方法有劃分聚類算法 、 層次聚類算法 、基于密度的聚類算法 、基于網(wǎng)格的 聚類算法 、基于模型 的聚 類 算法

2、 以及 模 糊聚 類算 法 ,貝葉斯方法的顯著特點是它可以通過結(jié)果來了 解假設 ,在對先驗知識知之甚少的情況下 ,貝葉斯 方法具有以上聚類方法不可比擬的長處 。而數(shù)據(jù) 挖掘就是要挖掘先前未知的知識 ,具有先前未知 、 有效和實用三個特征 。因此 ,本文介紹將貝葉斯方 法應用于數(shù)據(jù)挖掘的聚類分析中 。t = 1( 3 )3 數(shù)據(jù)挖掘中常用的貝葉斯公式設事件 a1 , a2 , a3 ak 構(gòu)成互不相容的完備事件組 , p (a j ) , j = 1, 2k 表示先驗分布 , 由于事件 b 的發(fā)生 , 可以對 a1 , a2 , a3ak 發(fā)生的概率提供新的信息 , p (a i | b ) ,

3、 i = 1, 2k 表示后 驗分布 。則概率論中的貝葉斯公式為 :p (b | a i ) p (a i )p (a |b ) =( 4 )ikp (b |a j ) p (a j )2 聚類分析聚類分析的基本思想是認為所研究的數(shù)據(jù)集 中的數(shù)據(jù)或者屬性之間存在著程度不同的相似性 。 從數(shù)據(jù)集中取出一批數(shù)據(jù) ,具體找出一些能夠度量 數(shù)值之間或者屬性之間的相似程度的量 ,以這些量 為中心作為劃分類型的依據(jù) ,把一些相似程度較大 的數(shù)據(jù)或?qū)傩跃蹫橐活?,把另外一些彼此之間相似 程度較大的樣品又聚合為另一類 ,關系密切的聚合 到一個小的分類單位 ,關系疏遠的聚合到一個大的 分類單位 ,直到所有的數(shù)據(jù)

4、或者屬性都聚合完畢 。聚類的實質(zhì)是使屬于同一類別的個體之間的 距離盡可能小 ,而不同類別的個體之間距離盡可能大 。因此需要用到各種不同的距離度量來判定類 別 。比較常用的距離公式有 :( 1 )絕對值距離 :j = 1用隨機變量的形式改寫公式 ( 4 ) 并引入離散型隨機變量 , 它的取值是 1 , 2 ,k , 其中 ,3j=( a , 表示的是當 a 發(fā)生時 ,的取值為 j )j , 先j驗分布 ()為 : () = p (=) = p (a )jjjb 是另外一個隨機變量 , 定義一個隨機變量 x, x= x (b ) ,則公式 ( 4)中的 p (b |a j )表示為 p ( x |

5、j ) ,即 :p (b |a j ) = p ( x |j ) = p ( x |=j ) j = 1, 2那么 , 根據(jù)公式 ( 4 ) , 可以得到 : p (i | x ) = p (=i | x ) p ( x |i ) (i ) k。= kp ( x |j ) (j )j = 1i = 1, 2( 5 )k4 基于貝葉斯方法的聚類算法聚類分析通常根據(jù)類對象的不同分為 q 型和 r 型兩大類 , q 型是對數(shù)據(jù)集中的數(shù)據(jù)值進行分類 處理 , r 型是對屬性進行分類處理 。本文研究的是p( 1 )dij = xik- xjkk = 1p21 / 2( 2 )歐氏距離 : dij = (

6、 xik- xjk )( 2 )k = 13 收到本文時間 : 2006年 9月 11日作者簡介 :余麗 ,女 ,碩士研究生 ,研究方向 :信息系統(tǒng)理論與技術q 型聚類 。根據(jù)貝葉斯方法和 q 型聚類的基本思想設計 如下算法 :第一步 :確立聚類中心數(shù)據(jù)值 ;第二步 :以聚類中心數(shù)據(jù)為聚類依據(jù) , 根據(jù)先 驗信息假定出分布 () , () 即為先驗分布 , 并作為貝葉斯公式的先驗概率 ;第三步 :調(diào)用聚類算法進行聚類 ,具體算法如下 :的數(shù)據(jù) ,從每組數(shù)據(jù)中抽取十條記錄得到表 1、表 2。由于建筑物表面凹凸不平 ,被測量的點位于不 同的平面 ,聚類的要求是把位于同一垂直平面上的 點聚為一類 。

7、6結(jié)束語實 驗 結(jié) 果 表明算法是可行的 。設聚類中心對應的類為聚類的數(shù)據(jù)樣本為 t1 , t2 , t3c1 , c2 , c3cm , 需要在對 先 驗 知 識 知之甚少的情況下 ,貝葉 斯 方 法 具 有 其他 聚 類 方 法 不可比擬的長處 。在該算法中 , 需要確定閾值 ,本 文采 用 的 方 法 是先預定初始值 ,然 后給出測試數(shù)據(jù) , 再根 據(jù) 算 法 進 行 聚 類 。這 種 方 法 根據(jù) 經(jīng) 驗 或 者 簡單的測試而定 ,調(diào) 整的 幅 度 不 好 確 定 ,需要反復測試 調(diào)整 ,工作量比較 大 ,進一步的工作 是研 究 高 效 率 的( m , n 均為正整tn ,數(shù) ) c

8、1 , c2 , c3cm 均為集合 。( 1 ) 設 某 一 聚 類 中 心 數(shù) 據(jù) 為c1 , 則 c1 = t1 。( 2 )對樣本數(shù)據(jù)中的任一數(shù)據(jù)t1 , 相 應 的 類 為ti ( 1 i n ) , 按照公式 ( 1 ) 、( 2 ) 或 ( 3 ) 進行距離的運算 , 設所得到的距離值為 d,ifd 聚類閾值f, th enc1 = c1 ti = t1 , ti end if( 3 )轉(zhuǎn)到第 ( 2 )步 。第四步 :根據(jù)公式 (5)計算出聚類后的后驗概率 。 第五步 :用第四步得到的后驗概率作為檢驗聚類結(jié)果的標準 。若符合用戶的要求 , 則整個算法過 程結(jié)束 ; 否則就需要修

9、改先驗分布的部分參數(shù)或重 新確立新的先驗分布 , 直到所得到后驗概率符合用戶的要求 。5 實驗結(jié)果確定閾值的方法 。表 1:第一組表 2:第二組所以 在 恰 當 選 擇閾值的條件下 ,本 文提 出 的 貝 葉 斯圖 1 表 示的是處理之前 各 點 的 分 布圖 。在執(zhí)行算法 的 過 程 中 , 閾值表示的是 兩個測量點之間 的 歐 氏 距 離 , 取閾值 f = 0. 0007, 當 d f 時點聚為一類 。執(zhí) 行聚類算法后 , 得到的聚類結(jié)果如圖 2。多次測量某點到一建筑物的距離 ,得到兩組距離圖 2 聚類結(jié)果聚類算法 ,對數(shù)據(jù)挖掘算法的研究具有一定的參考價值 。參 考 文 獻 1 史忠植

10、. 知識發(fā)現(xiàn) m . 北京 :清華大學出版社 , 2002. 2 呂 鋒 ,陳華勝 . 關聯(lián)算法的改進及其在審計數(shù)據(jù)挖掘 中的應用 j . 武漢理工大學學報 . 2004 , 26 , 59. 3 冀俊忠 ,劉椿年 ,沙志強 . 貝葉斯網(wǎng)模型的學習 、推理和應用 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 ifor

11、m 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

12、 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,

13、 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

14、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

15、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 t

16、a 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

17、 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

18、 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

19、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

20、 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

21、 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

22、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

23、 , 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

24、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

25、 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

26、 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 2t

27、ic 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 ro

28、bo 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 n

29、n 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