雙聚類算法SMR在圖像聚類中的應用

王國政 傅迎華 張生

摘要：大數據時代，從大量數據中尋找出數據潛在的關聯受到廣泛關注。雙聚類是指對行和列同時聚類，對矩陣局部進行搜索，旨在對高維數據中的有效信息進行發掘，主要應用于基因表達序列。通過對雙聚類算法SMR進行深入研究，對其進行改進，加入稀疏性和非負性，使得在原有基礎上的“硬”聚類轉變為“軟”聚類。應用到圖像領域，對圖像中的局部信息能很好地聚類。實驗結果表明，改進后的算法收斂速度很快，效果很好。

關鍵詞：雙聚類算法；Lasso；稀疏性；非負性

DOI：10.11907/rjdk.173197

中圖分類號：TP317.4

文獻標識碼：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引言

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

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

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

1雙聚類理論

雙聚類可表示為數據矩陣的約束外積分解[8]，每個雙聚類由分解的秩-分量表示，其潛在的元素是稀疏的，不是使用簡單的雙線性模型。直觀上看，潛在的稀疏性選擇屬于每個雙聚類適當的行和列，使不屬于某個雙聚類的其它系數為零，因此，每個雙線性分量表示一個雙聚類。理論上雙聚類求解可表述為最小化損失函數：

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

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

2算法

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

3實驗結果分析

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

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

經過對算法進行改進，使算法收斂速度很快，收斂曲線如圖3所示。

4結語

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

參考文獻：

[1]李莉.五種雙聚類算法在基因表達譜數據中的比較與評價[D].咸陽：西北農林科技大學，2012.

[2]劉楠楠.應用于基因表達數據的雙聚類算法的研究[D].秦皇島：燕山大學，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.

（責任編輯：杜能鋼）