原鏈接：漫談高維數(shù)據(jù)聚類(2):子空間聚類
1.子空間聚類
給定一個n個樣本構(gòu)成的矩陣驹碍，并且已知這
個樣本是分別來自
個子空間
椭微。令
表示
個子空間的維度（其中
是未知的）耍攘。子空間聚類的目的是將這個
個樣本正確地劃歸到各自所屬的子空間中去，即將
個樣本聚成
類，每一個類就是一個子空間儿捧。
從上圖可以看到委造，總共有三個子空間，每個子空間上都有一些樣本佩迟，位于同一個子空間內(nèi)的樣本就可以說是同一類的团滥。每一個子空間有其相應(yīng)的維數(shù),和一組基
，由這組基可以表示該子空間中任意一個向量报强。
2.稀疏表示模型和低秩表示模型
目前灸姊，有四大類主流的求解子空間聚類問題的算法，分別是：
（1）基于統(tǒng)計的方法：混合數(shù)據(jù)假設(shè)是從服從某一概率分布（如混合高斯分布）中抽取出的獨立樣本集躺涝，于是數(shù)據(jù)的分割問題就轉(zhuǎn)化為一模型估計問題厨钻。代表性的工作有凝聚有損壓縮[2]和隨機抽樣一致[1]扼雏；
（2）基于矩陣分解的方法：將數(shù)據(jù)矩陣分解為一正交基矩陣和一低秩矩陣的乘積，從分解結(jié)果的結(jié)構(gòu)來揭示聚類的特性夯膀。當(dāng)子空間含有噪聲和奇異值诗充，或者獨立子空間的假設(shè)不成立時，此類方法的效果不盡人意诱建。代表性的工作有K子空間分割[4]蝴蜓；
（3）基于代數(shù)的方法：可以處理子空間不是相互獨立的情況，但計算量大俺猿，且對噪聲和奇異值敏感茎匠。代表性的工作有Generalized PCA(GPCA)[3]；
（4）基于譜聚類的方法：譜聚類算法是一種對高維數(shù)據(jù)進(jìn)行聚類的技術(shù)押袍∷忻埃基于譜聚類的子空間分割算法先根據(jù)觀測樣本求得一個相似矩陣，然后對這個相似矩陣進(jìn)行譜聚類獲得最終的聚類結(jié)果谊惭。代表性的工作有稀疏子空間聚類[5]和低秩表示子空間聚類[6][7]汽馋。
這里我們展開解釋稀疏表示和低秩表示。
稀疏表示(Sparse Representation)
稀疏表示這一概念的提出圈盔，說到底還是受到壓縮感知理論[8][9]的啟發(fā)豹芯。該理論認(rèn)為很多高維數(shù)據(jù)是冗余的，如果其具有可壓縮性驱敲，那么可以只需要通過少量的采樣便可恢復(fù)原始高維數(shù)據(jù)铁蹈。更簡單地說就是，許多高維數(shù)據(jù)是存在其低維表示的众眨。
學(xué)過線性代數(shù)的都應(yīng)該知道線性相關(guān)這一概念握牧，即向量組,其中
是
的列向量，若存在不全為0 的系數(shù)
围辙，使得
成立我碟，則說
是線性相關(guān)的，如若
不等于零姚建，那
就可以被其余向量線性表示矫俺，即
。
有了以上兩個認(rèn)知掸冤，就可以理解稀疏表示了厘托。在前面提到過位于同一個子空間中的樣本，如果樣本數(shù)足夠多稿湿，那么某一個樣本是可以被與它位于同一個子空間中的其他樣本線性表示的铅匹，而我們希望用盡量少的樣本來表示
，這就是稀疏表示的簡單理解饺藤，用數(shù)學(xué)語言描述該模型如下：
給定一個n個樣本構(gòu)成的矩陣,其中每一列是一個樣本包斑，由
中
個樣本構(gòu)成一個“字典”
,
中每一列成為原子流礁。那么，每一個樣本都可以表示成“字典”中原子的線性組合：
其中,是系數(shù)矩陣罗丰，
是樣本
的“表示”神帅。而字典
通常是過完備的，因為經(jīng)常是選取全部樣本作為字典萌抵，即
找御。因此，上市會有多個解绍填。但是如給系數(shù)矩陣加上約束霎桅，則會有唯一解。稀疏表示即是要求系數(shù)矩陣
是最稀疏的讨永，即
其中滔驶，是求矩陣所有元素的絕對值的和。進(jìn)一步卿闹，這個模型還可以加上噪聲瓜浸，即
低秩表示模型(Low-rank Representation)
低秩表示模型和稀疏表示模型幾乎一樣，區(qū)別僅在于對系數(shù)矩陣的約束不同比原，在低秩表示中，它期望系數(shù)表示矩陣Z盡可能的低秩杠巡，用數(shù)學(xué)語言描述如下:
其中,表示矩陣
的秩量窘。與
范數(shù)一樣，秩函數(shù)也具有離散組合性質(zhì)氢拥，因此求解上式是一個NP難得蚌铜。但是如果上式存在一個較低秩的解的話，秩優(yōu)化問題可以被松弛為核范數(shù)最小化問題嫩海，即:
其中冬殃，是矩陣的核范數(shù)。松弛的原理可以這么理解叁怪，一個矩陣的秩等于其非零奇異值的個數(shù)审葬。那么矩陣的秩最小化等價于矩陣的奇異值非零個數(shù)盡量少，進(jìn)一步可以松弛為矩陣的所有奇異值的和盡量小奕谭。
低秩表示模型是在稀疏表示模型之后提出來的涣觉，當(dāng)然它比稀疏表示模型的性能更好，這是因為低秩表示模型中的核函數(shù)自帶聚集屬性血柳，具體的原因我推薦論文[10]中的講解（在其第五章中）官册。
求解上述兩個模型的方法有很多，有興趣的朋友可以參閱論文[11]难捌。
Reference
[1]Fischler M., Bolles R. RANSAC random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Journal of ACM, 1981, 24(6): 381–395.
[2]Ma Y., Derksen H., Hong W., Wright J. Segmentation of multivariate mixed data via lossy coding and compression. IEEE Trans. Pattern Analysis and Machine Intelligence, 2007, 29(9): 1546–1562.
[3]Vidal R., Ma Y., Sastry S. Generalized principal component analysis (GPCA). IEEE Trans. Pattern Analysis and Machine Intelligence, 2005, 27(12): 1–15.
[4]Lu L., Vidal R. Combined central and subspace clustering on computer vision applications. In: Proc. 23rd Int’l Conf. Machine Learning (ICML), 2006, pp.593–600.
[5] Elhamifar E, Vidal R. Sparse subspace clustering[J]. IEEE Conference on Computer Vision and Pattern Recognition, Cvpr, 2009:2790 - 2797.
[6]G L, Z L, S Y, et al. Robust Recovery of Subspace Structures by LowRank Representation[J]. Pattern Analysis & Machine Intelligence IEEE Transactions on, 2010, 35(1):171 - 184.
[7]X G, K Z, D T, et al. Image SuperResolution With Sparse Neighbor Embedding[J]. IEEE Transactions on Image Processing, 2012, 21(7):3194 - 3205.
[8]Donoho D L． Compressed sensing． IEEE Transactions on Information Theory,2006 52(4)：1289-1306．
[9]Cand6s E．Compressive sampling．Proceedings of Proceedings of Inter-national Congress of Mathematicians膝宁，2006．1433-1452．
[10] 盧參義. 基于稀疏表示的人臉分類與聚類[D]. 中國科學(xué)技術(shù)大學(xué), 2012. DOI:10.7666/d.y2126052.
[11]Lin Z, Chen M, Ma Y. The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices[J]. Eprint Arxiv, 2010.
