基于距離閾值的自適應(yīng)K-均值聚類算法

曾慶山, 張貴勇

(鄭州大學(xué) 電氣工程學(xué)院 河南 鄭州 450001)

?

基于距離閾值的自適應(yīng)K-均值聚類算法

曾慶山, 張貴勇

(鄭州大學(xué) 電氣工程學(xué)院 河南 鄭州 450001)

為快速有效地確定聚類中心，提出一種基于距離閾值的自適應(yīng)K-均值聚類算法.首先確定合理的距離閾值，其次根據(jù)距離閾值確定初始聚類中心位置及個數(shù)，最后對位置相近的聚類中心簇進(jìn)行合并，獲得新的聚類中心位置及個數(shù).結(jié)果表明，該方法可以自動確定k值及中心位置，有效避免將離群點(diǎn)錯誤聚類，從而改善了聚類效果.

K-均值； 距離閾值； 聚類中心

0 引言

聚類分析在數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、模式識別、圖像分割等領(lǐng)域有著廣泛的應(yīng)用[1]，也是這些領(lǐng)域的研究熱點(diǎn)之一.目前，常用的聚類方法主要有劃分聚類、層次聚類、基于數(shù)據(jù)密度的聚類、基于網(wǎng)格的聚類、基于模型的聚類等[2].其中劃分聚類就是對給定的數(shù)據(jù)集，采用劃分的方法將其分為k個類，每個類至少有一個數(shù)據(jù)對象，每個數(shù)據(jù)對象只能屬于一個類.K-均值聚類是一種經(jīng)典的劃分聚類方法，該方法以確定的類數(shù)k和選定的初始類中心為前提，將各數(shù)據(jù)對象聚成多個類簇，使得同一個類簇的對象之間具有較高相似度，而不同類簇的對象之間具有較高相異度[3].目前對K-均值聚類算法的研究大致可以分為兩個方向：一個方向是初始類中心的選取.文獻(xiàn)[4]提出一種基于數(shù)據(jù)內(nèi)在密集性的初始類中心選取方法;文獻(xiàn)[5]對最大、最小距離算法進(jìn)行改進(jìn)，提出一種最大距離積法，選取與已初始的聚類中心距離最遠(yuǎn)的高密度的中心點(diǎn)作為當(dāng)前聚類中心.另一個方向是克服NP難問題.文獻(xiàn)[6]提出了一種全局的K-均值算法，該算法通過不斷地迭代確定最佳的初始類中心;文獻(xiàn)[7]引入特征權(quán)值的思想，提出了基于數(shù)據(jù)密度的初始類中心選取方法和改進(jìn)的特征賦權(quán)的K-均值算法;文獻(xiàn)[8]利用遺傳算法的全局尋優(yōu)能力改進(jìn)K-均值聚類算法;文獻(xiàn)[9]將K-均值聚類與改進(jìn)的人工蜂群算法相結(jié)合，提高了全局尋優(yōu)能力，克服了傳統(tǒng)K-均值聚類算法穩(wěn)定性差的缺點(diǎn).

初始k值的選取對最后的聚類效果有著直接的影響，尤其在數(shù)據(jù)集沒有給出準(zhǔn)確的類別個數(shù)，又對數(shù)據(jù)集無先驗(yàn)知識的情況下，很難確定合適的k值.即使k值可以確定，仍需要考慮到初始中心對K-均值聚類的影響.許多文獻(xiàn)給出了根據(jù)數(shù)據(jù)密度確定初始聚類中心的方法，但是數(shù)據(jù)密度的計算方法較為復(fù)雜.因此，本文提出了一種基于距離閾值的自適應(yīng)K-均值聚類算法.通過尋找合適的距離閾值，并根據(jù)該距離閾值對數(shù)據(jù)集進(jìn)行初始聚類以及初始聚類簇合并等，得到適合該數(shù)據(jù)集的聚類中心.該距離閾值的確定方法簡單易實(shí)現(xiàn)，可以在無監(jiān)督學(xué)習(xí)的情況下，自動地確定數(shù)據(jù)集的聚類中心個數(shù)k以及聚類中心位置，克服離群點(diǎn)對聚類結(jié)果的干擾，獲得更穩(wěn)定、更好的聚類效果.

1 改進(jìn)的K-均值聚類算法

1.1 傳統(tǒng)K-均值聚類算法

傳統(tǒng)K-均值聚類算法的基本思想為：從數(shù)據(jù)集中隨機(jī)選取k個樣本作為初始聚類中心；剩余數(shù)據(jù)樣本根據(jù)它們與這些初始聚類中心的相似度量，將它們分配給與其最相似的聚類；計算每個聚類的新的類中心(一般是該聚類所有樣本的平均值)；不斷重復(fù)上述過程，直到聚類中心收斂.算法的具體過程如下：

1)對于給定的數(shù)據(jù)集X={x1,x2,…,xn}，n為數(shù)據(jù)集的樣本個數(shù)，隨機(jī)選取k個樣本作為初始聚類中心C={c1,c2,…,ck}.

2)將數(shù)據(jù)集中的每個樣本與當(dāng)前k個聚類中心分別計算歐氏距離，然后將樣本放入與其距離最近的類中心所對應(yīng)的聚類簇中，最后得到初始聚類后k個聚類簇G={g1,g2,…,gk}.

4)重復(fù)步驟2)和3)，直至聚類中心不再變化，得到最終的k個聚類簇，聚類過程結(jié)束.

1.2 改進(jìn)的自適應(yīng)K-均值聚類算法

對于未標(biāo)記的數(shù)據(jù)集，在沒有先驗(yàn)知識的情況下，很難給出準(zhǔn)確的k值以及聚類中心位置.改進(jìn)的自適應(yīng)K-均值聚類算法的原理為：首先確定一個合適大小的距離閾值，然后根據(jù)該閾值對數(shù)據(jù)集進(jìn)行初始聚類，確定初始的k值及聚類中心位置，最后對距離較近的類進(jìn)行合并，確定最終的k值及聚類中心位置.算法的具體過程如下：

1)對于給定的數(shù)據(jù)集X={x1,x2,…,xn}，n為數(shù)據(jù)集的樣本個數(shù)，確定合適的距離閾值d.

2)從數(shù)據(jù)集X中隨機(jī)抽取一個樣本作為第一個類中心c1，并放入聚類中心集合C1中，更新數(shù)據(jù)集(將抽出的樣本從當(dāng)前數(shù)據(jù)集中剔除，獲得新數(shù)據(jù)集，下同).

3)從當(dāng)前數(shù)據(jù)集中隨機(jī)抽取一個樣本，將其與聚類中心集合C1中的每個類中心分別計算歐氏距離.若這些距離中的最小值dmin≥2d，則將該樣本作為新的類中心放入C1中，更新數(shù)據(jù)集；若0≤dmin≤2d，則直接更新數(shù)據(jù)集.重復(fù)該步驟直至遍歷完整個數(shù)據(jù)集，得到初始聚類中心集合C1={c11,c12,…,c1k1}.

4)將原始數(shù)據(jù)集中的每個樣本與當(dāng)前k1個類中心分別計算歐氏距離，然后將每個樣本放入與其距離最近的類中心所對應(yīng)的聚類簇中，最后得到k1個聚類簇G1={g11,g12,…,g1k1}.

6)重復(fù)步驟4)和5)，直至聚類中心不再變化.計算當(dāng)前聚類中心集合中兩兩類中心的歐氏距離，如果某兩個類中心的歐氏距離dmn(m和n分別表示第m和n個類中心)滿足dmn≤2d，則將這兩個類中心對應(yīng)的兩個聚類簇合并成一個聚類簇，重新計算平均類中心，最后得到新的聚類中心集合C2={c21,c22,…,c2k2}，k2表示當(dāng)前類中心的個數(shù).

7)將原始數(shù)據(jù)集中的每個樣本與當(dāng)前k2個類中心分別計算歐氏距離，然后將每個樣本放入與其距離最近的類中心所對應(yīng)的聚類簇中，最后得到k2個聚類簇G2={g21,g22,…,g2k2}，計算每個聚類簇的平均類中心，得到新的聚類中心集合C2={c21,c22,…,c2k2}.

8)重復(fù)步驟7)，直至聚類中心不再變化，得到最終的聚類中心集合，記為C={c1,c2，…,ck}，原始數(shù)據(jù)集中的每個樣本與當(dāng)前k個類中心分別計算歐氏距離，然后將樣本放入與其距離最近的類中心所屬的簇中，最后得到k個聚類簇G={g1,g2,…,gk}，完成聚類.

1.3 距離閾值的確定方法

距離閾值直接影響著k值的確定，進(jìn)而影響聚類效果.如果距離閾值太小，則會出現(xiàn)類別過多，甚至無法完成有效聚類；如果距離閾值太大，則會將整個數(shù)據(jù)集聚成一個類.本文引入數(shù)據(jù)密度的思想，給出一種確定距離閾值的方法，即對數(shù)據(jù)集進(jìn)行采樣，計算抽取的樣本之間的距離，從中尋找合適的距離閾值.具體過程為：首先從數(shù)據(jù)集中抽取m個樣本，計算m個樣本兩兩之間的歐氏距離，得到m(m-1)/2 個距離值；然后對其進(jìn)行升序排序，截取前1/3部分的距離值，求平均值，該平均值定為距離閾值.結(jié)合相關(guān)資料以及經(jīng)過本文檢驗(yàn)，當(dāng)樣本容量m≈M/10(M為數(shù)據(jù)集大小)時，可獲得合適大小的距離閾值.通過這種方法確定的距離閾值偏小，但是不會太小.理論上這種情況是合理的，因?yàn)橥ㄟ^適當(dāng)小的距離閾值可獲得較多的初始聚類簇，有利于二次聚類.

1.4 聚類有效性評價指標(biāo)

聚類有效性評價指標(biāo)用于評判聚類結(jié)果的質(zhì)量，因此，選擇合適的評價指標(biāo)尤為重要.目前已經(jīng)有一些用于評價聚類效果優(yōu)劣的指標(biāo)，其中性能較好的有Calinski-Harabasz(CCH)指標(biāo)、Weighted inter-intra(WWint)指標(biāo)、In-Group Proportion (IIGP)指標(biāo)和Silhouette(SSil)指標(biāo)等[2].其中SSil指標(biāo)簡單易用且具有良好的評價能力，得到了廣泛應(yīng)用.本文采用SSil指標(biāo)作為聚類效果優(yōu)劣的評價指標(biāo)，其具體定義為

(1)

式中：樣本xi屬于簇gi；a(xi) 表示樣本xi到簇gi中剩余樣本的平均距離；b(xi) 表示樣本xi到其他簇中樣本的平均距離最小值.即

(2)

當(dāng)SSil(xi)接近于1時，表示將xi劃分到簇gi中是合適的；當(dāng)SSil(xi)接近于0時，表示xi可能屬于距離簇gi最近的簇；當(dāng)SSil(xi)接近于-1時，表示xi被錯分到簇gi中.由此可以看出，SSil指標(biāo)既能反映出類內(nèi)樣本的相似程度，又能反映出類間樣本的相異程度.數(shù)據(jù)集所有樣本的平均SSil指標(biāo)值越大，說明聚類效果越好，反之越差.所有樣本的平均SSil指標(biāo)值定義為

(3)

式中：n為數(shù)據(jù)集樣本個數(shù).

另外，由于選取的數(shù)據(jù)集類別已知，因此，選擇聚類準(zhǔn)確率作為最后聚類效果的參考指標(biāo).聚類準(zhǔn)確率是被正確劃分的數(shù)據(jù)樣本的比率，其值越高說明聚類效果越好.

2 實(shí)驗(yàn)仿真及分析

2.1 實(shí)驗(yàn)仿真過程

為了驗(yàn)證本文方法(A)的聚類有效性,選取文獻(xiàn)[10]中的方法(S)、文獻(xiàn)[11]中的方法(K)，文獻(xiàn)[12]中的方法(H)、經(jīng)典K-均值聚類算法(B)4種K-均值聚類算法進(jìn)行對比，在國內(nèi)外文獻(xiàn)中常用的6個數(shù)據(jù)集上進(jìn)行驗(yàn)證，每種方法分別在這6個數(shù)據(jù)集上各運(yùn)行50次，以聚類準(zhǔn)確率、平均SSil指標(biāo)以及平均運(yùn)行時間作為評價標(biāo)準(zhǔn).為了驗(yàn)證對含離群點(diǎn)以及帶狀分布數(shù)據(jù)的聚類有效性，選取經(jīng)典K-均值聚類算法(B)作為對比，在人工數(shù)據(jù)集Testset上進(jìn)行驗(yàn)證.

2.2 實(shí)驗(yàn)數(shù)據(jù)說明

采用的7個數(shù)據(jù)集分別為4k2_far、Iris、Leuk72_3k、Wine、Breast Cancer Wisconsin、Glass Identification、Testset.其中Iris、Wine、Breast Cancer Wisconsin、Glass Identification數(shù)據(jù)集來源于UCI標(biāo)準(zhǔn)數(shù)據(jù)集，Testset數(shù)據(jù)集是包含離群點(diǎn)且呈帶狀分布的人工數(shù)據(jù)集，4k2_far、Leuk72_3k數(shù)據(jù)集是模擬數(shù)據(jù)集[13].表1描述了數(shù)據(jù)集的詳細(xì)信息.

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

編號數(shù)據(jù)集樣本數(shù)特征數(shù)類別14k2＿far400242Iris150433Leuk72＿3k723934Wine1781335BreastCancerWisconsin699986GlassIdentification214967Testset8025

雖然這些數(shù)據(jù)集都已知類別個數(shù)，但是不作為本文算法的參數(shù)，僅用于最后的性能評價.由于數(shù)據(jù)集每一維度的量綱不同，對數(shù)據(jù)進(jìn)行了歸一化處理，使數(shù)據(jù)分布在[0,1]范圍內(nèi).歸一化公式為

(4)

2.3 仿真結(jié)果及分析

表2給出S、K、H、B和A 5種算法在6個數(shù)據(jù)集上運(yùn)行50次后的聚類準(zhǔn)確率.表3給出5種算法在6個數(shù)據(jù)集上運(yùn)行50次后的平均SSil指標(biāo)值.表4給出5種算法在6個數(shù)據(jù)集上運(yùn)行50次后的平均運(yùn)行時間.

表2 聚類準(zhǔn)確率
Tab.2 The precision of clustering

數(shù)據(jù)集編號算法SKHBA10．960．940．920．900．9620．880．860．900．880．8630．920．940．920．900．9440．900．880．840．860．9250．880．920．880．840．9460．940．900．900．900．92

表3 平均SSil指標(biāo)
Tab.3 The average value of SSil

數(shù)據(jù)集編號算法SKHBA10．910．890．900．870．9220．870．850．890．840．7930．840．860．820．730．8640．710．690．730．650．7550．890．920．910．760．9360．860．830．800．810．85

表4 平均運(yùn)行時間

從表2可以看出，本文方法(A)是5種算法中聚類效果最好的，在6個測試數(shù)據(jù)集中的4個數(shù)據(jù)集上的聚類準(zhǔn)確率最高，且在特征數(shù)較多時也能表現(xiàn)出良好的聚類性能.表3給出了5種算法完成50次聚類后的平均SSil指標(biāo)值，該值越接近于1，聚類結(jié)果越合理，可以看出，本文方法在4個數(shù)據(jù)集上的平均SSil指標(biāo)值都更接近于1.從表4中5種算法的平均運(yùn)行時間來看，本文方法的計算時間相對較長，這是因?yàn)樵诟鶕?jù)距離閾值進(jìn)行初始聚類時需要反復(fù)迭代，但是與方法H相比，本文方法的運(yùn)行時間還是較低的.經(jīng)典K-均值聚類算法(B)的運(yùn)行時間最短，是因?yàn)槠錄]有進(jìn)行初始類中心的優(yōu)化，迭代過程較為簡單.

圖1顯示了Testset數(shù)據(jù)集的原始分布圖，圖2給出了經(jīng)典K-均值聚類方法在該數(shù)據(jù)集上的聚類效果，圖3給出了本文方法的聚類效果.圖2和圖3中的圓圈表示聚類中心，其他不同形狀的圖形表示屬于不同的類.

圖1 Testset數(shù)據(jù)集的原始分布圖Fig.1 The original distribution of Testset data set

圖2 經(jīng)典K-均值聚類效果Fig.2 The clustering effect of classic K-means

圖3 本文方法的聚類效果Fig.3 The clustering effect of the proposed method

從圖1中可以看出，原始數(shù)據(jù)集Testset包含4個呈帶狀分布的樣本簇以及1個離群樣本點(diǎn)，其類中心應(yīng)當(dāng)是5個.當(dāng)這4個簇中的某兩個簇的中心距離小于單個簇的分布長度時，經(jīng)典K-均值聚類方法很容易將一個簇的樣本錯分到另一個簇，同樣也很難識別出離群樣本點(diǎn)而將其錯分到某一個簇中，聚類效果如圖2所示.從圖3中可以看出，采用本文方法對Testset數(shù)據(jù)集進(jìn)行聚類時(此時距離閾值為0.088)，可對帶狀分布的樣本簇和離群樣本點(diǎn)進(jìn)行正確劃分.

3 結(jié)束語

提出了一種基于距離閾值的自適應(yīng)K-均值聚類算法，并給出了一種確定距離閾值的方法.通過確定合適的距離閾值獲取初始的k值，并引入層次聚類的思想優(yōu)化k值，最終確定合適的聚類中心個數(shù)k以及它們的位置.本文算法易于實(shí)現(xiàn)，可以在對數(shù)據(jù)無先驗(yàn)知識、數(shù)據(jù)類別不確定的情況下，依據(jù)數(shù)據(jù)本身的分布特點(diǎn)，自動地確定合適k值以及聚類中心位置，同時也能取得很好的聚類效果.當(dāng)數(shù)據(jù)集呈帶狀分布或者包含離群點(diǎn)時，本文方法可以對數(shù)據(jù)進(jìn)行正確的劃分，避免離群點(diǎn)對聚類效果的干擾，表現(xiàn)出更好的性能.但是在實(shí)驗(yàn)中也發(fā)現(xiàn)，距離閾值影響著最終的聚類效果.在后續(xù)的研究工作中，將尋找更好的距離閾值的確定方法，以提高算法的準(zhǔn)確性.

[1] 張志兵.空間數(shù)據(jù)挖掘及其相關(guān)問題研究[M].武漢：華中科技大學(xué)出版社，2011.

[2] 何云斌，肖宇鵬，萬靜，等. 基于密度期望和有效性指標(biāo)的K-均值算法[J].計算機(jī)工程與應(yīng)用，2013,49(24)：105-111.

[3] 王輝，張望，范明.基于集群環(huán)境的K-means聚類算法的并行化[J].河南科技大學(xué)學(xué)報(自然科學(xué)版)，2008,29(4)：42-45．

[4] 韓最蛟.基于數(shù)據(jù)密集性的自適應(yīng)K均值初始化方法[J].計算機(jī)應(yīng)用與軟件，2014,31(2)：182-187.

[5] 熊忠陽，陳若田，張玉芳.一種有效的K-means聚類中心初始化方法[J].計算機(jī)應(yīng)用研究,2011,28(11)：4188-4190.

[6] LIKAS A, VLASSIS N,VERBEEK J J. The globalK-means clustering algorithm[J].Pattern recognition,2003,36(2):451-461.

[7] 任江濤，施瀟瀟，孫婧昊，等.一種改進(jìn)的基于特征賦權(quán)的K均值聚類算法[J].計算機(jī)科學(xué)，2006，33(7)：186-187.

[8] 徐家寧，張立文，徐素莉，等.改進(jìn)遺傳算法的K-均值聚類算法研究[J].微計算機(jī)應(yīng)用，2010，31(4)：11-15.

[9] 畢曉君，宮汝江.一種結(jié)合人工蜂群和K-均值的混合聚類算法[J].計算機(jī)應(yīng)用研究，2012，29(6)：2040-2046.

[10] 沈國珍.依賴數(shù)據(jù)密度的K均值初始化調(diào)優(yōu)[J] .計算機(jī)工程與應(yīng)用，2014，50(11)：139-144.

[11] ARTHUR D，VASSILVITSKII S．K-means++：the advantages of careful seeding[C]//Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms．New Orleans,2007：1027-1035．

[12] 韓凌波，王強(qiáng)，蔣正峰，等．一種改進(jìn)的K-means初始聚類中心選取算法[J]．計算機(jī)工程與應(yīng)用，2010，46(17)：150-152．

[13] 王磊，汪西莉，劉高霞，等.一種結(jié)合半監(jiān)督的改進(jìn)自適應(yīng)親和傳播聚類[J].計算機(jī)應(yīng)用研究,2010，27(12)：4436-4442.

(責(zé)任編輯：孔 薇)

An AdaptiveK-means Clustering Method Based on Distance Threshold

ZENG Qingshan， ZHANG Guiyong

(SchoolofElectricalEngineering,ZhengzhouUniversity,Zhengzhou450001,China)

An adaptiveK-means clustering approach based on distance threshold was proposed to get a proper clustering result. Firstly, a reasonable distance threshold was obtained from a given dataset. Then the initial clustering centers were set based on the distance threshold. Clusters with centers close to each other were merged to a new clustering center. Experimental results proved that the suitable value ofkand clustering centers could be found with the proposed method, and outliers could effectively be avoided being clustered incorrectly,thus the cluster effect was improved.

K-means； distance threshold； clustering center

2016-08-20

河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項目(14A120003).

曾慶山(1963—)，男，湖北武漢人，教授，主要從事復(fù)雜系統(tǒng)建模及圖像信號處理研究，E-mail：qszeng@126.com；張貴勇(1990—)，男，河南新鄉(xiāng)人，碩士研究生，主要從事模式識別與智能系統(tǒng)研究，E-mail：zhangguiyong186@163.com.

曾慶山，張貴勇.基于距離閾值的自適應(yīng)K-均值聚類算法[J].鄭州大學(xué)學(xué)報(理學(xué)版)，2016,48(4)：90-94.

TP181

A

1671-6841(2016)04-0090-05

10.13705/j.issn.1671-6841.2016680