一種對(duì)孤立點(diǎn)不敏感的新的K?Means聚類(lèi)算法

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

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

關(guān)鍵詞： K?Means聚類(lèi)算法; 孤立點(diǎn); 輪廓系數(shù); 簇類(lèi)數(shù); 聚類(lèi)有效性評(píng)價(jià)函數(shù); 聚類(lèi)中心

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

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

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

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

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

1? K?Means聚類(lèi)算法

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

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

式中：[xi]表示第[i]個(gè)樣本點(diǎn);[μj]表示第[j]類(lèi)的聚類(lèi)中心;[d（xi，μj）]表示樣本點(diǎn)[xi]與聚類(lèi)中心[μj]的距離。

歐氏距離[10]常被用來(lái)度量樣本點(diǎn)之間的距離，其定義方式如下：

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

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

2? 對(duì)孤立點(diǎn)不敏感的新的K?Means聚類(lèi)算法

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

2.1? 孤立點(diǎn)移除思想

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

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

Step2：求剩余[N]-1個(gè)點(diǎn)的平均歐氏距離[ad];

Step3：求點(diǎn)[A]到剩余[N]-1個(gè)點(diǎn)的歐氏距離[d]的最小值min_[d];

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

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

2.2? 輪廓系數(shù)

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

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

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

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

2.3? 聚類(lèi)有效性評(píng)價(jià)函數(shù)

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

本文采用如下方法作為判別聚類(lèi)有效性的準(zhǔn)則，即對(duì)類(lèi)內(nèi)距離within（[k]）和類(lèi)間距離between（[k]）的倒數(shù)和取自然對(duì)數(shù)，且自然對(duì)數(shù)為單調(diào)增函數(shù)，即當(dāng)within（[k]）與[1between（k）]越小時(shí)，[J（k）]越小，聚類(lèi)效果越好。

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

1） 類(lèi)內(nèi)距離

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

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

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

2） 類(lèi)間距離

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

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

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

2.4? 新的K?Means聚類(lèi)算法

新的K?Means聚類(lèi)算法步驟如下：

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

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

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

Step4：引入聚類(lèi)有效性評(píng)價(jià)函數(shù)[J（k）]評(píng)估聚類(lèi)效果。

3? 仿真實(shí)驗(yàn)分析

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

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

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

將該數(shù)據(jù)集通過(guò)本文提出的對(duì)孤立點(diǎn)不敏感的新的K?Means聚類(lèi)后，數(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）的三個(gè)點(diǎn)即圖3中的三個(gè)黑圓點(diǎn)被視為孤立點(diǎn)且被移除，移除后的數(shù)據(jù)集分布圖如圖4所示。

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

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

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

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

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

4? 結(jié)? 語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

[9] 王宏杰，師彥文.結(jié)合初始中心優(yōu)化和特征加權(quán)的K?Means聚類(lèi)算法[J].計(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ù)的劃分聚類(lèi)方法[J].云南民族大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，25（4）：367?371.

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