K均值優(yōu)化算法綜述

鄧濱玥

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

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

中圖分類號(hào)： TP391????文獻(xiàn)標(biāo)識(shí)碼：?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??引言

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

聚類分析將數(shù)據(jù)劃分為有效可使用的組（簇），使得每一個(gè)簇內(nèi)的數(shù)據(jù)點(diǎn)特征相似。與預(yù)測(cè)模型不同，聚類中沒有明顯的目標(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í)算法，它對(duì)數(shù)據(jù)挖掘應(yīng)用與大量的模式向量十分重要。因?yàn)槠洳襟E簡(jiǎn)單快速，對(duì)大數(shù)據(jù)效率較高、可伸縮性強(qiáng)，K-means算法被大量運(yùn)用在數(shù)據(jù)挖掘的任務(wù)中。但K-means的弊端也十分明顯，算法常會(huì)陷入局部最優(yōu)，初始質(zhì)心以及K值都需要人為設(shè)定，其選擇對(duì)最后結(jié)果影響較大，針對(duì)此問題，許多學(xué)者對(duì)K-means算法進(jìn)行了提升與優(yōu)化。

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

2.2 ?二分k-means

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

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

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

2.3??K-medoids

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

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

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

3 ?k-means算法改進(jìn)

3.1 ?基于k值選擇

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

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

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

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

由于K-means算法對(duì)初始點(diǎn)以及噪點(diǎn)十分敏感，常常會(huì)收斂到局部最小值而引起聚類結(jié)果的偏差，通過算法對(duì)噪點(diǎn)的處理以及迭代過程中劃分規(guī)則的改變可以解決此問題以達(dá)到全局最優(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]提出基于距離與密度，計(jì)算數(shù)據(jù)集的平均樣本距離，根據(jù)數(shù)據(jù)點(diǎn)之間的距離計(jì)算數(shù)據(jù)權(quán)重，從而選取最大權(quán)重?cái)?shù)據(jù)作為第一個(gè)中心點(diǎn)，將數(shù)據(jù)集進(jìn)行分類，并建立滿二叉樹，合并葉子結(jié)點(diǎn)得到k個(gè)初始聚類中心，快速處理中小型規(guī)模的數(shù)據(jù)集。

3.3??初始中心選擇

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

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

3.4??其他改進(jìn)方法

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

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

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

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

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

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

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

4??結(jié)束語

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