基于樣本相似度的三支聚類算法

李劉萬(wàn), 朱 金, 王平心

(江蘇科技大學(xué)a. 計(jì)算機(jī)學(xué)院; b. 理學(xué)院, 江蘇 鎮(zhèn)江 212003)

聚類是數(shù)據(jù)挖掘算法中常用的方法,它可以有效發(fā)現(xiàn)事物之間的內(nèi)在聯(lián)系,將隱含在數(shù)據(jù)集內(nèi)部的結(jié)構(gòu)特征描述出來(lái)．聚類的目的就是將給定數(shù)據(jù)集劃分成不同的類簇,使相同簇中的樣本相似度較高, 不同簇中的樣本相似度較低．多年來(lái),聚類已在目標(biāo)檢索[1]、數(shù)據(jù)挖掘[2]、生物醫(yī)學(xué)[3]等研究領(lǐng)域得到廣泛應(yīng)用．聚類集成的基本思想是用多個(gè)獨(dú)立的基聚類器分別對(duì)原始數(shù)據(jù)集進(jìn)行聚類, 然后設(shè)計(jì)有效的一致性函數(shù)對(duì)基聚類成員進(jìn)行集成, 最后得到統(tǒng)一的數(shù)據(jù)劃分．與單一的聚類算法相比, 聚類集成算法具有更高的魯棒性、穩(wěn)定性和聚類質(zhì)量．聚類集成技術(shù)已被有效地用于處理許多聚類任務(wù), 如分類數(shù)據(jù)[4]、高維數(shù)據(jù)[5]、噪聲數(shù)據(jù)[6]、時(shí)間數(shù)據(jù)[7]、特征選擇[8]等．

傳統(tǒng)聚類算法屬于硬聚類, 即二支聚類, 該種聚類要求類簇之間邊界清晰,但在實(shí)際聚類過程中常常遇到信息不充分的情況, 如果將數(shù)據(jù)對(duì)象強(qiáng)行劃分到某一類簇, 會(huì)增加誤分類的概率,導(dǎo)致聚類精度降低．針對(duì)傳統(tǒng)聚類方法的不足,許多軟聚類方法應(yīng)運(yùn)而生．三支決策理論的核心思想是將研究對(duì)象分為正域、負(fù)域、邊界域,分別對(duì)應(yīng)接受、拒絕以及不承諾三種決策規(guī)則．Yu等[9]將三支決策的理論應(yīng)用到聚類中, 提出了三支聚類理論．基于這一理論, Wang等[10]將數(shù)學(xué)形態(tài)的侵蝕和膨脹思想引入聚類中, 提出了CE3框架．與二支聚類算法相比, 三支聚類引入了邊界區(qū)域的概念, 可有效解決傳統(tǒng)二支聚類算法中因信息不完整或數(shù)據(jù)不足導(dǎo)致的分區(qū)不準(zhǔn)確問題．

聚類結(jié)果主要受聚類數(shù)量和閾值的影響．在現(xiàn)有的工作中,人們通常根據(jù)專家選擇合適的類簇?cái)?shù)目, 并在聚類的迭代過程中為所有數(shù)據(jù)選擇相同的閾值．然而這種固定閾值和類簇?cái)?shù)量的選擇并不能很好地表明類簇與數(shù)據(jù)集之間的差異, 尤其是對(duì)于不同大小和密度的數(shù)據(jù)集．本文將三支聚類的思想和聚類集成思想相結(jié)合, 提出一種基于樣本相似度的三支聚類算法．該算法首先通過隨機(jī)選擇樣本部分特征的方法生成一組基聚類成員,以此構(gòu)造樣本相似度．然后利用樣本相似度定義劃分有效性指標(biāo), 用以自動(dòng)計(jì)算最優(yōu)閾值．最后, 使用投票法對(duì)基聚類成員集成得到初步的聚類結(jié)果, 再利用最優(yōu)閾值對(duì)其進(jìn)行劃分, 得到最終的核心域集合和邊界域集合．

1 基于樣本相似度的三支聚類方法

1.1 閾值的自適應(yīng)選擇

在三支聚類問題中,傾向于得到一個(gè)分類誤差較低的分區(qū), 并將不確定性樣本放在邊界域以延遲決策,因此在增加邊界域的同時(shí)也增加了粗糙度,可通過最小化粗糙度限制邊界域．無(wú)論邊界域最大化還是粗糙度最小化,劃分有效性指標(biāo)值均趨于0, 故選擇最大PVI的值作為粗糙度和邊界域取值的平衡點(diǎn), 以達(dá)到更好的聚類效果．其最大PVI(X)由最優(yōu)閾值α決定．

為獲得α最優(yōu)值, 設(shè)置適當(dāng)步長(zhǎng)遍歷所有候選閾值．在該算法中, 首先計(jì)算樣本相似度．步長(zhǎng)為0.01的樣本相似度最小值Smin和最大值Smax構(gòu)成候選閾值空間．對(duì)于每個(gè)候選閾值, 計(jì)算目標(biāo)子集X對(duì)應(yīng)的核心域和邊界域,得到當(dāng)前的劃分有效性指標(biāo)．最后, 輸出當(dāng)前達(dá)到最大PVI值的閾值作為最優(yōu)閾值．圖1為閾值的自適應(yīng)選擇方法的流程圖．

圖1 閾值的自適應(yīng)選擇方法的流程圖Fig.1 The flowchart of an adaptive selection method for thresholds

1.2 基于樣本相似度的三支聚類

聚類集成首先要獲得一組基聚類結(jié)果, 現(xiàn)有的聚類集成方法常使用不同的聚類算法生成不同的基聚類結(jié)果, 而本文算法使用樣本的部分特征獲得基聚類結(jié)果．對(duì)于一個(gè)具有m個(gè)特征的數(shù)據(jù)集, 隨機(jī)抽取部分特征, 使用傳統(tǒng)的聚類算法得到聚類結(jié)果．不同的特征會(huì)導(dǎo)致不同的聚類結(jié)果．重復(fù)上述過程L次, 得到基聚類成員C′1,C′2,…,C′L．

圖2 基于樣本相似度的三支聚類方法的流程圖Fig.2 The flowchart of three-way clustering selection method based on sample similarity

2 聚類性能評(píng)價(jià)指標(biāo)

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

為測(cè)試基于樣本相似度的三支聚類算法的有效性, 本文選取8組常見的UCI(University of California Irvine)標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集, 使用核心域的結(jié)果計(jì)算ACC、NMI和ARI的值, 并與k-means算法、FCM算法和一種基于k-means的自動(dòng)三支聚類算法TWC[14]進(jìn)行比較．每組數(shù)據(jù)集進(jìn)行50次聚類集成,每次聚類時(shí)隨機(jī)提取特征的百分比設(shè)置為70%,實(shí)驗(yàn)結(jié)果如表1所示．由表1可知,與其他3種算法相比,本文算法的ACC、NMI和ARI值具有明顯的優(yōu)勢(shì)．說(shuō)明本文算法能有效提高聚類精度,更好地顯示聚類結(jié)果．

表1 UCI數(shù)據(jù)集上的結(jié)果