基于加權處罰的K-均值優化算法

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

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

數據挖掘（Data Mining）［1］就是從一些大量的、模糊的數據中，獲取未知的、潛在有用的信息和知識的過程。聚類分析［2］在數據挖掘領域的應用最為廣泛。聚類［3］屬于一種無監督的機器學習算法，通過獲取數據的內在屬性，實現對數據的分類或壓縮，使得同一類中的對象之間彼此相似，不同類中的對象之間彼此相異［4，5］。

聚類分析廣泛應用于許多研究領域，如模式識別、數據挖掘、圖像處理、市場研究、數據分析等。對于不同的問題和用戶，國內外學者研究出許多具有代表性的聚類算法，大致分為基于層次的方法、基于劃分的方法、基于網格的方法、基于密度的方法等［6］。基于層次的方法使用兩種遞歸方式把數據對象構造成一棵聚類樹，第一種是以從下到上的合并方式進行遞歸，第二種是以從上到下的分裂方式進行遞歸，該方法的聚類結果受合并和分裂操作的影響，一旦一組數據對象被合并或分裂，下一步的操作將在此基礎上進行，不能進行修改。基于網格的方法把數據空間劃分為有限個網格單元，以每個網格單元為處理對象，該方法比較粗放，影響聚類質量。基于密度的方法把密集區域定義為密度高于給定閾值的區域，對這些密集區域進行連接形成目標類簇，這種方法的聚類結果受閾值影響較大，處理每個樣本時可能需要掃描整個數據庫，引起大量的I/O操作。基于劃分的方法把數據空間劃分成不同的區域，每個區域表示一個數據類，計算量小，時間消耗與樣本個數呈線性關系。

K-均值［7，8］是基于劃分方法的代表算法，使用誤差平方和SSE（Sum of the Squared Error）作為目標函數測度聚類質量，屬于最小化SSE的聚類問題。K-均值算法思想簡單，易于實現，其實現版本廣泛應用于數據挖掘工具包中，可以通過修改算法的初始化、相似性度量、算法終止條件等部分適應新的應用環境，應用領域廣泛。K-均值算法對初始聚類中心比較敏感，不同的初始聚類中心對應不同準確率的聚類結果，且得到的聚類結果不穩定易陷入局部最優。因此，怎樣使K-均值算法對初始聚類中心不敏感，得到準確率高、波動性小的聚類結果，具有重要的研究意義。

為了消除初始聚類中心對K-均值算法的影響，可以通過選擇不同的初始聚類中心多次執行K-均值算法，然后選擇最好的聚類結果。顯然，若選擇初始聚類中心的次數較少，則不能保證得到全局最優解，若選擇初始聚類中心的次數較多，則算法計算量較大，不適用于大數據集聚類。許多研究者對于此問題提出改進算法。例如Bradley P S等人在數據集中隨機選擇多個樣本子集，在這些樣本子集中執行K-均值算法，最后挑選出較優的初始聚類中心，對整個數據集進行聚類，但是該方法受樣本子集選取方法的影響，聚類結果僅收斂到局部最優。一些研究者在挑選初始聚類中心時，引入隨機算法的思想。例如CLARANS算法，通過隨機選取多個初始聚類中心，比較得到的局部極小值，選出全局最優解。Likas等人使用增量的方式選取初始聚類中心，通過求解一系列子聚類的問題來解決K個聚類的問題，使用局部搜索能力得到全局優化的聚類結果，具體步驟是：首先從實現一個聚類的問題開始，選取數據集的質心作為第一個初始聚類中心，設置K=1，在此基礎上，實現兩個聚類的問題，設置K=2，K=1時的聚類中心默認為K=2時的第一個聚類中心，迭代地讓剩余樣本假設為第二個初始聚類中心，運行K-均值算法，選擇目標函數SSE最小時對應的樣本作為K=2時的第二個聚類中心，重復該過程直到找出K個聚類中心。該算法可以得到全局優化的聚類結果，但是計算量太大，不適用于大數據集聚類。仝雪姣等人［9］利用貪心思想根據數據的實際分布構建K個數據集合，計算K個數據集合的均值作為初始聚類中心，使得到的初始聚類中心接近算法期待的聚類中心。

對于K-均值初始聚類中心選取方法的研究已有大量的研究成果，但是沒有出現公認最好的初始聚類中心選取方法。當數據集中存在噪音和孤立點時，已有的方法很難選出合適的初始聚類中心。

K-均值算法的終止條件是目標準則函數達到最小值。因初試聚類中心對K-均值算法的影響，對數據集劃分形成的簇集中，有些簇的誤差平方和較大，有些簇的誤差平方和較小。此時，通過誤差平方和較小的簇抵消誤差平方和較大的簇的影響，可以使所有簇的誤差平方和的累加和最小。因此，K-均值算法會把不屬于同一類簇的樣本劃分到同一類簇中，使聚類結果偏離數據集的真實分布。每次迭代過程中，K-均值算法沒有考慮到各個簇之間誤差平方和的差異性，算法結束時，簇集中可能會存在平均誤差較大的簇，即該簇中包含的樣本屬于兩類或兩類以上。為此，本文使用加權方案限制簇集中出現平均誤差較大的簇，解決K-均值算法對初始聚類中心敏感的問題，得到全局優化的聚類結果。

1 基于加權處罰的K-均值優化算法

1.1 K-均值算法

K-均值算法是一種已知聚類個數的“無監督學習”算法。首先指定表示聚類個數的K值，然后對數據集聚類，算法結束時用K個聚類中心表示聚類結果。對于設定的目標準則函數，通過向目標準則函數值減小的方向進行迭代更新，目標準則函數值達到極小值時算法結束，得到較優的聚類結果。

定義目標準則函數為：

其中||Ci表示Ci類包含樣本的個數，使用歐式距離

度量樣本間的相似性。歐式距離適用于類內數據對象符合超球形分布的情況，目標準則函數SSE表示為每個數據對象到相應聚類中心距離的平方和，即聚類均方誤差的最小值。

K-均值算法的流程如下：

（1）隨機選取K個初始聚類中心V1,V2,...,Vk；

（2）按照最小距離原則，對數據集聚類，確定每個樣本的類屬關系；

（3）使用公式（1）更新K個簇的中心；

（4）重復執行（2）到（4），直到目標準則函數收斂或聚類中心穩定。

顯然，初始聚類中心對K-均值算法產生很大的影響，簇集中易存在平均誤差較大的簇，聚類結果僅能收斂到局部最優。即使選取不同的初始聚類中心執行多次K-均值算法，也只是在龐大的初值空間里進行簡單的搜索，聚類結果很難達到全局最優。當數據集中存在較多噪音或孤立點時，已有的初始聚類中心優化方法很難發現合適的初始聚類中心。

1.2 基于加權處罰的K-均值優化算法

1.2.1 算法思想

由于初始聚類中心對K-均值算法的影響，聚類結果中易存在平均誤差較大的簇，即簇中包含的數據對象屬于兩類或兩類以上，聚類結果僅是局部最優。為此，在每次迭代過程中，使用加權方案對平均誤差較大的簇進行處罰，給平均誤差較大的簇賦予較大的權值，給平均誤差較小的簇賦予較小的權值。定義處罰因子，控制對簇的處罰力度。定義加權準則函數，分配樣本時，計算加權距離，把樣本分到加權距離最小的簇中。這樣，平均誤差較大的簇將會失去一些距離簇心較遠的實例，即把不屬于該簇的樣本劃分到正確的簇中，平均誤差較小的簇將會獲得一些距離簇心較遠但屬于該簇的實例。每次迭代更新簇的權值時，引入記憶因子，控制上次迭代的權值對當前更新的權值的影響，提高算法的穩定性。以期使每次迭代過程中，都能對數據集做出正確的劃分，進而使最終的聚類結果收斂到全局最優。

1.2.2 相關概念

定義3為了提高算法的穩定性，在權值更新過程中添加記憶因子。設第t-1次迭代時簇S的權值為，那么添加記憶因子后，我們定義第t次迭代時簇S的權值為：

其中α是記憶因子，0≤α≤1，控制上次迭代的權值對當前更新的權值的影響。本文使用公式（6）更新每個簇的權值。

若連續兩次迭代過程中，加權準則函數值的變化量小于給定的閾值ξ，則算法結束。

1.2.3 算法偽代碼描述

2 結果與討論

實驗目的測試本文算法的聚類性能、抗噪性能及伸縮性。分別使用UCI機器學習數據庫中的數據集，隨機生成的不同規模的含有不同比例噪音的人工模擬數據集進行實驗。分別使用不同記憶因子α=0下的本文算法1、α=0.2下的本文算法2、α=0.4下的本文算法3與K-均值算法、文獻［9］中的算法進行實驗比較。實驗環境是Intel CPU，2.99G內存，931G硬盤，Windows XP操作系統，Visual Studio2013應用軟件，C++作為編程語言。使用聚類誤差平方和、聚類準確率，以及常用的外部評價指標Adjusted Rand Index參數對算法的性能進行評價。外部評價指標是已知分類信息的前提下對聚類結果進行評價。Adjusted Rand Index參數，用來衡量聚類結果與數據的外部標準類之間的一致程度，是Rand指數的一個變種。

2.1 UCI數據集實驗

使用UCI機器學習數據庫中的數據集測試算法的聚類性能，數據集描述如表1所示。分別運行不同記憶因子α=0下的本文算法1、α=0.2下的本文算法2、α=0.4下的本文算法3與K-均值算法、文獻［9］中的算法各100次，比較算法的平均聚類結果。表2給出了算法的聚類誤差平方和的比較結果。圖1給出了算法的聚類準確率與Adjusted Rand Index參數的比較結果。

表1 UCI數據集描述

表2 UCI數據集上算法的聚類誤差平方和的比較結果

圖1 UCI數據集上算法的聚類準確率與Adjusted Rand Index參數的比較

由表2可知，K-均值算法的聚類誤差平方和在數據集A4（WDBC）、A5（Pima Indians Diabetes）上最優，本文算法在數據集A4、A5上的聚類誤差平方和明顯優于K-均值算法。文獻［9］算法的聚類誤差平方和在數據集A2（Iris）上最優，數據集A2上α=0.2下的本文算法的聚類誤差平方和優于文獻［9］算法。

圖1中關于聚類準確率的比較結果可知，在所有數據集上本文算法的聚類準確率均高于K-均值算法。在數據集A2（Iris）上，文獻［9］算法的聚類準確率略高（α=0，α=0.4）下的本文算法，其它數據集上均低于本文算法。圖1中關于評價指標Adjusted Rand Index參數的比較結果可知，本文算法的聚類效果最好。

上述UCI數據集的實驗結果表明，本文算法優于K-均值算法和優化初試聚類中心的K-均值算法，改善了K-均值算法的聚類性能，且提高了算法的伸縮性。

2.2 人工模擬數據集實驗

為了測試本文算法對含有噪音數據的聚類能力，隨機生成兩組分別含有10%、15%、20%、25%、30%噪音的二維人工模擬數據集對算法進行測試。這兩組人工模擬數據集中的樣本均符合正態分布。第一組數據集包含4個類簇，樣本集的規模為600。該組數據集按噪音比例由小到大排列分別為D1、D2、D3、D4、D5。第二組數據集包含6個類簇，樣本集的規模為8400。該組數據集按噪音比例由小到大排列分別為S1、S2、S3、S4、S5。在10個人工模擬數據集上分別運行不同記憶因子α=0下的本文算法1、α=0.2下的本文算法2、α=0.4下的本文算法3與K-均值算法、文獻［9］的算法各100次，比較平均聚類結果。表3給出了算法的聚類誤差平方和的比較結果。圖2是算法的聚類準確率與Adjusted Rand Index參數的比較結果。

表3 人工模擬數據集上算法的聚類誤差平方和的比較結果

圖2 模擬數據集上算法的聚類準確率與Adjusted Rand Index參數的比較

由表3可知，在隨機生成的大小規模數據集上，本文算法的聚類誤差平方和均低于K-均值算法和文獻［9］算法。由圖2可知，在隨機生成的大小規模數據集上，本文算法的聚類準確率和Adjusted Rand Index參數最優。

上述人工模擬數據集的實驗結果表明，本文算法在含有噪音的數據集上的聚類結果，準確率高且穩定，證明本文算法具有較強的抗噪性能。

3 結論

本文針對K-均值算法易受初始聚類中心影響的問題。每次迭代過程中，使用加權方案對平均誤差較大的簇進行處罰，限制簇集中出現平均誤差較大的聚簇。對數據集做出正確的劃分，使聚類結果收斂到全局最優。通過UCI數據庫中的數據集與人工模擬數據集的實驗測試表明，本文算法具有較好的聚類性能及伸縮性，且具有較強的抗噪性能。

［1］張俊溪，吳曉軍.一種新的基于進化計算的聚類算法［J］.計算機工程與應用，2011，4（24）：111-114.

［2］HanJiawei，KamberM.DataMining：Concepts and Techniques［M］.Beijing：China Machine Press，2011.

［3］張赤，豐洪才，金凱，等.基于聚類分析的缺失數據最近鄰填補算法［J］.計算機應用與件，2014，31（5）：282-284.

［4］Yu H，Li Z，Yao N.Research on optimization method for K-Means clustering algorithm［J］.Journal of Chinese Computer Systems，2012，33（10）：2273-2277.

［5］韓忠明，陳妮，張慧，等.一種非對稱距離下的層次聚類算法［J］.模式識別與人工智能，2014，27（5）：410-416.

［6］黃德才，李曉暢.基于相對密度的混合屬性數據增量聚類算法［J］.控制與策，2013，28（6）：815-822.

［7］傅德勝，周辰.基于密度的改進K均值算法及實現［J］.計算機應用，2011，31（2）：432-434.

［8］楊志，羅可.一種改進的基于粒子群的聚類算法［J］.計算機應用研究，2014，31（9）：2597-2600.

［9］仝雪姣，孟凡榮，王志曉.對K-means初始聚類中心的優化［J］.計算機工程與設計，2011，32（8）：2721-2724.