基于核函數動態分配聚類中心的DGK-Kmeans算法
來源:用戶上傳
作者:
摘 要：Kmeans算法存在兩個主要缺陷，導致聚類結果準確率較低。為改善聚類效果，提出一種DGK-Kmeans算法。該算法選用核密度估計處理數據，得到備選聚類中心，依據平均類間相似度動態增加初始聚類中心個數，直至平均類間相似度大于前次計算值時，選取平均類內相似度最小時對應的聚類中心為初始聚類中心，進行Kmeans聚類計算。采用UCI標準數據集進行實驗，證明改進后的DGK-Kmeans算法在聚類準確率和穩定性方面有很大提高。
關鍵詞：Kmeans算法;高斯核函數;動態聚類中心
DOI：10. 11907/rjdk. 182140
中圖分類號：TP312 文獻標識碼：A 文章編號：1672-7800（2019）002-0042-03
Abstract：There are two main defects in the Kmeans algorithm which lead to lower accuracy of clustering results.In order to improve the clustering effect， a DGK-Kmeans algorithm is proposed.The algorithm uses the kernel density estimation to process the data to obtain the candidate cluster center， and dynamically increases the number of initial cluster centers according to the average inter-class similarity until the average inter-class similarity is greater than the previous calculated value， and the average intra-class similarity is selected. The cluster center corresponding to the minimum degree is Kmeans clustering calculation for the initial cluster center.The experiment uses the UCI standard data set to verify that the improved DGK-Kmeans algorithm and greatly improves the accuracy and stability of clustering.
Key Words：Kmeans clustering;Gaussian kernel function;dynamic clustering center
0 引言
Kmeans算法是一種適用于大規模數據集[1]的簡單聚類算法，但算法迭代次數受初始聚類中心和實際聚類中心偏差的影響很大，所以選擇合適的初始聚類中心是很有必要的[2]。Kmeans算法有兩個主要缺點：一是需要人工輸入聚類K值;二是隨機選擇K個初始中心[3]。
為提高Kmeans算法的性能，許多學者從不同方面對算法進行改進[4]。ALSABTI[5]選擇利用K-D樹結構對Kmeans算法進行改進。賴玉霞等[6]根據聚類對象分布密度，從K個處于高密度區域的點中選取相互距離值最遠的樣本點作為初始聚類中心。王玲等[7]提出一種基于密度敏感的相似度度量方法。程艷云等[8]提出通過定義的平均類間最大相似度指標值確定最佳K值，進而動態分配聚類中心的聚類算法。韓凌波等[9]提出按照密度大小選擇K個聚類中心的算法。馬帥等[10]選擇根據密度和參考點提高聚類算法，基本滿足聚類以適應數據集分布的特征。袁方等[11]提出一種基于樣本距離相似度及通過合適的權值初始化聚類的方法，對特定的數據集選擇合適權值進行聚類，達到了良好的效果。周涓等[12]提出基于距離大小的算法，初始聚類中心選擇的是相互之間距離最遠的K個樣本點。周世兵等[13]從樣本幾何結構的角度定義樣本聚類距離和樣本聚類離差距離，設計一種新的聚類有效指標，從而提出一種自動確定最佳聚類數量的方法。劉鳳芹等[14]提出一種基于最大距離實現K值自動生成的算法。翟東海等[15]提出基于最大距離選取初始簇中心的算法。
以上研究通過密度、權值及距離對算法進行改進，但都存在聚類精度不高、時間復雜度高等情況。因此本文提出一種基于高斯核密度、動態確定初始聚類中心的DGK-Kmeans算法（Gaussian Kernel Kmeans Algorithm）。通過實驗證明，本文算法在UCI數據集中的聚類精度高于傳統K-means算法，并且在誤差平方和方面也有很大優勢。
1 高斯核密度估計
核密度估計方法對于數據分布特征的研究從數據樣本集合本身出發，不需要利用數據分布的先驗知識或對數據樣本服從何種分布作出任何假設[16]。核函數的作用是在高維空間對輸入的空間進行特征映射后，直接在高維數據空間進行數據處理。核函數映射是非線性變換的，可確保映射出各種不同的高維特征空間[17]。
使用高斯核函數作為核平滑函數的密度估計，是一種用來估計概率密度函數的非參數方法，假定[x1，x2，？，xn]為獨立分布[F]的[n]個數據點，數據點服從的分布密度函數為[f]，函數定義為：
本文采用高斯核函數為核平滑函數，公式為：
[h]的取值公式為：
2 DGK-Kmeans算法
由于Kmeans算法聚類數需事先確定，且初始聚類中心的選取具有隨機性，因此本文提出基于高斯核密度的動態確定初始聚類中心的算法（DGK-Kmeans算法）。 2.1 相關概念及公式定義
本文采用歐氏距離定義數據之間的距離度量。
定義1 類內距離表示類中每個點到其聚類中心之間距離的均值。
其中，[ci]為類[i]聚類中心。
定義2 類間距離表示某個聚類中心到另一類聚類中心的距離。
定義3 平均類內最大相似度（AMS）表示一個類與其它類存在相似度的大小，由最大相似度取均值得到。
AMS越小則聚類效果越好，所以當AMS取得最小值時聚類效果最好，此時可獲取最佳聚類個數。
2.2 DGK-Kmeans算法
根據數據樣本位置屬性，首先進行核密度估計，從而得到一個高密度區域，然后將高密度區域通過空間分析（焦點統計，柵格計算等）提取在特定區域內密度值最高的點，得到一個極大密度點的集合，將該極大密度點集作為備選聚類中心，從備選點中選取距離最遠的兩個點作為初始聚類中心，進行初步聚類并計算平均類間最大相似度。當計算得到的平均類間最大相似度現值小于前次計算值時，則依據相對距離原則從備選點中動態選擇下一個聚類中心; 否則，將當前聚類中心當作最佳初始聚類中心后進行Kmeans聚類。
DGK-Kmeans算法執行步驟如下所示。
輸入：一個數據集中包含N個數據對象。AMS初始值、算法終止條件。
輸出：K個簇、評價函數值、算法聚類時間。
（1）使用核密度估計算法計算每個數據點，再使用焦點統計得到一個極大密度點集作為備選初始聚類點集D。
?。?）從D中選擇密度最大的一個點作為第一個初始聚類中心，D中距其最遠的點作為第二個聚類中心，將選出的兩個聚類中心放入初始聚類中心集合I中，并且將其從集合D中刪除。
（3）根據已選擇的聚類中心將N個數據點進行迭代劃分，然后計算此時AMS值。
?。?）若步驟（3）得出的AMS值小于前次AMS值或者備選聚類中心集合D不為空，則轉步驟（5）繼續執行算法;否則，選擇AMS處于最小值時的集合I，即從Kmeans聚類的初始聚類中心進入步驟（6）。
（5）從D中選擇一個到已選初始聚類中心距離的各自乘積最大的樣本點，添加至集合I，并將其從D中刪除。轉步驟（3）。
?。?）進行Kmeans聚類。
3 實驗部分
3.1 實驗描述
為了驗證DGK-Kmeans算法的有效性，本文采用UCI數據庫的4組數據集作為測試數據集。UCI數據集是對機器學習和數據挖掘的相關算法進行測試的標準數據集[18]。從數據總量、類別數和數據維度等方面選擇的4組數據集分別是Iris數據集、Wine數據集、Glass數據集和Yeast數據集，這樣可以更好地檢測改進算法的有效性?，F今對算法聚類效果的評價標準有很多種，本文采用以下3種度量指標：準確率、誤差平方和、時間性能[19-20]。
3.2 實驗結果
本文利用DGK-Kmeans算法、傳統K-means算法、文獻[8]中的動態分配聚類中心的改進K均值算法、文獻[9]中基于密度的K-means初始聚類中心選取算法，使用選取的4組測試數據集進行對比實驗。為盡量避免傳統算法容易陷入局部最優的缺陷，聚類結果取10次實驗數據的平均值。表1是4種聚類算法在4組數據集中聚類準確率比較結果。表2是4種不同聚類算法誤差平方和的比較結果。
由表1可以看出DGK-Kmeans算法在Iris數據集上的準確率比文獻[8]中的算法準確率低，在Wine和Glass數據集上，DGK-Kmeans算法準確率略高于其它3個算法，從Yeast數據集來看，DGK-Kmeans算法準確率遠遠高于其它3個算法。
由表2可以看出，與傳統算法、文獻[8]算法和文獻[9]算法相比，本文DGK-Kmeans算法誤差平方和有所降低。
圖1為4種聚類算法使用4個標準數據集時的聚類時間折線變化。
由圖1可以看出，傳統Kmeans算法和文獻[8]的算法在數據量小時，運行時間較短，但是當數據量增大時，運行時間呈指數增長。文獻[9]的算法及本文DGK-Kmeans算法在Iris、Wine和Glass數據集運行時間高于其它兩個算法，但是在數據量大的Yeast數據集中，運行時聚類時間并不像前兩個算法那樣呈指數增長。在數據總量增大的情況下與其它3個算法相比，本文DGK-Kmeans算法運行時間增長最為緩慢，在Yeast數據集下的聚類時間最短。所以在數據總量增大時，DGK-Kmeans運行時間具有很大優勢。
3.3 實驗分析
結合上面3種實驗結果可以看出，與其它3個算法相比，雖然DGK-Kmeans在數據量小、聚類數小及數據維度低時，聚類準確率沒有明顯改善，而且在Iris數據集中低于文獻[8]的算法，但是在數據量大時聚類準確率改善很明顯，在誤差平方和方面也有所改善。在運行時間方面，雖然DGK-Kmeans算法在數據量小的情況下比傳統Kmeans算法和動態分配聚類中心的算法所需時間多，但是在數據量大的情況下其聚類時間優于其它3個算法，而且DGK-Kmeans算法聚類結果十分穩定。因此DGK-Kmeans算法在準確率、誤差平方和及運行時間等方面有很大提高。
4 結語
本文提出的DGK-Kmeans算法使用核密度估計對初始聚類中心進行選取，所以經過本文算法選取得到的初始聚類中心保持不變，故該算法聚類結果較穩定。DGK-Kmeans算法可以自動獲取K值，不需要人工輸入，在準確率、誤差平方和及運行時間方面較其它算法都有很大改進，在數據量大的情況下，大幅縮短了運行時間。但是在數據量小的情況下，本文算法運行時間較其它算法略長，所以在數據量小的情況下如何降低時間復雜度，是下一步需要解決的問題。 參考文獻：
[1] 戴濤. 聚類分析算法研究[D]. 北京：清華大學， 2005.
[2] 柯良文， 王靖. 基于用戶相似度遷移的協同過濾推薦算法[J]. 微型機與應用， 2014（14）：71-74.
[3] 倪志偉. 動態數據挖掘[M]. 北京：科學出版社， 2010.
[4] 莫錦萍，陳琴，馬琳，等. 一種新的K-Means蟻群聚類算法[J]. 廣西科學院學報，2008，24（4）：284-286
[5] ALSABTI K，RANKA S，SINGH V. An efficient K-means clustering algorithm[C]. Proceedings of IPPS/SPDP Workshop on High Performance Data Mining， 1997.
[6] 賴玉霞， 劉建平. K-means算法的初始聚類中心的優化[J]. 計算機工程與應用， 2008， 44（10）：147-149.
[7] 王玲， 薄列峰， 焦李成. 密度敏感的譜聚類[J]. 電子學報，2007， 35（8）：1577-1581.
[8] 程艷云，周鵬. 動態分配聚類中心的改進K均值聚類算法[J]. 計算機技術與發展，2017， 27（2）：33-36.
[9] 韓凌波，王強，蔣正鋒，等. 一種改進的K-means初始聚類中心選取算法[J]. 計算機工程與應用， 2010， 46（17）：150-152.
[10] 馬帥，王騰蛟，唐世渭，等. 一種基于參考點和密度的快速聚類算法[J]. 軟件學報，2003， 14（6）：1089-1095.
[11] 袁方，孟增輝，于戈. 對k-means聚類算法的改進[J]. 計算機工程與應用， 2004， 40（36）：177-178.
[12] 周涓， 熊忠陽，張玉芳，等. 基于最大最小距離法的多中心聚類算法[J]. 計算機應用，2006，26（6）：1425-1427.
[13] 周世兵，徐振源，唐旭清. K-means算法最佳聚類數確定方法[J]. 計算機應用，2010，30（8）：1995-1998.
[14] 劉鳳芹. K-means聚類算法改進研究[D]. 濟南：山東師范大學， 2013.
[15] 翟東海，魚江，高飛，等. 最大距離法選取初始簇中心的K-means文本聚類算法的研究[J]. 計算機應用研究，2014，31（3）：713-715.
[16] 熊開玲， 彭俊杰， 楊曉飛，等. 基于核密度估計的K-means聚類優化[J]. 計算機技術與發展， 2017， 27（2）：1-5.
[17] 趙明明， 張桂蕓， 潘冬寧，等. 基于高斯核函數的K-means聚類在分布式下的優化[J]. 軟件導刊， 2018，17（4）：64-66.
[18] 毛國君， 段立娟， 王實. 數據挖掘原理與算法[M].北京：清華大學出版社，2016.
[19] 周煒奔， 石躍祥. 基于密度的K-means聚類中心選取的優化算法[J]. 計算機應用研究， 2012， 29（5）：1726-1728.
[20] 王曉燕. K-均值算法與自組織神經網絡算法的改進研究及應用[D]. 太原：中北大學， 2017.
?。ㄘ熑尉庉嫞航?艷）
轉載注明來源:http://www.hailuomaifang.com/8/view-14803820.htm
