魯棒自適應對稱非負矩陣分解聚類算法

作者簡介：高海燕（1980－），女，甘肅金昌人，教授，碩導，博士，主要研究方向為函數型數據分析、聚類分析（gaohy_54@sina.com）；劉萬金（1994－），男，甘肅白銀人，碩士研究生，主要研究方向為機器學習、聚類分析；黃恒君（1981－），男，浙江溫州人，教授，博導，博士，主要研究方向為數據融合、聚類分析.

摘 要：對稱非負矩陣分解SNMF作為一種基于圖的聚類算法，能夠更自然地捕獲圖表示中嵌入的聚類結構，并且在線性和非線性流形上獲得更好的聚類結果，但對變量的初始化比較敏感。另外，標準的SNMF算法利用誤差平方和來衡量分解的質量，對噪聲和異常值敏感。為了解決這些問題，在集成學習視角下，提出一種魯棒自適應對稱非負矩陣分解聚類算法RS3NMF（robust self-adaptived symmetric nonnegative matrix factorization）。基于L2，1范數的RS3NMF模型緩解了噪聲和異常值的影響，保持了特征旋轉不變性，提高了模型的魯棒性。同時，在不借助任何附加信息的前提下，利用SNMF對初始化特征的敏感性來逐步增強聚類性能。采用交替迭代方法優化，并保證目標函數值的收斂性。大量實驗結果表明，所提RS3NMF算法優于其他先進的算法，具有較強的魯棒性。

關鍵詞：對稱非負矩陣分解；魯棒性；聚類；交替迭代方法

中圖分類號：TP181 文獻標志碼：A 文章編號：1001－3695（2023）04－011－1024－06doi： 10.19734/j.issn.1001－3695.2022.08.0414

Abstract：As a graph-based clustering method， SNMF can more naturally capture the clustering structure embedded in the graph representation and obtain better clustering results on linear and nonlinear manifolds， but it is sensitive to the initialization of variables. In addition， standard SNMF algorithm uses the sum of error squares to measure the quality of decomposition， which is sensitive to noise and outliers. In order to solve these problems， this paper proposed a novel robust self-adaptived symmetric nonnegative matrix factorization for clustering （RS3NMF） from the perspective of ensemble learning. The L2，1 norm-based RS3NMF model alleviated the noise and outliers influence， and kept the rotation invariance property to improve the model robustness. Meanwhile， using the sensitivity of SNMF to initialization features， it gradually enhanced the clustering performance， without relying on any additional information. It adopted alternating iteration method to optimize， and ensured the convergence of the objective function value. Extensive experimental results show that the proposed RS3NMF outperforms other state-of-the-art algorithms in terms of both clustering performance and robustness.

Key words：symmetric nonnegative matrix factorization（SNMF）; robustness; clustering; alternative iterative algorithm

0 引言

非負矩陣分解（nonnegative matrix factorization，NMF）［1］ 作為一種流行的數據表示方法和聚類技術［2］被廣泛應用于數據挖掘和機器學習。它將原始數據矩陣中呈現的樣本或特征表示為基向量的線性組合［3］。同時，通過相應的系數矩陣將隸屬標簽分配給每個樣本或特征。當數據分布具有線性結構時，NMF能夠獲得良好的聚類性能。然而，NMF不能利用輸入數據的非線性結構產生聚類結果［3］。

對稱非負矩陣分解（SNMF）［4］是一類特殊的約束NMF，它將記錄樣本成對相似性的親和矩陣分解成聚類指示矩陣及其轉置的乘積。Ding等人［2］研究發現SNMF與譜聚類（spectral clustering，SC）具有相同的目標函數。因此，SNMF可看做是圖聚類算法，可分非線性數據并能直接生成聚類指標，通常比SC表現得更好［5］。近年來，涌現了一些改進的SNMF算法。He等人［6］提出了有效的SNMF算法，并將其應用于概率聚類。Gao等人［7］提出了一種圖正則化SNMF（GrSymNMF）來提高其在圖聚類中的性能。Jia 等人［8］提出從樣本數據中自適應學習親和矩陣用于SNMF算法。 Zhang等人［9］構建了一種用于多視角聚類的圖正則化SNMF框架（GSNMF）。此外，SNMF也被推廣應用于半監督學習［10］、多任務聚類問題［11］等。SNMF在數學上被表述為一個非凸優化問題，對變量的初始化很敏感，而初始化矩陣的好壞將嚴重影響其聚類性能。為了解決此問題，Jia 等人［12］充分考慮SNMF對初始化的敏感性，提出了自適應的SNMF算法（S3NMF）。

在實際應用中，數據往往受到噪聲和異常值的污染，標準NMF中的Frobenius范數利用最小二乘誤差函數來計算原始數據點和預測數據點之間的差異，對噪聲和異常值非常敏感，降低了算法的魯棒性［13］。因此，有必要開發更魯棒的損失函數。文獻［14，15］等證明了L2，1范數可有效處理上述問題。同時，文獻［16］提出了基于L2，1范數的魯棒非負矩陣分解RNMF（robust nonnegative matrix factorization）。Liu等人［17］構建了一種新穎的魯棒多視角非負矩陣算法RMNMF框架。以及用于圖像聚類的魯棒半監督非負矩陣算法CSNMF［18］、基于魯棒分布的非負矩陣分解算法 RDNMF［19］、基于L2，1范數的正則化非負矩陣分解算法（RNMFL21）［20］、基于L2，1范式的多圖正則化非負矩陣分解方法（L21-MGNMF）［21］、基于子空間結構正則化的L2，1非負矩陣分解高光譜解混［22］等。此外，也可采用L2，p范數（0lt;p≤1）和相關熵（correntropy）等損失函數，進一步發展魯棒的非負矩陣分解方法［23～25］。

然而，現有方法沒有同時考慮魯棒性和SNMF初始化的敏感性。針對這一問題，受魯棒非負矩陣分解、自適應方法和集成學習的啟發，本文提出了一種新的魯棒自適應對稱非負矩陣分解聚類算法（RS3NMF），該算法將魯棒性融入SNMF框架。研究的主要目的是為了緩解噪聲和異常值問題，以及解決SNMF對初始化特征敏感性。在集成學習視角下，利用L2，1范數衡量重構誤差，使模型對噪聲和異常值不敏感，以確保魯棒性。同時，基于L2，1范數的RS3NMF模型保持了特征旋轉不變性，增強了聚類性能。具體來說，首先重復執行魯棒SNMF隨機生成一組初始非負矩陣，對應獲得一組劃分矩陣；然后根據自適應學習的權重對所得初始非負矩陣的質量進行排序，從而為魯棒SNMF重構區分性更好的相似矩陣；重復以上兩個步驟，直到達到終止準則/最大迭代次數。

1 預備知識

1.1 符號與定義

3.2 實驗設置

在五個數據集上，所提RS3NMF 聚類算法與七種算法進行對比分析，驗證RS3NMF算法的有效性。包括三類：a）K-means、NMF［1］ 、GNMF［5］與RNMF［16］；b）圖聚類算法SC［27］與SNMF［16］；c）集成聚類算法S3NMF［12］。為了使八種方法實驗結果具有可比性，對八種方法的結構參數進行統一設置。

K-means設置為默認參數設置。RS3NMF與S3NMF的迭代次數設為20次，超參數取γ=2，k=20；GNMF迭代次數為300次，超參數λ=100。特別地，當λ=0時，GNMF退化為NMF。NMF、 SC、RNMF、SNMF迭代次數為300次。RS3NMF和S3NMF、SNMF采用相同的親和矩陣作為輸入。為了排除隨機性對K-means和初始化的影響，本文將每種方法獨立重復實驗20次，并報告了平均性能。

3.3 聚類性能分析

聚類結果通過聚類精度（ACC）、歸一化互信息（NMI）、純度（PUR）、調整蘭德指數（ARI）和F1分數（F1-score）五個常用指標進行評估［8］。除ARI之外的所有度量都在［0，1］，而ARI值的為［－1，1］。所有的指標值越大，說明聚類性能越好。表2～6展示了八種不同方法在五個數據集上的聚類性能。

從表2～6得到以下結論：a）RS3NMF算法顯著優于S3NMF算法，特別在iris和wine數據集上五個聚類評價指標結果有明顯改進，這表明RS3NMF算法優于S3NMF算法，更具魯棒性，例如，在iris數據集上，ACC值從0.753 3提高到0.933 3，NMI值從0.539 8增加到0.802 7，PUR、ARI和F1-score的值也分別提高了0.180 0、0.340 1和0.220 1；b）與魯棒聚類算法RNMF相比，RS3NMF算法的優勢也很明顯，例如在seeds、 iris和3-sources數據集上，RS3NMF的ACC值分別提升了35%、32%和40%，這意味著RS3NMF算法對噪聲和異常值具有十分良好的魯棒性；c）與圖聚類算法SC和SNMF相比，RS3NMF算法的聚類性能也顯著提升，例如，在iris數據集上，與SC算法比較，ACC值提高了27%，在seeds數據集上，與SNMF算法比較，ACC值提高了20%。總的來說，相比其他七種聚類算法，RS3NMF算法在這五個數據集上始終產生最好或較好的聚類性能，驗證了其魯棒性。

3.4 迭代次數對聚類性能的影響

下面研究RS3NMF算法中迭代次數對聚類性能的影響。如圖2所示，虛線表示所提RS3NMF在不同迭代次數下的ACC值，實線表示RS3NMF算法終止準則ANMI的值，圓圈表示在該點達到了所建議的終止準則。圖2顯示在seeds、wine和Yale數據集上，所提算法RS3NMF的ACC值在最初的三次迭代中迅速增加，然后隨著迭代次數的增加其最高值基本保持不變，波動范圍在0.02～0.06，趨于相對穩定，RS3NMF算法的終止準則ANMI可以選擇最高的ACC。對于iris數據集，雖沒有選擇最高的ACC，但終止準則ANMI也可以為RS3NMF產生一個滿意的ACC，并保持最大取值基本不變。注意到，在seeds、wine和Yale數據集上，2或3次迭代內就可終止算法1，有效降低了計算成本。因此，RS3NMF算法的終止準則ANMI是有效且高效的。

3.5 收斂性分析

本節通過實驗驗證了RS3NMF算法的收斂性，并研究了算法的收斂速度。收斂曲線如圖3所示。圖3呈現了當γ=2，k=20時，五個數據集上目標函數值的對數與迭代次數的關系。隨著迭代次數的增加，目標函數值的對數快速單調遞減。算法RS3NMF對五個數據集通常在30次迭代內收斂，說明本文優化算法是有效的，收斂速度很快。

4 結束語

本文提出了一種魯棒自適應對稱非負矩陣分解算法（RS3NMF），該算法利用SNMF對初始化特征敏感的特點，結合L2，1范數提高模型的魯棒性，緩解噪聲和異常值的影響，進一步提高聚類性能。此外，采用交替迭代優化算法推導了RS3NMF的乘法更新規則，分析了算法的收斂性和計算復雜性。實驗結果證實了RS3NMF算法比七種先進的聚類算法具有更好的聚類性能。

盡管所提RS3NMF算法在聚類任務中表現出了良好的效果，但未來還可以做一些改進：a）探索數據的內在幾何結構，將數據的局部結構并入RS3NMF，考慮用于聚類的圖正則化RS3NMF；b）本文應用了魯棒的L2，1 損失函數，進一步可采用相關熵作為相似度度量來降低噪聲和異常值的影響，構建基于相關熵的自適應SNMF算法；c）嘗試將RS3NMF算法推廣到解決多視角聚類問題和函數型聚類問題。

參考文獻：

［1］Lee D D，Seung H S. Learning the parts of objects by non-negative matrix factorization［J］. Nature，1999，6755（401）： 788－791.

［2］Ding C，He Xiaofeng，Simon H D. On the equivalence of nonnegative matrix factorization and spectral clustering［C］// Proc of SIAM International Conference on Data Mining. 2005： 606－610.

［3］Cai Deng，He Xiaofei，Han Jiawei，et al. Graph regularized nonnegative matrix factorization for data representation［J］. IEEE Trans on Pattern Analysis and Machine Intelligence，2011，33（8）： 1548－1560.

［4］Kuang Da，Park H，Ding C. Symmetric non-negative matrix factorization for graph clustering［C］// Proc of SIAM International Conference on Data Mining. 2018： 379－384.

［5］Kuang Da，Yun S，Park H. SymNMF： nonnegative low-rank approximation of a similarity matrix for graph clustering［J］. Journal of Global Optimization，2015，62（3）： 545－574.

［6］He Zhaoshui，Xie Shengli，Zdunek R，et al. Symmetric nonnegative matrix factorization： algorithms and applications to probabilistic clustering［J］. IEEE Trans on Neural Networks，2011，22（12）： 2117－2131.

［7］Gao Ziheng，Guan Naiyang，Su Longfei. Graph regularized symmetric non-negative matrix factorization for graph clustering ［C］// Proc of IEEE International Conference on Data Mining Workshops. Pisca-taway，NJ： IEEE Press，2018： 379－384.

［8］Jia Yuheng，Liu Hui，Hou Junhui，et al. Clustering-aware graph construction： a joint learning perspective ［J］. IEEE Trans on Signal and Information Processing over Networks，2020，6： 357－370.

［9］Zhang Xianchao，Wang Zhongxiu，Zong Linlin，et al. Multi-view clustering via graph regularized symmetric nonnegative matrix factorization ［C］// Proc of IEEE International Conference on Cloud Computing and Big Data Analysis. Piscataway，NJ： IEEE Press，2016： 109－114.

［10］Yang Liang，Cao Xiaochun，Jin Di，et al. A unified semi-supervised community detection framework using latent space graph regularization ［J］. IEEE Trans on Cybernetics，2015，45（11）： 2585－2598.

［11］Alstouhi S，Reddy C K. Multi-task clustering using constrained symmetric non-negative matrix factorization［C］// Proc of SIAM International Conference on Data Mining. 2014： 785－793.

［12］Jia Yuheng，Liu Hui，Hou Junhui，et al. Self-adaptived symmetric nonnegative matrix factorization［EB/OL］. （2021－03－02）. https：//arxiv.org/abs/2103.01689.

［13］Lee D D，Seung H S. Algorithms for non-negative matrix factorization ［C］// Proc of the 13th International Conference on Neural Information Processing Systems. 2001： 556－562.

［14］Nie Feiping，Huang Heng，Cai Xiao，et al. Efficient and robust feature selection via joint L2，1-norms minimization［C］// Proc of the 23rd International Conference on Neural Information Processing Systems. 2010： 1813－1821.

［15］Li Zechao，Liu Jing，Yang Yi，et al. Clustering-guided sparse struc-tural learning for unsupervised feature selection ［J］. IEEE Trans on Knowledge and Data Engineering，2014，26（9）： 2138－2150.

［16］Kuang Da，Yun S，Park H. SymNMF： nonnegative low-rank approximation of a similarity matrix for graph clustering［J］. Journal of Global Optimization，2015，62（3）： 545－574.

［17］Liu Xiangyu，Song Peng，Sheng Chao，et al. Robust multi-view non-negative matrix factorization for clustering［J］. Digital Signal Processing，2022，123（4）： 103447.

［18］Peng Siyuan，Ser W，Chen Badong，et al. Robust semi-supervised nonnegative matrix factorization for image clustering［J］. Pattern Recognition，2021，111（3）： 107683.

［19］Peng Xinjun，Xu Dong，Chen De. Robust distribution-based nonnegative matrix factorizations for dimensionality reduction［J］. Information Sciences，2021，552： 244－260.

［20］李成，趙海琳. 基于L21范數的正則化非負矩陣分解算法［J］. 控制工程，2019，26（9）： 1712－1716. （Li Cheng，Zhao Hailin. Regularized nonnegative matrix factorization based on L21 norm［J］. Control Engineering of China，2019，26（9）： 1712－1716.）

［21］周長宇，姚明海，李勁松. 基于L21范式的多圖正則化非負矩陣分解方法［J］. 計算機應用與軟件，2021，38（4）： 271－275. （Zhou Changyu，Yao Minghai，Li Jinsong. Multiple graph regularized non-negative matrix factorization based on L21 norm［J］. Computer Applications and Software，2021，38（4）： 271－275.）

［22］陳善學，劉榮華. 基于子空間結構正則化的L21非負矩陣分解高光譜解混［J］. 電子與信息學報，2022，44（5）： 1704－1713. （Chen Shanxue，Liu Ronghua. L21 nonnegative matrix factorization for hyperspectral unmixing based on subspace structure regularization［J］. Journal of Electronics amp; Information Technology，222，44（5）： 1704－1713.）

［23］Xiong He， Kong Deguang. Elastic nonnegative matrix factorization［J］. Pattern Recognition，2019，90（6）： 464－475.

［24］Li Le，Yang Jianjun，Zhao Kaili，et al. Graph regularized non-negative matrix factorization by maximizing correntropy［J］. Journal of Computers，2014，9（6）： 2570－2579.

［25］Wang Yuanyuan，Wu Shuyi，Mao Bin，et al. Correntropy induced metric based graph regularized non-negative matrix factorization［J］. Neurocomputing，2016，204（5）： 172－182.

［26］Yi Yugen，Wang Jianzhong，Zhou Wei，et al. Non-negative matrix factorization with locality constrained adaptive graph［J］. IEEE Trans on Circuits and Systems for Video Technology，2020，30（2）： 427－441.

［27］Ng A，Jordan M，Weiss. Y. On spectral clustering： analysis and an algorithm［C］// Proc of the 14th International Conference on Neural Information Processing Systems. Cambridge，MA： MIT Press，2002： 849－856.