基于核函數動態分配聚類中心的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算法）。