一種基于隨機(jī)游走的軟子空間聚類集成方法

李 嫚,王立宏

(煙臺(tái)大學(xué)計(jì)算機(jī)與控制工程學(xué)院,山東 煙臺(tái) 264005)

數(shù)據(jù)聚類是一種經(jīng)典的無(wú)監(jiān)督學(xué)習(xí)技術(shù),它在機(jī)器學(xué)習(xí)及數(shù)據(jù)挖掘等領(lǐng)域得到了廣泛應(yīng)用。聚類旨在通過(guò)某種相似度計(jì)算方法將數(shù)據(jù)集劃分為多個(gè)不同的簇,使同一簇內(nèi)的數(shù)據(jù)對(duì)象之間具有較高的相似度,不同簇內(nèi)的數(shù)據(jù)對(duì)象之間相似度較小。在過(guò)去的幾十年中,已經(jīng)提出了許多成功的聚類方法,但是沒(méi)有一種聚類算法可以解決所有不同形狀、密度或者包含噪聲的簇的聚類問(wèn)題。研究人員發(fā)現(xiàn),集成學(xué)習(xí)將多個(gè)學(xué)習(xí)器的結(jié)果進(jìn)行組合,可以獲得比單個(gè)學(xué)習(xí)器更好的效果,因此將集成的思想引入到數(shù)據(jù)聚類中。2002年,STREHL和GHOSH[1]正式提出聚類集成的概念,通過(guò)組合多個(gè)不同的基聚類結(jié)果得到一個(gè)性能更佳、魯棒性更強(qiáng)的聚類結(jié)果。

聚類集成已經(jīng)成為機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)之一。學(xué)者們將博弈論[2-4]、粒度計(jì)算[5-6]、隨機(jī)游走[7-12]等思想與聚類相結(jié)合,開(kāi)創(chuàng)新的聚類集成算法。FELDMAN等[3]引入了hedonic games(享樂(lè)博弈)思想處理聚類問(wèn)題,SANDES等[4]在其基礎(chǔ)上,對(duì)博弈理論進(jìn)行了更深入的分析,并應(yīng)用于聚類集成中,提出了基于享樂(lè)博弈的聚類集成算法HGCE(Hedonic Game based Clustering Ensemble)。XU等[6]從粒度計(jì)算的角度出發(fā),引入粒度距離度量基聚類成員之間的相似性,提出基于粒度計(jì)算的聚類集成算法CEGC(Clustering Ensemble based on Granular Computing)。2006年,PONS等[7]提出了一種基于隨機(jī)游走的節(jié)點(diǎn)相似性度量方法Walktrap,通過(guò)隨機(jī)游走軌跡量化網(wǎng)絡(luò)節(jié)點(diǎn)之間的結(jié)構(gòu)相似性,進(jìn)而有效計(jì)算網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。2012年,金弟等[8]根據(jù)馬爾可夫隨機(jī)游走思想,結(jié)合網(wǎng)絡(luò)聚類,提出一種新的網(wǎng)絡(luò)聚類算法——基于隨機(jī)游走的蟻群算法,并通過(guò)實(shí)驗(yàn)證實(shí)該算法能夠準(zhǔn)確得到網(wǎng)絡(luò)的真實(shí)聚類簇?cái)?shù)且具有較高的聚類精度。2013年,FU等[9]提出了CD-Trandwalk算法,與采用隨機(jī)游走計(jì)算節(jié)點(diǎn)相似度的算法不同的是,該算法首先選擇活動(dòng)節(jié)點(diǎn)作為種子節(jié)點(diǎn),通過(guò)設(shè)定隨機(jī)游走者的閾值來(lái)檢測(cè)核心社區(qū),剩余的非核心節(jié)點(diǎn)根據(jù)策略分配到核心社區(qū)中。 2016年,HUANG等[10]以微簇(各基分區(qū)基簇的交集)為對(duì)象,提出了精英鄰居選擇策略,通過(guò)局部自適應(yīng)閾值識(shí)別不可靠的鏈接,構(gòu)造K-ENG(K-Elite Neighbor Graph)圖。在K-ENG圖上進(jìn)行隨機(jī)游走,將隨機(jī)游走的概率軌跡作為相似性矩陣,進(jìn)而采用層次聚類算法得到聚類結(jié)果。

本文提出了以hedonic games生成的簇為對(duì)象,簇間社會(huì)福利值為邊權(quán)值構(gòu)造博弈簇相似圖,在博弈簇相似圖上隨機(jī)游走的聚類集成算法CERW。在生成基聚類成員時(shí),采用了熵正則化軟子空間聚類算法ERKM(Entropy Regularization K-Means),利用熵系數(shù)的不確定性生成多樣化的基聚類成員,然后采用基于hedonic games的算法HGCE得到博弈簇,最后采用基于隨機(jī)游走的聚類集成算法CERW得到共識(shí)劃分結(jié)果。在實(shí)驗(yàn)部分,本文提出的算法與基于單個(gè)節(jié)點(diǎn)、微簇節(jié)點(diǎn)、以及基簇節(jié)點(diǎn)隨機(jī)游走的算法在20個(gè)數(shù)據(jù)集上進(jìn)行了性能對(duì)比。

1 知識(shí)準(zhǔn)備

1.1 熵正則化的軟子空間聚類

為了解決傳統(tǒng)聚類算法在處理高維數(shù)據(jù)時(shí)容易受到“維度災(zāi)難”的影響問(wèn)題,提出了子空間聚類算法。子空間聚類可以分為硬子空間聚類和軟子空間聚類,本文關(guān)注一類基于熵正則化的軟子空間聚類算法[13-15],以ERKM算法為例。

2019年,XIONG等[15]提出了ERKM算法,該算法旨在最小化簇內(nèi)數(shù)據(jù)點(diǎn)與簇中心點(diǎn)之間的加權(quán)距離和的同時(shí)最大化不同簇間數(shù)據(jù)點(diǎn)的加權(quán)距離和,且所有的子空間都共用一個(gè)特征加權(quán)向量,其目標(biāo)函數(shù)如下:

F(U,W,V)=

(1)

假設(shè)數(shù)據(jù)集X={xij}N×D表示數(shù)據(jù)集具有N個(gè)數(shù)據(jù)對(duì)象,D個(gè)屬性值。U={uki}K×N為隸屬度矩陣,V={vkj}K×D表示K個(gè)簇中心的向量矩陣。目標(biāo)函數(shù)的第一項(xiàng)表示加權(quán)的簇內(nèi)距離和;第二項(xiàng)為熵正則化項(xiàng),參數(shù)γ>0控制每個(gè)維中權(quán)值的分布;第三項(xiàng)表示加權(quán)的簇間距離和,η>0是一個(gè)控制簇內(nèi)距離和簇間距離的平衡參數(shù)。

熵正則化項(xiàng)中含有的參數(shù)γ取值范圍廣,且對(duì)于不同的數(shù)據(jù)集,在算法運(yùn)行前難以確定系數(shù)的具體取值。此處采用ERKM算法生成基聚類主要是利用系數(shù)的波動(dòng)以生成多樣性的基聚類成員參與集成,期望得到更好的聚類結(jié)果。

1.2 聚類集成

一般而言,聚類集成包括兩個(gè)關(guān)鍵步驟:一是生成基聚類成員,二是設(shè)計(jì)組合函數(shù)。在生成基聚類成員時(shí),一般采用兩種方法:(1)采用同一個(gè)聚類算法,通過(guò)設(shè)置不同的參數(shù)或初始值來(lái)獲得多樣性的基聚類集合。由于K-means算法實(shí)現(xiàn)簡(jiǎn)單且對(duì)初始值敏感,常被用來(lái)作為基分區(qū)生成器[4,16]。(2)采用不同的聚類算法[17],便于從多個(gè)角度了解數(shù)據(jù)集的結(jié)構(gòu)。通過(guò)這兩種方法就可以得到泛化能力強(qiáng)且具有一定差異性的基聚類成員。

得到基聚類成員后,對(duì)于基聚類的表示也有不同的方式,目前常用的基聚類表示方式主要分為三種:聯(lián)合矩陣[18]、二元矩陣[16]、超圖[1]。通常,聯(lián)合矩陣用來(lái)衡量?jī)蓚€(gè)數(shù)據(jù)對(duì)象之間的相似度,二元矩陣用來(lái)衡量一個(gè)數(shù)據(jù)對(duì)象對(duì)一個(gè)聚類的簇隸屬度,超圖用來(lái)衡量數(shù)據(jù)對(duì)象關(guān)于簇的隸屬度。

共識(shí)函數(shù)實(shí)質(zhì)上是一種方法,它將聚類成員進(jìn)行合并(或稱為集成),得到一個(gè)統(tǒng)一的聚類結(jié)果。目前已經(jīng)提出了許多聚類集成設(shè)計(jì)方法,概括分為基于關(guān)聯(lián)矩陣CA(Co-Association)的方法、投票方法、信息論方法、圖方法以及混合模型方法等[19]。

1.3 Hedonic games

在合作博弈中,數(shù)據(jù)對(duì)象被視為參與者,簇集被視為聯(lián)盟,則基劃分CS={Ck|k=1,2,…,K}為一個(gè)聯(lián)盟結(jié)構(gòu)。假設(shè)vi表示參與者xi的偏好函數(shù),vij表示參與者xi對(duì)參與者xj的效用值,則vij=vi(j)=vj(i)=vji。參與者xi對(duì)聯(lián)盟Ck的偏好可表示為vi(Ck)=∑j∈Ckvij。

給定聯(lián)盟結(jié)構(gòu)CS,聯(lián)盟的效益為聯(lián)盟結(jié)構(gòu)內(nèi)所有參與者效用值的總和,即

(2)

如果參與者xi離開(kāi)當(dāng)前的聯(lián)盟CSi到另一個(gè)聯(lián)盟Ck,則新的聯(lián)盟結(jié)構(gòu)CS′關(guān)于CS的社會(huì)福利差異為

v(CS′)-v(CS)=vi(Ck)-vi(CSi),

(3)

如果vi(Ck)>vi(CSi),則聯(lián)盟結(jié)構(gòu)CS′相比于CS會(huì)得到一個(gè)更高的社會(huì)福利值。因此,若當(dāng)前聯(lián)盟結(jié)構(gòu)內(nèi)的所有參與者的偏好值達(dá)到最大,且不再向其他聯(lián)盟移動(dòng)時(shí),hedonic games 達(dá)到納什均衡,即當(dāng)前的聯(lián)盟結(jié)構(gòu)對(duì)于聯(lián)盟內(nèi)的所有參與者而言是納什穩(wěn)定的。

SANDES等[4]通過(guò)定義參與者xi對(duì)聯(lián)盟Ck的偏好,提出了基于享樂(lè)博弈的聚類算法HGCE。偏好函數(shù)定義如下:

(4)

(5)

2 基于隨機(jī)游走的聚類集成

在社區(qū)發(fā)現(xiàn)中,各節(jié)點(diǎn)隨機(jī)訪問(wèn)下一個(gè)節(jié)點(diǎn),當(dāng)一個(gè)節(jié)點(diǎn)重復(fù)訪問(wèn)同一個(gè)節(jié)點(diǎn)的次數(shù)足夠大時(shí),則該節(jié)點(diǎn)被訪問(wèn)的頻率逐漸趨于穩(wěn)定。用頻率代替概率,便可以得到每個(gè)節(jié)點(diǎn)被訪問(wèn)的概率。在數(shù)據(jù)聚類中,根據(jù)不同節(jié)點(diǎn)的概率軌跡,可以探索數(shù)據(jù)集的全局結(jié)構(gòu)信息,發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)之間的潛在關(guān)聯(lián)。

2016年,HUANG等[10]提出了基于微簇節(jié)點(diǎn)隨機(jī)游走的方法,該方法通過(guò)隨機(jī)游走的概率軌跡衡量微簇節(jié)點(diǎn)之間的相似性。

2021年,HUANG等[11]又以基簇為對(duì)象,以Jaccard系數(shù)為邊權(quán)值構(gòu)造基簇相似度圖,在相似度圖的基礎(chǔ)上進(jìn)行隨機(jī)游走,得到基簇間的轉(zhuǎn)移概率矩陣作為新的相似度矩陣,然后映射到數(shù)據(jù)對(duì)象層ECA(Enhanced Co-Association)矩陣中進(jìn)行聚類。

受此啟發(fā),我們以hedonic games算法生成的簇為對(duì)象,簇之間的社會(huì)福利值為邊加權(quán)構(gòu)造初始相似圖,定義如下:

G=(V′,L),

(6)

V′是通過(guò)hedonic games算法生成的簇節(jié)點(diǎn)集,其基數(shù)為N′,L為圖的邊集,定義簇節(jié)點(diǎn)之間的邊權(quán)值為簇之間的參與者效用值的和,計(jì)算公式為

wij=v(Ci)+v(Cj),

(7)

由于Ci和Cj同為簇節(jié)點(diǎn),即一個(gè)聯(lián)盟,則v(Ci)、v(Cj)的計(jì)算同公式(2)。

得到初始相似圖后,為了發(fā)現(xiàn)圖中的簇結(jié)構(gòu)信息,采用隨機(jī)游走技術(shù),通過(guò)分析不同節(jié)點(diǎn)的隨機(jī)游走概率軌跡來(lái)探索圖節(jié)點(diǎn)之間的潛在關(guān)系。在構(gòu)造初始相似圖時(shí),不同算法對(duì)圖節(jié)點(diǎn)的定義是有區(qū)別的。假設(shè)參與集成聚類的三種基聚類如圖1所示,不同算法基于圖1基聚類得到的隨機(jī)游走節(jié)點(diǎn)間的主要差異如圖2所示。

圖1 基聚類

圖2 不同算法隨機(jī)游走節(jié)點(diǎn)對(duì)比

觀察圖2可以發(fā)現(xiàn),不同算法參與隨機(jī)游走的節(jié)點(diǎn)不同。圖2(a)是文獻(xiàn)[10]的節(jié)點(diǎn)示意圖,它以微簇為圖節(jié)點(diǎn),微簇在基聚類中聚類在同一簇時(shí)的次數(shù)累積為邊加權(quán)構(gòu)造簇關(guān)聯(lián)矩陣,以此構(gòu)成相似度圖。根據(jù)定義,在所有的基聚類中,均聚類在同一簇中的數(shù)據(jù)點(diǎn)定義為一個(gè)微簇。圖2(b)是文獻(xiàn)[11]的節(jié)點(diǎn)示意圖,以基簇為圖節(jié)點(diǎn),以Jaccard系數(shù)為邊加權(quán)構(gòu)造基簇相似度圖。圖2(c)是一般的單點(diǎn)游走算法,其中每個(gè)數(shù)據(jù)點(diǎn)都是一個(gè)圖節(jié)點(diǎn),相似性定義采用CA矩陣,即數(shù)據(jù)點(diǎn)在基聚類中成對(duì)出現(xiàn)的頻率。圖2(d)是本文的CERW算法,其中的節(jié)點(diǎn)是通過(guò)hedonic games算法生成的博弈簇,相似性定義為簇間社會(huì)福利值。

根據(jù)HUANG的觀點(diǎn)[10],在鏈接加權(quán)圖中,一個(gè)節(jié)點(diǎn)到鄰居節(jié)點(diǎn)的轉(zhuǎn)移概率通常與鏈接權(quán)值成正比。由于隨機(jī)游走節(jié)點(diǎn)為簇節(jié)點(diǎn),簇內(nèi)的數(shù)據(jù)對(duì)象存在隱含信息,轉(zhuǎn)移概率考慮到簇的大小,定義節(jié)點(diǎn)Ci到節(jié)點(diǎn)Cj的轉(zhuǎn)移概率Pij如下:

(8)

Pij表示一步轉(zhuǎn)移概率矩陣P的第(i,j)項(xiàng),其中nj表示簇Cj中的數(shù)據(jù)對(duì)象數(shù)。則S步隨機(jī)游走的轉(zhuǎn)移概率矩陣定義為

(9)

(10)

根據(jù)上式,得到簇節(jié)點(diǎn)之間基于概率軌跡的相似性度量準(zhǔn)則。節(jié)點(diǎn)Ci和Cj之間基于概率軌跡的相似度定義為

Sim(Ci,Cj)=

(11)

此處采用余弦相似度定義了節(jié)點(diǎn)之間基于隨機(jī)游走概率軌跡的相似性,<-,->表示向量的點(diǎn)積,由此可以得到新的簇級(jí)相似度,以新的簇級(jí)相似度矩陣為輸入,采用常用的聚類算法如層次聚類等進(jìn)行聚類集成得到最終集成結(jié)果。

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

3.1 數(shù)據(jù)集和評(píng)價(jià)指標(biāo)

在本節(jié),采用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的Iris等16個(gè)數(shù)據(jù)集和4個(gè)合成數(shù)據(jù)集對(duì)CERW算法的性能進(jìn)行測(cè)試,各數(shù)據(jù)集的詳細(xì)信息如表1所示。此外,采用聚類準(zhǔn)確率ACC[21](Accuracy)、歸一化互信息NMI[22](Normalized Mutual Information)和調(diào)整蘭德系數(shù)ARI[23](Adjusted Rand Index)三個(gè)聚類評(píng)價(jià)指標(biāo)對(duì)共識(shí)聚類的質(zhì)量進(jìn)行了評(píng)估。ACC與NMI的取值范圍為[0,1],ARI的取值范圍為[-1,1],三者的數(shù)值越高,表明共識(shí)聚類結(jié)果越準(zhǔn)確。

表1 實(shí)驗(yàn)數(shù)據(jù)集描述

3.2 實(shí)驗(yàn)方案

本節(jié)選擇的對(duì)比算法有三種:以微簇為對(duì)象,構(gòu)造微簇-微簇相似度圖進(jìn)行精英選擇及隨機(jī)游走的PTA[10]算法;以基簇為對(duì)象,構(gòu)造基簇-基簇相似度圖進(jìn)行隨機(jī)游走的ECPCS-HC[11]算法;以博弈簇為對(duì)象,構(gòu)造博弈簇-博弈簇相似度圖進(jìn)行隨機(jī)游走的本文CERW算法。通過(guò)對(duì)比,可以觀察以不同節(jié)點(diǎn)開(kāi)始游走的隨機(jī)游走軌跡,挖掘不同簇之間的關(guān)聯(lián)信息。

以上三種算法都是基于簇節(jié)點(diǎn)的隨機(jī)游走,我們測(cè)試了基于數(shù)據(jù)點(diǎn)的隨機(jī)游走實(shí)驗(yàn),記作EAC算法,各算法隨機(jī)游走節(jié)點(diǎn)的區(qū)別如圖2所示。上述算法分別從數(shù)據(jù)點(diǎn)、簇的層次參與聚類集成,另一個(gè)對(duì)比算法WEAC[24]算法則以基聚類為對(duì)象,依據(jù)提出的NCAI指標(biāo)評(píng)估基聚類的質(zhì)量,進(jìn)而根據(jù)聚類有效性對(duì)基聚類進(jìn)行加權(quán)。

對(duì)于每個(gè)數(shù)據(jù)集,所有的算法均運(yùn)行30次,并記錄30次運(yùn)行結(jié)果的平均值。表2—4顯示了所有算法的ACC、NMI和ARI的平均值。每個(gè)數(shù)據(jù)集采用不同算法得到的最優(yōu)值以粗體顯示,次優(yōu)值以斜體顯示。W/T/L (Wins/Ties/Losses)記錄算法達(dá)到最優(yōu)值/等于最優(yōu)值/非最優(yōu)值的次數(shù)。

3.3 實(shí)驗(yàn)結(jié)果及分析

在聚類集成時(shí),所有算法均采用聚合層次聚類,包括單連接、全連接和組平均三種方式,每次實(shí)驗(yàn)保留所有方法中的最大值。記錄了聚類集成在數(shù)據(jù)集得到真實(shí)簇?cái)?shù)時(shí)的各項(xiàng)指標(biāo)值,分別如表2—4所示。此外,還記錄了各種算法關(guān)于不同指標(biāo)的得分情況,計(jì)算得出平均秩(Avg. Rank)。Avg.Rank值表明了算法優(yōu)越性的排序情況,Avg.Rank值越低越好,平均排名最低的算法是性能最佳的算法。

表2 不同集成聚類算法得到的平均ACC值

表2(續(xù))

表3 不同集成聚類算法得到的平均NMI值

表4 不同集成聚類算法得到的平均ARI值

觀察表2可知,參與實(shí)驗(yàn)的數(shù)據(jù)集共20個(gè),我們提出的CERW算法有10個(gè)數(shù)據(jù)集取得最優(yōu)ACC值,其余取得最佳值的數(shù)據(jù)集離散分布在其他算法上。且CERW算法取得最低的Avg.Rank值(2.275),表現(xiàn)更優(yōu)越。

表3是不同集成聚類方法的平均NMI值,CERW算法取得最優(yōu)值的數(shù)據(jù)集個(gè)數(shù)是13。表4給出了不同集成聚類方法的平均ARI值,CERW算法關(guān)于取得最優(yōu)值的數(shù)據(jù)集個(gè)數(shù)為11,其余算法取得最優(yōu)值的數(shù)據(jù)集個(gè)數(shù)比較均勻,且CERW算法在NMI和ARI上都有最低的Avg.Rank值(1.825,1.925)。綜上所述,在聚類結(jié)果得到數(shù)據(jù)集的真實(shí)簇?cái)?shù)時(shí),與其他對(duì)比算法相比,我們提出的CERW算法能夠表現(xiàn)出更好的性能。

4 結(jié) 論

軟子空間聚類算法是傳統(tǒng)特征加權(quán)方法的擴(kuò)展,能權(quán)衡各維度對(duì)簇的重要性,更精確描述各簇所在的子空間,因而越來(lái)越得到重視。隨機(jī)游走已經(jīng)被證明是發(fā)現(xiàn)簇結(jié)構(gòu)的有力工具,本文提出的CERW算法以軟子空間聚類算法ERKM的結(jié)果為基簇,通過(guò)享樂(lè)博弈得到的簇為節(jié)點(diǎn),簇之間的社會(huì)福利值為邊加權(quán)構(gòu)造相似圖,通過(guò)隨機(jī)游走軌跡發(fā)現(xiàn)簇之間的結(jié)構(gòu)關(guān)系。并與以基簇、微簇、數(shù)據(jù)點(diǎn)隨機(jī)游走的算法進(jìn)行了對(duì)比實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明了CERW算法在聚類集成時(shí)的表現(xiàn)更為優(yōu)越。