雙聚類算法SMR在圖像聚類中的應(yīng)用

王國政 傅迎華 張生

摘要：大數(shù)據(jù)時代，從大量數(shù)據(jù)中尋找出數(shù)據(jù)潛在的關(guān)聯(lián)受到廣泛關(guān)注。雙聚類是指對行和列同時聚類，對矩陣局部進(jìn)行搜索，旨在對高維數(shù)據(jù)中的有效信息進(jìn)行發(fā)掘，主要應(yīng)用于基因表達(dá)序列。通過對雙聚類算法SMR進(jìn)行深入研究，對其進(jìn)行改進(jìn)，加入稀疏性和非負(fù)性，使得在原有基礎(chǔ)上的“硬”聚類轉(zhuǎn)變?yōu)椤败洝本垲悺?yīng)用到圖像領(lǐng)域，對圖像中的局部信息能很好地聚類。實驗結(jié)果表明，改進(jìn)后的算法收斂速度很快，效果很好。

關(guān)鍵詞：雙聚類算法；Lasso；稀疏性；非負(fù)性

DOI：10.11907/rjdk.173197

中圖分類號：TP317.4

文獻(xiàn)標(biāo)識碼：A文章編號：1672-7800（2018）007-0223-04

Abstract：Intheeraofbigdata，withtheincreaseoftheamountofdata，itiswidelystudiedtofindoutthepotentialdataconnectionfromalargeamountofdata.Doubleclusteringisaclusteringofrowsandcolumnsatthesametime，anditsearchesthematrixlocallytoexploretheeffectiveinformationinhigh-dimensionaldata，whichismainlyusedingeneexpressionsequences.Inthispaper，westudyandimprovethedoubleclusteringalgorithmSMRby，addingsparsityandnonnegativenesstotransformthe"hard"clusteringbasedontheoriginaltransforminto"soft"clusteringandapplyittothefieldofimage，Thelocalinformationintheimageiswellclustered，andtheimprovedalgorithmconvergesquicklyandtheexperimentworkwell.

KeyWords：biclusteringalgorithm；Lasso；sparsity；non-negative

0引言

在大量數(shù)據(jù)中找到關(guān)鍵信息已經(jīng)成為一個新的研究熱點。聚類算法能有效分析這些數(shù)據(jù)，但層出不窮的聚類算法[1-2]僅僅對數(shù)據(jù)矩陣的行或列單一聚類，這些聚類方法[3]更多應(yīng)用于“經(jīng)典”數(shù)據(jù)的預(yù)測分析。而現(xiàn)在的重點往往是尋找少數(shù)所謂的局部關(guān)鍵點，這些關(guān)鍵信息可以是樣本與變量之間特定的聯(lián)系。

雙聚類思想于1972年由Hartigan[4]提出。雙聚類開始僅僅應(yīng)用在基因問題研究上，可以很好地克服傳統(tǒng)聚類方法的局限性，通過基因矩陣的行和列同時聚類，可挖掘其中的局部信息。通常情況下，就是這些局部信息對生物信息的研究很有意義。1999年由兩位科學(xué)家Cheng和Church[5]提出了具體算法，并命名為CC算法，從此之后各種雙聚類算法涌現(xiàn)出來。Yang[6]等改進(jìn)了CC雙聚類算法，提出一個新的算法FLOC，此算法能同時發(fā)現(xiàn)一組符合重疊的雙聚類。Getz[7]等提出了一種耦合雙向迭代的雙聚類算法用于識別雙聚類。

基于雙聚類對于局部信息挖掘的不可比擬優(yōu)勢，將其應(yīng)用在圖像聚類中，對圖像中潛在的細(xì)節(jié)進(jìn)行挖掘，簡化圖片所傳遞的信息。本文實驗通過選取一幅噪點圖，將圖片中具有相同特點的圖形聚到一類，選取噪點圖的目的是為了增加圖片前景和背景的差別，同時也增加細(xì)微的干擾。實驗證明本文算法能夠獲得關(guān)聯(lián)性較高的雙聚類解，可以更好地分析圖片中的潛在信息，該方法還可延伸到圖像中的其它許多領(lǐng)域。

1雙聚類理論

雙聚類可表示為數(shù)據(jù)矩陣的約束外積分解[8]，每個雙聚類由分解的秩-分量表示，其潛在的元素是稀疏的，不是使用簡單的雙線性模型。直觀上看，潛在的稀疏性選擇屬于每個雙聚類適當(dāng)?shù)男泻土校共粚儆谀硞€雙聚類的其它系數(shù)為零，因此，每個雙線性分量表示一個雙聚類。理論上雙聚類求解可表述為最小化損失函數(shù)：

開始的預(yù)想是用奇異值分解{15-16}（SVD）和非負(fù)矩陣分解（NMF）進(jìn)行雙聚類，然而A和B的列是密集的，這樣就破壞了潛在的局部信息，恰恰是這些信息在雙聚類應(yīng)用中至關(guān)重要。SVD強(qiáng)加了人為設(shè)定的正交性，如果也強(qiáng)加非負(fù)性的話，則會限制對非重疊（硬）雙聚類的分析。強(qiáng)加非負(fù)性并實施稀疏性是通過懲罰非零元素的數(shù)量（0范數(shù)）完成的，然而0范數(shù)會產(chǎn)生棘手的最優(yōu)化問題。最近的研究表明，一個好的選擇是用1范數(shù)懲罰代替0范數(shù)懲罰，1范數(shù)是0范數(shù)的最優(yōu)凸近似，而且它比0范數(shù)更容易優(yōu)化求解，由此產(chǎn)生下面的雙聚類模型：

在這個公式中，代價因子λa和λb的引入是為了使雙聚類包括行比列多或行比列少的情況。例如一個基因序列由一個數(shù)據(jù)矩陣表示，其有3個基因和12個實驗，在這種情況下，潛在的稀疏程度（非零元素的數(shù)量或百分比）在不同模式中是不同的，應(yīng)該使用不平衡的稀疏懲罰揭示潛在的結(jié)構(gòu)。令

2算法

對于雙聚類，采用了稀疏矩陣回歸（SMR）算法，式（2）中的問題是高度非凸的，所以全局最優(yōu)解不能得到保證。式（5）允許單元或坐標(biāo)下降更新，這降低了計算成本，并且以低的迭代次數(shù)產(chǎn)生了單調(diào)改進(jìn)的可允許解序列。例如，A的通用元素更新表示為α，以剩余的模型參數(shù)為條件，問題歸結(jié)為：

3實驗結(jié)果分析

將雙聚類算法用在圖像聚類是一個新思路。為了測試算法的可行性，特選取一幅噪點圖進(jìn)行雙聚類實驗。選取噪點圖進(jìn)行雙聚類驗證有兩個優(yōu)點：①可以很好地將局部關(guān)鍵點用雙聚類聚類出來；②可以增加干擾，增強(qiáng)算法的健壯性。如圖1為噪點圖，在這幅圖上有3個小方塊，將3個小方塊作為局部關(guān)鍵點作為聚類可視化。由于3個小方塊所屬位置不同，所以聚成3個不同聚類。背景和局部關(guān)鍵點區(qū)別很大，也分屬于一個聚類。

將圖片矩陣輸入MATLAB程序中，設(shè)置K為4，最終得出4個聚類，如圖2所示。從實驗結(jié)果上看，雙聚類算法可很好地將局部關(guān)鍵點（小方塊）聚類出來，算法實現(xiàn)效果很好。

經(jīng)過對算法進(jìn)行改進(jìn)，使算法收斂速度很快，收斂曲線如圖3所示。

4結(jié)語

雙聚類算法是一個新的研究方向，本文在原有算法研究基礎(chǔ)上對算法進(jìn)行了改進(jìn)，使算法增加了非負(fù)性和稀疏性，潛在的關(guān)鍵因子更易被提取出來。創(chuàng)新性地將算法應(yīng)用到圖像領(lǐng)域，研究如何利用雙聚類算法對噪點圖上關(guān)鍵信息進(jìn)行聚類，實驗效果很好。通過雙聚類算法并加上非負(fù)約束和稀疏性，使算法可以很好地解決圖像聚類問題。

參考文獻(xiàn)：

[1]李莉.五種雙聚類算法在基因表達(dá)譜數(shù)據(jù)中的比較與評價[D].咸陽：西北農(nóng)林科技大學(xué)，2012.

[2]劉楠楠.應(yīng)用于基因表達(dá)數(shù)據(jù)的雙聚類算法的研究[D].秦皇島：燕山大學(xué)，2011.

[3]LEEM，SHENH，HUANGJZ，etal.Biclusteringviasparsesingularvaluedecomposition[J].Biometrics2010（66）：1087-1095.

[4]HARTIGANJA.Directclusteringofadatamatrix[J].JASA，1972（67）：123-129.

[5]CHENGY，CHURCHGM.Biclusteringofexpressiondata[C].Proceedingsofthe8thInternationalConferenceonIntelligentSystemsforMolecularBiology（ISMB00），2000：93-103.

[6]YANGJ，WANGW，WANGHX，etal.δ-clustering：capturingsubspacecorrelationinalargedataset[C].ProceedingsofThe18thIEEEInternationalConferenceonDataEngineering，2002：501-528.

[7]GETZG，LEVINEE，DOMANYE.Coupledtwo-wayclusteringanalysisofgenemicroarraydata[C].ProceedingsoftheNaturalAcademyofSciencesUSA，2000：12079-12084.

[8]EVANGELOSE，PAPALEXAKIS，STUDENTMEMBER.FromK-meanstohighter-wayco-clustering：multilineardecompositionwithsparselatentfactors[EB/OL].http：//www.docin.com/p-1471552987.html

[9]KAISERHF.Thevarimaxcriterionforanalyticrotationinfactoranalysis[J].Psychometrika1958（23）：187-200.

[10]WITTENDM，TIBSHIRANIR，HASTIET.Apenalizedmatrixdecomposition，withapplicationstosparseprincipalcompo-nentsandcanonicalcorrelationanalysis[J].Biostatistics2009（10）：515-534.

[11]ZHOUQB，XUGD，YUZ.Webco-clusteringofusagenetworkusingtensordecomposition[EB/OL].https：//en.so.com/s？q=web+co-clustering+of+usage+network+using+tensor+decomposition.

[12]TIBSHIRANIR.Regressionshrinkageandselectionviathelasso[J].Roy.Stat.Soc.B，1996（58）：247-288.

[13]OSBORNEMR，PRESNELLB，TURLACHBA.Onthelassoanditsdual[J].JournalofComputational&GraphicalStatistics.2000;（9）：319-337.

[14]PAPALEXAKISEE，SIDIROPOULOSND，GAROFALAKISMN.Reviewerprofilingusingsparsematrixregression[C].2010IEEEInternationalConferenceonDataMiningWorkshops，2010：1214-1219.

[15]TANGC，ZHANGL，ZHANGA，etal.Interrelat-edtwo-wayclustering：anunsupervisedapproachforgeneexpressiondataanalysis[C].Proc.SecondIEEEInternationalSymposiumBioinformaticsandBioeng，2001：41-48.

[16]TANGC，ZHANGL，ZHANGI.Interrelatedtwo-wayclustering：anunsupervisedapproachforgeneexpressiondataanalysis[C].proceedingofProc.SecondIEEEInternationalSymposium.BioinformaticsandBioeng，2001：41-48.

（責(zé)任編輯：杜能鋼）