子空間聚類算法概述目錄TOC\o"1-3"\h\u23595子空間聚類算法概述 1324071.1.1子空間聚類概述 1108121.1.2子空間聚類算法 2子空間聚類的發(fā)展以及相關(guān)的工作在第一章已經(jīng)很詳細(xì)地講述了，接下來將介紹子空間聚類的原理，性能與相關(guān)的算法實現(xiàn)。聚類算法，簡而言之，就是要將被處理的數(shù)據(jù)有效地聚在一起，之間相似度高的數(shù)據(jù)應(yīng)該被分到同一類，之間相似度低的同樣就不能被放在同一類，一般都用錯誤聚類的數(shù)據(jù)比上所有數(shù)據(jù)這種錯誤率來表示聚類算法的性能。子空間聚類就是將特征數(shù)據(jù)分到各個子空間，然后再計算各個子空間中數(shù)據(jù)的相似性，這種相似度通常都是用距離來表示，一般用歐式距離或者Sampson距離。但有時也有方法用相似系數(shù)來表示，通常有夾角余弦，指數(shù)相似等表示方法。子空間聚類概述子空間聚類主要是為了處理高維的數(shù)據(jù)而被提出的，在一些高維數(shù)據(jù)中，需要將其分為多個不同維數(shù)的子空間，然后才能對低維的數(shù)據(jù)進(jìn)行下一步的處理，如下圖2.1所示，圖中明顯是個三維圖像，也就是說代表的是三維數(shù)據(jù)，但是按照圖中的子空間降維，整個數(shù)據(jù)就可以變成一個一維的數(shù)據(jù)空間和兩個二維的數(shù)據(jù)空間，這就是子空間聚類的精髓所在，然后再同一子空間的數(shù)據(jù)可以再進(jìn)一步地處理。圖2.1子空間聚類之前也討論過，很多研究子空間聚類的學(xué)者有很多新的思路去改進(jìn)子空間聚類這一算法。因為即使被降維的數(shù)據(jù)各個來看是比較簡單地一個數(shù)據(jù)，容易被處理，但是總得來看，這還是一組龐大的數(shù)據(jù)，只是再用相似度矩陣去表示時容易了很多。所以后面很多方法如SSC、LRR都對得到的相似度矩陣進(jìn)行簡化處理，但是這樣的簡化也有可能將一些先驗的信息丟掉，這樣反而得不出數(shù)據(jù)之間的差異性，而且這些方法在面對噪聲影響時，并不具備一定的抗干擾能力，魯棒性和穩(wěn)定性有待提高。這些都是基于子空間的聚類方法?，F(xiàn)在比較流行的是基于相似度矩陣的方法，也可以叫親和矩陣，這類方法抗噪聲能力明顯強(qiáng)于基于子空間的聚類算法，因為這些方法通過對所有條運(yùn)動軌跡之間的相似性進(jìn)行分析，而不是對于一個個數(shù)據(jù)點。所以子空間聚類也可以學(xué)其所長進(jìn)行優(yōu)化。子空間聚類算法上面講述了關(guān)于子空間聚類的原理與優(yōu)缺點，下面介紹一種比較傳統(tǒng)的子空間聚類算法CLIQUE算法。CLIQUE[56]算法和很多算法都有點差異，這是一種基于網(wǎng)格的算法，這種基于網(wǎng)格的聚類算法好處是可以輕松處理高維數(shù)據(jù)，雖然這是所有基于子空間算法的優(yōu)點，但是此方法好在可以得到更好的子空間劃分，降維能力很強(qiáng)。CLIQUE算法和一般的子空間聚類算法不同，一般的聚類算法的各個子空間有可能重疊在一起，但是這種聚類算法不會，這是基于網(wǎng)格算法的又一好處，他能把輸入進(jìn)來的數(shù)據(jù)分到各個不重疊的子空間，這樣數(shù)據(jù)提前有了個分類，不會再互相干擾。其實這個算法也運(yùn)用了基于密度的聚類算法的技術(shù)，在進(jìn)行降維以后，用密度來表示各個數(shù)據(jù)之間的相似性。所以這個算法有兩個重要的模型參數(shù)，一個是每個網(wǎng)格的步長，也就相當(dāng)于子空間的劃分，還有一個是密度，密度是用來表示被網(wǎng)格劃分后各個數(shù)據(jù)點之間的相似性，是聚類的關(guān)鍵。下面將簡單講一下算法實現(xiàn)過程：首先要先將所有數(shù)據(jù)都劃分到各個子空間中，然后各個子空間也被分為多個網(wǎng)格。然后遍歷一遍所有的網(wǎng)格，如果發(fā)現(xiàn)這個網(wǎng)格是足夠密集的，就將這個網(wǎng)格內(nèi)的數(shù)據(jù)保留，之所以要找密度足夠高的網(wǎng)格，是因為密度低的網(wǎng)格就可以不處理，因為密度低就說明了這些數(shù)據(jù)不是很多，且不重要，肯定不是所需要的數(shù)據(jù)。下一步就是開始擴(kuò)展，接下來繼續(xù)掃描網(wǎng)格，找到下一個密度很高的網(wǎng)格，然后就可以將這些網(wǎng)格合并起來，直到所有這樣的網(wǎng)格都進(jìn)行了合并。這樣，基本上所有網(wǎng)格都有被掃描到，這樣所有密集的子空間都可以被找到，然后這些網(wǎng)格進(jìn)行合并。這有點類似于稀疏子空間聚類，將一些不太相關(guān)的