基于密度標準差優(yōu)化初始聚類中心的k_means改進算法

黃靈 王云鋒 陳光武

摘要： 傳統(tǒng)k_means算法采用隨機法選擇初始聚類中心，易造成聚類結果陷入局部最優(yōu)解和聚類精度低的問題，而且易受孤立點的影響。為了解決這一問題，提出了一種基于密度標準差優(yōu)化初始聚類中心的改進算法。該算法先計算數(shù)據(jù)集樣本的平均值和標準差，接著計算每個數(shù)據(jù)點的密度分布函數(shù)值，然后計算樣本的平均密度和密度標準差，若小于密度標準差，則劃分為孤立點；搜索密度分布函數(shù)值數(shù)組中的最大值，那么最大值對應的樣本點即為初始聚類中心，并將以初始聚類中心為原點，以樣本平均值為半徑的圓內(nèi)各點的密度函數(shù)值賦值為0，如此重復，直到找到k個初始聚類中心。該算法基于Python語言在PyCharm軟件平臺實現(xiàn)。實驗結果表明，這種基于密度標準差優(yōu)化初始聚類中心的算法消除了孤立點的影響，具有更高的準確率和更好的聚類結果。

關鍵詞： k_means算法；密度標準差；初始聚類中心；Python

中圖分類號：TP301 文獻標識碼：A 文章編號：1009-3044（2019）06-0147-05

1 引言

數(shù)據(jù)挖掘，又稱為數(shù)據(jù)庫知識發(fā)現(xiàn)，是從海量的、無規(guī)律的、有噪聲的數(shù)據(jù)中，提取出潛在的、對人們有利用價值的信息和知識的過程[1]。數(shù)據(jù)挖掘是一門多學科交叉的學問，包括：機器學習、統(tǒng)計、數(shù)據(jù)庫、人工智能、信息檢索和可視化[2]。數(shù)據(jù)挖掘分析方法包括：分類，估計，預測，相關性分組或關聯(lián)規(guī)則，聚類，復雜數(shù)據(jù)類型挖掘（Text，Web，圖形圖像，視頻，音頻等）。

聚類分析作為數(shù)據(jù)挖掘領域中常用的數(shù)據(jù)分析方法，它是數(shù)據(jù)之間的相似度作為評判事物類別的依據(jù)，將具有足夠相似度的數(shù)據(jù)聚為一類，使得同一類簇內(nèi)數(shù)據(jù)的相似度盡量大，不同類簇間的數(shù)據(jù)相似度盡量小[3]。通過聚類分析，可以發(fā)現(xiàn)全部數(shù)據(jù)對象屬性的分布規(guī)律，明確數(shù)據(jù)的整體發(fā)展態(tài)勢。聚類算法[3-4]可以分為：基于劃分的方法，基于層次的方法，基于密度的方法，基于網(wǎng)格的方法，基于模型的方法?；趧澐址椒ǖ木垲愃惴ㄓ衚_means算法，k_medoids算法，clarans算法等[3-4]；基于層次的聚類算法有birch算法，cure算法，chameleon算法等[3-4]；基于密度的聚類算法有dbscan算法，optics算法[3-4]；基于網(wǎng)格的聚類算法有sting算法，clique算法，wave_cluster算法[3-4]。不同類型的聚類算法具有不同的應用條件，到目前為止，面對所有數(shù)據(jù)集，沒有哪一種算法能一直保持其優(yōu)點。為了解決這一問題，一些研究人員提出融合聚類的思想，融合不同的聚類算法，以便取長補短，達到更好的聚類效果。

聚類算法的研究主要集中在以下幾個方面：

1）強可伸縮性[5]：強可伸縮性是指聚類算法面對任何規(guī)模的數(shù)據(jù)集都應具有良好的聚類效果。

2）可處理高維數(shù)據(jù)集[6]：在現(xiàn)實生活中，數(shù)據(jù)一般都是高維的，使一些常用的相似度評判標準失去意義，導致數(shù)據(jù)無法聚類。故聚類算法應該具有處理高維數(shù)據(jù)集的解決方案。

3）對參數(shù)依賴性小[7]：在很多聚類算法中，需要指定一些參數(shù)來初始化算法，但面對未知的數(shù)據(jù)集，無法確定參數(shù)值，不能得到良好的聚類效果。故應減少參數(shù)的設定，提高魯棒性。

4）可過濾噪聲[8]：在現(xiàn)實生活中，數(shù)據(jù)的質(zhì)量是不高的，包含大量的孤立點，會嚴重影響聚類效果。故應過濾掉孤立點，保留有用數(shù)據(jù)，以便得到更好的聚類效果。

5）可處理任意形狀的簇[9]：在現(xiàn)實生活的數(shù)據(jù)集中，同種類型的數(shù)據(jù)按照簇狀分布，但是簇的形狀不一定是規(guī)則的。聚類算法不應只能處理某一種形狀的數(shù)據(jù)，應能處理任性形狀的簇。

6）可在分布式環(huán)境中運行[10]：傳統(tǒng)的聚類算法大多是處理集中式數(shù)據(jù)的，即要聚類的數(shù)據(jù)存儲在同一計算機或同一地點，但是隨著信息技術和網(wǎng)絡技術的不斷發(fā)展，大部分應用系統(tǒng)和數(shù)據(jù)是以分布式存在的。采用傳統(tǒng)的聚類算法會消耗大量存儲資源，降低聚類效果，故分布式聚類算法由此而生。 傳統(tǒng)式聚類算法在分布式環(huán)境中運行目前聚類算法的主要研究方向。

k_means聚類算法是1967年由Macqueen提出的，是聚類分析中最常用的一種典型的聚類算法，也是一種應用最廣泛的聚類算法[4]。其目標是根據(jù)數(shù)據(jù)某種相似性度量方法進行劃分，使每個數(shù)據(jù)到所屬類簇的中心的距離盡可能小，不同類簇間的距離盡可能大。由于該算法具有簡單，快速，高效和良好的搜索能力，并且適用于大數(shù)據(jù)集的優(yōu)點而被廣泛應用。主要缺點有：1）必須給定聚類數(shù)目k值[11]，k值不同可能導致不同的聚類結果；2）初始聚類中心[12-13]的選擇對聚類結果有很大的影響，易陷入局部最優(yōu)解；3）只能處理數(shù)值型數(shù)據(jù)，且對噪聲和孤立點[12]數(shù)據(jù)敏感；4）只對球狀數(shù)據(jù)具有良好的聚類效果，不能發(fā)現(xiàn)其他形狀的數(shù)據(jù)。

針對k_means算法存在的缺點，已經(jīng)有許多研究人員提出了一系列的改進方法。有人提出一種改進k_means算法[11]，此算法可以自確定聚類數(shù)目和初始聚類中心，改善了聚類結果，但對噪聲敏感，此外，該算法對分布較稀疏的數(shù)據(jù)集的聚類效果不理想。也有人提出了結合初始中心優(yōu)化和特征加權的K-Means聚類算法[12]，此算法根據(jù)樣本特征對聚類的貢獻程度獲得初始特征權重，構建一種加權距離度量，利用提出的初始聚類中心選擇方法獲得k個初始聚類中心，并結合初始特征權重進行初步聚類。此算法具有較高的聚類準確性，但需指定聚類數(shù)目k。有人提出了最小最大K-means聚類算法[13]，該算法通過大量的迭代工作來獲取全局最優(yōu)解。隨著現(xiàn)代互聯(lián)網(wǎng)技術的發(fā)展，海量數(shù)據(jù)以分布式形式存儲，傳統(tǒng)算法的應用出現(xiàn)障礙，分布式算法應運而生，稱為k_means算法的新的研究方向。

目前k_means算法的研究主要集中在以下幾個方面：

1）自確定聚類數(shù)目k；2）優(yōu)化初始聚類中心；3）可過濾噪聲；4）可處理任意形狀的簇；5）可處理高維數(shù)據(jù)集；6）可在分布式環(huán)境中運行。

本文提出了一種基于密度標準差優(yōu)化初始聚類中心的改進算法，此算法改變了初始聚類中心的選擇對聚類結果的影響，大大減少了迭代次數(shù)，提高了聚類精度，同時也不再只對球狀數(shù)據(jù)有良好的聚類效果，可發(fā)現(xiàn)多種形狀的簇，且對噪聲不敏感，可處理高維數(shù)據(jù)。本算法為提升k-means算法聚類結果提供了一種新的研究思路。在大數(shù)據(jù)和人工智能的時代，只有掌握數(shù)據(jù)處理的方法，才能在這個競爭激烈的社會下生存。同時此算法也為分布式的k-means算法提供了一種優(yōu)化初始聚類中心的解決方法。

2 傳統(tǒng)k-means算法

K-means算法的思想[14-15]是對給定的一個樣本數(shù)據(jù)的數(shù)據(jù)集[X=X1，X2，...，Xn]，并且每個Xi是d維的向量（d維向量由樣本數(shù)據(jù)的d個特征組成），在給定分類組數(shù)k（[k≤n]）值的條件下，將數(shù)據(jù)集X劃分成k個子集[S=S1，S2，...，Sk]，每個子集代表一個類，這k組子集應滿足以下條件：

傳統(tǒng)K-means算法步驟如下：

1）從數(shù)據(jù)集X中隨機選取k個數(shù)據(jù)對象作為初始聚類中心；

2）計算數(shù)據(jù)集中每個對象到k個聚類中心的距離，將數(shù)據(jù)劃分到與聚類中心距離最短的類中；

3）根據(jù)聚類結果，重新計算k個簇的聚類中心，計算方法是取簇中所有元素各自維度的算數(shù)平均數(shù)；

4）將X中全部元素按照新的中心重新聚類；

5）重復4，直到每個簇的中心基本不再變化；

6）將結果輸出。

3 基于密度標準差優(yōu)化初始聚類中心的k_means改進算法

3.1 基本定義

待聚類的數(shù)集[X=X1，X2，...，Xn]，其中[Xi=xi1，xi2，...，xid]，是實數(shù)空間[X∈Rd]中的向量，并且d表示數(shù)據(jù)的屬性數(shù)目（數(shù)據(jù)空間的維數(shù)）。

3.2 改進k_means算法

為了更準確的找到初始聚類中心，本文利用樣本點的標準差作為探尋半徑，依據(jù)樣本點的密度函數(shù)值尋找初始聚類中心。本文依據(jù)孤立點條件將待聚類的數(shù)集X分成兩部分，將滿足孤立點條件的點放入集合G，其余點放入集合Q，Q對應的密度函數(shù)值放入集合D。本文提出計算密度標準差，將大于密度標準差的密度函數(shù)值放入集合M，將介于密度標準差和孤立點密度的密度函數(shù)值放入集合P。這樣就降低了搜索范圍，減少了搜索時間，避免了選取到孤立點。改進算法思想如下：

算法 基于密度標準差優(yōu)化初始聚類中心的k_means算法

輸入 待聚類的數(shù)集X={X1，X2，…，Xn}，其中xi ={xi1，xi2， …，xid}；k簇的數(shù)目

輸出 k個初始聚類中心

步驟：

1）根據(jù)公式（1）（2）（3）計算數(shù)據(jù)對象之間的歐式距離，樣本的平均距離和樣本的標準差。

2）根據(jù)公式（4）（5）（6）計算樣本點的密度函數(shù)值，平均密度和密度標準差。

3）根據(jù)公式（7）將滿足孤立點條件的點放入集合G，其余點放入集合Q。

4）在Q中執(zhí)行（2），樣本點的密度函數(shù)值存入集合D，將大于密度標準差的密度函數(shù)值放入集合M。

5）找到M中密度函數(shù)最大值MAX在Q中對應的樣本點xi即為初始聚類中心。

6）將以初始聚類中心為圓心，樣本標準差為半徑的圓內(nèi)所有點的密度函數(shù)值賦為0。

7）重復（4）～（6）直到找到k個初始聚類中心。

3.3 孤立點的處理

本文將原始數(shù)據(jù)集分成兩部分，將滿足孤立點條件的點放入集合G，其余點放入集合Q；利用新提出的改進算法對集合Q進行聚類，得到各個類的初始聚類中心。孤立點不參與聚類，將歸為一類顯示。因為孤立點不參與聚類過程中的各種計算，所以不影響聚類中心的值，故本文新提出的改進算法對孤立點不敏感。

為了驗證本文改進算法對孤立點不敏感，測試數(shù)據(jù)有70個數(shù)據(jù)點，其中孤立點5個，約占總數(shù)的7%，用傳統(tǒng)k_means算法和本文改進的k_means算法進行測試，結果如下圖1和圖2所示。

圖2中五個黑色三角形的數(shù)據(jù)點是孤立點，而在圖1中可以看到五個點分別聚類到三個類中。圖1和圖2對比發(fā)現(xiàn)，有孤立點的聚類結果和無孤立點的聚類結果是不同的。

4 實驗結果分析

本文將傳統(tǒng)的k_means算法和基于密度標準差的k_means優(yōu)化算法進行了實驗對比，選擇了專用于測試數(shù)據(jù)挖掘算法的UCI數(shù)據(jù)庫[16]中的Iris數(shù)據(jù)集、Wine數(shù)據(jù)集和模擬實驗數(shù)據(jù)集作為本文測試數(shù)據(jù)集。

本文算法采用Python語言實現(xiàn)，測試環(huán)境是：CPU：Intel（R）Core?i5-2520 CPU @2.50 GHz；內(nèi)存： 4 GB；操作系統(tǒng)：Windows 10 64位；算法調(diào)試運行工具：PyCharm。

4.1 模擬實驗數(shù)據(jù)和結果分析

實驗使用的兩個數(shù)據(jù)集如圖3、圖4所示，數(shù)據(jù)集使用隨機數(shù)隨機生成如表1所示。分別在兩個數(shù)據(jù)集上運行傳統(tǒng)k_means算法和改進k_means算法，傳統(tǒng)k_means算法運行結果如圖5、圖6所示，改進k_means算法運行結果如圖7、圖8所示。

由此實驗可見，改進k_means算法不僅具有傳統(tǒng)k_means算法的優(yōu)點，還改善了傳統(tǒng)k_means算法對孤立點敏感，隨機選擇初始聚類中心易陷入局部最優(yōu)解的缺點。改進后的k_means算法不再只對球狀數(shù)據(jù)有較好的聚類效果，對密度不同的簇也有較好的聚類效果，可以大大改善數(shù)據(jù)量較大但稀疏的數(shù)據(jù)對象被分類到相鄰的數(shù)據(jù)量小但密集的簇中的情況，提高了聚類精度。

4.2 UCI實驗數(shù)據(jù)和結果分析

為了驗證本文提出的改進k_means算法的性能，本文用UCI數(shù)據(jù)集進行了測試。UCI數(shù)據(jù)集的名稱、屬性個數(shù)、數(shù)據(jù)對象數(shù)如表4所示。

因為本文提出的改進k_means算法根據(jù)密度標準差得到初始聚類中心，所以初始聚類中心是確定的，如果數(shù)據(jù)集確定，那么得到的聚類結果也是確定的。故只需進行一次實驗即可得到聚類結果。然而傳統(tǒng)k_means算法隨機生成初始聚類中心，故每次實驗結果都是不確定的。本實驗運行10次傳統(tǒng)k_means算法和一次改進k_means算法進行聚類結果的對比。運行10次傳統(tǒng)k_means算法的聚類結果如表5所示，可知，10次實驗中聚類精度相同的情況下，迭代次數(shù)和運行時間還是不同的。由此可以看出，傳統(tǒng)k_means算法是不穩(wěn)定的，初始聚類中心的選擇對聚類結果影響很大，尤其對迭代次數(shù)的影響是最大的。如果選擇好初始聚類中心，是明顯可以減少迭代次數(shù)的。

運行10次傳統(tǒng)k_means算法的聚類結果和運行1次改進k_means算法的聚類結果對比如表6所示。通過表6可知，改進k_means算法提高了聚類精度，且運行1次即可達到傳統(tǒng)k_means算法最好的聚類效果，改進算法的迭代次數(shù)小于傳統(tǒng)算法的迭代次數(shù)的平均值，雖然改進算法比傳統(tǒng)算法用時要多，但是改進算法運行1次即可達到最好的聚類效果。改進k_means算法用時較多的原因是尋找初始聚類中心時，對數(shù)據(jù)集進行了大量的運算，如求樣本均值、樣本標準差密度函數(shù)值、平均密度、密度標準差。

5 結束語

本文提出的基于密度標準差優(yōu)化初始聚類中心的改進k_means算法更好的確定了初始聚類中心，避免了隨機選取聚類中心，提高了聚類精度，減少了迭代次數(shù)，有效避免了傳統(tǒng)k_means算法易陷入局部最優(yōu)解的情況，減少了孤立點對初始聚類中心的影響。本文的目的是提供一種優(yōu)化初始聚類中心的方法，為聚類算法添磚加瓦，以便得到更準確的聚類結果。本改進算法的缺點是：1）需指定k值。2）耗時較多，由于此改進算法需進行大量的計算，故花費的時間較多一些。3）隨著需要聚類的數(shù)據(jù)量的不斷增大，計算機的計算性能要更好。下一步要做的工作是尋找確定k值的方法，并改善數(shù)據(jù)存儲的方式以降低時間的消耗。

參考文獻：

[1] Han J and Kimber M.數(shù)據(jù)挖掘概念與技術[M]. 范明，孟小峰，等.譯.北京：機械工業(yè)出版社，2001.

[2] Bing Liu著.余勇，薛貴榮等譯.Web數(shù)據(jù)挖掘[M].2版.北京：清華大學出版社，2013.

[3] 李碩.聚類算法的研究與改進[D].北京：北京郵電大學，2017.

[4] 李薈嬈. K-means聚類方法的改進及其應用[D].黑龍江哈爾濱：東北農(nóng)業(yè)大學，2014.

[5] Chaudhuri D， Chaudhuri B. A novel multispeed nonhierarchical data clustering technique [J]. IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics a Publication of the IEEE Systems Man & Cybernetics Society， 1997，27（5）：71-876.

[6] Faber V. Clustering and the continuous K-means algorithm[J].Los Alamos Science， 1994（22）：138-144.

[7] Dan P， Moore A. Accelerating Exact k-means Algorithms with Geometric Reasoning [A]. // ACM SIGKDD International Conference on Knowledge Discovery & Data Mining [C]， New York： ACM Press， 1999：277-281.

[8] Wu X， Yao C. Application of improved K-means clustering algorithm in transit data collection [A]. // International Conference on Biomedical Engineering and Informatics[C]， New York： IEEE， 2010：3028-3030.

[9] 王莉.數(shù)據(jù)挖掘中聚類方法的研究[D].天津：天津大學，2004.

[10] 毛銳.基于密度的分布式聚類算法的研究[D].吉林長春：吉林大學，2012.

[11] 賈瑞玉，李玉功. 類簇數(shù)目和初始中心點自確定的K_means算法[J]. 計算機工程與應用，2018，54（7） ：152-158.

[12] 王宏杰，師彥文. 結合初始中心優(yōu)化和特征加權的K-Means聚類算法[J]. 計算機科學，2017，44（11） ：457-459.

[13] Zhu M， Wang W， Huang J. Improved initial cluster center selection in K-means clustering[J].Engineering Computations，2014，31（8）：1661一1667.

[14] Tzortzis G， Likas A. The Min Max K-means clustering algorithm [J].Pattern Recognition， 2014， 47 （7）： 2505-2516.

[15] Lai J Z C， Huang T J. Fast global k-means clustering using cluster membership and inequality [J].Pattern Recognition， 2010， 43（5）：1954-1963.

[16] Asuncion A，Newman D J.UCI machine learning repository [EB/OL]. [2018-3-23]. http：//archive.ics.uci.edu/ml/index.php

【通聯(lián)編輯：唐一東】