一種新的層次譜聚類算法

楊曉慧， 王莉莉， 李登峰

（河南大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，開封 475004）

聚類算法在數(shù)據(jù)分析和模式識別領(lǐng)域都扮演著重要的角色，其目的是將相似對象聚為一類.在目前計算機視覺的研究中存在的困難是如何有效地提高聚類算法的性能.作為一種有效的數(shù)據(jù)分析方法，聚類算法在計算機視覺、信息檢索及數(shù)據(jù)挖掘等領(lǐng)域都有廣泛的應(yīng)用.聚類搜索策略是當(dāng)前研究的一個熱點.1998年，Iyengar等［1］利用聚類算法已達(dá)到對大型數(shù)據(jù)庫進行有效的訪問.2002年，Saux等［2］提出利用圖像聚類可以從更好的角度幫助用戶快速的從大型數(shù)據(jù)庫中找到所要找的圖像.2003年，K?ster等［3］提出了一種利用圖像分割技術(shù)實現(xiàn)圖像聚類的方法.在聚類算法的研究中，代表性的常用聚類算法有：LBG 算法［4－6］、K－means算法［7－11］、譜聚類算 法［12－15］和 層 次 聚 類 算 法［10，16－18］.層 次 聚 類算法可以提高聚類精確度，而譜聚類算法能夠盡可能的平衡分割，而這正是所要測試的兩個圖像庫所需要的.于是提出了一種層次譜聚類算法，它融合了兩種聚類算法的優(yōu)點，并且抑制了兩者的缺點.實驗表明，層次譜聚類算法在聚類精確度上優(yōu)于譜聚類算法，相對于層次聚類算法又大大減少了運算時間.

文中介紹了層次譜聚類算法的具體實施過程及兩種聚類評價標(biāo)準(zhǔn).并選取Wang圖像庫為實驗圖像庫，對比試驗結(jié)果.得出了層次譜聚類算法的聚類正確率高于層次聚類算法、譜聚類算法的結(jié)論.

1 層次譜聚類

根據(jù)層次是自底向上還是自頂向下形成，可以將層次聚類算法分為合并型層次聚類算法和分裂型層次聚類算法兩種.兩者的不同之處在于合并型算法初始時，每一個成員都組成一個單獨的簇，在以后的迭代過程中，再將那些相鄰的簇合并為一個簇，直到所有的成員組成一個簇為止.而分裂型算法則在初始時將所有元組歸于同一簇，然后將上層的簇重復(fù)的分裂為兩個下層簇，直到每一個元組都組成一個單獨的簇為止.本文聚類的初始狀態(tài)是將每一幅圖像視為一類，所以文中采用了合并型層次聚類算法.譜聚類來源于譜圖劃分準(zhǔn)則，是一種受歡迎的功能強大的計算方法.它將數(shù)據(jù)聚類問題看成是一個無向圖的多路劃分問題.數(shù)據(jù)點看成是一個無向圖G（V，E）（如圖1）的頂點V，邊權(quán)重的集合E＝｛Wij｝，表示基于某一相似性度量計算的兩點間的相似性，W 表示待聚類數(shù)據(jù)點間的相似性矩陣，將其看做是該無向圖的鄰接矩陣，它包含了聚類所需要的所有信息.然后定義一個劃分準(zhǔn)則，最優(yōu)化這一準(zhǔn)則使得同一類內(nèi)的點具有較高的相似性，而不同類之間的點具有較低的相似性.本文采用的譜聚類算法是由Shi和Malik提出的SM 算法［12］.它作為一個啟發(fā)式算法，目標(biāo)在于最小化由同一作者提出的規(guī)范切準(zhǔn)則（normalized cut，NCut）［12］.

圖1 無向圖G（V，E）Fig.1 Undirective graph G （V，E）

充分融合層次聚類算法較高的聚類精確度的優(yōu)點和譜聚類算法盡可能平衡分割的優(yōu)點，將兩者結(jié)合并提出了一種層次譜聚類算法.具體步驟如下：

步驟1 用SM 聚類算法將整個圖像庫分為S1和S2兩類.

步驟2 比較S1和S2哪一類所包含的節(jié)點多，不失一般性，假設(shè)S2包含的節(jié)點多于S1，對S2施行層次聚類.當(dāng)所要合并的兩類之間的距離大于等于閾值T 時，層次聚類終止（T 為圖像庫中任意兩幅圖之間距離的均值）.

步驟3 計算對S2施行層次聚類所得類的類中心，并對其施行SM 聚類.

步驟4 重復(fù)步驟2、步驟3，直到得出所需的類數(shù)為止.

2 聚類的評價標(biāo)準(zhǔn)

2.1 聚類正確率

聚類正確率是一種常用的聚類算法評價標(biāo)準(zhǔn)，它將聚類結(jié)果和已知的真實類屬信息進行匹配后，得出聚類的正確率.其計算式為

式中，n為圖像庫中所包含的圖像個數(shù)；a 為兩幅圖像在已知的真實類屬信息中屬于同一類，而聚類所得的結(jié)果中他們也屬于同一類的對數(shù)；b 為兩幅圖像在已知的真實類屬信息中不屬于同一類，而聚類所得的結(jié)果中它們也不屬于同一類的對數(shù).

2.2 聚類的純度

聚類所得的結(jié)果在一類中可能會包含屬于不同語義的對象.聚類的純度是指一類中主語義類所占的百分比.假設(shè)對于某一類Cj中有n 幅圖像屬于c個語義（在試驗中，c≤10），那么該類的純度計算式為

3 實驗結(jié)果及分析

文中所有程序的運行環(huán)境為matlab R2010aon Dual－core Intel（R）Pentium （R）CPU P6000＠1.87GHZ，512M memory，operating system：windows7.對Corel Database 的 子 圖 像 庫 Wang Database進行試驗.Wang Database共包含10類，每類中包含100幅圖像.這10類分別是Africa people and Villages，Beach，Buildings，Buses，Dinosaurs，Elephants，F(xiàn)lowers，Horses，Mountains and Glaciers和Food.圖2給出了每類中的一個代表圖像.

圖2 Wang database中每類的代表圖像Fig.2 Example images of each category in Wang database

文獻［21］中提出的MPEG－7 邊緣直方圖特征能夠保留傳統(tǒng)直方圖的強度，并包含有圖像的邊緣連通性和區(qū)域塊邊緣模式的連續(xù)性信息，因此基于圖像的MPEG－7 邊緣直方圖特征進行聚類.兩幅圖像之間的相似性用兩幅圖像的直方圖A，B 之間的距離D（A，B）來度量

式中，A（i），B（i）分別為圖像的直方圖A，B 的第i個直方條的度量值.

表1和表2 是分別對不同特征用LBG 和KMeans算法所得的結(jié)果［22］和本文實驗結(jié)果的對比.表中（1）代表不變特征直方圖，（2）代表不變特征關(guān)系直方圖，（3）代表Tamura 特征直方圖.對比結(jié)果表明層次聚類算法所得的聚類正確率是最高的，這主要得益于在譜聚類算法的過程中運用了層次聚類算法，而層次聚類算法可以提高聚類的正確率.

表1 不同特征用LBG 算法［22］和本文結(jié)果的比較Tab.1 Comparison between the results by LBG algorithm［22］and our results for different features

表3和圖3及圖4為層次聚類、譜聚類、層次譜聚類3種聚類算法所得結(jié)果的比較，所采用的圖像特征和相似性度量與文獻［21］中相同.

表3是3種聚類算法所得結(jié)果的聚類正確率和計算時間的比較，從表3可以看出層次譜聚類的聚類正確率比層次聚類、譜聚類的聚類正確率都高.這再次證明了在譜聚類過程中采用層次聚類有助于提高聚類的正確率.而層次譜聚類所用的時間比層次聚類所用的時間少，卻遠(yuǎn)遠(yuǎn)多于譜聚類所用的時間，這是因為層次聚類的計算復(fù)雜度較高，在譜聚類過程中運用層次聚類雖然提高了聚類正確率，卻大大延長了運算時間.

表2 不同特征用K－Means算法［22］和本文結(jié)果的比較Tab.2 Comparison between the results by K－Means algorithm［22］and our results for different features

表3 3種聚類算法的聚類正確率和計算時間Tab.3 Accuracy and computing time consumption of the three clustering algorithms

圖3是層次聚類、譜聚類和層次譜聚類所得結(jié)果的每類中的圖像個數(shù)（按從多到少排列）比較，橫坐標(biāo)表示圖像類，縱坐標(biāo)表示每類中包含圖像的個數(shù).從圖3 的結(jié)果可以看出層次聚類在聚類過程中得到了歪斜劃分，而譜聚類和層次譜聚類所得的聚類結(jié)果每類中所含的圖像個數(shù)相對平均，這是由于譜聚類有盡可能平衡分割的特點，而這是Wang Database所需要的.

圖3 W 層次聚類、譜聚類和層次譜聚類所得的每類中的圖像個數(shù)比較Fig.3 Comparson of the number of images in each cluster of hierarchical clustering，spectral clustering and hierarchical spectral clustering

圖4（見下頁）給出3種聚類算法所得結(jié)果中每類的純度比較，橫坐標(biāo)表示圖像類，縱坐標(biāo)表示圖像類中圖像的純度.從圖4的結(jié)果可以看出層次譜聚類 所 得 的 結(jié) 果 除 了 第1 類（Africa people and Villages）和譜聚類所得的結(jié)果一致外，其它9類均優(yōu)于譜聚類的結(jié)果.而層次聚類算法得到的是歪斜劃分，10類中有5類都只含有1幅圖像（只包含1幅圖像的類純度當(dāng)然是100%），因此對于本文的實驗圖像庫其純度結(jié)果不具有參考價值.這同時說明在譜聚類過程中運用層次聚類可以提高聚類的正確率.

圖4 3種聚類算法每類的純度比較Fig.4 Comparson of cluster purity of the three clustering algorithms

3 結(jié) 論

充分考慮了各種聚類算法的優(yōu)缺點，將層次聚類和譜聚類結(jié)合在一起，提出的層次譜聚類算法吸收了層次聚類算法和譜聚類算法的優(yōu)點.實驗結(jié)果表明，層次譜聚類算法既避免了聚類過程中的歪斜劃分，又比譜聚類算法提高了聚類正確率，同時又比層次聚類算法減少了運算時間.但其運算時間仍然較長，且其聚類正確率有待于進一步提高.希望以后能夠?qū)ふ业礁鼉?yōu)的聚類算法.

［1］Iyengar G，Lippman A B.Clustering images using relative entropy for efficient retrieval ［C］∥International Workshop on Very Low Bitrate Video Coding，Urbana，1998.

［2］Saux B L， Boujemaa N. Unsupervised robust clustering for image database categorization［C］∥Proceeding International Conference Pattern Recognition Quebec，Canada：IEEE，2002：259－262.

［3］K?ster T，Wendt V，Sagerer G.Comparing clustering methods for database categorization in image retrieval［J］.Pattern Recognition，2003，2781：228－235.

［4］Linder Y，Buzo A，Gray R M.An algorithm for vector quantization design［J］.Proceeding IEEE Transaction Communications Society，1980，28（1）：84－95.

［5］Gersho A，Gray R M.Vector Quantization and Signal Compression［M］.Boston：Kluwer Academic，1991.

［6］Kekre H，Sarode T，Bharadi V，et al.Iris recognition using vector quantization［C］∥Internation Conference Signal Acquisition and Processing，Bangalore：IEEE，2010：58－62.

［7］Bradley P，F(xiàn)ayyad U.Refining initial points for Kmeans clustering［C］∥Proceeding International Conference on Machine Learning，San Francisco：Morgan kaufmann publishers Inc，1998：91－99.

［8］Liu H，Yu X H.Application research of K－means clustering algorithm in image retrieval system［C］∥Proceeding of the Second Symposium International Computer Science and Computation Technology，Huangshan，2009：274－277.

［9］Yang Y，Xu D，Nie F P，et al.Image clustering using local discriminate models and global integration［J］.IEEE Transactions on Image Processing，2010，19（10）：2761－2773.

［10］Chen T S，Tsai T H，Chen Y T，et al.A combined Kmeans and hierarchical clustering method for improving the clustering efficiency of microarray［C］∥Proceeding of 2005International Symposium on Intelligent Signal Processing and Communication System，Hong Kong：IEEE，2005：405－408.

［11］Honda K，Notsu A，Ichihashi H.Fuzzy PCA－guided robust K－means clustering［J］.IEEE Transaction Fuzzy Systems，2010，18（1）：67－79.

［12］Shi J， Malik J. Normalized cuts and image segmentation［J］.IEEE Transaction Pattern Analysis and Machine Intelligence，2000，22（8）：888－905.

［13］Xu L，Li W，Schuurmans D.Fast normalized cut with linear constraints［C］∥IEEE Conference on Computer Vision and Pattern Recognition，F(xiàn)lorida：IEEE，2009：2866－2873.

［14］Li Z，Liu J，Tang X.Constrained clustering via spectral regularization［C］∥IEEE Conference on Computer Vision and Pattern Recognition，Miami：IEEE，2009：421－428.

［15］Ning H，Xu W，Chi Y，et al.Incremental spectral clustering by efficiently updating the eigen－system［J］.Pattern Recognition，2010，43（1）：113－127.

［16］Bandyopadhyay S.An automatic shape independent clustering technique［J］.Pattern Recognition，2004，37（1）：33－45.

［17］Maqbool O，Babri H.Hierarchical clustering for software architecture recovery［J］.IEEE Transactions on Software Engineering，2007，33（11）：759－780.

［18］Cilibrasi R，Vitanyi P.A fast quartet tree heuristic for hierarchical clustering［J］.Pattern Recognition，2011，44（3）：662－677.

［19］Jain A K，Dubes R C.Algorithms for clustering data［M］.Englewood Cliff：Prentice－Hall，1988.

［20］Saporta G，Youness G.Comparing two partitions：some proposals and experiments［C］∥Compstat Berlin：Physical－Verlag HD，2002：243－248.

［21］康勤.基于MPEG－7 邊緣直方圖描述符的圖像檢索算法［J］.西南大學(xué)學(xué)報，2008，30（5）：149－153.

［22］Deselaers T，Ney H，Keysers D.Features for image retrieval［D］.Aachen：RWTH Aachen University，2003：77－79.