自動屬性加權的K-調和均值聚類算法

范桂明 張桂珠

(江南大學物聯網工程學院 江蘇 無錫 214122)

?

自動屬性加權的K-調和均值聚類算法

范桂明 張桂珠

(江南大學物聯網工程學院 江蘇 無錫 214122)

針對K-調和均值算法中距離度量將所有屬性視為相等重要而存在的不足，提出一種利用自動屬性加權的改進聚類算法。在算法的目標函數中，用加權歐氏距離替代傳統的歐氏距離，并證明了使得算法能夠收斂的屬性權重更新機制。為進一步提高聚類性能，將粒子群算法融入到改進的屬性加權聚類算法中以抑制其陷于局部最優，其中采用聚類中心和屬性權重的值同時表示粒子的位置進行尋優。在UCI數據集的測試結果表明，該算法的聚類指標平均提高了約9個百分點，具有更高的聚類準確性和穩定性。

K-調和均值 聚類 屬性加權 粒子群

0 引 言

聚類分析是一種廣泛使用的數據分析方法，一直被應用于多個領域，特別是在機器學習、數據挖掘、模式識別、圖像處理等領域應用十分廣泛。在所有的聚類分析算法中，K-means是最經典且使用最為廣泛的一種算法，它是基于劃分的原理，且算法過程簡單快捷，容易實現。但是K-means算法也有兩個主要的缺陷，對初始聚類中心的敏感以及容易陷入局部最優解。因此，針對上述缺陷很多文獻不斷提出改進方法，由Zhang[1]提出的K-調和均值KHM(K-harmonic means)算法能夠有效解決對初始值敏感的問題。

由于KHM與K-均值仍然具有陷入局部最優的問題，一些啟發式進化算法被用于與其組合而獲得新的混合算法，以充分利用其全局搜索能力，現已成為對KHM的研究工作中最常用的方法。目前，融合粒子群算法PSO的PSOKHM[2]是較為經典的混合算法。隨后，結合蟻群優化算法[3]、變鄰域搜索算法[4]以及其改進版本[5]、候選組搜索算法[6]、帝國主義競爭算法[7]等相繼被提出，然而它們并未直接與PSOKHM進行對比，并依據相應的實驗結果可將它們看作為相近的研究工作。近來，由Bouyer等[8]提出一種結合改進PSO的混合算法KHM-MPSO能夠獲得比PSOKHM更準確且更具魯棒性的聚類結果，其中利用了布谷鳥搜索算法的levy飛行策略進一步提高全局搜索能力。然而，這些混合聚類算法結合啟發式算法進行搜索的策略均增加了時間復雜度，從而影響了計算效率，在這方面的改進值得進一步研究。此外，一些學者將模糊策略引入到KHM進行改進，使其具有軟劃分性能，如基于模糊KHM的譜聚類算法[9]以及其在單詞-文檔中的應用[10]。近來，Wu等[11]利用概率C均值的原理提出一種新穎的混合模糊K調和均值HFKHM(hybrid fuzzy K-harmonic means)聚類算法，能夠有效解決對噪聲敏感的問題。在上述的各種KHM算法中，均將數據的所有屬性看作相等的作用進行距離度量，具有一定的局限性。由Huang等[12]提出一種自動變量加權型的W-k-means算法，它能夠在聚類過程中度量不同屬性的重要性，從而自動調整其權重使得更重要的屬性具有相對較大的權重值。目前，基于屬性加權的聚類算法已得到十分廣泛的關注，被用于對各種算法進行改進[13-17]，而尚未有關結合KHM的相關研究。

本文中首次將屬性權重引入到KHM算法的距離度量中提出一種加權K-調和均值聚類算法WKHM(weight K-harmonic means)，考慮不同屬性對聚類的影響，并且在算法迭代過程中自動更新其權重。此外，為了進行更全面的分析，將WKHM與PSO相結合獲得混合加權聚類算法PSOWKHM，并且與PSOKHM不同的是其將屬性權重與類中心坐標相結合來表示每個粒子群個體。實驗結果表明，本文算法能夠有效提高聚類精度，具有較高的穩定性。

1 算法基本原理

1.1 K-調和均值聚類及其改進算法

K-調和均值算法的原理基本上與K均值是相似的，不同的是其使用調和均值HM(harmonic means)代替算術均值來計算目標函數。由于HM具有最小化群體內的偏差以及最大化群體間的偏差的特性，因此KHM能夠有效克服對初始中心點敏感的問題。若數據集X=(x1,…，x2,…,xn),xi=(x1i,…,xqi)為空間Rq上的N個數據，將其劃分為k個聚類簇，且每個聚類的中心用cj表示。根據文獻，K-調和均值的目標函數為[1]：

(1)

這里采用歐氏距離計算數據xi到聚類中心的cj的距離，即dij=‖xi-cj‖，p是一個輸入參數，對算法的性能具有重要的影響，研究發現當p≥2時聚類的效果比較好[1]。聚類過程通過迭代使得目標函數值不斷減小并保持穩定，直至結束運行。每次迭代中，各個聚類簇的中心點cj(j=1,2,…,k)的更新如下所示：

(2)

(3)

(4)

在上文提到KHM具有易陷于局部最優的缺陷，因此融入群智能算法能夠有效改善其性能，考慮到相關的改進算法較為相近，這里僅介紹最具有代表性的PSOKHM。由于PSO是一種被廣泛研究的群智能優化算法，對于其具體原理本文不再詳細介紹，可參考文獻[2,8]了解。若k為聚類數，m為數據的維數，則一個粒子可表示為一個k×m列的一維實數向量，如圖1所示。并且，PSOKHM的適應度函數即為KHM的目標函數。

X11X12…X1d…Xk1Xk2…Xkm

圖1 PSOKHM中一個粒子的表達

PSOKHM的具體過程如下所示[2]：

1) 設置算法的基本參數，包括最大迭代次數IterCount，種群規模Psize，PSO的慣性權重因子w以及加速度因子c1和c2。

2) 初始化Psize個粒子的位置，并設置迭代次數Gen1=0。

3) 執行PSO算法進行搜索，迭代運行Gen2次后輸出當前最優解，進入下一步操作。

4) 以當前最優粒子的位置作為聚類中心執行KHM算法，迭代運行Gen3次，獲得新的聚類中心作為粒子的位置。

5) Gen1=Gen1+1，若Gen1

其中，文獻[2]給出步驟2和步驟3中迭代次數Gen2和Gen3的取值分別分別為8和4，且文獻[8]的KHM-MPSO中采用了同樣的取值。然而，原文中均未給出確定這些迭代數的細節，可認為其為作者結合實驗選用的值，能夠滿足絕大多數情況。

1.2 自動加權K均值

W-K-means算法是對K-means的拓展，將加權相異性度量引入到目標函數中，用wq(q=1,2,…,d)表示各維屬性權重并通過指數參數β進一步控制其重要性，改進的目標函數為[12]：

(5)

每次迭代過程中，屬性權重的更新如下所示：

(6)

2 自動屬性加權的K-調和均值聚類

2.1 屬性加權K-調和均值算法

根據式(5)可見，屬性權重引入了一個新的指數參數β，其對算法的性能具有比較重要的影響，對于不同數據集的最佳β值難以確定?？紤]到KHM的距離度量已具有指數參數p，本文算法中未直接采用W-K-means的屬性加權方式，而是采用加權歐氏距離dij(w)計算樣本與類中心的距離。各屬性權重同樣用wq(q=1,2,…,m)表示，則WKHM算法的目標函數如下式所示：

(7)

由于聚類過程是通過最小化目標函數進行，可將WKHM視為一種優化問題，即為：

(8)

式(8)可通過格朗日乘法求解，函數表達式L可以表示為：

(9)

其中λ為拉格朗日系數。

算法中包含聚類中心和屬性權重這兩個決策變量，需推導出它們的更新公式使得L始終能夠收斂到一個局部最小值。首先求出L關于類中心cj(j=1,2,…,K)的偏導并使其為0：

(10)

求出L關于wq(q=1,2,…,m)的偏導并使其為0，進而獲得關于屬性權重的計算式，如下所示：

(11)

(12)

結合式(12)以及式(8)中屬性權重的約束條件即可求出λ的計算式，然后再代入到式(12)中即可獲得屬性權重最終的更新公式為：

(13)

綜上可得，WKHM聚類算法的具體流程為：

Step1 初始化算法的基本參數，隨機選取樣本點并作較小的擾動作為初始的聚類中心。

Step2 根據式(8)計算目標函數的值。

Step4 根據式(2)計算新的聚類中心。

Step5 根據式(13)計算新的屬性權重。

Step6 若達到最大迭代次數或者目標函數不發生明顯變化則停止；否則，轉Step2繼續迭代運行。

2.2 融合粒子群算法的屬性加權K-調和均值聚類

上述聚類算法在迭代過程中的時間復雜度主要依賴于距離的計算，且dij和dij(w)的計算復雜度均為O(knm)，其中相應變量的含義均與上文相同。因此，KHM與WKHM的時間復雜度均為O(Gen3·knm)，即混合聚類算法步驟4的時間復雜度，步驟3的時間復雜度為O(Gen2·Psize·knm)，由于Gen3

3 實驗與分析

3.1 實驗數據以及評估標準

為了驗證本文算法的有效性和可行性，選取了UCI數據庫中比較常用的6個數據集對各算法的聚類性能進行測試，它們的具體特性如表1所示。

表1 實驗數據集的特性

本文中通過兩個常用的度量指標RI(rand index)和NMI(normalized mutual information)對聚類結果進行評估和比較分析。假定數據集真實的聚類為T，算法獲得的聚類結果為C。令a、b、c、d分別表示同時屬于T和C的相同類，屬于T的相同類但是屬于C的不同類，屬于C的相同類但是屬于T的不同類，以及同時屬于T和C的不同類的數據的個數。則RI的計算公式如下所示：

(14)

NMI指標采用信息論中的熵計算每個真實的類與每個聚類結果的簇之間的平均互信息，若ni為類i中數據點的個數，nj為簇j中數據點的個數，nij為同時在類i和簇j中的數據點得個數，則NMI的計算公式為：

(15)

它們的值均在0到1之間，且越大則表明聚類結果越好。此外，由于距離度量中屬性加權的作用，WKHM目標函數的值相比KHM小很多，這里不對其進行比較。

3.2 實驗結果與分析

為了分析算法的聚類性能，本文分別對KHM、WKHM、PSOKHM以及WPSOKHM進行對比分析。實驗通過MATLAB2010b編程運行，計算機的硬件配置為：Intel Core P7450、CPU 2.13 GHz、2 GB RAM。各算法的參數設置為：KHM和WKHM的最大迭代次數Maxgen=100；PSOKHM的參數采用文獻[3]中的Psize=18，w=0.7298，c1=c2=1.496，總迭代次數IterCount=5，且Gen1=8，需要注意文獻[2]中數據集的復雜度相對較低，Gen2=4已無法滿足求解要求，因此本文中為Gen2=10。分別取p=2.5、3、3.5時對聚類結果進行比較，每種算法獨立運行20次，計算RI、NMI和運行時間的平均值，且為了進一步分析算法的穩定性，計算出RI和NMI的標準差記錄至括號內，實驗結果分別為表2至表4中所示。

表2 p=2.5時的實驗結果對比

表3 p=3.0時的實驗結果對比

續表3

表4 p=3.5時的實驗結果對比

首先，根據表2至表4可以看出，在大多數情況下WKHM算法相對于KHM具有明顯的提升，驗證了采用加權歐氏距離對算法進行改進的可行性。盡管NMI指標的趨勢與RI指標基本一致，但仍存在少數不一致的情況，比如在表3中PSOWKHM的RI值高于KHM，NMI值低于KHM，這表明采用多個指標進行對比分析的必要性。為進一步分析，以p=2.5時為例，根據表2中各算法的RI指標可見，WKHM算法對6種數據集分別提升了6.93%、4.06%、9.83%、26.88%、4.24%、2.67%。而PSOKHM算法對數據集Iris、Ionosphere、Australian的RI值均與KHM相同且標準差為0；對數據集WDBC的RI值取得了微弱的提升；僅對于數據集Vehicle和Satellite的RI值獲得了相對較明顯的提升，分別比KHM提高了1.79%、1.70%，但仍低于WKHM算法的改善效果。因此，可以看出現有的相關文獻主要關注于將智能優化算法融入KHM中以克服局部最優的問題而忽略了對算法原理的進一步改進，具有一定的局限性，無法獲得更好的聚類性能。并且，本文中同樣將PSO融入WKHM算法中，以同時利用了屬性權重的改進和智能算法全局搜索的優勢。其中，對于數據集Iris、Ionosphere和Vehicle，PSOWKHM的RI值相對于WKHM沒有明顯變化，而對于數據集WDBC、Australian和Satellite提高了1.93%、3.58%、1.18%，可見算法性能得到了進一步的提高。此外，值得注意的是表2中除數據集Satellite，KHM算法對其他數據的聚類指標值的標準差均為0，有效驗證了其對初始聚類中心不敏感。由于KHM算法中p(通常p≥2)的選取對其性能具有一定的影響，本文中分別選取大多數文獻中采用的2.5、3.0和3.5進行分析?？梢?，KHM對于數據集Iris、Ionosphere和Australian而言，p的選取對算法的性能的影響不是很明顯，而對于數據集WDBC、Vehicle和Satellite則相對較為明顯。WKHM同樣存在對參數p敏感的問題，在某種程度上可能更明顯，比如WKHM對于WDBC和Vehicle在2.5和p=3.0時的性能均優于KHM，而在3.5時比后者更差。為了更直觀分析，圖2給出WKHM以及PSOWKHM取不同p值時對各數據集的RI指標值，其中橫坐標的1～6分別表示數據集Iris、Ionosphere、WDBC、Australian、Vehicle、Satallite。由圖中可見，WKHM和PSOWKHM在p=2.5和p=3.0時對各數據集的性能均較為接近，而在p=3.5時對一些數據集出現了明顯的下降。此外，圖2中(a)顯示WKHM對于Vehicle在p=3.5出現驟降，而(b)顯示PSOWKHM對于Vehicle在p=3.5并沒有明顯下降，表明融入PSO后有效抑制了陷入局部最優的問題。綜合分析，本文取p值在[2,3]內可使得改進算法對各數據集能獲得比較滿意的結果，并且由(b)中可見PSOWKHM在p=2.5時相對于p=3.0時具有較小程度的優勢。

由表2-表4中各算法的平均運行時間可見，WKHM較KHM的時間有較小的增加，這是由于增加了屬性權重的計算過程，其中WKHM對Satellite的運行時間更短是由于其提前終止使總迭代次數更小。兩種混合聚類算法較原算法的平均運行時間均具有較大的增加，特別是對樣本數較大的Satellite數據集的運行時間比較長，這是由于PSO執行全局搜索需要較大的時間開銷。然而，在步驟2中若PSO始終執行Gen2次迭代可能會增加不必要的計算開銷，因此這里采用一個較小的閾值ε=10^(-4)判斷是否終止。在PSO優化過程中，計算第t次迭代最優解的適應度值fbest(t)與前一次迭代最優解的適應度值fbest(t-1)的差值，當滿足fbest(t)-fbest(t-1)<ε時停止PSO迭代，輸出當前最優解并繼續執行步驟3。這里以較大的數據集Satellite進行分析，采用閾值ε判斷終止的實驗結果如表5所示?？梢姡O定閾值后PSOWKHM對Satellite的性能并沒有下降，而運行時間減少了很多，從而有效提高了算法的運行效率。

圖2 本文兩種算法對各數據集的RI值

表5 PSOWKHM中設定閾值后對Satellite的實驗結果

盡管如此，融入PSO的混合聚類算法在時間性能方面仍處于劣勢，因此對于WKHM和PSOWKHM可根據具體問題進行選取?？紤]到WKHM較后者的聚類性能并沒有較明顯的降低而在時間效率方面具有明顯的優勢，一般情況下可優先采用，若對于聚類準確度要求較高時則可選用PSOWKHM，以降低算法陷入局部最優的可能性。

4 結 語

由于KHM算法在聚類過程中將所有權重的作用視為相等而具有一定的局限性，本文利用屬性加權歐氏距離提出一種改進的WKHM算法，且在聚類過程中自動更新屬性權重。并且，為了進一步提高算法的聚類性能，將其與PSO相結合獲得新的混合聚類算法。實驗結果有效驗證了改進算法的可行性，對各數據集的性能均具有較為明顯的改善。考慮到不同屬性對不同類的聚類作用也存在差異，而若將向量加權歐氏距離改為矩陣加權歐氏距離則會增加算法推導的復雜性，后續將繼續研究將軟子空間的原理引入到KHM中，以期進一步提升算法的性能。

[1] Zhang B.Generalized k-harmonic means[J].Hewlett-Packard Laboratoris Technical Report,2000.

[2] Yang F Q,Sun T E L,Zhang C H.An efficient hybrid data clustering method based on K-harmonic means and Particle Swarm Optimization [J].Expert Systems with Applications,2009,36(6):9847-9852.

[3] Jiang H,Yi S,Li J,et al.Ant clustering algorithm with K-harmonic means clustering [J].Expert Systems with Applications,2010,37(12):8679-8684.

[5] Carrizosa E,Alguwaizani A,Hansen P,et al.New heuristic for harmonic means clustering [J].Journal of Global Optimization,2014,1-17.

[6] Hung C H,Chiou H M,Yang W N.Candidate groups search for K-harmonic means data clustering [J].Applied Mathematical Modelling,2013,37(24):10123-10128.

[7] Abdeyazdan M.Data clustering based on hybrid K-harmonic means and modifier imperialist competitive algorithm [J].The Journal of Supercomputing,2014,68(2):574-598.

[8] Bouyer A,Farajzadeh N.An Optimized K-Harmonic Means Algorithm Combined with Modified Particle Swarm Optimization and Cuckoo Search Algorithm [J].Journal of Intelligent Systems,2015.

[9] 汪中,劉貴全,陳恩紅.基于模糊 K-harmonic means 的譜聚類算法 [J].智能系統學報,2009,4(2):95-99.

[10] 劉娜,肖智博,魯明羽.基于模糊 K-調和均值的單詞-文檔譜聚類方法 [J].控制與決策,2012,27(4):501-506.

[11] Wu X,Wu B,Sun J,et al.A hybrid fuzzy K-harmonic means clustering algorithm [J].Applied Mathematical Modelling,2015,39(12):3398-3409.

[12] Huang J Z,Ng M K,Rong H,et al.Automated variable weighting in k-means type clustering [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(5):657-668.

[13] Jing L,Ng M K,Huang J Z.An entropy weighting k-means algorithm for subspace clustering of high-dimensional sparse data [J].IEEE Transactions on Knowledge and Data Engineering,2007,19(8):1026-1041.

[14] 李仁侃,葉東毅.屬性賦權的 K-Modes 算法優化 [J].計算機科學與探索,2012,6(1):90-96.

[15] Ji J,Bai T,Zhou C,et al.An improved k-prototypes clustering algorithm for mixed numeric and categorical data [J].Neurocomputing,2013,120:590-596.

[16] Ferreira M R,de Carvalho F d A.Kernel-based hard clustering methods in the feature space with automatic variable weighting [J].Pattern Recognit,2014,47(9):3082-3095.

[17] Zhang L,Pedrycz W,Lu W,et al.An interval weighed fuzzy c-means clustering by genetically guided alternating optimization [J].Expert Systems with Applications,2014,41(13):5960-5971.

K-HARMONIC MEANS CLUSTERING BASED ON AUTOMATED FEATURE WEIGHTING

Fan Guiming Zhang Guizhu

(School of Internet of Things Engineering,Jiangnan University,Wuxi 214122,Jiangsu,China)

K-harmonic means algorithm has the disadvantage of viewing all features as the same importance in its distance metric.In light of this,we proposed an improved clustering algorithm which takes the advantage of automated feature weighting.In objective function of the algorithm,we replaced the conventional Euclidian distance with the weighted Euclidian distance,and proved the feature weight update mechanism which enables the algorithm to be converged.In order to further improve the clustering performance,we integrated the particle swarm optimisation into the feature weighting clustering algorithm so as to suppress its problem of being trapped into local optimum,in which we used both the centres of clusters and the value of feature weight to represent the position of each particle for optimisation.Tests result on UCI datasets showed that the clustering index of the proposed algorithm has raised about 9 percents,so our method is more accurate and stable.

K-harmonic means Clustering Feature weighting Particle swarm optimisation

2015-10-09。江蘇省自然科學基金項目(BK20140165)。范桂明，碩士生，主研領域：數據挖掘。張桂珠，副教授。

TP301.6

A

10.3969/j.issn.1000-386x.2016.11.055