一種融合三支決策理論的改進(jìn)K-means算法

夏月月，張以文

(安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601)

1 引 言

“無監(jiān)督”的聚類算法旨在對(duì)無標(biāo)記的樣本進(jìn)行訓(xùn)練來發(fā)現(xiàn)數(shù)據(jù)的內(nèi)在性質(zhì)，自主地將數(shù)據(jù)集中的樣本劃分為互不相交的若干子集.通常將劃分好的數(shù)據(jù)子集稱之為“簇”.聚類分析如今已經(jīng)被應(yīng)用在許多熱門領(lǐng)域，包括數(shù)據(jù)分析、模式識(shí)別和圖像處理等[1-3].

在眾多的文獻(xiàn)中將聚類算法分為劃分聚類算法、層次聚類算法、密度聚類算法、網(wǎng)格聚類算法和模型聚類算法[4].本文聚焦于劃分聚類算法，劃分聚類算法通常要給定需要生成的簇?cái)?shù)k(k≤n)[5].其中，經(jīng)典的劃分聚類算法是K-means算法和K-medoids算法[6-8]，K-means算法根據(jù)給定的簇?cái)?shù)從數(shù)據(jù)集中隨機(jī)選擇k個(gè)樣本點(diǎn)作為初始聚類中心，根據(jù)就近分配的原則將數(shù)據(jù)集中的樣本點(diǎn)劃分到各個(gè)聚類中心所屬的簇中.K-medoids算法與K-means算法類似，只是在迭代聚類中心的過程中，K-means算法以簇中樣本點(diǎn)的平均值作為新的聚類中心，K-medoids算法選擇簇中與其他樣本點(diǎn)誤差最小的樣本點(diǎn)作為新的聚類中心.K-means++算法首先隨機(jī)選擇一個(gè)樣本點(diǎn)作為第一個(gè)初始聚類中心，再使用輪盤法選擇與已有聚類中心距離較遠(yuǎn)的樣本點(diǎn)作為下一個(gè)初始聚類中心[9].朱二周[10]等人提出的改進(jìn)K-means(ZK-means)算法是選擇樣本點(diǎn)中密度較高的點(diǎn)作為初始聚類中心.由于每個(gè)樣本點(diǎn)都只屬于一個(gè)簇，因此，K-means算法、K-medoids算法、K-means++算法和ZK-means算法屬于硬聚類算法.與之相對(duì)的軟聚類算法是將模糊集理論引入聚類分析中，根據(jù)隸屬度劃分樣本點(diǎn).Bezdek提出了fuzzy c-means(FCM)算法是應(yīng)用最為廣泛的模糊聚類算法[11].

姚一豫[12]提出的三支決策理論的核心思想是通過延遲決策來實(shí)現(xiàn)對(duì)問題的細(xì)分，將復(fù)雜問題轉(zhuǎn)化成三個(gè)較小的問題.即，當(dāng)對(duì)對(duì)象的信息掌握不足，難以判斷對(duì)象的歸屬時(shí)，通過延遲決策獲得緩沖時(shí)間用于收集信息，當(dāng)信息掌握充足后將做出最終的歸屬權(quán)判定.也就是說三支決策是最終實(shí)現(xiàn)二支決策的一個(gè)中間步驟.三支決策理論在云計(jì)算和大數(shù)據(jù)領(lǐng)域中擁有廣泛的應(yīng)用前景.將三支決策思想應(yīng)用在聚類分析中，對(duì)于數(shù)據(jù)集中的樣本判定分為三種類型，即樣本點(diǎn)對(duì)劃分好的聚簇的歸屬性為：完全屬于，部分屬于和完全不屬于.

本文主要聚焦于對(duì)K-means算法的改進(jìn)，將三支決策理論與K-means算法結(jié)合提出新的三支決策K-means算法(TK-means).經(jīng)典的K-means算法實(shí)現(xiàn)簡單、收斂速度快，但是仍然存在以下不足：初始聚類中心隨機(jī)選擇，數(shù)據(jù)處理能力有待提高，對(duì)離群點(diǎn)較為敏感.針對(duì)這些問題，三支決策理論被應(yīng)用到K-means算法中，用以提高K-means算法的性能.王平心等人[13]提出了TWKM算法就是將三支決策理論與K-means算法結(jié)合，用以區(qū)分?jǐn)?shù)據(jù)集中的核心區(qū)域和邊緣區(qū)域.但是TWKM算法是通過密度來區(qū)分?jǐn)?shù)據(jù)集中樣本點(diǎn)的屬性，時(shí)間復(fù)雜度較高.本文將三支決策理論與網(wǎng)格算法中劃分網(wǎng)格的思想應(yīng)用到K-means算法中，提出新的TK-means算法.TK-means算法的主要?jiǎng)?chuàng)新如下：

1)TK-means算法利用三支決策理論中的延遲決策的思想對(duì)邊緣區(qū)域的樣本點(diǎn)延遲處理，核心區(qū)域的樣本點(diǎn)之間的邊界更加明顯；在核心區(qū)域的樣本點(diǎn)聚類完成后，對(duì)邊緣區(qū)域的樣本點(diǎn)再處理，更易判斷其歸屬性.

2)為了規(guī)避劃分樣本點(diǎn)屬性效率較低的問題，TK-means算法結(jié)合網(wǎng)格聚類算法中劃分網(wǎng)格的思想，利用網(wǎng)格密度來快速確定核心點(diǎn)和邊緣點(diǎn)，規(guī)避對(duì)所有樣本點(diǎn)的計(jì)算從而降低算法的時(shí)間復(fù)雜度；

3)對(duì)于K-means算法初始聚類中心隨機(jī)選擇使得聚類結(jié)果不穩(wěn)定的問題，TK-means算法提出了新的利用密度法和輪盤法結(jié)合的初始聚類中心確定方法；

4)針對(duì)K-means算法對(duì)不規(guī)則數(shù)據(jù)集聚類效果較差的問題，TK-means算法采用對(duì)核心點(diǎn)和邊緣點(diǎn)不同劃分方式替換K-means算法的質(zhì)心就近劃分方法，對(duì)核心點(diǎn)采用對(duì)質(zhì)心就近劃分的原則；對(duì)邊緣點(diǎn)采用標(biāo)記樣本點(diǎn)就近劃分的原則.通過新的劃分方式可以高效的處理邊緣點(diǎn)，提高算法對(duì)不規(guī)則數(shù)據(jù)集的處理能力.

2 基礎(chǔ)理論

在介紹TK-means算法之前，首先要介紹三支決策理論和K-means算法.

2.1 三支決策理論

對(duì)于數(shù)據(jù)集D={x1,x2,…,xn}中的所有樣本點(diǎn)xi={xi1,xi2,…,xim}(m是D的維數(shù))，經(jīng)過聚類所得的結(jié)果為C={C1,C2,…,CK}.在硬聚類算法中，聚類的結(jié)果是每一個(gè)樣本點(diǎn)都隸屬于且只隸屬于一個(gè)簇.對(duì)所有的樣本點(diǎn)，存在隸屬矩陣U(D)=[uki]，其中，k=1,2,…,K;i=1,2,…,n;uki是樣本點(diǎn)xi與聚簇Ci之間的隸屬關(guān)系.硬聚類算法中的隸屬關(guān)系可以表示為：

(1)

判斷隸屬關(guān)系通常是計(jì)算樣本點(diǎn)xi={xi1,xi2,…,xim}和xj={xj1,xj2,…,xjm}之間的歐式距離：

(2)

也就是說，樣本點(diǎn)與聚簇間的關(guān)系被絕對(duì)化為兩種關(guān)系：屬于和不屬于.顯然，在實(shí)際情況下，很多樣本點(diǎn)與聚簇之間的隸屬關(guān)系存在不確定性，需要進(jìn)一步訓(xùn)練收集信息來增強(qiáng)樣本點(diǎn)的隸屬性判斷.因此，將樣本點(diǎn)與聚簇之間的隸屬關(guān)系分為三種更為有效：屬于、不屬于和不確定.Yu Hong[14]結(jié)合三支決策的思想提出了一種三支決策聚類方法(active three-way clustering method，ATC).通過將整個(gè)樣本空間分為三種區(qū)域：核心區(qū)域CoreRegion(Ci)、邊緣區(qū)域EdgeRegion(Ci)和無效區(qū)域InvalidRegion(Ci).其中，與聚簇之間的隸屬關(guān)系確定的樣本點(diǎn)(核心點(diǎn))將被投入到核心區(qū)域中，而與聚簇之間的隸屬關(guān)系不確定的樣本點(diǎn)(邊緣點(diǎn))被分配到邊緣區(qū)域中，離群樣本點(diǎn)被分配到無效區(qū)域.也就是說每一個(gè)聚簇Ci都有兩部分組成：

Ci=Co(Ci)∪Ed(Ci),Co(Ci)?D,Ed(Ci)?D

(3)

In(Ci)=D-(Co(Ci)∪Ed(Ci))

(4)

聚類完成后聚簇將整個(gè)樣本空間劃分成核心區(qū)域、邊緣區(qū)域和無效區(qū)域，對(duì)應(yīng)關(guān)系如下：

(5)

(6)

(7)

除此之外，核心點(diǎn)、邊緣點(diǎn)和離群點(diǎn)之間的關(guān)系如下：

(8)

Co(Ci)∩Ed(Ci)=φ

(9)

Co(Ci)∩In(Ci)=φ

(10)

In(Ci)∩Ed(Ci)=φ

(11)

最終的聚類結(jié)果為：

C={(Co(C1),Ed(C1)),…,(Co(CK),Ed(CK))}

(12)

2.2 K-means算法

基于劃分的聚類算法中的最為經(jīng)典的就是K-means和K-medoids算法.本文主要研究的是對(duì)K-means算法的改進(jìn).

傳統(tǒng)的K-means的算法主要有以下四個(gè)步驟：

1.輸入數(shù)據(jù)集D和聚簇?cái)?shù)K；

2.在數(shù)據(jù)集D中隨機(jī)選取K個(gè)數(shù)據(jù)對(duì)象作為聚類中心；

3.計(jì)算數(shù)據(jù)集D中的數(shù)據(jù)對(duì)象與步驟2中選取的聚類中心的歐式距離，并且將數(shù)據(jù)對(duì)象劃分到歐式距離最小的簇中；

4.計(jì)算每個(gè)聚簇內(nèi)數(shù)據(jù)對(duì)象的平均值作為新的聚類中心，返回步驟3，直到聚類中心不再變化或小于某個(gè)指定的極小數(shù)為止.

3 TK-means算法

硬聚類算法和軟聚類算法的主要區(qū)別在于對(duì)于邊緣點(diǎn)的處理.盡管使用三支決策理論改進(jìn)的算法有很多，但是這些算法往往只是將樣本點(diǎn)分為核心點(diǎn)和邊緣點(diǎn)分別處理，但是對(duì)于區(qū)分核心點(diǎn)和邊緣點(diǎn)方法過于復(fù)雜，多采用密度法.采用密度的方法來區(qū)分核心點(diǎn)和樣本點(diǎn)存在如下問題：1.需要對(duì)數(shù)據(jù)集中的所有樣本點(diǎn)進(jìn)行區(qū)域密度計(jì)算，時(shí)間復(fù)雜度較高；2.需要設(shè)置較多參數(shù)，諸如半徑參數(shù)和密度參數(shù).為此，本文通過引入網(wǎng)格聚類算法中劃分網(wǎng)格的方法對(duì)三支決策理論進(jìn)行拓展用于對(duì)K-means算法的優(yōu)化.

已經(jīng)提出了許多將網(wǎng)格算法與K-means算法結(jié)合用以提升效率的混合算法，朱二周[15]等人提出的Grid-K-means算法是一種動(dòng)態(tài)劃分網(wǎng)格的K-means算法，雖然算法效率很高，但是仍然只是將網(wǎng)格劃分的思想應(yīng)用到K-means算法中，將對(duì)樣本點(diǎn)的操作改為對(duì)網(wǎng)格的操作，處理較為簡單.同樣地，TK-means算法在對(duì)數(shù)據(jù)集中的樣本點(diǎn)進(jìn)行核心點(diǎn)、邊緣點(diǎn)和離群點(diǎn)的屬性劃分之前需要對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，將樣本點(diǎn)放入網(wǎng)格中.TK-means算法主要分為以下過程：

3.1 網(wǎng)格劃分

為了更準(zhǔn)確地劃分網(wǎng)格，在讀取數(shù)據(jù)集時(shí)，記錄樣本點(diǎn)每一維的邊界值(Border)(即：最大值和最小值)Bi={Bimax,Bimin}，其中，i=1,2,…,K.為了增加準(zhǔn)確性，分別對(duì)樣本點(diǎn)每一維的最小值向下取整，最大值向上取整，即B′i={B′imax,B′imin}.因此可以獲得樣本點(diǎn)每一維度的數(shù)據(jù)范圍(Range)，計(jì)算方式如下：

Ri=B′imax,B′imin

(13)

(14)

Si=Ri/G

(15)

完成網(wǎng)格劃分后即可將數(shù)據(jù)集中的樣本點(diǎn)讀取并放置于對(duì)應(yīng)的網(wǎng)格中，即把數(shù)據(jù)集的樣本點(diǎn)xi={xi1,xi2,…,xim}轉(zhuǎn)換成網(wǎng)格點(diǎn)Gi={Gi1,Gi2,…,Gim,Gi0}，其中Gi0即為網(wǎng)格密度.

(16)

3.2 屬性劃分

在完成數(shù)據(jù)集中樣本點(diǎn)xi向網(wǎng)格點(diǎn)Gi的轉(zhuǎn)換后，利用三支決策理論和網(wǎng)格密度將樣本點(diǎn)進(jìn)行屬性劃分.由于數(shù)據(jù)集存在多樣性和復(fù)雜性，針對(duì)不同的數(shù)據(jù)集需要設(shè)置不同參數(shù)(Density)De來做出最優(yōu)的屬性劃分.在實(shí)驗(yàn)部分將列出所有數(shù)據(jù)集的密度參數(shù)De.根據(jù)設(shè)置的密度參數(shù)De，將網(wǎng)格密度Gi0大于密度參數(shù)De的網(wǎng)格點(diǎn)視為核心點(diǎn)，而網(wǎng)格密度Gi0小于密度參數(shù)De的網(wǎng)格點(diǎn)視為邊緣點(diǎn)，即：

(17)

在完成對(duì)網(wǎng)格點(diǎn)的屬性劃分后，網(wǎng)格中的樣本點(diǎn)的屬性也就可以確定.

3.3 選取初始聚類中心

K-means算法的初始聚類中心的隨機(jī)選擇使得聚類結(jié)果不穩(wěn)定，容易陷入局部最優(yōu).K-means++算法隨機(jī)選擇一個(gè)樣本點(diǎn)作為第一個(gè)初始聚類中心，再使用輪盤法選擇與已有聚類中心距離較遠(yuǎn)的樣本點(diǎn)作為下一個(gè)初始聚類中心，仍然存在隨機(jī)性不夠穩(wěn)定；而ZK-means算法則是選擇樣本點(diǎn)中密度較高的點(diǎn)作為初始聚類中心，需要計(jì)算所有樣本點(diǎn)的密度，時(shí)間復(fù)雜度較高；Grid-K-means算法利用網(wǎng)格密度對(duì)所有網(wǎng)格點(diǎn)進(jìn)行排序，選取高密度網(wǎng)格作為初始聚類中心，同時(shí)設(shè)置參數(shù)來調(diào)整干擾半徑.

本文進(jìn)一步優(yōu)化，將隸屬于核心區(qū)域中的網(wǎng)格點(diǎn)依據(jù)網(wǎng)格密度進(jìn)行排序，選取最高密度的網(wǎng)格點(diǎn)作為第一個(gè)初始聚類中心v1，剩余的K-1個(gè)初始聚類中心{v2,v3,…,vk}采取和K-means++算法相同的輪盤法選取相聚較遠(yuǎn)的高密度網(wǎng)格點(diǎn)，并且為輪盤法選擇的網(wǎng)格點(diǎn)添加限制條件R，即選取剩余的網(wǎng)格點(diǎn)與已選的初始聚類中心的距離要大于R，輪盤法計(jì)算公式和R的計(jì)算方法如下.通常最高密度的網(wǎng)格點(diǎn)必然是聚類中心，以及了添加限制條件R，避免了K-means++算法選取聚類中心時(shí)存在的隨機(jī)性，也避免了Grid-K-means算法需要提供額外參數(shù)，最后獲取初始聚類中心v={v1,v2,…,vk}.

(18)

R=GN/K

(19)

3.4 聚類過程

在確定初始聚類中心后，即可執(zhí)行聚類.K-means算法以及眾多的對(duì)K-means算法改進(jìn)的算法都對(duì)所有的樣本點(diǎn)采用質(zhì)心就近劃分的思想，即將所有的樣本點(diǎn)劃分到與聚類中心最近的聚簇中.通常這種處理方式采用歐式距離計(jì)算樣本點(diǎn)與聚類中心的距離，因而算法無法處理不同形狀的數(shù)據(jù)集，僅僅適用于類圓形數(shù)據(jù)集.TK-means算法為了突破K-means算法的固有缺陷，結(jié)合三支決策理論對(duì)K-means算法進(jìn)行優(yōu)化.整個(gè)聚類過程分為兩步：

第1步.在確定網(wǎng)格點(diǎn)的屬性和初始聚類中心后，對(duì)網(wǎng)格點(diǎn)中的核心點(diǎn)采用就近劃分的原則，計(jì)算所有網(wǎng)格點(diǎn)與初始聚類中心之間的距離，將網(wǎng)格點(diǎn)中的核心點(diǎn)劃分到離聚類中心最近的聚簇；而對(duì)網(wǎng)格點(diǎn)中的邊緣點(diǎn)采用延遲決策的思想暫不處理.劃分完畢后，重新計(jì)算聚類中心.

(20)

獲取到新的聚類中心v′={v′1,v′2,…,v′k}.對(duì)網(wǎng)格點(diǎn)中的核心點(diǎn)重新劃分，反復(fù)迭代直到聚類中心v′不再發(fā)生變化.

第2步.在完成對(duì)網(wǎng)格點(diǎn)中的核心點(diǎn)的聚類之后，對(duì)網(wǎng)格點(diǎn)中的邊緣點(diǎn)不再計(jì)算與聚類中心之間的距離，而是計(jì)算所有已經(jīng)劃分好的核心點(diǎn)之間的距離，將邊緣點(diǎn)劃分到最近的核心點(diǎn)隸屬的聚簇中.

初始聚類中心選取算法的形式描述如下：

輸入：D：包含n個(gè)對(duì)象的數(shù)據(jù)集；聚類數(shù)：K；限制條件：R.

輸出：初始聚類中心：v={v1,v2,…,vk}.

1.使用公式(13)～公式(17)對(duì)數(shù)據(jù)集D進(jìn)行預(yù)處理并劃分網(wǎng)格空間；

2.根據(jù)網(wǎng)格密度利用快速排序?qū)λ泻诵膮^(qū)域網(wǎng)格點(diǎn)進(jìn)行排序；

3.選取密度最高的網(wǎng)格點(diǎn)作為第一個(gè)初始聚類中心；

4.fori=2toK

5.利用公式(18)計(jì)算所有樣本點(diǎn)與已選擇的初始聚類中心之間的最小距離以及最小距離之和，計(jì)算每個(gè)網(wǎng)格點(diǎn)Gi被選擇作為下一個(gè)初始聚類中心的概率；

6.根據(jù)P(Gi)利用快速排序?qū)W(wǎng)格點(diǎn)進(jìn)行排序；

7.計(jì)算Gi與已選初始聚類中心之間的距離；

8.選取P(Gi)較高且Gi與已選初始聚類中心之間的距離大于R的網(wǎng)格點(diǎn)作為下一個(gè)初始聚類中心；

9.end for

3.5 TK-means算法的具體實(shí)現(xiàn)過程

TK-means算法的主要步驟如下：

輸入：D：包含n個(gè)對(duì)象的數(shù)據(jù)集；聚類數(shù)：K；密度參數(shù)：De.

輸出：聚簇的集合C={(Co(C1),Ed(C1)),(Co(C2),Ed(C2)),…,(Co(CK),Ed(CK))}.

1.使用公式(13)-公式(15)對(duì)數(shù)據(jù)集D進(jìn)行預(yù)處理并劃分網(wǎng)格空間(通過這些公式，計(jì)算Ri，GN和Si)；

2.根據(jù)公式(16)，將數(shù)據(jù)集D中的樣本點(diǎn)讀入網(wǎng)格空間，樣本點(diǎn)轉(zhuǎn)換為網(wǎng)格點(diǎn)；

3.根據(jù)密度參數(shù)De判斷網(wǎng)格點(diǎn)屬性為核心點(diǎn)和邊緣點(diǎn)；

4.選取核心點(diǎn)中密度最高的網(wǎng)格點(diǎn)為第一個(gè)初始聚類中心v1；

5.利用輪盤法選擇與已有初始聚類中心距離較遠(yuǎn)的核心點(diǎn)為下一個(gè)初始聚類中心，選出所有初始聚類中心v={v1,v2,…,vK}；

6.Repeat

7.令C=φ

8.fori=1，2，…，mdo

9.計(jì)算所有核心點(diǎn)到初始聚類中心的距離，將核心點(diǎn)劃分到距離最小的聚類中心所在的聚簇；

10.end for

11.fori=1，2，…，Kdo

13.ifv′i≠vi

14.更新聚類中心：vi←v′i；

15.end for

16.Until聚類中心v′={v′1,v′2,…,v′K}不再變化；

17.fori=1 tomdo

18.計(jì)算所有邊緣點(diǎn)到所有核心之間的距離，將邊緣點(diǎn)劃分到距離最小的核心點(diǎn)所隸屬的聚簇中；

19.end for；

20.讀取已聚類的網(wǎng)格點(diǎn)中的樣本點(diǎn)標(biāo)記完成聚類，C={(Co(C1),Ed(C1)),(Co(C2),Ed(C2)),…,(Co(CK),Ed(CK))}.

根據(jù)劃分好的網(wǎng)格點(diǎn)，讀取網(wǎng)格點(diǎn)中的樣本點(diǎn)并標(biāo)記即完成聚類，聚類的結(jié)果為：C={(Co(C1),Ed(C1)),(Co(C2),Ed(C2)),…,(Co(CK),Ed(CK))}.通過邊緣點(diǎn)的延遲劃分以及邊緣點(diǎn)隸屬關(guān)系的特殊判斷方式對(duì)K-means算法進(jìn)行優(yōu)化，可以獲得更好的聚類效果.

TK-means算法的偽代碼步驟中，1-3是對(duì)數(shù)據(jù)集中樣本點(diǎn)進(jìn)行網(wǎng)格劃分，并根據(jù)參數(shù)對(duì)網(wǎng)格點(diǎn)進(jìn)行屬性劃分；4是利用網(wǎng)格密度確定所有的初始聚類中心；6-16是對(duì)核心點(diǎn)進(jìn)行聚類劃分；17-19是對(duì)邊緣點(diǎn)進(jìn)行聚類劃分；20是對(duì)已聚類的網(wǎng)格點(diǎn)中的樣本點(diǎn)進(jìn)行標(biāo)記并完成聚類.

4 實(shí)驗(yàn)評(píng)估

4.1 評(píng)估指標(biāo)

通過使用聚類算法可以將目標(biāo)數(shù)據(jù)集劃分成指定數(shù)目的聚簇，然而對(duì)于聚類結(jié)果仍然需要特定的方法給予評(píng)估.對(duì)于聚類算法的性能評(píng)估通常由兩方面組成：聚類算法效率和聚類結(jié)果.對(duì)于聚類算法效率的評(píng)估即為對(duì)比聚類算法的執(zhí)行時(shí)間；而對(duì)于聚類結(jié)果可以通過聚類結(jié)果的準(zhǔn)確率來判斷.此外，聚類有效性指標(biāo)也是一種判斷聚類結(jié)果的有效方法.

1)準(zhǔn)確率

(21)

準(zhǔn)確率是判斷聚類結(jié)果質(zhì)量最為直觀的方式.通過將聚類結(jié)果中所有聚簇中的樣本點(diǎn)和對(duì)應(yīng)數(shù)據(jù)集中的聚簇樣本點(diǎn)進(jìn)行一一對(duì)比可以得到聚類結(jié)果的準(zhǔn)確性.Acc越高即代表聚類結(jié)果的準(zhǔn)確性越高，聚類效果越好.當(dāng)Acc=100%時(shí)，聚類結(jié)果與目標(biāo)數(shù)據(jù)集完全匹配.

2)聚類有效性指標(biāo)Davies-Bouldin(DBI)

(22)

4.2 實(shí)驗(yàn)數(shù)據(jù)

本文的實(shí)驗(yàn)采用Java語言編寫，具體的實(shí)驗(yàn)環(huán)境如表1所示.為了驗(yàn)證本文提出的TK-means算法的性能，仿真實(shí)驗(yàn)共選擇了12個(gè)數(shù)據(jù)集，其中6個(gè)模擬數(shù)據(jù)集：400-4k2、Aggregation、D9、Pathbased、R15和Unbalance，6個(gè)UCI機(jī)器學(xué)習(xí)庫中的真實(shí)數(shù)據(jù)集：Iris、seeds、tae、bupa、mammographic和newthyroid.表2展示這些數(shù)據(jù)集的詳細(xì)信息，其中參數(shù)Effect為區(qū)分核心區(qū)域和邊緣區(qū)域的參數(shù).真實(shí)數(shù)據(jù)集均為高維度的數(shù)據(jù)集，需要通過降維處理才能在低維度空間中展示.本文采用T-SNE方法對(duì)高緯度數(shù)據(jù)集進(jìn)行降維處理[17].圖1和圖2分別是模擬數(shù)據(jù)集和降維后的真實(shí)數(shù)據(jù)集的空間分布圖.

表1 實(shí)驗(yàn)環(huán)境
Table 1 Experiment environment

CPUIntel(R)Core(TM)i5-7500(3.40GHz)RAMKingston DDR4 2667(16GB)Hard diskTOSHIBA DT01ACA100(1TB,7200r/min)OSMicrosoft Windows 10 Enterprise(64 bit)

表2 實(shí)驗(yàn)數(shù)據(jù)集描述
Table 2 Experimental data set description

IDDatasetsSamplesAttributesClassesEffect1400-4k24002442Aggregation7542643D99002924Pathbased2822425R1560021526Unbalance65002827Iris1504338seeds2107329tae15153210bupa34562211mammographic83052312newthyroid215531

4.3 實(shí)驗(yàn)數(shù)據(jù)結(jié)果分析

為了驗(yàn)證本文提出TK-means算法的聚類效果，K-means算法、K-medoids算法、K-means++算法、ZK-means算法、ZK-medoids算法(本文將ZK-means算法中利用密度選取初始聚類中心的方法應(yīng)用到K-medoids算法)和TWKM算法被選擇用來與TK-means算法進(jìn)行比較.對(duì)于上述聚類算法，通過DBI指標(biāo)和對(duì)聚類結(jié)果進(jìn)行評(píng)估，用以展示TK-means算法的性能.同時(shí)測(cè)量各種算法的運(yùn)行時(shí)間用以衡量算法效率.

圖1 6個(gè)模擬數(shù)據(jù)集的空間分布圖Fig.1 Spatial distribution of six simulated data sets

圖2 6個(gè)真實(shí)數(shù)據(jù)集的三維空間分布圖Fig.2 Three-dimensional spatial distribution of six real data sets

表3給出了6種聚類算法對(duì)12個(gè)數(shù)據(jù)集運(yùn)行10次的平均準(zhǔn)確率.其中，將表中不同算法中的最佳聚類結(jié)果標(biāo)記為粗體.由于K-means算法、K-medoids算法、K-means++算法和TWKM算法初始聚類中心隨機(jī)選擇，所以三種聚類算法每次的聚類結(jié)果存在不確定性.而ZK-means算法、ZK-medoids算法和TK-means算法采用了初始聚類中心確定算法，聚類結(jié)果穩(wěn)定.表3顯示采用了三支決策理論改進(jìn)的TK-means算法具有更好的聚類結(jié)果.表4列出了7種聚類算法對(duì)12個(gè)數(shù)據(jù)集的聚類最佳結(jié)果.表4顯示，對(duì)于其他6種聚類算法的最佳聚類結(jié)果，TK-means算法依舊優(yōu)勢(shì)明顯，有更好的聚類結(jié)果.

表5列出了7種聚類算法對(duì)12個(gè)數(shù)據(jù)集進(jìn)行聚類運(yùn)行10次的平均時(shí)間，時(shí)間單位為“毫秒”.表5顯示，針對(duì)二維的模擬數(shù)據(jù)集，TK-means算法和其他6種算法相比，效率相當(dāng).針對(duì)高維度的真實(shí)數(shù)據(jù)集，由于TK-means算法增加了網(wǎng)格操作，需要對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，多維度劃分網(wǎng)格所需時(shí)間較多，而處理的樣本點(diǎn)較少，不能發(fā)揮網(wǎng)格算法的優(yōu)勢(shì)，因此效率低于其他6種算法.

從表6和表7中可以發(fā)現(xiàn)，TK-means算法在DBI指標(biāo)對(duì)聚類結(jié)果的評(píng)估上優(yōu)于其他算法，TK-means算法可以獲得較多數(shù)據(jù)集的高質(zhì)量聚類結(jié)果.DBI指標(biāo)對(duì)于K-means算法的最佳聚類結(jié)果的評(píng)估上優(yōu)于TK-means算法，這是因?yàn)镵-means算法的最佳聚類結(jié)果較為接近TK-means算法，且主要是在多維且重疊度較大的數(shù)據(jù)集上存在偏差.這種情況與DBI指標(biāo)的性能有關(guān)，DBI指標(biāo)對(duì)于重疊度大的數(shù)據(jù)集的評(píng)估能力較為薄弱.在DBI指標(biāo)的平均評(píng)估結(jié)果上，TK-means算法和TWKM算法優(yōu)于其他算法.

表3 算法平均準(zhǔn)確率
Table 3 Average accuracy of algorithms

Data setsK-meansK-medoidsK-means++ZK-meansZK-medoidsTWKMTK-means400-4k292.00%89.60%97.45%100%86.25%91.00%100%Aggregation93.40%70.41%93.66%94.83%67.11%88.29%95.36%D980.98%78.17%83.13%88.78%88.67%78.84%100%Pathbased74.11%67.09%76.14%71.99%66.31%74.47%82.27%R1582.35%73.12%90.73%99.67%91.67%90.10%99.67%Unbalance93.85%94.62%93.85%93.85%93.85%94.68%99.94%Iris88.30%76.13%75.60%92.67%73.33%74.80%99.33%seeds89.29%77.52%89.19%89.52%66.67%73.91%89.52%tae68.54%43.51%44.17%64.90%41.72%59.34%79.47%bupa58.55%57.97%57.97%58.55%57.97%58.73%59.13%mammographic69.46%70.33%69.59%70.48%71.20%68.58%78.92%newthyroid80.65%80.00%82.79%86.05%76.28%76.84%87.91%

表4 算法最佳準(zhǔn)確率
Table 4 Best accuracy of algorithms

Data setsK-meansK-medoidsK-means++ZK-meansZK-medoidsTWKMTK-means400-4k2100%95.25%100%100%86.25%100%100%Aggregation94.96%74.80%94.96%94.83%67.11%92.97%95.36%D999.78%89.56%99.67%88.78%88.67%99.89%100%Pathbased80.85%68.79%79.79%71.99%66.31%81.21%82.27%R1599.67%82.50%99.67%99.67%91.67%98.17%99.67%Unbalance93.85%95.38%93.85%93.85%93.85%96.92%99.94%Iris93.33%80.67%89.33%92.67%73.33%99.33%99.33%seeds89.52%83.81%89.52%89.52%66.67%96.67%89.52%tae72.19%46.36%45.70%64.90%41.72%70.86%79.47%bupa58.55%57.97%57.97%58.55%57.97%65.80%59.13%mammographic70.48%71.57%70.48%70.48%71.20%72.17%78.92%newthyroid86.05%83.72%86.05%86.05%76.28%81.40%87.91%

表5 算法平均運(yùn)行時(shí)間(單位：毫秒)
Table 5 Average running time of algorithms(unit：ms)

4.4 性能分析

表6 DBI指標(biāo)評(píng)估算法結(jié)果的平均表現(xiàn)
Table 6 Average performance of the DBI index evaluation algorithm results

Data setsK-meansK-medoidsK-means++ZK-meansZK-medoidsTWKMTK-means400-4k20.38981.60830.35530.24760.70920.24330.2712Aggregation0.82067.19780.79450.72004.75340.62190.4376D90.55131.59640.59340.57620.57970.37620.3267Pathbased0.98765.88250.96271.10057.12920.40760.7719R150.55930.80320.47490.36940.56190.14310.4468Unbalance0.82081.02800.93470.83090.65391.02830.3897Iris0.73421.25990.70520.593141.42400.29121.3459seeds0.46583.50200.47740.58383.03550.42620.3875tae4.61612.83913.09422.62464.25984.13792.3387bupa2.80090.80102.67653.14810.73591.14811.3947mammographic0.40911.29890.39070.30203.35940.37301.2285newthyroid0.64401.05670.69980.93210.44160.59810.5473

表7 DBI指標(biāo)評(píng)估算法結(jié)果的最佳表現(xiàn)
Table 7 Best performance of the DBI index evaluation algorithm results

Data setsK-meansK-medoidsK-means++ZK-meansZK-medoidsTWKMTK-mean400-4k20.22300.43290.23610.24760.70920.05470.2712Aggregation0.67232.63530.71840.72004.75340.58070.4376D90.32050.65780.45970.57620.57970.38060.3267Pathbased0.79064.63480.88981.10057.12920.25160.7719R150.43000.66520.39420.36940.56190.44680.4468Unbalance0.69950.65770.75910.83090.65390.69920.3897Iris0.58460.91880.58460.593141.42400.14051.3459seeds0.38240.81730.28380.58383.03550.05750.3875tae2.51261.16551.40992.62464.25982.19942.3387bupa2.48100.70012.43493.14810.73590.29511.3947mammographic0.29660.47790.29900.30203.35940.20351.2285newthyroid0.54490.41670.47850.93210.44160.19160.5473

綜上所述，TK-means算法和K-means算法、K-medoids算法、K-means++算法、ZK-means算法、ZK-medoids算法、TWKM算法相比擁有更好的性能.利用三支決策理論和網(wǎng)格算法對(duì)K-means算法進(jìn)行優(yōu)化的TK-means算法可以快速地確定初始聚類中心并高效地處理邊緣樣本點(diǎn)，具有更好的聚類效果.

5 結(jié)束語

現(xiàn)有的聚類算法中通常在判斷樣本點(diǎn)與聚簇的隸屬關(guān)系時(shí)分為屬于和不屬于的關(guān)系，忽略對(duì)隸屬關(guān)系不確定樣本點(diǎn)的再判斷.本文通過將三支決策理論與K-means算法結(jié)合提出新的TK-means算法.TK-means算法通過增加對(duì)樣本點(diǎn)的屬性劃分提高算法的準(zhǔn)確率；通過引入網(wǎng)格算法中劃分網(wǎng)格的思想提高樣本點(diǎn)屬性劃分的效率；通過密度法和輪盤法的結(jié)合使用提高初始聚類中心確定的準(zhǔn)確性；通過提出對(duì)核心點(diǎn)和邊緣點(diǎn)不同劃分方式解決K-means算法僅適用于類圓形數(shù)據(jù)集的固有缺陷.通過測(cè)試不同數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明，TK-means算法擁有更好的性能.