王雨思，路德楊，李海洋

1.西安工程大學(xué) 理學(xué)院，西安710048

2.廣州大學(xué) 人事處，廣州510006

3.廣州大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，廣州510006

1 引言

聚類分析作為數(shù)據(jù)挖掘和模式識(shí)別等領(lǐng)域的重要工具，一直得到廣泛的應(yīng)用。但是，隨著信息時(shí)代的來臨，高維數(shù)據(jù)變得越來越普遍。在處理高維數(shù)據(jù)時(shí)，傳統(tǒng)聚類方法，如k-means[1]等，表現(xiàn)出兩方面不足。一方面，這些方法通常采用距離作為相似性度量來進(jìn)行聚類，而高維空間中的數(shù)據(jù)較低維空間中的數(shù)據(jù)分布要稀疏，且數(shù)據(jù)間距離處處相等是非常普遍的現(xiàn)象；另一方面，高維數(shù)據(jù)集中存在大量的無關(guān)屬性，這些無關(guān)屬性使得在數(shù)據(jù)集中存在簇的可能性幾乎為零。研究表明，高維數(shù)據(jù)往往存在于低維流形結(jié)構(gòu)中，而不是均勻的分布在任意空間，且它們的本質(zhì)維數(shù)比其真實(shí)的維數(shù)要低得多[2]。如含有數(shù)百萬幀的影像資料，剛性運(yùn)動(dòng)物體的軌跡特征[3]，不同光照條件下的人臉圖像[4]等都位于低維聯(lián)合子空間中。因此，子空間聚類應(yīng)運(yùn)而生[5]。

子空間聚類作為高維數(shù)據(jù)聚類的一種新方法成為當(dāng)前的研究熱點(diǎn)。常用的子空間聚類主要分為以下4類：迭代方法、代數(shù)方法、統(tǒng)計(jì)方法和基于譜聚類的方法[6]。目前，基于譜聚類的子空間聚類方法在眾多算法中是比較成功的。它首先通過搜索數(shù)據(jù)點(diǎn)之間的關(guān)系，利用相似性構(gòu)建親和矩陣（Affinity Matrix）；然后基于圖論的原理利用譜聚類方法對(duì)親和矩陣進(jìn)行聚類；最后得到聚類結(jié)果[7]?；谧V聚類的子空間聚類方法的關(guān)鍵是如何更好的構(gòu)建數(shù)據(jù)點(diǎn)之間的關(guān)系，使得親和矩陣能夠更有效的表示數(shù)據(jù)間的相似性，這對(duì)聚類效果的影響至關(guān)重要。當(dāng)前構(gòu)建親和矩陣的方法主要有ε-鄰近法、k 鄰近法和全連接法等，其中全連接法選擇使用高斯核函數(shù)RBF 或Sigmoid 核函數(shù)來刻畫數(shù)據(jù)點(diǎn)之間的關(guān)系，是目前應(yīng)用中最普遍的方法。

針對(duì)如何有效的建立親和矩陣的問題，基于高維數(shù)據(jù)的自表征特性，即每個(gè)依存于子空間并上的數(shù)據(jù)點(diǎn)都能被數(shù)據(jù)集中其他數(shù)據(jù)點(diǎn)的組合所表示，Elhamifar 和Vidal 在文獻(xiàn)[8]中提出了稀疏子空間聚類算法（Sparse Subspace Clustering，SSC）[9-10]。文獻(xiàn)[11]提出了基于低秩表示的子空間聚類方法（Low Rank Representation，LRR）[12-13]，與其他較好的子空間聚類算法相較，基于稀疏和低秩表示的方法不需要先驗(yàn)條件可以直接處理噪聲和異常點(diǎn)。文獻(xiàn)[14]結(jié)合稀疏性與低秩性提出了多子空間表示（Multi-Space Representation，MSR）模型。文獻(xiàn)[15]同時(shí)對(duì)系數(shù)矩陣進(jìn)行稀疏和低秩正則項(xiàng)約束，提出了LRSSC（Low-Rank Sparse Subspace Clustering）模型。文獻(xiàn)[16]結(jié)合稀疏表示的局部性和流行學(xué)習(xí)思想，提出了局部子空間聚類（Local Subspace Clustering，LSC）方法。雖然上述一系列的模型和算法很大程度的提高了子空間聚類的性能，但遺憾的是，上述這些方法皆采用矩陣的核范數(shù)或向量的1-范數(shù)對(duì)親和矩陣和稀疏隨機(jī)噪聲進(jìn)行約束。然而核范數(shù)或1-范數(shù)約束得到的最優(yōu)解往往不夠稀疏，不能準(zhǔn)確反應(yīng)高維空間中數(shù)據(jù)分布的稀疏性以及稀疏隨機(jī)噪聲的位置和大小，對(duì)聚類結(jié)果產(chǎn)生了不利影響。

鑒于分式函數(shù)良好的稀疏性，本文主要把分式函數(shù)應(yīng)用于子空間聚類，研究內(nèi)容如下：（1）在稀疏子空間聚類模型中以分式函數(shù)作為目標(biāo)函數(shù)代替0-范數(shù)，并證明了該模型所求的稀疏系數(shù)矩陣具有塊對(duì)角結(jié)構(gòu)，能夠更好地揭示出數(shù)據(jù)的子空間結(jié)構(gòu)。（2）本文針對(duì)含噪聲情況，將含噪數(shù)據(jù)分解為干凈數(shù)據(jù)、高斯噪聲和異常點(diǎn)噪聲，并對(duì)異常點(diǎn)噪聲仍舊采用分式函數(shù)約束作為正則項(xiàng)，提高模型的魯棒性。（3）利用交替方向迭代方法（alternating direction iteration method）[18]對(duì)模型進(jìn)行求解，得到稀疏系數(shù)矩陣，進(jìn)而求出相似性矩陣，最后將相似性矩陣應(yīng)用于經(jīng)典的譜聚類方法進(jìn)行聚類。本文結(jié)構(gòu)圖如圖1所示。

圖1 文章結(jié)構(gòu)圖

2 相關(guān)知識(shí)

2.1 子空間聚類

定義1（子空間聚類Subspace Clustering）給定位于n 個(gè)聯(lián)合線性子空間并上的N 個(gè)無噪聲數(shù)據(jù)點(diǎn)，子空間相互獨(dú)立，子空間Si對(duì)應(yīng)的維數(shù)為di，定義數(shù)據(jù)矩陣X：

其中Xi∈RD×Ni是一個(gè)秩為di(N ＞di)的矩陣，表示第i個(gè)子空間數(shù)據(jù)點(diǎn)組成的矩陣；Γ 為未知置換矩陣。子空間聚類的目的是求解子空間的個(gè)數(shù)n 以及它們對(duì)應(yīng)的維數(shù)di，同時(shí)將數(shù)據(jù)點(diǎn)xi分割到原本對(duì)應(yīng)的子空間中，理想情況下每一類對(duì)應(yīng)一個(gè)子空間。

為了解決子空間聚類問題，基于數(shù)據(jù)的自表征特性，Elhamifar 和Vidal 提出稀疏子空間聚類（SSC）算法。該算法運(yùn)用理想情況下，數(shù)據(jù)點(diǎn)的稀疏表示中的非零元素對(duì)應(yīng)于來自相同子空間的數(shù)據(jù)點(diǎn)這一特性，通過一個(gè)稀疏優(yōu)化框架，獲得不同子空間的數(shù)據(jù)劃分，再根據(jù)這一信息使用譜聚類框架獲取聚類結(jié)果。SSC 的基本思想是將矩陣X 表示成字典矩陣D 下的線性組合，即X=DC，同時(shí)希望線性組合的系數(shù)矩陣C 是最稀疏的，SSC的基本模型如下：

由于0-范數(shù)的最小化求解是一個(gè)NP-hard 問題，故一定條件下，上述0-范數(shù)優(yōu)化問題等價(jià)于下式所示的凸1-范數(shù)優(yōu)化問題：

2.2 分式函數(shù)及其主要特性

本文考慮利用分式函數(shù)逼近0-范數(shù)來提高模型的稀疏性。以下給出分式函數(shù)的定義及其主要性質(zhì)。

定義2[17]（分式函數(shù)）對(duì)于任意的t ∈?，定義分式函數(shù)pb(t)為：

其中參數(shù)b ∈( 0,+ ∞)。

在分式函數(shù)中：當(dāng)t=0 時(shí)，pb(0)=0；當(dāng)t0 且參數(shù)b →+∞時(shí)，pb(t)→1，可見隨著參數(shù)b 的增大它能夠逼近0-范數(shù)。圖2 給出在不同參數(shù)下的分式函數(shù)圖像。

圖2 不同參數(shù)下的分式函數(shù)圖像

因此分式函數(shù)pb(| t|)可以近似逼近0-范數(shù)，即

2.3 分式迭代閾值算法

在求解0-范數(shù)優(yōu)化問題中，迭代閾值算法作為一種成功的方法被廣泛應(yīng)用在壓縮感知中。其中迭代硬閾值算法（Iterative Hard Thresholding，IHT）[19]主要是將0-范數(shù)優(yōu)化問題轉(zhuǎn)化為求解無約束0-范數(shù)優(yōu)化，迭代硬閾值算法的迭代格式為：

其中：

迭代軟閾值算法（Iterative Soft Thresholding）[20]主要求解無約束的1-范數(shù)優(yōu)化問題，其迭代格式如下：

其中：

分式迭代閾值算法在文獻(xiàn)[17]被提出并應(yīng)用于壓縮感知中，表現(xiàn)出良好的性能，其迭代格式通過定理1給出。

其中：

故X*的第i 列為：

其中參數(shù)t 滿足：

3 基于分式函數(shù)約束的稀疏子空間聚類模型

本章提出基于分式函數(shù)約束的稀疏子空間聚類模型（Fraction function Penalty Sparse Subspace Clustering，F(xiàn)PSSC），相較于經(jīng)典的凸1-范數(shù)約束的稀疏子空間聚類模型，F(xiàn)PSSC能獲得比凸1-范數(shù)約束稀疏性更好的系數(shù)矩陣。

3.1 構(gòu)建模型

分式函數(shù)可以逼近0-范數(shù)且較凸1-范數(shù)逼近獲得的系數(shù)矩陣更加稀疏，同時(shí)較0-范數(shù)易于求解。因此本文用分式函數(shù)替代不連續(xù)的0-范數(shù)，將0-范數(shù)約束問題：

轉(zhuǎn)化為如下基于分式函數(shù)的約束問題：

通常情況下，SSC目標(biāo)函數(shù)的目的是保證子空間中數(shù)據(jù)點(diǎn)的表示系數(shù)矩陣具有良好的有利于子空間聚類的結(jié)構(gòu)，即具有塊對(duì)角結(jié)構(gòu)[21]。文獻(xiàn)[22]在假設(shè)數(shù)據(jù)無噪聲干擾、子空間相互獨(dú)立的情況下，提出強(qiáng)制塊對(duì)角（Enhance Block Diagonal，EBD）條件。該強(qiáng)制塊對(duì)角條件能夠保證子空間表示系數(shù)矩陣，即所求模型的最優(yōu)解具有塊對(duì)角結(jié)構(gòu)。下面證明本文構(gòu)建的模型（12）在求解過程中獲取的系數(shù)矩陣C 具有塊對(duì)角結(jié)構(gòu)。

強(qiáng)制塊對(duì)角條件（Enforced Block Diagonal conditions，EBD）：函數(shù)f 是一個(gè)定義在上的矩陣集。對(duì)于任意其中A和D是方陣，B 和C 是任意維數(shù)的兼容矩陣。令則有強(qiáng)制塊對(duì)角條件：

（1）對(duì)任意置換矩陣P，ZP ∈Ω，有f( Z )=f( ZP)。

（2）f( Z )≥f( ZD)，當(dāng)且僅當(dāng)B=C=0（或Z=ZD）時(shí)等式成立。

（3）f( ZD)=f( A)+f( D)。

引理1[22]假設(shè)數(shù)據(jù)樣本充分且子空間相互獨(dú)立，若函數(shù)f 滿足EBD條件（1）、（2）、（3），則模型：

的最優(yōu)解Z*一定是塊對(duì)角結(jié)構(gòu)：

定理2假設(shè)數(shù)據(jù)樣本充分，且子空間相互獨(dú)立，定義矩陣分式函數(shù)：

證明由引理1 可知，只需驗(yàn)證分式函數(shù)滿足EBD條件（1）、（2）、（3）即可。事實(shí)上，由模型（12）中Pb(C)的定義易證EBD條件（1）、（2）、（3）都成立。

在實(shí)際問題中，待聚類數(shù)據(jù)集中通常含有異常點(diǎn)和高斯噪聲。考慮令第i 個(gè)數(shù)據(jù)樣本點(diǎn)：

將式（15）代入式（14）有：

則數(shù)據(jù)樣本點(diǎn)在被噪聲和異常點(diǎn)干擾情況下可表示為：

即：

寫成矩陣的形式為：

其中E、G 的每一列向量ei、gi被定義為：

因此，考慮到噪音的情形，對(duì)模型（12）進(jìn)行優(yōu)化，可變?yōu)椋?/p>

3.2 模型求解

本節(jié)對(duì)基于分式函數(shù)約束的稀疏子空間聚類模型式（22）進(jìn)行求解。首先，利用正則化方法，模型（22）可寫為：

然后，利用交替方向迭代算法對(duì)式（23）進(jìn)行求解。先將問題轉(zhuǎn)換為以下兩個(gè)子問題（24）和（26），再利用FP迭代閾值算法對(duì)式（24）、（26）進(jìn)行求解如下所示。

固定Gk，對(duì)C 求極?。?/p>

再令

固定Ck+1，對(duì)G 求極?。?/p>

式（24）求解，該式可以轉(zhuǎn)化成標(biāo)量最小化問題，應(yīng)用定理1給出的分式迭代閾值算法的迭代格式，將變量代入迭代格式中即可求得。

式（26）求解，可知該式存在閉合解為：

其中，Ω 為分式函數(shù)約束最小化運(yùn)算符，則G 可通過FP迭代閾值算法獲得，和式（24）求解方法一致，由定理1中的FP閾值迭代格式可求出。

綜上所述，通過交替方向迭代算法求解FPSSC模型進(jìn)行聚類時(shí)，首先利用更新規(guī)則得到最優(yōu)解，然后構(gòu)建親和矩陣，最后應(yīng)用譜聚類來得到聚類結(jié)果。具體實(shí)現(xiàn)過程如算法1所示。

算法1FPSSC算法

輸入：數(shù)據(jù)點(diǎn)矩陣X=[x1,x2,…,xN]，參數(shù)λe、λg。

初始化：Ck=Gk=0，μ=10-6，ρ=1.1，ε=10-8。

1.通過式（24）、（25）、（26）分別對(duì)變量Ck、Gk進(jìn)行更新

2.更新參數(shù)：μk+1=min{ρ μk,μmax}

4.獲得最優(yōu)化問題的解(C*,G*)

6.譜聚類

輸出：每個(gè)數(shù)據(jù)點(diǎn)的聚類結(jié)果。

3.3 算法收斂性分析

本節(jié)中，討論FPSSC算法的收斂性。本文利用交替方向迭代方法對(duì)模型（22）進(jìn)行求解，由于Pb( C )和Pb( G )都是非凸函數(shù)，因此不能從理論上保證上述算法的收斂性。但是，本文進(jìn)行了大量實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果顯示，實(shí)際應(yīng)用中的FPSSC 在最優(yōu)化問題的求解中通常都能很好地收斂。

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

將本文提出的FPSSC 算法與當(dāng)下比較流行的幾個(gè)基于譜聚類的子空間聚類算法進(jìn)行實(shí)驗(yàn)比較，選擇人工數(shù)據(jù)集、Extended Yale B人臉數(shù)據(jù)庫、Hopkins155運(yùn)動(dòng)分割數(shù)據(jù)集這3 個(gè)流行的標(biāo)準(zhǔn)數(shù)據(jù)庫進(jìn)行對(duì)比實(shí)驗(yàn)。上述數(shù)據(jù)庫的部分樣本圖像如圖3 所示。在人工合成數(shù)據(jù)集上，本文用算法分割的精確度衡量其性能的優(yōu)劣；在Extended Yale B 人臉數(shù)據(jù)庫和Hopkins155 運(yùn)動(dòng)分割數(shù)據(jù)集上，采用子空間聚類錯(cuò)誤率衡量其性能的優(yōu)劣，其中定義：

圖3 數(shù)據(jù)庫的部分樣本圖像

可見，子空間聚類錯(cuò)誤率越小，其聚類結(jié)果越好，算法性能越優(yōu)。本文實(shí)驗(yàn)環(huán)境為Microsoft Windows 10，采用Inter?Core?i5-3230M CPU@2.60 GHz處理器，4 GB內(nèi)存的聯(lián)想G500筆記本電腦。

4.1 人工數(shù)據(jù)集

本文構(gòu)建一個(gè)人工數(shù)據(jù)集用來比較不同子空間聚類算法的性能。依據(jù)類似于文獻(xiàn)[23]和[24]的方法，創(chuàng)建5 個(gè)相互獨(dú)立的子空間Si?R200(i=1,2,3,4,5)，子空間的基能夠利用Ui+1=TUi,1 ≤i ≤4 得到，其中T 是一個(gè)隨機(jī)矩陣，U1是一個(gè)100×4 維數(shù)的隨機(jī)正交矩陣。故每個(gè)子空間的維數(shù)是4，外圍空間的維數(shù)是100。首先，通過Xi=UiQi，1 ≤i ≤5 從每個(gè)子空間中選取20個(gè)100維的數(shù)據(jù)點(diǎn)向量，這里Qi是一個(gè)4×20的隨機(jī)矩陣且矩陣內(nèi)每個(gè)元素皆在（0，1）之間均勻分布，故可以得到5 個(gè)子空間樣本為20×100 的數(shù)據(jù)點(diǎn)矩陣X=[X1X2X3X4X5]。然后，在數(shù)據(jù)點(diǎn)矩陣中隨機(jī)選取20%的數(shù)據(jù)點(diǎn)向量加入高斯噪聲，這里的高斯噪聲分布服從均值為0，方差為0.3‖ x‖（‖ x ‖表示選取的數(shù)據(jù)點(diǎn)向量）。最后，應(yīng)用譜算法把數(shù)據(jù)點(diǎn)分成5 類同時(shí)比較每類方法分割的準(zhǔn)確率。由于該人工數(shù)據(jù)集上僅加入了高斯噪聲，故在此實(shí)驗(yàn)中取參數(shù)λg=0。

在本數(shù)據(jù)集上，將所提出的FPSSC 算法與經(jīng)典的SSC、SR2,1、SR1和LRR 子空間聚類算法進(jìn)行對(duì)比實(shí)驗(yàn)，其中SR2,1模型和SR1模型分別為：

表1 不同算法中系數(shù)矩陣的稀疏度

圖4 不同算法在人工數(shù)據(jù)集上的分割精確度

圖4 為各算法在該人工數(shù)據(jù)集上的運(yùn)行結(jié)果。通過綜合比較，可以看出本文的FPSSC對(duì)數(shù)據(jù)的分割精確度高于其他幾種算法，表現(xiàn)出良好的性能。親和矩陣可以影響算法性能的優(yōu)劣，SSC、LRR、SR1和SR2,1同本文算法一致，都是先求取親和矩陣，然后將親和矩陣用于NCuts的譜聚類算法進(jìn)行數(shù)據(jù)聚類。結(jié)合表1和圖4可知，由于SSC、SR1和SR2,1皆是用1-范數(shù)作為目標(biāo)函數(shù)，故獲得的系數(shù)矩陣不夠稀疏。然而本文的FPSSC用分式函數(shù)作為目標(biāo)約束，通過調(diào)節(jié)分式函數(shù)中的參數(shù)b使得系數(shù)矩陣的稀疏度低于其他幾種算法，獲得了更好的稀疏性。另一方面，各算法在噪聲的處理上有所不同，本文在處理噪聲時(shí)使用Forbenius范數(shù)進(jìn)行約束，表現(xiàn)出對(duì)高斯噪聲較好的魯棒性。可以看到隨著噪聲比率的增加，各算法的分割精確度都在下降，SSC和SR2,1精確度下降較緩慢，但是都低于FPSSC 的精確度，可見FPSSC受噪聲影響較小，魯棒性更好。SR1使用1-范數(shù)進(jìn)行噪聲約束，當(dāng)噪聲比率高于60%時(shí)其精確度相對(duì)穩(wěn)定且高于SSC 和SR2,1，但FPSSC 的精確度仍然高于SR1算法?？梢?，本文的FPSSC算法通過調(diào)節(jié)分式函數(shù)的參數(shù)b 提高了模型的稀疏性，且在處理噪聲時(shí)使用Forbenius范數(shù)對(duì)噪聲進(jìn)行有效約束，提高了模型的魯棒性，使FPSSC表現(xiàn)出良好的性能。

4.2 Extended Yale B人臉數(shù)據(jù)庫

Extended Yale B人臉數(shù)據(jù)庫是用于測試子空間聚類算法的標(biāo)準(zhǔn)數(shù)據(jù)庫，本文將所提算法應(yīng)用到該數(shù)據(jù)庫檢驗(yàn)FPSSC的有效性。Extended Yale B人臉數(shù)據(jù)庫采樣了38 類灰度大小為192×168 的人臉，每類含有64 張?zhí)幱诓煌庹障碌娜四槇D像，本文將圖像灰度轉(zhuǎn)化為48×42 并使用2 016 維矢量化的圖像作為一個(gè)數(shù)據(jù)樣本。結(jié)合文獻(xiàn)[25]，本文將38類目標(biāo)圖像依次分為如下4 組：1～10、11～20、21～30 和31～38，其中前3 組中的每一組，本文實(shí)驗(yàn)采用所有可以選擇的2、3、5、8、10個(gè)類別，對(duì)于第4 組，本文使用所有可選的2、3、5、8 個(gè)類別進(jìn)行重復(fù)實(shí)驗(yàn)。為了驗(yàn)證本文算法的有效性，實(shí)驗(yàn)過程中將結(jié)果與當(dāng)前性能較好的SCC[26]、LSA（Local Subspace Affinity）[27]、LRSC[28]、LRR、SSC 進(jìn)行比較，實(shí)驗(yàn)結(jié)果如表2 所示，其結(jié)果中給出不同算法在取不同類別時(shí)，在Extend Yale B數(shù)據(jù)庫進(jìn)行重復(fù)實(shí)驗(yàn)過程中聚類錯(cuò)誤率的平均數(shù)和中位數(shù)。

由表2 可知，在不同的聚類類別下，F(xiàn)PSSC 聚類結(jié)果的錯(cuò)誤率要低于其他幾種算法，具有更好的性能。在該人臉數(shù)據(jù)庫上，SCC和LSA通過搜索數(shù)據(jù)點(diǎn)的全局和局部結(jié)構(gòu)構(gòu)建親和矩陣，其模型自身具有局限性，導(dǎo)致它們聚類錯(cuò)誤率偏高，表現(xiàn)出最差的性能。觀察到SSC和LRR作為經(jīng)典的基于稀疏表示和低秩表示的子空間聚類算法，其能夠獲得比LRSC算法相較更低的聚類錯(cuò)誤率，而且隨著聚類類別數(shù)的增加，SSC 表現(xiàn)出比LRR更優(yōu)秀的性能。然而，本文所提的FPSSC算法，由于獲得更為稀疏的系數(shù)矩陣并對(duì)兩個(gè)噪聲項(xiàng)進(jìn)行了有效約束，所以在聚類類別不同的情況下，平均聚類錯(cuò)誤率均低于SSC和LRR算法，且在類別數(shù)逐漸增大時(shí)，要明顯低于其他算法的聚類錯(cuò)誤率。故FPSSC 提高了聚類結(jié)果的準(zhǔn)確性和穩(wěn)定性，算法性能優(yōu)于其他幾種算法。

表2 不同算法在Extended Yale B人臉數(shù)據(jù)庫上的聚類錯(cuò)誤率%

4.3 Hopkins155運(yùn)動(dòng)分割數(shù)據(jù)集

Hopkins155 數(shù)據(jù)集是一個(gè)具有代表性的標(biāo)準(zhǔn)視頻數(shù)據(jù)集，廣泛地應(yīng)用于聚類實(shí)驗(yàn)中。運(yùn)動(dòng)分割是指根據(jù)場景中的不同運(yùn)動(dòng)對(duì)一個(gè)包含多個(gè)運(yùn)動(dòng)物體的視頻序列進(jìn)行分割。對(duì)視頻中每一幀的N 個(gè)特征數(shù)據(jù)點(diǎn)進(jìn)行提取和跟蹤，特征數(shù)據(jù)點(diǎn)堆疊獲得的一個(gè)2F 維向量（F為視頻的總幀數(shù)）對(duì)應(yīng)特征軌跡，因此，運(yùn)動(dòng)分割就是根據(jù)其基本的運(yùn)動(dòng)分離這些運(yùn)動(dòng)軌跡的問題。本文實(shí)驗(yàn)采用的Hopkins155 運(yùn)動(dòng)分割數(shù)據(jù)集中包含155 個(gè)視頻序列，其中122 個(gè)視頻序列含有2 個(gè)運(yùn)動(dòng)，每個(gè)序列30幀，具有266個(gè)特征軌跡；35個(gè)視頻序列含有3個(gè)運(yùn)動(dòng)，每個(gè)序列29幀，具有398個(gè)特征軌跡。每個(gè)視頻幀的子空間低于三維。參照文獻(xiàn)[29]的實(shí)驗(yàn)設(shè)置，本文首先應(yīng)用主成分分析算法對(duì)運(yùn)動(dòng)軌跡進(jìn)行有效降維，將運(yùn)動(dòng)軌跡從2F 維降到4n（n 為子空間的數(shù)量）維，然后分別將子空間聚類算法應(yīng)用于該數(shù)據(jù)集中執(zhí)行算法程序，結(jié)果中表3 是2F 維數(shù)據(jù)點(diǎn)下聚類錯(cuò)誤率的均值和中位數(shù)，表4是4n 維數(shù)據(jù)點(diǎn)下聚類錯(cuò)誤率的均值和中位數(shù)。

表3 不同算法在Hopkins155運(yùn)動(dòng)分割數(shù)據(jù)集2F維數(shù)據(jù)點(diǎn)下的聚類錯(cuò)誤率%

表4 不同算法在Hopkins155運(yùn)動(dòng)分割數(shù)據(jù)集4n維數(shù)據(jù)點(diǎn)下的聚類錯(cuò)誤率%

表3和表4分別為運(yùn)動(dòng)軌跡在2F 維和4n 維下的聚類結(jié)果。分析表中的聚類結(jié)果可以看出，F(xiàn)PSSC 在4n維數(shù)據(jù)點(diǎn)下的聚類錯(cuò)誤率低于其他幾種算法，具有較優(yōu)的聚類結(jié)果；在2F 維數(shù)據(jù)點(diǎn)下，由于該數(shù)據(jù)集中類別為2或3，相比其他數(shù)據(jù)集類別較少，因此在分式函數(shù)的約束下，稀疏性在一定程度上會(huì)加重?cái)?shù)據(jù)的局部性，導(dǎo)致在維數(shù)較大的情況下，本文算法與SSC 的性能相差無幾，算法性能沒有表現(xiàn)出明顯的優(yōu)勢。但是值得注意的是，相較于SCC、LSA、LRR和LRSC，F(xiàn)PSSC算法表現(xiàn)出了很好的性能，而且在2 個(gè)運(yùn)動(dòng)時(shí)，雖然FPSSC 的聚類錯(cuò)誤率相較SSC略高，但是隨著聚類類別數(shù)增加到3個(gè)運(yùn)動(dòng)時(shí)，F(xiàn)PSSC 的聚類錯(cuò)誤率卻要明顯低于SSC，說明隨著類別數(shù)的增加，F(xiàn)PSSC 能夠獲得較低的聚類錯(cuò)誤率。綜上所述，本文的FPSSC算法能夠有效的捕獲數(shù)據(jù)的結(jié)構(gòu)信息，在實(shí)際應(yīng)用中獲得較優(yōu)的聚類結(jié)果。

4.4 參數(shù)選擇

本節(jié)分析參數(shù)選擇對(duì)FPSSC 算法性能的影響。具體地，影響FPSSC 算法性能的參數(shù)主要包含3 個(gè)：調(diào)節(jié)分式函數(shù)的參數(shù)b、平衡噪聲項(xiàng)的參數(shù)λe和λg。本文利用交叉驗(yàn)證方法對(duì)參數(shù)進(jìn)行選擇，分別在Extended Yale B 人臉數(shù)據(jù)庫類別為10、Hopkins155 運(yùn)動(dòng)分割數(shù)據(jù)集類別為3 的情況下進(jìn)行實(shí)驗(yàn)。其中參數(shù)b={10,20,30,40,50,60,70,80,90,100}，λg={10-4,10-3,10-2,10-1,100,101,102}，λe={0,0.02,0.04,0.06,0.08,0.10,0.12}，通過搜索不同參數(shù)值對(duì)算法性能的影響進(jìn)行評(píng)價(jià)。圖5表明參數(shù)b 取值在70～90范圍變化時(shí)，算法的聚類錯(cuò)誤率較低，算法相對(duì)穩(wěn)定。圖6和圖7分別表明參數(shù)λe和λg變化時(shí)對(duì)聚類錯(cuò)誤率的影響，因所選數(shù)據(jù)庫受噪聲影響程度不同，故平衡參數(shù)λe和λg的最優(yōu)取值也不同。

圖5 參數(shù)b 對(duì)聚類錯(cuò)誤率的影響

圖6 參數(shù)λe 對(duì)聚類錯(cuò)誤率的影響

圖7 參數(shù)λg 對(duì)聚類錯(cuò)誤率的影響

綜上所述，基于分式函數(shù)約束的稀疏子空間聚類方法在人工數(shù)據(jù)集、Extended Yale B數(shù)據(jù)庫和Hopkins155數(shù)據(jù)集上表現(xiàn)出良好的性能?？梢钥吹?，相較其他的子空間聚類算法，由于分式函數(shù)能夠逼近0-范數(shù)，具有良好的稀疏性，采用分式函數(shù)進(jìn)行約束能夠準(zhǔn)確地刻畫高維數(shù)據(jù)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，因此該方法在子空間聚類中取得了更好的聚類結(jié)果。

5 結(jié)束語

本文提出一種基于分式函數(shù)約束的稀疏子空間聚類算法。不同于經(jīng)典的SSC算法，F(xiàn)PSSC使用分式函數(shù)替代0-范數(shù)作為目標(biāo)函數(shù)以提高系數(shù)矩陣的稀疏性，并證明了分式函數(shù)獲取的系數(shù)矩陣具有塊對(duì)角結(jié)構(gòu)，能夠有效地表現(xiàn)出數(shù)據(jù)點(diǎn)之間的關(guān)系，準(zhǔn)確捕獲數(shù)據(jù)的子空間結(jié)構(gòu)。同時(shí)，針對(duì)含噪聲的情況，對(duì)異常點(diǎn)噪聲同樣使用分式函數(shù)約束作為正則項(xiàng)，增加模型的穩(wěn)定性。再運(yùn)用交替方向迭代方法對(duì)模型進(jìn)行求解，構(gòu)建親和矩陣，最后使用譜聚類算法進(jìn)行聚類。在3個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文提出的FPSSC算法在系數(shù)矩陣稀疏性和聚類準(zhǔn)確率上均表現(xiàn)出較好的性能，算法更加有效。下一步的研究重點(diǎn)，將對(duì)復(fù)雜含噪數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)進(jìn)行研究，給出其成功恢復(fù)下的理論保證。