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

徐煜

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

0 引言

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

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

1 多視圖雙聚類算法

1.1 多視圖雙聚類算法

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

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

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

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

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

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

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

1.2 優化求解

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

輸入：多視圖矩陣{Xm}∈Rn×dm、子空間列維度、行簇以及列簇個數、參數λ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算法的優越性，本實驗采用已知細胞類型的癌癥基因單細胞表達數據集進行試驗，即結直腸癌（CRC）數據集。結直腸癌CRC數據集來源于GSE81861[8]，來自11位CRC患者的1591個單細胞測序數據，包括969腫瘤部位細胞以及622癌旁細胞，經過嚴格過濾后余下375個癌癥細胞以及215個正常組織細胞，以CRC數據集中癌癥細胞以及癌旁細胞分別對應兩個視圖組成數據集CRC，CRC包含有7種細胞類型。實驗前對多視圖scRNA-seq數據集進行了過濾，過濾了表達過低的基因，數據及構成如表1所示。

表1 細胞類型已知的多視圖單細胞表達數據集

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

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

表2 對比算法在多視圖數據集上的實驗結果

圖1 λz取值與F-score的關系

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

3 結語

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