楊曉慧， 王莉莉， 李登峰

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

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

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

1 層次譜聚類

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

圖1 無(wú)向圖G（V，E）Fig.1 Undirective graph G （V，E）

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

步驟1 用SM 聚類算法將整個(gè)圖像庫(kù)分為S1和S2兩類.

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

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

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

2 聚類的評(píng)價(jià)標(biāo)準(zhǔn)

2.1 聚類正確率

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

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

2.2 聚類的純度

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

表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é)果的比較，所采用的圖像特征和相似性度量與文獻(xiàn)［21］中相同.

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

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

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

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

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

圖4（見(jiàn)下頁(yè)）給出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%），因此對(duì)于本文的實(shí)驗(yàn)圖像庫(kù)其純度結(jié)果不具有參考價(jià)值.這同時(shí)說(shuō)明在譜聚類過(guò)程中運(yùn)用層次聚類可以提高聚類的正確率.

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

3 結(jié) 論

充分考慮了各種聚類算法的優(yōu)缺點(diǎn)，將層次聚類和譜聚類結(jié)合在一起，提出的層次譜聚類算法吸收了層次聚類算法和譜聚類算法的優(yōu)點(diǎn).實(shí)驗(yàn)結(jié)果表明，層次譜聚類算法既避免了聚類過(guò)程中的歪斜劃分，又比譜聚類算法提高了聚類正確率，同時(shí)又比層次聚類算法減少了運(yùn)算時(shí)間.但其運(yùn)算時(shí)間仍然較長(zhǎng)，且其聚類正確率有待于進(jìn)一步提高.希望以后能夠?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é)報(bào)，2008，30（5）：149－153.

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