基于部分實(shí)例重判的二分K-means算法

吳清壽, 劉耿耿, 郭文忠

(1. 武夷學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院, 福建 武夷山 354300; 2. 福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院, 福建 福州 350116)

0 引言

聚類分析是無(wú)監(jiān)督學(xué)習(xí)的重要方法. 聚類分析能夠發(fā)現(xiàn)數(shù)據(jù)集自身隱含的內(nèi)蘊(yùn)結(jié)構(gòu)信息， 其在模式識(shí)別與數(shù)據(jù)挖掘等研究方向有著廣泛的應(yīng)用. 根據(jù)數(shù)據(jù)集中數(shù)據(jù)的積聚規(guī)則和應(yīng)用這些規(guī)則的方法， 可以將聚類算法大致分成層次化聚類算法、 劃分式聚類算法、 基于密度和網(wǎng)格的聚類算法以及其他聚類算法[1].K-means聚類算法是劃分式聚類的典型代表.K-means算法的首要問(wèn)題在于對(duì)初始質(zhì)心的選擇是敏感的， 文獻(xiàn)[2]提出了一種基于最大最小距離法確定初始質(zhì)心的方法， 文獻(xiàn)[3]利用聚集度函數(shù)和層次聚類來(lái)獲取初始質(zhì)心. 針對(duì)K-means易于收斂到局部最小值而非全局最小值的問(wèn)題， Ding等[4]提出一致性保留K-means算法(K-means-CP)， 可實(shí)現(xiàn)全局聚類目標(biāo)函數(shù)優(yōu)化. 作為K-means算法的重要變種， 二分K-means也得到了廣泛的應(yīng)用和研究. 文獻(xiàn)[5]提出以極大距離點(diǎn)優(yōu)化二分K-means初始質(zhì)心的方法， 并對(duì)算法進(jìn)行并行化處理. 文獻(xiàn)[6]將二分k-均值與SVM決策樹(shù)相結(jié)合， 用二分k-均值在低維數(shù)據(jù)空間中聚類， 取得了良好效果.

在各類研究中， 對(duì)文獻(xiàn)[1]所提出的一個(gè)問(wèn)題未予以解決， 即二分K-means算法存在再分配能力差問(wèn)題. 問(wèn)題具體表現(xiàn)為： 若在某個(gè)階段把一些實(shí)例(instance)誤劃分給某個(gè)簇， 這些實(shí)例將失去回歸原應(yīng)歸屬簇的機(jī)會(huì). 本研究通過(guò)引入目標(biāo)簇和候選簇的概念， 在候選簇中選出若干距離目標(biāo)簇最近的實(shí)例作為召回實(shí)例， 并對(duì)召回實(shí)例進(jìn)行重判， 讓部分誤判實(shí)例有機(jī)會(huì)回歸， 從而提高聚類的精確度.

1 K-means算法

K-means算法把數(shù)據(jù)集X劃分成k個(gè)聚類(也稱為簇)C=(C1,C2， …，Ck)， 數(shù)據(jù)集X定義為{x1，x2， …，xn}， 其中xi=(xi1，xi2， …，xir)是一個(gè)向量， 表示數(shù)據(jù)集X中的第i個(gè)實(shí)例，r表示數(shù)據(jù)的屬性數(shù)目. 每個(gè)聚類中有一個(gè)中心， 稱作聚類質(zhì)心(centroid)， 表示為M=(m1，m2， …，mk). 定義簇Ck的質(zhì)心mk為：

(1)

其中:xik是簇Ck的第i個(gè)實(shí)例，nk表示簇Ck中的實(shí)例數(shù)量. 簇內(nèi)方差是簇中所有實(shí)例與簇質(zhì)心的歐氏距離平方和， 整個(gè)聚類空間的誤差平方和(sum of squared error， SSE)是簇內(nèi)方差之和. 簇內(nèi)實(shí)例與質(zhì)心的歐氏距離公式：

(2)

式中：xikn表示簇Ck的第i個(gè)實(shí)例的第n個(gè)屬性;mkn表示質(zhì)心mk的第n個(gè)屬性. 算法將SSE作為度量聚類效果指標(biāo)[7]， 可以定義為：

(3)

K-means算法的基本思想是將數(shù)據(jù)集中的所有實(shí)例劃分到k個(gè)簇中， 通過(guò)不斷地迭代質(zhì)心， 使簇中的所有實(shí)例到該簇質(zhì)心的距離最小， 并使得SSE最小.

K-means算法的終止條件可設(shè)定為以下幾種情況之一[8]： 1) 沒(méi)有(或最小數(shù)目)數(shù)據(jù)實(shí)例被重新分配給不同的簇； 2) 沒(méi)有(或最小數(shù)目)質(zhì)心發(fā)生變化； 3) SSE達(dá)到最小值(可能是局部最小).

K-means算法易于實(shí)現(xiàn)， 時(shí)間復(fù)雜度為O(tkn)，n是數(shù)據(jù)集中實(shí)例總數(shù)，k是聚類的個(gè)數(shù)，t是迭代次數(shù). 一般情況下，k，t值通常遠(yuǎn)小于n， 故K-means的時(shí)間復(fù)雜度對(duì)x是線性的. 以下主要討論算法存在的不足之處： 1) 算法只能應(yīng)用于均值能夠被定義的數(shù)據(jù)集上， 文獻(xiàn)[9]提出的k-modes是K-means的一種變體， 解決了K-means僅適合于數(shù)值屬性數(shù)據(jù)聚類的局限性， 適用于分類屬性數(shù)據(jù)聚類； 2) 需要預(yù)先設(shè)定聚類數(shù)目k， 文獻(xiàn)[7]和文獻(xiàn)[10]對(duì)這個(gè)問(wèn)題都提出了解決方案； 3) 對(duì)噪音點(diǎn)較為敏感[11].

2 二分K-means算法

二分K-means算法基本思想[12-14]： 首先， 初始數(shù)據(jù)集的所有實(shí)例歸屬同一個(gè)簇， 計(jì)算該簇質(zhì)心； 之后， 利用K-means算法將該簇進(jìn)行二分， 以最快速度降低SSE的值為劃分依據(jù)， 從現(xiàn)有簇中選擇一個(gè)簇繼續(xù)進(jìn)行二分； 不斷重復(fù)以上步驟， 以簇的總量達(dá)到要求為終止條件.

在二分K-means算法中， 度量第h簇劃分質(zhì)量的SSEh由兩個(gè)部分組成： 當(dāng)前簇的誤差平方和SSEcurr和其余簇的誤差平方和SSEother. 假設(shè)數(shù)據(jù)集X當(dāng)前包含n(n

(4)

h0和h1表示簇號(hào)，i表示簇中的第i個(gè)實(shí)例. 其余簇即除了簇Ch之外的所有簇， 表示為(C1，C2， …，Ch-1，Ch+1， …，Cn)， 其SSE計(jì)算式為：

(5)

其中:U={1， 2， …，h-1}∪{h+1， …，n}. 則SSEh可表示為：

SSEh=SSEcurr+SSEother

(6)

二分K-means算法流程如算法1所示.

算法1.BiKmeans算法.Begin 將數(shù)據(jù)集X的所有實(shí)例當(dāng)成第0簇 求第0個(gè)質(zhì)心 根據(jù)公式(3)計(jì)算初始SSE While (總簇?cái)?shù)

3 基于部分節(jié)點(diǎn)重判的改進(jìn)算法

二分K-means算法得到了廣泛的應(yīng)用， 針對(duì)二分K-means算法的改進(jìn)研究也取得了良好的效果[10]. 在眾多研究中， 有一個(gè)問(wèn)題沒(méi)有得到足夠的重視， 即二分聚類過(guò)程中， 部分實(shí)例可能會(huì)被劃分到錯(cuò)誤的簇中. 根據(jù)二分K-means的聚類規(guī)則， 實(shí)例一旦被錯(cuò)劃， 就失去了回歸正確簇的機(jī)會(huì). 基于部分實(shí)例重判的二分K-means算法對(duì)上述問(wèn)題提出了解決方案.

定義1在二分K-means算法執(zhí)行過(guò)程中， 簇Ci被二分為簇Cp和簇Cq， 則稱Cp和Cq互為兄弟簇，Ci稱為Cp和Cq的父簇，Cp和Cq稱為Ci的子簇. 將Ci二分聚類使得SSE最小， 則稱Ci為目標(biāo)簇， 若Ci和Cj互為兄弟簇， 且Cj從未成為目標(biāo)簇， 則稱Cj為Ci對(duì)應(yīng)的候選簇.

定義2候選簇Cj中存在若干實(shí)例xuj， 在目標(biāo)簇Ci二分為子簇Cp和Cq后， 計(jì)算xuj與Cj、Cp和Cq的質(zhì)心mj、mp和mq之間的距離d(xuj，mj)、d(xuj，mp)和d(xuj，mq)， 若d(xuj，mj)

圖1 二分后的目標(biāo)簇、 候選簇Fig.1 The object clusters and candidate clusters after bisecting

如圖1所示， 根據(jù)定義1， 簇2為目標(biāo)簇(用加粗表示)， 簇1為候選簇(用虛線表示). 若簇1中存在召回實(shí)例， 通過(guò)判斷實(shí)例與簇3和簇4的質(zhì)心之間的距離， 以決定將實(shí)例歸入簇3或簇4. 其判斷條件為若d(xuj，m3)>d(xuj，m4)， 則將實(shí)例劃入簇3， 否則， 將實(shí)例劃入簇4. 從圖1可以看出， 其包含兩個(gè)目標(biāo)簇(簇0和2)和一個(gè)候選簇(簇1)， 表示需進(jìn)行兩次二分聚類并需要一次召回實(shí)例的重判.

候選簇中的實(shí)例并不需要全部參與判別， 通過(guò)對(duì)候選簇的樣本進(jìn)行排序， 設(shè)定一個(gè)閾值θ， 以控制參與重判的實(shí)例數(shù)量. 排序主要依據(jù)二分時(shí)計(jì)算出的樣本與兩個(gè)質(zhì)心的距離. 兩相比較， 作為候選簇中的實(shí)例， 其與候選簇質(zhì)心的距離必然小于到目標(biāo)簇的距離， 所以在兩個(gè)距離中選擇較大的距離并進(jìn)行升序排序， 找到候選簇中距離目標(biāo)簇最近的若干個(gè)實(shí)例作為召回實(shí)例的判別對(duì)象.

圖2是二分K-means算法對(duì)數(shù)據(jù)集中全體實(shí)例的一次模擬二分聚類過(guò)程， 其劃分過(guò)程與簇號(hào)生成遵循以下規(guī)則.

圖2 二分K-means算法的二分聚類及簇號(hào)生成過(guò)程 Fig.2 The bisecting clustering and the cluster number generation process of the bisec-ting K-means algorithm

規(guī)則1. 目標(biāo)簇Ci二分為子簇Cp和Cq時(shí)， 一個(gè)子簇保留父簇的編號(hào)， 另一個(gè)子簇編號(hào)為二分前簇的總量， 簇號(hào)索引從0開(kāi)始.

規(guī)則2. 目標(biāo)簇Ci確定后， 要判斷其兄弟簇Cj是否為候選簇， 若Cj是候選簇， 則進(jìn)行召回實(shí)例重判處理.

根據(jù)規(guī)則1， 圖2所生成的簇號(hào)和圖1中的簇編號(hào)不同， 是因?yàn)椴捎脠D1方便說(shuō)明問(wèn)題， 圖2中的編號(hào)才是真正的簇編號(hào)生成方法.

圖2所示的二分聚類過(guò)程為0->(0， 1)， 1->(1， 2)， 0->(0， 3)， 1->(1， 4). 以1->(1， 2)為例， 這是第2次進(jìn)行二分， 簇Ci(i=1)是目標(biāo)簇， 當(dāng)前簇?cái)?shù)目為2(即簇0和1)， 根據(jù)規(guī)則1， 兩個(gè)子簇的編號(hào)為Cp(p=1， 父簇的編號(hào)為1)和Cq(q=2， 當(dāng)前簇?cái)?shù)目為2). 簇Ci(i=1)的兄弟簇Cj(j=0)是候選簇， 所以要進(jìn)行召回實(shí)例的重判處理. 而在0->(0， 3)這次二分中， 因目標(biāo)簇Ci(i=0)的兄弟簇Cj(j=1)已進(jìn)行過(guò)二分聚類， 所以Cj(j=1)不是候選簇， 其所包含的實(shí)例無(wú)需進(jìn)行召回實(shí)例重判.

表1 二分K-means算法的簇生成過(guò)程

為快速查找候選簇和目標(biāo)簇， 需維護(hù)一個(gè)二維數(shù)組cluster， 見(jiàn)表1， 其與圖2中簇生成過(guò)程存在一一對(duì)應(yīng)關(guān)系. 表1包含兩列， 第0列記錄按順序生成的簇號(hào)， 因數(shù)組索引從0開(kāi)始， 所以簇號(hào)與數(shù)組行索引同值. 第1列記錄第0列簇號(hào)對(duì)應(yīng)的兄弟簇及其變遷過(guò)程， 初始簇沒(méi)有兄弟簇， 不包含在表1中. 如表1所示， 第0列中的簇1對(duì)應(yīng)的兄弟簇號(hào)序列為0/2/4， 其表示簇1的初始兄弟簇為簇0， 后續(xù)又經(jīng)過(guò)兩次二分聚類： 1->(1， 2)， 1->(1， 4)， 其兄弟簇號(hào)先后更新為2和4. 應(yīng)用到算法中， 可用于快速定位候選簇.

規(guī)則3. 在cluster數(shù)組中， 因數(shù)組索引從0開(kāi)始， 所以簇號(hào)與數(shù)組行索引同值. 目標(biāo)簇Ci的兄弟簇為Cj， 則cluster[Ci][1]的值為Cj， cluster[Cj][1]的值為temp， 表示Cj的兄弟簇號(hào)； 若temp=Ci， 則說(shuō)明Cj至今未進(jìn)行二分， 是一個(gè)候選簇.

如1->(1， 2)， 目標(biāo)簇1的兄弟是簇0， 簇0的兄弟簇是1， 兩者相等， 則簇0為候選簇. 若0->(0， 3)， 目標(biāo)簇0的兄弟簇是1， 簇1的兄弟簇已變更為2， 兩者不相等， 則簇1不是候選簇， 簇中實(shí)例無(wú)需重判.

部分實(shí)例重判算法(partial instance rejudge， PIR)是作為二分K-means算法的一個(gè)組件存在， 算法2中對(duì)算法1的內(nèi)容不再重復(fù).

算法2.PIR算法Begin If Ci==cluster[cluster[Ci][1]][1] #根據(jù)規(guī)則3確定候選簇 過(guò)濾出候選簇Cj中的所有實(shí)例 對(duì)所有實(shí)例按照到目標(biāo)簇的距離升序排序 根據(jù)閾值θ確定參與重判的實(shí)例集合newClust For each instance in newClust 計(jì)算實(shí)例與目標(biāo)簇的兩個(gè)子簇質(zhì)心的距離D0、 D1 計(jì)算實(shí)例到候選簇的距離D2 根據(jù)定義2確定召回實(shí)例 將召回實(shí)例分配到相應(yīng)子簇 End 在cluster數(shù)組中將兩個(gè)子簇互標(biāo)為兄弟簇 EndEnd

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

為驗(yàn)證分析算法， 對(duì)K-means、 BiKmeans及PIR-BiKmeans三種算法進(jìn)行比較， 并從UCI機(jī)器學(xué)習(xí)數(shù)據(jù)集中選擇Iris、 Wine和ADL中的Drink_glass三個(gè)數(shù)值型數(shù)據(jù)集進(jìn)行測(cè)試. Iris數(shù)據(jù)集有150個(gè)實(shí)例， 每個(gè)實(shí)例有4個(gè)屬性， 數(shù)據(jù)集分3個(gè)類別， 每個(gè)類別包含50個(gè)實(shí)例， 這是在各類算法中被應(yīng)用最多的數(shù)據(jù)集. Wine數(shù)據(jù)集有178個(gè)實(shí)例， 實(shí)例有13個(gè)屬性， 也是分成3個(gè)類別， 第一類有59個(gè)， 第二類有71個(gè)， 第三類有48個(gè)， 其聚類結(jié)構(gòu)良好. Drink_glass數(shù)據(jù)集是從ADL中抽取部分實(shí)例構(gòu)成的， 共484個(gè)實(shí)例， 實(shí)例有3個(gè)屬性， 共分為5類， 每個(gè)類別分別包含140， 70， 90， 69和115個(gè)實(shí)例， 采用手工分類.

實(shí)驗(yàn)環(huán)境: 處理器Intel Core i5-3210M 2.5 GHz， 內(nèi)存4 G， 操作系統(tǒng)為Windows7 64位， 編程語(yǔ)言為Python2.7.

4.1 聚類準(zhǔn)確率與運(yùn)行時(shí)間分析

分別用三種算法對(duì)三組數(shù)據(jù)進(jìn)行聚類， 得到圖3～4所示結(jié)果.

圖3 不同算法對(duì)3個(gè)數(shù)據(jù)集進(jìn)行15次隨機(jī)實(shí)驗(yàn)的平均運(yùn)行時(shí)間

4.1.1 時(shí)間性能分析

從圖3可以看出， 對(duì)Wine數(shù)據(jù)集進(jìn)行聚類花費(fèi)的時(shí)間最長(zhǎng)， 因?yàn)閃ine數(shù)據(jù)集的實(shí)例有13個(gè)屬性， 大于其他兩個(gè)數(shù)據(jù)集的屬性數(shù)量， 增加了算法的計(jì)算時(shí)間.

用3種算法對(duì)同一個(gè)數(shù)據(jù)集進(jìn)行聚類， 運(yùn)行時(shí)間最長(zhǎng)的是BiKmeans算法， 最短的是K-means算法， 特別是對(duì)Drink數(shù)據(jù)集聚類時(shí)， BiKmeans算法的運(yùn)行時(shí)間是K-means算法的1.6倍. 這是因?yàn)閷?shù)據(jù)集分成3類時(shí)， BiKmeans算法調(diào)用K-means算法的次數(shù)是3次， 分成4類時(shí)， 要調(diào)用6次， 而分成5類時(shí)則是10次. 雖然每次調(diào)用要處理的實(shí)例數(shù)量減少， 但調(diào)用次數(shù)的大幅度增加是造成運(yùn)行時(shí)間延長(zhǎng)的主要原因.

運(yùn)行結(jié)果顯示， PIR-BiKmeans算法的平均運(yùn)行時(shí)間小于BiKmeans算法， 其原因在于通過(guò)對(duì)召回實(shí)例的處理， 使得簇結(jié)構(gòu)更為緊湊， 減少了聚類迭代次數(shù)， 從而提高了運(yùn)行效率.

為了更加直觀地展示算法， 表2對(duì)兩個(gè)算法的迭代次數(shù)進(jìn)行了分析. 通過(guò)表2可以看出， PIR算法的平均迭代次數(shù)明顯少于BiKmeans算法， 相應(yīng)地， 迭代次數(shù)決定了運(yùn)行時(shí)間， PIR算法的平均運(yùn)行時(shí)間也明顯少于BiKmeans算法.

表2 不同算法對(duì)三個(gè)數(shù)據(jù)集進(jìn)行15次隨機(jī)實(shí)驗(yàn)的迭代結(jié)果

4.1.2 聚類準(zhǔn)確率分析

圖4中， 對(duì)三個(gè)不同的數(shù)據(jù)集， 改進(jìn)算法PIR-BiKmeans的聚類效果都是最好的， 而原始算法K-means的效果都是最差的. BiKmeans算法不一定每次都能收斂于全局最佳值， 經(jīng)過(guò)多次運(yùn)行， 還是能夠彌補(bǔ)K-means算法經(jīng)常收斂于局部最小值的缺陷， 所以其在三個(gè)數(shù)據(jù)集中的平均聚類準(zhǔn)確率都高于K-means算法. PIR-BiKmeans算法通過(guò)對(duì)前期誤判的實(shí)例進(jìn)行召回， 部分糾正了實(shí)例的分簇結(jié)果， 所以能取得良好的聚類效果.

4.1.3 與同類工作的對(duì)比

Iris和Wine數(shù)據(jù)集常用于各類聚類算法的測(cè)試， 此處將本研究算法的聚類結(jié)果與文獻(xiàn)[7]和文獻(xiàn)[11]中的相關(guān)算法進(jìn)行對(duì)比.

文獻(xiàn)[11]中對(duì)Iris數(shù)據(jù)集采用了三種算法計(jì)算其聚類準(zhǔn)確率， 其與本研究算法的聚類準(zhǔn)確率對(duì)比情況如表3.

表3 本研究算法與文獻(xiàn)[11]的對(duì)比

文獻(xiàn)[7]中對(duì)Wine數(shù)據(jù)集采用了兩種算法計(jì)算其聚類準(zhǔn)確率， 其與本研究算法的聚類準(zhǔn)確率對(duì)比情況如表4.

表4 本研究算法與文獻(xiàn)[7]的對(duì)比

Drink_glass數(shù)據(jù)集未見(jiàn)于其他文獻(xiàn)， 無(wú)從比較.

通過(guò)對(duì)Iris和Wine兩個(gè)數(shù)據(jù)集的聚類情況看， 本研究實(shí)現(xiàn)的算法與同類工作相比， 在聚類準(zhǔn)確性方面有一定程度的提高.

4.2 召回實(shí)例正確率分析

在PIR-BiKmeans算法中， 閾值θ的取值關(guān)系到召回實(shí)例的有效率， 并最終決定聚類的整體準(zhǔn)確率. 經(jīng)對(duì)Iris等三個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證，θ的取值在5%～20%之間能取得較佳效果. 表5對(duì)θ全部取值為6%， 關(guān)于θ取值的有關(guān)問(wèn)題在下一節(jié)討論. 為防止候選簇中實(shí)例數(shù)較少出現(xiàn)召回實(shí)例數(shù)量為零的情況， 此處將參與重判的實(shí)例數(shù)設(shè)為|Cj|×θ+1， |Cj|表示候選簇Cj中的實(shí)例數(shù)量， 并進(jìn)行15次隨機(jī)實(shí)驗(yàn)， 得到表5中的實(shí)驗(yàn)結(jié)果.

表5 PIR-BiKmeans算法對(duì)三個(gè)數(shù)據(jù)集進(jìn)行15次隨機(jī)實(shí)驗(yàn)的召回實(shí)例情況

4.3 閾值θ的取值問(wèn)題

圖5 θ取值與聚類準(zhǔn)確率的關(guān)系 Fig.5 Relationship between theta’s value and clustering accuracy

對(duì)于閾值θ的取值規(guī)則， 此處進(jìn)一步予以說(shuō)明. 在本次實(shí)驗(yàn)中， 對(duì)θ的取值范圍設(shè)定為5%～20%， 并指定步長(zhǎng)為1%， 對(duì)三個(gè)數(shù)據(jù)集分別用不同的θ值進(jìn)行測(cè)試， 得到圖5所示結(jié)果. 從圖5中可以看出， 在不同的數(shù)據(jù)集中，θ的不同取值對(duì)聚類精確率并未呈現(xiàn)出統(tǒng)一的規(guī)律性， 如Iris數(shù)據(jù)集，θ的值為6%時(shí)聚類準(zhǔn)確度最高， 而后θ取值越高， 其準(zhǔn)確率越低(Iris本身的聚類效果較好， 參與重判的實(shí)例越多， 被誤判的實(shí)例也就越多). 在Drink數(shù)據(jù)集上用不同的θ值進(jìn)行測(cè)試，θ的取值越高， 聚類精確度也逐步提高. 而Wine數(shù)據(jù)集在θ取值為14%時(shí)達(dá)到較好聚類效果.

5 結(jié)語(yǔ)

本研究引入目標(biāo)簇及候選簇的概念， 通過(guò)維護(hù)一個(gè)二維數(shù)組簡(jiǎn)化了對(duì)候選簇的定位， 實(shí)現(xiàn)了對(duì)可能在劃分過(guò)程誤判的部分實(shí)例進(jìn)行二次聚類判斷， 提高了聚類精度和算法運(yùn)行效率.

改進(jìn)算法中還存在若干需要進(jìn)一步研究的問(wèn)題： 1)θ取值對(duì)不同的數(shù)據(jù)集是有所區(qū)別的， 尤其在大的數(shù)據(jù)集中， 取值的大小將影響大量的實(shí)例， 探索一個(gè)合理有效的θ取值規(guī)律和范圍是一項(xiàng)有意義的工作； 2) 從候選簇中確定召回實(shí)例有一定的效果， 但還是不夠全面， 特別是處在圖2中葉子節(jié)點(diǎn)位置的簇還未充分判斷.

參考文獻(xiàn)：

[1] 孫吉貴， 劉杰， 趙連宇. 聚類算法研究[J]. 軟件學(xué)報(bào)， 2008， 19(1): 48-50.

[2] TZORTZIS G， LIKAS A． The minmaxK-means clustering algorithm[J]. Pattern Recognition， 2014， 47(7): 2505-2516.

[3] MA G W， XU Z H， ZHANG W，etal. An enrichedK-means clustering method for grouping fractures with meliorated initial centers[J]. Arabian Journal of Geosciences， 2014， 8(4): 1881-1893.

[4] DING C， HE X. K-nearest-neighbor in data clustering: incorporating local information into global optimization[C]// Proceedings of the 2004 ACM Symposium on Applied Computing. Nicosia: ACM Press， 2004: 584-589.

[5] 張軍偉， 王念濱， 黃少濱， 等. 二分K均值聚類算法優(yōu)化及并行化研究[J]. 計(jì)算機(jī)工程， 2011， 37(17): 23-25.

[6] 裘國(guó)永， 張嬌. 基于二分K-均值的SVM決策樹(shù)自適應(yīng)分類方法[J]. 計(jì)算機(jī)應(yīng)用研究， 2012， 29(10): 3685-3687.

[7] 成衛(wèi)青， 盧艷紅. 一種基于最大最小距離和SSE的自適應(yīng)聚類算法[J]. 南京郵電大學(xué)學(xué)報(bào)(自然科學(xué)版)， 2015， 35(2): 102-107.

[8] LIU B. Web data mining[M]. Berlin: Springer-Verlag， 2009.

[9] HUANG Z. Extensions to theK-means algorithm for clustering large data sets with categorical values[J]. Data Mining and Knowledge， Discovery， 1998， 2(3): 283-304.

[10] 劉廣聰， 黃婷婷， 陳海南. 改進(jìn)的二分K均值聚類算法[J]. 計(jì)算機(jī)應(yīng)用與軟件， 2015， 32(2): 261-263.

[11] 左進(jìn)， 陳澤茂. 基于改進(jìn)K均值聚類的異常檢測(cè)算法[J]. 計(jì)算機(jī)科學(xué)， 2016， 43(8): 258-261.

[12] WITTEN I H， FRANK E. Data mining: practical machine learning tools and techniques[M]. 2nd. San Francisco: Morgan Kaufmann， 2005: 253-261.

[13] 李雯睿， 白晨希. 一種本體學(xué)習(xí)模型的設(shè)計(jì)與實(shí)現(xiàn)[J]. 河南大學(xué)學(xué)報(bào)(自然科學(xué)版)， 2006， 36(4): 100-102.

[14] 解小敏， 李云. 最小最大模塊化網(wǎng)絡(luò)中基于聚類的數(shù)據(jù)劃分方法研究[J]. 南京大學(xué)學(xué)報(bào)(自然科學(xué)版)， 2012， 48(2): 133-139.