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

黃靈 王云鋒 陳光武

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 傳統k-means算法

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

傳統K-means算法步驟如下：

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

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

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

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

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

6）將結果輸出。

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

3.1 基本定義

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

3.2 改進k_means算法

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

算法 基于密度標準差優化初始聚類中心的k_means算法

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

輸出 k個初始聚類中心

步驟：

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

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

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

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

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

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

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

3.3 孤立點的處理

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

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

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

4 實驗結果分析

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

本文算法采用Python語言實現，測試環境是：CPU：Intel（R）Core?i5-2520 CPU @2.50 GHz；內存： 4 GB；操作系統：Windows 10 64位；算法調試運行工具：PyCharm。

4.1 模擬實驗數據和結果分析

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

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

4.2 UCI實驗數據和結果分析

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

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

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

5 結束語

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

參考文獻：

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

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

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

[4] 李薈嬈. K-means聚類方法的改進及其應用[D].黑龍江哈爾濱：東北農業大學，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] 王莉.數據挖掘中聚類方法的研究[D].天津：天津大學，2004.

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

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

[12] 王宏杰，師彥文. 結合初始中心優化和特征加權的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

【通聯編輯：唐一東】