羅軍鋒　洪丹丹

摘 ?要：針對(duì)K-means算法中對(duì)初始聚類中心和孤立點(diǎn)敏感的缺點(diǎn)，我們通過從密度和距離兩個(gè)方面的改進(jìn)，提出新的改進(jìn)K-means算法。該算法引入特征權(quán)重，從近鄰密度出發(fā)，去除孤立點(diǎn)對(duì)算法的影響，同時(shí)確定初始聚類中心，在距離計(jì)算過程中，引入集成簇內(nèi)與簇間距離的計(jì)算方法，以提升聚類的效果。實(shí)驗(yàn)結(jié)果表明，該算法比傳統(tǒng)聚類算法能夠提升10%以上的聚類效果。

關(guān)鍵詞：聚類;K-means;特征加權(quán);近鄰密度;孤立點(diǎn)

中圖分類號(hào)：TP311 ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

A K-means Clustering Algorithm based on Density and Distance

LUO Junfeng， HONG Dandan

（Network Information Center， Xi'an Jiaotong University， Xi'an 710049， China）

luojf@xjtu.edu.cn; ddhong@xjtu.edu.cn

Abstract： In order to improve the sensitivity of initial clustering centers and outliers of K-means algorithm， an improved K-means algorithm is proposed based on density and distance. In this algorithm， feature weight is introduced to remove the influence of outliers on the algorithm from the neighborhood density. At the same time， the initial clustering center is determined. In the process of distance calculation， the distance calculation method within and between clusters is introduced to improve the clustering effect. The experimental results show that this algorithm improves the clustering effect by more than 10%， compared with the traditional clustering algorithm.

Keywords： clustering; K-means; feature weighting; neighbor density; isolated points

1 ? 引言（Introduction）

K-means[1]算法是數(shù)據(jù)挖掘算法中一種流行的、簡(jiǎn)單的、實(shí)用的聚類算法，其特點(diǎn)就是思想原理簡(jiǎn)單、聚類效果較佳。當(dāng)然，作為算法，傳統(tǒng)的K-means聚類算法存在著諸如初始聚類中心隨機(jī)選擇、K值需要事先確定、容易陷入局部最優(yōu)、對(duì)孤立點(diǎn)特別敏感等等缺點(diǎn)或者不足。

長期以來針對(duì)這些缺點(diǎn)或不足，許多科研人員提出了不同的改進(jìn)方法和策略，形成了較完善的聚類策略。文獻(xiàn)[2]用在初始聚類中心的選擇中，通過引入神經(jīng)網(wǎng)絡(luò)算法改進(jìn)算法，得到了很好的聚類效果;文獻(xiàn)[3]則引入了比較新穎的蟻群算法，將蟻群算法的核心思想和K-means算法的核心思想進(jìn)行融合，同樣也達(dá)到改進(jìn)聚類結(jié)果質(zhì)量這一目標(biāo)。文獻(xiàn)[4]首先對(duì)聚類對(duì)象進(jìn)行抽樣，利用抽樣后的數(shù)據(jù)樣本的分布來確定初始聚類中心。文獻(xiàn)[5]提出一種基于平均密度優(yōu)化初始聚類中心的算法。文獻(xiàn)[6]中提出的通過使用近似加權(quán)核函數(shù)優(yōu)化目標(biāo)函數(shù)。針對(duì)孤立點(diǎn)的處理一般都是利用聚類數(shù)據(jù)點(diǎn)與聚類核心的距離超過目標(biāo)函數(shù)的閾值從而定義為孤立點(diǎn)，文獻(xiàn)[7]則通過距離公式的不同定義來將孤立點(diǎn)數(shù)據(jù)剔除。文獻(xiàn)[8]則通過集成簇內(nèi)與簇間距離的加權(quán)算法來改進(jìn)算法的距離計(jì)算公式，以提升聚類的效果。

本文借鑒文獻(xiàn)[8]的距離計(jì)算方法，提出了一種基于密度和距離的K-means優(yōu)化算法，該算法首先計(jì)算數(shù)據(jù)對(duì)象的局部密度，以此為算法的出發(fā)點(diǎn)，首先去除孤立點(diǎn)以減少孤立點(diǎn)對(duì)算法結(jié)果的影響，再按照距離最遠(yuǎn)的原則來確定初始聚類中心，隨后引入集成簇內(nèi)與簇間距離的距離計(jì)算方法進(jìn)行聚類，著力提升K-means算法的性能，取得了不錯(cuò)的聚類效果。

2 ?傳統(tǒng)K-means算法（Traditional K-means algorithm）

傳統(tǒng)K-means算法的基本思想是：首先從數(shù)據(jù)對(duì)象集D中隨機(jī)選擇k個(gè)對(duì)象作為初始聚類中心;接著計(jì)算每個(gè)對(duì)象到這些初始聚類中心的距離，并根據(jù)最小距離原則進(jìn)行劃分，劃給聚類最近的簇;然后重新計(jì)算每個(gè)聚類簇的均值，直到計(jì)算收斂函數(shù)，滿足函數(shù)收斂的要求，算法就終止，否則，重復(fù)上述過程。

傳統(tǒng)算法中由于初始聚類中心是隨機(jī)任意選取的，根據(jù)選取的初始聚類中心的不同，容易陷入局部最優(yōu)，最為重要的是孤立點(diǎn)的存在，對(duì)平均值會(huì)產(chǎn)生很大的影響。本文因此為出發(fā)點(diǎn)，先著手解決如何選取初始聚類中心，消除鼓勵(lì)點(diǎn)，然后才根據(jù)新的距離公式進(jìn)行聚類。

3 ?基于密度和距離的K-means算法（K-means algorithm based on density and distance）

針對(duì)傳統(tǒng)K-means的缺點(diǎn)，本算法改進(jìn)包括：首先，引入近鄰密度，目的有兩個(gè)：其一，剔除聚類過程中的初始孤立點(diǎn)，因?yàn)楣铝Ⅻc(diǎn)對(duì)聚類的結(jié)果影響很大;其二，是用近鄰密度選擇高密度對(duì)象，并從中選擇初始聚類中心，以解決傳統(tǒng)K-means算法初始聚類中心選擇隨機(jī)造成的問題。然后利用文獻(xiàn)[8]的聚類方法和思想進(jìn)行聚類，這樣處理的原因就是大大減輕了孤立點(diǎn)對(duì)聚類結(jié)果的影響，由于初始聚類中心不是隨機(jī)形成的，大大提升了文獻(xiàn)[8]算法的效率和效果。下面從算法的基本概念、思想、步驟等分別加以描述。

3.1 ? 近鄰密度的概念

定義1 ?k距離

在數(shù)據(jù)集D中，數(shù)據(jù)對(duì)象o距離數(shù)據(jù)對(duì)象p之間的距離，我們記為：d（p，o）。對(duì)于任意一個(gè)正整數(shù)k，我們將數(shù)據(jù)對(duì)象p 的k距離記作k-dist（p）。

當(dāng)以下兩個(gè)條件同時(shí)滿足時(shí)，我們認(rèn)為k-dist（p）=d（p，o）：

（1）至多存在k-1個(gè)數(shù)據(jù)對(duì)象滿足： ? ? ?。

（2）至少存在k個(gè)數(shù)據(jù)對(duì)象滿足：;

定義2 ?k近鄰鄰居

首先，根據(jù)定義1中得到數(shù)據(jù)對(duì)象p的k距離，那么對(duì)象p的k近鄰鄰居為這樣一個(gè)集合，其中滿足：數(shù)據(jù)集中所有數(shù)據(jù)對(duì)象到p的距離小于等于k的數(shù)據(jù)對(duì)象。具體記為：。

定義3 近鄰距離

不失一般性，d（p，o）表示數(shù)據(jù)對(duì)象d和數(shù)據(jù)對(duì)象o之間的距離，那么對(duì)象p關(guān)于對(duì)象o的近鄰距離為數(shù)據(jù)對(duì)象p的k距離與數(shù)據(jù)對(duì)象o之間距離的最大值，表示為：

定義4 近鄰密度

給定任意數(shù)據(jù)集合D，數(shù)據(jù)對(duì)象p的近鄰密度定義為：

在定義4中，首先計(jì)算數(shù)據(jù)集中所考察對(duì)象p的k近鄰所有鄰居對(duì)象到對(duì)象p的近鄰距離之和。如果數(shù)據(jù)對(duì)象近鄰密度取值小，就說明它的k近鄰鄰居所涵蓋的范圍就非常小，這個(gè)區(qū)域就是個(gè)高密度區(qū)域。

3.2 ? 算法目標(biāo)函數(shù)

設(shè)為一個(gè)包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集合，其中第i個(gè)數(shù)據(jù)對(duì)象表示為，m為數(shù)據(jù)對(duì)象屬性的數(shù)目。由D生成的k近鄰密度矩陣為

，依據(jù)公式（1）進(jìn)行計(jì)算。數(shù)據(jù)對(duì)象分配矩陣U是的0-1矩陣，=1表示第i個(gè)屬性被分到第P個(gè)簇。為k個(gè)簇中心向量，其中為第p個(gè)簇中心。為k個(gè)權(quán)重向量，其中代表第p個(gè)簇的特征權(quán)重，為第p個(gè)簇中第j個(gè)特征的權(quán)重。通過結(jié)合簇間距離與簇內(nèi)距離的信息，本算法目標(biāo)函數(shù)為：

其中：

文獻(xiàn)[8]已經(jīng)證明了如何計(jì)算，，，這里就不在多做敘述。

3.3 ? 算法步驟與描述

針對(duì)文獻(xiàn)[8]改進(jìn)后的新算法分三大步驟：

首先，根據(jù)預(yù)先設(shè)定的特定權(quán)重W來計(jì)算各個(gè)對(duì)象的k近鄰密度矩陣;預(yù)先設(shè)定一個(gè)閾值，這個(gè)值的設(shè)定關(guān)系到聚類的效果，其主要目的是用來剔除孤立點(diǎn)，然后將剩余的所有數(shù)據(jù)對(duì)象重新組合成新的數(shù)據(jù)對(duì)象，重新對(duì)新的數(shù)據(jù)對(duì)象集進(jìn)行聚類，構(gòu)造新的k近鄰密度矩陣和特征權(quán)重W。

然后，對(duì)構(gòu)造出來的進(jìn)行從小到大的排序，將排在前列的2k個(gè)數(shù)據(jù)對(duì)象選擇出來，將作為初始的聚類中心候選集。在這個(gè)候選集中首選選取前兩個(gè)數(shù)據(jù)對(duì)象作為初始聚類中心，在候選集中剩余的數(shù)據(jù)對(duì)象中選取距離這兩個(gè)初始聚類中心最遠(yuǎn)的一個(gè)數(shù)據(jù)對(duì)象加入初始聚類中心集中，以此類推，直到最終k個(gè)數(shù)據(jù)中心Z形成。

最后，根據(jù)文獻(xiàn)[8]中的算法進(jìn)行聚類。

算法詳細(xì)描述如下：

輸入：d維數(shù)據(jù)集D、預(yù)先設(shè)定的特征權(quán)重W、k近鄰離群閾值

輸出：滿足準(zhǔn)則函數(shù)最小的k個(gè)族類

（1）用設(shè)定的特征權(quán)重W和距離公式來計(jì)算各個(gè)數(shù)據(jù)對(duì)象之間的加權(quán)距離，得到各數(shù)據(jù)對(duì)象的K-dist近鄰矩陣，并一并形成構(gòu)造K-dist近鄰鄰居矩陣和近鄰密度NND矩陣。

（2）根據(jù)近鄰密度矩陣，判斷所有對(duì)象的NND是否大于離群閾值，如果是大于，則將該數(shù)據(jù)對(duì)象作為孤立點(diǎn)去除;如果不是，則保留該數(shù)據(jù)對(duì)象;同時(shí)選擇NND最小的2k個(gè)對(duì)象作為準(zhǔn)初始聚類中心集待用。

（3）在步驟2中形成的矩陣中選取最下的2k個(gè)數(shù)據(jù)對(duì)象作為候選初始聚類中心，然后首先從中選取距離最遠(yuǎn)的兩個(gè)數(shù)據(jù)對(duì)象和，將其作為初始的2個(gè)聚類中心，同時(shí)在候選初始聚類中心集中刪除這兩個(gè)對(duì)象，依次類推，直到找到k個(gè)初始聚類中心。

（4）從上個(gè)步驟中得到的這k個(gè)初始聚類中心為聚類中心，利用文獻(xiàn)[8]的算法KICIC循環(huán)反復(fù)，直到P（W，U，Z）收斂或U不再改變。

3.4 ? 性能分析

根據(jù)上面的算法描述可以看出，改進(jìn)后的聚類算法（簡(jiǎn)稱NKICIC）的時(shí)間復(fù)雜度與傳統(tǒng)K-means聚類算法的區(qū)別主要體現(xiàn)在形成初始聚類中心的時(shí)候，本算法在形成初始聚類中心的時(shí)間復(fù)雜度為：

由于算法在計(jì)算每一個(gè)數(shù)據(jù)對(duì)象的距離矩陣后也會(huì)將其自身的距離矩陣保存起來以方便后續(xù)使用。這里，通過以空間換時(shí)間，算法的時(shí)間復(fù)雜度會(huì)大大降低，當(dāng)然，其空間開銷也會(huì)很巨大，經(jīng)過測(cè)算，增加的空間規(guī)模為的空間開銷。實(shí)驗(yàn)表面，這種方法至少提高10倍以上的時(shí)間效率。

4 ? 實(shí)驗(yàn)及結(jié)果分析（Experiments and results analysis）

為了便于和文獻(xiàn)[8]的算法KICIC進(jìn)行對(duì)比，我們同樣從網(wǎng)站上下載了六個(gè)數(shù)據(jù)集，算法所用的幾個(gè)參數(shù)采用了文獻(xiàn)[8]的結(jié)果，以同樣的評(píng)價(jià)指標(biāo)主要分析了傳統(tǒng)K-means、KICIC算法與改進(jìn)后的NKICIC算法。

實(shí)驗(yàn)結(jié)果：根據(jù)表1的結(jié)果分析，NKICIC總體上優(yōu)于原KICIC算法，遠(yuǎn)優(yōu)于傳統(tǒng)K-means算法。主要原因是由于原算法KICIC中沒有消除孤立點(diǎn)，加上對(duì)初始聚類中心的敏感原因?qū)е戮垲惤Y(jié)果不穩(wěn)定。

根據(jù)表1中的數(shù)據(jù)可以得出，從各項(xiàng)指標(biāo)來看，改進(jìn)后的K-means算法的綜合聚類效果提高了不少。

算法的時(shí)間性能方面，實(shí)驗(yàn)結(jié)果如圖1所示。

從圖1中可以看到，改進(jìn)后的算法雖然增加了三個(gè)矩陣的計(jì)算時(shí)間消耗，但由于三個(gè)矩陣為后期刪除了孤立點(diǎn)、確定了初始聚類中心，大大減少了后期聚類算法的收斂時(shí)間，兩者抵消，所以總的時(shí)間消耗沒有增加太多。

5 ? 結(jié)論（Conclusion）

本文在傳統(tǒng)距離公式中加入特征屬性的權(quán)重，并據(jù)此計(jì)算每個(gè)數(shù)據(jù)對(duì)象的近鄰矩陣，通過定義一定的距離閾值來減輕數(shù)據(jù)孤立點(diǎn)對(duì)聚類算法執(zhí)行結(jié)果的影響，同時(shí)有針對(duì)行的選擇形成初始聚類中心，隨后根據(jù)集成族內(nèi)與族間的距離來進(jìn)行聚類。實(shí)驗(yàn)結(jié)果顯示，新的聚類算法在性能基本沒有損耗的情況下提升了原算法的準(zhǔn)確度和聚類效果。

參考文獻(xiàn)（References）

[1] James MacQueen. Some methods for classification and analysis of multivariate observations[C]. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability， University of California Press， 1967： 281-297.

[2] Wang Huai-bin， Yang Hong-liang， Xu Zhi-jian. A clustering algorithm use SOM and K-Means in Intrusion Detection[C]. 2010 International Conference on E-Business and E-Government， Guangzhou， 2010： 1281-1284.

[3] 莫錦萍，陳琴，馬琳，等.一種新的K-Means蟻群聚類算法[J].廣西科學(xué)院學(xué)報(bào)，2008，24（4）：284-286.

[4] 曹志宇，張忠林，李元韜.快速查找初始聚類中心的k-means算法[J].蘭州交通大學(xué)學(xué)報(bào)，2009，28（6）：15-18.

[5] 邢長征，谷浩.基于平均密度優(yōu)化初始聚類中心的k-means算法[J].計(jì)算機(jī)工程與應(yīng)用，2014，50（20）：135-138.

[6] Jia H，Ding S，Du M，et al.Approximate normalized cuts without eigen-decomposition[J].Information Sciences，2016（374）：135-150.

[7] 張建民.一種改進(jìn)的K-means聚類算法[J].微計(jì)算機(jī)信息，2010（9）：233-234.

[8] 黃曉輝，王成，熊李艷，等.一種集成簇內(nèi)和簇間距離的加權(quán)k-means聚類方法[J].計(jì)算機(jī)學(xué)報(bào)，2019，59（42）：1-15.

作者簡(jiǎn)介：

羅軍鋒（1976-），男，碩士，高級(jí)工程師.研究領(lǐng)域：數(shù)據(jù)挖掘，區(qū)塊鏈.

洪丹丹（1981-），女，碩士，高級(jí)工程師.研究領(lǐng)域：主數(shù)據(jù)工程，高校信息化.