牛 科,張小琴,賈郭軍

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

基于距離度量學習的集成譜聚類

牛 科,張小琴,賈郭軍

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

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

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

1 概述

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

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

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

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

本文利用數(shù)據(jù)集抽樣樣本的相似性作為邊信息進行距離度量學習,并且將學習所得的距離度量應用于譜聚類算法。

2 基于邊信息的距離度量學習

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

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

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

假設利用抽樣樣本相似性邊信息進行學習所得距離度量具有如下所示的馬氏距離[4-5]形式:

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

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

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

此時,可以使用Newton-Raphson方法,定義:

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

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

梯度下降和迭代預測算法[3]如下:

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

本文實驗的距離度量學習采用Newton-Raphson方法,所得的矩陣A為對角矩陣。

3 譜聚類算法

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

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

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

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

度矩陣D則由下式計算所得:

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

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

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

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

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

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

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

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

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

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

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

4 基于距離度量學習的譜聚類算法

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

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

基于邊信息進行距離度量學習的譜聚類算法步驟如下:

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

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

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

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

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

Step5計算連接權矩陣W和度矩陣D。

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

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

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

5 實驗結(jié)果與分析

5.1 實驗平臺

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

5.2 結(jié)果分析

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

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

表1 各個UCI標準數(shù)據(jù)集的屬性

在實驗中采用聚類精度作為評價指標。分別在各個數(shù)據(jù)集中隨機抽取 5個、10個、15個、20個、25個、30個數(shù)據(jù)樣本,并判斷各樣本的所屬類別的相互關系作為相似性邊信息進行距離度量學習。實驗使用Hungarian算法[12]進行聚類精度計算。

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

表2 UCI數(shù)據(jù)集實驗結(jié)果對比

圖1～圖5為各個UCI標準數(shù)據(jù)集實驗對比結(jié)果。

圖1 數(shù)據(jù)集soy bean實驗結(jié)果對比

圖2 數(shù)據(jù)集Iris實驗結(jié)果對比

圖3 數(shù)據(jù)集wine實驗結(jié)果對比

圖4 數(shù)據(jù)集heart實驗結(jié)果對比

圖5 數(shù)據(jù)集boston housing實驗結(jié)果對比

通過對比分析可得,與標準譜聚類算法相比,利用數(shù)據(jù)集抽樣樣本相似性邊信息進行距離度量學習的譜聚類算法的聚類性能得到了顯著提高。然而,隨著數(shù)據(jù)集相似性邊信息的增多,聚類的性能并不會成正比例上升。

6 結(jié)束語

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

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

[2] 蔡曉妍,戴冠中,楊黎斌.譜聚類算法綜述[J].計算機科學,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] 張堯庭,方開泰.多元統(tǒng)計分析引論[M].北京:科學出版社,1982.

[5] 張 翔,王士同.一種基于馬氏距離的可能性聚類方法[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聚類算法研究及應用[D].武漢:武漢理工大學,2007.

[10] 王 千,王 成,馮振元,等.K-means聚類算法研究綜述[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

山西省軟科學基金資助項目(2009041052-03)。

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

2013-10-31

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

中文引用格式:牛 科,張小琴,賈郭軍.基于距離度量學習的集成譜聚類[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.