包志強(qiáng) 趙媛媛 胡嘯天 趙研

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

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

中圖分類號： TN911.1?34; TP391.9? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼： 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? 引? 言

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

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

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

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

1? K?Means聚類算法

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

[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聚類的初始聚類中心的選擇是隨機(jī)的，這導(dǎo)致聚類結(jié)果的隨機(jī)性，并且聚類中心的選擇易受到噪聲點、孤立點的影響，因此，隨機(jī)選取的聚類中心可能是孤立點或邊界點，導(dǎo)致聚類結(jié)果達(dá)不到最優(yōu)。針對該算法存在的缺陷，本文首先采用孤立點移除思想排除數(shù)據(jù)集中存在的孤立點，然后對不包含孤立點的數(shù)據(jù)集進(jìn)行傳統(tǒng)K?Means聚類，采用輪廓系數(shù)進(jìn)行最優(yōu)聚類數(shù)的選擇，并選取輪廓系數(shù)最大值對應(yīng)的聚類數(shù)作為最佳聚類數(shù)，最后引入本文定義的聚類有效性評價函數(shù)評估聚類結(jié)果，且評價函數(shù)的值越小，聚類的效果越好。

2.1? 孤立點移除思想

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

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

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

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

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

重復(fù)以上步驟，直到找出所有孤立點，算法結(jié)束。

2.2? 輪廓系數(shù)

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

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

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

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

2.3? 聚類有效性評價函數(shù)

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

本文采用如下方法作為判別聚類有效性的準(zhǔn)則，即對類內(nèi)距離within（[k]）和類間距離between（[k]）的倒數(shù)和取自然對數(shù)，且自然對數(shù)為單調(diào)增函數(shù)，即當(dāng)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） 類內(nèi)距離

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

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

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

2） 類間距離

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

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

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

2.4? 新的K?Means聚類算法

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

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

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

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

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

3? 仿真實驗分析

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

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

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

將該數(shù)據(jù)集通過本文提出的對孤立點不敏感的新的K?Means聚類后，數(shù)據(jù)集中坐標(biāo)為（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中的三個黑圓點被視為孤立點且被移除，移除后的數(shù)據(jù)集分布圖如圖4所示。

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

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

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

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

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

4? 結(jié)? 語

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

參考文獻(xiàn)

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

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

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

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

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

[6] 蔣林利，吳建生.層次K?均值聚類結(jié)合改進(jìn)ITML的遷移度量學(xué)習(xí)方法[J].計算機(jī)應(yīng)用研究，2017，34（12）：3552?3555.

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

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

[9] 王宏杰，師彥文.結(jié)合初始中心優(yōu)化和特征加權(quán)的K?Means聚類算法[J].計算機(jī)科學(xué)，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] 王學(xué)賀.一種基于改進(jìn)微粒群和輪廓系數(shù)的劃分聚類方法[J].云南民族大學(xué)學(xué)報（自然科學(xué)版），2016，25（4）：367?371.

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