藺艷艷 陸介平 王郁鑫 傅廷妍

（江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212001）

1 引言

隨著互聯(lián)網(wǎng)在生產(chǎn)生活中應(yīng)用的越來越廣泛，隨之產(chǎn)生的是大量的數(shù)據(jù)。這些數(shù)據(jù)往往潛藏著用戶的行為動(dòng)向或某個(gè)行業(yè)的發(fā)展規(guī)律。如何從這些海量數(shù)據(jù)中挖掘到有價(jià)值的信息是我們今天的研究熱點(diǎn)。聚類是數(shù)據(jù)挖掘中的一個(gè)非常重要的分支，它是根據(jù)信息相似度原則在預(yù)先不知道預(yù)劃分類的情況下進(jìn)行信息聚類的一種方法。k-means算法［1］是一種典型的基于劃分的聚類算法，自1967年MacQueen提出后，由于其具有算法簡單易懂且收斂速度快的優(yōu)點(diǎn)，得到較普遍的應(yīng)用［2］。比如，利用k-means聚類方法來對(duì)客戶進(jìn)行準(zhǔn)確的分類，其結(jié)果可以作為企業(yè)優(yōu)化營銷資源的重要依據(jù)等等。

但是，傳統(tǒng)的k-means算法是二支聚類，它不適用具有不確定因素的環(huán)境，并且k-means算法需要預(yù)先隨機(jī)選取初始聚類中心和設(shè)定聚類數(shù)目［3］，這些因素將導(dǎo)致聚類結(jié)果不穩(wěn)定，影響其精確性。有許多學(xué)者對(duì)k-means算法進(jìn)行研究和改進(jìn)，F(xiàn)eng等改進(jìn)k-means算法［4］是根據(jù)數(shù)據(jù)點(diǎn)的距離構(gòu)造最小生成樹，并加以剪枝來構(gòu)造樣本分布情況，從而動(dòng)態(tài)選取初始聚類中心。Yu等提出了一種結(jié)合關(guān)系矩陣和度中心性（Degree Centrality）的分析方法，從而確定k-means算法初始的k個(gè)中心點(diǎn)［5］。為了能自動(dòng)選擇k-means算法的初始k值，Debatty等提出了 G-means算法［6］，Yuan 等加入密度參數(shù)并通過計(jì)算平均密度來降噪［7］，Kettani等提出AK-means算法［8］等。但是，這些方法對(duì)局部最優(yōu)、聚類結(jié)果不穩(wěn)定和總迭代次數(shù)多等問題進(jìn)行優(yōu)化，并且在處理不確定性信息時(shí)，考慮到當(dāng)前獲取到的信息不夠充分的特點(diǎn)，如果強(qiáng)制將其中的元素劃分到一個(gè)類中，往往容易帶來較高的錯(cuò)誤率或決策風(fēng)險(xiǎn)?；诖?，Hoppner等提出用模糊集表示聚類結(jié)果的模糊聚類理論方法［9］，Lingras提出了粗糙聚類方法，將聚類結(jié)果由粗糙集的正域，邊界域和負(fù)域來表示［10-13］，Yao等用區(qū)間集來表示聚類結(jié)果中的一個(gè)類［14］等，這些方法計(jì)算復(fù)雜，對(duì)指標(biāo)權(quán)重矢量的確定主觀性較強(qiáng)。三支決策聚類理論的提出，有效地改善了傳統(tǒng)聚類方法處理具有不確定性因素的問題，并且可與傳統(tǒng)聚類算法結(jié)合，計(jì)算相對(duì)簡單。

三支決策聚類是一種重疊聚類，早先由Yao、Yu［15～17］等提出，它采用核心域、邊界域和瑣碎域來表示每個(gè)類別，其中邊界域中的元素是介于核心域和瑣碎域之間的元素，集中對(duì)邊界域中的元素判斷處理，可以較好地處理具有不確定性對(duì)象的聚類問題。在三支決策理論中，傳統(tǒng)的k-means二支聚類算法是一種特殊的三支聚類，即邊界域中的元素為空。有學(xué)者Li［18］利用傳統(tǒng)k-means聚類算法產(chǎn)生的結(jié)果和每個(gè)類中元素的鄰域所在的集合進(jìn)行收縮與擴(kuò)張，來研究將二支聚類轉(zhuǎn)化為三支聚類的方法，達(dá)到提高聚類結(jié)果的數(shù)據(jù)結(jié)構(gòu)的目的。但是，這些方法均是直接使用傳統(tǒng)k-means算法，聚類結(jié)果的準(zhǔn)確性和確定性受k-means算法缺點(diǎn)影響。

針對(duì)傳統(tǒng)k-means算法不適用具有不確定因素的環(huán)境和現(xiàn)有的基于k-means的三支聚類分析中并未避免傳統(tǒng)k-means聚類隨機(jī)選擇初始簇中心而導(dǎo)致聚類結(jié)果不穩(wěn)定的問題，本文提出一種改進(jìn)的k-means聚類方法，避免了傳統(tǒng)k-means算法由于初始簇中心選擇的隨機(jī)性而導(dǎo)致聚類結(jié)果不穩(wěn)定的現(xiàn)象；其次，為了避免傳統(tǒng)k-means算法在處理不確定性信息時(shí)，強(qiáng)制將其中的元素劃分到一個(gè)類中帶來的錯(cuò)誤率或決策風(fēng)險(xiǎn)，將改進(jìn)的k-means算法與Wang提出的將二支聚類結(jié)果轉(zhuǎn)換成三支聚類方法結(jié)合起來，研究本文所提出的方法在三支決策中的應(yīng)用，以提高聚類結(jié)果的結(jié)構(gòu)和精度，實(shí)驗(yàn)結(jié)果證明這種方法是有效的。

2 相關(guān)知識(shí)

2.1 k-means算法

k-means算法［19］原理簡單易懂，時(shí)間復(fù)雜度低，僅為O( )kNT ，并且具有計(jì)算簡單、高效等特點(diǎn)，廣泛應(yīng)用在生產(chǎn)生活的各個(gè)領(lǐng)域。k-means算法基于樣本間相似度原則，采用兩樣本間的歐氏距離遠(yuǎn)近作為衡量標(biāo)準(zhǔn)進(jìn)行數(shù)據(jù)集劃分。k-means的算法理論是：在數(shù)據(jù)集D中，先隨機(jī)選取k個(gè)樣本作為初始中心，再計(jì)算剩下的所有樣本到這一組初始中心的歐氏距離，根據(jù)距離最近原則將各個(gè)樣本歸入到相應(yīng)的聚類中心所在的類，然后計(jì)算每個(gè)類的新均值，重新修正聚類中心。不斷迭代更新，直到誤差平方和函數(shù)穩(wěn)定在最小值。

其中：k為聚類類別數(shù)，ri為第i類中的樣本的個(gè)數(shù)，ni為第i類中樣本的平均值。

2.2 三支決策聚類的相關(guān)概念

其中式（3）表明，可通過和來表示一個(gè)類，式（4）要求正域非空，即每個(gè)類中至少有一個(gè)對(duì)象，而式（5）保證每個(gè)對(duì)象至少被分到一個(gè)類中。與二支聚類結(jié)果不同，三支聚類的結(jié)果可由下式來表示：

2.3 基于傳統(tǒng)k-means算法的三支聚類

二支決策的聚類結(jié)果是對(duì)象一定屬于兩個(gè)類中的一個(gè)，而三支決策的聚類結(jié)果是：對(duì)象確定屬于某類、可能屬于某類或確定不屬于某類?？梢哉f二支決策是三支決策類結(jié)果中的一種，即不存在邊界區(qū)域。

圖1 數(shù)據(jù)集圖

如果刪除x1和x2，則很容易地將圖1聚成兩個(gè)結(jié)構(gòu)特征非常好的類，而無論將x1或x2放到哪一個(gè)類中均會(huì)降低這個(gè)類的緊致性?；谌Q策聚類的核心思想，將x1和x2放到兩個(gè)類的邊界域當(dāng)中去。定義一個(gè)θ域（距離該點(diǎn)最近的θ個(gè)點(diǎn)組成的集合），使θ域內(nèi)的點(diǎn)在二支聚類的結(jié)果下不完全包含于某個(gè)類中，例如x1和x2這類點(diǎn)。這樣先采用k-means聚類的結(jié)果，再結(jié)合θ域（邊界域）的進(jìn)行決策聚類的方法，便是基于傳統(tǒng)k-means算法的三支聚類。

3 改進(jìn)的k-means算法在三支決策中的應(yīng)用研究

3.1 改進(jìn)的k-means算法

傳統(tǒng)的k-means算法的缺點(diǎn)是隨機(jī)地選取任意k個(gè)樣本作為初始聚類中心，這種隨機(jī)性會(huì)影響最終聚類結(jié)果的穩(wěn)定性。本文提出的k-means算法的改進(jìn)能夠克服上述問題。首先，先對(duì)數(shù)據(jù)集進(jìn)行凝聚層次聚類，并采用輪廓系數(shù)對(duì)不同層次劃分進(jìn)行評(píng)估，獲得較為合理中心數(shù)K。再對(duì)數(shù)據(jù)集進(jìn)行n次樣本抽?。╪次抽取的樣本總數(shù)要大于等于原始樣本數(shù)），并以層次聚類所得K值做為輸入對(duì)其進(jìn)行k-means聚類，從而得出一組中心。然后計(jì)算這n組中心的誤差平方和準(zhǔn)則函數(shù)值，選擇值最小所對(duì)應(yīng)的聚類中心作為初始聚類中心。最后將其作為k-means三支聚類算法的初始中心和k值的輸入，避免了k-means算法隨機(jī)選擇初始中心和k值而導(dǎo)致最終三支聚類結(jié)果不穩(wěn)定的問題。其中，多次抽取樣本可以保持隨機(jī)性不被破壞。層次聚類算法可以在其聚類結(jié)果上采用輪廓系數(shù)對(duì)數(shù)據(jù)集的不同層次劃分進(jìn)行評(píng)估，在初始中心確定前先初步優(yōu)化簇?cái)?shù)K，最終的初始中心是由收斂函數(shù)來選取。為防止因適應(yīng)誤差平方和準(zhǔn)則函數(shù)而陷于局部最優(yōu)或?qū)е麓剡^度劃分，可以采取設(shè)定初始聚類中心數(shù)大于指定的K值，并且設(shè)定準(zhǔn)則函數(shù)收斂標(biāo)準(zhǔn)，使達(dá)到收斂后的初始聚類中心數(shù)在合并距離近的簇之后數(shù)量減少到指定的K值。

層次聚類中需要用的公式具體如下：

3.2 改進(jìn)的k-means算法在三支決策中的應(yīng)用研究

本文將層次聚類和科學(xué)抽樣法引入到k-means算法中，是為了獲取最優(yōu)初始簇類的數(shù)目，避免k-means算法隨機(jī)選擇k值和初始聚類中心而導(dǎo)致分類結(jié)果誤差較大、聚類結(jié)果不穩(wěn)定等問題。然后將改進(jìn)后的k-means算法聚類的結(jié)果做為三支聚類的初始輸入，實(shí)現(xiàn)最優(yōu)類別劃分的問題。

前文提到的θ域這里給出詳細(xì)定義：

因?yàn)棣鹊倪x取也會(huì)對(duì)最終聚類結(jié)果產(chǎn)生影響，所以選擇合適的θ很重要，這里選取的θ是數(shù)據(jù)集中樣本數(shù)目的開平方，即N。

算法1：改進(jìn)的k-means算法在三支決策中的應(yīng)用

Step1：通過式（6）、式（7）將U中所有樣本都合并成一類，利用輪廓系數(shù)對(duì)聚類結(jié)果進(jìn)行評(píng)估，得到較為合理的K值；

Step2：對(duì)U進(jìn)行多次抽樣，通過式（1）對(duì)每次抽取的樣本進(jìn)行k-means聚類，得到一組中心；

4 幾種聚類性能度量的指標(biāo)

4.1 平均輪廓系數(shù)

輪廓系數(shù)（silhouette coefficient）［20］是聚類效果好壞的一種評(píng)價(jià)方式，它結(jié)合內(nèi)聚度和分離度兩種因素，在相同原始數(shù)據(jù)的基礎(chǔ)上，評(píng)價(jià)不同算法或算法的不同運(yùn)行方式對(duì)聚類結(jié)果所產(chǎn)生的影響。

計(jì)算某一個(gè)點(diǎn)的輪廓系數(shù)公式：

其中：表示i點(diǎn)向量到與它同簇的其他點(diǎn)的平均距離；表示i點(diǎn)向量到與它異簇的點(diǎn)的平均距離最小值。由上式可知，輪廓系數(shù)的值為[- 1，1]，如果輪廓系數(shù)S(i)值越大，則表明i點(diǎn)所在的簇就越緊密。

對(duì)于整個(gè)數(shù)據(jù)集來說，其輪廓系數(shù)的計(jì)算公式如下：

其中：n表示數(shù)據(jù)集中的樣本總數(shù)；SC值越大，則聚類效果越好，反之越差。

4.2 Davies-Bouldin-Index評(píng)價(jià)準(zhǔn)則

Davies-Bouldin-Index（DBI）［21］，聚 類 結(jié) 果 的DBI越小，聚類效果越好。公式如下：

4.3 準(zhǔn)確率

準(zhǔn)確率（accuracy）是常見的一種評(píng)價(jià)聚類性能的外部指標(biāo)。準(zhǔn)確率越高，聚類效果越好。計(jì)算公式為

其中N是所有已被確定類別的對(duì)象的總數(shù)，k是聚類數(shù)，θi是第i個(gè)類中正確劃分的數(shù)據(jù)對(duì)象的個(gè)數(shù)。

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

本節(jié)選用5組標(biāo)準(zhǔn)UCI［22］數(shù)據(jù)集對(duì)本文提出的算法進(jìn)行測(cè)試實(shí)驗(yàn)來驗(yàn)證方法的性能。表1列出了實(shí)驗(yàn)中所使用的5組測(cè)試數(shù)據(jù)集的基本信息。對(duì)于每個(gè)數(shù)據(jù)集，重復(fù)進(jìn)行了200次實(shí)驗(yàn)，用200次的平均值作為算法性能差異比較的依據(jù)。

表1 實(shí)驗(yàn)所使用的數(shù)據(jù)集

本文設(shè)置兩個(gè)實(shí)驗(yàn)來說明提出的改進(jìn)的k-means算法以及基于改進(jìn)k-means算法的三支決策的聚類效果和準(zhǔn)確率。將改進(jìn)的k-means算法記為k-means PA。

第一個(gè)實(shí)驗(yàn)是二支聚類的測(cè)試，通過對(duì)比一些已有的算法，即首先用fuzzy c-means、k-medoid、傳統(tǒng)k-means和k-means PA分別在表1中的數(shù)據(jù)集上進(jìn)行聚類來驗(yàn)證本文提出的k-means PA算法的聚類結(jié)果DBI和準(zhǔn)確率，以及聚類結(jié)果的穩(wěn)定性。

第二個(gè)實(shí)驗(yàn)是在第一個(gè)實(shí)驗(yàn)的基礎(chǔ)上，結(jié)合本文介紹的三支決策方法進(jìn)一步優(yōu)化聚類結(jié)果。最后通過實(shí)驗(yàn)數(shù)據(jù)分別比較二支聚類和三支聚類兩組實(shí)驗(yàn)結(jié)果的DBI和ACC。

5.1 實(shí)驗(yàn)一

圖2是fuzzy c-means、k-medoid、傳統(tǒng)k-means和k-means PA四種算法表1中的數(shù)據(jù)集上進(jìn)行二支聚類后結(jié)果的DBI對(duì)比圖。由圖可知，本文提出的算法k-means PA在UCI的5個(gè)數(shù)據(jù)集上，其DBI均低于fuzzy c-means、k-medoid和傳統(tǒng)k-means的DBI，在Sonar數(shù)據(jù)集上尤其明顯。在Wine數(shù)據(jù)集上，本文算法與傳統(tǒng)k-means基本相同，低于fuzzy c-means和k-medoid。

圖3是fuzzy c-means、k-medoid、傳統(tǒng)k-means和k-means PA四種算法表1中的數(shù)據(jù)集上進(jìn)行二支聚類后結(jié)果的準(zhǔn)確率對(duì)比圖。由圖可知，本文提出的算法k-means PA在Iris數(shù)據(jù)集上的準(zhǔn)確率沒有 fuzzy c-means、k-medoid的 ACC 高，但比傳統(tǒng)k-means的準(zhǔn)確率要高；在Hill、Sonar和Wine數(shù)據(jù)集上，k-means PA的準(zhǔn)確率要高于其他三種算法；在Wdbc數(shù)據(jù)集上，k-means PA的準(zhǔn)確率和其他三種算法的準(zhǔn)確率不分伯仲。

圖2 算法DBI實(shí)驗(yàn)結(jié)果

圖3 算法準(zhǔn)確率實(shí)驗(yàn)結(jié)果

綜合圖2和圖3來，本文提出的改進(jìn)算法在UCI的5個(gè)數(shù)據(jù)集上獲得了較好的DBI和準(zhǔn)確率，因此，本文的算法能適應(yīng)于不同數(shù)據(jù)集的聚類挖掘。

5.2 實(shí)驗(yàn)二

實(shí)驗(yàn)二是在實(shí)驗(yàn)一的基礎(chǔ)上進(jìn)行的三支聚類，圖 4和圖 5是基于 fuzzy c-means、k-medoid、傳統(tǒng)k-means和改進(jìn)k-means算法結(jié)合三支聚類理論的聚類結(jié)果的DBI和ACC對(duì)比圖。

圖4 三支聚類結(jié)果DBI對(duì)比圖

圖5 三支聚類結(jié)果ACC對(duì)比圖

圖6 基于k-means PA的二支聚類和三支聚類結(jié)果的DBI和ACC對(duì)比圖

由圖可知，三支聚類結(jié)果的DBI和ACC對(duì)比結(jié)論同實(shí)驗(yàn)一。但從圖6中可以明顯看出基于本文提出的k-means PA算法的三支聚類結(jié)果的DBI比k-means PA二支聚類結(jié)果的DBI低，基于本文提出的k-means PA算法的三支聚類結(jié)果的ACC比k-means PA二支聚類結(jié)果的ACC高，這表明結(jié)合三支聚類方法的聚類效果更好，準(zhǔn)確率更高。綜上所述，本文提出的改進(jìn)的k-means算法在三支聚類算法中應(yīng)用是有效的。

5.3 穩(wěn)定性

由于傳統(tǒng)k-means算法在聚類時(shí)結(jié)果存在不穩(wěn)定現(xiàn)象，因此，對(duì)提出改進(jìn)行算法的聚類結(jié)果進(jìn)行了穩(wěn)定性實(shí)驗(yàn)。選取其中一個(gè)數(shù)據(jù)集并進(jìn)行30次運(yùn)行實(shí)驗(yàn)，其結(jié)果如圖7所示。從圖7可以看出，傳統(tǒng)的k-means算法穩(wěn)定性較差，結(jié)果會(huì)隨著運(yùn)行次數(shù)不同而呈現(xiàn)不同的聚類結(jié)果，而本文提出的聚類算法的聚類結(jié)果呈現(xiàn)出較好的穩(wěn)定性。

圖7 算法穩(wěn)定性比較

6 結(jié)語

本文針對(duì)傳統(tǒng)k-means聚類算法初始中心的選取做了改進(jìn)，并結(jié)合Yu等學(xué)者研究的基于鄰域的三支聚類理論，提出一種改進(jìn)的k-means算法并結(jié)合三支聚類的算法，解決了初始中心和k值的選取問題和處理不確定性信息時(shí)最優(yōu)類別劃分的問題。實(shí)驗(yàn)結(jié)果證明，本文所提出的算法可以有效地避免傳統(tǒng)k-means因隨機(jī)選取初始簇而導(dǎo)致了聚類不穩(wěn)定的現(xiàn)象，并且算法在準(zhǔn)確率上有所提高，DBI表明聚類的效果更好。但計(jì)算的時(shí)間有所增加，如何快速有效地獲取一個(gè)最優(yōu)參數(shù)k來使聚類效果和精度能達(dá)到一個(gè)最佳理想的結(jié)果，還有研究近鄰參數(shù)θ的值將會(huì)是下一步的研究工作內(nèi)容。