双聚类算法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.

（責任编辑：杜能钢）