屬性分布相似度吸引子傳播聚類算法研究

王依章， 王麗敏＊， 韓旭明

（1.吉林財(cái)經(jīng)大學(xué)管理科學(xué)與信息工程學(xué)院，吉林長(zhǎng)春 130117；2.長(zhǎng)春工業(yè)大學(xué)軟件學(xué)院，吉林長(zhǎng)春 130012）

0 引 言

吸引子傳播聚類算法是美國(guó)學(xué)者Frey2007年在《Science》雜志上提出的一種新聚類算法。目前，該算法已成功應(yīng)用于圖像分割［1－2］、圖像檢索［3］、基因識(shí)別［4］、文本聚類［5］、最優(yōu)航空路線確定［6］等諸多領(lǐng)域。近年來，國(guó)內(nèi)外學(xué)者提出多種改進(jìn)方法。例如國(guó)外學(xué)者Bruzzone L［7］等提出吸引子傳播算法應(yīng)用于多光譜圖像領(lǐng)域，Qasim I［8］等把該算法應(yīng)用在文本概念圖自動(dòng)生成領(lǐng)域，取得了顯著的應(yīng)用效果。國(guó)內(nèi)學(xué)者于吉紅［9］等提出用空間向量模型計(jì)算特征相似度，并應(yīng)用于艦船三維模型進(jìn)行視點(diǎn)空間均勻投影。張震［10］等提出將吸引子傳播算法與數(shù)據(jù)流聚類相結(jié)合，改良了數(shù)據(jù)流聚類模型。文中根據(jù)屬性間分布相似度提出改進(jìn)算法，提高對(duì)高維稀疏數(shù)據(jù)的聚類性能，并應(yīng)用于超市銷售數(shù)據(jù)聚類。

1 吸引子傳播聚類算法

吸引子傳播聚類算法利用數(shù)據(jù)點(diǎn)之間的相似度構(gòu)造相似度關(guān)系矩陣S［11］。相似度是兩點(diǎn)間距離的相反數(shù)［12］。

相似度矩陣對(duì)角線的中值就是偏向參數(shù)P［13］。該算法初始假設(shè)每個(gè)樣本點(diǎn)成為類代表的可能性相同，同時(shí)引入歸屬度矩陣和吸引度矩陣共同決定每一個(gè)樣本的類代表點(diǎn)，計(jì)算方法如下：

吸引子傳播聚類算法利用 下式計(jì)算歸屬度a（i，k）和吸引度r（i，k）之和，獲取每個(gè)樣本的類代表點(diǎn)［14］：

利用以下公式增強(qiáng)算法迭代的穩(wěn)定性［15］：

2 基于屬性分布相似度的吸引子傳播聚類算法

文中提出基于屬性分布相似度的吸引子傳播聚類算法，構(gòu)造新相似度矩陣。在高維二元數(shù)據(jù)中，假設(shè)X是數(shù)據(jù)對(duì)象集合，X＝｛Xi｜i＝1，2…，D｝，A是屬性集合，A＝｛Ai｜i＝1，2…，D｝，Y＝｛Yij｜i＝1，2…，D｝表示對(duì)象在各屬性分布上的取值分布情況，是i個(gè)對(duì)象的屬性分布特征向量。如果Yij＝1，表明第i個(gè)對(duì)象在第j個(gè)屬性上有值，否則稀疏。數(shù)據(jù)對(duì)象間相似度：

高維稀疏情形下，每個(gè)對(duì)象在屬性取值上存在大量零值，有取值的屬性數(shù)占總屬性數(shù)的比例很小。改進(jìn)方法如下式：

將式（8）計(jì)算的相似度矩陣引入吸引子傳播算法，取代歐式距離矩陣。在實(shí)際應(yīng)用中可以給相似度加上權(quán)重系數(shù)，當(dāng)維度較高時(shí)，權(quán)重系數(shù)越接近1，可以發(fā)現(xiàn)更多有意義的相似對(duì)象，如下式：

3 仿真模擬實(shí)驗(yàn)與分析

仿真模擬實(shí)驗(yàn)環(huán)境是Pentium G645 2.9GHz CPU，4GB內(nèi)存。實(shí)驗(yàn)采用UCI二元數(shù)據(jù)集，真實(shí)類數(shù)為2類，參數(shù)λ＝0.5，調(diào)整偏向參數(shù)P值，結(jié)果見表1和表2。

表1 AP聚類算法實(shí)驗(yàn)記錄

表2 PDS-AP聚類算法實(shí)驗(yàn)記錄

表1和表2表明，AP聚類算法在λ值不變的情況下，聚類類數(shù)逐漸減少，精度增高，最終穩(wěn)定的聚類類數(shù)是3類，P值增大至某一點(diǎn)時(shí)發(fā)散，得不到數(shù)據(jù)集的真實(shí)類數(shù)。PDS-AP聚類算法在不同偏向參數(shù)下聚類性能均優(yōu)于傳統(tǒng)算法，并能夠獲取真實(shí)類數(shù)。

4 超市銷售數(shù)據(jù)聚類應(yīng)用

PDS-AP聚類算法應(yīng)用在真實(shí)超市銷售數(shù)據(jù)，數(shù)據(jù)來源于科研數(shù)據(jù)共享平臺(tái)，數(shù)據(jù)總量共有741×41個(gè)數(shù)據(jù)點(diǎn)，超市銷售數(shù)據(jù)見表3。

表3 超市銷售數(shù)據(jù)

運(yùn)行PDS-AP聚類算法，類數(shù)16，將對(duì)應(yīng)的對(duì)象和其所屬樣本點(diǎn)放在一起，將增加客戶的購(gòu)買度和購(gòu)物享受。如果有顧客特征資料，可以分析不同客戶群的需求。

5 結(jié) 語

傳統(tǒng)吸引子傳播聚類算法的相似度矩陣基于歐式距離，對(duì)數(shù)據(jù)的類型具有選擇性。為了克服此弊端，文中提出的基于屬性分布相似度的PDSAP聚類算法，經(jīng)UCI標(biāo)準(zhǔn)數(shù)據(jù)集和真實(shí)數(shù)據(jù)的驗(yàn)證，與傳統(tǒng)的AP聚類算法相比，聚類精度更高，收斂速度更快，更適合高維稀疏數(shù)據(jù)的聚類。PDS-AP聚類算法的實(shí)際應(yīng)用也取得了滿意結(jié)果，而面對(duì)聚類結(jié)構(gòu)復(fù)雜的數(shù)據(jù)，還需結(jié)合群優(yōu)化算法進(jìn)一步研究。

［1］ 許曉麗，盧志茂，張格森，等.改進(jìn)近鄰傳播聚類的彩色圖像分割［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2012，24（4）：514-519.

［2］ 齊美彬，朱俊俊，紀(jì)平，等.大規(guī)模圖像集中的代表性圖像選?。跩］.自動(dòng)化學(xué)報(bào)，2014，40（4）：706-712.

［3］ 楊傳慧，吉根林，章志剛.基于分塊加權(quán)顏色直方圖的圖像聚類算法研究［J］.南京師范大學(xué)學(xué)報(bào)：工程技術(shù)版，2013，13（1）：42-43.

［4］ 湯健，管云雁，劉文廣，等.馬氏珠母貝家系遺傳結(jié)構(gòu)的微衛(wèi)星分析［J］.Marine Sciences，2013，37（8）：35.

［5］ 文翰，肖南峰.基于強(qiáng)類別特征近鄰傳播的半監(jiān)督文本聚類［J］.模式識(shí)別與人工智能，2013（5）：391.

［6］ 鄭志敏，徐青.基于吸引子傳播算法的城市航空便利性分析［J］.硅谷，2013（9）：72-73.

［7］ Yang C，Bruzzone L，Guan R C，et al.Incremental and decremental affinity propagation for semisupervised clustering in multispectral mages［J］.IEEE Transactions on Geoscience and Remote Sensing，2013，51（3）：1666-1679.

［8］ Qasim I，Jeong J W，Heu J U，et al.Concept map construction from text documents using affinity propagation［J］.Journal of Information Science，2013，39（1）：7-14.

［9］ 于吉紅，白曉明，呂俊偉.改進(jìn)相似度的吸引子傳播聚類算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2013，34（3）：603-604.

［10］ 張震，汪斌強(qiáng)，李向濤，等.基于近鄰傳播學(xué)習(xí)的半監(jiān)督流量分類方法［J］.自動(dòng)化學(xué)報(bào)，2013，39（7）：1100-1109.

［11］ Sakellariou A，Sanoudou D，Spyrou G.Combining multiple hypothesis testing and affinity propagation clustering leadsto accurate，robust and sample size independent classification on gene expression data［J］.BMC bioinformatics，2012，13（1）：270.

［12］ 張震，汪斌強(qiáng)，伊鵬，等.一種分層組合的半監(jiān)督近鄰傳播聚類算法［J］.電子與信息學(xué)報(bào)，2013，35（3）：645-651.

［13］ Torrent-Fontbona F，Muoz V，Lopez B.Solving large immobile location-allocation by affinity propagation and simulated annealing application to select which sporting event to watch［J］.Expert Systems with Applications，2013，40（11）：4593-4599.

［14］ Sattar F，Driessen P F.Non-stationary signals separation using STFT and affinity propagation clustering algorithm［C］／／Communications，Computers and Signal Processing（PACRIM），2013 IEEE Pacific Rim Conference on.IEEE，2013：389-394.

［15］ Foster B，Bagci U，Luna B，et al.Robust segmentation and accurate target definition for positron emission tomography images using Affinity Propagation［C］／／Biomedical Imaging（ISBI），2013IEEE 10th International Symposium on. IEEE，2013：1461-1464.