混合屬性數據集的自適應譜聚類算法

中圖分類號：TP391 文獻標志碼：A

Abstract：To address the attribute skew problem in spectral clustering algorithms when handling mixed attribute datasets and the manual selection of Gaussian kernel function scale parameters，we propose an improved classification attribute similarity measurement and shared natural neighbor adaptive spectral clustering algorithm （IEMN-SC）.This algorithm improves the traditional classification attribute similarity measurement by calculating the information entropy of numerical attributes and categorical attributes to obtain a balancing difference factor. In the Gaussian kernel function，it uses shared natural neighbors to compute the neighborhood radius of each sample and adaptively solves the scale parameter. Finally，it constructs a similarity matrix of mixed attribute samples through the kernel function for spectral clustering.Experimental results show that the IEMN-SC algorithm outperforms four commonly used mixed attribute data clustering algorithms in terms of ACC，ARI，and NMI metrics and provides more stable clustering results. This algorithm effectively solves the attribute skew problem and can fully adaptively discover the true distribution information of mixed attribute datasets，significantly improving clustering efficiency.

Key words：information entropy; spectral clustering; mixed-attribute dataset; natural neighbors；adaptive

0 引言

聚類分析作為數據挖掘技術中的一項重要技術，專注于根據數據對象之間的相似性進行分組，揭示數據的內部結構和隱藏模式.聚類作為無監督學習方法是數據科學和機器學習鄰域的關鍵研究課題，在機器學習、圖像分析、信息檢索、數據壓縮和生物信息學等領域都得到了廣泛的研究和應用[.傳統的聚類算法，如Kmeans 算法[2]、PAM[3]等構成經典的基于劃分的聚類算法，只適合發現球狀簇，無法發現非凸形狀的簇，且易陷入局部最優而不能發現數據的真實分布.

譜聚類基于譜圖理論，將數據聚類問題視為圖劃分問題，構造無向加權圖，從而實現分組達到聚類的目的.譜聚類在處理非線性可分數據時具有明顯的優勢，其堅實的理論基礎，可以適用于非測度空間，無需對數據整體結構作出假設且能收斂到全局最優解，具有識別任意形狀分布的聚類能力[4].研究者們[5-8]主要從相似矩陣的構造、特征向量的選取、聚類數目的確定、參數的優化設置等方面對譜聚類算法進行改進并取得了不錯的效果.

實際應用數據中混合屬性數據更為常見，數據的相似性度量是混合屬性數據聚類分析中的一個關鍵問題.解決混合屬性數據聚類問題有兩種常見策略，一種是將數據集統一轉化進行度量.David等9提出SpectralCAT算法，將數據自動轉換成分類型數據，再使用譜聚類實現聚類；Wei等[1°基于互信息提出一種無監督特征轉化方法，將分類特征轉換為數值特征后使用Kmeans算法進行聚類.但是，上述數據轉化過程難免會破壞原始數據結構，造成部分信息損失.

另一種策略是對混合屬性數據使用特定相似性度量.Huang等[11]提出的 Kprototypes 算法通過結合Kmeans算法和Kmodes算法實現對混合類型數據的聚類；Mcparland等[12」提出的Clust-MD算法使用潛在變量模型對混合數據進行聚類，并使用EM算法進行參數估計；Chu等[13]提出SMC算法，利用信息熵定義了一種分類屬性相似度度量公式并提出一種邊界數據分配策略；Rezaei等[14提出了智能選擇聚類中心并改進分類數據距離度量的算法，利用大量相似特征進行混合數據聚類.盡管這些算法在改善簇歸屬問題上取得了一定的進展，但是由于大多是基于迭代的方法，故對初始聚類中心較為敏感，更適合處理凸簇數據，

此外，Mbuga等[15]替換傳統譜聚類中的歐式距離度量，采用加權和全局不相似度測量方式構建相似度矩陣；李順勇等[16]提出的IEMLRR算法通過引入信息熵加權機制，有效解決了多視圖子空間聚類中視圖信息不均衡的問題，提高了聚類的準確性和魯棒性;陳曉曼等[17提出IJM-SC算法，基于Jaccard距離、馬氏距離的思想，引人核函數系數度量混合屬性相似度.這些方法都提高了數據聚類效果，但都涉及到人為參數選擇問題，增加了算法的不確定性.Liu[18]提出的AMDPC算法，利用混合屬性數據的統一距離度量構造距離矩陣，基于K近鄰計算局部密度，提出基于三個拐點的聚類中心自動確定方法.郭笑雨等[19提出DSSD算法，結合密度峰值思想，設計了一種基于密度峰值的初始類中心決策值選擇方法，解決了密度調整譜聚類中的聚類結果不穩定問題.然而，這些算法仍大多局限于數值型數據，無法滿足混合型數據的需求.

整體來說，譜聚類在混合屬性數據的相似性度量中，涉及到不同屬性的疊加，由于在數量級上的顯著差異，屬性相似度直接疊加，會導致相似性偏斜.同時，尺度參數是描述樣本特征的重要依據，可以根據樣本自身的近鄰信息計算得到，對相似度矩陣的構建至關重要，在聚類時將直接影響聚類結果的準確性和可靠性.因此，本文基于信息熵定義一種平衡差異因子，從而修正分類型屬性相似度的度量；并引入自然最近鄰算法利用共享最近鄰計算樣本的鄰域半徑從而得到尺度參數，實現自適應譜聚類.

本文主要貢獻如下：

（1）首先，引人信息熵改進分類屬性相似度的度量，定義平衡差異因子，避免了分類屬性和數值屬性偏斜的問題.

（2）其次，針對譜聚類使用高斯核函數度量數值屬性相似度中尺度參數的人為選擇問題，引入自然鄰居算法，得到樣本的共享鄰域半徑從而自適應選擇尺度參數，避免了人為參數選擇導致的誤差，實現了參數的自適應設置.

（3）最后，提出了處理混合屬性數據集的自適 應譜聚類算法IEMN-SC（ImprovedInformation Entropy and Mahalanobis Natural neighbors

SpectralClustering），并在多個UCI機器學習數據庫中的數據集上進行實驗，將聚類結果與現有文獻中的算法進行對比，驗證所提算法的有效性、優越性.

1算法模型

譜聚類算法將原始數據 X={x₁，x₂，…，x_n} 的聚類問題轉化為圖最優劃分的問題.本文采用全連接法構造譜聚類矩陣，待聚類樣本間的相似性矩陣 S=（S_ij），i，j=1，…，n ，又稱為親和矩陣，是無向圖的鄰接矩陣， S_ij 是兩個樣本之間的相似度，通常采用高斯核函數進行度量，定義為：

式（1）中： x_i 為第 i 個樣本， x_j 為第 j 個樣本，σ 為尺度參數.

傳統的譜聚類的計算過程為：

（1）構造圖 G 的相似度矩陣 S ，對于給定的尺度參數 σ?S 由式（1）構造.

（2）計算對角矩陣度矩陣 D ， ：

（3）計算歸一化的對稱正則化拉普拉斯矩陣 L_sym

（4）對 L_sym 進行特征分解，得到前 k 個特征向量，構造特征向量矩陣 F ：

（5）利用傳統的聚類算法如Kmeans算法，對矩陣 F 進行聚類.

傳統的譜聚類算法在進行數據聚類時，屬性數據的相似度度量至關重要.針對混合屬性數據聚類時屬性維度偏斜問題，引入平衡差異因子改進分類屬性相似度；針對尺度參數 σ 的人為選擇容易造成算法運行結果不穩定，引入共享自然鄰居算法，最終提出自適應IEMN-SC算法，算法模型如圖1所示.

IEMN-SC算法在生成分類屬性相似度矩陣時，為了避免不同屬性類型數據分布不均衡造成的累積誤差，通過均衡各屬性類型的信息熵，并考慮各屬性維度之間的不同重要性，以緩解相似性度量疊加造成的傾向.首先分別計算分類屬性和數值屬性的信息熵總和，從而得到平衡差異因子 ω ，修正簡單匹配公式，最后計算得到分類型屬性數據的相似度矩陣 S^′ ．在計算數值屬性相似度矩陣時，自然最近鄰算法計算樣本的自然最近鄰，得到樣本之間的共享最近鄰，然后計算每個樣本的鄰域半徑，根據共享鄰域半徑計算得到尺度參數 σ ，最終得到數值屬性相似度矩陣 S^' ．根據得到的分類屬性相似度矩陣和數值屬性相似度矩陣，定義控制因子γ計算混合屬性相似度矩陣.最后，計算度矩陣 D 和拉普拉斯矩陣 L_sym ，利用傳統的本征間隙法確定L_sym 的特征向量個數，構造特征向量向量矩陣 F ，對正則化后的 F 進行Kmeans聚類得到最終聚類結果.

圖1 IEMN-SC算法模型圖

2數據的相似性度量方法

設輸人的數據空間為 D ，其中有 n 個混合型屬性數據對象的樣本集.對于每一個數據 x ，都有M=（M +M））個屬性 A，A，…，AM，A+1，（204號 …，A_Ms+Mt^（t） ．在數據集中以 A₁^（s），A₂^（s），…，A_Ms^（s） 代表M_s 個分類型屬性， A_Ms+1^（t），A_Ms+2^（t），…，A_Ms+Mt^（t） 代表 M_t 個數值型屬性. x_i^（s） 代表數據 x 的第 i 個分類屬性； x_i^（t） 代表數據 x 的第 i 個數值屬性.與傳統的相似度測量方式不同，本文構建一個關于混合型屬性數據的相似性度量矩陣，該矩陣需要融合分類型數據的相似度矩陣和數值型數據的相似度矩陣.

2.1分類型屬性的相似性

對于 D 中任意的數據 x 和 y ，本文定義的分類型屬性的相似度量為 S^′（x，y） ，具體表示如下：

式 （3）～（5） 中： W_i^（s） 為分類屬性 A_i^（s） 的權重，δ^'（x_i^（s），y_i^（s）） ）為數據 x 和 y 在相同分類屬性上對應位置元素相同與否的結果， H（A_i^（s） ）為分類屬性A_i^（s） 信息熵， i=1，2，…，M_s ， ）為分類屬性的信息熵總和.

根據式（5）描述，當兩個樣本在相同的分類屬性上取值相同時， δ^′（x_i^（s），y_i^（s））=1 ；取值不同時，δ^'（x_i^（s），y_i^（s））=ω?α 為本文設計的平衡差異因子，具體表達式為：

式（6）中： H_s 為分類屬性信息熵總和， H_t 為數值屬性信息熵總和.平衡差異因子 ω 的設計，克服了當兩個樣本在同一個屬性上取值不同時，不管該屬性的權重 W_i^（s） 多么大，始終導致在該屬性上相似度為。的情況出現，符合實際意義.

對于分類屬性 A_i^（s） ，其所有取值情況為Dom （A_i^（s））={a_i，1^（s），a_i，2^（s），…，a_i，r^（s）} ，分類屬性 A_i^（s） 的信息熵定義為：

H（A_i^（s））=

式（7）、（8）中： P（a_i，j^（s） ）為分類屬性 A_i^（s） 取值為a_i，j^（s） 的概率， n_i^（s） 為在分類屬性 A_i^（s） 上取值為 a_i，j^（s） 的數據的總個數.

對于數值屬性 A_i^（t） ，所有取值為Dom （A_i^（t））= {b_i，1^（t），b_i，2^（t），…，b_i，q^（t）} ，其信息熵為：

H（A_i^（t））=

式（9）、（10）中： P（b_i，j^（t） ）為數值屬性 A_i^（t） 取值為 b_i，j^（t） 的概率， n_i^（t） 為數值屬性 A_i^（t） 上取值為 b_i，j^（t） 的數據總個數.則分類屬性信息熵的總和 H_s 和數值屬性信息熵的總和 H_t 分別為：

2.2數值型屬性的相似性

在計算數值屬性數據的相似矩陣之前，對數值屬性數據進行最大最小標準化，以避免特征量綱帶來的影響，標準化公式為：

式（13）中： min（x_：，j） 表示第 j 維特征的最小值， max（x_：，j） 表示第 j 維的最大值，數據的每個值都被放縮到了[0，1]之間.

自然鄰居算法是一種新的最近鄰分析方法，不同于K最近鄰算法中參數K需人為選取，自然鄰居算法通過自適應搜索構建鄰居關系樹來解決參數選擇的挑戰.自然鄰居算法自適應地搜索鄰居，導致密集區域中的數據點具有更多的自然鄰居，稀疏區域中的數據點幾乎沒有自然鄰居.利用自適應搜索，每個數據點具有唯一數量的鄰居，一旦所有數據點都識別出其自然鄰居，鄰居關系就穩定下來，搜索結束.

首先根據數值屬性 l_Ms+1^（t），A_Ms+2^（t），…，A_Ms+Mt^（t） 的取值，搜索得到每個數據的自然鄰居以及數據之間的共享自然鄰居.數據 x 和 y 搜索得到的自然鄰居集表示為 N（x），N（y） ，則共享近鄰表示為：

SNN（x，y）=N（x）?N（y）

共享近鄰的個數為：

?=|N（x）?N（y）|

對于數據 x∈D ，其鄰域半徑定義為：

則數據 x 的尺度參數定義為：

本文定義的任意兩個數據 x，y∈D 之間的數

值型屬性的相似度量為：

式（18）中： d（x，y） 為數據 x 和 y 的歐式距離， σ_i 為數據 x 的尺度參數， σ_j 為數據 y 的尺度參數， p 為數據 x 和 y 的共享自然鄰居的個數.

2.3混合型屬性的相似度矩陣的生成

文獻[17在構建混合屬性相似度矩陣時，考慮到分類數據屬性個數與數值型數據屬性個數不同，定義了γ作為分類屬性數據相似度的一個控制因子，對分類屬性數據相似度進行了一定程度的放縮，避免直接將這兩種類型數據的相似性矩陣進行相加造成的不合理.同時，本文中的尺度參數 σ 與樣本數據有關，不是固定的一個值，所以本文引入一簇γ作為分類型數據相似度的控制因子，數據 x 和 y 的控制因子定義為：

式（19）中： max（S^'） 表示生成的數值型數據相似度矩陣全部元素中的最大值， min（S^′） 表示生成的分類型數據相似度矩陣全部元素中的最小值，二者之差代表兩種形式計算相似性度量的最大差異，作為分子，兩者差異越大，則參數值越小，分類型數據未使用高斯核函數所帶來的影響越小.并且在運算實驗過程中發現，數值型相似矩陣全局最大值與分類型數據相似矩陣全局最小值之差略優于數值型相似矩陣全局最小值與分類型數據相似矩陣全局最大值之差. σ_i 和 σ_j 的取值與在計算數值屬性相似度中尺度參數取值相同.γ用來削弱分類型數據相似度計算時沒有使用高斯核函數帶來的影響，本文定義的混合屬性數據 x 和 y 之間的混合屬性相似性度量 S（x，y） 為：

S（x，y）=

得到混合屬性數據相似度后，采用全連接方式構造圖.然后生成度矩陣 D ，計算拉普拉斯矩陣L_sym ，最后利用Kmeans算法進行聚類得到最終結果.

2.4計算復雜度分析

對于樣本規模為 n ，聚類簇數為 k 的數據集，IEMN-SC算法的時間復雜度由六部分組成：

（1）構建分類型數據的相似度矩陣 S^′ ，時間復雜度為 O（n（n-1）/2） ·

（2）構建數值型數據的相似度矩陣 S^' ，時間復雜度為 O（n×N） ， N 為搜索得到的自然最近鄰個數， N 遠遠小于 n ·

（3）計算度矩陣 D ，時間復雜度為 O（n） ：

（4）計算拉普拉斯矩陣 L_sym ，時間復雜度為O（n²） ：

（5）構造特征向量矩陣 F ，時間復雜度為O（nk） ：

（6）Kmeans聚類算法的時間復雜度為O（nkid）， i 是迭代次數， d 是數據維度.

綜上，IEMN-SC算法的時間復雜度為 O（n²） ：

3實驗結果與分析

為驗證本文算法IEMN-SC的聚類有效性，在5個真實數據集上進行實驗，將實驗結果與Kprototype[18] DPC_-M^[18] 、AMDPC[18]和 IJM-SC^[17] 進行對比.

表1給出了實驗所使用的5個數據集的詳細描述，都來源于UCI機器學習數據庫.

表1數據集描述

數據處理，首先刪除含有缺失值的樣本.A-cute數據集含有1個數值屬性和5個分類屬性來確定每個患者是否患有膀胱炎和腎炎，有兩個類別標簽來表示這兩種疾病，實驗中使用第一種來預測膀胱炎；Cleveland數據集將原始類標簽中的 1～4 視為一個類標簽；Adult數據集刪除含有缺失值的樣本之后從剩余的30162個實例中隨機抽取3000個實例.

實驗中使用的評價指標為：準確率（Accuracy，ACC）、調整蘭德指數（AdjustedRandIndex，ARI）和歸一化互信息（NormalizedMutualInforma-tion，NMI．ACC值和NMI值的取值范圍為[0，1，ARI值的取值范圍為 [-1，1] ，所有指標值都是值越大表示聚類結果越接近真實情況.通過綜合使用這些評價指標來驗證算法聚類性能的好壞.

根據文獻［18]，Kprototypes算法的參數取值為 γ=1/2σ （ σ 為數值屬性的平均標準差）， DPC_-

M算法中百分比參數 ，AMDPC算法近鄰個數參數 k 取值為樣本數量的十分之一.因為Kmeans算法不穩定性會影響實驗的結果，為此，重復運行算法2O次得到平均ACC值、ARI值和NMI值.表 2～6 給出5種算法在5個數據集上各項指標的實驗結果.在Acute數據集上， DPC_-M 算法由于聚類中心選擇不同產生兩個效果差異較大的聚類結果，說明該算法對初始聚類中心敏感，穩定性較差.

表2算法在Acute數據集上指標值

表3算法在Heart數據集上指標值

表4算法在Cleveland數據集上指標值

表5算法在Creditapproval數據集上指標值

表6算法在Adult數據集上指標值

表 2～6 揭示，在Acute數據集上，IEMN-SC算法在ACC值、ARI值上達到了最優值，在NMI指標上達到了次優值；在Heart數據集和Cleve-land數據集上，IEMN-SC算法聚類效果顯著，在3個指標上均取得了最優值；在Credit approval數據集上，IEMN-SC算法的ACC值比最優值低0.0092，ARI值比最優值低O.0241，NMI值比最優值低0.0191，但是IEMN-SC算法無需參數選擇，算法運行效率更高；在Adult數據集上，IEMN-SC算法在ACC值上取得了最優值.

表7給出了IEMN-SC算法在數據集上的運行時間.表7揭示，本文的IEMN-SC算法在處理大規模數據集時運行時間較長，分析原因是：使用譜聚類算法進行聚類的過程中，需要計算樣本間相似度矩陣，隨著數據量的增多，生成的相似性矩陣的維數增多，矩陣之間的運算時間更長.

表7算法運行時間

總體來看，IEMN-SC算法有很好的聚類性能.IEMN-SC算法基于信息熵改進分類屬性相似性度量，有效避免屬性疊加造成的屬性偏斜問題，聚類效果顯著提高；基于自然最近鄰算法自適應參數選擇讓算法運行更穩定，本文提出的聚類算法是可行有效的.

4結論

（1）本文提出的IEMN-SC算法基于信息熵改進傳統簡單匹配方法，用于計算分類屬性相似度，有效避免了混合屬性數據相似度計算中可能存在的屬性偏斜問題；通過引入共享自然鄰的個數動態計算尺度參數，自適應優化高斯核函數，從而在構建相似度矩陣時避免了人為選擇參數導致的誤差，顯著提升了算法的穩定性和魯棒性

（2）基于UCI真實數據集實驗表明，本文提出的IEMN-SC算法在ACC值、ARI值和NMI值指標上普遍優于現有算法.聚類結果更加接近數據的真實劃分，IEMN-SC算法對初始聚類中心和參數設置的敏感性顯著降低，表現出更好的分類效果和結果穩定性，進一步驗證了所提算法的有效性和實用性.

（3）本文的研究為混合屬性數據的聚類問題提供了一種新的解決思路.未來的研究可進一步優化，探索基于混合屬性數據相似度計算后的樣本分配策略，以提升聚類的精確性和效率.

參考文獻

[1]HanJW，KamberM，Pei J.Data mining：Conceptsand tech niques[M].3 rd. San Francisco：Morgan Kaufmann，2012.

[2]MacqueenJB. Some methods for classification and analysisof multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statisticsand Probability. Berkeley：University of California Press， 1967：281-297.

[3]KaufmanL，RousseeuwPJ.Finding groups in data：An introduction to cluster analysis[M].New York，USA：John Wileyamp;Sons，1990.

[4]張憲超.數據聚類[M].北京：科學出版社，2017.

[5]Liu T，Zhu J T，Zhou JK，et al.Initialization-similarity clusteringalgorithm[J].Multimedia Tools and Applications，2019，78（12）：33 279-33296.

[6]Mizutani T. Convex programming based spectral clustering[J].Machine Learning，2021，110（5）：993-964.

[7] Wen G Q，Zhu Y H，Chen L J，et al. One-step spectral rotation clusteringwith balanced constrains[J].World Wide Web，2022，25（1）：259-280.

[8]謝娟英，丁麗娟.完全自適應的譜聚類算法[J].電子學報， 2019，47（5）：1 000-1 008.

[9]David G，Averbuch A.Spectral CAT：Categorical spectral clustering of numerical and nominal data[J].Pattern Recognition，2011，45（1）：416-433.

[10] Wei M，Chow T W S，Chan R H M. Clustering heterogeneous data with K Means by mutual information-based unsupervised feature transformation[J].Entropy，2015， 17（3）：1 535-1 548.

[11]Huang Z X. Extensions to the KMeans algorithm for clustering large data sets with categorical values[J].Data Mining and Knowledge Discovery，1998，2（9） ：283-304.

[12]Mcparland D，GormleyIC.Model based clusteringfor mixed data：ClustMD[J].Advances in Data Analysis and Classification，2016，10（2）：155-169.

[13]Chu K X，Zhang M，Xun Y L，et al.A hybrid similarity measure-based clustering approach for mixed attribute data[J].International Journal of Machine Learning and Cybernetics，2024，15（4）：1 295-1 311.

[14]Rezaei H，Daneshpour N.Mixed data clustering based on a number of similar features[J].Pattern Recognition， 2023，143：109815.

[15]Mbuga F，Tortora C.Spectral clustering of mixed-type data[J].Stats，2022，5（1）：1-11.

[16]李順勇，許曉麗.基于信息熵加權的多視圖子空間聚類算 法[J].陜西科技大學學報，2023，41（2）：207-214.

[17]陳曉曼，陳玉，蘇歡.面向混合型屬性數據的改進譜 聚類算法[J].陜西師范大學學報（自然科學版），2025，53 （1）：71-80.

[18]Liu S H.Adaptive mixed-attribute data clustering methodbased on density peaks[J]. Complexity，2022， 2 022：6 742120.

[19]郭笑雨，劉金金，陳亞軍，等.基于鄰域標準差的密度調整 譜聚類算法[J].工程科學與技術，2025，57（2）：40-53.

【責任編輯：陳 佳】