程旸，王士同

(江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無(wú)錫 214122)

?

基于局部保留投影的多可選聚類(lèi)發(fā)掘算法

程旸，王士同

(江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無(wú)錫 214122)

絕大多數(shù)的聚類(lèi)分析算法僅能得到單一的聚類(lèi)結(jié)果，考慮到數(shù)據(jù)的復(fù)雜程度普遍較高，以及看待數(shù)據(jù)的視角不同，所得到的聚類(lèi)結(jié)果在保證其合理性的基礎(chǔ)上應(yīng)當(dāng)是不唯一的，針對(duì)此問(wèn)題，提出了一個(gè)新的算法RLPP，用于發(fā)掘多種可供選擇的聚類(lèi)結(jié)果。RLPP的目標(biāo)函數(shù)兼顧了聚類(lèi)質(zhì)量和相異性?xún)纱笠?，采用子空間流形學(xué)習(xí)技術(shù)，通過(guò)新的子空間不斷生成多種互不相同的聚類(lèi)結(jié)果。RLPP同時(shí)適用于線性以及非線性的數(shù)據(jù)集。實(shí)驗(yàn)表明，RLPP成功地發(fā)掘了多種可供選擇的聚類(lèi)結(jié)果，其性能相當(dāng)或優(yōu)于現(xiàn)有的算法。

可供選擇的聚類(lèi)結(jié)果；無(wú)監(jiān)督學(xué)習(xí)；流形學(xué)習(xí)；多聚類(lèi)；特征分解

大多數(shù)傳統(tǒng)的聚類(lèi)算法僅僅能得到單個(gè)結(jié)果，但是當(dāng)對(duì)復(fù)雜數(shù)據(jù)進(jìn)行聚類(lèi)分析時(shí)，很可能存在多個(gè)具有合理性的聚類(lèi)結(jié)果。這一特點(diǎn)在高維數(shù)據(jù)上表現(xiàn)得尤為明顯，例如文本、圖像、基因數(shù)據(jù)等，這些數(shù)據(jù)具有多種特征，而不同的特征子空間往往會(huì)得到完全不同的聚類(lèi)結(jié)果，同時(shí)每一種結(jié)果都能體現(xiàn)數(shù)據(jù)不同的結(jié)構(gòu)信息。

本文根據(jù)文獻(xiàn)[1]所述原理，提出了一種能夠發(fā)掘多個(gè)可供選擇的聚類(lèi)結(jié)果的算法RLPP。算法結(jié)合了希爾伯特施密特獨(dú)立性度量準(zhǔn)則(hilbert-schmidt independence criterion，HSIC)[2]以及局部保持投影(locality preserving projections,LPP)[3]，改進(jìn)了LPP算法學(xué)習(xí)子空間的過(guò)程。由于HSIC可以高效地評(píng)估不同隨機(jī)變量之間的依賴(lài)性，而LPP算法具有流形學(xué)習(xí)能力，因此RLPP同時(shí)兼顧了聚類(lèi)結(jié)果的相異性和聚類(lèi)質(zhì)量這兩大要素。并且由于其目標(biāo)函數(shù)最終在特征分解問(wèn)題的框架內(nèi)求解，因此能夠確保求出的新的子空間一定存在，并且解是全局最優(yōu)的。

總的來(lái)說(shuō)，本文所做的工作為：1)提出了一種新的算法RLPP，用于發(fā)掘多種可供選擇的聚類(lèi)結(jié)果；2)RLPP根據(jù)同時(shí)滿(mǎn)足質(zhì)量和相異性要求的目標(biāo)函數(shù)，生成一個(gè)新的特征子空間，該特征子空間能夠確保存在，并且是全局最優(yōu)的；3)通過(guò)實(shí)驗(yàn)，驗(yàn)證了RLPP的效果，并與其他現(xiàn)有的算法進(jìn)行了性能比較。

1 當(dāng)前典型的可選聚類(lèi)發(fā)掘方法

當(dāng)前，有關(guān)發(fā)掘可選聚類(lèi)結(jié)果的算法大體上可以分為兩類(lèi):一類(lèi)直接利用原始數(shù)據(jù)空間尋找，另一類(lèi)則是基于投影(變形)子空間尋找。

1.1 基于全部原始數(shù)據(jù)空間

這類(lèi)研究利用的是整個(gè)原始特征空間，大多數(shù)研究的不同之處在于優(yōu)化聚類(lèi)質(zhì)量和相異性的目標(biāo)函數(shù)不同。文獻(xiàn)[4-9]中的研究可以歸類(lèi)為此類(lèi)。文獻(xiàn)[4]提出了一種分層聚類(lèi)(hierarchical clustering)算法COALA，該算法把從提供的聚類(lèi)結(jié)果中生成的cannot-link約束項(xiàng)合并入它的每一個(gè)凝聚步驟中，即盡可能多地滿(mǎn)足這些cannot-link約束項(xiàng)。在文獻(xiàn)[7]中，提出了CAMI算法，用于同時(shí)尋找兩個(gè)可供選擇的聚類(lèi)結(jié)果。CAMI算法在混合模型下構(gòu)造聚類(lèi)問(wèn)題，優(yōu)化了一個(gè)雙重目標(biāo)函數(shù)(dual-objective function)，使得當(dāng)兩個(gè)混合模型之間的互信息(反映了兩種聚類(lèi)結(jié)果之間的不同)最小時(shí)，對(duì)數(shù)似然(反映了聚類(lèi)質(zhì)量)最大。文獻(xiàn)[6]提出的兩種算法Dec-kmeans和Conv-EM也屬于此類(lèi)，這兩種算法分別改進(jìn)了k-means和EM的目標(biāo)函數(shù)，結(jié)合了一個(gè)修正項(xiàng)，用于表示兩種聚類(lèi)結(jié)果之間的去相關(guān)信息。文獻(xiàn)[8]中的工作采用了不同的方式，其原理來(lái)源于信息論，它的目標(biāo)函數(shù)最大化全部數(shù)據(jù)實(shí)例和可選聚類(lèi)結(jié)果類(lèi)標(biāo)之間的互信息(MI)，同時(shí)最小化可選聚類(lèi)和所提供的聚類(lèi)結(jié)果之間的互信息。文獻(xiàn)[8]中并沒(méi)有基于傳統(tǒng)的香農(nóng)熵[10]，而是采用了Renyi熵，以及相對(duì)應(yīng)的二次互信息[11-12]，這種方法在結(jié)合了非參數(shù)Parzen窗[13]后使得MI基本近似。這種雙重優(yōu)化聚類(lèi)目標(biāo)同樣被用于文獻(xiàn)[9]中，區(qū)別在于文獻(xiàn)[9]使用的是迭代法，而不是文獻(xiàn)[8]中所使用的分層技術(shù)。

1.2 基于投影子空間

如果原數(shù)據(jù)空間的子空間與原數(shù)據(jù)空間是相互獨(dú)立的(比如是正交的)，那么根據(jù)該子空間得到的聚類(lèi)結(jié)果也與原聚類(lèi)結(jié)果不同。文獻(xiàn)[14-18]就是根據(jù)這樣的理論基礎(chǔ)提出了各自的算法。文獻(xiàn)[14]由正交投影方法提出了兩種尋找可供選擇的聚類(lèi)結(jié)果的算法。已知一個(gè)向量b，投影到矩陣的列空間中，可以用P×b計(jì)算，其中P被稱(chēng)為投影矩陣，P=A(ATA)-1AT。而(Ⅰ-P)同樣也是一個(gè)投影矩陣，表示把投影到了AT的零空間中。文獻(xiàn)[14]中提出的2種算法把每個(gè)數(shù)據(jù)實(shí)例看作向量，利用了上述投影等式。文獻(xiàn)[15]中的研究也與此相關(guān)，投影矩陣被應(yīng)用于從所提供的聚類(lèi)結(jié)果導(dǎo)出的距離矩陣上。相比于文獻(xiàn)[14]中的2種算法，這種方法的優(yōu)勢(shì)在于能夠解決數(shù)據(jù)維數(shù)比類(lèi)別數(shù)小的情況。文獻(xiàn)[16]提出的算法采用了不同的方法，通過(guò)對(duì)數(shù)據(jù)的投影，使得在參考聚類(lèi)結(jié)果中屬于相同類(lèi)別的數(shù)據(jù)點(diǎn)經(jīng)過(guò)映射后在新的空間中拉開(kāi)距離。這一方法與其他方法之間的不同之處在于它并不尋找一個(gè)全新的可選聚類(lèi)，而是通過(guò)設(shè)定2個(gè)聚類(lèi)結(jié)果之間的相異度閾值，允許已知的聚類(lèi)結(jié)果中的部分在可選聚類(lèi)結(jié)果中保留下來(lái)。文獻(xiàn)[17]和文獻(xiàn)[18]中所提出的算法基于譜聚類(lèi)實(shí)現(xiàn)，前者表明可選聚類(lèi)結(jié)果可以通過(guò)拉普拉斯矩陣不同的特征向量找到，后者所提出的多重譜聚類(lèi)(multiple spectral clustering, MSC)把子空間學(xué)習(xí)技術(shù)融入了譜聚類(lèi)的過(guò)程中，也就是說(shuō)，MSC的目標(biāo)函數(shù)是一個(gè)對(duì)偶函數(shù)(dual-function)，通過(guò)最優(yōu)化一項(xiàng)來(lái)修正另一項(xiàng)。另外，文獻(xiàn)[1]提出了正則化PCA(regularized PCA, RPCA)和正則化的圖方法(regularized graph-based method, RegGB)算法，其中RPCA與MSC一樣，都采用了HSIC，用于評(píng)估相關(guān)性，而RegGB算法則是基于圖論構(gòu)造?？偟膩?lái)說(shuō)，RPCA和RegGB算法在尋找可選聚類(lèi)的能力上要優(yōu)于之前所提到的算法，但是RPCA算法只適用于線性結(jié)構(gòu)的數(shù)據(jù)集，并且其尋找可選聚類(lèi)結(jié)果的能力有限，往往只能找到一個(gè)可選聚類(lèi)，這些都極大地影響了它在使用上的靈活性。因此，本文在文獻(xiàn)[1]所提出的思路上，探索了一種新的算法，通過(guò)引入流形學(xué)習(xí)大大提高了其發(fā)掘低維流形結(jié)構(gòu)的能力和子空間學(xué)習(xí)能力，并通過(guò)核化擴(kuò)大了其適用范圍，使得其既適用于線性，同時(shí)又適用于非線性的數(shù)據(jù)集。

2 問(wèn)題描述

為了發(fā)掘另一個(gè)可供選擇的聚類(lèi)結(jié)果，使用子空間流形學(xué)習(xí)方法，將原始數(shù)據(jù)空間X映射到一個(gè)新的子空間中。該空間保留了X的特征，并且完全獨(dú)立于其他的參考聚類(lèi)結(jié)果。任何聚類(lèi)算法都可以使用這個(gè)新的子空間進(jìn)行聚類(lèi)分析。

3 局部保持投影

局部保持投影(locality preserving projections，LPP)[3]是一種非監(jiān)督降維方法，是流形學(xué)習(xí)算法Laplacian Eigenmap的線性逼近。給定Rd中的n個(gè)數(shù)據(jù)點(diǎn)x1,x2,…,xn，LPP通過(guò)尋找轉(zhuǎn)換矩陣A，將這n個(gè)數(shù)據(jù)點(diǎn)映射為Rl(l?d)上的數(shù)據(jù)點(diǎn)y1,y2,…,yn，即：

式中所需的轉(zhuǎn)換矩陣A可以通過(guò)最小化式(2)目標(biāo)函數(shù)得到：

式中:Wij是權(quán)值矩陣，可采用k最近鄰算法得到鄰接圖，再求出權(quán)值矩陣。

從目標(biāo)函數(shù)式(2)可以看出，降維后的特征空間可以保持原始高維空間的局部結(jié)構(gòu)。結(jié)合式(1)和式(2)，做簡(jiǎn)單的代數(shù)變換：

(3)

能夠使得式(3)取最小值的變換矩陣A的求解可以轉(zhuǎn)換為如下的廣義特征值問(wèn)題：

此外，LPP不僅適用于原始數(shù)據(jù)空間，還適用于再生核希爾伯特空間(reproducing kernel hilbert space, RKHS)，這樣就可以引出核LPP算法。

考慮如下的核函數(shù)：

4 希爾伯特-施密特獨(dú)立性度量準(zhǔn)則

已知一個(gè)參考聚類(lèi)結(jié)果C(1)，使用RLPP算法學(xué)習(xí)相對(duì)于C(1)獨(dú)立的子空間A，這樣就確保了使用A得到的聚類(lèi)結(jié)果C(2)與C(1)不同。為了計(jì)算不同子空間之間的相異性，采用了HSIC(hilbert-schmidt independence criterion)[1]，更重要的是，LPP與HSIC結(jié)合后可以導(dǎo)出一個(gè)特征分解問(wèn)題，這樣就一定可以計(jì)算出全局最佳解。

HSIC是一種基于核的獨(dú)立性度量方法，采用Hilbert-Schmidt互協(xié)方差算子，通過(guò)對(duì)該算子范數(shù)的經(jīng)驗(yàn)估計(jì)得到獨(dú)立性判斷準(zhǔn)則。具體來(lái)說(shuō)，已知X和Y兩個(gè)隨機(jī)變量，HSIC(X,Y)的值越大說(shuō)明X和Y的關(guān)聯(lián)性越強(qiáng)，值等于0時(shí)說(shuō)明X和Y相互之間完全獨(dú)立。

為了表示簡(jiǎn)單，使用HSIC(X,Y)代替HSIC(Z,F,G)，表示隨機(jī)變量X和φ(x)=ATx，也就是X和Y之間的依賴(lài)性。

5 基于局部保留投影的多可選聚類(lèi)發(fā)掘算法

由于通過(guò)HSIC(X,Y)可以自然地評(píng)估結(jié)構(gòu)很復(fù)雜的樣本X和Y之間的相關(guān)性，因此結(jié)合HSIC(X,Y)對(duì)LPP的目標(biāo)函數(shù)進(jìn)行修改。要求是轉(zhuǎn)換矩陣A必須能夠發(fā)掘嵌入在高維數(shù)據(jù)中的低維流形結(jié)構(gòu)，并且與已知的聚類(lèi)結(jié)果C(1)完全獨(dú)立。換句話(huà)說(shuō)，在所有與已經(jīng)存在的聚類(lèi)結(jié)果C(1)不同的子空間中，要選出能夠最好地保持高維數(shù)據(jù)流形結(jié)構(gòu)的子空間。因此，改進(jìn)LPP的目標(biāo)函數(shù)如下：

(6)

(7)

將數(shù)據(jù)集合X映射到高維特征空間中后，就可以最終得到φ(X)=[φ(x1)φ(x2) …φ(xn)]。其中，核矩陣K的元素為Kij=φ(xi)T·φ(xj)。即：

可以看到，φ(X)HLyHφ(X)T直接影響了LPP算法中φ(X)Lφ(X)T項(xiàng)，也就是說(shuō)，可以把兩個(gè)聚類(lèi)結(jié)果之間的獨(dú)立性看作添加的約束項(xiàng)。同時(shí)，通過(guò)添加更多的HSIC項(xiàng)，將算法推廣可以找到更多可供選擇的聚類(lèi)結(jié)果。

舉例來(lái)說(shuō)，在尋找第3個(gè)可供選擇的聚類(lèi)結(jié)果C(3)時(shí)，只要提供之前找到的兩個(gè)聚類(lèi)結(jié)果C(1)和C(2)，并把式(6)中的HSIC(ATX,C(1))一項(xiàng)替換為HSIC(ATX,C(1))+HSIC(ATX,C(2))即可。因此只要在式(8)中使用ATXHLy1HXTA+ATXHLy2HXTA，即直接使用ATXH(Ly1+Ly2)HXTA代替ATXHLyHXTA。也就是說(shuō)，使用(Ly1+Ly2)代替了Ly，其他矩陣保持不變即可。

RLPP算法描述如下：

1)輸入 數(shù)據(jù)集X;一個(gè)X上的參考聚類(lèi)結(jié)果C(1)。

2)輸出 一個(gè)數(shù)據(jù)集X上可供選擇的參考聚類(lèi)結(jié)果C(2)。

3)算法流程:

①計(jì)算Ly，Ly=〈yi,yj〉，其中yi是一個(gè)二元向量，表示C(1)中xi的類(lèi)標(biāo)簽的編碼。

⑤使用高斯核計(jì)算核矩陣K，Kij=φ(xi)T·φ(xj)。

⑦計(jì)算φ(X)Lφ(X)T+φ(X)HLyHφ(X)T的特征值和特征向量。

⑧按特征值從小到大的順序?qū)μ卣飨蛄颗判颉?/p>

⑨選擇前k個(gè)最小的特征值對(duì)應(yīng)的特征向量，即A=[a0a1…ak-1]。

⑩C(2)=k-means(ATφ(X))。

RLPP算法的時(shí)間復(fù)雜度完全由計(jì)算最近鄰矩陣以及核矩陣決定，因?yàn)樗鼈兊臅r(shí)間復(fù)雜度均為O(n2d)，因此整體的時(shí)間復(fù)雜度也為O(n2d)。

6 實(shí)驗(yàn)與分析

6.1 聚類(lèi)結(jié)果評(píng)估

對(duì)于NMI和JI指標(biāo)，值越小意味著不同聚類(lèi)結(jié)果之間的相似度越高；對(duì)于F-measure和Dunn Index指標(biāo)，值越大意味著更高的聚類(lèi)質(zhì)量。

6.2 人工數(shù)據(jù)集

使用兩種流行的人工數(shù)據(jù)集評(píng)估RLPP的效果，并與其他算法進(jìn)行比較。第1組人工數(shù)據(jù)集Syn1分布在二維空間內(nèi)，分為4部分，每部分由200個(gè)數(shù)據(jù)點(diǎn)組成，共800個(gè)數(shù)據(jù)點(diǎn)。使用數(shù)據(jù)集Syn1的目的是檢驗(yàn)算法是否能夠盡可能多的發(fā)現(xiàn)可供選擇的聚類(lèi)結(jié)果，且所有結(jié)果均滿(mǎn)足與初始聚類(lèi)結(jié)果正交的條件。第2組人工數(shù)據(jù)集Syn2的結(jié)構(gòu)較為復(fù)雜，每部分的形狀都是非凸的。使用數(shù)據(jù)集Syn2的目的是檢驗(yàn)算法是否能夠處理非線性的數(shù)據(jù)結(jié)構(gòu)，并且發(fā)掘出嵌入在高維數(shù)據(jù)中的低維流形結(jié)構(gòu)。

圖1中的第1行表示的是RLPP使用數(shù)據(jù)集Syn1得到的運(yùn)行結(jié)果。其中，第1列表示的是所提供的參考聚類(lèi)結(jié)果C(1)，第2列表示的是由RLPP得到的可供選擇的聚類(lèi)結(jié)果C(2)。從圖中可以直觀地看出，RLPP成功地找到了與所提供的參考聚類(lèi)結(jié)果完全不相同，但是聚類(lèi)質(zhì)量很高的可選聚類(lèi)結(jié)果。另外，如果我們把該結(jié)果C(2)看作除C(1)外新增的參考聚類(lèi)結(jié)果，并且尋找第2個(gè)可選的參考聚類(lèi)結(jié)果C(3)，RLPP會(huì)得到第3列所顯示的聚類(lèi)結(jié)果。C(3)在歐氏距離下與前兩個(gè)聚類(lèi)結(jié)果相比不是特別得自然，但是C(3)仍然很有啟發(fā)性，并且它完全獨(dú)立于前2個(gè)參考聚類(lèi)結(jié)果C(1)和C(2)。同時(shí)注意到，RPCA算法無(wú)法尋找出合適的C(3)。在表1中，提供了這些算法的表現(xiàn)。

圖1 由數(shù)據(jù)集Syn1(第1行)和Syn2(第2行)得到的可選聚類(lèi)結(jié)果

表1 人工數(shù)據(jù)集Syn1上3種算法的表現(xiàn)

表2 人工數(shù)據(jù)集Syn2上3種算法的表現(xiàn)

6.3 舍爾圖數(shù)據(jù)集

選擇文獻(xiàn)[11]中所介紹的埃舍爾圖(escher image)作為另一個(gè)用于尋找多個(gè)可選聚類(lèi)結(jié)果實(shí)驗(yàn)的數(shù)據(jù)集。對(duì)于人眼來(lái)說(shuō)，埃舍爾圖有多種分割結(jié)果(即聚類(lèi)結(jié)果)。圖2(a)顯示的圖片為原始圖片，可以看到圖中有多只爬行動(dòng)物，并且聚類(lèi)時(shí)明顯可以有多種聚類(lèi)結(jié)果。在分割過(guò)程中，圖中的每個(gè)像素點(diǎn)都表示一個(gè)反映了RGB信息的數(shù)據(jù)點(diǎn)。我們使用k-means對(duì)圖2(a)進(jìn)行聚類(lèi)。圖2(b)為k-means得到的聚類(lèi)結(jié)果，作為其他算法所需要的參考聚類(lèi)結(jié)果。圖2(c)和圖2(d)分別為RLPP得到的可選聚類(lèi)結(jié)果C(2)和C(3)，可以看出圖2(c)中的爬行動(dòng)物為水平姿勢(shì)，圖2(d)中的爬行動(dòng)物為垂直姿勢(shì)。為了對(duì)比，提供了由RegGB算法得到的結(jié)果(RPCA算法得到的C(2)與RegGB算法近似，C(3)則效果很差，因此不加入對(duì)比)。圖2(e)和圖2(f)為RegGB得到的可選聚類(lèi)結(jié)果C(2)和C(3)。從肉眼觀察的角度可以發(fā)現(xiàn)，圖2(c)與圖2(e)相比輪廓更加清晰，聚類(lèi)的效果更好。圖2(d)與圖2(f)相比，

雖然圖2(f)的結(jié)果看似更佳，但是圖2(d)保留了原圖中更多的信息，每只爬行動(dòng)物的輪廓都能夠得到保留，這是由于RLPP采用了流形子空間學(xué)習(xí)技術(shù)，能夠最大程度地保留原始數(shù)據(jù)的結(jié)構(gòu)。對(duì)每種算法重復(fù)運(yùn)行了10次，表3給出了這些算法的平均表現(xiàn)。

圖2 埃舍爾圖數(shù)據(jù)集上的圖像分割結(jié)果

表3 埃舍爾圖數(shù)據(jù)集上兩種算法的表現(xiàn)

6.4 CMUFace數(shù)據(jù)集

使用UCI數(shù)據(jù)庫(kù)中的CMUFace數(shù)據(jù)集檢驗(yàn)算法。CMUFace數(shù)據(jù)集包含20個(gè)人的圖像，每個(gè)人又分為不同的面部表情(正常、高興、悲傷、生氣)，不同的頭部朝向(向左、向右、向前、向上)，不同眼部狀況(睜開(kāi)、墨鏡)。每個(gè)人有32張圖片，包含了上述特征的組合。由于圖片中的人的身份是已知的，因此身份信息可以作為參考聚類(lèi)結(jié)果直接使用。隨機(jī)選取了3個(gè)人的全部圖像進(jìn)行試驗(yàn)。

圖3顯示的是聚類(lèi)結(jié)果的平均值的圖像。其中第1行是原始圖像經(jīng)由k-means算法得到的平均值圖像，第2行由RLPP算法得到，第3行和第4行由RPCA與RegGB算法得到。

從圖像上看，第1行聚類(lèi)的依據(jù)是不同的人，其余3行聚類(lèi)的依據(jù)是人不同的頭部朝向。很明顯，3種算法都從數(shù)據(jù)集中得到了另一組完全不同，但是同等重要的聚類(lèi)結(jié)果。從圖中可以看出，RLPP和RPCA的聚類(lèi)效果最好，RegGB稍差。表4是這3種算法的對(duì)比。

表4 CMUFace數(shù)據(jù)集上3種算法的表現(xiàn)

圖3 CMUFace數(shù)據(jù)集上的運(yùn)行結(jié)果

6.5 算法運(yùn)行時(shí)間

實(shí)驗(yàn)均在MARTLAB 8.1.0.604(R2013a)平臺(tái)下完成，操作系統(tǒng)為64位Windows7，CPU為Intel(R) Core(TM) i3-3240 3.40G Hz，內(nèi)存為4 GB。

對(duì)于人工數(shù)據(jù)集Syn1和Syn2，RLPP算法發(fā)掘出一個(gè)可供選擇的聚類(lèi)結(jié)果分別耗時(shí)3.4 s和2.9 s。對(duì)于Esher圖，由于聚類(lèi)之前需要進(jìn)行圖像一維化處理，因此數(shù)據(jù)集的維數(shù)很大，共耗時(shí)136 s。對(duì)于CMUFace數(shù)據(jù)集，RLPP算法找到一個(gè)可供選擇的聚類(lèi)結(jié)果共耗時(shí)2.7 s。以上運(yùn)行時(shí)間均為運(yùn)行10次試驗(yàn)的平均時(shí)間。

上述運(yùn)行時(shí)間表明本文算法在合適的數(shù)據(jù)集上是完全適用的，但是在數(shù)據(jù)集規(guī)模很大的情況下，仍存有改進(jìn)的空間。

7 結(jié)束語(yǔ)

本文提出了一種新的算法RLPP，采用子空間流形學(xué)習(xí)技術(shù)，尋找可供選擇的聚類(lèi)結(jié)果。RLPP算法的優(yōu)勢(shì)在于最終能夠轉(zhuǎn)化為特征分解問(wèn)題，也就是說(shuō)可以找到封閉解，并且子空間一定是全局最優(yōu)的，這也是本文區(qū)別于其他相關(guān)研究的重要特點(diǎn)之一。在文章中對(duì)RLPP算法進(jìn)行了論證和實(shí)驗(yàn)，并對(duì)比了目前效果最好的著名算法。實(shí)驗(yàn)結(jié)果表明RLPP算法的性能不輸于甚至優(yōu)于其他算法。對(duì)于如何更好地選取最小特征值的個(gè)數(shù)k，以及如何降低算法在處理維數(shù)較大數(shù)據(jù)時(shí)的時(shí)間復(fù)雜度，都是繼續(xù)研究的方向。

[1]DANG Xuanhong, BAILEY J. Generating multiple alternative clusterings via globally optimal subspaces[J]. Data mining and knowledge discovery, 2014, 28(3): 569-592.

[2]GRETTON A, BOUSQUET O, SMOLA A, et al. Measuring statistical dependence with Hilbert-Schmidt norms[M]//JAIN S, SIMON H U, TOMITA E. Algorithmic Learning Theory. Berlin Heidelberg: Springer, 2005: 63-77.

[3]HE Xiaofei, NIYOGI X. Locality preserving projections[C]//Advances in Neural Information Processing Systems. Vancouver, Canada, 2003, 16: 153-160.

[4]BAE E, BAILEY J. COALA: a novel approach for the extraction of an alternate clustering of high quality and high dissimilarity[C]//Proceedings of the 6th International Conference on Data Mining. Hong Kong, China, 2006: 53-62.

[5]GONDEK D, HOFMANN T. Non-redundant data clustering[J]. Knowledge and information systems, 2007, 12(1): 1-24.

[6]JAIN P, MEKA R, DHILLON I S. Simultaneous unsupervised learning of disparate clusterings[J]. Statistical analysis and data mining: the ASA data science journal, 2008, 1(3): 195-210.

[7]DANG Xuanhong, BAILEY J. Generation of alternative clusterings using the CAMI approach[C]//Proceedings of the SIAM International Conference on Data Mining, SDM 2010. Columbus, Ohio, USA, 2010, 10: 118-129.

[8]DANG Xuanhong, BAILEY J. A hierarchical information theoretic technique for the discovery of non linear alternative clusterings[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington, DC, USA, 2010: 573-582.

[9]VINH N X, EPPS J. MinCEntropy: a novel information theoretic approach for the generation of alternative clusterings[C]//Proceedings of the IEEE International Conference on Data Mining. Sydney, Australia, 2010: 521-530.

[10]COVER T M, THOMAS J A. Elements of information theory[M]. Chichester: John Wiley & Sons, 2012.

[11] KAPUR J N. Measures of information and their applications[M]. New York: Wiley-Interscience, 1994.

[12]PRINCIPE J C, XU D, FISHER J. Information theoretic learning[M]//HAYKIN S. Unsupervised Adaptive Filtering. New York: Wiley, 2000, 1: 265-319.

[13]PARZEN E. On estimation of a probability density function and mode[J]. The annals of mathematical statistics, 1962, 33(3): 1065-1076.

[14]CUI Ying, FERN X Z, DY J G. Non-redundant multi-view clustering via orthogonalization[C]//Proceedings of the 7th IEEE International Conference on Data Mining. Omaha, Nebraska, USA, 2007: 133-142.

[15]DAVIDSON I, QI Zijie. Finding alternative clusterings using constraints[C]//Proceedings of the 8th IEEE International Conference on Data Mining. Pisa, Italy, 2008: 773-778.

[16]QI Zijie, DAVIDSON I. A principled and flexible framework for finding alternative clusterings[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris, France, 2009: 717-726.

[17]DASGUPTA S, NG V. Mining clustering dimensions[C]//Proceedings of the 27th International Conference on Machine Learning. Haifa, Israel, 2010: 263-270.

[18]NIU Donglin, DY J G, JORDAN M I. Multiple non-redundant spectral clustering views[C]//Proceedings of the 27th International Conference on Machine Learning. Haifa, Israel, 2010: 831-838.

程旸，男，1991年生，碩士研究生，主要研究方向?yàn)槿斯ぶ悄芘c模式識(shí)別、數(shù)據(jù)挖掘。

王士同，男，1964年生，教授，博士生導(dǎo)師，中國(guó)離散數(shù)學(xué)學(xué)會(huì)常務(wù)理事，中國(guó)機(jī)器學(xué)習(xí)學(xué)會(huì)常務(wù)理事。主要研究方向?yàn)槿斯ぶ悄?、模式識(shí)別和圖像處理。發(fā)表學(xué)術(shù)論文近百篇，其中被SCI、EI檢索50余篇。

第2屆物聯(lián)網(wǎng),大數(shù)據(jù)和安全國(guó)際會(huì)議

2nd International Conference on Internet of Things,Big Data and Security

24-26 April, 2017, Porto, Portugal

Internet of Things (IoT) is a platform and a phenomenon that allows everything to process information, communicate data, analyze context collaboratively and in the service or individuals, organizations and businesses. In the process of doing so, a large amount of data with different formats and content has to be processed efficiently, quickly and intelligently through advanced algorithms, techniques, models and tools. This new paradigm is enabled by the maturity of several different technologies, including the internet, wireless communication, cloud computing, sensors, big data analytics and machine learning algorithms.

Big Data is another paradigm to describe processing of data to make it ‘make sense’ to people using IoT. Big Data has five characteristics: volume, velocity, variety, veracity and value. There are reports that businesses and research communities equipped with Big Data skills can provide additional incentives, opportunities, funding and innovation to their long-term strategies. The new knowledge, tools, practices, and infrastructures produced will enable breakthrough discoveries and innovation in physical science, engineering, mobile services, medicine, business, education, earth science, security and risk analysis. For organizations that adopt Big Data, the boundary between the use of private clouds, public clouds, IoT is sometimes very thin to allow better access, performance and efficiency of analyzing the data and understanding the data analysis. A common approach is to develop Big Data in the IoT to deliver “Everything as a Service”. In the process of doing so, innovative services known as “Emerging Services and Analytics” can be the highlight and strategic solutions to organizations adopting IoT and Big Data.

Website: http://www.iotbd.org/?y=2017

A multiple alternative clusterings mining algorithm using locality preserving projections

CHENG Yang, WANG Shitong

(School of Digit Media, Jiangnan University, Wuxi 214122, China)

Most clustering algorithms typically find just one single result for the data inputted. Considering that the complexity of the data is generally high, combined with the need to allow the data to be viewed from different perspectives (on the basis of ensuring reasonableness), means that clustering results are often not unique. We present a new algorithm RLPP for an alternative clustering generation method. The objective of RLPP is to find a balance between clustering quality and dissimilarity using a subspace manifold learning technique in a new subspace so that a variety of clustering results can be generated. Experimental results using both linear and nonlinear datasets show that RLPP successfully provides a variety of alternative clustering results, and is able to outperform or at least match a range of existing methods.

alternative clustering; unsupervised learning; manifold learning; multiple clusterings; eigendecomposition

2015-08-26.

日期：2016-08-24.

國(guó)家自然科學(xué)基金項(xiàng)目(61272210).

程旸. E-mail：szhchengyang@163.com.

TP18

A

1673-4785(2016)05-0600-08

10.11992/tis.201508022

http://www.cnki.net/kcms/detail/23.1538.TP.20160824.0928.004.html

程旸，王士同.基于局部保留投影的多可選聚類(lèi)發(fā)掘算法[J]. 智能系統(tǒng)學(xué)報(bào)， 2016, 11(5): 600-607.

英文引用格式：CHENG Yang, WANG Shitong. A multiple alternative clusterings mining algorithm using locality preserving projections[J]. CAAI transactions on intelligent systems, 2016,11(5): 600-607.