白潔 楊懌

關(guān)鍵詞：K-Means 算法；聚類分析；聚類中心；最大距離；最大密度

0 引言

最近科學(xué)數(shù)據(jù)收集技術(shù)的進(jìn)步和復(fù)雜多樣的數(shù)據(jù)量的不斷增長(zhǎng)，在數(shù)據(jù)分析或挖掘過程中更難操縱它們或提取有用的信息。此外，為數(shù)據(jù)找到合適的標(biāo)簽既昂貴又耗時(shí)，因此大多數(shù)數(shù)據(jù)都沒有標(biāo)簽。這就是無監(jiān)督聚類方法發(fā)揮作用的地方。聚類是將具有相似特征的項(xiàng)目分組在一起的行為。這樣，每個(gè)聚類分組由與其他聚類分組的項(xiàng)目不同的相似項(xiàng)目組成。

目前最流行的數(shù)據(jù)挖掘方法有分類、聚類、關(guān)聯(lián)規(guī)則分析、回歸等，聚類算法是數(shù)據(jù)挖掘的一個(gè)重要分支，它豐富了各種不同的問題主題，在現(xiàn)實(shí)生活中有著廣泛的應(yīng)用，包含機(jī)器視覺、信息檢索、圖像處理等領(lǐng)域[1]。它是一種無監(jiān)督的學(xué)習(xí)方法，其過程是將數(shù)據(jù)集劃分成若干個(gè)類，使得同一類中的數(shù)據(jù)信息相似度盡可能大，不同類中的數(shù)據(jù)信息差異盡可能大[2]。聚類算法近些年不斷發(fā)展，現(xiàn)今已經(jīng)有很多分支，按照算法的性能主要分為基于劃分的聚類、基于層次的聚類、基于網(wǎng)格的聚類、基于密度的聚類等。KMeans算法是基于劃分的聚類算法這一分支中經(jīng)典的算法。1967年，MacQueen首次提出了K-Means聚類算法[3]。由于它具有實(shí)現(xiàn)形式簡(jiǎn)單、時(shí)間復(fù)雜度低的優(yōu)點(diǎn)，已在數(shù)據(jù)科學(xué)、工業(yè)應(yīng)用等領(lǐng)域中被廣泛采用[4-6]。

1 K-Means 算法及改進(jìn)

1.1 K-Means 算法

K-Means算法是基于劃分的聚類算法這一分支中經(jīng)典的算法。K-Means算法一般采用歐氏距離作為度量對(duì)象之間相似性的指標(biāo)。相似度與記錄之間的歐氏距離成反比。記錄之間的相似度越大，距離越小。該算法需要事先指定初始聚類個(gè)數(shù)k 和初始聚類中心，并根據(jù)數(shù)據(jù)對(duì)象與聚類中心的相似度不斷更新聚類中心的位置。當(dāng)目標(biāo)函數(shù)收斂時(shí)，聚類結(jié)束[7]。

目前，K-Means算法的改進(jìn)方法主要集中在以下幾個(gè)方向：算法初始k 值的選取、初始聚類中心點(diǎn)的選取、孤立點(diǎn)的檢測(cè)與去除。

1.2算法改進(jìn)

K-Means聚類算法是經(jīng)典且應(yīng)用廣泛的基于劃分的聚類方法之一，具有理論可靠、算法簡(jiǎn)單、收斂速度快、能有效處理大數(shù)據(jù)集等優(yōu)點(diǎn)。但是傳統(tǒng)的KMeans算法過度依賴于初始條件[8]。即初始聚類數(shù)目K值和聚類中心的選擇影響最終的聚類結(jié)果以及KMeans算法的收斂速度。假設(shè)聚類數(shù)目K值已經(jīng)確定，選取不同的初始聚類中心又會(huì)導(dǎo)致不同的聚類結(jié)果，隨機(jī)選取的初始聚類中心點(diǎn)將會(huì)增加最終聚類結(jié)果的隨機(jī)性和不可靠性。在上文的分析中也總結(jié)出，K-Means算法對(duì)離群點(diǎn)和孤立點(diǎn)敏感。因此針對(duì)聚類中心的選擇對(duì)K-Means算法作出改進(jìn)。

在K-Means++中，對(duì)于下一個(gè)聚類中心點(diǎn)一般選擇距離當(dāng)次迭代的聚類中心最遠(yuǎn)的數(shù)據(jù)點(diǎn)或者與其最近的數(shù)據(jù)點(diǎn)，此方法遵循了兩個(gè)類簇盡可能遠(yuǎn)的原則。因此借鑒K-Means++選擇聚類中心的思想，以及基于密度分類的DBSCAN算法的思路，提出一種優(yōu)化聚類中心的K-Means算法。改進(jìn)以及優(yōu)化聚類中心的選擇與確定，同時(shí)基于密度和最大距離來分類的思想也可以避免選擇離群點(diǎn)或孤立點(diǎn)為聚類中心，導(dǎo)致聚類結(jié)果有偏差的情況。

傳統(tǒng)K-Means算法是計(jì)算各個(gè)類內(nèi)記錄的均值作為新的聚類中心，但往往因?yàn)楫惓Ｖ祷蛘唠x群點(diǎn)導(dǎo)致結(jié)果出現(xiàn)局部最優(yōu)，因此采用最大密度和最大距離的方法來確定聚類中心?；谧畲缶嚯x和最大密度的中心點(diǎn)初始化方法分為兩個(gè)步驟，首先計(jì)算所有樣本的密度，然后選取一部分密度較大的樣本作為候選集，然后從候選集中選取彼此相距較遠(yuǎn)的k個(gè)樣本作為初始中心。

改進(jìn)后的算法思路是，計(jì)算數(shù)據(jù)集中所有任意兩個(gè)數(shù)據(jù)之間的距離和平均距離，計(jì)算出數(shù)據(jù)的密度和平均密度，設(shè)置一個(gè)空數(shù)據(jù)集T，將大于平均密度的所有數(shù)據(jù)對(duì)象添加到數(shù)據(jù)集T中，選擇密度最大的數(shù)據(jù)對(duì)象作為第一個(gè)聚類中心，并將這個(gè)數(shù)據(jù)添加到設(shè)置的空數(shù)據(jù)集F中；再根據(jù)定義5計(jì)算數(shù)據(jù)集T中距離數(shù)據(jù)集F最遠(yuǎn)的數(shù)據(jù)，把這個(gè)數(shù)據(jù)添加到數(shù)據(jù)集F中；重復(fù)計(jì)算，直到數(shù)據(jù)集F中有K 個(gè)數(shù)據(jù)，就是最終的聚類中心。根據(jù)距離公式計(jì)算其他數(shù)據(jù)與k 個(gè)聚類中心的距離，根據(jù)大小劃分到最近的聚類當(dāng)中。

具體步驟如下：

輸入：n條數(shù)據(jù)的數(shù)據(jù)集D，聚類個(gè)數(shù)k

輸出：k 個(gè)聚類中心和k 個(gè)類

Step1：根據(jù)歐氏距離公式和定義1計(jì)算出任意兩條記錄之間的距離和平均距離。

Step2：根據(jù)定義3和定義4計(jì)算出數(shù)據(jù)集中每條數(shù)據(jù)的密度和平均密度。

Step3：比較每條數(shù)據(jù)的密度和平均密度，設(shè)置一個(gè)空數(shù)據(jù)集T，將大于平均密度的數(shù)據(jù)添加到T中。

Step4：在數(shù)據(jù)集T中選取密度最大的一條數(shù)據(jù)作為第一個(gè)聚類中心，加入新數(shù)據(jù)集F中。

Step5：從T中選擇離數(shù)據(jù)F最遠(yuǎn)的數(shù)據(jù)，作為下一個(gè)聚類中心。

Step6：重復(fù)step5，直到數(shù)據(jù)集F中有k條數(shù)據(jù)，也就是k個(gè)聚類中心。

Step7：根據(jù)剩余n-k條數(shù)據(jù)和k個(gè)聚類中心之間的距離，依次劃分到相應(yīng)的類當(dāng)中，得到k個(gè)聚類。

2 實(shí)驗(yàn)結(jié)果對(duì)比分析

在K-Means++的算法思想基礎(chǔ)上，提出一種基于k 值確定和優(yōu)化聚類中心的K-Means 算法（DD-Kmeans）。其中，優(yōu)化聚類中心是基于距離和密度來確定聚類中心，和DBSCAN 算法有部分相同思想。因此，這部分實(shí)驗(yàn)是將改進(jìn)的K-Means 算法與KMeans++、DBSCAN算法進(jìn)行對(duì)比分析。實(shí)驗(yàn)部分選擇UCI上的機(jī)器學(xué)習(xí)常用數(shù)據(jù)集，包括wine、yeast、Di?abetes、segmentation。

實(shí)驗(yàn)從準(zhǔn)確率和算法穩(wěn)定性兩方面進(jìn)行對(duì)比。準(zhǔn)確率就是改進(jìn)算法DD-K-means的聚類結(jié)果中，每個(gè)類別的數(shù)量與數(shù)據(jù)集原始類中數(shù)據(jù)數(shù)量的比值。將DD-K-Means算法與K-Means++算法，DBSCAN算法在wine，segmention，yeast，Diabetes 數(shù)據(jù)下多次實(shí)驗(yàn)，取平均值。實(shí)驗(yàn)結(jié)果圖如圖1所示，由圖可以分析出，DD-K-Means算法相較于K-Means++和DBSCAN有明顯的準(zhǔn)確度提升。在wine 數(shù)據(jù)集上，DD-KMeans算法聚類準(zhǔn)確率相較于其他算法提高了7.03%，4.06%；而在Segmentaion 數(shù)據(jù)集上，DD-KMeans算法相較于其他算法提高了16.54%，13.64%。數(shù)據(jù)量越大，聚類效果提升更明顯。因此，基于密度和最大距離的算法改進(jìn)，有效優(yōu)化了聚類結(jié)果。如圖2 所示，DD-K-Means 算法和K-Means++算法，DB?SCAN算法在Yeast數(shù)據(jù)集上進(jìn)行多次實(shí)驗(yàn)，明顯看出K-Means++算法穩(wěn)定性在這三種算法中最差，最高達(dá)到19%的差值，而DBSCAN算法近11%的波動(dòng)范圍。DD-K-Means將算法準(zhǔn)確率的波動(dòng)維持在6%以內(nèi)，保證了算法的穩(wěn)定性。

3 結(jié)論

K-Means聚類算法中初始聚類中心一般是隨機(jī)選取，聚類數(shù)目往往人為確定，使得有不同的初始聚類中心和聚類數(shù)目的相同數(shù)據(jù)集聚類結(jié)果不一樣。為了解決此問題，基于最大距離和最大密度選取聚類中心，計(jì)算數(shù)據(jù)的距離和平均距離，密度和平均密度，根據(jù)距離和密度選擇合適的聚類中心，避免人為選擇聚類中心影響聚類結(jié)果，同時(shí)也避免孤立點(diǎn)和離散點(diǎn)對(duì)聚類結(jié)果的影響。實(shí)驗(yàn)結(jié)果表明，所提出算法聚類結(jié)果更穩(wěn)定，效果更好。與K-Means聚類算法相比，改進(jìn)算法具有如下優(yōu)勢(shì)：初始聚類中心以及其他聚類中心的選取是經(jīng)過計(jì)算得到的。但是，由于改進(jìn)算法同時(shí)進(jìn)行了距離和密度的計(jì)算，導(dǎo)致復(fù)雜度增加；聚類數(shù)目人為確定的問題也沒有改善。因此，在今后的研究工作中，可以考慮優(yōu)化k值的選擇，利用程序確定合適的k值，同智能優(yōu)化相結(jié)合，以得到更加高效的聚類效果。