拉普拉斯矩陣在聚類中的應(yīng)用

劉 穎，張艷邦

(咸陽師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院，咸陽 712000)

隨著信息時代的發(fā)展，各行各業(yè)都產(chǎn)生了大量的數(shù)據(jù)，人們不再滿足數(shù)據(jù)僅僅被電子化，而是希望對數(shù)據(jù)進(jìn)行分析挖掘，透過數(shù)據(jù)的表象，找到隱藏在數(shù)據(jù)背后的規(guī)律和結(jié)構(gòu)[1]．聚類分析是數(shù)據(jù)挖掘的一個重要工具，聚類分析的目的是從一個未知數(shù)據(jù)集中發(fā)現(xiàn)隱含在其間的數(shù)據(jù)內(nèi)在結(jié)構(gòu)信息，將數(shù)據(jù)劃分為若干個不相交的子集，每個子集成為一個簇，同一個簇內(nèi)數(shù)據(jù)相似性大，簇間數(shù)據(jù)相異性大[2]．?dāng)?shù)據(jù)聚類分析主要面臨兩個問題：一是如何確定聚類的結(jié)構(gòu)；二是現(xiàn)在的數(shù)據(jù)大都是高維數(shù)據(jù)，如何能在聚類前對數(shù)據(jù)進(jìn)行降維，從而提高聚類的效率[3]．這兩個問題也是目前研究的熱點．拉普拉斯矩陣(Laplacian matrix)也稱為導(dǎo)納矩陣，主要應(yīng)用在圖論中，作為一個圖的矩陣表示，它廣泛地應(yīng)用在工程中[4-5]．聚類問題從圖的角度看就是對圖的分割問題[6]，因此拉普拉斯矩陣被應(yīng)用到聚類分析中，出現(xiàn)了一種譜聚類算法(spectral clustering)，該算法的核心思想就是把樣本空間的聚類問題轉(zhuǎn)化為無向圖G的圖劃分問題[7]．譜聚類算法在尋找聚類方面比傳統(tǒng)算法(如k-means)更有效[8]．然而，當(dāng)數(shù)據(jù)集很大時，譜聚類的時空復(fù)雜度都比較大．為了對大數(shù)據(jù)集進(jìn)行聚類，基于拉普拉斯矩陣，結(jié)合樣本點的密度和距離，介紹了一種新的候選聚類中心選擇方法．該方法先利用拉普拉斯矩陣對數(shù)據(jù)集進(jìn)行降維處理，對經(jīng)過降維處理的數(shù)據(jù)求出其密度和距離兩個參數(shù)，從而形成密度距離決策圖；然后利用決策圖選出候選聚類中心，對其進(jìn)行合并，得到最終的聚類中心，最后將剩余點分配給聚類中心，完成聚類．實驗結(jié)果表明了算法的有效性．

1 拉普拉斯矩陣

1.1 拉普拉斯矩陣的概念

拉普拉斯矩陣[9]主要應(yīng)用在圖論中，是表示圖的一種矩陣．給定一個有n個頂點的無向圖G=(V,E)，其中V表示所有頂點 v1, v2,…, vn的集合，E表示頂點之間連接的邊的集合，拉普拉斯矩陣的定義如式(1)所示

式中：D 為圖的度矩陣，W 為圖的鄰接矩陣．用圖 1對拉普拉斯矩陣進(jìn)行說明．

圖1 簡單無向圖Fig. 1 Simple undirected graph

圖1是由8個頂點組成的簡單無向圖，頂點的度簡單的說是一個頂點連接的邊的個數(shù)，度矩陣是一個對角矩陣，圖1的度矩陣D為

根據(jù)式(2)可知，圖1的鄰接矩陣為

有了 D和W，根據(jù)式(1)可知，圖 1的拉普拉斯矩陣為

1.2 拉普拉斯矩陣的性質(zhì)

拉普拉斯矩陣具有以下4個性質(zhì)[10]：

(1)拉普拉斯矩陣的最小特征值為 0，其所對應(yīng)的特征向量為1．

(2)拉普拉斯矩陣是對稱的半正定矩陣．

(4)對于任意向量f∈Rn有式(3)成立

1.3 拉普拉斯矩陣特征映射

拉普拉斯特征映射(Laplacian Eigenmaps)[11]是從局部的角度出發(fā)來處理圖，盡量在保留原圖基本結(jié)構(gòu)的情況下，將其映射到低維下表示．根據(jù)拉普拉斯矩陣的性質(zhì)，得出拉普拉斯特征映射的基本思想是希望相互有關(guān)系的點如圖1中的頂點1和頂點2，在降維后的空間中盡可能的靠近，相互之間沒有關(guān)系的頂點如圖1中的頂點1和頂點6，在降維后的空間中盡可能的遠(yuǎn)離．從拉普拉斯矩陣特征映射，發(fā)現(xiàn)其非常符合從高維數(shù)據(jù)中提取出能代表原始數(shù)據(jù)的低維表達(dá)這一情況．

2 拉普拉斯矩陣在降維中的應(yīng)用

對于高維數(shù)據(jù)集來說，其包含有冗余信息以及噪聲信息，使得這些數(shù)據(jù)在聚類的過程中準(zhǔn)確率低，時空復(fù)雜度高．因此，為了高效發(fā)現(xiàn)數(shù)據(jù)的內(nèi)在結(jié)構(gòu)，通常在數(shù)據(jù)分析之前對數(shù)據(jù)進(jìn)行降維處理，使用拉普拉斯的特征進(jìn)行降維是目前流行的一種降維方法．

拉普拉斯特征映射的基本思想是對給定的有n個數(shù)據(jù)對象的高維數(shù)據(jù)集，在保持局部臨近關(guān)系特征不變的情況下，找到數(shù)據(jù)集 A對應(yīng)的低維數(shù)據(jù)集

降維的過程如下：

(1)根據(jù)K近鄰求出數(shù)據(jù)集的鄰接矩陣W，對任意一對數(shù)據(jù)對象xi和xj，若xi在xj的最近K個點內(nèi)，則 wij=1，否則 wij=0；由于 xi與周圍最近的 K個點之間的距離大小不一，為了精確刻畫點之間的距離，根據(jù)數(shù)據(jù)的需要，還可以為每條邊賦權(quán)，利用熱核函數(shù)為每條邊賦權(quán)W如式(4)所示．

(2)利用拉格朗日乘數(shù)法計算拉普拉斯矩陣L的特征值：

3 拉普拉斯矩陣在聚類分析中的應(yīng)用

大多聚類算法都需要人為的選擇聚類中心，經(jīng)典的 k-means算法需在開始隨機給出k個點作為初始聚類中心，經(jīng)過不斷迭代，最后選擇穩(wěn)定下來的聚類分布作為最后的結(jié)果，由于初始聚類中心的任意性，在很大程度上影響了聚類效果．2014年發(fā)表在Science上的一個聚類算法FSDP[12]，摒棄了 k-means隨機選擇聚類中心的不確定性．FSDP算法提出聚類中心一定是那些在某一個鄰域內(nèi)密度最高，且較其他高于自己密度的數(shù)據(jù)點的距離較遠(yuǎn)的點．算法構(gòu)造一個橫坐標(biāo)為密度ρ、縱坐標(biāo)為距離δ的決策圖，供用戶選擇合適的聚類中心．其中：第 i個點的密度ρi表示在 i點的指定鄰域 d c內(nèi)包含的數(shù)據(jù)點的個數(shù)，即式(6)

該算法對低維數(shù)據(jù)聚類分析有眾多優(yōu)點，以數(shù)據(jù)集flame為例，如圖2所示．圖2(a)為二維數(shù)據(jù)集的圖形表示，圖 2(b)為由密度ρ和距離δ組成的決策圖，算法通過選擇找到聚類中心(ρ和δ數(shù)值都大的點)．首先找到彩色的點即候選聚類中心，然后采用合并原則，對候選聚類中心進(jìn)行合并，得到真正的聚類中心，最后完成聚類．

圖2 Flame數(shù)據(jù)集及其決策圖Fig. 2 Flame data set and its decision graph

由于此數(shù)據(jù)集維度低，且無噪聲點，因此聚類效果好．對于維度高、噪聲多的數(shù)據(jù)集，由于其特征冗余、噪聲點影響，所以從決策圖很難準(zhǔn)確找到聚類中心，如圖3所示．

對此類數(shù)據(jù)集的聚類分析過程如下：

(1)計算數(shù)據(jù)集 S = (sij)a×b的鄰接矩陣M．

(2)計算數(shù)據(jù)集 S = (sij)a×b的度矩陣D．

(3)計算數(shù)據(jù)集 S = (sij)a×b的拉普拉斯矩陣L．

(4)利用拉格朗日乘數(shù)法計算拉普拉斯矩陣的各特征值和特征向量．

(5)對特征值按升序進(jìn)行排序，自次小特征值起取 m個特征值，并求出其對應(yīng)的 m個特征向量，這些特征向量組成新的矩陣．

(6)對新的矩陣按式(6)和式(7)分別計算ρ和δ，最后畫出新的決策圖，找到聚類中心，完成聚類．

圖3 高維含噪聲數(shù)據(jù)集決策圖Fig. 3 Decision diagram of high-dimensional noisecontaining data set

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

為了測試算法對不同樣本數(shù)目、維度大小、類別數(shù)目的高維數(shù)據(jù)集的有效程度，特別從 UCI(http：//archive.ics.uci.edu/ml/datasets.html)中選出了 Dermatology、Credit approval、German credit、Wine、Ionosphere 5個數(shù)據(jù)集(維度大于10維、樣本數(shù)目大小不一、類別數(shù)目不同)進(jìn)行聚類分析實驗，結(jié)果見表 1．

表1 高維數(shù)據(jù)集的聚類信息表Tab. 1 Clustering information table for high-dimensional data sets

為了測試算法在對高維數(shù)據(jù)有效的同時，不失去對低維數(shù)據(jù)的效力，特別從 Clustering datasets(http：//cs.uef.fi/sipu/datasets/)中選 出了 Flame、Jain、Smiles、Aggregation、Spiral 5個低維數(shù)據(jù)集(維度 2維、樣本數(shù)目大小不一、類別數(shù)目不同)在同樣的環(huán)境下進(jìn)行了聚類實驗分析測試，實驗結(jié)果見表2．

表2 低維數(shù)據(jù)集的聚類信息表Tab. 2 Clustering information table for low-dimensional data sets

實驗在個人電腦上運行，采用Matlab R2014b編程工具進(jìn)行聚類分析．

以 Dermatology數(shù)據(jù)集為例對實驗過程進(jìn)行描述：

(1)設(shè)數(shù)據(jù)集 Dermatology為 S = (sij)a×b，a為樣本數(shù)366，b為數(shù)據(jù)集的維數(shù)34．

(2)構(gòu)造鄰接矩陣 M =(mij)a×a，mij為樣本 i與樣本j的相似度．

(3)計算數(shù)據(jù)集 S = (sij)a×b的度矩陣 D =(dij)a×a．

(4)計 算 數(shù) 據(jù) 集 S = (sij)a×b的 拉 普 拉 斯 矩 陣L = (lij)a×b．

(5)利用拉格朗日乘數(shù)法計算拉普拉斯矩陣的各特征值和特征向量．

(6)對特征值按升序進(jìn)行排序，自次小特征值起取 m個特征值，并求出其對應(yīng)的 m個特征向量，這些特征向量組成新的矩陣 S'=(s'ij)a×m(m≤b)．

(7)對矩陣S'按公式(6)、(7)分別計算ρ和δ，最后畫出新的決策圖，找到聚類中心．

(8)將剩余的樣本點按照最近鄰原則分配到各個聚類中心，完成聚類．

表1的實驗結(jié)果顯示聚類數(shù)目選擇正確，聚類效果良好，這表明通過使用拉普拉斯矩陣對數(shù)據(jù)集進(jìn)行降維處理，能有效處理冗余數(shù)據(jù)和噪聲數(shù)據(jù)，從而純化數(shù)據(jù)集，提高候選聚類中心選擇的正確率，進(jìn)而達(dá)到了提高聚類效率和正確率的目的．表 2的實驗結(jié)果表明，算法不僅對高維數(shù)據(jù)集有效，對低維數(shù)據(jù)集效力并沒有消失，聚類數(shù)目選擇正確，聚類結(jié)果正確率高，因此證明算法對聚類數(shù)據(jù)集一定的寬泛性．

5 結(jié) 語

本文討論了拉普拉斯矩陣的原理，針對拉普拉斯矩陣的特征，首先，使用拉普拉斯矩陣對數(shù)據(jù)集進(jìn)行降維處理，為數(shù)據(jù)的高效聚類打好基礎(chǔ)；其次，結(jié)合FSDP算法，對降維后的數(shù)據(jù)集求出密度和距離，得到候選聚類中心，對候選聚類中心進(jìn)行合并，獲得最終的聚類中心；最后，將剩余樣本點分配到各個聚類中心，求出最終的聚類結(jié)果．拉普拉斯矩陣的應(yīng)用降低了冗余數(shù)據(jù)和噪聲數(shù)據(jù)對數(shù)據(jù)結(jié)構(gòu)的影響，在 10個不同樣本數(shù)、不同維度、不同類別數(shù)的數(shù)據(jù)集上進(jìn)行聚類分析實驗，實驗結(jié)果表明算法的有效性．拉普拉斯矩陣在聚類中的使用，凸顯了拉普拉斯矩陣特征的實用性，為在其他領(lǐng)域使用提供了啟示．