子空間聚類

傳統聚類方法在高維數據集中進行聚類時，主要遇到兩個問題。 子空間聚類算法拓展了特徵選擇的任務，嘗試在相同數據集的不同子空間上發現聚類。

聚類分析是數據挖掘領域中的關鍵技術之一。高維數據聚類是聚類分析技術的難點和重點，子空間聚類是實現高維數據集聚類的有效途徑，它是在高維數據空間中對傳統聚類算法的一種擴展，其思想是將搜尋局部化在相關維中進行。
根據算法思想，傳統的聚類算法可分以下五類 ：① 劃分方法：將數據集隨機劃分為k個子集，隨後通過疊代重定位技術試圖將數據對象從一個簇移到另一個簇來不斷改進聚類的質量；②層次方法：對給定的數據對象集合進行層次的分解，根據層次的形成方法，又可以分為凝聚和分裂方法兩大類；③基於密度的方法：根據領域對象的密度或者某種密度函式來生成聚類，使得每個類在給定範圍的區域內必須至少包含一定數目的點；④基於格線的方法：將對象空間量化為有限數目的單元，形成一個格線結構，使所有聚類操作都在這個格線結構上進行，使聚類速度得到較大提高；⑤基於模型的方法：為每個類假定一個模型，尋找數據對給定模型的最佳擬合。
目前，聚類分析的研究集中在聚類方法的可伸縮性、對複雜形狀和類型的數據進行聚類的有效性、高維聚類分析技術以及混合數據的聚類方法研究，其中，高維數據聚類是聚類分析的難題，也是涉及到聚類算法是否適用於很多領域的關鍵。而傳統聚類算法對高維數據空間進行聚類時會遇到困難，為了解決這個問題，R．Agrawal首次提出了子空間聚類的概念 ，以解決高維數據的聚類問題。
傳統聚類方法在高維數據集中進行聚類時，主要遇到兩個問題。①高維數據集中存在大量無關的屬性使得在所有維中存在簇的可能性幾乎為零；②高維空間中數據較低維空間中數據分布要稀疏，其中數據間距離幾乎相等是普遍現象，而傳統聚類方法是基於距離進行聚類的，因此在高維空間中無法基於距離來構建簇。
目前一般使用兩種方法解決以上問題：（1）特徵轉換，（2）特徵選擇 ／子空間聚類。
特徵選擇只在那些相關的子空間上執行挖掘任務，因此它比特徵轉換更有效地減少維。特徵選擇一般使用貪心策略等搜尋方法搜尋不同的特徵子空間，然後使用一些標準來評價這些子空間，從而找到所需的簇。
子空間聚類算法拓展了特徵選擇的任務，嘗試在相同數據集的不同子空間上發現聚類。和特徵選擇一樣，子空間聚類需要使用一種搜尋策略和評測標準來篩選出需要聚類的簇，不過考慮到不同簇存在於不同的子空間，需要對評測標準做一些限制。
選擇的搜尋策略對聚類結果有很大的影響。根據搜尋的方向的不同，可以將子空間聚類方法分成兩大類：自頂向下的搜尋策略和自底向上的搜尋策略。