付剛　吳觀茂

摘要：文章提出了一種迭代加權(quán)的稀疏子空間的聚類算法。通過在數(shù)據(jù)集的實(shí)驗(yàn)，發(fā)現(xiàn)迭代加權(quán)稀疏子空間聚類算法極大降低了稀疏子空間的聚類算法的錯(cuò)誤率，但并不增加算法的計(jì)算復(fù)雜度。

關(guān)鍵詞：迭代；稀疏子空間；聚類

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）28-0030-02

1 子空間聚類

在這一節(jié)中，文章簡要介紹下稀疏子空間聚類算法。在1.2節(jié)中文章介紹加權(quán)[?1] 最小化框架、所要解決的問題以及解決問題的算法。

1.1 稀疏子空間聚類

在這一節(jié)中，文章簡要介紹SSC算法。該種算法采用稀疏表示方式，構(gòu)建了相似圖或多個(gè)子空間中數(shù)據(jù)點(diǎn)集聚類的親和矩陣。

考慮一系列點(diǎn)[Y=[y1，y2，…，yn]]，其中[yi∈?m]，[yi]為原始空間的低維子空間中的第[i]個(gè)數(shù)據(jù)點(diǎn)。SSC算法在這些數(shù)據(jù)點(diǎn)中尋求自身相似性，這需要通過解決下面的最優(yōu)化問題：

[minC1 s.t. Y=YC，diag（C）=0] （1）

其中，[C∈?n×n]是數(shù)據(jù)點(diǎn)集[Y]的稀疏表示矩陣。那么，該稀疏表示矩陣[C]用來把高維空間分割成多個(gè)低維子空間。

在SSC算法中，后置處理步驟就是子空間聚類。

SSC是通過解決下面[?1]最小化問題：

[min（C，E，Z） C1+λeE1+λz2Z2F s.t. Y=YC+E+Z，1TC=1T， diag（C）=0.] （2）

其中，變量矩陣[E]表示數(shù)據(jù)的稀疏外圍，變量矩陣[Z]表示數(shù)據(jù)的噪聲或誤用。

參數(shù)[λe>0]和[λz>0]在目標(biāo)函數(shù)中起著平衡作用。注意到最優(yōu)目標(biāo)函數(shù)（2）是凸優(yōu)化變量，因此，可以使用凸程序工具（具體參考[1]）有效解決。

1.2 加權(quán)稀疏子空間

在理想情況下，在公式（1）中，對所有的[j∈S1]令[cij=0]。但是對于真實(shí)的數(shù)據(jù)SSC算法可能并不能確定理想的解決方案。我們可以用加權(quán)的[?1]最小框架代替[?1]最小框架，這將可能地改善子空間聚類的性能。正如所討論的，加權(quán)矩陣的更新是建立在[PW1]解的前一次迭代上。

下面是我們的加權(quán)稀疏子空間框架：

[min（C，E，Z） W⊙C1+λeE1+λz2Z2F s.t. Y=YC+E+Z，1TC=1T， diag（C）=0.] （3）

在仿射的情況下，上面提出的框架可以用下面的描述：

[min（C，E，A） W⊙C1+λeE1+λz2Y-YZ-E2F s.t. AT1=1，A=C-diag（C）.] （4）

其中，[A]是通過在所要優(yōu)化的變量的硬閾值得到更快的更新值的一個(gè)輔助矩陣。將所有的元素設(shè)置為一個(gè)加權(quán)矩陣。因此，上述框架是一個(gè)簡單的[?1]最小化問題。它是凸的，可以通過凸程序算法（具體見參考文獻(xiàn)[2][3]）有效的解決。

2 實(shí)驗(yàn)和討論

對于所有的算法，我們使用它們作者所提供的代碼。所有的參數(shù)的選擇都是在最終平均聚類錯(cuò)誤率最低時(shí)。使用的是Matlab2014b，Intel（R） Core（TM） i7-4770K CPU 3.50GHz 12GB RAM。

對于Hopkins 155數(shù)據(jù)集：在LRR算法中，我們使用[λ=4]。在LSR算法中，作者在LSR問題上應(yīng)用了兩種不同的方法，分別為LSR1和LSR2。最好的性能是在[λ=0.0048]（LSR1）和[λ=0.0046]（LSR2）取的。在SMR算法中，我們使用[α=20]。在SSC算法中，我們使用[α=800]。另外，為了數(shù)值穩(wěn)定性，我們使用[ε1=0.001]，[ε2=0.02]。

在我們的試驗(yàn)中，表1顯示的是使用原始2F維特征軌跡。表2顯示的是通過PCA將2F維投影到4n維子空間，n代表移動(dòng)物體的數(shù)目。在這里，我們使用相同的參數(shù)。有如下的結(jié)論：

（1） 在2F和4n情況下，所有的算法取得低的平均錯(cuò)誤率（低于5%）。但是，相比于已經(jīng)存在的算法，最近提出的SMR算法和本文中的RSSC算法取得低于1%的錯(cuò)誤率。這些結(jié)果說明了RSSC算法在運(yùn)動(dòng)分割中有很強(qiáng)的穩(wěn)定性。

（2） 在原始2F原始運(yùn)動(dòng)追蹤的情況下，使用RSSC算法所得到的2個(gè)運(yùn)動(dòng)物體聚類錯(cuò)誤率從1.53%降到0.64%，3個(gè)運(yùn)動(dòng)物體聚類錯(cuò)誤率從4.4%降到2.01%。對于整個(gè)Hopkins 155數(shù)據(jù)集，SSC算法平均聚類錯(cuò)誤率為2.28%，RSSC算法的為0.95%。對于投影到4n維數(shù)特征追蹤，對兩個(gè)物體和三個(gè)物體分別使用RSSC算法得到的聚類錯(cuò)誤率從1.69%和4.38%分別降到0.83%和2.50%。對于整個(gè)Hopkins 155數(shù)據(jù)集平均聚類錯(cuò)誤率：SSC算法的為2.29%，RSSC算法的為1.21%。結(jié)果表明RSSC算法通過加權(quán)迭代[?1]最小比SSC算法性能更優(yōu)。

參考文獻(xiàn)：

[1] Elhamifar E，Vidal R.Sparse subspace clustering： algorithm， theory， and applications[J].IEEE Trans，Pattern Anal. Mach. Intell. 2013，35 （11）：2765–2781.

[2] Boyd S P， Vandenberghe L.Convex Optimization[M].Cambridge University Press，2004.

[3] Boyd S， Parikh N， Chu E.Distributed optimization and statistical learning via the alternating direction method of multipliers， Found. Trends Mach. Learn. 2011，3 （1）：1–122.

[4] Liu G， Lin Z， Yu Y.Robust subspace segmentation by low-rank representation[C].ICML， 2010.