張晉逢 孫忠林

摘 要：Kmeans算法存在兩個(gè)主要缺陷，導(dǎo)致聚類結(jié)果準(zhǔn)確率較低。為改善聚類效果，提出一種DGK-Kmeans算法。該算法選用核密度估計(jì)處理數(shù)據(jù)，得到備選聚類中心，依據(jù)平均類間相似度動(dòng)態(tài)增加初始聚類中心個(gè)數(shù)，直至平均類間相似度大于前次計(jì)算值時(shí)，選取平均類內(nèi)相似度最小時(shí)對(duì)應(yīng)的聚類中心為初始聚類中心，進(jìn)行Kmeans聚類計(jì)算。采用UCI標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，證明改進(jìn)后的DGK-Kmeans算法在聚類準(zhǔn)確率和穩(wěn)定性方面有很大提高。

關(guān)鍵詞：Kmeans算法;高斯核函數(shù);動(dòng)態(tài)聚類中心

DOI：10. 11907/rjdk. 182140

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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算法是一種適用于大規(guī)模數(shù)據(jù)集[1]的簡單聚類算法，但算法迭代次數(shù)受初始聚類中心和實(shí)際聚類中心偏差的影響很大，所以選擇合適的初始聚類中心是很有必要的[2]。Kmeans算法有兩個(gè)主要缺點(diǎn)：一是需要人工輸入聚類K值;二是隨機(jī)選擇K個(gè)初始中心[3]。

為提高Kmeans算法的性能，許多學(xué)者從不同方面對(duì)算法進(jìn)行改進(jìn)[4]。ALSABTI[5]選擇利用K-D樹結(jié)構(gòu)對(duì)Kmeans算法進(jìn)行改進(jìn)。賴玉霞等[6]根據(jù)聚類對(duì)象分布密度，從K個(gè)處于高密度區(qū)域的點(diǎn)中選取相互距離值最遠(yuǎn)的樣本點(diǎn)作為初始聚類中心。王玲等[7]提出一種基于密度敏感的相似度度量方法。程艷云等[8]提出通過定義的平均類間最大相似度指標(biāo)值確定最佳K值，進(jìn)而動(dòng)態(tài)分配聚類中心的聚類算法。韓凌波等[9]提出按照密度大小選擇K個(gè)聚類中心的算法。馬帥等[10]選擇根據(jù)密度和參考點(diǎn)提高聚類算法，基本滿足聚類以適應(yīng)數(shù)據(jù)集分布的特征。袁方等[11]提出一種基于樣本距離相似度及通過合適的權(quán)值初始化聚類的方法，對(duì)特定的數(shù)據(jù)集選擇合適權(quán)值進(jìn)行聚類，達(dá)到了良好的效果。周涓等[12]提出基于距離大小的算法，初始聚類中心選擇的是相互之間距離最遠(yuǎn)的K個(gè)樣本點(diǎn)。周世兵等[13]從樣本幾何結(jié)構(gòu)的角度定義樣本聚類距離和樣本聚類離差距離，設(shè)計(jì)一種新的聚類有效指標(biāo)，從而提出一種自動(dòng)確定最佳聚類數(shù)量的方法。劉鳳芹等[14]提出一種基于最大距離實(shí)現(xiàn)K值自動(dòng)生成的算法。翟東海等[15]提出基于最大距離選取初始簇中心的算法。

以上研究通過密度、權(quán)值及距離對(duì)算法進(jìn)行改進(jìn)，但都存在聚類精度不高、時(shí)間復(fù)雜度高等情況。因此本文提出一種基于高斯核密度、動(dòng)態(tài)確定初始聚類中心的DGK-Kmeans算法（Gaussian Kernel Kmeans Algorithm）。通過實(shí)驗(yàn)證明，本文算法在UCI數(shù)據(jù)集中的聚類精度高于傳統(tǒng)K-means算法，并且在誤差平方和方面也有很大優(yōu)勢(shì)。

1 高斯核密度估計(jì)

核密度估計(jì)方法對(duì)于數(shù)據(jù)分布特征的研究從數(shù)據(jù)樣本集合本身出發(fā)，不需要利用數(shù)據(jù)分布的先驗(yàn)知識(shí)或?qū)?shù)據(jù)樣本服從何種分布作出任何假設(shè)[16]。核函數(shù)的作用是在高維空間對(duì)輸入的空間進(jìn)行特征映射后，直接在高維數(shù)據(jù)空間進(jìn)行數(shù)據(jù)處理。核函數(shù)映射是非線性變換的，可確保映射出各種不同的高維特征空間[17]。

使用高斯核函數(shù)作為核平滑函數(shù)的密度估計(jì)，是一種用來估計(jì)概率密度函數(shù)的非參數(shù)方法，假定[x1，x2，？，xn]為獨(dú)立分布[F]的[n]個(gè)數(shù)據(jù)點(diǎn)，數(shù)據(jù)點(diǎn)服從的分布密度函數(shù)為[f]，函數(shù)定義為：

本文采用高斯核函數(shù)為核平滑函數(shù)，公式為：

[h]的取值公式為：

2 DGK-Kmeans算法

由于Kmeans算法聚類數(shù)需事先確定，且初始聚類中心的選取具有隨機(jī)性，因此本文提出基于高斯核密度的動(dòng)態(tài)確定初始聚類中心的算法（DGK-Kmeans算法）。