基于潛在因子模型在子空間上的缺失值注意力聚類算法

王嘯飛，鮑勝利*，陳炯環

基于潛在因子模型在子空間上的缺失值注意力聚類算法

王嘯飛1，2，鮑勝利1，2*，陳炯環1，2

（1.中國科學院 成都計算機應用研究所，成都 610041； 2.中國科學院大學，北京 100049）（?通信作者電子郵箱 baoshengli@casit.com.cn）

針對傳統聚類算法在對缺失樣本進行數據填充過程中存在樣本相似度難度量且填充數據質量差的問題，提出一種基于潛在因子模型（LFM）在子空間上的缺失值注意力聚類算法。首先，通過LFM將原始數據空間映射到低維子空間，降低樣本的稀疏程度；其次，通過分解原空間得到的特征矩陣構建不同特征間的注意力權重圖，優化子空間樣本間的相似度計算方式，使樣本相似度的計算更準確、泛化性更好；最后，為了降低樣本相似度計算過程中過高的時間復雜度，設計一種多指針的注意力權重圖進行優化。在4個按比例隨機缺失的數據集上進行實驗。在Hand-digits數據集上，相較于面向高維特征缺失數據的K近鄰插補子空間聚類（KISC）算法，在數據缺失比例為10%的情況下，所提算法的聚類準確度（ACC）提高了2.33個百分點，歸一化互信息（NMI）提高了2.77個百分點，在數據缺失比例為20%的情況下，所提算法的ACC提高了0.39個百分點，NMI提高了1.33個百分點，驗證了所提算法的有效性。

潛在因子模型；缺失值；注意力機制；聚類算法；子空間

0 引言

隨著互聯網的快速發展以及企業數據業務的大規模擴張，數據資源呈現爆炸式增長的趨勢，對數據挖掘、信息過濾和搜索的研究得到了廣泛關注。聚類算法作為數據挖掘技術的一種重要形式，能夠根據相似度將一組數據（通常表現成一組數據張量或者多維數據空間當中的點集）聚類成簇。同一個簇內的數據密切相關，不同簇內的數據存在一定的差異［1］。

聚類算法作為一種無監督的機器學習算法，可以在缺少先驗信息的條件下，通過計算樣本間的相似度對數據進行聚類。目前常見的聚類算法包括K均值（K-means）聚類算法［2］、高斯模型聚類［3］、DBSCAN（Density-Based Spatial Clustering of Applications with Noise）［4］、層次聚類［5］和子空間聚類［6］。目前聚類算法被廣泛應用到多個領域，如生物醫學分析［7］、推薦系統［8］、工程優化和社交網絡［9］等。

聚類算法在聚類過程中需要衡量數據樣本間的相似程度，盡可能地保證相似樣本分類在一個簇；但是在現實世界的數據收集過程中，底層數據通常不完整，存在部分缺失值樣本。缺失值產生的原因可能有多種：1）人為因素，例如在收集調查的數據集中，調查參與的人員可能拒絕回答或者忽略某些敏感問題；2）非人為因素，如設備的故障、不正確的測量、數據采集過程中存在限制或數據的損壞都會導致產生缺失數據［10］。文獻［11］中闡述了數據的缺失是聚類算法過程中常見的一類數據質量問題，有效缺失值填充可以減少數據缺失造成的聚類錯誤，提高聚類的準確度。如果采用不恰當的填充方式，則數據填充只是為了在算法上運行缺失數據，對提高算法準確度并沒有幫助；如果算法準確度較低，則數據填充對后續工作也沒有幫助，仍然存在數據質量問題。對存在缺失值的樣本進行聚類的結果通常不準確，因為樣本間的相似度度量受缺失值的影響導致樣本分類錯誤。為了提高聚類算法準確度，解決數據質量問題，使用聚類算法對帶有缺失值的數據進行聚類，準確衡量缺失數據中樣本的相似度就顯得尤為重要。

對于缺失數據的處理，比較簡單且常用的方式有直接刪除或者不處理缺失值；但是在聚類過程中必然會使樣本相似度的計算準確率降低，導致聚類的精度降低。目前應用較為廣泛的數據插補法主要有特殊值替換（均值替換、0替換和最大最小值替換等）、多重插補法、K最近鄰（K-Nearest Neighbors， KNN）插補法、期望最大化（Expectation Maximization， EM）插補法和其他機器學習算法等［12］。

針對數據不完整的情況，對缺失數據進行聚類分析引起了國內外學者的廣泛討論。Albayrak等［13］通過極大似然估計填充缺失數據，但需要一部分的完整數據進行聚類，再對缺失數據進行處理；如果數據的缺失位分布均勻，將很難篩選完整的數據進行建模。Pattanodom等［14］通過隨機填充缺失數據構建不同的聚類模型，再衡量模型的效果以篩選最佳的填充方式；然而該方法構建的模型可解釋性很難被評估，且對計算量的要求過高，如果數據規模較大，將產生大量的子模型。Huayan等［15］通過EM算法結合K-means算法處理缺失數據，但是EM算法存在收斂慢和對初始化依賴較嚴重的缺點，所以存在較大的不穩定性。喬永堅等［16］提出了一種面向高維特征缺失數據的KNN插補子空間聚類（KNN Interpolation Subspace Clustering， KISC）算法，利用數據子空間的近鄰關系填充數據；然而在樣本相似度計算上僅計算了子空間中系數矩陣的歐氏距離進行填充，并未考慮基數矩陣的關聯關系。王一棠等［17］采用了模糊聚類和非線性回歸插補的算法填充缺失數據，針對盾構機數據的效果良好；但是應用具備一定的領域限制，且實現較復雜。

針對以上算法存在的問題，本文提出了一種基于潛在因子模型（Latent Factor Model， LFM）在子空間上的缺失值注意力聚類算法。LFM結合矩陣分解可以很好地處理數據稀疏問題［18］。該算法主要分為以下幾個部分：1）針對缺失數據樣本間相似度難以度量的問題，通過LFM將原始數據空間映射到子空間，緩解樣本的稀疏性，且子空間包含樣本的結構特征信息，使得樣本相似度得以計算且具備一定可解釋性。2）在樣本相似度計算方式上引入特征矩陣進行權重注意力分配，使得樣本相似度的度量方式更精確，插補的泛化性更好。3）為了緩解在特征點對點相似度計算方式上高額的時間復雜度問題，改進了注意力權重矩陣的結構，使時間復雜度達到了指數級別的優化。

1 基于LFM的缺失值注意力聚類算法

1.1　問題定義

表1符號和定義

Tab.1　Symbols and definitions

1.2　算法框架

圖1　本文算法的框架

1.3　LFM子空間分解

1.3.1求解方法

1.3.2優化方法

1.4　樣本間的權重注意力相似度算法

1.4.1特征相似度權重圖

通過計算不同特征的余弦相似度可以得到特征間的注意力權重值，不同特征的注意力權重可以構建一個樣本注意力權重矩陣，它的結構如圖2所示。

圖2　樣本注意力權重矩陣的結構

1.4.2樣本注意力相似度計算方法

圖3　樣本相似度計算方式

如果相似集對應位置存在缺失，則計算公式如式（13）所示：

1.5　特征權重圖的結構優化

算法1 相似樣本集算法。

圖4　多指針相似度權重圖

2 實驗與結果分析

2.1　實驗數據

實驗通過4個數據集驗證本文算法的有效性，包括兩個圖像分類數據集和兩個小樣本標準分類數據集，數據集信息如表2所示。

表2　數據集信息

其中Hand-digits和COIL20為兩個被廣泛使用的圖像分類數據集，分別為手寫數字的圖像數據集和多個物體不同角度拍攝的圖像數據集［16］。Breast-cancer和Wine為Sklearn開源機器學習工具庫中的標準分類數據集。

2.2　實驗設置和說明

實驗在Ubuntu18.04，CPU 2.90 GHz 16 GB內存 GPU RTX3060 12 GB顯存上進行，其中深度學習框架采用Torch，對數據的預處理和分析采用numpy和pandas進行。

同時為了驗證多指針相似度權重圖對算法時間復雜度的提升，通過計算相似度算法每一個epoch數據插補的運行時間進行衡量，最終結果取10次運行時間的平均值。

2.3　評價指標

為了充分驗證算法的有效性，實驗選用聚類準確度（Accuracy，ACC）和歸一化互信息（Normalized Mutual Information， NMI）作為評測指標，其中：ACC可以直接衡量聚類的準確度，是常用的聚類度量指標；相較于ACC，NMI通過比較兩個聚類結果的相似程度，它的值域是［0，1］，且NMI值不受簇類標簽排列的影響［22］。NMI的計算公式如式（16）所示：

2.4　實驗結果和分析

表3展示了不同數據集分別在ACC和NMI指標上的實驗結果。

表3不同算法聚類結果的ACC和NMI比較 單位：%

Tab.3　Comparison of ACC and NMI in clustering results between different algorithms unit：%

由表3可以發現：1）在Hand-digits數據集上，當缺失比例為10%～20%時，本文算法在子空間上的ACC和NMI均高于KISC算法和特殊值填充的K-means算法；相較于次優的KISC算法，在數據缺失比例為10%的情況下，本文算法的ACC提高了2.33個百分點，NMI提高了2.77個百分點，在數據缺失比例為20%的情況下，本文算法的ACC提高了0.39個百分點，NMI提高了1.33個百分點；當缺失比例為30%～40%時，本文算法在原始空間的聚類效果優于本文算法在子空間的聚類效果，說明當缺失比例過大時，子空間的特征結構被損壞，聚類精度降低；同時，在該缺失比例下本文算法在原始空間上的聚類效果優于KISC算法和特殊值填充的K-means算法在原始空間的聚類效果，說明本文算法采用的子空間特征注意力的缺失值填充算法是有效的。2）在COIL2數據集上，本文算法在子空間上的ACC值均高于KISC算法和特殊值填充的K-means算法，說明了本文算法的先進性；但是NMI指標在缺失比例為30%時，本文算法相較于KISC算法NMI指標精度有所下降，在缺失比例為40%時，本文算法在原始空間上的NMI指標最優，可以發現當缺失比例為30%時本文算法在原始空間的NMI指標和KISC算法在子空間的NMI指標差距較小，進一步說明了子空間特征注意力的缺失值填充算法的有效性。3）在Breast-cancer和Wine數據集上，本文算法的ACC值均高于KISC算法和特殊值填充的K-means算法，只有當Wine數據集缺失比例為40%時，本文算法的NMI值低于0填充的K-means算法。進一步發現，當缺失比例擴大時，本文算法和其他算法的差距逐漸縮小，如在Wine數據集上，當缺失比例位于10%～30%，本文算法的ACC和NMI指標均為最優；但當缺失比例達到40%，本文算法的NMI指標相較于K-means算法低了1.39個百分點，說明在缺失比例過大的情況下，子空間對特征的整體概括能力有所下降。所以本文算法在缺失比例位于10%～30%區間具備明顯優勢。

3 結語

本文針對傳統聚類算法在對缺失樣本進行數據填充過程中存在樣本相似度難度量且填充數據質量差的問題，提出了一種基于LFM在子空間上的缺失值注意力聚類算法。該算法通過LFM解決了因為樣本稀疏性導致相似距離無法度量、精度較低的問題；同時在樣本相似度的計算上考慮到子空間特征矩陣之間的相關性，并將它引入相似度計算方式，提高了樣本相似度計算方式的準確度和泛化性。最后在多個數據集上通過ACC和NMI指標驗證了算法的有效性和可靠性。同時實驗中發現：當數據缺失比例增大時，子空間對特征信息的概括能力有所降低；當數據缺失比例過大時，當前算法的聚類精度會有所下降。如何在數據缺失比例過大的情況下有效提高子空間下數據聚類算法的精度，需要進一步研究。

[1] AHALYA G，PANDEY H M. Data clustering approaches survey and analysis ［C］// Proceedings of the 2015 International Conference on Futuristic Trends on Computational Analysis and Knowledge Management. Piscataway： IEEE，2015： 532-537.

[2] XU H， YAO S， LI Q， et al. An improved K-means clustering algorithm［C］// Proceedings of the 2020 IEEE 5th International Symposium on Smart and Wireless Systems within the Conferences on Intelligent Data Acquisition and Advanced Computing Systems. Piscataway： IEEE， 2020： 1-5.

[3] 王一妹，劉輝，宋鵬，等.基于高斯混合模型聚類的風電場短期功率預測方法［J］.電力系統自動化，2021，45（7）：37-43.（WANG Y M， LIU H， SONG P， et al. Short-term power forecasting method of wind farm based on Gaussian mixture model clustering ［J］. Power System Automation， 2021，45（7）： 37-43.）

[4] JEBARI S， SMITI A， LOUATI A.AF-DBSCAN： an unsupervised automatic fuzzy clustering method based on DBSCAN approach［C］// Proceedings of the 2019 IEEE International Work Conference on Bioinspired Intelligence. Piscataway： IEEE，2019：1-6.

[5] RONG Y， LIU Y.Staged text clustering algorithm based on K-means and hierarchical agglomeration clustering［C］// Proceedings of the 2020 IEEE International Conference on Artificial Intelligence and Computer Applications. Piscataway： IEEE，2020：124-127.

[6] 任麗娜，秦永彬，黃瑞章，等.基于多層子空間語義融合的深度文本聚類［J］.計算機應用研究， 2023，40（1）：70-74，79.（REN L N， QIN Y B， HUANG R Z，et al. Deep document clustering model via multi-layer subspace semantic fusion ［J］. Application Research of Computers， 2023，40（1）：70-74，79.）

[7] TAN L， GU S， WU C， et al. K-means clustering method based on node similarity in traditional Chinese medicine efficacy［C］// Proceedings of the 2020 39th Chinese Control Conference. Piscataway： IEEE，2020：742-747.

[8] YI Y. Design of intelligent recommendation APP for eco-tourism routes based on popular data clustering of points of interest［C］// Proceedings of the 2021 2nd International Conference on Smart Electronics and Communication. Piscataway： IEEE，2021： 1270-1273.

[9] SHRUTHI S， JOSE A M， ANUROOP P R. Improvisation of cluster efficiency using min-cut algorithm in social networks［C］// Proceedings of the 2017 International Conference on Communication and Signal Processing. Piscataway： IEEE，2017：1641-1644.

[10] LIU Q，HAUSWIRTH M. A provenance meta learning framework for missing data handling methods selection［C］// Proceedings of the 2020 11th IEEE Annual Ubiquitous Computing， Electronics & Mobile Communication Conference. Piscataway： IEEE，2020： 349-358.

[11] 徐宇明，陳誠，熊赟，等.APT-KNN：一種面向分類問題的高效缺失值填充算法［J］.計算機應用與軟件，2011，28（4）：135-139.（XU Y M， CHEN C， XIONG Y，et al. APT-KNN： an efficient missing value imputation method oriented toward classification issue ［J］. Computer Applications and Software， 2011， 28 （4）： 135-139.）

[12] 徐鴻艷，孫云山，秦琦琳，等.缺失數據插補方法性能比較分析［J］.軟件工程，2021，24（11）：11-14.（XU H Y， SUN Y S， QIN Q L， et al. Comparative analysis of the performance of interpolation methods for of missing data［J］. Software Engineering， 2021，24 （11）： 11-14.）

[13] ALBAYRAK M， TURHAN K， KURT B. A missing data imputation approach using clustering and maximum likelihood estimation［C］// Proceedings of the 2017 Medical Technologies National Congress. Piscataway：IEEE， 2017：1-4.

[14] PATTANODOM， IAM-ON N， BOONGOEN T. Clustering data with the presence of missing values by ensemble approach［C］// Proceedings of the 2016 Second Asian Conference on Defence Technology. Piscataway： IEEE， 2016： 151-156.

[15] HUAYAN S， YELI L， RUNFEI Z， et al. Accelerating EM missing data filling algorithm based on the K-means［C］// Proceedings of the 2018 4th Annual International Conference on Network and Information Systems for Computers. Piscataway： IEEE， 2018：401-406.

[16] 喬永堅，劉曉琳，白亮.面向高維特征缺失數據的K最近鄰插補子空間聚類算法［J］.計算機應用，2022，42（11）：3322-3329.（QIAO Y J， LIU X L， BAI L. K-nearest neighbor interpolation subspace clustering algorithm for high-dimensional data with feature missing ［J］. Journal of Computer Application， 2022，42（11）： 3322-3329.）

[17] 王一棠，龐勇，張立勇，等.面向盾構機不完整數據的模糊聚類與非線性回歸填補［J］.機械工程學報， 2023， 59（12）： 28-37.（WANG Y T， PANG Y， ZHANG L Y ，et al. Fuzzy clustering and nonlinear regression filling for incomplete data of shield machine ［J］. Journal of Mechanical Engineering， 2023， 59（12）： 28-37.）

[18] 陳曄，劉志強.基于LFM矩陣分解的推薦算法優化研究［J］.計算機工程與應用，2019，55（2）：116-120.（CHEN Y， LIU Z Q. Research on improved recommendation algorithm based on LFM matrix factorization ［J］. Computer Engineering and Applications， 2019，55（2）： 116-120.）

[19] XIONG Y， LI H. Collaborative filtering algorithm in pictures recommendation based on SVD［C］// Proceedings of the 2018 International Conference on Robots & Intelligent System. Piscataway： IEEE， 2018：262-265.

[20] 楊鏌. 基于偏置LFM和LSH的混合電影推薦算法研究［D］.武漢：華中師范大學，2021：13-15.（YANG M. Research on hybrid movie recommendation algorithm based on bias LFM and LSH［D］. Wuhan： Central China Normal University， 2021： 13-15.）

[21] GUO S， LI C. Hybrid recommendation algorithm based on user behavior［C］// Proceedings of the 2020 IEEE 9th Joint International Information Technology and Artificial Intelligence Conference. Piscataway： IEEE， 2020：2242-2246.

[22] 龍建武，王強.反向近鄰構造連通圖的聚類算法［J/OL］.計算機科學與探索：1-15 ［2023-02-07］. http：//kns.cnki.net/kcms/detail/11.5602.TP.20220930.1744.006.html.（LONG J W， WANG Q. Clustering algorithm for constructing connected graphs by reverse nearest neighbors ［J/OL］. Journal of Frontiers of Computer Science and Technology： 1-15 ［2023-02-07］. http：//kns.cnki.net/kcms/detail/11.5602.TP.20220930.1744.006.html.）

Missing value attention clustering algorithm based on latent factor model in subspace

WANG Xiaofei1，2， BAO Shengli1，2*， CHEN Jionghuan1，2

（1，，610041，；2，100049，）

To solve the problems that traditional clustering algorithms are difficult to measure the sample similarity and have poor quality of filled data in the process of filling missing samples， a missing value attention clustering algorithm based on Latent Factor Model （LFM） in subspace was proposed. First， LFM was used to map the original data space to a low dimensional subspace to reduce the sparsity of samples. Then， the attention weight graph between different features was constructed by decomposing the feature matrix obtained from the original space， and the similarity calculation method between subspace samples was optimized to make the calculation of sample similarity more accurate and more generalized. Finally， to reduce the high time complexity in the process of sample similarity calculation， a multi-pointer attention weight graph was designed for optimization. The algorithm was tested on four proportional random missing datasets. On the Hand-digits dataset， compared with the KISC （K-nearest neighbors Interpolation Subspace Clustering） algorithm for high-dimensional feature missing data， when the missing data was 10%， the Accuracy （ACC） of the proposed algorithm was improved by 2.33 percentage points and the Normalized Mutual Information （NMI） was improved by 2.77 percentage points； when the missing data was 20%， the ACC of the proposed algorithm was improved by 0.39 percentage points， and the NMI was improved by 1.33 percentage points， which verified the effectiveness of the proposed algorithm.

Latent Factor Model (LFM); missing value; attention mechanism; clustering algorithm; subspace

This work is partially supported by Western Young Scholars Project of Chinese Academy of Sciences （RRJZ2021003）.

WANG Xiaofei， born in 1997， M. S. candidate. His research interests include machine learning， recommendation algorithm.

BAO Shengli， born in 1973， Ph. D.， research fellow， His research interests include software engineering， big data.

CHEN Jionghuan， born in 1998， M. S. candidate. His research interests include machine learning， big data.

TP391.1

A

1001-9081（2023）12-3772-07

10.11772/j.issn.1001-9081.2022121838

2022?12?12；

2023?02?13；

2023?02?16。

中國科學院西部青年學者項目（RRJZ2021003）。

王嘯飛（1997—），男，湖南慈利人，碩士研究生，主要研究方向：機器學習、推薦算法；鮑勝利（1973—），男，安徽黃山人，研究員，博士，主要研究方向：軟件工程、大數據；陳炯環（1998—），男，山東濰坊人，碩士研究生，主要研究方向：機器學習、大數據。