基于動態(tài)加權張量距離的多聚類算法

薛狀狀，李鵬，2*，樊衛(wèi)北，2，張宏俊，孟凡朔

基于動態(tài)加權張量距離的多聚類算法

薛狀狀1，李鵬1，2*，樊衛(wèi)北1，2，張宏俊1，孟凡朔1

（1.南京郵電大學 計算機學院、軟件學院、網絡空間安全學院，南京 210023； 2.南京郵電大學 網絡安全與可信計算研究所，南京 210023）（ ? 通信作者電子郵箱lipeng@njupt.edu.cn）

基于張量的多聚類算法（TMC）在衡量屬性重要性時忽略了對象張量內部屬性組合的關聯性，而且在不同的特征空間選擇下，固定權重策略導致所選與未選擇特征空間沒有完全分離。針對上述問題，提出一種基于動態(tài)加權張量距離（DWTD）的多聚類算法（DWTD-MC）。首先，為提升各特征空間屬性重要性衡量的準確性，建立了自-關聯張量模型；其次，構建多視圖權重張量模型，在不同特征空間選擇下通過動態(tài)加權策略滿足多聚類分析的需求；最后，使用DWTD衡量數據點的相似性，生成最終的多聚類結果。在真實數據集上的仿真實驗結果表明，DWTD-MC在杰卡德指數（JI）、鄧恩指數（DI）、DB指數（DB）和輪廓系數（SC）評價指標上均優(yōu)于TMC等對比算法，而且可以在獲得較高質量的聚類結果的同時，使各聚類結果之間保持較低的冗余度，滿足多聚類分析的任務需求。

異構數據；多聚類；張量；張量距離；動態(tài)加權；社會物理信息系統

0 引言

隨著網絡化應用的發(fā)展，信息和物理系統被進一步融會貫通，網絡與人類社會緊密聯合，形成了融合人、機器、信息于一體的系統，即社會物理信息系統（Cyber-Physical-Social System，CPSS）［1］。從CPSS中產生了大量的多源異構數據，包括結構化、半結構化和非結構化數據。如何對這些數據進行分析，挖掘出其中潛在的知識和價值，對社會和企業(yè)有著重要意義。

聚類分析作為數據分析中的重要技術，可以揭示數據中的隱藏模式，但是單一的聚類模式難以充分挖掘出來源多樣、特征高維、關系復雜的異構數據的隱藏信息。多聚類作為數據挖掘的新興研究領域，近年來受到各領域學者的廣泛關注［2］。CPSS中，從多個維度產生了大規(guī)模的多源異構數據，這些數據往往具有來源多樣、類型復雜、維度高、特征模糊等特點。多聚類可以根據實際應用的不同，從數據多個角度產生多種不同的聚類結果，更深層次地揭示數據中的不同結構與隱藏信息，更好地滿足當今大數據多分析任務的需求［3］。

在單聚類領域，典型的密度峰值聚類算法［4］能夠高效地發(fā)掘任意形狀的類簇，且不易發(fā)生錯誤，聚類質量較高；但算法計算復雜度較高，限制了它在大規(guī)模數據集中的應用。針對此問題，徐曉等［5］提出了一種基于網格篩選的大規(guī)模密度峰值聚類算法，使用網格化方法去除部分密度稀疏的點，可以在保證聚類準確性的基礎上有效降低計算復雜度；Bo等［6］提出了一種結構化深度聚類網絡將結構信息集成到深度聚類，克服了現有方法在數據結構表示方面的不足。多聚類分析的研究主要集中在多視圖聚類［7］、可選擇聚類［8］和子空間聚類［9］，這些方法雖然能在一定程度滿足多聚類分析的需求，但也具有局限性。比如，Tzortzis等［10］提出了一種基于核的加權多視圖聚類算法，該算法通過融合多源信息，從事物的不同角度生成多個特征描述視圖，以此降低單個視圖內的噪聲，最終產生比只使用單一視圖更高質量的聚類結果；但不能從多角度選擇不同特征的組合產生不同的聚類結果。Yang等［11］提出了一種基于非負矩陣分解（Nonnegative Matrix Factorization， NMF）的非冗余多重聚類算法，該算法建立在NMF的基礎上，利用非負性實現非冗余，能創(chuàng)建一個或多個高質量且彼此不同的聚類結果；但主要針對小規(guī)模、單領域數據集，不能通過結合多源信息來提高聚類質量。Gan等［12］提出了一種使用近鄰傳播的子空間聚類算法，該算法在近鄰傳播算法中引入屬性權重，并根據當前分區(qū)迭代更新屬性權重，以此識別嵌入簇的子空間，能夠實現高維數據集聚類分析并通過提取的子空間發(fā)現良好的類簇；但是該算法不能從不同的角度產生不同的可解釋的聚類結果。歐琦媛等［13］提出了一種基于壓縮子空間對齊的多核聚類算法，使用線性壓縮矩陣對采樣過程進行建模，將采樣和多核聚類任務合并到一個統一的框架，在融合多源信息提高聚類性能方面的同時大幅提高了計算效率；但只能生成單一的聚類結果。綜上所述，這些多聚類算法主要針對低維、小規(guī)模、單領域數據集，它們的聚類結果難以解釋，且無法根據現實需要靈活變化聚類對象生成不同的聚類結果。

Zhao等［14］提出了一種基于張量的多聚類算法（Tensor-based Multiple Clustering algorithm， TMC）能夠克服上述局限性。TMC使用張量模型對異構數據進行統一表示，適用于高維、多領域的數據，使用多線性數據排名算法為多屬性組合賦予權重，最后通過不同特征空間選擇生成不同的聚類結果；但該算法在衡量屬性重要性和固定權重策略導致的所選與未選擇特征空間沒有完全分離兩方面存在不足。在聚類結果的評價指標領域，唐益明等［15］提出了一種新的基于數據集幾何結構和大小集群的模糊聚類的有效性指標GSDC，解決了現有指標對數據結構復雜和集群大小差異懸殊的數據集難以作出精確判斷的問題。嚴加展等［16］提出了一種改進的有效性評價指標CSC，該指標結合簇內數據平方誤差和、隸屬度權值等定義，能解決現有評價指標沒有涉及到數據集真實幾何分布結構和先驗信息的問題。

為解決多聚類算法領域中，多聚類結果冗余度高、聚類結果難以解釋等問題，本文在TMC的基礎上提出一種基于動態(tài)加權張量距離的多聚類算法（Multiple Clustering algorithm based on Dynamic Weighted Tensor Distance，DWTD-MC）。本文的主要工作如下：

1）提出自-關聯張量模型改進多線性數據排名算法，以更準確地衡量各屬性的重要性。

2）構建多視圖權重張量模型。在不同特征空間選擇下，賦予各多屬性組合對應的權重，分離各特征空間，減少未選擇特征空間對已選特征空間的影響。

3）在上述兩項工作基礎上，提出動態(tài)加權張量距離（Dynamic Weighted Tensor Distance， DWTD）的概念，并將它作為不同數據間相似性衡量的標準。

4）在真實的數據集上進行對比實驗驗證，實驗結果表明，DWTD-MC能夠生成冗余度更低、類內結構更緊湊的多聚類結果。

1 TMC

1.1　張量與張量距離

1.1.1張量

張量理論起源于數學，在力學中有重要應用。現在，張量已成功應用于計算機視覺、圖像識別等領域［17］。張量可以視為對矩陣的高階推廣。向量為一階張量，矩陣為二階張量，三階或更高階的張量稱為高階張量。

1.1.2張量距離

1.2　TMC

首先，使用多線性數據排名算法［19］計算各特征空間的屬性排名向量，衡量特征空間屬性的重要程度。該算法結合轉移概率模型［20］對網頁排名算法［21］的擴展。算法流程如下：

1.3　TMC的局限性

本文主要針對TMC以下兩個局限性進行討論。

1）在關聯張量的構造過程中，僅考慮不同對象張量之間的各屬性組合的關聯性，忽視了一個對象張量內部各屬性組合的關聯，造成各特征空間屬性權重度量不夠準確。

2）在不同特征空間選擇下，采用固定權重策略，忽視了不同特征空間選擇的差異性，導致所選特征空間與未選特征空間沒有完全分離，在衡量各屬性組合重要性和對象張量之間相似性時，未選擇特征空間對其他特征空間產生影響；同時固定權重會導致各聚類模式間相似度較大，多聚類結果之間冗余度過高。

2 基于動態(tài)加權張量距離的多聚類算法

針對TMC中存在的不足，本文提出了一種基于動態(tài)加權張量距離的多聚類算法DWTD-MC。首先，提出了自-關聯張量衡量各對象張量之間關聯，以此改進多線性數據排名算法；其次，提出多視圖權重張量模型，采用動態(tài)加權策略，將各特征空間分離，降低聚類結果冗余度；最后在此基礎上，使用動態(tài)加權張量距離作為對象張量相似性衡量的依據，生成多聚類結果。

2.1　動態(tài)加權張量距離模型構建

2.1.1自-關聯張量模型

圖1　三階對象張量

2.1.2多視圖權重張量模型

圖2　三階權重張量

算法1 多視圖權重張量算法。

repeat

end for

for=1 todo

end for

2.1.3動態(tài)加權張量距離

張量距離能夠有效衡量高階空間對象之間的相似度，但根據相關定義可知，在張量距離中，坐標對應的屬性組合被認為是同等重要的，并且反映元素位置內在關系的度量系數是固定的。這使張量距離的概念不能降低噪聲屬性的影響，同時不能滿足多聚類分析的任務需求。而在TMC中，通過給屬性組合添加權重因子能有效降低噪聲屬性的影響，但固定的加權策略忽視了不同特征空間選擇之間的差異，也使聚類性能較差。基于此問題，本文提出動態(tài)加權張量距離的概念，在張量距離中引入特征空間選擇向量和動態(tài)權重因子，可以根據情境選擇特征空間進行多聚類分析，同時降低噪聲屬性的影響以及多聚類結果之間的冗余度。

2.2　多視圖相似度矩陣張量模型構建

圖3　多視圖相似度矩陣張量

2.3　算法流程

基于上述介紹的理論和模型，本文結合密度峰值聚類算法，提出了基于動態(tài)加權張量距離的多聚類算法DWTD-MC。

算法2 基于動態(tài)加權張量距離的多聚類算法。

for=1 todo

end for

end for

end for

end for

end for

3 實驗與結果分析

本章對DWTD-MC進行實驗分析，并與以下算法進行比較：TMC、使用不加權的張量距離衡量相似性的多聚類算法（Multiple Clustering algorithm based on Non-Weighted Tensor Distance， NWTD-MC）［14］和基于張量分解的多聚類算法（Multiple Clustering algorithm based on Tensor Decomposition， TD-MC）［23］。

3.1　復雜度分析

3.2　數據集

本文使用真實數據集進行實驗，數據集分別為：1）氣候數據集（包括廣州、北京、上海等地區(qū)氣候狀況），每條記錄包括天氣狀況、溫度、濕度特征（記錄范圍分別為晴/多云/陰/雨、［21，33］℃、［35，98］%rh），后文記為數據集1；2）空氣質量數據集（包括多地空氣質量狀況），每條記錄包括PM2.5、SO2、NO2、O3等特征，后文記為數據集2，它的詳細信息見表1。通過不同的特征選取與聚類分析，可以將在此特征上相似度較高的地區(qū)進行分組，生成多聚類結果。

表1　空氣質量數據集特征 單位： mg/m3

3.3　評價指標

評價指標的選取依據：1）對不同的聚類結果之間冗余度進行評價，分析算法在多聚類方面的性能；2）對各聚類結果的內部質量進行評價，分析算法的聚類性能。

1）杰卡德指數（Jaccard Index，JI）。JI用來度量兩種不同聚類結果之間的相似性，衡量聚類結果之間的冗余度［24］。假設和是兩種不同的聚類結果，JI定義如下：

其中：分子部分是一種類間間距度量，表示不同類簇中數據點間的最小距離；分母是一種類內間距度量，表示同一類簇中數據點間的最大距離。根據式（18），DI值越大，表示類內越緊湊，類與類之間越能區(qū)分開，聚類質量越好。

其中：avg（cl）、avg（cl）表示對應類簇內，樣本間的平均距離；den（cl，cl）表示兩個類簇中心點間的距離。根據式（19），DB值越小，表明不同類簇間分離度更好。

4）輪廓系數（Silhouette Coefficient， SC）。SC是所有樣本輪廓系數的平均值，定義如下：

3.4　結果分析

首先對數據進行預處理：

圖6、7分別為數據集1和數據集2上的DI值， 其中：圖6橫軸的A～G分別表示特征空間選擇向量｛0，0，1｝、｛0，1，0｝、｛1，0，0｝、｛0，1，1｝、｛1，0，1｝、｛1，1，0｝、｛1，1，1｝；圖7橫軸的A～G分別表示特征空間選擇向量｛1，0，1，0，1｝、｛1，1，0，1，0｝、｛1，1，1，0，0｝、｛1，1，0，1，1｝、｛1，0，1，1，1｝、｛1，1，1，1，0｝、｛1，1，1，1，1｝。從直方圖可以看出，DWTD-MC的DI值大多高于TMC、NWTD-MC與TD-MC。但也出現了部分DWTD-MC的DI值略低的情況，分析其原因：在此種聚類模式下，數據分布較為均勻，類簇與類簇之間劃分不夠明顯，導致DI值較低。從表2中4組實驗的平均DI值可以看出，DWTD-MC的平均DI值都相對較高。DWTD-MC通過動態(tài)地添加權重，將特征空間完全分離，區(qū)分了不同特征空間選擇下，多屬性組合重要程度的不同，降低了噪聲屬性的影響，最終提高了聚類結果的質量。

從表2中4組實驗的平均DB值和平均SC值可知，DWTD-MC生成的聚類結果中不同類簇間分離度更好，同一類簇內更為緊湊。

綜上所述，相較于TMC、NWTD-MC與TD-MC，DWTD-MC所產生的多聚果之間有著更低的冗余度，產生的聚類結果更為豐富，同時每種聚類結果的類內結構也更緊湊，聚類結果質量更高。

圖5　數據集2上的JI值

圖6　數據集1上的DI值

圖7　數據集2上的DI值

表2　指標平均值統計表

4 結語

本文針對TMC中關聯張量模型無法準確衡量屬性重要性，特征空間未完全分離導致的聚類結果冗余度高、質量差的問題，提出了一種基于動態(tài)加權張量距離的多聚類算法（DWTD-MC）。實驗結果表明，DWTD-MC具有更好的聚類效果。但該算法中，使用張量模型統一表示異構數據時，并不能適用于所有種類的數據；聚類分析時僅將數據對象間的距離作為相似度衡量的依據，指標單一可能會使得聚類結果不夠準確；在多視圖相似度矩陣張量的構建過程與密度峰值聚類算法中，涉及到大量的張量、矩陣運算，這導致該算法的計算復雜度較高，影響算法的效率。因此，下一步要研究如何更全面表示多源異構數據，多角度衡量數據對象相似度，以及從并行化等角度提高計算效率的方法。

[1] ZHOU Y， YU F R， CHEN J， et al. Cyber-physical-social systems： a state-of-the-art survey， challenges and opportunities［J］. IEEE Communications Surveys and Tutorials， 2020， 22（1）： 389-425.

[2] MüLLER E， ASSENT I， GüNNEMANN S， et al.special issue on discovering， summarizing and using multiple clusterings［J］. Machine Learning， 2015， 98（1/2）： 1-5.

[3] WANG J， WANG X， YU G， et al. Discovering multiple co-clusterings with matrix factorization［J］. IEEE Transactions on Cybernetics， 2021， 51（7）： 3576-3587.

[4] RODRIGUEZ A， LAIO A. Clustering by fast search and find of density peaks［J］. Science， 2014， 344（6191）： 1492-1496.

[5] 徐曉，丁世飛，孫統風，等. 基于網格篩選的大規(guī)模密度峰值聚類算法［J］. 計算機研究與發(fā)展， 2018， 55（11）： 2419-2429.（XU X， DING S F， SUN T F， et al. Large-scale density peaks clustering algorithm based on grid screening［J］. Journal of Computer Research and Development， 2018， 55（11）： 2419-2429.）

[6] BO D， WANG X， SHI C， et al. Structural deep clustering network［C］// Proceedings of the 2020 Web Conference. Republic and Canton of Geneva： International World Wide Web Conferences Steering Committee， 2020： 1400-1410.

[7] LIU X， JI S， GL?NZEL W， et al. Multiview partitioning via tensor methods［J］. IEEE Transactions on Knowledge and Data Engineering， 2013， 25（5）： 1056-1069.

[8] HE T， ONG Y S， HU P. Multi-source propagation aware network clustering［J］. Neurocomputing， 2021， 453： 119-130.

[9] ELHAMIFAR E， VIDAL R. Sparse subspace clustering： algorithm， theory， and applications［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2013， 35（11）： 2765-2781.

[10] TZORTZIS G， LIKAS A. Kernel-based weighted multi-view clustering［C］// Proceedings of the IEEE 12th International Conference on Data Mining. Piscataway： IEEE， 2012： 675-684.

[11] YANG S， ZHANG L. Non-redundant multiple clustering by nonnegative matrix factorization［J］. Machine Learning， 2017， 106（5）： 695-712.

[12] GAN G， NG M K P. Subspace clustering using affinity propagation［J］. Pattern Recognition， 2015， 48（4）： 1455-1464.

[13] 歐琦媛，祝恩. 基于壓縮子空間對齊的多核聚類算法［J］. 計算機工程與科學， 2021， 43（10）： 1730-1735.（OU Q Y， ZHU E. Multi-kernel clustering algorithm based on compressed subspace alignment［J］. Computer Engineering and Science， 2021， 43（10）： 1730-1735.）

[14] ZHAO Y， YANG L T， ZHANG R. A tensor-based multiple clustering approach with its applications in automation systems［J］. IEEE Transactions on Industrial Informatics， 2018， 14（1）： 283-291.

[15] 唐益明，豐剛永，任福繼，等. 面向結構復雜數據集的模糊聚類有效性指標［J］. 電子測量與儀器學報， 2018， 32（4）：119-127.（TANG Y M， FENG G Y， REN F J， et al. Fuzzy clustering validity index facing data set with complexity structure［J］. Journal of Electronic Measurement and Instrumentation， 2018， 32（4）： 119-127.）

[16] 嚴加展，陳華，李陽. 改進的模糊C-均值聚類有效性指標［J］. 計算機工程與應用， 2020， 56（9）： 156-161.（YAN J Z， CHEN H， LI Y. Improved fuzzy C-means clustering validity index［J］. Computer Engineering and Applications， 2020， 56（9）： 156-161.）

[17] KOLDA T G， BADER B W. Tensor decompositions and applications［J］. SIAM Review， 2009， 51（3）： 455-500.

[18] LIU Y， LIU Y， CHAN K C C. Tensor distance based multilinear locality-preserved maximum information embedding［J］. IEEE Transactions on Neural Networks， 2010， 21（11）： 1848-1854.

[19] 匡立偉. 基于張量的大數據統一表示及降維方法研究［D］. 武漢：華中科技大學， 2016： 32-35.（KUANG L W. A tensor-based approach for united representation and dimensionality reduction of big data［D］. Wuhan： Huazhong University of Science and Technology， 2016： 32-35）

[20] JOSE M， MARTINEZ V， REINALDO A， et al. On the limiting probabilities of theM/E/1 queueing system［J］. Statistics and Probability Letters， 2014， 88： 56-61.

[21] GUO P-C， GAO S-C， GUO X-X. A modified newton method for multilinear PageRank［J］. Journal of Mathematics， 2018， 22（5）： 1161-1171.

[22] KUANG L， HAO F， YANG L T， et al. A tensor-based approach for big data representation and dimensionality reduction［J］. IEEE Transactions on Emerging Topics in Computing， 2014， 2（3）： 280-291.

[23] ZHAO Y， YANG L T， ZHANG R. Tensor-based multiple clustering approaches for cyber-physical-social applications［J］. IEEE Transactions on Emerging Topics in Computing， 2020， 8（1）： 69-81.

[24] LIU S， ZHENG J， LIN Q， et al. Evolutionary multi and many-objective optimization via clustering for environmental selection［J］. Information Sciences， 2021， 578： 930-949.

[25] ZHENG X， LIU X， CHEN J， et al. Adaptive partial graph learning and fusion for incomplete multi-view clustering［J］. International Journal of Intelligent Systems， 2022， 37（1）： 991-1009.

Multiple clustering algorithm based on dynamic weighted tensor distance

XUE Zhuangzhuang1， LI Peng1，2*， FAN Weibei1，2， ZHANG Hongjun1， MENG Fanshuo1

（1，，210023，；2，，210023，）

When measuring the importance of attributes in Tensor-based Multiple Clustering algorithm （TMC）， the relevance of attribute combinations within object tensors are ignored， and the selected and unselected feature space are incompletely separated because of the fixed weight strategy under different feature space selection. For above problems， a Multiple Clustering algorithm based on Dynamic Weighted Tensor Distance （DWTD-MC） was proposed. Firstly， a self-association tensor model was constructed to improve the accuracy of attribute importance measurement of each feature space. Then， a multi-view weight tensor model was built to meet the task requirements of multiple clustering analysis by dynamic weighting strategy under different feature space selection. Finally， the dynamic weighted tensor distance was used to measure the similarity of data points， generating multiple clustering results. Simulation results on real datasets show that DWTD-MC outperforms comparative algorithms such as TMC in terms of Jaccard Index （JI）， Dunn Index （DI）， Davies-Bouldin index （DB） and Silhouette Coefficient （SC）. It can obtain high quality clustering results while maintaining low redundancy among clustering results， as well as meeting the task requirements of multiple clustering analysis.

heterogeneous data; multiple clustering; tensor; tensor distance; dynamically weighting; Cyber-Physical-Social System (CPSS)

1001-9081（2023）11-3449-08

10.11772/j.issn.1001-9081.2022101626

2022?11?09；

2022?12?29；

國家自然科學基金資助項目（62102194）； 江蘇省“六大人才高峰”高層次人才項目（RJFW?111）。

薛狀狀（1997—），男，江蘇睢寧人，碩士研究生，主要研究方向：機器學習、多聚類算法； 李鵬（1979—），男，福建長汀人，教授，博士，CCF會員，主要研究方向：計算機通信網絡、無線傳感器網絡、信息安全； 樊衛(wèi)北（1987—），男，河南開封人，講師，博士，CCF會員，主要研究方向：并行和分布式系統、數據中心網絡、云計算； 張宏俊（1985—），男，安徽皖和人，博士研究生，主要研究方向：基于張量鏈分解的多聚類及并行優(yōu)化； 孟凡朔（1997—），男，江蘇徐州人，碩士研究生，主要研究方向：張量鏈式分解。

TP181

A

2023?01?03。

This work is partially supported by National Natural Science Foundation of China （62102194）， “Six Talent Peaks” High-level Talents Project of Jiangsu Province （RJFW-111）.

XUE Zhuangzhuang， born in 1997， M. S. candidate. His research interests include machine learning， multiple clustering algorithm.

LI Peng， born in 1979， Ph. D.， professor. His research interests include computer communication networks， wireless sensor networks， information security.

FAN Weibei， born in 1987， Ph. D.， lecturer. His research interests include parallel and distributed systems， data center network， cloud computing.

ZHANG Hongjun， born in 1985， Ph. D. candidate. His research interests include multiple clustering and parallel optimization based on tensor chain decomposition.

MENG Fanshuo， born in 1997， M. S. candidate. His research interests include tensor chain decomposition.