峰值點非負矩陣分解聚類算法

徐曉華，方 威，何 萍，仁 祥，姜玉麟，葛方毅

（揚州大學信息工程學院，揚州 225000）

隨著互聯(lián)網(wǎng)和計算機技術(shù)的發(fā)展，人類已經(jīng)獲取了大量的高維數(shù)據(jù)。在信號處理［1］、模式識別［2］和計算機視覺［3］領(lǐng)域，如何將高維數(shù)據(jù)轉(zhuǎn)換為更有效的低維表示是至關(guān)重要的問題。在大多數(shù)情況下，數(shù)據(jù)被組織成矩陣或張量，因此一些線性模型，例如主成分分析（Principal component analysis，PCA）［4］，局部線性嵌入（Locally linear embedding，LLE）［5］和線性判別分析（Linear discriminant analy?sis，LDA）［6］可以很好地工作。與上述方法不同，Lee and Seung 在Nature 上提出了非負矩陣分解［7］（Non?negative matrix factorization，NMF）方法，它要求分解原始矩陣和通過分解得到的兩個矩陣都是非負的，并實現(xiàn)線性降維。非負矩陣分解及其改進算法已成功應用于文本聚類［8］、圖像去噪［9］以及人臉識別［10］等領(lǐng)域。

然而傳統(tǒng)NMF 方法的單一非負約束束不能滿足各個領(lǐng)域的需求，因此仍存在一些缺陷和局限性。為了挖掘高維數(shù)據(jù)間潛在的流形結(jié)構(gòu)信息，Cai 等［11］基于數(shù)據(jù)點之間的相似性構(gòu)造一個鄰居圖和一個加權(quán)鄰接矩陣提出了圖正則非負矩陣分解（Graph?regularized non?negative matrix factoriza?tion，GNMF），而考慮到NMF 和GNMF 中單個聚類中心不足以描述原始數(shù)據(jù)的復雜結(jié)構(gòu)，Gao 等［12］采用多個中心點來表示樣本的類別從而提出了局部中心結(jié)構(gòu)非負矩陣分解（Local centroids struc?tured non?negative matrix factorization， LCSN?MF）。為了自適應學習局部流形結(jié)構(gòu)，Huang 等［13］提出自適應鄰域的概念，為每個數(shù)據(jù)點自適應分配鄰居從而提出了具有自適應領(lǐng)域的非負矩陣分解（Non?negative matrix factorization with adaptive neighbor，NMFAN）。一般來說，簇中心是由一些局部密度較低的點所圍繞，且這些點距離其他高密度的點的距離都比較遠，針對簇中心的該特性，文獻［14］中提出了密度峰值算法，該算法通過計算最近鄰的距離，并依據(jù)密度大小進行排列得到數(shù)據(jù)的多個峰值點，從而得到聚類中心以實現(xiàn)數(shù)據(jù)的高效聚類。

然而GNMF 所構(gòu)造的近鄰圖是基于傳統(tǒng)的歐幾里得距離，在處理復雜數(shù)據(jù)結(jié)構(gòu)時有時并不能準確地描繪出樣本間的真實距離。此外，LCSNMF模型中對每個簇指定了相同的中心點數(shù)，而在實際應用中不同簇的結(jié)構(gòu)都存在差異，這樣的描述顯然是有缺陷的。針對上述兩個算法中存在的問題，本文提出了峰值點非負矩陣分解算法（Peaks non?negative matrix factorization，PNMF）。該算法通過找到數(shù)據(jù)的多個密度峰值點，并將其峰值點與樣本點構(gòu)造二部圖，再通過構(gòu)造基于測地線距離的數(shù)據(jù)近鄰圖，并將其融入非負矩陣分解模型。在利用多個密度峰值點表示樣本的類別的同時，也考慮了數(shù)據(jù)內(nèi)在的流形結(jié)構(gòu)。在多種類型的數(shù)據(jù)集上的實驗結(jié)果表明，該方法在特征提取和數(shù)據(jù)聚類等方面優(yōu)于其他同類的算法。

1 相關(guān)工作

1.1 非負矩陣分解

對于非負數(shù)據(jù)矩陣X∈Rm×n，NMF［7］算法可以將其分解為兩個非負矩陣F∈Rm×k和G∈Rn×k的乘積形式，其中k為樣本簇數(shù)。F中的每個列向量可以看作是每個簇的聚類中心，G中的每個行向量是每個樣本點與中心點之間的相關(guān)度。最初的NMF 提議采用Frobenius 范數(shù)來最大程度地減少重構(gòu)誤差，旨在解決以下問題

1.2 圖正則非負矩陣分解

由于NMF 是學習歐氏空間中輸入數(shù)據(jù)的低維表示的線性方法，因此它無法發(fā)現(xiàn)輸入數(shù)據(jù)的固有幾何結(jié)構(gòu)。因此，Cai 等研究了一種GNMF 的算法，該算法將基于圖的正則化器引入非負矩陣分解中，以在矩陣分解過程中保留數(shù)據(jù)的固有幾何結(jié)構(gòu)［11］。該問題的算法模型表示為

式中：λ為平衡參數(shù)；L為拉普拉斯矩陣。

1.3 局部中心結(jié)構(gòu)非負矩陣分解

在NMF 和GNMF 等算法中每個類別僅由一個中心點表示，然而這種表示由于缺少類別的結(jié)構(gòu)信息往往是模糊且粗糙的。針對上述問題，Gao等［12］提出了LCSNMF，該算法將非負數(shù)據(jù)矩陣X∈Rm×n分解成兩個矩陣F∈Rm×k和G∈Rn×k，這里k=ac且a為每個簇中的中心點數(shù)，且每個簇都由a個中心點來表示。LCSNMF 的優(yōu)化問題可以記為

因為每個簇有多個中心點，所以在分解后需要利用K?means［15］算法對系數(shù)矩陣G進一步聚類，但是因為考慮到K?means 算法對初始值較敏感，可能無法獲得最優(yōu)解，為了解決這一問題，LCSNMF 構(gòu)造了一個由中心點和樣本點組成的二部圖，其相似度矩陣S為

2 峰值點非負矩陣分解

雖然LCSNMF 算法采用了利用多個中心點來表示一個簇中樣本點的方法，但實際應用中每個簇的結(jié)構(gòu)不盡相同，對不同的簇指定相同的中心點數(shù)量顯然是不合理的，對于結(jié)構(gòu)復雜的數(shù)據(jù)無法得到最優(yōu)聚類結(jié)果。針對于該問題，本文提出了PNMF，本算法先通過密度峰值算法為數(shù)據(jù)集找到多個密度峰值點，再利用密度峰值點的線性組合得到簇中心點進行聚類，此外利用測地線距離構(gòu)建流形近鄰圖正則項融入NMF 框架。

2.1 測地線距離

在很多研究中，一般都會使用樣本點之間距離作為相似性度量。常用的距離度量包括歐氏距離、曼哈頓距離等。為了更好地利用復雜結(jié)構(gòu)的數(shù)據(jù)中的流形結(jié)構(gòu)信息，采用測地線距離［16］作為本文的距離度量標準。首先為原始數(shù)據(jù)中的所有樣本點構(gòu)造一個加權(quán)無向圖H=，每個樣本點都是圖H中的一個頂點，邊的集合表示為E={eij}，即樣本點xi和xj之間的歐氏距離。令q表示樣本點xi到xj的路徑，Qij={q1，q2，…}表示所有樣本點xi到xj的路徑的集合，則樣本點xi和xj間的測地線距離為

2.2 密度峰值

假設數(shù)據(jù)集X∈Rm×n中樣本點xi和xj之間的測地線距離為dij，假如將樣本點xi的鄰域定義為以樣本點xi為中心，截斷距離dcut為半徑的范圍，那該鄰域內(nèi)樣本點xi的局部密度就可以定義為

式中截斷距離dcut的值取太大會使得每個數(shù)據(jù)點都被歸為一類以致區(qū)分度不高，dcut的值取太小會使得每個數(shù)據(jù)點都被單獨分為一個類。根據(jù)文獻［14］中的經(jīng)驗，在實驗中對于dcut的選取，使平均每個點的鄰居數(shù)為所有點的1%。其中χ(a)為比較函數(shù)，且如果a<0 值為1；否則為0。

另外，從局部密度比xi大的樣本點中選取與最接近xi的樣本點，并將它們之間的距離表示為

當有局部密度更大的樣本點時，將δi定義為從最接近xi的樣本點到xi的距離；如果xi已經(jīng)是局部密度最大的樣本點時，δi定義為數(shù)據(jù)集中離xi最遠的樣本點到xi的距離。

因此對于密度峰值點的選取，綜合考慮樣本點局部密度和與密度中心的距離。在實際應用中，不同類中樣本的個數(shù)相差較大，密度也不盡相同，這樣會使得選取的峰值點分布不均，首先將所有樣本點作為密度峰值點的候補集合，再考慮每個樣本點的局部密度和與密度中心的距離按從大到小的順序依次選出一個樣本點，并從此前的候補集中去除以該點為中心、半徑為dcut的領(lǐng)域內(nèi)的樣本點，直到剩下的密度峰值點的數(shù)目為k，然后可以得到峰值矩陣Xdp∈Rm×k。

在人造數(shù)據(jù)集Twomoons 中，將提出的PNMF 通過密度峰值算法在Twomoons 數(shù)據(jù)集中找到多個密度峰值點，如圖1 所示，密度峰值［17］算法通過考慮樣本點之間的距離和密度得到選取的密度峰值點能更好地獲得數(shù)據(jù)本身的流形結(jié)構(gòu)。

圖1 Twomoons 數(shù)據(jù)集上的密度峰值點Fig.1 Peaks on the Twomoons dataset

2.3 峰值點非負矩陣分解

在得到數(shù)據(jù)集中的密度峰值點后，本文提出的PNMF 算法將原矩陣分解為

式中：Xdp∈Rm×k為密度峰值矩陣；F∈Rk×k為峰值點的非負線性組合；G∈Rn×k為樣本點與峰值點的關(guān)聯(lián)矩陣。

根據(jù)流形假設：如果在原始空間中樣本點xi和xj間的測地線dij距離相近，那么它們在子空間下的表示gi和gj間的距離也應該是相近的，因此構(gòu)造圖正則項tr(GTLgeoG)，其中Lgeo=D(W)-W為原始空間中樣本點間流形距離的拉普斯拉斯矩陣，其中D(W) =diag(W1)，W定義為

將密度峰值矩陣融入NMF 分解模型，利用密度峰值點與樣本點的關(guān)聯(lián)矩陣G構(gòu)造二部圖，引入基于測地線距離的流形圖正則項，最終得到PNMF 的優(yōu)化模型為

2.4 模型優(yōu)化

目標函數(shù)式（12）中的F，G，P并非同時都是凸的，因此很難找到全局最小值解，下面將介紹一種迭代算法來獲取模型的局部最優(yōu)解。

更新因子P：先固定因子F，G，求解因子P，此時的優(yōu)化問題為

該問題的最優(yōu)解由拉普拉斯矩陣LS前c小的特征值所對應的特征向量組成。

更新因子F：先固定因子P，G，求解因子F。此時的優(yōu)化問題為

則式（15）關(guān)于F的偏導數(shù)為

因此，F(xiàn)的更新公式為

更新因子G：先固定因子P，F(xiàn)，求解因子G。此時的優(yōu)化問題為

其中正則項tr(PTLS P)可以寫成

則式（20）關(guān)于G的偏導數(shù)為

因此，G的更新公式為

2.5 復雜度分析

計算更新P的復雜度為LS特征值分解需要O((n+k)3)。F的更新中分子的復雜度為O(mnk)，分母的復雜度為O(mnk)，因此更新F的復雜度為O(mnk)。在G的更新中分子的復雜度為O(mnk)， 分 母 的 復 雜 度 為O(mnk) +O((m+n)c)+O(mnk) =O(mnk)，因此更新F的復雜度為O(mnk)。

綜上，因為k≤min{m，n}，迭代更新一次PNMF 算法需要復雜度為O(mnk) +O((n+k)3) +O(mnk) +O(mnk) =O(n3)。如果更新迭代t次，則算法復雜度為O(n3t)。

3 實驗分析

為了驗證所提出的PNMF 算法的有效性，分別在3 個常見的面部數(shù)據(jù)集（Yale，ORL，COIL20）、1 個文本數(shù)據(jù)集TDT2 以及1 個聲音數(shù)據(jù)集ISOLET 上進行聚類實驗，并選取NMF、GN?MF、LSCNMF 和NMFAN 為比較算法。本節(jié)將給出數(shù)據(jù)集、評價指標和實驗分析等內(nèi)容，此外每次實驗獨立隨機，重復20 次取平均和標準差作為最后實驗結(jié)果。

3.1 數(shù)據(jù)集

為了進一步驗證PNMF 算法的有效性，選擇的數(shù)據(jù)集有：Yale、ORL、COIL20、TDT2 和ISO?LET。

Yale 人臉數(shù)據(jù)集包含來自15 個主題的165 張圖像，每個人有11 張圖像。圖像顯示了在不同照明條件下（左燈，中央燈和右燈）、面部表情（正常，快樂，悲傷，困倦，驚訝和眨眼）以及戴著或不戴眼鏡的變化。

ORL 數(shù)據(jù)集具有40 個不同主題中的每個主題的10 個不同圖像。一些圖像是在不同的時間拍攝的，它們具有不同的照明，面部表情（睜開/閉合的眼睛，微笑/沒有笑容）和面部細節(jié)（有眼鏡/無眼鏡）。

COIL20 圖像數(shù)據(jù)集包含不同角度觀看的20個對象的32×32 灰度面部圖像，每個對象有72 個圖像。

TDT2 文本數(shù)據(jù)集來自NIST 主題檢測與跟蹤語料庫。TDT2 包括1998 年上半年收集的數(shù)據(jù)，來自6 個來源，包括2 個新聞通訊社（APW、NYT）、2 個廣播節(jié)目（美國之音、PRI）和2 個電視節(jié)目（CNN、ABC）。它包含11 201 個主題文檔，分為96 個語義類別。實驗中選擇其子集包括1 319個主題文檔，分為5 個語義類別。

ISOLET 聲音數(shù)據(jù)集來自UCI 機器學習資料庫，它包括150 名受試者說出字母表中每個字母的名字兩次，因此每個人有52 個樣本。選取原始數(shù)據(jù)集的子集，共包括2 098 個樣本。

在實驗中將所有圖像均壓縮成32×32 大小的灰度圖，將其每列相連構(gòu)成大小為1 024 維的向量，其中TDT2 文本數(shù)據(jù)集維度為14 964，ISO?LET 聲音數(shù)據(jù)集維度為617，所有數(shù)據(jù)集都進行歸一化處理。圖2 給出了3 個面部數(shù)據(jù)庫的一些樣本示例。

圖2 實驗數(shù)據(jù)集示例Fig.2 Instances of experimental datasets

3.2 聚類評價指標

為了更好地評估每個數(shù)據(jù)集上每種算法的聚類性能，使用了3 個常用的聚類評估指標：ACC、NMI 和Rand Index［18］。

聚類準確率（ACC）：它查找真實類與聚類結(jié)果之間的一對一關(guān)系，并從相應類中獲取每個聚類所具有的數(shù)據(jù)樣本，定義為

式中：ri表示xi的聚類結(jié)果；li表示數(shù)據(jù)xi的真實標簽；n為整體的樣本數(shù)量；map(ri)表示最佳映射函數(shù)，并使用Kuhn?Munkres 算法確定最佳映射。此外δ(a，b)表示Delta 函數(shù)，且如果a=b值為1，否則為0。

標準互信息（NMI）：NMI 使用互信息函數(shù)和熵函數(shù)來評估聚類結(jié)果，定義如下

Rand Index：它將聚類結(jié)果與數(shù)據(jù)的真實類別進行比較，計算正確聚類結(jié)果的比例。Rand Index值越大，聚類效果越好。

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

在實驗中，對于NMF、GNMF 和NMFAN 算法，將分解的規(guī)模k默認設為數(shù)據(jù)集中簇的個數(shù)；對于LCSNMF 算法和PNMF 算法，將簇平均樣本點個數(shù)的1%～10%作為每個簇中心點的個數(shù)m，并且每個簇中的每個樣本點與s個中心點相關(guān)，且m是從｛1、2、3、4、5、6、7｝中選擇的，s是從｛1、2、3、4｝中選擇的。此外，對于PNMF 算法模型中的正則化參數(shù)，在｛1、10、100、1 000、10 000｝的范圍內(nèi)選擇參數(shù)λ1，但是基于測地距離的圖正則項的參數(shù)λ2和GNMF 一致，均設置固定值為100。與譜聚類等其他聚類算法相比，K?means 因其有效性和效率高而得到廣泛運用，實驗中和文獻［19?20］中一樣使用K?means 應用于矩陣分解后的表示矩陣G，就可以得到最終的聚類結(jié)果。

表1～5 分別顯示了面部、文本和人臉數(shù)據(jù)集上的聚類性能。從表1～5 可以看出，在大多數(shù)情況下，PNMF 聚類評估指數(shù)的結(jié)果更好。從實驗結(jié)果來看，構(gòu)造基于歐幾里得距離的近鄰圖的GN?MF 和NMFAN 不如構(gòu)造基于流形距離近鄰圖的PNMF 的聚類性能好，說明了傳統(tǒng)的歐幾里得距離在面對更加復雜高維的數(shù)據(jù)時，并不能很好且準確地表示數(shù)據(jù)間的真實距離。LCSNMF 由于其簇中心選取的局限性，效果也不如PNMF，而傳統(tǒng)的NMF 聚類因為缺乏約束，性能不是很好。從實驗結(jié)果來看，本文提出的利用多個峰值點與樣本點構(gòu)造二部圖的方法可以更好地捕獲復雜數(shù)據(jù)的內(nèi)部幾何結(jié)構(gòu)，從而提高聚類效果。

表1 Yale 數(shù)據(jù)集上的聚類性能比較Table 1 Comparison of clustering performance on Yale dataset

表2 ORL 數(shù)據(jù)集上的聚類性能比較Table 2 Comparison of clustering performance on ORL dataset

表3 COIL20 數(shù)據(jù)集上的聚類性能比較Table 3 Comparison of clustering performance on COIL20 dataset

表4 TDT2 數(shù)據(jù)集上的聚類性能比較Table 4 Comparison of clustering performance on TDT2 dataset

表5 ISOLET 數(shù)據(jù)集上的聚類性能比較Table 5 Comparison of clustering performance on ISOLET dataset

3.4 參數(shù)討論

本節(jié)將給出PNMF 在不同正則化參數(shù)設置下的聚類性能。在PNMF 算法中，簇中心點數(shù)m設置決定了矩陣分解的大小，而樣本點可以關(guān)聯(lián)的中心點數(shù)s決定了二部圖的構(gòu)造，因此對聚類的結(jié)果有一定影響。另外，參數(shù)λ1和λ2來平衡二部圖的正則項和基于測地距離的近鄰圖正則項。在實驗中，將λ2和GNMF 都設置一致為100，并討論了參數(shù)λ1對聚類性能的影響。

以COIL20 數(shù)據(jù)集為例，將m設置為1～7，將s設置為1～4。在這種參數(shù)變化的情況下，測試了COIL20 的3 個聚類指標變化。測試結(jié)果如圖3～5所示。從測試結(jié)果來看，當m=5 且s=4 時，COIL 20 的聚類性能最佳。且隨著s值的增加可以增強聚類性能，并且當m為4～6 時，每個聚類指標的值都較高。從實驗結(jié)果可以看出，聚類中心點的數(shù)量m對聚類性能影響較小，但s的值對聚類性能顯得更敏感，可能因為s的值決定構(gòu)造的二部圖的質(zhì)量，因此對結(jié)果有一定影響。

圖3 COIL20 在不同m 及s 下的ACCFig.3 ACC under different m and s on COIL20

然后將討論正則化參數(shù)對提出的PNMF 模型的影響。模型具有兩個正則化參數(shù)即λ1和λ2，它們分別來平衡二部圖正則項和基于流形距離圖正則項。在實驗中將λ2設置為100，然后討論λ1的變化對COIL20 數(shù)據(jù)集的3 個聚類性能指標的影響，λ1的值選自｛1、10、100、1 000、10 000｝，實驗結(jié)果如圖6 所示。

從圖6 可以看出，PNMF 對λ1只是一點點敏感。可以發(fā)現(xiàn)，隨著λ1值的增加，3 個性能指標呈略微上升的趨勢。

圖4 COIL20 在不同m 及s 下的NMIFig.4 NMI under different m and s on COIL20

圖5 COIL20 在不同m 及s 下的Rand IndexFig.5 Rand index under different m and s on COIL20

圖6 COIL20 在不同λ1 下的聚類結(jié)果Fig.6 Clustering results of COIL20 under different λ1

4 結(jié)論

本文提出了一種新方法PNMF。首先計算每個樣本點的局部密度，利用局部密度從數(shù)據(jù)集中找到多個密度峰點，它為每個簇指定多個中心點，并利用密度峰值點和樣本點構(gòu)造二部圖。另外采用流形結(jié)構(gòu)下的測地線距離，并用測地線距離構(gòu)造了數(shù)據(jù)的近鄰圖，從而描述了局部幾何關(guān)系，使得樣本點之間距離更準確。為了證明該算法的有效性，本文比較了該算法在幾個面部數(shù)據(jù)集以及文本、聲音數(shù)據(jù)集上的聚類效果。實驗結(jié)果表明，PNMF 相比其他NMF 算法具有更好的聚類性能。