一種優(yōu)化初始聚類(lèi)中心的自適應(yīng)聚類(lèi)算法

曹端喜 唐加山 陳香

摘 要：K均值算法（K-Means）是聚類(lèi)算法中最受歡迎且最健壯的一種算法，然而在實(shí)際應(yīng)用中，存在真實(shí)數(shù)據(jù)集劃分的類(lèi)數(shù)無(wú)法提前確定及初始聚類(lèi)中心點(diǎn)隨機(jī)選擇易使聚類(lèi)結(jié)果陷入局部最優(yōu)解的問(wèn)題。因此提出一種基于最大距離中位數(shù)及誤差平方和（SSE）的自適應(yīng)改進(jìn)算法。該算法根據(jù)計(jì)算獲取初始聚類(lèi)中心點(diǎn)，并通過(guò)SSE變化趨勢(shì)決定終止聚類(lèi)或繼續(xù)簇的分裂，從而自動(dòng)確定劃分的類(lèi)簇個(gè)數(shù)。采用UCI的4種數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。結(jié)果表明，改進(jìn)后的算法相比傳統(tǒng)聚類(lèi)算法在不增加迭代次數(shù)的情況下，聚類(lèi)準(zhǔn)確率分別提高了17.133%、22.416%、1.545%、0.238%，且聚類(lèi)結(jié)果更加穩(wěn)定。

關(guān)鍵詞：聚類(lèi)算法;K-Means算法;初始聚類(lèi)中心;自適應(yīng)

DOI：10. 11907/rjdk. 201478 開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類(lèi)號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2020）007-0028-04

An Adaptive Clustering Algorithm by Optimizing Initial Clustering Centers

CAO Duan-xi1，TANG Jia-shan2，CHEN Xiang2

（1. School of Communication and Information Engineering， Nanjing University of Posts and Telecommunications;

2. School of Science， Nanjing University of Posts and Telecommunications， Nanjing 210000，China）

Abstract：K-Means is one of the most popular and robust clustering algorithms. However， in practical applications， the number of classes divided by the real data set cannot be determined in advance and the random selection of the initial clustering center point easily leads to the problem that the clustering result falls into the local optimal solution. To this end， this paper proposes an adaptive and improved algorithm based on the maximum distance median and the sum of squared errors （SSE）. The algorithm obtains the initial cluster center point through calculation， and decides to terminate the cluster or continue the division of the cluster based on the change trend of the SSE， so as to automatically determine the number of clusters to be divided. The results of experiments using four UCI data sets show that the improved algorithm improves the clustering accuracy by 17.133%， 22.416%， 1.545%， and 0.238% respectively without increasing the number of iterations compared to the traditional clustering algorithm， and the clustering results are more stable.

Key Words： clustering algorithm; K-Means algorithm; initial clustering center; adaptive

0 引言

“物以類(lèi)聚”指將同類(lèi)事物聚在一起。在數(shù)據(jù)科學(xué)方面，將相類(lèi)似的數(shù)據(jù)通過(guò)某種準(zhǔn)則聚集在一起，從而發(fā)現(xiàn)數(shù)據(jù)間的聯(lián)系，稱(chēng)為聚類(lèi)。在實(shí)際問(wèn)題中，聚類(lèi)分析無(wú)法事先知道待操作數(shù)據(jù)劃分的類(lèi)結(jié)果，類(lèi)結(jié)果的形成完全取決于數(shù)據(jù)集中樣本之間的內(nèi)在聯(lián)系[1]，這種發(fā)現(xiàn)內(nèi)在結(jié)構(gòu)的方法，是一種無(wú)監(jiān)督學(xué)習(xí)方法。聚類(lèi)技術(shù)是數(shù)據(jù)挖掘領(lǐng)域的重要方法。近年來(lái)隨著數(shù)據(jù)量的倍增及大數(shù)據(jù)技術(shù)的發(fā)展，該技術(shù)備受關(guān)注，其在模式識(shí)別、圖像分割[2]、文檔聚類(lèi)[3]、市場(chǎng)細(xì)分[4-5]、特征學(xué)習(xí)[6-7]等方面應(yīng)用廣泛。

K-Means[8]算法是一種基于劃分的無(wú)監(jiān)督學(xué)習(xí)聚類(lèi)算法[9]，最早由Macqueen提出，該算法由于其簡(jiǎn)單、快速的特點(diǎn)得到了廣泛應(yīng)用，但算法存在難以估計(jì)簇?cái)?shù)、隨機(jī)選擇的初始聚類(lèi)中心會(huì)使結(jié)果陷入局部最優(yōu)化、對(duì)離群點(diǎn)和孤立點(diǎn)敏感、無(wú)法識(shí)別非球形簇的數(shù)據(jù)等缺陷。

目前K-Means算法研究方向主要分為聚類(lèi)簇?cái)?shù)[k]值確定與初始聚類(lèi)中心點(diǎn)確定兩個(gè)方面。國(guó)內(nèi)外眾多學(xué)者提出了許多改進(jìn)算法。文獻(xiàn)[10]基于圖像分割的思想，利用數(shù)據(jù)維數(shù)密度分析，使用分水嶺算法對(duì)原始數(shù)據(jù)集進(jìn)行分割，根據(jù)分割的區(qū)域中心點(diǎn)確定初始聚類(lèi)中心，分割的區(qū)域個(gè)數(shù)作為簇?cái)?shù)[k]。該方法在一定程度上能夠獲得準(zhǔn)確的[k]值與初始聚類(lèi)中心，但分水嶺算法存在噪聲敏感及過(guò)分割現(xiàn)象，若數(shù)據(jù)集含有噪聲則聚類(lèi)結(jié)果精度將大幅下降;文獻(xiàn)[11]利用LOF離群點(diǎn)檢測(cè)算法篩除離群點(diǎn)，在篩選后的樣本中利用最大最小距離算法選擇初始聚類(lèi)中心，能有效避免離群點(diǎn)的影響，但篩選過(guò)程降低了算法效率;文獻(xiàn)[12]通過(guò)比較[k]取所有可能值的聚類(lèi)結(jié)果，選出其中聚類(lèi)結(jié)果最佳[k]值，提出一種確定類(lèi)簇個(gè)數(shù)的方法，但當(dāng)[k]值變化范圍很大時(shí)，該方法將耗費(fèi)大量時(shí)間和精力;文獻(xiàn)[13]提出的X-means算法，采用貝葉斯信息準(zhǔn)則（BIC）計(jì)算得分，利用K-Means算法二分相應(yīng)的簇，以此確定最優(yōu)類(lèi)簇個(gè)數(shù);文獻(xiàn)[14]利用期望最大化算法理論，提出似然函數(shù)的碎石圖方法，對(duì)于不規(guī)則數(shù)據(jù)集的聚類(lèi)結(jié)果比利用BIC方法更加可靠;文獻(xiàn)[15]利用最小方差與密度之間的關(guān)系，提出一種利用最小方差優(yōu)化初始聚類(lèi)中心的方法，該方法在方差計(jì)算與比較上時(shí)間復(fù)雜度過(guò)高，且對(duì)于存在孤立點(diǎn)的數(shù)據(jù)不能獲得較好的聚類(lèi)結(jié)果;文獻(xiàn)[16]采用最大最小距離方法，通過(guò)兩階段搜索獲取最佳初始聚類(lèi)中心，對(duì)數(shù)據(jù)集采用先分割后合并的思想獲得分類(lèi)結(jié)果，提出一種多中心距離算法。該方法對(duì)于不規(guī)則簇有良好的聚類(lèi)能力。

本文在分析已有算法的基礎(chǔ)上，提出一種基于最大距離中位數(shù)的改進(jìn)算法，該算法基于K-Means算法，通過(guò)計(jì)算獲取初始聚類(lèi)中心點(diǎn)，可自適應(yīng)確定類(lèi)簇個(gè)數(shù)，在不增加迭代次數(shù)的情況下提升聚類(lèi)結(jié)果準(zhǔn)確率。仿真結(jié)果表明，本文算法聚類(lèi)結(jié)果更加穩(wěn)定。

1 最大距離中位數(shù)與SSE的自適應(yīng)聚類(lèi)算法

1.1 算法基本思想

K-Means算法基本思想為：將含有[n]個(gè)對(duì)象的數(shù)據(jù)集S劃分為[k]個(gè)簇，簇中每個(gè)對(duì)象到簇中心距離最小。K-Means算法是一個(gè)不斷迭代的過(guò)程[17]，影響該算法性能的一個(gè)重要方面是初始聚類(lèi)中心點(diǎn)的選擇，K-Means算法采用隨機(jī)獲取的方法，聚類(lèi)結(jié)果易陷入局部最優(yōu)解，另外在使用時(shí)必須提前設(shè)置好k值，具有一定局限性。

本文算法初始聚類(lèi)中心點(diǎn)選擇，借鑒K-Means++[18]算法的思想，將數(shù)據(jù)集中最有可能成為聚類(lèi)中心且相距最遠(yuǎn)的兩個(gè)點(diǎn)作為最初的選擇點(diǎn)。在數(shù)據(jù)集中存在噪聲或孤立點(diǎn)的情況下，如果直接選擇相距最遠(yuǎn)兩點(diǎn)作為初始聚類(lèi)中心，一旦選擇到的點(diǎn)為噪聲或孤立點(diǎn)，聚類(lèi)結(jié)果會(huì)陷入局部最優(yōu)解。故本文提出最大距離中位數(shù)的方法，根據(jù)當(dāng)前聚類(lèi)數(shù)據(jù)點(diǎn)與相距最遠(yuǎn)兩點(diǎn)和當(dāng)前聚類(lèi)中心點(diǎn)之間的距離大小關(guān)系，獲取距離值為中位數(shù)的數(shù)據(jù)點(diǎn)，作為下一輪迭代的初始聚類(lèi)中心點(diǎn)。該方法可有效避免選擇噪聲或者孤立點(diǎn)對(duì)聚類(lèi)結(jié)果產(chǎn)生的影響。具體過(guò)程如下。

首先獲取相距最遠(yuǎn)的點(diǎn)[xa]、[xb]，記錄距離為[Dist]。計(jì)算所有點(diǎn)與[xa]、[xb]之間的距離[d]以及與初始聚類(lèi)中心[ic]（當(dāng)前簇的聚類(lèi)中心點(diǎn)）之間的距離[dc]，為使數(shù)據(jù)點(diǎn)限定在各自相應(yīng)的簇中，采用[dDist/2]且[dcDist/2]作為數(shù)據(jù)點(diǎn)過(guò)濾準(zhǔn)則，滿(mǎn)足要求的點(diǎn)的總距離[dsum=d+dc]會(huì)被記錄下來(lái);最后對(duì)記錄集中的[dsum]進(jìn)行從小到大排序，選擇距離值為中位數(shù)的點(diǎn)作為新的初始聚類(lèi)中心點(diǎn)。

通過(guò)SSE值變化趨勢(shì)實(shí)現(xiàn)自動(dòng)確定聚類(lèi)簇?cái)?shù)，曲線(xiàn)變化程度下降幅度最大位置為肘部，對(duì)應(yīng)[k]值為最佳聚類(lèi)個(gè)數(shù)，由此可得在此[k]值下聚類(lèi)的SSE值為最佳值，往后會(huì)增加聚類(lèi)個(gè)數(shù)，但SSE值變化很小，產(chǎn)生如圖1所示的類(lèi)似于肘部一般的曲線(xiàn)。但一些數(shù)據(jù)集在聚類(lèi)過(guò)程中呈現(xiàn)出的SSE值變化曲線(xiàn)下降比較平滑，如圖2所示，不易于直觀獲取最佳的聚類(lèi)個(gè)數(shù)[k]。本文對(duì)于第一種情況，由于變化曲線(xiàn)遞減程度比較明顯，利用本次與前一次的SSE差值對(duì)比[（SSE（t-1）-SSE（t））/SSE（t）]獲取變化量;第二種情況，由于變化趨勢(shì)不明顯，可以采用區(qū)間變化值進(jìn)行比較，每次比較兩段區(qū)間內(nèi)的SSE值變化量，即采用[SSE（t-2）-][SSE（t-1）]與[SSE（t-1）-SSE（t）]對(duì)比;將兩種方法得出的變化量與設(shè)定的閾值進(jìn)行比較，如果變化量小于設(shè)定的閾值變化量，則終止聚類(lèi)運(yùn)算，否則繼續(xù)進(jìn)行簇分裂操作，從而實(shí)現(xiàn)自動(dòng)確定聚類(lèi)簇?cái)?shù)。簇分裂操作是根據(jù)已劃分的簇SSE值與簇?cái)?shù)據(jù)個(gè)數(shù)的平均值大小選擇分裂平均值最大的簇，平均SSE值越大在一定程度上可以說(shuō)明數(shù)據(jù)之間差異性較大，需要分裂以降低數(shù)據(jù)之間的差異性。簇的分裂采用K-Means算法。[SSE]值計(jì)算公式為：

其中，[k]表示當(dāng)前類(lèi)簇個(gè)數(shù)，[x]表示簇[Ci]中的數(shù)據(jù)點(diǎn)，[Oi]表示當(dāng)前類(lèi)簇質(zhì)心。

1.2 算法步驟

給定數(shù)據(jù)集[S={x1，x2，？，xn}]，設(shè)定算法初始聚類(lèi)中心集[C]，K-Means算法初始聚類(lèi)中心點(diǎn)集合[C]，閾值[δ1]、[δ2]，聚類(lèi)個(gè)數(shù)最大值[kmax]，迭代處理標(biāo)志[flag]（[flag=3]表示算法步驟（3）進(jìn)入迭代，[flag=7]表示跳轉(zhuǎn)至步驟（7）），算法具體步驟如下：

（1）計(jì)算數(shù)據(jù)集S中所有數(shù)據(jù)點(diǎn)之間的距離[d（xi，xj）]，保存并從小到大排序。

（2）由于初始簇由當(dāng)前整個(gè)數(shù)據(jù)集組成，故令初始[SSE（0）=∞]，[t=1]（簇?cái)?shù)最小為1，也表示當(dāng)前類(lèi)簇的個(gè)數(shù)） ， 計(jì)算質(zhì)心作為聚類(lèi)初始中心[C（1）={X}]。

（3）定義迭代標(biāo)志[flag=3]，處理過(guò)程中若發(fā)生變化，下一輪即滿(mǎn)足聚類(lèi)終止條件結(jié)束聚類(lèi)。判斷[C（t）=kmax]（[C（t）]也表示聚類(lèi)簇?cái)?shù)），若成立表示初始聚類(lèi)中心點(diǎn)數(shù)已到達(dá)最大聚類(lèi)個(gè)數(shù)，終止聚類(lèi)，[flag=7];否則分別計(jì)算所有劃分好的簇[Si]（[i]=1，…，t，表示第幾個(gè)簇）的[SSE]值以及簇的數(shù)據(jù)個(gè)數(shù)[Num]。判斷[SSE]值下降趨勢(shì)變化量與閾值之間的關(guān)系：[SSE（t-1）-SSE（t）SSE（t）<δ1]，滿(mǎn)足則終止聚類(lèi)，[flag=7];否則繼續(xù)判斷[t3]（確保SSE含有兩段可比較的曲線(xiàn)）且[SSE（t-2）-SSE（t-1）SSE（t-1）-SSE（t）<δ2]，滿(mǎn)足則終止聚類(lèi)，[flag=7]，否則執(zhí)行步驟（4）。

（4）根據(jù)計(jì)算的[SSE]獲取[SSE]均值最大的簇，記為[Smax=maxSSENum]，當(dāng)前簇聚類(lèi)中心標(biāo)記為[cmax]，隨后利用最大距離法找出[Smax]中相距最遠(yuǎn)的兩個(gè)點(diǎn)[xa]和[xb]，兩點(diǎn)之間距離記為[Dist=dxa，xb]，計(jì)算數(shù)據(jù)中所有滿(mǎn)足要求的點(diǎn)，利用中位數(shù)方法獲取距離中位數(shù)點(diǎn)[xc]和[xd]，返回[xc，xd]。

（5）令[t=t+1]（進(jìn)行分裂操作，簇?cái)?shù)加1），此時(shí)[xc，xd]兩點(diǎn)分開(kāi)拷貝至前一個(gè)聚類(lèi)初始中心點(diǎn)[Ccmax]處，另一點(diǎn)則拷貝至當(dāng)前初始聚類(lèi)中心點(diǎn)[Ct]處。

（6）將[C]中的點(diǎn)作為初始聚類(lèi)中心點(diǎn)，采用傳統(tǒng)K-Means算法劃分簇[Smax]，將[C]拷貝至[C]，在K-Means算法迭代中更新聚類(lèi)中心集[C]，生成[C]個(gè)簇。之后將[C]拷貝至初始聚類(lèi)中心集[C]中，[flag=3]。

（7）結(jié)束聚類(lèi)運(yùn)算，輸出最終結(jié)果[t]、[C]，此時(shí)[t]值即最佳的類(lèi)簇個(gè)數(shù)[k]值，初始聚類(lèi)中心點(diǎn)集為[C]。

步驟（3）中根據(jù)SSE值的變化趨勢(shì)判斷是否終止聚類(lèi)或繼續(xù)簇分裂操作，從而自適應(yīng)獲取聚類(lèi)簇?cái)?shù)。步驟（4）是對(duì)于當(dāng)前劃分的簇中需進(jìn)一步分裂的簇，決定要分裂哪一個(gè)簇，通過(guò)最大距離中位數(shù)方法獲取新一輪迭代的初始聚類(lèi)中心點(diǎn)。選擇距離中位數(shù)點(diǎn)作為初始聚類(lèi)中心可避免數(shù)據(jù)偏移（左偏或右偏）帶來(lái)的影響，緊密度更高。

本文算法與K-Means算法最大的不同在于初始聚類(lèi)中心點(diǎn)的選擇，K-Means算法是隨機(jī)選擇，而本文算法是通過(guò)計(jì)算獲取。K-Means算法時(shí)間復(fù)雜度為[O（knt）]，本文算法的時(shí)間復(fù)雜度為[O（n2）+O（k2nt）]，其中[k]為類(lèi)別數(shù)，[n]為數(shù)據(jù)集包含的對(duì)象個(gè)數(shù)，[t]為聚類(lèi)的迭代次數(shù)。雖然計(jì)算數(shù)據(jù)集中數(shù)據(jù)點(diǎn)之間的距離增加了算法時(shí)間開(kāi)銷(xiāo)，但是通過(guò)最大距離中位數(shù)方法獲取的初始聚類(lèi)中心點(diǎn)，相比隨機(jī)選擇的初始聚類(lèi)中心點(diǎn)，最大距離方法降低了初始聚類(lèi)中心點(diǎn)分布集中度，使得中心點(diǎn)分布更為分散。過(guò)于集中的點(diǎn)會(huì)增加迭代次數(shù)，而較分散的點(diǎn)通常會(huì)減少迭代次數(shù)[19]。中位數(shù)選擇緊密程度相對(duì)高的點(diǎn)，即點(diǎn)距離聚類(lèi)實(shí)際中心點(diǎn)更近，可進(jìn)一步減少算法迭代次數(shù)，縮短迭代算法時(shí)間，迭代次數(shù)越少表明算法收斂越快，收斂性越好;其次本文算法可根據(jù)SSE值變化自動(dòng)獲取簇?cái)?shù)k值大小，去除聚類(lèi)之前對(duì)簇?cái)?shù)k值的預(yù)估過(guò)程，在一定程度上提升了聚類(lèi)算法效率。

2 實(shí)驗(yàn)結(jié)果與分析

2.1 實(shí)驗(yàn)數(shù)據(jù)集與實(shí)驗(yàn)環(huán)境

本文實(shí)驗(yàn)采用加州大學(xué)歐文分校提供的UCI機(jī)器學(xué)習(xí)庫(kù)，選取Iris、Balance-scale、Wine、Seeds數(shù)據(jù)集作為測(cè)試數(shù)據(jù)集。實(shí)驗(yàn)編程語(yǔ)言為Java，測(cè)試用的主機(jī)CPU為Intel？ CoreTM i5-4210U CPU，主頻為1.7GHz，內(nèi)存為12GB，改進(jìn)算法在IDEA上進(jìn)行測(cè)試。實(shí)驗(yàn)主要性能指標(biāo)為聚類(lèi)準(zhǔn)確率、迭代次數(shù)和運(yùn)行時(shí)間。實(shí)驗(yàn)選擇的Iris、Balance-scale、Wine、Seeds 4個(gè)數(shù)據(jù)集的統(tǒng)計(jì)信息如表1所示 。實(shí)驗(yàn)參數(shù)[δ1]為0.75，[δ2]為0.18，聚類(lèi)最大個(gè)數(shù)[kmax]為[n]，其中[n]為數(shù)據(jù)集數(shù)據(jù)個(gè)數(shù)。

2.2 實(shí)驗(yàn)結(jié)果分析

由于K-Means算法聚類(lèi)結(jié)果不穩(wěn)定，實(shí)驗(yàn)中對(duì)K-Means算法運(yùn)行結(jié)果采取運(yùn)算10次結(jié)果取均值的方法參與比較，有利于提高實(shí)驗(yàn)結(jié)果分析合理性。

將不同算法運(yùn)用至4個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，將數(shù)據(jù)集分別讀入寫(xiě)好的運(yùn)算程序中，實(shí)驗(yàn)結(jié)果如表2—表4所示。其中表2為在Iris與Balance-scale數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，表3為Wine數(shù)據(jù)集與Seeds數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果，表4為各數(shù)據(jù)集在各算法下平均運(yùn)行時(shí)間。

為了驗(yàn)證本文提出算法相比其它優(yōu)化初始中心點(diǎn)算法具有較好的性能，本文選取文獻(xiàn)[20]算法進(jìn)行實(shí)驗(yàn)結(jié)果對(duì)比。

從表2—表3可以看出，在聚類(lèi)準(zhǔn)確率方面，本文算法相比傳統(tǒng)算法在不增加迭代次數(shù)的情況下，Iris、Balance-scale、Wine、Seeds數(shù)據(jù)集聚類(lèi)結(jié)果準(zhǔn)確率分別提高了17.133%、22.416%、9.545%、0.238%。本文算法通過(guò)自適應(yīng)得到各個(gè)數(shù)據(jù)集的類(lèi)簇個(gè)數(shù)，其中Iris、Wine、Seeds數(shù)據(jù)集得出的類(lèi)簇個(gè)數(shù)與數(shù)據(jù)集類(lèi)簇個(gè)數(shù)一致，Balance-scale數(shù)據(jù)集本文算法自動(dòng)獲取2個(gè)類(lèi)簇，相比數(shù)據(jù)集真實(shí)類(lèi)簇個(gè)數(shù)少1個(gè)，但聚類(lèi)準(zhǔn)確率提升了22.416%，迭代次數(shù)減少了13.7次。

相比文獻(xiàn)[20]算法，本文算法在不降低聚類(lèi)準(zhǔn)確率的同時(shí)，Iris、Wine、Seeds數(shù)據(jù)集運(yùn)算迭代次數(shù)分別減少1次、4次、4次，對(duì)于Balance-scale數(shù)據(jù)集，雖然迭代次數(shù)一致，但準(zhǔn)確率提升了0.96%。上述聚類(lèi)結(jié)果對(duì)比表明，通過(guò)最大距離中位數(shù)方法計(jì)算獲取的初始聚類(lèi)中心點(diǎn)距離類(lèi)簇實(shí)際聚類(lèi)中心點(diǎn)更近，算法收斂次數(shù)更少，收斂速度更快，本文算法在初始聚類(lèi)中心點(diǎn)的選擇上性能更優(yōu)。

從表4可以看出，由于文獻(xiàn)[20]算法在算法開(kāi)始階段需計(jì)算各個(gè)數(shù)據(jù)點(diǎn)之間的距離大小并排序，且在進(jìn)行簇分裂計(jì)算時(shí)需根據(jù)相應(yīng)算法計(jì)算選出相對(duì)最佳初始聚類(lèi)中心點(diǎn)，這些計(jì)算增加了算法時(shí)間復(fù)雜度，所以本文算法與文獻(xiàn)[20]算法相比，運(yùn)行時(shí)間更短。從本文算法與文獻(xiàn)[20]算法的運(yùn)行時(shí)間對(duì)比可以看出，4個(gè)數(shù)據(jù)集在本文算法下進(jìn)行實(shí)驗(yàn)的整體運(yùn)行時(shí)間均比文獻(xiàn)[20]算法更短，表明迭代次數(shù)的減少可有效降低整體算法時(shí)間復(fù)雜度，提升算法運(yùn)行效率。

3 結(jié)語(yǔ)

本文針對(duì)傳統(tǒng)K-Means算法存在的主要缺陷，提出了一種基于最大距離中位數(shù)與SSE的自適應(yīng)改進(jìn)算法，利用最大距離取中位數(shù)的方法，通過(guò)計(jì)算獲取初始聚類(lèi)中心點(diǎn)，并根據(jù)SSE值變化趨勢(shì)決定終止聚類(lèi)或繼續(xù)簇的分裂，自動(dòng)確定數(shù)據(jù)劃分類(lèi)簇個(gè)數(shù)。實(shí)驗(yàn)結(jié)果表明，該算法可獲取較高的聚類(lèi)準(zhǔn)確率和較為可觀的收斂速度，聚類(lèi)結(jié)果穩(wěn)定且可自動(dòng)獲取聚類(lèi)類(lèi)簇個(gè)數(shù)，具有一定的技術(shù)優(yōu)勢(shì)和應(yīng)用價(jià)值。

參考文獻(xiàn)：

[1] 海沫，張書(shū)云，馬燕林. 分布式環(huán)境中聚類(lèi)問(wèn)題算法研究綜述[J]. 計(jì)算機(jī)應(yīng)用研究，2013，30（9）：2561-2564.

[2] 鄒旭華，葉曉東，譚治英.? 一種密度峰值聚類(lèi)的彩色圖像分割方法[J].? 小型微型計(jì)算機(jī)系統(tǒng)，2017，38（4）：868-871.

[3] SARDAR T H，ANRISA A. An analysis of MapReduce efficiency in document clustering using parallel K-means algorithm[J]. Future Computing and Informatics Journal，2018， 3（2）： 200-209.

[4] TLEIS M，CALLIERIS R，ROMA R. Segmenting the organic food market in Lebanon： an application of K-means cluster analysis[J]. British Food Journal， 2017， 119（7）： 1423-1441.

[5] HUNG P D，NGOC ND，HANH T D. K-means clustering using R A case study of market segmentation[C]. Proceedings of the 2019 5th International Conference on E-Business and Applications，2019：100-104.

[6] TANG J L，WANG D，ZHANG Z G，et al.Weed identification based on K-means feature learning combined with convolutional neural network[J]. Computers and Electronics in Agriculture，2017，135： 63-70.

[7] TANG J L， ZHANG Z G， WANG D， et al. Research on weeds identification based on K-means feature learning[J]. Soft Computing， 2018， 22（22）： 7649-7658.

[8] MACQUEEN J. Some methods for classification and analysis of multivariate observations[C]. Proceedings of Berkeley Symposium on Mathematical Statistics & Probability，1965：281-297.

[9] SAROJ K. Review：study on simple K-mean and modified K-mean clustering technique[J]. International Journal of Computer Science Engineering and Technology， 2016， 6（7）：279-281.

[10] WANG X，JIAO Y，F(xiàn)EI S. Estimation of clusters number and initial centers of K-means algorithm using watershed method[C]. Guiyang： International Symposium on Distributed Computing & Applications for Business Engineering & Science， 2015.

[11] 唐東凱，王紅梅，胡明，等.? 優(yōu)化初始聚類(lèi)中心的改進(jìn)K-means算法[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 2018， 39（8）：1819-1823.

[12] 周世兵，徐振源，唐旭清.? K-means算法最佳聚類(lèi)數(shù)確定方法[J]. 計(jì)算機(jī)應(yīng)用，2010，30（8）：1995-1998.

[13] GOODE A. X-means： extending K-means with efficient estimation of the number of clusters[M]. Berlin：Springer，2000.

[14] 趙楊璐，段丹丹，胡饒敏，等. 基于EM算法的混合模型中子總體個(gè)數(shù)的研究[J]. 數(shù)理統(tǒng)計(jì)與管理， 2020， 39（1）：35-50.

[15] 謝娟英，王艷娥. 最小方差優(yōu)化初始聚類(lèi)中心的K-Means算法[J].? 計(jì)算機(jī)工程，2014， 40（8）：205-211，223.

[16] 周涓，熊忠陽(yáng)，張玉芳，等. 基于最大最小距離法的多中心聚類(lèi)算法[J]. 計(jì)算機(jī)應(yīng)用，2006，26 （6）：1425-1427.

[17] ANIL K J. Data clustering： 50 years beyond K-means[J]. Pattern Recognition Letters，2010， 31（8）：651-666.

[18] ARTHUR D，VASSILVITSKII S. K-means++： the advantages of careful seeding[C]. New Orleans： Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms， 2007.

[19] AGRAWL R， IMIELINSKI T， IYERB， et al. Mining K-Means rules between sets of items in large database[C]. Proceedings of ACM SIGMOD Conference on Management of Data，2013：1-10.

[20] 成衛(wèi)青，盧艷紅. 一種基于最大最小距離和SSE的自適應(yīng)聚類(lèi)算法[J]. 南京郵電大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，35（2）：102-107.

（責(zé)任編輯：江 艷）