基于多維網(wǎng)格空間的改進(jìn)K-means聚類算法

邵 倫,周新志,趙成萍,張 旭

(四川大學(xué) 電子信息學(xué)院,成都 610065)(*通信作者電子郵箱xz.zhou@scu.edu.cn)

0 引言

聚類算法是一種典型的無監(jiān)督學(xué)習(xí)算法,是利用樣本的特征比較樣本的相似性,將具有相似屬性的樣本劃分到同一類或簇中的算法[1-5]。聚類算法的應(yīng)用廣泛,在數(shù)據(jù)挖掘、信息檢索和圖像分割等方面都有重要的作用[6-11]。迄今為止已經(jīng)衍生出了眾多的聚類算法,這些算法可以分為劃分法、層次法、密度法、圖論法、網(wǎng)格法和模型法等[5,11-14]。K-means是一種典型的基于劃分的聚類算法[12,16-17],其應(yīng)用非常普遍,但是傳統(tǒng)的K-means算法存在一些不足之處,比如隨機(jī)選擇的初始聚類中心通常是不理想的,易使最后的聚類結(jié)果局部最優(yōu),而非全局最優(yōu);另外初始聚類中心選擇的不穩(wěn)定性,也會(huì)導(dǎo)致算法迭代次數(shù)及聚類結(jié)果的不穩(wěn)定[18-19]。很多研究人員對初始聚類中心的選擇提出了優(yōu)化的方法,文獻(xiàn)[11]中提出了一種基于最小生成樹的層次K-means聚類算法,文獻(xiàn)[20]中提出了一種基于最小方差優(yōu)化初始聚類中心的K-means算法,但是這些算法在初始聚類中心選擇的效果上仍不夠理想,聚類結(jié)果的穩(wěn)定性和準(zhǔn)確性仍有待提高。

針對上述問題,本文提出了一種基于多維網(wǎng)格空間結(jié)構(gòu)優(yōu)化初始聚類中心的改進(jìn)K-means聚類算法。此算法首先根據(jù)樣本集的屬性個(gè)數(shù)n,將樣本集映射到一個(gè)包含有限個(gè)子網(wǎng)格的n維網(wǎng)格空間結(jié)構(gòu)中。其映射流程如下:以樣本集中每一類屬性的最大值和最小值作為網(wǎng)格空間中每一維度的上邊界和下邊界；接著，根據(jù)樣本的類別數(shù)k,依次將每一維度均等切分成k等份;然后，計(jì)算出每個(gè)子網(wǎng)格中的樣本數(shù),選擇包含樣本數(shù)最多且距離較遠(yuǎn)的k個(gè)子網(wǎng)格作為初始聚類中心網(wǎng)格,再計(jì)算初始聚類中心網(wǎng)格中樣本的均值點(diǎn)作為初始聚類中心;最后，依據(jù)距離作為相似性的評價(jià)標(biāo)準(zhǔn)來迭代更新聚類中心,直到找出最終的聚類中心。相對于傳統(tǒng)的K-means算法中隨機(jī)選擇初始聚類中心的方法,本文算法基于多維網(wǎng)格空間目的性選擇的初始聚類中心與實(shí)際聚類中心接近,使得算法的迭代次數(shù)明顯減少,聚類結(jié)果穩(wěn)定且錯(cuò)誤率較低。

1 多維網(wǎng)格空間的設(shè)計(jì)

需要進(jìn)行聚類分析的數(shù)據(jù)集其數(shù)據(jù)量往往較大,并且數(shù)據(jù)屬性往往有多個(gè),在這一大堆數(shù)據(jù)中隨機(jī)選擇初始聚類中心,通常很難選中與實(shí)際聚類中心相近的樣本點(diǎn)作為初始聚類中心。設(shè)想將數(shù)據(jù)集映射到一個(gè)多維的網(wǎng)格空間中,由于數(shù)據(jù)樣本各屬性值的差異,數(shù)據(jù)集就被分散到了多個(gè)小的子網(wǎng)格之中,那么數(shù)據(jù)集便以空間化的形式得到?；Ａ硗?由于數(shù)據(jù)集中包含多個(gè)不同類別的樣本,而不同類別的樣本間屬性值差異一般較大,因而分布在各個(gè)子網(wǎng)格中的樣本數(shù)必定會(huì)存在差異,而且在同一子網(wǎng)格中的樣本必定是距離相近的樣本,即同一子網(wǎng)格中的樣本很有可能屬于同一類別。由此,有理由認(rèn)為含樣本數(shù)最多且距離較遠(yuǎn)的子網(wǎng)格是包含有實(shí)際聚類中心或者與實(shí)際聚類中心接近的網(wǎng)格,那么在此子網(wǎng)格中選定初始聚類中心便是與實(shí)際聚類中心最接近的,此子網(wǎng)格亦被稱為初始聚類中心網(wǎng)格。

基于多維網(wǎng)格空間選擇初始聚類中心網(wǎng)格,其網(wǎng)格空間中子網(wǎng)格的個(gè)數(shù)對于選擇出完美的初始聚類中心網(wǎng)格至關(guān)重要:過多的子網(wǎng)格會(huì)使對樣本集的切分過度細(xì)化,出現(xiàn)較多包含樣本點(diǎn)個(gè)數(shù)無差異的子網(wǎng)格,對初始聚類中心網(wǎng)格的選擇產(chǎn)生干擾;過少的子網(wǎng)格又無法將樣本集中的所有類別完全切分開,出現(xiàn)一個(gè)子網(wǎng)格中包含較多多個(gè)類別的樣本,導(dǎo)致最終無法正確選擇初始聚類中心網(wǎng)格。如果按照數(shù)據(jù)集的類別數(shù)k來切分?jǐn)?shù)據(jù)集,即將數(shù)據(jù)集所映射的多維空間結(jié)構(gòu)中每一維度均等切分為k份,則所得子網(wǎng)格數(shù)最為合理,切分好后多維網(wǎng)格空間的子網(wǎng)格數(shù)為kn(n為數(shù)據(jù)集的屬性個(gè)數(shù))。

1.1 二維網(wǎng)格空間

假設(shè)如圖1所示的樣本集為X={X(1),X(2), …,X(m)},包含m個(gè)樣本,共3類數(shù)據(jù)(即k=3),其中X(i)=(x(i),y(i))為單個(gè)樣本,并且包含x(i)和y(i)(i∈{1, 2, …,m})兩個(gè)屬性特征。那么將樣本集X映射到二維網(wǎng)格空間中,其每一維度均等切分3份,則切分后該二維網(wǎng)格空間包含9個(gè)同等形狀和大小的子網(wǎng)格,如圖2所示。其中，(x0,y0)小于或等于樣本集中最小的點(diǎn),(x3,y3)大于或等于樣本集中最大的點(diǎn),即：

?i∈{1,2,…,m},有

(1)

(2)

令屬性特征x(i)所代表的維度的切分步長為dx,屬性特征y(i)所代表的維度的切分步長為dy,有

dx=(xmax-xmin)/3

(3)

dy=(ymax-ymin)/3

(4)

易知,xi=xi-1+dx和yi=yi-1+dy,其中i∈{1, 2, 3}。

為了方便標(biāo)記二維網(wǎng)格空間中的子網(wǎng)格和記錄每個(gè)子網(wǎng)格中樣本點(diǎn)的個(gè)數(shù),以(x0,x1;y0,y1)表示圖2中左邊下方的子網(wǎng)格,在此表示形式中,x0和y0分別稱之為此子網(wǎng)格第1維度上和第2維度上的前界,x1和y1分別稱之為此子網(wǎng)格第1維度上和第2維度上的后界,將此子網(wǎng)格中的樣本點(diǎn)數(shù)記為w1;以(x0,x1;y1,y2)表示圖2中左邊中間的子網(wǎng)格,并將此子網(wǎng)格中的樣本點(diǎn)數(shù)記為w2;依照此法,最后(x2,x3;y2,y3)表示圖2中右邊上方的子網(wǎng)格,并將此子網(wǎng)格中的樣本點(diǎn)數(shù)記為w9。最終,可以得到樣本集X映射到二維網(wǎng)格空間后各個(gè)子網(wǎng)格中樣本點(diǎn)個(gè)數(shù)的分布為{w1,w2, …,w9},如圖2所示,虛線框所標(biāo)出的子網(wǎng)格(x0,x1;y2,y3)、(x1,x2;y0,y1)、(x2,x3;y2,y3)中的樣本點(diǎn)數(shù)分別為w3、w4、w9。可以看出這3個(gè)子網(wǎng)格中樣本數(shù)最多并且它們的距離較遠(yuǎn),故樣本集X的3個(gè)初始聚類中心網(wǎng)格就選擇這3個(gè)子網(wǎng)格。

圖1 二維屬性數(shù)據(jù)集Fig. 1 Data set with two-dimensional attribute feature

圖2 基于二維網(wǎng)格空間選擇初始聚類中心網(wǎng)格Fig. 2 Initial cluster center grid selection based on two-dimensional grid space

1.2 三維網(wǎng)格空間

三維網(wǎng)格空間的設(shè)計(jì)及數(shù)學(xué)描述與二維網(wǎng)格空間基本一致。假設(shè)如圖3所示的樣本集為X={X(1),X(2), …,X(m)},包含m個(gè)樣本,共3類數(shù)據(jù),其中X(i)=(x(i),y(i),z(i))為單個(gè)樣本,并且包含3個(gè)屬性特征x(i)、y(i)和z(i),i∈{1, 2, …,m}。那么將樣本集X映射到三維網(wǎng)格空間中,如圖4所示,該三維網(wǎng)格空間包含27個(gè)同等形狀和大小的子網(wǎng)格。其中,(x0,y0,z0)小于或等于樣本集中最小的點(diǎn),(x3,y3,z3)大于或等于樣本集中最大的點(diǎn),即

?i∈{1,2,…,m},有

(5)

(6)

令屬性特征x(i)所代表的維度的切分步長為dx,屬性特征y(i)所代表的維度的切分步長為dy,屬性特征z(i)所代表的維度的切分步長為dz，有

dx=(xmax-xmin)/3

(7)

dy=(ymax-ymin)/3

(8)

dz=(zmax-zmin)/3

(9)

易知,xi=xi-1+dx、yi=yi-1+dy和zi=zi-1+dz,其中i∈{1, 2, 3}。

同樣,為了方便標(biāo)記三維網(wǎng)格空間中的子網(wǎng)格和記錄每個(gè)子網(wǎng)格中樣本點(diǎn)的個(gè)數(shù),以(x0,x1;y0,y1;z0,z1)、(x0,x1;y0,y1;z1,z2)、…、(x2,x3;y2,y3;z2,z3)表示各個(gè)子網(wǎng)格,并且各個(gè)子網(wǎng)格中樣本點(diǎn)個(gè)數(shù)的分布為{w1,w2, …,w27}。如圖4所示,粗虛線框所標(biāo)出的子網(wǎng)格(x0,x1;y2,y3;z1,z2)、(x1,x2;y0,y1;z0,z1)和(x2,x3;y0,y1;z2,z3)中的樣本點(diǎn)數(shù)分別為w8、w10、w21,可以看出這3個(gè)子網(wǎng)格中樣本數(shù)最多并且它們的距離較遠(yuǎn),故樣本集X選擇這3個(gè)子網(wǎng)格作為初始聚類中心網(wǎng)格。

圖3 三維屬性數(shù)據(jù)集Fig. 3 Data set with three dimensional attribute feature

圖4 基于三維網(wǎng)格空間選擇初始聚類中心網(wǎng)格Fig. 4 Initial cluster center grid selection based on three-dimensional grid space

1.3 n維網(wǎng)格空間

?i∈{1,2,…,m},有

(10)

其中:j∈{1, 2, …,n}。

dj=(xj_max-xj_min)/k

(11)

其中:j∈{1, 2, …,n}。

記(x1_min,x1_min+d1;x2_min,x2_min+d2; …;xn_min,xn_min+dn)、 (x1_min,x1_min+d1;x2_min,x2_min+d2; …;xn_min,xn_min+2dn)、 …、 (x1_min+(ε-1)d1,x1_min+εd1;x2_min+(ε-1)d2,x2_min+εd2; …;xn_min+(ε-1)dn,xn_min+εdn)、 …、 (x1_min+(k-1)d1,x1_max;x2_min+(k-1)d2,x2_max; …;xn_min+(k-1)dn,xn_max)是各個(gè)子網(wǎng)格的表示形式,分號將子網(wǎng)格每一維度的前界和后界隔開,前界和后界又以逗號隔開,其中ε∈{1, 2, …,k},并且各個(gè)子網(wǎng)格中樣本點(diǎn)個(gè)數(shù)的分布為{w1,w2, …,wkn}。

在選擇初始聚類中心網(wǎng)格時(shí),要考慮到的一個(gè)重要指標(biāo)是各初始聚類中心網(wǎng)格之間的距離要比較遠(yuǎn),下面給出此指標(biāo)的判斷公式:

令兩個(gè)子網(wǎng)格之間的距離為D,有

(12)

或

(13)

若D滿足式(14),則認(rèn)為這兩個(gè)子網(wǎng)格之間的距離較遠(yuǎn)。

?j∈{1,2,…,n},有

D≥(k/2)×max{dj}

(14)

2 K-means算法的改進(jìn)

本文對傳統(tǒng)K-means算法的改進(jìn)主要在于對初始聚類中心的選擇方式作出了良好的改進(jìn),傳統(tǒng)K-means算法是通過隨機(jī)的方式選擇出k個(gè)初始聚類中心,而本文算法是基于多維網(wǎng)格空間結(jié)構(gòu)選擇出k個(gè)初始聚類中心,多維網(wǎng)格空間以子網(wǎng)格的形式將數(shù)據(jù)集中屬性相似的樣本包裹、屬性差異較大的樣本隔離,此方法選擇出來的初始聚類中心擺脫了隨機(jī)性,并且基本接近實(shí)際的聚類中心。

算法具體流程:

1)輸入包含m個(gè)樣本的數(shù)據(jù)集X={X1,X2, …,Xm},其中每一個(gè)樣本Xi為n維向量,其中n為樣本屬性個(gè)數(shù),i∈{1, 2, …,m}。

2)初始化樣本類別k,將數(shù)據(jù)集映射到虛擬的n維網(wǎng)格空間結(jié)構(gòu)中。

詳細(xì)步驟:首先,找到第1個(gè)屬性的最大值和最小值,根據(jù)式(11)計(jì)算出步長,按照該步長將數(shù)據(jù)集分成k份;然后,再找到第2個(gè)屬性的最大值和最小值,計(jì)算出步長,按照該步長將上一步分得的k份中的每一份再分成k份;依次遞推,直到將數(shù)據(jù)集分成kn份,即完成將數(shù)據(jù)集映射到n維網(wǎng)格空間結(jié)構(gòu)中了。

3)根據(jù)上一步構(gòu)造網(wǎng)格空間結(jié)構(gòu)的遞進(jìn)規(guī)則,依次計(jì)算每一個(gè)子網(wǎng)格中樣本點(diǎn)的個(gè)數(shù),得到{w1,w2, …,wkn}。

4)選擇k個(gè)包含樣本數(shù)最多,且兩兩之間距離D滿足式(14)的初始聚類中心網(wǎng)格{G1,G2, …,Gk},再在各初始聚類中心網(wǎng)格中計(jì)算出其內(nèi)含樣本點(diǎn)的均值點(diǎn),得到k個(gè)初始聚類中心{C1,C2, …,Ck},即：

其中:q∈{1,2,…,k};|Xi∈Gq|表示Gq所包含樣本的個(gè)數(shù)。

5)依據(jù)K-means算法迭代步驟,更新聚類中心,直到最終聚類中心不再改變便停止迭代。

計(jì)算每個(gè)樣本與每個(gè)初始聚類中心之間的相似度,將樣本劃分到最相似的類別中,即,若Xi與Cq之間歐氏距離d(Xi,Cq)最小,則Xi屬于類別Cq。

計(jì)算劃分到每個(gè)類別中的所有樣本特征的均值,并將各均值作為各類新的聚類中心,重復(fù)步驟5)直到最終的聚類中心不再改變或達(dá)到最大迭代次數(shù)時(shí)停止更新聚類中心,即新的聚類中心有：

6)輸出最終的聚類中心,以及每個(gè)樣本所屬的類別。

本文算法主要由兩部分組成:第一部分是選擇初始聚類中心,時(shí)間主要花費(fèi)在將數(shù)據(jù)集映射到多維網(wǎng)格空間上,這部分的時(shí)間復(fù)雜度為O(knm)；第二部分是根據(jù)初始聚類中心來迭代更新聚類中心，這部分的時(shí)間復(fù)雜度與傳統(tǒng)K-Means算法的時(shí)間復(fù)雜度一樣為O(tknm)。兩部分的時(shí)間復(fù)雜度相加即為本文算法的時(shí)間復(fù)雜度,所以本文算法的時(shí)間復(fù)雜度為O(tknm)；另外,空間復(fù)雜度為O((k+m)×n),其中：t表示迭代次數(shù),k表示樣本集類別個(gè)數(shù),n表示樣本屬性個(gè)數(shù),m表示樣本數(shù)。

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

為了充分驗(yàn)證本文算法的效果,實(shí)驗(yàn)分為兩個(gè)階段:第一階段采用計(jì)算機(jī)模擬的二維數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù),對傳統(tǒng)的K-means算法和本文的基于多維網(wǎng)格空間的改進(jìn)K-means算法進(jìn)行可視化對比;第二階段采用三個(gè)UCI數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù),分別對傳統(tǒng)K-means算法、文獻(xiàn)[11]算法、文獻(xiàn)[20]算法和本文算法進(jìn)行對比。實(shí)驗(yàn)環(huán)境是Windows 10操作系統(tǒng),Intel Core i7-8550U處理器,8 GB內(nèi)存,Python編程語言。

3.1 模擬數(shù)據(jù)集測試實(shí)驗(yàn)

計(jì)算機(jī)模擬的數(shù)據(jù)集具有4個(gè)類別,包含80個(gè)二維數(shù)據(jù),如圖5所示。通過此數(shù)據(jù)集分別對K-means算法和本文提出的改進(jìn)算法進(jìn)行聚類實(shí)驗(yàn),各經(jīng)過60次重復(fù)實(shí)驗(yàn)后,在實(shí)驗(yàn)結(jié)果中各隨機(jī)挑選三組,如圖6所示是K-means算法得到的三組實(shí)驗(yàn)結(jié)果。圖7所示是本文的改進(jìn)算法得到的三組實(shí)驗(yàn)結(jié)果,其中十字點(diǎn)為初始聚類中心,星形點(diǎn)為最終的聚類中心。對比這三組實(shí)驗(yàn)結(jié)果可以看出，K-means算法的初始聚類中心選擇的隨機(jī)性導(dǎo)致了迭代次數(shù)和聚類結(jié)果的不穩(wěn)定,其中圖6(b)所示的聚類結(jié)果B陷入了局部最優(yōu),與實(shí)際聚類中心的偏離非常大;而本文的改進(jìn)算法的初始聚類中心非常穩(wěn)定且與實(shí)際聚類中心距離較近,故算法迭代次數(shù)較少,最終的聚類結(jié)果準(zhǔn)確和穩(wěn)定。

圖5 模擬的二維數(shù)據(jù)集Fig. 5 Simulated two-dimensional data set

3.2 UCI數(shù)據(jù)集測試實(shí)驗(yàn)

表1 UCI數(shù)據(jù)集描述Tab. 1 UCI data set description

三個(gè)UCI數(shù)據(jù)集Iris、Wine和Seeds的描述如表1所示。利用這三個(gè)數(shù)據(jù)集分別對傳統(tǒng)K-means算法、文獻(xiàn)[11]算法、文獻(xiàn)[20]算法和本文算法進(jìn)行了40次重復(fù)實(shí)驗(yàn),記錄每一次的迭代次數(shù)和錯(cuò)誤率,實(shí)驗(yàn)結(jié)果如表2所示。從表2中四種算法的迭代次數(shù)可以看出，K-means算法的最大迭代次數(shù)基本都是最小迭代次數(shù)的4倍左右,迭代次數(shù)的不穩(wěn)定是較為突出的問題;而本文算法的迭代次數(shù)是穩(wěn)定不變的,非常接近K-means算法的最小迭代次數(shù)且略小于文獻(xiàn)[11]和文獻(xiàn)[20]算法的迭代次數(shù)。實(shí)驗(yàn)結(jié)果表明基于多維網(wǎng)格空間選擇初始聚類中心對算法的收斂速度有較為明顯的提升。

表2 4種算法在不同數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Tab. 2 Experimental results of four algorithms on different data sets

圖6 K-means算法隨機(jī)抽取的三組實(shí)驗(yàn)結(jié)果Fig. 6 Three groups of randomly selected experimental results of K-means algorithm

再對比四種算法的錯(cuò)誤率,可以發(fā)現(xiàn)K-means算法的最大錯(cuò)誤率一般是最小錯(cuò)誤率的2到3倍;而本文算法的錯(cuò)誤率穩(wěn)定不變,并且都低于K-means、文獻(xiàn)[11]和文獻(xiàn)[20]算法的平均錯(cuò)誤率。

圖7 改進(jìn)的K-means算法隨機(jī)抽取的三組實(shí)驗(yàn)結(jié)果Fig. 7 Three groups of randomly selected experimental results of the improved K-means algorithm

4 結(jié)語

本文提出的基于多維網(wǎng)格空間優(yōu)化的K-means算法,其核心是通過多維網(wǎng)格空間分解數(shù)據(jù)集,凸顯同類別數(shù)據(jù)之間的凝聚性和不同類別數(shù)據(jù)之間的距離差,從而選擇出與實(shí)際聚類中心較為接近的初始聚類中心,克服了傳統(tǒng)K-means算法易陷入局部最優(yōu)，算法迭代次數(shù)和聚類結(jié)果不穩(wěn)定的缺點(diǎn)。本文算法的聚類結(jié)果仍然依賴于距離作為相似性的度量方式,在接下來的工作中,將重點(diǎn)研究相似性的度量方式,在距離的基礎(chǔ)上再綜合考慮密度和屬性間的相關(guān)系數(shù)等,探求從單一的相似性度量方式轉(zhuǎn)變?yōu)榫C合的相似性度量方式,以實(shí)現(xiàn)更低錯(cuò)誤率的聚類結(jié)果。