劉 穎，張艷邦

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

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

1 拉普拉斯矩陣

1.1 拉普拉斯矩陣的概念

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

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

圖1 簡(jiǎn)單無(wú)向圖Fig. 1 Simple undirected graph

圖1是由8個(gè)頂點(diǎn)組成的簡(jiǎn)單無(wú)向圖，頂點(diǎn)的度簡(jiǎn)單的說(shuō)是一個(gè)頂點(diǎn)連接的邊的個(gè)數(shù)，度矩陣是一個(gè)對(duì)角矩陣，圖1的度矩陣D為

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

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

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

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

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

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

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

1.3 拉普拉斯矩陣特征映射

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

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

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

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

降維的過(guò)程如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

以 Dermatology數(shù)據(jù)集為例對(duì)實(shí)驗(yàn)過(guò)程進(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)計(jì)算數(shù)據(jù)集 S = (sij)a×b的度矩陣 D =(dij)a×a．

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

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

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

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

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

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

5 結(jié) 語(yǔ)

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