鄧濱玥

摘 ?要： k-means算法源于信號處理中的一種向量量化方法，現(xiàn)在則更多地作為一種聚類分析方法流行于數(shù)據(jù)挖掘領(lǐng)域。在數(shù)據(jù)挖掘技術(shù)中常常使用聚類方法，而k-means算法作為最典型、最常見、實用度最廣的一種聚類算法，具有簡單易操作等優(yōu)點。但此算法需要人工設(shè)定聚類中心的數(shù)量，初始聚類中心，容易陷入局部最優(yōu)，使得算法的時間復(fù)雜度變得較大，得到的聚類結(jié)果易受到k值與設(shè)定的初始聚類中心的影響，針對這些問題，本文介紹了k-means算法的改進方法，分析其優(yōu)缺點并提出了優(yōu)化算法的下一步研究方向。

關(guān)鍵詞：?k-means算法;聚類算法;聚類中心;誤差平方和;無監(jiān)督學(xué)習(xí)

中圖分類號： TP391????文獻標(biāo)識碼：?A????DOI：10.3969/j.issn.1003-6970.2020.02.041

【Abstract】： K-means algorithm originated from a vector quantization method in signal processing and is now more popular in the field of data mining as a clustering analysis method. Clustering method is often used in data mining technology， and k-means algorithm， as the most typical， the most common and the most practical clustering algorithm， has the advantages of simple and easy operation. But this algorithm need to manually set the number of cluster centers， the initial clustering center， easy to fall into local optimum， makes the time complexity of the algorithm is larger， the clustering results are susceptible to k value and setting of the influence of the initial clustering center， to solve these problems， this paper introduces the improvement methods of k - means algorithm， analyzes the advantages and disadvantages and puts forward the optimization algorithm of the next research direction.

【Key words】：?K-means; Clustering algorithm; Cluster center; SSE; Unsupervised learning

0??引言

在這個數(shù)據(jù)庫技飛速發(fā)展的大數(shù)據(jù)時代，指數(shù)型增長的數(shù)據(jù)對數(shù)據(jù)的處理分析技術(shù)的要求越來越高，人們希望能通過計算機自動智能地在大型數(shù)據(jù)中，發(fā)現(xiàn)有用的信息并預(yù)測未來的樣本觀測結(jié)果。隨著不斷地探索研究，數(shù)據(jù)挖掘技術(shù)在處理數(shù)據(jù)方面發(fā)展已經(jīng)較為成熟，它在常規(guī)數(shù)據(jù)分析方法的基礎(chǔ)上配合復(fù)雜算法來處理大規(guī)模的數(shù)據(jù)，已在各個領(lǐng)域的應(yīng)用中取得了豐碩的成果。

聚類分析將數(shù)據(jù)劃分為有效可使用的組（簇），使得每一個簇內(nèi)的數(shù)據(jù)點特征相似。與預(yù)測模型不同，聚類中沒有明顯的目標(biāo)變量作為數(shù)據(jù)的屬性存在。聚類分析在理解數(shù)據(jù)與數(shù)據(jù)預(yù)處理領(lǐng)域中都發(fā)揮了很大的作用，也是數(shù)據(jù)挖掘中常為應(yīng)用的一種算法。

k均值聚類算法（k- means clustering algorithm）是聚類分析方法中常被使用的一種迭代求解的無監(jiān)督學(xué)習(xí)算法，它對數(shù)據(jù)挖掘應(yīng)用與大量的模式向量十分重要。因為其步驟簡單快速，對大數(shù)據(jù)效率較高、可伸縮性強，K-means算法被大量運用在數(shù)據(jù)挖掘的任務(wù)中。但K-means的弊端也十分明顯，算法常會陷入局部最優(yōu)，初始質(zhì)心以及K值都需要人為設(shè)定，其選擇對最后結(jié)果影響較大，針對此問題，許多學(xué)者對K-means算法進行了提升與優(yōu)化。

本文將介紹K-means算法的基本思想和傳統(tǒng)K-means優(yōu)化的算法，以及現(xiàn)在學(xué)者針對K-means主要問題的改進。

2.2 ?二分k-means

為了減少初始劃分情況對聚類結(jié)果的影響，以及改進k-means算法收斂于局部的問題，提出了二分k-means算法，此算法為分層聚類中自頂向下進行分裂的一種方法。

算法的主要思想為：將所有數(shù)據(jù)點作為一個簇堆，并將其一分為二，計算所有簇堆的誤差平方和，并反復(fù)選擇誤差平方和偏大的簇，使用k-means算法將其劃分，直到簇的數(shù)量等于用戶所給定的k值。步驟圖解如圖2所示。

而由于二分K-means算法需要多次采用多次K-means方法聚類，增加了其復(fù)雜度，劉廣聰?shù)萚2]提出了用層次聚類與Chameleon算法對二分算法進行改進，隨機抽取初始聚類中心，尋找離質(zhì)心最近與最遠的兩個數(shù)據(jù)點作為新的聚類中心重新聚類，并通過計算簇間的相似度，建立相似度矩陣來進行優(yōu)化，提高算法的效率。

2.3??K-medoids

由于K-means算法取質(zhì)點時計算的為當(dāng)前簇中所有數(shù)據(jù)點的平均值，K-means算法對異常值十分敏感，在此問題上，K-medoids算法對其做出了改進。

在K-medoids中，選取當(dāng)前簇中到同一簇其他數(shù)據(jù)點距離之和最小的點作為質(zhì)心，并使用絕對差值和（Sum of Absolute Differences，SAD）代替SSE作為衡量聚類結(jié)果的標(biāo)準(zhǔn)。SAD的計算公式如下：

文獻[6]針對快速K-medoids初始聚類中心可能位于同一類簇及傳統(tǒng)K-medoids算法的缺陷，提出基于粒計算的K-medoids聚類算法，利用等價關(guān)系產(chǎn)生粒子，并根據(jù)粒子包含的樣本個數(shù)定義粒子密度，從而選擇密度較大的K個例子作為初始聚類中心，使得此算法聚類結(jié)果更加穩(wěn)定，并可適用于大規(guī)模的數(shù)據(jù)集。郝占剛[7]等提出一種基于遺傳算法和K-medoids算法的聚類新算法，此算法采用遺傳算法中的錦標(biāo)賽選擇法隨機選擇一定數(shù)目的樣本，并結(jié)合k-medoids對選擇出的個體進行優(yōu)化，代替原有個體，不斷進化直到結(jié)果符合要求，這種算法可以很好地解決k-medoids算法局部最優(yōu)與孤立點的問題，并加快了遺傳算法的收斂速度。

3 ?k-means算法改進

3.1 ?基于k值選擇

在K-means算法中，由于初始質(zhì)心點數(shù)k需要使用者指定，不同k值選擇所得出的聚類結(jié)果也不一樣，如何確定最優(yōu)k值或讓算法自動獲取k值成為學(xué)者改進k-means算法的一個目標(biāo)。

1998年，Razaee[8][8]提出最佳的聚類數(shù)應(yīng)該在2與之間，其中n為所有數(shù)據(jù)點的個數(shù)，此結(jié)論為后期k值選取優(yōu)化方面提供了基礎(chǔ)。由于傳統(tǒng)二分k-means時間復(fù)雜度較高，張忠平[9]等人對此算法進行改進，提出基于二分思想的確定聚類數(shù)目的算法，由于每次二分只需要兩個初始聚類中心，減少聚類中心對其算法結(jié)果的影響。KDM算法[11][10]通過最大最小距離法和數(shù)據(jù)存儲方法，劃分時不斷調(diào)整聚類中心實現(xiàn)了k值的自動確定，同時實現(xiàn)了初始中心的選擇。

之后有學(xué)者提出使用“手肘法”選擇肘點作為最優(yōu)的K值，此方法簡單直觀但可能會出現(xiàn)不明顯的“肘點”或是特殊情況使得K值的選擇出現(xiàn)偏差，文獻[11]ET-SSE算法對此進行了k值選擇的優(yōu)化，引入偏執(zhí)項調(diào)節(jié)變量改進總誤差平方和，通過對權(quán)重的調(diào)節(jié)得出最終k值。

3.2 ?基于局部最優(yōu)問題

由于K-means算法對初始點以及噪點十分敏感，常常會收斂到局部最小值而引起聚類結(jié)果的偏差，通過算法對噪點的處理以及迭代過程中劃分規(guī)則的改變可以解決此問題以達到全局最優(yōu)。

陳慧萍等[12]采用模擬退火思想提出了一種全局尋優(yōu)的K-means方法，設(shè)定目標(biāo)函數(shù)及控制參數(shù)，不斷迭代調(diào)整控制參數(shù)t（各聚類中心的值）直到得出當(dāng)前近似最優(yōu)解，得以得到最優(yōu)解。PBK-means算法[13]提出基于距離與密度，計算數(shù)據(jù)集的平均樣本距離，根據(jù)數(shù)據(jù)點之間的距離計算數(shù)據(jù)權(quán)重，從而選取最大權(quán)重數(shù)據(jù)作為第一個中心點，將數(shù)據(jù)集進行分類，并建立滿二叉樹，合并葉子結(jié)點得到k個初始聚類中心，快速處理中小型規(guī)模的數(shù)據(jù)集。

3.3??初始中心選擇

K-means一般采取隨機選擇的方式確定初始質(zhì)心，而這樣不僅會使得算法的時間復(fù)雜度增大，并且可能會選取到離群點導(dǎo)致結(jié)果差異很大，現(xiàn)代學(xué)者更偏向通過與其他算法相結(jié)合的方式獲得較準(zhǔn)確初始質(zhì)心。

Redmond[14]等人最早提出通過kd-tree從帶劃分的數(shù)據(jù)集中篩選密度大又相互分離的數(shù)據(jù)作為初始中心，而由于此方法在估計數(shù)據(jù)密度方面存在缺陷，基于此方法，后代學(xué)者提出了對應(yīng)的改進。文獻[15]提出基于最小支撐樹，選中密度大且足夠分離的數(shù)據(jù)稠密區(qū)中的點作為初始聚類中心，使得算法可以在選出處在不同類的數(shù)據(jù)作為初始中心。文獻[16]提出一種利用關(guān)系矩陣和度數(shù)中心度的分析方法來選取初始中心點，減少聚類過程的迭代次數(shù)得到更穩(wěn)定的聚類結(jié)果，但此方法在處理大規(guī)模數(shù)據(jù)問題上還存在局限性。

3.4??其他改進方法

Dan Pelleg[17]等在2000年提出一種x-means的聚類方法，運用統(tǒng)計學(xué)標(biāo)準(zhǔn)將樣本的似然函數(shù)最大化，通過計算BIC score來決定是否將簇二分，算法的主要步驟圖如下：

此方法不用預(yù)先指定k的個數(shù)，只需要給出k值范圍，很好地解決了k-means算法k值難以確定的問題，對大規(guī)模的數(shù)據(jù)也具有很好的效率，但是不適用于高維數(shù)據(jù)中。

此外，還有很多學(xué)者分別提出了基于Spark框架[18]、MapReduce框架[19]、Hadoop[20]框架等常見數(shù)據(jù)計算平臺來改進K-means算法，通過并行計算提高聚類提速。

在d維空間中找到k-均值聚類問題的最優(yōu)解的計算復(fù)雜度：

NP-hard：一般歐式空間中，即使目標(biāo)聚類數(shù)僅為2

NP困難：平面中，不對聚類數(shù)目k作限制

如果k和d都是固定的，時間復(fù)雜度為，其中n為待聚類的觀測點數(shù)目

4??結(jié)束語

作為聚類算法中較為經(jīng)典的K-means算法，因為計算快速方便被廣泛應(yīng)用在數(shù)據(jù)挖掘等大數(shù)據(jù)處理方面，由于其缺點也十分明顯，在提出后便不斷有學(xué)者針對這些問題進行優(yōu)化與改進，但在對算法進行改進時將會犧牲其他各方面的指標(biāo)。所以在優(yōu)化k-means算法三個主要問題的同時，如何有效地縮短算法的復(fù)雜度、使算法能夠適用于多維度問題以及大規(guī)模數(shù)據(jù)問題等將成為學(xué)者們的下一步的研究方向，尤其是在機器學(xué)習(xí)技術(shù)的日益豐富的背景下，各種聚類算法與機器學(xué)習(xí)相結(jié)合，各種優(yōu)化方案等更是以后的攻堅工程。