一種對孤立點不敏感的新的K?Means聚類算法

包志強 趙媛媛 胡嘯天 趙研

摘? 要： 針對傳統K?Means聚類算法的不足，提出一種新的對孤立點不敏感的K?Means聚類算法。首先，采用孤立點移除算法消除數據集中存在的孤立點;然后，對不包含孤立點的數據集進行傳統K?Means聚類，再引入輪廓系數并選擇輪廓系數最大值對應的簇類數作為數據集中簇的最優選擇數目[K];最后，通過自定義的聚類有效性評價函數評估聚類效果。實驗結果表明，相對于傳統K?Means聚類算法，對孤立點不敏感的新的K?Means聚類算法能夠消除孤立點對數據集整體的影響，并優化了聚類中心的選擇。

關鍵詞： K?Means聚類算法; 孤立點; 輪廓系數; 簇類數; 聚類有效性評價函數; 聚類中心

中圖分類號： TN911.1?34; TP391.9? ? ? ? ? ? ? ? ? ?文獻標識碼： A? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2020）05?0109?04

A new K?Means clustering algorithm not sensitive to outliers

BAO Zhiqiang， ZHAO Yuanyuan， HU Xiaotian， ZHAO Yan

（College of Communication and Information Engineering， Xian University of Posts and Telecommunications， Xian 710121， China）

Abstract： In view of the shortcomings of traditional K?Means clustering algorithm， a new K?Means clustering algorithm not sensitive to outliers is proposed. Firstly， the outlier removal algorithm is adopted to eliminate the outliers in the data sets. Secondly， the traditional K?Means clustering algorithm is applied to the data sets that do not contain outliers. And then， the contour coefficient is introduced and the number of clusters corresponding to the maximum value of the contour coefficient is chosen as the optimal number [K] of clusters in the data sets. Finally， the clustering effect is evaluated by the clustering effectiveness evaluation function defined in this paper. The experimental results show that， in comparison with the traditional K?Means clustering algorithm， the new K?Means clustering algorithm not sensitive to outliers can eliminate the influence of outliers on the whole data sets and optimize the selection of cluster centers.

Keywords： K?Means clustering algorithm; outlier; contour coefficient; number of clusters; clustering effectiveness evaluation function; cluster center

0? 引? 言

聚類是數據挖掘及數據分析中的一項重要技術[1]。數據聚類是將空間中的[N]個點聚為[K]個類，并最大化類內對象的相似性，同時最小化類間對象的相似性[1]，主要用于發現數據中的不同類別及從數據中識別出特定的分布或模式[2]。隨著聚類分析的快速發展，到目前為止已經提出了許多經典的聚類算法，例如，基于分區的K?Means聚類算法[3]和[k]中心點算法[4]、基于密度的DBSCAN聚類模型[5]、基于連通性的層次聚類算法[6]等。

K?Means聚類是Mac Queen在1967年開發的，是經典的和最廣泛使用的聚類算法之一。傳統K?Means聚類算法在初始聚類中心的選擇過程中易受到邊界點、孤立點的影響，從而使得隨機選取的聚類中心可能是孤立點，導致聚類結果偏離數據集中樣本的真實分布，且K?Means的最終聚類結果受初始聚類中心點的影響，選擇不好的初始種子點會使解決方案收斂到局部最優，且會妨礙算法收斂速度[1]。

針對這一缺陷，文獻[7]提出采用最小方差優化初始聚類中心的K?Means算法，該算法對噪聲具有較強的免疫功能。文獻[8]引入密度思想解決了用戶隨機確定聚類數的問題，但該算法仍然存在密度參數設置方面的缺陷，有待進一步改進。文獻[9]提出一種結合初始聚類中心優化和特征加權的改進算法，該算法具有比傳統算法更高的聚類精度。鑒于該算法存在的這一缺點，消除孤立點對數據集的影響以及優化初始聚類中心的問題一直是該算法改進的重要方向。

本文提出一種對孤立點不敏感的改進K?Means聚類算法，即首先對所有樣本進行某種距離計算，排除數據集中存在的孤立點，然后對不包含孤立點的數據集進行傳統K?Means聚類算法，再引入輪廓系數并選擇輪廓系數最大值對應的簇類數作為數據集中簇的最優選擇數目[K]，得到聚類結果。實驗結果表明，與傳統的K?Means聚類算法相比，改進算法消除了邊界點、孤立點對聚類結果的影響，優化了對聚類中心的選擇。

1? K?Means聚類算法

K?Means聚類以處理大型數據集和快速收斂到局部最優而聞名。在K?Means聚類中，首先選擇簇的個數[K]，其次，反復迭代尋找最佳聚類中心并將[N]個樣本點劃分為[K]個互不相交的簇，使得簇內對象的相似性最大化且最小化簇間對象的相似性。設數據集樣本為[X=（x1，x2，…，xN）]，[xi∈Rd]。目標函數常被用來衡量聚類結果的好壞，其定義方式如下：

[J=j=1K i，j∈μjd（xi，μj）]

式中：[xi]表示第[i]個樣本點;[μj]表示第[j]類的聚類中心;[d（xi，μj）]表示樣本點[xi]與聚類中心[μj]的距離。

歐氏距離[10]常被用來度量樣本點之間的距離，其定義方式如下：

[d（xi，xj）=（xi1-xj1）2+（xi2-xj2）2+…+（xin-xjn）2]

式中：[xi=（xi1，xi2，…，xin）];[xj=（xj1，xj2，…，xjn）]。

2? 對孤立點不敏感的新的K?Means聚類算法

K?Means聚類的初始聚類中心的選擇是隨機的，這導致聚類結果的隨機性，并且聚類中心的選擇易受到噪聲點、孤立點的影響，因此，隨機選取的聚類中心可能是孤立點或邊界點，導致聚類結果達不到最優。針對該算法存在的缺陷，本文首先采用孤立點移除思想排除數據集中存在的孤立點，然后對不包含孤立點的數據集進行傳統K?Means聚類，采用輪廓系數進行最優聚類數的選擇，并選取輪廓系數最大值對應的聚類數作為最佳聚類數，最后引入本文定義的聚類有效性評價函數評估聚類結果，且評價函數的值越小，聚類的效果越好。

2.1? 孤立點移除思想

設數據集樣本為[X=（x1，x2，…，xN）]，[xi∈Rd]，樣本點個數為[N]。

Step1：假設[N]個樣本點中任意一個點[A]為孤立點;

Step2：求剩余[N]-1個點的平均歐氏距離[ad];

Step3：求點[A]到剩余[N]-1個點的歐氏距離[d]的最小值min_[d];

Step4：若min_[d]>[ad]，則視該點為孤立點，將其移除;若min_[d

重復以上步驟，直到找出所有孤立點，算法結束。

2.2? 輪廓系數

輪廓系數是評價聚類效果好壞的方法[11]。為了提高聚類質量，本文引入輪廓系數確定聚類數目[K]，它量化數據集中的任一對象與本簇中其他對象的相似性以及該對象與其他簇中對象的相似性，且將量化后的兩種相似性以某種形式組合，獲得聚類的優劣評價標準[11]。對于任意對象[i]，其輪廓系數[silhouettei]的計算公式為：

[silhouettei=bi-aimax（ai，bi）]

式中：[ai]是對凝聚度的體現，是指對象[i]到它所屬簇中其他對象的平均距離;[bi]是對分離度的體現，是指對象[i]到不包含該對象的任意簇中所有對象的平均距離。

當[silhouettei]=1時，表示對象[i]與其他簇中的對象之間差異性較大;當[silhouettei]=0時，表示對象[i]分類不明顯;當[silhouettei]=-1時，表示對象[i]被錯誤分配到一個簇中。

2.3? 聚類有效性評價函數

好的聚類算法是使得屬于同一個類的對象盡可能的相似，屬于不同類的對象盡可能的相異。也就是說，聚類的最終目的是使得簇內距離越小，簇間距離越大，從而使得聚類質量越高，聚類效果越明顯。

本文采用如下方法作為判別聚類有效性的準則，即對類內距離within（[k]）和類間距離between（[k]）的倒數和取自然對數，且自然對數為單調增函數，即當within（[k]）與[1between（k）]越小時，[J（k）]越小，聚類效果越好。

[J（k）=ln1between（k）+within（k）=ln1+within（k）between（k）between（k）=ln1+within（k）between（k）-lnbetween（k）]

1） 類內距離

本文以每個對象到同一簇內其他所有對象之間距離的最大值作為該簇的類內距離，以簇內距離的最大值作為數據集整體的類內距離。

[within（k）=max1≤i≤kmax1≤j≤Ci1Ci-1p=1，p≠jCixj-xp]

式中：within（[k]）表示數據集整體的類內距離;[Ci]為類別屬于[Ci]的樣本數量的個數;[xj][-][xp]為類別[Ci]中的距離，而數據集整體的類內距離即為所有簇的類內距離的最大值，即樣本對象。由評價函數可知，within（[k]）越小，則[J（k）]越小，聚類質量越佳。

2） 類間距離

本文以不同簇中任一樣本對象之間的最小距離作為數據集整體的類間距離。

[between（k）=minxp∈Ci，xq∈Cj，i≠jxp-xq]

式中：between（[k]）表示數據集整體的類間距離; [i=1，2，…，k];[j=1，2，…，k];[xp]，[xq]分別為簇[Ci]和[Cj]中的樣本對象。由評價函數可知，between（[k]）越大，則[J（k）]越小，聚類質量越佳。

2.4? 新的K?Means聚類算法

新的K?Means聚類算法步驟如下：

Step1：輸入待聚類的數據集樣本[X=（x1，x2，…，xN）];

Step2：采用孤立點移除思想將數據集樣本中的所有孤立點移除，得到樣本分布相對集中不包含孤立點的數據集[X=（x′1，x′2，…，x′M）]，[M≤N];

Step3：將傳統K?Means聚類算法應用于數據集[X=（x′1，x′2，…，x′M）]，然后引入輪廓系數[silhouettei]并選擇輪廓系數最大值對應的簇類數[K]作為數據集中簇的最優選擇數目[Kopt];

Step4：引入聚類有效性評價函數[J（k）]評估聚類效果。

3? 仿真實驗分析

為了驗證本文提出的新的K?Means聚類算法對孤立點不敏感的有效性，現對原始算法和新的K?Means聚類算法進行比較實驗。實驗選取的數據源為滿足二維正態高斯分布的隨機數據集，樣本數[N=174]。原始數據集如圖1所示，該數據集是由3個二維正態高斯分布所生成。

實驗采用輪廓系數進行聚類[K]值的選擇，即對數據集進行傳統K?Means聚類，得到不同聚類數對應的輪廓系數，并選取輪廓系數最大值對應的聚類數[K]作為最佳聚類數[Kopt]，且對應的輪廓系數為最佳輪廓系數。聚類數[K]等于2，3，4，5，6時對應的輪廓系數如表1所示。

由表1可知，當聚類數[K=2]時，對應的輪廓系數[silhouettei=0.781]，達到最大值，因此，該實驗數據的最佳聚類數為2。聚類數[K=2]時數據集的分布圖如圖2所示。

將該數據集通過本文提出的對孤立點不敏感的新的K?Means聚類后，數據集中坐標為（2.622 331 59，11.939 470 51），（9.364 644 07，0.180 513 12），（40.231 436 48，0.230 515 19）的三個點即圖3中的三個黑圓點被視為孤立點且被移除，移除后的數據集分布圖如圖4所示。

對移除孤立點后的數據進行K?Means聚類，并采用輪廓系數最優原則進行聚類數[K]值的選擇，移除孤立點后該數據集聚類數[K]等于2，3，4，5，6時對應的輪廓系數如表2所示。

由表2可知，移除孤立點后該數據集的最大輪廓系數為[silhouettei=0.799]，對應的最佳聚類數為[K=2]，且相較于原始數據集聚類后的最佳輪廓系數[silhouettei=0.781]，[silhouettei]增大了0.018，輪廓系數越大，聚類效果越好。

為了更有效地驗證本文算法的有效性，通過本文定義的聚類有效性評價函數，對移除孤立點前后的數據集進行[J（k）]值的比較對照，如表3所示。

由聚類有效性評價函數的分析可知，[J（k）]值越小，聚類效果越好，表3中移除孤立點之后的[J（k）]值均明顯小于未移除孤立點的[J（k）]值，且當聚類數[K=2]時，對應的[J（k）]值最小，聚類效果最好。

因此，與經典K?Means聚類算法相比，本文算法消除了孤立點對聚類效果的影響，優化了對初始聚類中心的隨機選取。本文算法相較于其他改進算法，如文獻[12]的孤立點移除算法，該算法引入了基于密度的思想，需要確定密度參數，但在具體實現中參數的選擇很難確定，本文算法克服了密度參數選擇這一缺陷，采用基于距離的思想移除數據集中存在的孤立點。

4? 結? 語

K?Means聚類算法是最廣泛使用的聚類算法之一，但其因初始聚類中心的不確定性以及聚類數[K]值未知且易受孤立點、噪聲點的影響，導致聚類結果不穩定，且易造成局部最優，使得聚類效果不佳。本文提出的對孤立點不敏感的新的K?Means聚類算法相較于傳統K?Means聚類算法，消除了孤立點對數據集整體的影響，從而避免陷入局部最優，且采用輪廓系數進行聚類數[K]值的選擇，解決了[K]值未知的問題，并提出聚類有效性評價函數[J（k）]評估數據集的聚類效果。實驗結果表明，本文算法能夠消除孤立點對數據集整體的影響，并引入輪廓系數確定最佳聚類數，引入聚類有效性評價函數評估了最優聚類中心。

參考文獻

[1] JAIN A K. Data clustering： 50 years beyond K?means [J]. Pattern recognition letters， 2010， 31（8）： 651?666.

[2] 王秀華，秦振吉.基于層次K?均值聚類的支持向量機模型[J].計算機應用與軟件，2014，31（5）：172?176.

[3] 劉建生，吳斌，章澤煜.基于相關性加權的K?means算法[J].江西理工大學學報，2018，39（1）：87?92.

[4] 陳逸斐，虞慧群.xk?split：基于k?medoids的分裂式聚類算法[J].華東理工大學學報（自然科學版），2017，43（6）：849?854.

[5] 王兆豐，單甘霖.一種基于k?均值的DBSCAN算法參數動態選擇方法[J].計算機工程與應用，2017，53（3）：80?86.

[6] 蔣林利，吳建生.層次K?均值聚類結合改進ITML的遷移度量學習方法[J].計算機應用研究，2017，34（12）：3552?3555.

[7] 謝娟英，王艷娥.最小方差優化初始聚類中心的K?means算法[J].計算機工程，2014，40（8）：205?211.

[8] 張琳，陳燕，汲業，等.一種基于密度的K?means算法研究[J].計算機應用研究，2011，28（11）：4071?4073.

[9] 王宏杰，師彥文.結合初始中心優化和特征加權的K?Means聚類算法[J].計算機科學，2017，44（z2）：457?459.

[10] LIU X M， LEI D. An improved K?Means clustering algorithm [J]. Journal of networks， 2014， 9（1）： 1?3.

[11] 王學賀.一種基于改進微粒群和輪廓系數的劃分聚類方法[J].云南民族大學學報（自然科學版），2016，25（4）：367?371.

[12] 蔣麗，薛善良.優化初始聚類中心及確定[K]值的K?Means算法[J].計算機與數字工程，2018，46（1）：21?24.