王國(guó)政 傅迎華 張生

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

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

DOI：10.11907/rjdk.173197

中圖分類號(hào)：TP317.4

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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)成為一個(gè)新的研究熱點(diǎn)。聚類算法能有效分析這些數(shù)據(jù)，但層出不窮的聚類算法[1-2]僅僅對(duì)數(shù)據(jù)矩陣的行或列單一聚類，這些聚類方法[3]更多應(yīng)用于“經(jīng)典”數(shù)據(jù)的預(yù)測(cè)分析。而現(xiàn)在的重點(diǎn)往往是尋找少數(shù)所謂的局部關(guān)鍵點(diǎn)，這些關(guān)鍵信息可以是樣本與變量之間特定的聯(lián)系。

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

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

1雙聚類理論

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

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

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

2算法

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

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

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

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

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

4結(jié)語(yǔ)

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

參考文獻(xiàn)：

[1]李莉.五種雙聚類算法在基因表達(dá)譜數(shù)據(jù)中的比較與評(píng)價(jià)[D].咸陽(yáng)：西北農(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é)任編輯：杜能鋼）