拉普拉斯矩陣在聚類中的應用

劉 穎，張艷邦

(咸陽師范學院數學與信息科學學院，咸陽 712000)

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

1 拉普拉斯矩陣

1.1 拉普拉斯矩陣的概念

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

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

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

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

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

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

1.2 拉普拉斯矩陣的性質

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

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

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

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

1.3 拉普拉斯矩陣特征映射

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

2 拉普拉斯矩陣在降維中的應用

對于高維數據集來說，其包含有冗余信息以及噪聲信息，使得這些數據在聚類的過程中準確率低，時空復雜度高．因此，為了高效發現數據的內在結構，通常在數據分析之前對數據進行降維處理，使用拉普拉斯的特征進行降維是目前流行的一種降維方法．

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

降維的過程如下：

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

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

3 拉普拉斯矩陣在聚類分析中的應用

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

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

圖2 Flame數據集及其決策圖Fig. 2 Flame data set and its decision graph

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

對此類數據集的聚類分析過程如下：

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

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

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

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

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

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

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

4 實驗結果與分析

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

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

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

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

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

以 Dermatology數據集為例對實驗過程進行描述：

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

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

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

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

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

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

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

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

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

5 結 語

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