范桂明 張桂珠

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院 江蘇 無(wú)錫 214122)

?

自動(dòng)屬性加權(quán)的K-調(diào)和均值聚類(lèi)算法

范桂明 張桂珠

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院 江蘇 無(wú)錫 214122)

針對(duì)K-調(diào)和均值算法中距離度量將所有屬性視為相等重要而存在的不足，提出一種利用自動(dòng)屬性加權(quán)的改進(jìn)聚類(lèi)算法。在算法的目標(biāo)函數(shù)中，用加權(quán)歐氏距離替代傳統(tǒng)的歐氏距離，并證明了使得算法能夠收斂的屬性權(quán)重更新機(jī)制。為進(jìn)一步提高聚類(lèi)性能，將粒子群算法融入到改進(jìn)的屬性加權(quán)聚類(lèi)算法中以抑制其陷于局部最優(yōu)，其中采用聚類(lèi)中心和屬性權(quán)重的值同時(shí)表示粒子的位置進(jìn)行尋優(yōu)。在UCI數(shù)據(jù)集的測(cè)試結(jié)果表明，該算法的聚類(lèi)指標(biāo)平均提高了約9個(gè)百分點(diǎn)，具有更高的聚類(lèi)準(zhǔn)確性和穩(wěn)定性。

K-調(diào)和均值 聚類(lèi) 屬性加權(quán) 粒子群

0 引 言

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

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

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

1 算法基本原理

1.1 K-調(diào)和均值聚類(lèi)及其改進(jìn)算法

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

(1)

這里采用歐氏距離計(jì)算數(shù)據(jù)xi到聚類(lèi)中心的cj的距離，即dij=‖xi-cj‖，p是一個(gè)輸入?yún)?shù)，對(duì)算法的性能具有重要的影響，研究發(fā)現(xiàn)當(dāng)p≥2時(shí)聚類(lèi)的效果比較好[1]。聚類(lèi)過(guò)程通過(guò)迭代使得目標(biāo)函數(shù)值不斷減小并保持穩(wěn)定，直至結(jié)束運(yùn)行。每次迭代中，各個(gè)聚類(lèi)簇的中心點(diǎn)cj(j=1,2,…,k)的更新如下所示：

(2)

(3)

(4)

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

X11X12…X1d…Xk1Xk2…Xkm

圖1 PSOKHM中一個(gè)粒子的表達(dá)

PSOKHM的具體過(guò)程如下所示[2]：

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

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

3) 執(zhí)行PSO算法進(jìn)行搜索，迭代運(yùn)行Gen2次后輸出當(dāng)前最優(yōu)解，進(jìn)入下一步操作。

4) 以當(dāng)前最優(yōu)粒子的位置作為聚類(lèi)中心執(zhí)行KHM算法，迭代運(yùn)行Gen3次，獲得新的聚類(lèi)中心作為粒子的位置。

5) Gen1=Gen1+1，若Gen1

其中，文獻(xiàn)[2]給出步驟2和步驟3中迭代次數(shù)Gen2和Gen3的取值分別分別為8和4，且文獻(xiàn)[8]的KHM-MPSO中采用了同樣的取值。然而，原文中均未給出確定這些迭代數(shù)的細(xì)節(jié)，可認(rèn)為其為作者結(jié)合實(shí)驗(yàn)選用的值，能夠滿(mǎn)足絕大多數(shù)情況。

1.2 自動(dòng)加權(quán)K均值

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

(5)

每次迭代過(guò)程中，屬性權(quán)重的更新如下所示：

(6)

2 自動(dòng)屬性加權(quán)的K-調(diào)和均值聚類(lèi)

2.1 屬性加權(quán)K-調(diào)和均值算法

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

(7)

由于聚類(lèi)過(guò)程是通過(guò)最小化目標(biāo)函數(shù)進(jìn)行，可將WKHM視為一種優(yōu)化問(wèn)題，即為：

(8)

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

(9)

其中λ為拉格朗日系數(shù)。

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

(10)

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

(11)

(12)

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

(13)

綜上可得，WKHM聚類(lèi)算法的具體流程為：

Step1 初始化算法的基本參數(shù)，隨機(jī)選取樣本點(diǎn)并作較小的擾動(dòng)作為初始的聚類(lèi)中心。

Step2 根據(jù)式(8)計(jì)算目標(biāo)函數(shù)的值。

Step4 根據(jù)式(2)計(jì)算新的聚類(lèi)中心。

Step5 根據(jù)式(13)計(jì)算新的屬性權(quán)重。

Step6 若達(dá)到最大迭代次數(shù)或者目標(biāo)函數(shù)不發(fā)生明顯變化則停止；否則，轉(zhuǎn)Step2繼續(xù)迭代運(yùn)行。

2.2 融合粒子群算法的屬性加權(quán)K-調(diào)和均值聚類(lèi)

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

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)以及評(píng)估標(biāo)準(zhǔn)

為了驗(yàn)證本文算法的有效性和可行性，選取了UCI數(shù)據(jù)庫(kù)中比較常用的6個(gè)數(shù)據(jù)集對(duì)各算法的聚類(lèi)性能進(jìn)行測(cè)試，它們的具體特性如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集的特性

本文中通過(guò)兩個(gè)常用的度量指標(biāo)RI(rand index)和NMI(normalized mutual information)對(duì)聚類(lèi)結(jié)果進(jìn)行評(píng)估和比較分析。假定數(shù)據(jù)集真實(shí)的聚類(lèi)為T(mén)，算法獲得的聚類(lèi)結(jié)果為C。令a、b、c、d分別表示同時(shí)屬于T和C的相同類(lèi)，屬于T的相同類(lèi)但是屬于C的不同類(lèi)，屬于C的相同類(lèi)但是屬于T的不同類(lèi)，以及同時(shí)屬于T和C的不同類(lèi)的數(shù)據(jù)的個(gè)數(shù)。則RI的計(jì)算公式如下所示：

(14)

NMI指標(biāo)采用信息論中的熵計(jì)算每個(gè)真實(shí)的類(lèi)與每個(gè)聚類(lèi)結(jié)果的簇之間的平均互信息，若ni為類(lèi)i中數(shù)據(jù)點(diǎn)的個(gè)數(shù)，nj為簇j中數(shù)據(jù)點(diǎn)的個(gè)數(shù)，nij為同時(shí)在類(lèi)i和簇j中的數(shù)據(jù)點(diǎn)得個(gè)數(shù)，則NMI的計(jì)算公式為：

(15)

它們的值均在0到1之間，且越大則表明聚類(lèi)結(jié)果越好。此外，由于距離度量中屬性加權(quán)的作用，WKHM目標(biāo)函數(shù)的值相比KHM小很多，這里不對(duì)其進(jìn)行比較。

3.2 實(shí)驗(yàn)結(jié)果與分析

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

表2 p=2.5時(shí)的實(shí)驗(yàn)結(jié)果對(duì)比

表3 p=3.0時(shí)的實(shí)驗(yàn)結(jié)果對(duì)比

續(xù)表3

表4 p=3.5時(shí)的實(shí)驗(yàn)結(jié)果對(duì)比

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

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

圖2 本文兩種算法對(duì)各數(shù)據(jù)集的RI值

表5 PSOWKHM中設(shè)定閾值后對(duì)Satellite的實(shí)驗(yàn)結(jié)果

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

4 結(jié) 語(yǔ)

由于KHM算法在聚類(lèi)過(guò)程中將所有權(quán)重的作用視為相等而具有一定的局限性，本文利用屬性加權(quán)歐氏距離提出一種改進(jìn)的WKHM算法，且在聚類(lèi)過(guò)程中自動(dòng)更新屬性權(quán)重。并且，為了進(jìn)一步提高算法的聚類(lèi)性能，將其與PSO相結(jié)合獲得新的混合聚類(lèi)算法。實(shí)驗(yàn)結(jié)果有效驗(yàn)證了改進(jìn)算法的可行性，對(duì)各數(shù)據(jù)集的性能均具有較為明顯的改善?？紤]到不同屬性對(duì)不同類(lèi)的聚類(lèi)作用也存在差異，而若將向量加權(quán)歐氏距離改為矩陣加權(quán)歐氏距離則會(huì)增加算法推導(dǎo)的復(fù)雜性，后續(xù)將繼續(xù)研究將軟子空間的原理引入到KHM中，以期進(jìn)一步提升算法的性能。

[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 的譜聚類(lèi)算法 [J].智能系統(tǒng)學(xué)報(bào),2009,4(2):95-99.

[10] 劉娜,肖智博,魯明羽.基于模糊 K-調(diào)和均值的單詞-文檔譜聚類(lèi)方法 [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] 李仁侃,葉東毅.屬性賦權(quán)的 K-Modes 算法優(yōu)化 [J].計(jì)算機(jī)科學(xué)與探索,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。江蘇省自然科學(xué)基金項(xiàng)目(BK20140165)。范桂明，碩士生，主研領(lǐng)域：數(shù)據(jù)挖掘。張桂珠，副教授。

TP301.6

A

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