K-means算法研究綜述
2018-02-26 12:23:22叢思安王星星
電子技術與軟件工程 2018年17期
叢思安 王星星
摘要
k-means算法是一種非常簡單并且使用廣泛的聚類算法，但是一是k值需要預先給定，很多情況下k值的佑計很困難。二是K-Means算法對初始選取的聚類中心點很敏感，不同的中心點聚類結果有很大的不同。也就是說，有可能陷入局部最優解。三是對離群點敏感，聚類結果易產生誤差。四是相似性度量的函數不同也會對聚類結果產生影響。本文針對k-means的缺陷，對這幾年k-means算法的研究進展進行了綜述。從初始中心點的選取、離群點的檢測與去除、相似性度量等幾個方面進行概括、比較最后，對k-means算法的未來趨勢進行展望。
【關鍵詞】k-means算法 初始聚類中心 相似性度量 離群點
K-means聚類算法是由Steinhaus 1955年、Lloyd 1957年、Ball&Hall; 1965年、McQueen1967年分別在各自的不同的科學研究領域獨立的提出。K-means聚類算法被提出來后，經過多年的實踐證明，k-means算法依然是簡單、高效的算法，并且被廣泛應用在科學研究以及工業應用中，發展出大量的改進的算法。目前，k-means算法仍然是一個研究熱點。
K-means算法的改進主要從以下幾個方面：一是如何確定合適的k值，二是如何選取好的初始聚類中心，三是離群點的檢測與去除，四是距離與相似度度量的改進以及其他方面的改進等等。本文則從以上幾個方面對k-means算法的研究進展進行綜述。本文第一部分介紹傳統的k-means算法，第二部分從各個方面介紹k-means算法的優化，第三部分進行總結以及展望。
1 傳統的k-means算法
K-means算法是一種簡單、高效的聚類算法，并得到了廣泛的應用。K-means算法的基本思想是首先隨機選取初始聚類中心，然后計算每個樣本點到初始聚類中心的歐式距離，按照距離最近的準則將它們分配給相似度最大的聚類中心所代表的類。計算每個類別所有樣本點的均值，更新聚類中心，直到目標準則函數收斂為止。具體算法步驟如下：
（1）用戶輸入類簇數目的值k，從n個樣本點中隨機選取k個點作為初始聚類中心;
（2）遍歷所有的樣本點，計算每個樣本點到初始聚類中心的歐式距離，歐氏距離的大小作為相似度的評判標準，歐氏距離越小，相似度越大。按照距離最近的準則將樣本點分配給相似度最大的聚類中心所代表的類。
（3）重新確定聚類中心。將每個類簇中的所有樣本點的均值作為新的聚類中心。
（4）重復（2）和（3），直到聚類中心不再發生變化。
2 k-means算法的改進
2.1 初始聚類中心的選取
初始聚類中心的選取對k-means算法聚類結果的影響很大，不同的初始聚類中心，可能會產生不同的聚類結果。也可以說，k-means算法是一種貪心算法，容易陷入局部最優解。
賈瑞玉等人[2]主要運用了Rodriguez A等人[3]提出的類簇中心都處在局部密度比較大的位置，且距離具有比它更大的局部密度的對象相對較遠的思想。運用此思想可以確定最佳初始聚類中心及數據集的最佳類簇數目。賈瑞玉等人在這個思想的基礎上，為了避免密度對截斷距離的依賴性，重新定義了計算樣本局部密度ρi的方法，計算樣本點到具有比它更高的局部密度數據對象的最近距離δi（當樣本點xi是數據集中具有最大局部密度的樣本點時，δi定義為xi和距離他最遠的樣本點之間的歐氏距離）。根據ρi和δi構造決策圖，運用統計學中殘差分析的方法，選取殘差絕對值大于閾值的異常點，即為聚類中心。在二維以及高維數據集上的實驗結果均驗證了該算法的有效性。但是不足之處在于這個算法適用于比較集中的數據集，稀疏的數據集結果并不理想。
Lei Gu[4]等人采用減法聚類的算法確定初始聚類中心。首先是計算每個樣本點的山峰函數值，選取山峰函數值最大的點作為聚類中心。選取下一個聚類中心時要消除已經確定的聚類中心的影響，就修改山峰函數，減去上一個確定的聚類中心的比例高斯函數，如此反復，直到得到足夠多的聚類中心。這個方法的缺點在于對于離群點、異常值抗干擾能力比較弱，且需要設置的參數較多（一般需要3個）。
M.S.Premkumar等人[5]采用了四分位數的概念來確定初始聚類中心。首先采用特征選擇的方法選取數據有意義的屬性。然后將將屬性的值按照順序排列，以分成兩類為例，將數據集的上四分位點和下四分位點作為初始聚類中心，計算所有樣本點到到這兩個聚類中心的距離，進行分類;接下來更新聚類中心，將每類所有樣本點的均值作為新的聚類中心，直到類簇不再發生變化。這個方法不足之處是當數據集比較大時，花費時間會比較長。
C.Lasheng等人[6]首先是采用最大一最小準則算法初步確定初始聚類中心，然后通過FLANT（快速最近鄰搜索庫）將聚類中心偏移到盡可能地靠近實際的聚類中心。最大一最小準則算法是首先隨機選取一個點作為第一個聚類中心，選取距離這個點最遠的點作為第二個聚類中心，然后計算每個點到這兩個聚類中心的距離，選取較小的距離加入到集合V中，在集合V中選取距離最遠的點作為下一個聚類中心，依次類推，直到最大最小距離不大于θ·D1，2（C1，2為第一個和第二個聚類中心的距離）。FLANT是一個在高維空間中快速搜索k個最近鄰居的庫。使用FLANT找到聚類中心的k近鄰，計算中心點即為新的聚類中心。
2.2 距離和相似性度量
傳統的k-means算法使用歐幾里得距離來度量相似度。陳磊磊[7]采用了歐式距離、平方歐式距離、曼哈頓距離、余弦距離、谷本距離分別作為相似度度量對文本數據進行處理，實驗結果顯示余弦距離、谷本距離者在文本聚類中的表現更優。不同的測度距離作為相似性度量對聚類結果會產生不同的影響，對于不同類型的數據也應采用不同的距離函數作為相似度度量。
W.Xue等人[8]針對k-means算法不能求解非線性流形聚類的缺陷，提出了用空間密度相似性度量來代替歐幾里得距離，使k-means算法能夠適應數據集的分布。同一簇中的數據點應位于高密度區域，不同簇中的數據點應該用低密度區域分隔開來。所以需要壓縮高密度區域的距離，放大低密度區域的距離。作者在文中定義了空間密度長度公式L（i，j）。通過連接點i和j定義圖G，其中點i為j的k近鄰點。對于近距離的兩個點，使用L（i，j）的值作為邊長，對于遠距離的兩個點，則設置短跳（i通過一個或者多個中間點到達j），求最短路徑為遠距離兩個點的距離值。這種方法能夠有效的對非線性聚類中心進行求解。
J.P.Singh和N.Bouguila[9]針對比例數據，提出用Aitchison距離度量來對比例數據進行聚類。作者使用Aitchison距離、歐幾里德對數距離、余弦距離、Kullback距離、Matisuita距離進行了對比實驗，文本聚類結果顯示Aitchison距離度量最適合所有，因為較高的輪廓值，聚類更合適。對于圖像比例數據聚類，使用Aitchison距離作為初始化步驟可以提供適用于比例數據的更好的混合結果。
2.3 離群點的檢測
K-means算法對于離群點敏感，對聚類結果產生很大的影響，因此離群點的檢測與刪除極為重要。
Breunig等人[10]的基于密度的方法是一種流行的異常值檢測方法。它計算每個點的局部離群因子（LOF）。一個點的LOF是基于該點附近區域的密度和它的鄰居的局部密度的比值。LOF方法依賴于用戶提供的最小數量點，用于確定鄰居的大小。
K.Zhang等人[11]建立了一個基于本地距離的離群因子（LDOF）來測量分散的數據集對象的離群程度。LDOF使用一個對象到它的鄰居的相對位置，以確定物體偏離其鄰近區域的程度。為了方便實際應用中的參數設置，作者在離群值檢測方法中使用了一種top-n技術，其中只有具有最高值的對象才被視為離群值。與傳統的方法（如前n和頂n）相比，方法是在分散的數據中檢測出離群值。
Ting Zhang等人[12]提出了通過添加上限范數和一種有效的迭代重加權算法，來減小離群點的影響。離群點的檢測發生在每次聚類中心迭代時，每個樣本點到聚類中心的距離大于給定的參數ε，便會被去除。并且重新給樣本分配權重，低錯誤率的樣本具有更高的權重。這個方面的缺陷在于參數ε需要人為的設置與調整，不同的ε值導致的聚類結果準確率不同。
P.O.Olukanmi and B.Twala[13]提出了k-means-sharp算法，通過從點到質心距離的分布得到的全局閾值自動檢測離群點。離群點檢測過程和聚類過程同時完成。假設k-means的數據呈高斯分布，離群點檢測發生在每次聚類中心更新時，計算每個樣本點到聚類中心的距離，如果距離大于3σ，則為離群點，其中σ=1.4826MADe，MADe為每個點到中值點的距離組成的所有數據的中值點。因此，每次更新聚類中心時，就會去除一部分離群點。
2.4 k-means算法的其他改進
最近幾年出現了遺傳算法、粒子群算法、螢火蟲算法、蟻群算法等與傳統的kmeans算法相結合的改進算法，這幾類算法的共同點是具有一定的全局優化能力，理論上可以在一定的時間內找到最優解或近似最優解。通常是使用這些算法來尋找k-means算法的初始聚類中心。
Kapil等人[14]的實驗結果顯示，和遺傳算法結合的k-means算法優于k-means算法。遺傳k-means算法就是把每個聚類中心坐標當成染色體基因。聚類中心個數就是染色體長度，對若干相異染色體進行初始化操作并將其當成一個種群進行遺傳操作，最終獲得適應度最大染色體，而最優聚類中心坐標就是解析出的各中心點坐標。
沈艷等人[15]將粒子群算法與k-means算法結合，提出多子群多于多子群粒子群偽均值（PK-means）聚類算法，理論分析和實驗表明，該算法不但可以防止空類出現，而且同時還具有非常好的全局收斂性和局部尋優能力，并且在孤立點問題的處理上也具有很好的效果。
陳小雪等人[16]提出了一種基于螢火蟲優化的加權K-means算法。該算法在提升聚類性能的同時，有效增強了算法的收斂速度。在實驗階段，通過UCI數據集中的幾組數據對該算法進行了聚類實驗及有效性測試，實驗結果充分表明了該算法的有效性及優越性。
可見，將k-means算法與其他算法相結合，可以彌補k-means算法的不足，獲得更好的聚類效果。
3 結束語
K-means的發展已經經歷了很長的一段時間，它所具有的獨特優勢使得其被廣大研究者不斷地優化和使用。本文從k-means算法中心點的選取、離群點的檢測與去除、距離與相似性度量等方面進行了綜述，可以看出k-means算法在這幾方面的改進依然需要進行深入的研究。對k-means的研究和改進還應注意以下幾點：
（1）隨著互聯網技術的發展，數據量呈現出一種指數級增長。如何高效地對這些海量數據進行處理和分析己成為當前研究熱點。傳統的k-means算法難以有效處理大的數據集。所以將并行計算和k-means算法結合，并不斷地對其加以改進和優化，是處理海量數據的有效途徑。
（2）k-means聚類算法的改進有許多依然需要用戶輸入參數，傳統的k-means算法的k值的確定研究不多。所以參數的自確定是一個不斷需要發展研究的問題。
（3）從文中可以看出，現在存在著各種各樣的數據類型，文本、圖像、混合型數據等等，現有的多是處理二維數據，對高維數據處理的研究不多，需要對k-means算法進行擴展，以得到一個能夠適應大多數類型數據類型的k-means算法模型。
參考文獻
[1]王千，王成，馮振元，葉金鳳.K-means聚類算法研究綜述[d].電子設計工程，2012，20（07）：21-24.
[2]賈瑞玉，李玉功.類簇數目和初始中心點自確定的K-means算法[.1l.計算機工程與應用，2018，54（07）：152-158.
[3]Rodriguez A，Laio A.Clustering byfast search and findof densitypeaks[J].Science，2014，344：1492-1496.
[4]Lei Gu.A novel locality sensitivek-means clustering algorithm basedon subtractive clustering[C].IEEEInternational Conference on SoftwareEngineering and Service Science.IEEE，2017：836-839.
[5]M.S.Premkumar and S.H.Ganesh，.A Median Based External InitialCentroid Selection Method forK-Means Clustering[C].World Congresson Computing and CommunicationTechnologies.IEEE Computer Society，2017：143-146.
[6]C.Lasheng and L.Yuqiang.Improvedinitial clustering center selectionalgorithm for K-means[C].2017 SignalProcessing：Algorithms，Architectures，Arrangements，and Applications（SPA），Poznan，2017：275-279.
[7]陳磊磊.不同距離測度的K-Means文本聚類研究[J].軟件，2015，36（01）：56-61.
[8] W.Xue，R.1.Yang，X.y.Hong，et al.A novelk-Means based on spatial densitysimilarity measurement[C].Control andDecision Conference.IEEE，2017：7782-7784
[9]J.P.Singh and N.Bouguila.Proportional data clustering usingK-means algorithm：A comparisonof different distances[C].IEEE International Conferenceon Industrial Technology.IEEE，2017：1048-1052.
[10]Breunig M M.LOF：identifyingdensity-based local outliers[C].ACMSIGMOD International Conference onManagement of Data.ACM，2000：93-104.
[11]K.Zhang，M.Hutter，and H.J in.Anew local distance-based outlierdetection approach for scatteredreal-world data[C].Proceedings ofthe 13th Pacific-Asia Conference onAdvances in Knowledge Discovery andData Mining，2009：813-822.
[12]T.Zhang，F.Yuan and L.Yang.CappedRobust K-means Algorithm[C].International Conference onMachine Learning and Cybernetics.IEEE，2017：150-155.
[13]P.O.Olukanmi and B.Twala.K-means-sharp：Modified centroid update foroutlier-robust k-means clustering[C].2017 Pattern Recognition Associationof South Africa and Robotics andMechatronics（PRASA一RobMech），Bloemfontein，2017：14-19.
[14]Kapil S，Chawla M，Ansari M D.OnK-means data clustering algorithmwith genetic algorithm[C].FourthInternational Conference on Parallel，Distributed and Grid Computing.IEEE，2017：202-206.
[14]沈艷，余冬華，王昊雷.粒子群K-means聚類算法的改進[J].計算機工程與應用，2014，50（21）：125-128
[15]陳小雪，尉永清，任敏，孟媛媛.基于螢火蟲優化的加權K-means算法[J].計算機應用研究，2018，35（02）：466-470.
