基于矩陣分解的多視圖雙聚類算法

徐煜

（西南大學(xué)計算機與信息科學(xué)學(xué)院，重慶400715）

0 引言

隨著技術(shù)發(fā)展，有效地處理多視圖數(shù)據(jù)成為了雙聚類算法的發(fā)展趨勢。為有效融合多源數(shù)據(jù)信息，研究人員結(jié)合多視圖學(xué)習(xí)以及雙聚類算法提出了多視圖雙聚類算法[1]（Multi-View Bi-Clustering）算法來對多視圖、多源數(shù)據(jù)進行雙聚類分析。多視圖雙聚類算法可以利用多視圖數(shù)據(jù)中隱含的共享性信息以及差異性信息指導(dǎo)聚類過程，進而獲得更高的精度。然而，目前的多視圖雙聚類算法研究中，研究者使用的算法都是以單一視圖的雙聚類為基礎(chǔ)，尋找不同視圖間的共享特征來鏈接多個視圖從而拓展為多視圖雙聚類算法，如Sun等人[1-4]算法以及Farhan等人[5]算法。Sun等人[1-2]提出了一種基于稀疏奇異值分解（SSVD）的多視圖雙聚類算法，該算法以單視圖的稀疏奇異值為基礎(chǔ)，引入二值向量鏈接兩個視圖將算法從單視圖算法拓展為雙視圖雙聚類算法，最終給出了適用于更多視圖情況下的目標方程，從而提出了多視圖稀疏奇異值分解雙聚類算法。但是Sun等人[1-2]算法沒有考慮視圖之間信息含量差異的問題，沒有合理利用多視圖數(shù)據(jù)中的互補性以及一致性信息，并且該方法無法保證收斂[4]。為此他們進一步提出了一種基于稀疏低秩矩陣分解的多視圖雙聚類算法[3]，該算法以單視圖的稀疏秩一矩陣分解算法為基礎(chǔ)，改用對角矩陣鏈接多個視圖獲取雙聚簇。但是該方法需要預(yù)先定義雙聚類簇的大小，即簇中行的數(shù)量[4]，在面對未知簇類的數(shù)據(jù)集時，該方法不適用。Sun等人[4]進一步地以單個視圖的稀疏秩一矩陣分解為基礎(chǔ)，以二值向量鏈接多個視圖優(yōu)化雙聚類簇。該方法有了收斂的保證，并且首次給出了雙視圖數(shù)據(jù)集的不同方案，給出了不同的模式，但是該方法運行時間過長，在面對復(fù)雜的數(shù)據(jù)集時需要耗費數(shù)天時間。并且該方法依舊沒有合理利用多視圖數(shù)據(jù)中的互補性以及一致性信息，無法有效地提高聚類精度。

為解決上述問題，本文提出了一種不同于上述算法的多視圖雙聚類算法（Multi-view Subspace Bi-Clustering，MSBC）。MSBC首先設(shè)計了基于稀疏矩陣分解、多視圖學(xué)習(xí)以及三因子矩陣分解的多視圖雙聚類的統(tǒng)一目標方程，同時引入流形正則項以差異性地整合多個視圖指導(dǎo)高質(zhì)量互補子空間的學(xué)習(xí)。在大型生物數(shù)據(jù)集上獲取了比現(xiàn)有相關(guān)聚類算法更準確聚類簇，證明了算法的有效性。

1 多視圖雙聚類算法

1.1 多視圖雙聚類算法

現(xiàn)有的多視圖雙聚類算法[1-5]算法普遍面向傳統(tǒng)基因表達分析任務(wù)，其算法框架以單視圖矩陣分解為基礎(chǔ)，以公共向量或者公共矩陣來鏈接多個視圖從而形成多視圖雙聚類算法。而在面對更為復(fù)雜、噪音更大、數(shù)據(jù)更稀疏、數(shù)據(jù)量更大的多視圖數(shù)據(jù)時，其算法運行時間過長，甚至沒有結(jié)果，聚類精度降低。

為了解決上述問題，本文引入非負稀疏矩陣分解來獲取一個更為稠密的子空間以降低聚類難度，提高聚類精度，NMF（Nonnegative Matrix Factorization）的非負約束有助于獲得基于數(shù)據(jù)本身的表示，并提高了子空間學(xué)習(xí)的可解釋性，具體方式如下：

其中{Xm}∈Rn×dm為多視圖數(shù)據(jù)中第m個視圖的矩陣數(shù)據(jù)，X∈Rn×d，Hm∈Rn×d為所求的更稠密的子空間表示，Hm在所有的視圖間鏈接視圖之間的共享性信息，以期學(xué)習(xí)這些視圖數(shù)據(jù)間的共享信息。n表示行的數(shù)量，d表示列的數(shù)量，||·||為Frobenius范數(shù)，Hm≥0為非負約束。上式中子空間Hm整合了視圖內(nèi)以及視圖之間的差異性信息，從而在使得子空間數(shù)據(jù)變得稠密的同時捕獲多視圖數(shù)據(jù)中的跨視圖關(guān)系?？梢蕴岣呔垲惥?。

視圖數(shù)據(jù)之間差異性信息以及一致性信息的有效利用決定了多視圖聚類的質(zhì)量，為了更好地抽取多視圖數(shù)據(jù)中的共性和互補性，本文在具有一致性的子空間W上設(shè)計流形正則項[7]約束，獲取增強的多視圖數(shù)據(jù)的共享和互補信息，具體方式如下：

其中λz為平衡參數(shù)，為第m個視圖中行i與行j之間的相似度，本文采用皮爾森相關(guān)系數(shù)計算，表示如下：上式中對角矩陣，可以引導(dǎo)子空間保持每個視圖數(shù)據(jù)的局部流形結(jié)構(gòu)（通過Dm刻畫），從而整合利用這些視圖數(shù)據(jù)之間的互補差異性。

相比于其他雙聚類技術(shù)如奇異值分解算法以及秩一矩陣分解算法，基于三因子矩陣分解（Semi-Non?negative Matrix Tri-Factorization，SNMTF）的雙聚類算法不僅具有較低的復(fù)雜度和良好的可解釋性，還具有良好的穩(wěn)定性，而且聚類過程中不需要更多的先驗知識和參數(shù)設(shè)置。因此本文在前面獲取的子空間Hm上設(shè)計基于半非負三因子矩陣分解雙聚類目標方程如下：

其中S為系數(shù)矩陣，其作用是使得行簇和列簇的數(shù)目不同，并可使矩陣分解引起的平方誤差最小化。R為行聚類的指示矩陣，C為列聚類的指示矩陣，并且R與C為二值矩陣，矩陣R與C中的值為1時表示特征i與樣本j分別屬于相應(yīng)的行、列聚類，值為0時則表示表示特征i與樣本j不屬于相應(yīng)的行、列聚類，根據(jù)矩陣R與C中的值即可判定聚類結(jié)果。上述目標方程將多個視圖的共享與互補子空間的學(xué)習(xí)與子空間上的雙聚類統(tǒng)一同一個目標方程中，從而提高了子空間學(xué)習(xí)和子空間上雙聚類之間的耦合性，有利于獲得高質(zhì)量的雙聚類簇。

1.2 優(yōu)化求解

由于統(tǒng)一的目標方程中R與C元素取值在0~1之間，直接優(yōu)化該目標方程是非常困難的。為此，本文將矩陣R與C的取值范圍松弛到非負值，再優(yōu)化Xm、W、Hm、R、S、Cm。為實現(xiàn)上述多變量優(yōu)化，本文引入交替方向乘子法（Alternating Direction Method of Multipliers），其主要思想為交替固定上述6個變量中的5個并求解另一個變量，通過多步迭代交替優(yōu)化計算這些變量的優(yōu)化解。主要流程如下：

輸入：多視圖矩陣{Xm}∈Rn×dm、子空間列維度、行簇以及列簇個數(shù)、參數(shù)λz

輸出：指示矩陣R、樣本簇指示矩陣C

1.L←基于多視圖矩陣Xm計算拉普拉斯矩陣

2.Xm、W、Hm、R、S、Cm←Init（Xm、W、Hm、R、S、Cm）//初始化Xm、W、Hm、R、S、Cm

3.WHILE（not convergence）

4.S←update（S）//更新S

5.R←update（R）//更新R

6.Cm←update（Cm）//更新Cm

7.Xm←update（Xm）//更新Xm

8.W←update（W）//用公式（15）更新W

9.Hm←update（Hm）//用公式（19）更新Hm

10.END WHILE

2 實驗分析

為了證明本文提出的MVBC算法的優(yōu)越性，本實驗采用已知細胞類型的癌癥基因單細胞表達數(shù)據(jù)集進行試驗，即結(jié)直腸癌（CRC）數(shù)據(jù)集。結(jié)直腸癌CRC數(shù)據(jù)集來源于GSE81861[8]，來自11位CRC患者的1591個單細胞測序數(shù)據(jù)，包括969腫瘤部位細胞以及622癌旁細胞，經(jīng)過嚴格過濾后余下375個癌癥細胞以及215個正常組織細胞，以CRC數(shù)據(jù)集中癌癥細胞以及癌旁細胞分別對應(yīng)兩個視圖組成數(shù)據(jù)集CRC，CRC包含有7種細胞類型。實驗前對多視圖scRNA-seq數(shù)據(jù)集進行了過濾，過濾了表達過低的基因，數(shù)據(jù)及構(gòu)成如表1所示。

表1 細胞類型已知的多視圖單細胞表達數(shù)據(jù)集

本文采用聚類中常用的度量指標Accuracy、Fscore、Precision、Recall進行評價。本實驗中采用的對比算法有MVSVD[1-2]、MVSCC[3]以及CSBC[4]，且對CS?BC的模式均進行了實驗，其中CSBC-e為“equal”模式，CSBC-w為“weighted”模式，實驗結(jié)果如表2所示。

從表2中可以看出MVBC方法在4個指標都領(lǐng)先于現(xiàn)有方法，可以證明本文提出MVBC方法的優(yōu)越性。表2中每一算法的每一個指標均有兩行，這是由于采用的CRC數(shù)據(jù)集是多視圖數(shù)據(jù)集，擁有兩個視圖，每個視圖包含的列不一樣，因此算法在每個視圖上都會產(chǎn)生一個結(jié)果，從而得到了兩個結(jié)果。第一行為視圖1的結(jié)果，第二行為視圖2的結(jié)果，視圖2的結(jié)果普遍高于視圖1，這是因為視圖2擁有375個樣本，而試圖1僅有215個樣本，視圖2的維度更大，聚類難度更高，因此每個算法在視圖2上的結(jié)果都會低于視圖1。而CSBC提供的兩種模式中，w模式比e模式效果更差，說明預(yù)設(shè)的w模式不符合數(shù)據(jù)分布，e模式更貼近數(shù)據(jù)的分布。而本文所提出的MVBC算法在沒有提供預(yù)設(shè)模式的情況下，利用多視圖數(shù)據(jù)中的一致性信息以及差異性信息，在Accura?cy、F-score、Precision、Recall這4個結(jié)果上都優(yōu)于現(xiàn)有算法，說明了本文提出的MVBC算法的優(yōu)越性。

表2 對比算法在多視圖數(shù)據(jù)集上的實驗結(jié)果

圖1 λz取值與F-score的關(guān)系

在本節(jié)中，本文還設(shè)置了實驗對參數(shù)λz進行了分析，從圖1為數(shù)據(jù)集CRC1中λz與F-score（取兩視圖F-score平均值）的關(guān)系的折線圖，從圖1中可以得出當(dāng)λz為0.01時MVBC算法性能最佳。

3 結(jié)語

本文提出了有別于現(xiàn)有多視圖雙聚類框架的多視圖子空間雙聚類算法，并給出了相應(yīng)的優(yōu)化方法。首先本文通過空間學(xué)習(xí)從多視圖的表達數(shù)據(jù)中提取具有一致性的公共子空間以及具有差異性的子空間，差異性整合這些視圖結(jié)合，利用流行正則項進行約束，再在特征子空間上進行三因子矩陣分解得到雙聚類。在大型多視圖的數(shù)據(jù)集上的實驗結(jié)果表明，本文提出的多視圖雙聚類算法在檢測多視圖數(shù)據(jù)中的聚類簇有著優(yōu)良的效果。因此，本文的方法是可行且高效的