基于距離度量學(xué)習(xí)的集成譜聚類(lèi)

牛 科,張小琴,賈郭軍

(山西師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,山西臨汾041004)

基于距離度量學(xué)習(xí)的集成譜聚類(lèi)

牛 科,張小琴,賈郭軍

(山西師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,山西臨汾041004)

無(wú)監(jiān)督學(xué)習(xí)聚類(lèi)算法的性能依賴(lài)于用戶(hù)在輸入數(shù)據(jù)集上指定的距離度量,該距離度量直接影響數(shù)據(jù)樣本之間的相似性計(jì)算,因此,不同的距離度量往往對(duì)數(shù)據(jù)集的聚類(lèi)結(jié)果具有重要的影響。針對(duì)譜聚類(lèi)算法中距離度量的選取問(wèn)題,提出一種基于邊信息距離度量學(xué)習(xí)的譜聚類(lèi)算法。該算法利用數(shù)據(jù)集本身蘊(yùn)涵的邊信息,即在數(shù)據(jù)集中抽樣產(chǎn)生的若干數(shù)據(jù)樣本之間是否具有相似性的信息,進(jìn)行距離度量學(xué)習(xí),將學(xué)習(xí)所得的距離度量準(zhǔn)則應(yīng)用于譜聚類(lèi)算法的相似度計(jì)算函數(shù),并據(jù)此構(gòu)造相似度矩陣。通過(guò)在UCI標(biāo)準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)進(jìn)行分析,結(jié)果表明,與標(biāo)準(zhǔn)譜聚類(lèi)算法相比,該算法的預(yù)測(cè)精度得到明顯提高。

數(shù)據(jù)挖掘;邊信息;相似度矩陣;距離度量學(xué)習(xí);譜聚類(lèi);UCI數(shù)據(jù)集

1 概述

聚類(lèi)是數(shù)據(jù)挖掘技術(shù)的一種重要手段,旨在將集合中的數(shù)據(jù)對(duì)象分組成不同的類(lèi)別,使不同的類(lèi)別之間呈現(xiàn)出高內(nèi)聚低耦合的特點(diǎn)。

事實(shí)上,聚類(lèi)是一種無(wú)監(jiān)督分類(lèi),它沒(méi)有任何先驗(yàn)知識(shí)可用[1],因此,數(shù)據(jù)對(duì)象之間的距離度量對(duì)聚類(lèi)算法的表現(xiàn)性能具有重要影響。合理的距離度量能夠準(zhǔn)確地反映出數(shù)據(jù)集中數(shù)據(jù)對(duì)象之間的相互關(guān)系,從而提升聚類(lèi)算法的表現(xiàn)性能,使聚類(lèi)結(jié)果更合理客觀的呈現(xiàn)出數(shù)據(jù)集中數(shù)據(jù)對(duì)象的所屬類(lèi)別及其之間的相互關(guān)系。

譜聚類(lèi)是建立在譜圖理論基礎(chǔ)上的一種聚類(lèi)算法。與傳統(tǒng)的聚類(lèi)算法相比,譜聚類(lèi)能夠在任意形狀的樣本空間上進(jìn)行聚類(lèi)且收斂于全局最優(yōu)解[2],并且使用線性代數(shù)基本知識(shí)即可實(shí)現(xiàn)。

文獻(xiàn)[3]提出利用抽樣數(shù)據(jù)樣本的相似性作為邊信息進(jìn)行距離度量學(xué)習(xí)的方法,從而使距離度量能夠更加合理地刻畫(huà)出該數(shù)據(jù)集中數(shù)據(jù)樣本之間的相互關(guān)系,并將其應(yīng)用 k-means和 Comstrained k-means聚類(lèi)算法中,使算法的預(yù)測(cè)精度得到了顯著提高。

本文利用數(shù)據(jù)集抽樣樣本的相似性作為邊信息進(jìn)行距離度量學(xué)習(xí),并且將學(xué)習(xí)所得的距離度量應(yīng)用于譜聚類(lèi)算法。

2 基于邊信息的距離度量學(xué)習(xí)

聚類(lèi)是一種無(wú)監(jiān)督的機(jī)器學(xué)習(xí)算法,所謂的相似性邊信息也就是從數(shù)據(jù)集中隨機(jī)抽取出來(lái)的一些數(shù)據(jù)樣本以及數(shù)據(jù)樣本之間所屬類(lèi)別的相互關(guān)系。

設(shè)現(xiàn)有數(shù)據(jù)集X={xi}?Rn,i=1,2,…,n,從X中隨機(jī)取出一些數(shù)據(jù)樣本,并確認(rèn)數(shù)據(jù)樣本xi與xj是否具有某種相似性,即數(shù)據(jù)樣本xi與xj否屬于同一類(lèi)別。若xi與xj屬于同一類(lèi)別,則(xi,xj)∈S,否則(xi,xj)∈DS。對(duì)于采集到的邊信息,本文使用矩陣SC,DC進(jìn)行描述如下:

其中,i,j=1,2,…,N,N為隨機(jī)抽取的數(shù)據(jù)樣本個(gè)數(shù)。

假設(shè)利用抽樣樣本相似性邊信息進(jìn)行學(xué)習(xí)所得距離度量具有如下所示的馬氏距離[4-5]形式:

其中,為了保證d(x,y)能夠滿足非負(fù)性和三角不等式,A必須是一個(gè)半正定的矩陣。

若A=I,則d(x,y)即為標(biāo)準(zhǔn)歐氏距離;若A是一個(gè)對(duì)角陣,則相當(dāng)于對(duì)數(shù)據(jù)樣本的每一個(gè)維度賦予了不同的權(quán)值。更廣泛地說(shuō),d(x,y)是Rn上的一個(gè)使用矩陣A參數(shù)化了的馬氏距離。

文獻(xiàn)[3]提出,求解矩陣A的一種可行方法就是規(guī)定集合S中的數(shù)據(jù)點(diǎn)對(duì)(xi,xj)之間具有最小的距離和。而集合DS中的數(shù)據(jù)點(diǎn)對(duì)(xi,xj)之間的距離大于等于1且矩陣A滿足半正定。因此,可以通過(guò)求解如下凸優(yōu)化問(wèn)題,得到矩陣A:

此時(shí),可以使用Newton-Raphson方法,定義:

在約束條件A≥0下最小化g對(duì)式(7)進(jìn)行求解,即可以得到一個(gè)對(duì)角矩陣A。

若使學(xué)習(xí)所得的矩陣A為全矩陣,可以使用梯度下降和迭代預(yù)測(cè)算法,求解如下與式(4)～式(6)等價(jià)的凸優(yōu)化問(wèn)題,即可得到全矩陣A:

梯度下降和迭代預(yù)測(cè)算法[3]如下:

其中,||M||F表示M的F范數(shù)

本文實(shí)驗(yàn)的距離度量學(xué)習(xí)采用Newton-Raphson方法,所得的矩陣A為對(duì)角矩陣。

3 譜聚類(lèi)算法

譜聚類(lèi)是近年來(lái)機(jī)器學(xué)習(xí)領(lǐng)域的一個(gè)新的研究熱點(diǎn),基于譜圖理論的譜聚類(lèi)已逐漸成為最為廣泛使用的聚類(lèi)算法之一。在計(jì)算機(jī)科學(xué)、統(tǒng)計(jì)學(xué)、物理學(xué)等領(lǐng)域越來(lái)越受到人們的關(guān)注[5]。與傳統(tǒng)的 kmeans等聚類(lèi)算法相比,譜聚類(lèi)在復(fù)雜形狀樣本空間聚類(lèi)中表現(xiàn)出了良好的性能。

標(biāo)準(zhǔn)譜聚類(lèi)算法的實(shí)現(xiàn)主要依賴(lài)于數(shù)據(jù)集中數(shù)據(jù)樣本的相似度矩陣S=Rn×n、連接矩陣W=Rn×n和度矩陣D=Rn×n。

在譜聚類(lèi)中通常采用高斯函數(shù)計(jì)算數(shù)據(jù)點(diǎn)之間的相似度[6]:

通常將相似度矩陣S采用ξ-近鄰、k-近鄰、全連通3種方式進(jìn)行稀疏化處理即可得到連接矩陣W,wij≥0,i,j=1,2,…,n且wij=wji。

度矩陣D則由下式計(jì)算所得:

由連接矩陣W和度矩陣D可以得到頂點(diǎn)集的拉普拉斯矩陣[7]。拉普拉斯矩陣分為非歸一化和歸一化2種。非歸一化的拉普拉斯矩陣計(jì)算公式如下:

歸一化的拉普拉斯矩陣計(jì)算公式如下:

其中,式(14)和式(15)中的L即為式(13)中的非歸一化拉普拉斯矩陣。Lsym是對(duì)稱(chēng)矩陣,Lrw是一個(gè)隨機(jī)游走矩陣,通常是非對(duì)稱(chēng)的[6]。

傳統(tǒng)譜聚類(lèi)算法就是在構(gòu)建的拉普拉斯矩陣中,根據(jù)聚類(lèi)個(gè)數(shù)k,求解其前k個(gè)特征值以及與其對(duì)應(yīng)的特征向量并構(gòu)建特征向量空間。然后采用k-means算法對(duì)特征向量空間中的特征向量進(jìn)行聚類(lèi)[8]。算法步驟描述如下:

輸入數(shù)據(jù)集X={xi}?Rn,i=1,2,…,n

輸出聚類(lèi)結(jié)果C1,C2,…,Ck

本研究結(jié)果提示,應(yīng)用利培酮對(duì)精神分裂進(jìn)行治療,能有效改善患者精神癥狀,且不良反應(yīng)輕,但可導(dǎo)致患者血脂異常及泌乳素水平上升。因此,在應(yīng)用利培酮對(duì)精神分裂癥患者進(jìn)行治療的過(guò)程中,需針對(duì)患者血脂和泌乳素實(shí)施定期的監(jiān)測(cè),加強(qiáng)相關(guān)危險(xiǎn)因素方面的評(píng)估。

Step1構(gòu)造基于樣本間相似度的相似度圖,并計(jì)算加權(quán)連接矩陣W,度矩陣D。

Step2計(jì)算拉普拉斯矩陣L(依據(jù)需要解決的實(shí)際應(yīng)用問(wèn)題采用非歸一化的拉普拉斯矩陣或者歸一化的拉普拉斯矩陣Lsym或者Lrw)。

Step3計(jì)算拉普拉斯矩陣L的前k個(gè)特征值及其對(duì)應(yīng)的特征向量v1,v2,…,vn(k為需要將數(shù)據(jù)集進(jìn)行聚類(lèi)的個(gè)數(shù))。

Step4采用經(jīng)典的k-means[9-10]聚類(lèi)算法對(duì)特征向量空間的特征向量進(jìn)行聚類(lèi),得到聚類(lèi)結(jié)果C1,C2,…,Ck。

4 基于距離度量學(xué)習(xí)的譜聚類(lèi)算法

在基于相似性邊信息進(jìn)行距離度量學(xué)習(xí)的譜聚類(lèi)算法中,將學(xué)習(xí)所得的距離度量d(x,y)應(yīng)用于譜聚類(lèi)算法的相似度計(jì)算函數(shù),構(gòu)造數(shù)據(jù)集的相似度矩陣S。數(shù)據(jù)樣本xi和xj的相似度采用如下公式進(jìn)行計(jì)算:

文獻(xiàn)[3]提出學(xué)習(xí)這樣的一個(gè)距離度量等價(jià)于尋找數(shù)據(jù)樣本的一種縮放尺度,即使用A1/2x替代數(shù)據(jù)樣本x,然后再在縮放后的數(shù)據(jù)集上使用標(biāo)準(zhǔn)的歐氏距離作為距離度量。

基于邊信息進(jìn)行距離度量學(xué)習(xí)的譜聚類(lèi)算法步驟如下:

輸出聚類(lèi)結(jié)果C1,C2,…,Ck

Step1從數(shù)據(jù)集X={xi}?Rn,i=1,2,…,n中隨機(jī)抽取N(N＜n)個(gè)樣本,記為樣本Y={yi}?Rn,i=1,2,…,N。

Step2通過(guò)識(shí)別判斷集合Y中的數(shù)據(jù)點(diǎn)(yi,yj),i,j=1,2,…,N是否屬于同一類(lèi)別,從而得到相似性邊信息矩陣SC,DC。

Step3利用相似性邊信息進(jìn)行距離度量學(xué)習(xí),得到距離度量公式d(x,y)。

Step4利用學(xué)習(xí)所得的距離度量公式,計(jì)算數(shù)據(jù)點(diǎn)之間的相似度矩陣S。

Step5計(jì)算連接權(quán)矩陣W和度矩陣D。

Step6計(jì)算拉普拉斯矩陣L(依據(jù)需要解決的實(shí)際應(yīng)用問(wèn)題采用非歸一化的拉普拉斯矩陣或者歸一化的拉普拉斯矩陣Lsym或者Lrw)。

Step7計(jì)算拉普拉斯矩陣L的前k個(gè)特征值及其對(duì)應(yīng)的特征向量v1,v2,…,vn(k為需要將數(shù)據(jù)集進(jìn)行聚類(lèi)的個(gè)數(shù))。

Step8采用經(jīng)典的k-means[9-10]聚類(lèi)算法對(duì)特征向量空間的特征向量進(jìn)行聚類(lèi),得到聚類(lèi)結(jié)果C1,C2,…,Ck。

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

5.1 實(shí)驗(yàn)平臺(tái)

本文所有實(shí)驗(yàn)都是在1臺(tái)PC機(jī)(Intel Core i3 CPU,主頻2.40 GHz,內(nèi)存2.0 GB)上進(jìn)行。采用Windows XP SP3操作系統(tǒng),Matlab R2009a開(kāi)發(fā)平臺(tái)。

5.2 結(jié)果分析

為了驗(yàn)證本文提出的使用數(shù)據(jù)集抽樣樣本相似性邊信息進(jìn)行距離度量學(xué)習(xí)的譜聚類(lèi)算法的有效性,分別在5個(gè)UCI[11]標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn),并將聚類(lèi)結(jié)果與標(biāo)準(zhǔn)的譜聚類(lèi)算法進(jìn)行了比較。

各個(gè)數(shù)據(jù)集的屬性如表1所示。

表1 各個(gè)UCI標(biāo)準(zhǔn)數(shù)據(jù)集的屬性

在實(shí)驗(yàn)中采用聚類(lèi)精度作為評(píng)價(jià)指標(biāo)。分別在各個(gè)數(shù)據(jù)集中隨機(jī)抽取 5個(gè)、10個(gè)、15個(gè)、20個(gè)、25個(gè)、30個(gè)數(shù)據(jù)樣本,并判斷各樣本的所屬類(lèi)別的相互關(guān)系作為相似性邊信息進(jìn)行距離度量學(xué)習(xí)。實(shí)驗(yàn)使用Hungarian算法[12]進(jìn)行聚類(lèi)精度計(jì)算。

各數(shù)據(jù)集實(shí)驗(yàn)結(jié)果如表2所示。

表2 UCI數(shù)據(jù)集實(shí)驗(yàn)結(jié)果對(duì)比

圖1～圖5為各個(gè)UCI標(biāo)準(zhǔn)數(shù)據(jù)集實(shí)驗(yàn)對(duì)比結(jié)果。

圖1 數(shù)據(jù)集soy bean實(shí)驗(yàn)結(jié)果對(duì)比

圖2 數(shù)據(jù)集Iris實(shí)驗(yàn)結(jié)果對(duì)比

圖3 數(shù)據(jù)集wine實(shí)驗(yàn)結(jié)果對(duì)比

圖4 數(shù)據(jù)集heart實(shí)驗(yàn)結(jié)果對(duì)比

圖5 數(shù)據(jù)集boston housing實(shí)驗(yàn)結(jié)果對(duì)比

通過(guò)對(duì)比分析可得,與標(biāo)準(zhǔn)譜聚類(lèi)算法相比,利用數(shù)據(jù)集抽樣樣本相似性邊信息進(jìn)行距離度量學(xué)習(xí)的譜聚類(lèi)算法的聚類(lèi)性能得到了顯著提高。然而,隨著數(shù)據(jù)集相似性邊信息的增多,聚類(lèi)的性能并不會(huì)成正比例上升。

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

本文提出一種利用數(shù)據(jù)集抽樣樣本相似性邊信息進(jìn)行距離度量學(xué)習(xí)的譜聚類(lèi)算法。實(shí)驗(yàn)結(jié)果表明,與標(biāo)準(zhǔn)譜聚類(lèi)算法相比,該算法的聚類(lèi)性能得到了明顯改善。在執(zhí)行譜聚類(lèi)算法時(shí),高斯相似度函數(shù)中的參數(shù)σ選取的是否合理,也會(huì)對(duì)聚類(lèi)結(jié)果產(chǎn)生重要的影響。因此,參數(shù)σ的選取是下一步需要研究的工作。

[1] 孫吉貴,劉 杰,趙連宇.聚類(lèi)算法研究[J].軟件學(xué)報(bào),2008,19(1):48-61.

[2] 蔡曉妍,戴冠中,楊黎斌.譜聚類(lèi)算法綜述[J].計(jì)算機(jī)科學(xué),2008,35(7):14-18.

[3] Eric P,Andrew Y,Michael I.Distance Metric Learning with Application to Clustering with Side-information[C]// Proceedings of NIPS’02.Vancouver,Canada:[s.n.], 2002:505-512.

[4] 張堯庭,方開(kāi)泰.多元統(tǒng)計(jì)分析引論[M].北京:科學(xué)出版社,1982.

[5] 張 翔,王士同.一種基于馬氏距離的可能性聚類(lèi)方法[J].數(shù)據(jù)采集與處理,2011,23(8):86-88.

[6] Luxburg U.A Tutorial on Spectral Clustering[J].Satictics and Computing,2007,17(4):395-416.

[7] Fiede M.Algebraic Connectivity of Graphs[J].Czechoslovak Math,1973,23(2):298-305.

[8] Ng A Y,Jordan M I,Weiss Y.On Spectral Clustering: Analysis and an Algorithm[C]//Proceedings of NIPS’01. Vancouver,Canada:[s.n.],2001:849-856.

[9] 張建輝.K-means聚類(lèi)算法研究及應(yīng)用[D].武漢:武漢理工大學(xué),2007.

[10] 王 千,王 成,馮振元,等.K-means聚類(lèi)算法研究綜述[J].電子設(shè)計(jì)工程,2012,20(7):21-24.

[11] UC Irvine. UC Irvine Machine Learning Repository[EB/OL].(2012-11-21).http://archive.ics.uci. edu/ml/index.html.

[12] Kuhn H W.The Hungarian Method for the Assignment Problem[J].Naval Research Logistics Quarterly,1955, 2(1/2):83-97.

編輯 劉 冰

Integrated Spectral Clustering Based on Distance Metric Learning

NIU Ke,ZHANG Xiaoqin,JIA Guojun
(School of Mathematics and Computer Science,Shanxi Normal University,Linfen 041004,China)

The performance of the unsupervised learning clustering algorithm is critically dependent on the distance metric being given by a user over the inputs of the data set.The calculation of the similarity between the data samples lies on the specified metric,therefore,the distance metric has a significant influence to the results of the clustering algorithm. Aiming at the problem of the selection of the distance metric for the spectral clustering algorithm,a spectral clustering algorithm based on distance metric learning with side-information is presented.The algorithm learns a distance metric with the side-information.The similarity between the data samples is chosen randomly from the data set,and is applied to the similarity function of spectral clustering algorithm.It structures the similarity matrix of the algorithm.The effectiveness of the algorithm is verified on real standard data sets on UCI,and experimental results show that compared with the standard spectral clustering algorithms,the prediction accuracy of the proposed algorithm is improved significantly.

data mining;side-information;similarity matrix;distance metric learning;spectral clustering;UCI data set

1000-3428(2015)01-0207-04

A

TP18

10.3969/j.issn.1000-3428.2015.01.038

山西省軟科學(xué)基金資助項(xiàng)目(2009041052-03)。

牛 科(1987-),男,碩士研究生,主研方向:智能計(jì)算,軟件工程;張小琴,碩士研究生;賈郭軍,副教授。

2013-10-31

2014-03-03 E-mail:niuke870505@163.com

中文引用格式:牛 科,張小琴,賈郭軍.基于距離度量學(xué)習(xí)的集成譜聚類(lèi)[J].計(jì)算機(jī)工程,2015,41(1):207-210.

英文引用格式:Niu Ke,Zhang Xiaoqin,Jia Guojun.Integrated Spectral Clustering Based on Distance Metric Learning[J]. Computer Engineering,2015,41(1):207-210.