一種高效的全局K-均值算法

梁鮮，曲福恒，楊勇，才華

（1.長春理工大學 計算機科學技術學院，長春 130022；2.長春理工大學 電子信息工程學院，長春 130022）

聚類［1］分析是一種無先驗知識的機器學習過程，是數據挖掘一個重要的分支，遵循同一個集合中的樣本相似性最大，不同集合中的樣本相異性最大的理念［2］，把樣本集分為若干個集合，每個集合稱為一個聚簇。已有的經典聚類算法大致可分為五種：基于層次的、基于劃分的、基于密度的、基于網格的和基于模型的。K-均值是一種基于劃分的聚類算法，因效率高，處理速度快等特點，適合對大數據集聚類。K-均值算法選擇初始聚類中心的隨機性，使聚類結果因不同初始聚類中心和不同初始數據輸入順序的影響而波動，聚類結果僅能收斂到局部最優。

針對K-均值算法的不足，很多學者提出一系列改進算法。Grigorios Tzortzis選取相距最遠的樣本作為前兩個初始聚類中心，按照最小最大原則選取下一個聚類中心，保證每次選擇的聚類中心距已有聚類中心較遠，得到正確的初始聚類中心；Kong Dexi把核函數引入到K-均值算法中，把數據映射到高維空間（或核空間），在高維空間中使用K-均值對數據聚類，使用正定核（CPD）提高算法效率；Hassanzadeh提出螢火蟲算法和K-均值結合的算法，對數據集細化，找到子數據集的質心，提高算法的精度和性能；但是這些算法沒有得到廣泛的認可，Likas A等人在2003年提出全局K-均值算法［6］增量選擇初始聚類中心，得到全局最優的聚類結果，但算法時間復雜度大，不適合對大數據集聚類。本文提出全局K-均值的改進算法，在不影響聚類效果的基礎上，減少聚類時間。

1 K-均值

K-均值算法相關描述［7］：設樣本集X={xi|i=1,2,...,N}，K個類別為Cj（j=1,2,...,K），K個聚類中心為Aj（j=1,2,...,K）。

樣本間的歐式距離公式：

聚簇中心：

誤差平方準則函數：

K-均值算法流程圖如圖1所示。

圖1 K-均值算法流程圖

2 全局K-均值

全局K-均值算法通過求解一系列子聚類問題來解決K個聚簇的問題。該算法使用K-均值算法局域搜索的能力得到全局優化的聚類結果。為了克服初始值敏感的問題，該算法通過每一次傳統K-均值算法找出一個最佳聚簇中心，直到找出K個聚簇中心。該算法具體步驟是：首先從實現一個聚簇的聚類問題開始，設置K=1，即先找到第一個聚簇的最佳質心。在這個基礎上，實現兩個聚簇的聚類問題，設置K=2，找到的K=1的聚簇質心默認為K=2時的一個最佳聚簇中心，迭代地讓剩余樣本假設為第二個聚簇中心，然后運行K-均值算法，找到誤差平方準則函數最小時對應的樣本作為另一個最佳聚簇中心，重復該過程，直到找到K個最佳聚簇中心。算法描述如下：

（1）初始化：計算所有樣本的均值當做第一個最佳聚簇中心，設置 t=1；

（2）結束條件：t=t+1，當t＞K時，算法終止；

（3）查找下一個最佳聚簇中心：前t-1個最佳聚簇中心為m1，m2，...，mt-1迭代地讓剩余樣本作為最佳聚簇中心，運行K-均值算法，找到誤差平方準則函數最小時對應的樣本作為第t個最佳聚簇中心，即K=t的最佳聚簇中心為b1,b2,...,bt；

（4）讓 mj=bj,j=1,2,...,t，轉到（2）。

3 快速全局K-均值

全局K-均值算法可以得到較好的聚類結果，但是計算量太大。Likas等人對全局K-均值算法進行改進，得到快速全局K-均值算法，該算法通過計算bn，選擇bn最大時對應的樣本作為最佳聚簇中心，進而減少計算量。

bn的定義如：

4 一種高效的全局K-均值算法

針對全局K-均值算法時間復雜度大的問題，提出改進算法，繼承全局K-均值算法增量選擇初始聚簇中心的思想，定義目標函數：

選擇正確的初始聚類中心，減少迭代次數，降低時間復雜度。定義目標函數：

選擇數據集中周圍分布最密集的樣本作為第一個初始聚類中心，選擇使目標函數：

取最小值的樣本（距離已有聚類中心遠，形成的子簇包含樣本個數多并且凝聚度小），作為下一個聚類中心，直到選出K個最佳聚類中心。實驗證明算法在不影響聚類性能的基礎上減小聚類時間。

問題描述：把樣本集合A=（a1,a2,...,an）劃分K個聚簇，使誤差平方準則函數E最小，該算法使用歐式距離度量兩個樣本的相似度。

算法描述：

（1）計算

其中，i=1，2，...，n。

最終M的取值對應的樣本作為第一個最佳聚簇中心，設置w=1；

（2）另w=w+1，如果簇的個數w＞K，該算法結束，轉到Step4；

（3）選取下一個聚簇中心，對剩余樣本，計算

其中，Di是樣本ai為聚簇中心形成的子簇中樣本到簇心的距離之和，Ni是子簇中樣本個數，di是ai到已有最佳聚簇中心的距離和，Fi最小時對應的樣本ai作為下一個最佳聚簇中心，轉到Step2；

（4）用得到的K個聚簇中心作為K-均值算法的初始聚簇中心，按照就近原則分配樣本到距離最近的簇中，分配完畢，更新聚簇中心，直到目標函數收斂。

5 實驗結果分析

實驗目的是證明改進算法的性能。硬件運行環境是Intel CPU，2.99G內存，931G硬盤；軟件運行環境是WindowsXP操作統，Visual Studio 2013開發平臺，算法使用C++作為編程語言。

選用Segmentation數據集、pixel averages數據集和Pendigits數據集作為測試數據集，在測試數據集上分別運行10次改進算法、全局K-均值算法、快速全局K-均值算法、K-Means++和Pifs K-均值算法，對測試數據集聚類個數分別為3、4、5、6、7、8、9、10比較平均聚類結果。測試數據集描述如表1所示，算法在Segmentation數據集上平均聚類誤差比較如圖2所示，平均聚類時間比較如圖3所示，算法在pixel averages數據集上平均聚類誤差比較如圖4所示，平均聚類時間比較如圖5所示，算法在Pendigits數據集上平均聚類誤差比較如圖6所示，平均聚類時間比較如圖7所示。

表1 測試數據集的描述

圖2 Segmentation測試數據集上聚類誤差比較

圖3 Segmentation測試數據集上聚類時間比較

圖4 pixel averages測試數據集上聚類誤差比較

圖5 在pixel averages測試數據集上聚類時間比較

圖6 Pendigits測試數據集上聚類誤差比較

圖7 在Pendigits測試數據集上聚類時間比較

由圖2、圖4和圖6可知，改進算法與全局K-均值算法、快速全局K-均值算法相比，不影響聚類誤差，與K-Means++和Pifs K-均值相比，聚類誤差小，聚類效果更好。由圖3、5和7可知，改進算法相比全局K-均值算法、快速全局K-均值算法減小了聚類時間，聚類個數為正確值時，聚類時間減小量最大，在Segmentation和Pendigits數據集上，改進算法的聚類時間大于K-Means++算法，相比Pifs K-均值算法時間復雜度小。實驗證明，改進算法可以得到更好的聚類結果，與全局K-均值算法、快速全局K-均值算法相比，降低了時間復雜度，與優化初始聚類中心的其它K-均值算法相比，得到更好的聚類效果，聚類時間上也有一定的優勢，證明改進算法是可行的。

6 結束語

為了解決全局K-均值算法時間復雜度大的問題，定義新的目標函數，選擇最小化目標函數貢獻大，并且和已有聚類中心距離遠的樣本作為下一個聚類中心，選擇周圍分布較密集的樣本作為第一個初始聚類中心，得到一種高效的全局K-均值算法。實驗證明，改進算法相比全局K-均值算法、快速全局K-均值算法，在不影響聚類效果的基礎上，降低了時間復雜度，與優化初始聚類中心的其它K-均值算法的比較結果表明，改進算法選取正確的初始聚類中心，得到更好的聚類效果，聚類時間上也有一定的優勢。

［1］Yukio Ohsawa，Katsutoshi Yada.Data mining for design and marketing［M］.CRC Rress，2009.

［2］Aswani K C，Srinivas S.Concept lattice reduction using fuzzy K-means clustering［J］.Expert System with Application，2010，37（3）：2696-2704.

［3］Grigorios Tzortzis，Aristidis Likas.The min max K-means clustering algorithm［J］.Pattern Recognition，2014：47（2）：2505-2516.

［4］Kong Dexi，Kong Rui.A fast and effective kernel based K-Means clustering Algorithm［C］.IEEE Intelligent Systems，2013：58-61.

［5］Hassanzadeh T，Meybodi，M R.A new hybrid approach fordata clustering using firefly algorithm and K-means［C］.IEEE Intelligent Systems，2012：7-11.

［6］Likas A，Vlassis M，Verbeek J.The global K-means clustering algorothm［J］.Pattern Recognition，2003，36（2）：451-461.

［7］Erisoglu M，Calis N，Sakallioglu S.A new algorithm for initial cluster centers in K-means algorithm.Pattern Recognition Letters，2011（32）：1701-1705.