K-means 聚類算法研究綜述

王 森，劉 琛，邢帥杰

（華東交通大學理學院，江西 南昌 330013）

隨著計算機和網(wǎng)絡技術的日益成熟， 大數(shù)據(jù)時代快速發(fā)展，每時每刻都在產(chǎn)生大量的數(shù)據(jù)信息，并且越來越復雜。 而聚類分析是數(shù)據(jù)挖掘中數(shù)據(jù)劃分和數(shù)據(jù)分組的重要方法， 一直以來受到眾多研究者的關注，在生物學和醫(yī)學[1-4]、市場營銷[5-6]、文本分類[7]、機器學習[8-11]等各個領域得到廣泛應用。

聚類算法是一種區(qū)別于分類的無監(jiān)督學習算法，即對無標簽的樣本點根據(jù)數(shù)據(jù)及數(shù)據(jù)間的信息關系，對數(shù)據(jù)對象進行分組。 聚類的最終目的使組內的對象之間相似，不同組中的對象之間有區(qū)別[12]。組內的樣本點相似性越大，組間相似性越小，則聚類效果越好。 目前廣泛研究的聚類算法大致可以分為以下幾類：基于層次的聚類，基于密度的聚類，基于原型的聚類，基于劃分的聚類。

劃分聚類是將數(shù)據(jù)集劃分成不重疊的子簇，使得最終每個數(shù)據(jù)點恰好位于一個子簇中，而且各個子簇的并恰是整個數(shù)據(jù)集，經(jīng)典算法有K-means 算法，AP 算法。 層次聚類是嵌套簇的集族，組織成一棵樹。 除去葉節(jié)點外，樹中每一個結點（簇）都是其子簇的并，樹根則是包含所有對象的簇，其中聚類樹的構建分為凝聚的層次聚類和分裂的層次聚類，經(jīng)典算法有AGNES 算法，DIANA 算法。基于密度的聚類則是通過尋找被低密度區(qū)域所分離的高密度區(qū)域的方法而進行的聚類， 算法有DBSCAN 算法，DPC 算法。

K-means 算法最早是由Mac[13]于1967 年提出，是非常經(jīng)典的算法，目前仍是非常流行的“十大算法”之一。 該算法由于其原理簡單、效率高而被人們廣泛使用， 但是聚類結果也易受其他因素的影響，例如K 值的確定，離群點，初始聚類中心的選取，隨意選取不同的點作為初始聚類中心將會導致不同的聚類結果，甚至可能陷入局部最優(yōu)。

首先， 概述K-means 算法的基本思想原理；其次， 分別對關于初始聚類中心的選取、K 值的確定和離群點三方面的改進算法進行基于密度和距離方面的分類總結，分析各個改進算法的優(yōu)缺點；最后，展望K-means 算法在未來的研究方向和發(fā)展趨勢。

1 傳統(tǒng)K-means 聚類算法

1.1 K-means 算法基本思想

K-means 聚類算法是一種簡單的迭代性聚類算法， 是對一個n 維向量的數(shù)據(jù)點集D={xi|i=1，···，N}進行聚類，其中xi表示第i 個數(shù)據(jù)點，最終將集合D 劃分成k 個類簇。分組的依據(jù)主要是“緊密度”或者“相似度”，組內對象越相似、組間差距越大越好[14]。 距離的度量有歐幾里得距離、曼哈頓距離和切比雪夫距離， 聚類算法通常用歐氏距離作為相似性度量， 以誤差平方和 （sum of squared error, SSE）作為度量聚類質量的目標函數(shù)，通過最小化目標函數(shù)， 將數(shù)據(jù)點按照距離聚類中心的遠近分成k 個簇。

定義1數(shù)據(jù)點之間的歐幾里得距離

定義2數(shù)據(jù)點與聚類中心ci間的歐幾里得距離公式

式中：ci為第i 個類簇的聚類中心；x 為數(shù)據(jù)集D 中的數(shù)據(jù)對象。

定義3誤差平方和SSE 計算公式

式中：Ci為第i 個類簇；ci為簇Ci的聚類中心；x 為數(shù)據(jù)集D 中的數(shù)據(jù)對象；k 為類簇數(shù)目。

K-means 聚類算法是一種動態(tài)聚類算法，需要進行不斷重復迭代。 該算法的基本思想原理是：選擇K 個數(shù)據(jù)作初始聚類中心，其中K 為用戶指定的類簇個數(shù)。 計算數(shù)據(jù)點到各個初始聚類中心的距離，將數(shù)據(jù)點就近分配到各個初始聚類中心所在的集合中形成一個簇。 根據(jù)簇中的各個點，更新每個簇的中心。 重復分配和更新的步驟，直到簇不在發(fā)生變化，或者目標函數(shù)滿足條件即可。

2 K-means 算法的改進

2.1 初始聚類中心的選取

K-means 算法中， 初始聚類中心點的選取對聚類結果的影響非常大， 對于不同的初始聚類中心，最終的聚類的結果往往不同，所以K-means 聚類算法的穩(wěn)定性較差， 并且聚類中心的選擇會導致出現(xiàn)聚類結果陷入局部最優(yōu)的問題。 目前針對初始聚類中心的選擇的改進研究主要從密度和距離兩個方面入手。

2.1.1 基于密度

目前眾多學者提出基于密度的K-means 算法改進方案，主要依據(jù)數(shù)據(jù)集中數(shù)據(jù)點的密度分布來選取， 避免由于隨機選取的初始聚類中心過于密集，導致聚類陷入局部最優(yōu)的情況。

蔡宇浩等[15]提出了WLV-K-means 算法，通過對局部方差進行加權來優(yōu)化初始聚類中心。 方差表示了數(shù)據(jù)的離散程度，方差越小則離散程度越小，密度越大。該算法首先計算樣本數(shù)據(jù)的鄰域半徑θ和鄰域內部的樣本數(shù)據(jù)到樣本中心的方差， 以加權的局部方差為新的密度度量。 再對各個樣本的加權局部方差進行排序， 將加權局部方差最小即密度最大的數(shù)據(jù)點作為第一個初始聚類中心。 最后利用改進的最大最小法， 即對加權局部方差作倒數(shù)作為密度系數(shù)對最大最小值進行加權， 進而找到各個初始聚類中心。WLV-K-means 算法的優(yōu)點在于引入加權局部方差，提升了計算的準確性，減少了噪聲點對聚類效果的影響， 但同時增加了算法時間復雜度和空間復雜度， 針對數(shù)據(jù)集中樣本的數(shù)目和分布不同，對應的最優(yōu)半徑調節(jié)參數(shù)θ也不同，需要多次調節(jié)尋找合適的調節(jié)參數(shù)值。 薛印璽等[16]提出基于樣本密度的全局優(yōu)化K 均值聚類算法KMS-GOSD 算法，該算法通過高斯模型得到迭代初始所有聚類中心的預估計密度， 在更新聚類中心迭代過程中加入偏移操作， 引入衰減因子Ra=（m-1）/m，其中m 為最大的迭代次數(shù)，以此逐步降低預估計密度，加速偏移收斂，通過比較實際密度和逐漸減小的預估計密度， 得到密度較高的聚類中心。 KMS-GOSD 算法極大地避免了質心作為聚類中心時陷入局部最優(yōu)的可能， 降低了算法復雜度， 并且增強了聚類中心點對全局的探索能力，具有較高的準確率和穩(wěn)定性。

2.1.2 基于距離

目前， 有學者基于歐氏距離提出相異度概念，通過構造相異度矩陣進而判斷數(shù)據(jù)樣本點之間的差異，并借此判斷數(shù)據(jù)樣本點能否作為初始聚類中心。 孟子健等[17]定義了兩個數(shù)據(jù)點間的第k 個屬性的相異度且對數(shù)據(jù)進行了標準化處理

式中：xik和xjk分別為數(shù)據(jù)點xi和xj的第k 個屬性值；xRk為D 中所有數(shù)據(jù)點的第k 個屬性的所有取值。 并由此給出了兩數(shù)據(jù)點間的相異度公式

式中：N 為數(shù)據(jù)的維數(shù)。

進而構造相異度矩陣

又定義了樣本的平均相異度

對于給定的數(shù)據(jù)點x0，通過計算點x0的相異度參數(shù)N（x0，）即以x0為中心，以為半徑的區(qū)域內點的個數(shù)

數(shù)據(jù)點x0的相異度參數(shù)N（x0，r）越大，數(shù)據(jù)點x0的鄰域內的點越多，則x0更有可能為某一簇的初始聚類中心。

計算數(shù)據(jù)集D 中的每個數(shù)據(jù)點的相異度參數(shù)，并組成一相異度參數(shù)集合M，從集合M 中找出最大的參數(shù)所對應的數(shù)據(jù)點作為第一個初始聚類中心，并將該數(shù)據(jù)點和與該數(shù)據(jù)點的相異度小于r 的所有數(shù)據(jù)點從集合M 中刪去，重復計算剩下數(shù)據(jù)點的相異度參數(shù)，直到找出K 個初始聚類中心為止。 該算法消除了聚類對初始聚類中心的敏感性，提高了聚類的準確率。 但是該算法的缺點是當最大相異度參數(shù)所對應的點不唯一時，不能夠合理地選取初始聚類中心。董秋仙等[18]對算法此缺陷進行改進，找出最大的相異度參數(shù)值對應的所有樣本點xi計算

式中：rij≤，j=1，2，…，p，且構成集合sum，若sum(i)=min sum， 則第i 個樣本點即為第一個初始聚類中心。 通過此算法，可在相異度參數(shù)最大值不唯一時，找到合適的第一個初始聚類中心，實驗表明，此改進算法比原算法具有更高的準確率，同時減少了迭代次數(shù)。 廖紀勇等[19]利用歐氏距離定義了數(shù)據(jù)點間的相異性，均值相異性和總體相異性，構造相異性矩陣，提出了IK-DM 算法。 均值相異性反映了數(shù)據(jù)點在數(shù)據(jù)集D 中的分布情況，值越大，則數(shù)據(jù)點xi的密度越低，與其他點距離越遠。 IK-DM 算法通過計算，選取均值相異性最大的點作為第一個初始聚類中心，選擇均值相異性第二大的點作為臨時第二個初始聚類中心， 通過計算該點與已有初始聚類中心間的相異性，若大于總體相異性，則該點確立為第二個初始聚類中心， 否則找均值相異性次大的點進行判斷，依次找出所有的初始聚類中心。 該算法降低了離群點對聚類結果的影響， 有效地選擇數(shù)據(jù)集D 中相異性較大的數(shù)據(jù)點作為初始聚類中心，避免選擇的中心點過于密集，顯著提高了算法的穩(wěn)定性和準確率， 但算法的執(zhí)行速度較為緩慢，耗時略長。

2.2 K 值的選擇

K 值的選取極大地影響了K－means 聚類結果，而聚類算法中K 值的選擇往往需要事先指定，且多數(shù)是根據(jù)歷史經(jīng)驗或者多次嘗試中得到的。 Rezaee等[20]根據(jù)實驗證明，最佳K 值位于區(qū)間[1，n]中。 為了得到更準確的類簇數(shù)目，學界嘗試從各個方面對聚類算法進行深入研究，提出了多種改進算法。

2.2.1 基于密度

賈瑞玉等[21]首先通過計算樣本密度選出初始聚類中心，在此基礎上計算對應不同的K 值時，優(yōu)化傳統(tǒng)聚類有效性指標BWP 為IBWP 指標， 更好地反應了單個數(shù)據(jù)點的聚類效果，IBWP 指標值越大，聚類效果越好，以此求得最佳聚類數(shù)目K。 該算法改進了聚類有效性指標，具有較好的準確性和穩(wěn)定性，但增加了算法的時間復雜度，運行時間過長。 賈瑞玉等[22]提出CNACS－K－means 算法，該算法重新定義數(shù)據(jù)點的局部密度， 構造數(shù)據(jù)集D 的決策圖，通過殘差分析自動確定類簇數(shù)目和初始聚類中心。實驗表明，CNACS－K－means 算法在二維和高維數(shù)據(jù)集上具有較高的準確性，能自動確定聚類類簇數(shù)目，該算法的缺點是不同數(shù)據(jù)集的數(shù)據(jù)分布會對聚類效果造成一定的影響，對于分布比較稀疏的數(shù)據(jù)集聚類效果不理想。

2.2.2 基于距離

眾多學者基于歐氏距離與誤差平方和SSE 來確定聚類數(shù)目K，隨著K 值增大，則聚類數(shù)目越多，類內差距會越來越小且SSE 會逐漸減小。當K 值小于真實聚類數(shù)時，隨著K 值增大，SSE 下降幅度大，當K 值等于真實聚類數(shù)時，再增加K 值，則斜率會迅速增大，隨著K 值增大，折線圖趨于平緩；因此拐點處對應的K 值多數(shù)為最佳K 值。 但是，對于某些數(shù)據(jù)集來說，“拐點”并不明顯，而得到的是一個“拐點區(qū)間”， 則無法確定準確K 值， 導致實驗出現(xiàn)偏差。 王建仁等[23]改進“手肘法”為ET－SSE 算法，針對“手肘法”中的“肘點”不明確問題進行改進。 改進算法利用指數(shù)函數(shù)的指數(shù)爆炸性質，引入偏執(zhí)項提高聚類誤差較大簇的SSE 的比重，引入權重θ 進行放縮調節(jié)使得該算法能更快更準地確定K 值。該算法有效地解決了“肘點不明確”的問題，提高準確率的同時，降低時間復雜度，缺點是權重θ 的調節(jié)需要根據(jù)實驗進行調整， 無法根據(jù)最佳權重進行實驗。 王子龍等[24]對歐氏距離進行維度加權的改進，并且引入樣本點的權重wi和參數(shù)τi， 通過改進后的歐氏距離計算樣本的密度和權重， 選取密度最大的樣本點作為第一個初始中心點， 再利用樣本點的權重和參數(shù)τi以此得到下一個初始中心點。該算法明顯改進了正常數(shù)據(jù)點與離群數(shù)據(jù)點到聚類中心的距離， 使得離群數(shù)據(jù)點到聚類中心之間的距離變大，放大差異，同時，權重的引入避免選取噪聲點作為聚類中心，避免聚類陷入局部最優(yōu)。在中小型數(shù)據(jù)上，該算法提高了運行速度，減少了算法的迭代次數(shù)，但針對大型數(shù)據(jù)，提高了算法的時間復雜度，耗時較長。

2.3 離群點篩選

聚類過程中，離群點的存在一定程度上影響了初始聚類中心的選取，導致離群點可能成為初始聚類中心，增加了迭代次數(shù)，降低了算法效率。 目前對于離群點的研究也成為一個熱門方向，眾多研究者嘗試通過多種方法對數(shù)據(jù)進行預處理來降低離群點對聚類的影響，以此提升算法效率。

2.3.1 基于密度

唐東凱等[25]提出了OFMMK－means 算法，通過使用LOF 算法——基于密度的離群點檢測算法來排除離群點的影響， 再根據(jù)最大最小法選取初始聚類中心，進行聚類。 該聚類算法首先對數(shù)據(jù)集D進行離群點檢測， 計算出每個數(shù)據(jù)點的離群因子值。 數(shù)據(jù)點的離群因子值分布體現(xiàn)了該點是離群點的概率，值越大，則該點為離群點的概率越大。再根據(jù)離群因子值的大小對數(shù)據(jù)集D 中的數(shù)據(jù)點進行升序排列，取前αn（0＜α≤1，n=|D|）個數(shù)據(jù)點作為初始聚類中心的候選集。 最后根據(jù)最大最小法[26]在初始聚類中心的候選集上選取距離盡可能遠的數(shù)據(jù)點作為初始聚類中心， 再進行K-means聚類。 OFMMK-means 算法提高了算法的穩(wěn)定性，具有較高的聚類準確率， 同時， 相較于傳統(tǒng)Kmeans 算法，聚類平均迭代次數(shù)也較小，但參數(shù)α的取值需要依據(jù)實驗確定，無法得到最佳準確值。楊紅等[27]利用LOF 算法進行離群點檢測，對數(shù)據(jù)集進行數(shù)據(jù)預處理， 得到密集點數(shù)據(jù)集iris-1 和離群點數(shù)據(jù)集iris-2， 接著對iris-1 數(shù)據(jù)集進行K-means 聚類，根據(jù)準則函數(shù)得到各個簇，其中準則函數(shù)作了改進

最后，把離群點數(shù)據(jù)集中的點根據(jù)距離最近原則分配到各個簇中。 該算法主要針對傳統(tǒng)準則函數(shù)僅僅考慮類內相似性的缺點進行改進，改進準則函數(shù)更考慮到類間差異性，放大了聚類效果，進一步優(yōu)化了聚類結果。 劉鳳等[28]利用局部密度離群值檢測方法檢測并去除數(shù)據(jù)集D 中離群值，對剩余點進行K-means 聚類，通過DB 指標、Dunn 指標、Sihouette 指標進行有效性評價， 以此評估數(shù)據(jù)集聚類結果，提高了聚類穩(wěn)定性。

2.3.2 基于距離

基于距離的離群點檢測方法計算簡單，可以用于任何可以計算數(shù)據(jù)點的數(shù)據(jù)集中，且與數(shù)據(jù)集的分布無關。 冷泳林等[29]利用基于距離的離群點檢測首先隨機選一數(shù)據(jù)點，計算該數(shù)據(jù)點與其他數(shù)據(jù)點間的歐氏距離，如果距離大于d 的數(shù)據(jù)點的比例大于參數(shù)p，則認為該點為離群點，依次測驗數(shù)據(jù)集中D 中的數(shù)據(jù)點，找出所有離群點。 接著，在非離群點中隨機選取K 個初始聚類中心， 對非離群點進行K-means 聚類，最后將離群點按照距離最近原則分配到各個簇中。 該算法降低了離群點對與聚類的影響，提高了聚類精度和穩(wěn)定性，但對于高維數(shù)據(jù)集來說，聚類效果并不十分明顯。 Milos 等[30]研究了基于距離法的高維數(shù)據(jù)集的離群點檢測，發(fā)現(xiàn)基于距離的方法可在高維數(shù)據(jù)中產(chǎn)生更具對比性的異常值分數(shù)，通過比較異常值分數(shù)進而得到離群點。 此改進算法解決了高維數(shù)據(jù)集之中基于距離法檢測離群點的問題。

3 K-means 改進算法對比分析

表1、 表2 和表3 分別給出選取初始聚類中心的改進算法對比、確定K 值的改進算法對比以及篩選離群點的改進算法對比。

表1 初始聚類中心選取的改進算法對比Tab.1 Comparison of improved algorithms for selecting initial cluster centers

表2 K 值確定的改進算法對比Tab.2 Comparison of improved algorithms for determining K value

表3 篩選離群點的改進算法對比Tab.3 Comparison of improved algorithms for screening outliers

4 結論

K-means 算法是一個極其經(jīng)典的聚類算法，自提出以來，以其思想簡單、聚類速度快、結果良好而得到廣泛應用。 但該算法也存在缺陷，本文主要對初始聚類中心的選取、K 值的選擇、 離群點的篩選問題進行論述，并且對各個缺陷分別基于密度和距離兩個方面進行詳細闡述，分析各個改進算法的優(yōu)缺點。

隨著近年來K-means 算法應用領域的逐漸拓寬，學術界對算法進行的改進也逐漸增多，但多數(shù)改進算法聚類效果的提高多是以增加時間復雜度作為代價，對于多維數(shù)據(jù)應用時，算法有效性尚不顯著，在后繼優(yōu)化研究中，可以考慮從以下幾個方面入手。

1） 在提升聚類效果的同時降低時間復雜度。

2） 考慮提升算法處理高維數(shù)據(jù)集的能力，隨著時代快速發(fā)展，各種數(shù)據(jù)信息繁冗復雜，能夠利用K-means 算法快速高效地處理多維數(shù)據(jù)也是未來重要的研究方向。

3） 目前，越來越多的K-means 改進算法中，多數(shù)改進算法會引入?yún)?shù)，但對于參數(shù)值的確定需要依據(jù)實驗經(jīng)驗調試，無法確定準確參數(shù)值，這需要進一步研究。