正則化低秩子空間譜聚類算法

何家玉+許峰

摘 要：為解決缺損數(shù)據(jù)譜聚類中的不適定問題，提出一種正則化低秩子空間譜聚類算法。首先根據(jù)數(shù)據(jù)集建立核范數(shù)正則化低秩矩陣分解模型，然后用迭代法求解模型得出系數(shù)矩陣，由此構造相似矩陣，最后利用譜聚類算法得出聚類結果。實驗表明，該算法在一定程度上可以解決缺損數(shù)據(jù)的譜聚類問題，抑制噪聲，獲得質量較高的聚類結果。

關鍵詞：聚類分析；譜聚類；低秩子空間；不適定；正則化

DOIDOI：10.11907/rjdk.162025

中圖分類號：TP311

文獻標識碼：A文章編號：1672-7800（2016）012-0022-03

0 引言

聚類分析是數(shù)據(jù)挖掘的一個重要研究領域，在統(tǒng)計學、生物學、模式識別、機器學習和社會科學中有著極為廣泛的應用。所謂聚類就是將數(shù)據(jù)對象分組成為多個類或簇，使得在同一簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大。k-均值聚類是聚類分析中最經(jīng)典的算法，算法簡單，可用于多種類型數(shù)據(jù)的聚類。但當數(shù)據(jù)集為非凸時，k-均值聚類往往陷于局部最優(yōu)，聚類效果欠佳。另外，對于大小或密度不均勻的簇，k-均值聚類通常無法處理[1]。

譜聚類是一種新型的聚類分析方法，可以克服k-均值聚類等經(jīng)典方法的一些缺陷[2]。譜聚類方法以圖論中的譜圖理論為基礎，將聚類問題轉化為圖的最優(yōu)劃分問題。在眾多圖的最優(yōu)劃分準則中，歸一化割集準則的劃分效果相對較好，是譜聚類中常用的劃分準則[3]。對于給定的劃分準則和聚類數(shù)目k，譜聚類通常采用多路譜聚類算法將數(shù)據(jù)集劃分為k個簇[4]。

最早的譜聚類算法是Ng，Bach和Jordan[4-5]提出的多路譜聚類方法。代表性的譜聚類算法還有Meila[6]提出的多路歸一化割譜聚類方法；Vidal[7]提出的子空間譜聚類方法；Wang等[8]提出的多流形譜聚類方法；Cheng等[9]提出的低秩譜聚類方法；Elhamifar等[10]提出的稀疏子空間譜聚類方法。

在眾多譜聚類算法中，低秩稀疏子空間譜聚類越來越受到學者的重視。在有些實際問題中，數(shù)據(jù)并不符合混合子空間的假設，分析這種數(shù)據(jù)具有很大的挑戰(zhàn)性。研究表明，基于譜聚類的方法是處理該類問題的有效方法。雖然這類數(shù)據(jù)本身無法使用相互表示的方式，但是數(shù)據(jù)的特征可相互線性表示，且表示系數(shù)具有稀疏性或低秩性的特點。目前，這種低秩表示方法已被擴展用于圖像處理。

本文在低秩子空間譜聚類算法的基礎上，引入正則化過程以解決不適定問題，并根據(jù)數(shù)值實驗對該算法進行性能測試。

1 譜聚類矩陣

譜聚類的基本思想是將聚類問題轉化為圖的最優(yōu)劃分問題，利用圖的最優(yōu)劃分準則，使劃分出的子圖之間的邊權之和較小，而子圖內(nèi)的邊權之和較大。下面簡要介紹本文算法設計過程中涉及到的譜聚類矩陣。

上述譜聚類矩陣性質類似但又有差異，不同的譜聚類算法可以選用不同的譜聚類矩陣。

2 正則化低秩子空間譜聚類算法

2.1 不適定問題與正則化

問題的適定性最早由法國數(shù)學家Hadamard[11]指出問題的解存在且唯一。不適定性通常包含兩重含義：問題解的多重性和問題對擾動的敏感性。在很長一段時間內(nèi)，人們認為研究不適定問題沒有意義。直到1956年，人們逐漸發(fā)現(xiàn)適定問題并不能正確描述許多自然現(xiàn)象，許多現(xiàn)象均具有不適定性。至此，不適定問題的研究才引起相關學者的重視。

目前，對于不適定問題，已有PST、GPST、Monte Carlo、最佳攝動量、正則化等方法。其中，正則化是求解不適定問題的主要方法。不適定問題的正則化最早由前蘇聯(lián)數(shù)學家吉洪諾夫提出，其基本思想是：將所研究問題的解和相應空間加以適當限制，以保證當原始數(shù)據(jù)有缺損或擾動時，問題的近似解與真解具有較高的近似度。由于這種方法是通過對原問題附加“規(guī)則”，從而保證解的存在性和數(shù)值穩(wěn)定性，因而稱之為“正則化”方法。

2.2 低秩矩陣分解

大部分圖像中都含有一些公共模式，這些基本模式稱為基底或字典。通過這些基底的線性組合，可以表示出幾乎所有的圖像。在許多情況下，基底的數(shù)量是較少的，即許多圖像的數(shù)據(jù)矩陣是低秩或近似低秩的。因為低秩矩陣可以被映射到低維空間進行分析，這就給圖像處理帶來了極大便利。

但在有些情況下，由于數(shù)據(jù)缺損及噪聲影響，破壞了矩陣的低秩性。因為噪聲往往是分布稀疏的，為了恢復矩陣的低秩性，可將略低數(shù)據(jù)矩陣D分解為兩個矩陣A與E之和，其中第一個矩陣A低秩，第二個矩陣E稀疏。具體分解模型如下[13]：

3 數(shù)值實驗

為了檢驗正則化低秩子空間譜聚類算法的性能，本文選取了兩組典型的譜聚類仿真數(shù)據(jù)和兩個人在不同光照下的共20幅人臉圖像進行實驗。

圖1是視覺重建中的問題。特征提取是視覺重建的一個關鍵環(huán)節(jié)，圖1中的十字的位置信息已經(jīng)提取出來，為了確定十字的中心位置，要求將十字中的點按照 “橫”和“豎”分為兩類。

圖2為一個平面和兩條直線，這是一個不滿足獨立子空間的關系的例子，數(shù)據(jù)聚類有一定難度。從圖2中還可以看出，原始數(shù)據(jù)有缺損，這在一定程度上要求聚類算法要有較強的缺損數(shù)據(jù)處理能力。

兩個人在不同光照下的人臉圖像共20幅，數(shù)據(jù)中每一列為一幅人臉圖像，要求將這20幅圖像分成兩類。這是典型的圖像低秩分解問題。譜聚類結果如下：

圖3顯示，十字線的聚類效果很好；圖4顯示，一平面二直線的聚類效果也較好，基本上將平面與兩直線區(qū)分開來；圖5顯示，人臉圖像被明顯的分為兩類，但第一行第三個圖像和第五行第五個圖像的識別結果出現(xiàn)了錯誤，這表明正則化低秩子空間譜聚類算法可能還存在某種不足，需要進一步改進。

4 結語

低秩子空間譜聚類算法適宜于缺損數(shù)據(jù)的聚類問題，但此算法可能出現(xiàn)不適定性。為此，本文提出用正則化方法解決不適定性。數(shù)值實驗表明，這種算法在一定程度上可以解決缺損數(shù)據(jù)的譜聚類問題，抑制噪聲，獲得質量較高的聚類結果。

需指出的是，目前譜聚類的理論尚不成熟，許多算法性能的評價只能依賴于數(shù)據(jù)仿真。本文提出的算法雖可以解決低秩子空間譜聚類算法的不適定問題，但與經(jīng)典的譜聚類算法相比，具有較高的復雜度，且對于復雜的圖像分類問題效果有時欠佳，需要進一步深入研究。

參考文獻：

[1] JAIN A，MURTY M，F(xiàn)LYNN P.Data clustering：a review[J].ACM Computing Surveys，1999，31（3）：264-323.

[2] LUXBRUG U.A tutorial on spectral clustering[J].Statistics and Computing，2007，17（4）：395-416.

[3] VERMA D，MEILA M.A comparison of spectral clustering algorithm[R].Washington：University of Washington，2003.

[4] NG A，JORDAN M，WEISS Y.On spectral clustering：analysis and an algorithm[C].Advances in Neural Information Processing Systems，Cambridge：MIT Press，2001：849-856.

[5] BACH F，JORDAN M.Learning spectral clustering[C].Advances in Neural Information Processing Systems，Cambridge：MIT Press，2004：1-13.

[6] MEILA M，XU L.Multiway cuts and spectral clustering[R].Washington：University of Washington，2003.

[7] VIDAL R.Subspace clustering[J].IEEE Signal Processing Magazine，2011，28（2）：52-68.

[8] WANF Y，JIANG Y，WU Y，et al.Spectral clustering on multiple manifolds[J].IEEE Transactions on Neural Networks，2011，22（7）：1149-1161.

[9] CHENG B，LIU G，WANG J，et al.Multi-task low rank affinity pursuit for image segmentation[J].ICCV，2011（10）：57-61.

[10] ELHAMIFAR E，VIDAL R.Sparse subspace clustering：algorithm，theory and applications[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35（11）：2765-2781.

[11] 劉繼軍.不適定問題的正則化方法及應用[M].北京：科學出版社，2005.

[12] 李宏偉.求解不適定問題的正則化方法[D].哈爾濱：哈爾濱理工大學，2011.

[13] 趙科科.低秩矩陣分解的正則化方法與應用[D].杭州：浙江大學，2012.

[14] 何家玉，許峰.基于特征向量自動選取的譜聚類算法[J].軟件導刊，2016，15（8）：23-25.

（責任編輯：陳福時）