融合了K近鄰與密度峰值算法的K-means算法

王煒唯 周云才

摘要：初始聚類中心的隨機(jī)選擇，根據(jù)主觀經(jīng)驗(yàn)確定類簇?cái)?shù)等問題時(shí)常伴隨著原始K - means算法。為了攻克以上問題，改進(jìn)算法采用峰值法以及融合了K近鄰算法的密度峰值算法逐一調(diào)整。通過在UCI數(shù)據(jù)集上測(cè)試及與原始K - means算法、最大最小距離距離算法在準(zhǔn)確率、穩(wěn)定性和處理數(shù)據(jù)速率方面的比較，其中最為突出的是，改進(jìn)算法的準(zhǔn)確率達(dá)到了96%以上。

關(guān)鍵詞：K-means算法;PCA降維;峰值法;KDPC算法

中圖分類號(hào)：TP301.6? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2021）08-0182-03

Abstract：The random selection of the initial clustering centers， and the determination of the number of clustering based on subjective experience often accompany the original K-means algorithm. In order to overcome the problems， the algorithm used Peak method and the fusion of the density peak algorithm and K-nearest neighbor algorithm to adjusted K-means algorithm. The most prominent of these is that the accuracy of the improved algorithm has reached more than 96% through testing on the UCI dataset and comparing with the original K-meaning algorithm， the maximum and minimum distance algorithm in terms of accuracy， stability and processing data rate.

Key words： K-means algorithm; shannon entropy; improved DPC algorithm

1 引言

近年來，數(shù)據(jù)大爆炸引發(fā)了人們對(duì)數(shù)據(jù)分析的需求，數(shù)據(jù)挖掘技術(shù)應(yīng)運(yùn)而生。而K-means算法在數(shù)據(jù)挖掘中處于重要地位。因其具有簡(jiǎn)單易懂、容易實(shí)現(xiàn)、時(shí)間復(fù)雜度低，處理龐大數(shù)據(jù)集效率更高等優(yōu)點(diǎn)，所以在工作中常常成為首要的選擇。然而在該算法也會(huì)產(chǎn)生不容忽略的問題[1-4]：①類簇?cái)?shù)需要根據(jù)經(jīng)驗(yàn)人工確定;②初始類中心的選擇是隨機(jī)的。

針對(duì)上述的不足，本文對(duì)算法做了以下改進(jìn)：首先利用香農(nóng)熵改進(jìn)歐式距離計(jì)算公式，提高樣本點(diǎn)相似度計(jì)算的精度;其次同時(shí)使用峰值法、融合了K近鄰算法的密度峰值算法（簡(jiǎn)稱KDPC算法）自動(dòng)確定類簇?cái)?shù)及精準(zhǔn)的初始類心。論文的實(shí)驗(yàn)數(shù)據(jù)顯示，改進(jìn)后的算法（簡(jiǎn)稱KDPCK-means算法）聚類結(jié)果十分貼近真實(shí)數(shù)據(jù)分布，算法性能較高。

2 原始K-means算法

2.1 原始K-means算法原理

K-means算法是經(jīng)典的無監(jiān)督聚類算法[5-7]，在對(duì)數(shù)據(jù)處理前無須知道數(shù)據(jù)真實(shí)類別，直接以數(shù)據(jù)相似度判斷函數(shù)來估量數(shù)據(jù)間的相似度，將整體未知類別的數(shù)據(jù)集劃分成不同的數(shù)據(jù)簇。K-means 算法的執(zhí)行過程是：

1） 根據(jù)對(duì)數(shù)據(jù)集X的先驗(yàn)知識(shí)，確定數(shù)據(jù)集X的類簇?cái)?shù)k;

2） 在X中隨機(jī)選取k個(gè)數(shù)據(jù)點(diǎn)作首次聚類的k個(gè)類簇的類心ci（i = 1，2，...，k），同樣地，每個(gè)聚類中心也有d維屬性即cij（j = 1，2，...， d）;

3） 計(jì)算除類心點(diǎn)以外的剩余數(shù)據(jù)對(duì)象與這k個(gè)類心的相似度，根據(jù)計(jì)算結(jié)果，將這些剩余數(shù)據(jù)對(duì)象分配給最相似的那個(gè)類心所屬類別，最終形成k個(gè)類簇Ci。相似度計(jì)算一般使用歐式距離計(jì)算公式：

4） 重新計(jì)算各個(gè)新得到的類簇Ci中所有數(shù)據(jù)對(duì)象d個(gè)維度的均值，將計(jì)算結(jié)果賦值給聚類中心。然后重復(fù)步驟c、d直至聚類目標(biāo)函數(shù)收斂。目標(biāo)函數(shù)的定義如下：

式中的x代表屬于簇Ci的所有數(shù)據(jù)對(duì)象。

2.2 原始K-means算法缺陷分析及改進(jìn)

根據(jù)2.1節(jié)中的算法思想可知，原始K-means算法存在諸多如下缺陷。

1） 數(shù)據(jù)集的最佳聚類數(shù)k根據(jù)對(duì)數(shù)據(jù)的先驗(yàn)知識(shí)確定，缺乏客觀科學(xué)性。針對(duì)該問題，本文提出峰值法來決此問題。

2） 本文利用原始K-means算法對(duì)10維以上數(shù)據(jù)集聚類時(shí)發(fā)現(xiàn)，該算法對(duì)10維以上的數(shù)據(jù)集聚類效果很差，因此本文在面對(duì)高維數(shù)據(jù)集時(shí)，先對(duì)其降維處理，以便得到較好的聚類效果。

3） 當(dāng)初始聚類中心選到含有相同類簇的數(shù)據(jù)對(duì)象時(shí)，聚類結(jié)果將會(huì)偏離真實(shí)數(shù)據(jù)分布情況，生成局部最優(yōu)解。針對(duì)該問題，本文利用融合了K近鄰算法的密度峰值算法加以解決。

3 原始K-means算法的改進(jìn)

3.1 峰值法確定數(shù)據(jù)集的最佳類別

實(shí)驗(yàn)證實(shí)，最佳聚類數(shù)范圍為[2，Int（[n]）][8]。本文經(jīng)過大量實(shí)驗(yàn)發(fā)現(xiàn)以Calinski-Harabasz系數(shù)（CH）為指標(biāo)，得到各數(shù)據(jù)集的最佳聚類數(shù)最準(zhǔn)確。同時(shí)，由于K-means算法對(duì)高維數(shù)據(jù)集聚類效果差，本文在對(duì)高維數(shù)據(jù)集聚類前采用能最大保留數(shù)據(jù)信息的PCA降維。峰值法選取最佳聚類數(shù)的過程如下：

1） 判斷數(shù)據(jù)集維數(shù)，若數(shù)據(jù)集超過10維，先對(duì)數(shù)據(jù)集采用PCA降維，然后計(jì)算數(shù)據(jù)集的最佳聚類數(shù)范圍;

2） 在該范圍內(nèi)取不同的整數(shù)k值，對(duì)每個(gè)確定的k值用原始K-means算法對(duì)該數(shù)據(jù)集聚類10次，得到不同k值對(duì)應(yīng)的最佳CH值。CH系數(shù)定義如下：

Ci表示簇Ci的類心，ni表示簇Ci擁有的數(shù)據(jù)總數(shù)，cM表示整個(gè)數(shù)據(jù)集的中心即均值，n表示整體數(shù)據(jù)集的數(shù)據(jù)數(shù)，即CH值越大，聚類效果越好。

3） 根據(jù)b步驟，以k為橫坐標(biāo)，CH系數(shù)為縱坐標(biāo)，畫出對(duì)應(yīng)的折線圖，選擇圖中的峰值點(diǎn)對(duì)應(yīng)的k值即為該數(shù)據(jù)集的最佳類別數(shù)。

3.2 KDPC算法

根據(jù)大多數(shù)據(jù)集中樣本點(diǎn)的分布可知，類心常被其他樣本點(diǎn)環(huán)繞，且各個(gè)類心之間相隔較遠(yuǎn)。而這一特點(diǎn)正好符合DPC算法應(yīng)用的前提條件。因此該算法可以很好地解決原始K-means算法中首次聚類類心隨意選擇的問題。然而該算法在計(jì)算樣本點(diǎn)局部密度值時(shí)未考慮鄰近樣本點(diǎn)的分布且在選取初始聚類中心時(shí)，仍依賴人工選擇，因此本文提出KDPC算法，具體過程如下：

1） 樣本點(diǎn)局部密度的計(jì)算：

（1）? 引入?yún)?shù)K結(jié)合賦權(quán)歐式距離來計(jì)算截?cái)嗑嚯xdc：

上式中的N代表樣本點(diǎn)總數(shù)，（4）式表示距離樣本點(diǎn)i最鄰近的第K個(gè)樣本點(diǎn)間的賦權(quán)歐氏距離，（6）式等號(hào)右邊的第二項(xiàng)是每個(gè)樣本點(diǎn)的第K最鄰近賦權(quán)歐氏距離與所有樣本點(diǎn)的第K最鄰近賦權(quán)歐氏距離的均值的標(biāo)準(zhǔn)差。

2） 樣本點(diǎn)i的距離計(jì)算：

根據(jù)上式結(jié)果，將其降序排列，然后以γ為縱軸，點(diǎn)的標(biāo)號(hào)為橫軸，建立平面直角坐標(biāo)系。靠近近橫軸、更平滑密集是非類簇中心，而類簇中心遠(yuǎn)離橫軸，且相對(duì)分散，類簇中心點(diǎn)與非類簇中心間界限較明顯。在自動(dòng)選取初始類心前需要結(jié)合3.1節(jié)的峰值法選擇排在前k位的點(diǎn)作為初始類心。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)概述

本文在下圖所示的數(shù)據(jù)集上，通過與原始K-means算法、最大最小距離聚類算法的準(zhǔn)確度、穩(wěn)定性和收斂速度的比較來檢驗(yàn)KDPCK-means算法的改進(jìn)是否有效。

4.2 實(shí)驗(yàn)展示與分析

由于文本篇幅限制，下文主要展示本文算法在Iris數(shù)據(jù)集上的運(yùn)行效果。

由圖1可知：Iris數(shù)據(jù)集有3個(gè)γ值凸出的間斷點(diǎn)，最佳聚類數(shù)為3，將前3個(gè)最大的γ值點(diǎn)作為Iris數(shù)據(jù)集的初始類心。

由表2可知，KDPCK-means算法得到的初始類心、最終類心與Iris數(shù)據(jù)集真實(shí)類心十分接近。

在這兩種數(shù)據(jù)集中，KDPCK-means算法的精確度顯優(yōu)于前兩種算法，其迭代次數(shù)也明顯少于前兩種算法。通過以上實(shí)驗(yàn)數(shù)據(jù)可知，KDPCK-means算法在一舉解決了原始K-means算法中問題的同時(shí)，在準(zhǔn)確率、穩(wěn)定性及運(yùn)行效率上都得到了有效的提升。

參考文獻(xiàn)：

[1] Al Hasib A，Cebrian J M，Natvig L.A vectorized k-means algorithm for compressed datasets：design and experimental analysis[J].The Journal of Supercomputing，2018，74（6）：2705-2728.

[2] Douzas G，Bacao F，Last F.Improving imbalanced learning through a heuristic oversampling method based on k-means and SMOTE[J].Information Sciences，2018，465：1-20.

[3] García J，Crawford B，Soto R，et al.A k-means binarization framework applied to multidimensional knapsack problem[J].Applied Intelligence，2018，48（2）：357-380.

[4] Manju V N，Lenin Fred A.AC coefficient and K-means cuckoo optimisation algorithm-based segmentation and compression of compound images[J].IET Image Processing，2018，12（2）：218 -225.

[5] 陳思敏.基于位置指紋識(shí)別的WiFi室內(nèi)定位算法研究與實(shí)現(xiàn)[D].南京：南京郵電大學(xué)，2016.

[6] 韓雅雯.kmeans聚類算法的改進(jìn)及其在信息檢索系統(tǒng)中的應(yīng)用[D].昆明：云南大學(xué)，2016.

[7] 孔超.基于分布式平臺(tái)的高校網(wǎng)絡(luò)輿情分析系統(tǒng)研究與實(shí)現(xiàn)[D].成都：電子科技大學(xué)，2017.

[8] 郭靖.K-means聚類算法改進(jìn)研究[D].北京：中國(guó)人民公安大學(xué)，2018.

【通聯(lián)編輯：李雅琪】