高維聚類分析

高維聚類分析

將物理或抽象對象的集合分組稱為由類似的對象組成的多個類的過程被稱為聚類。高維聚類分析與傳統聚類分析的最主要差別就是高維度。高維數據聚類是聚類技術的難點和重點。

詳細內容

目前,聚類分析的研究集中在聚類方法的可伸縮性、對複雜形狀和類型的數據進行聚類的有效性、高維聚類分析技術以及混合數據的聚類方法研究,其中,高維數據聚類是聚類分析的難題,也是涉及到聚類算法是否適用於很多領域的關鍵。而傳統聚類算法對高維數據空間進行聚類時會遇到困難,為了解決這個問題,R.Agrawal首次提出了子空間聚類的概念 ,以解決高維數據的聚類問題。

高維數據聚類已成為數據挖掘中的一個重要研究方向。因為隨著技術的進步使得數據收集變得越來越容易,導致資料庫規模越來越大、複雜性越來越高,如各種類型的貿易交易數據、Web 文檔、基因表達數據等,它們的維度(屬性)通常可以達到成百上千維,甚至更高。但是,受“維度效應”的影響,許多在低維數據空間表現良好的聚類方法運用在高維空間上往往無法獲得好的聚類效果。

傳統算法

傳統的聚類算法可分以下五類 :① 劃分方法②層次方法③基於密度的方法④基於格線的方法⑤基於模型的方法。它們已經比較成功的解決了低維數據的聚類問題。但是由於實際套用中數據的複雜性,在處理許多問題時,現有的算法經常失效,特別是對於高維數據和大型數據的情況。因為傳統聚類方法在高維數據集中進行聚類時,主要遇到兩個問題。①高維數據集中存在大量無關的屬性使得在所有維中存在簇的可能性幾乎為零;②高維空間中數據較低維空間中數據分布要稀疏,其中數據間距離幾乎相等是普遍現象,而傳統聚類方法是基於距離進行聚類的,因此在高維空間中無法基於距離來構建簇。

目前一般使用兩種方法解決以上問題:(1)特徵轉換,(2)特徵選擇 /子空間聚類。

特徵轉換是一種傳統的方法,包括主成份分析和奇異值分解等策略。該方法通過線性合併將原數據集的維合併至k個新維,使得諸如k~均值一類的傳統算法能在這k個新維中進行有效聚類,從而達到減少維的目的。但是該方法的缺點有三點:一是難於確定合適的k值,二是高維空間中存在大量無關維而掩蓋了簇,給聚類造成困難;三是聚類時容易產生無意義的簇。因此該方法只適合對事先已知多數維都相關的高維數據集進行聚類。

特徵選擇和特徵轉換不同,它只在那些相關的子空間上執行挖掘任務,因此它比特徵轉換更有效地減少維。特徵選擇一般使用貪心策略等搜尋方法搜尋不同的特徵子空間,然後使用一些標準來評價這些子空間,從而找到所需的簇。

子空間聚類算法拓展了特徵選擇的任務,嘗試在相同數據集的不同子空間上發現聚類。和特徵選擇一樣,子空間聚類需要使用一種搜尋策略和評測標準來篩選出需要聚類的簇,不過考慮到不同簇存在於不同的子空間,需要對評測標準做一些限制。選擇的搜尋策略對聚類結果有很大的影響。根據搜尋的方向的不同,可以將子空間聚類方法分成兩大類:自頂向下的搜尋策略和自底向上的搜尋策略。子空間聚類是實現高維數據集聚類的有效途徑,它是在高維數據空間中對傳統聚類算法的一種擴展,其思想是將搜尋局部化在相關維中進行。

套用

高維數據聚類分析是聚類分析中一個非常活躍的領域,同時它也是一個具有挑戰性的工作。目前,高維數據聚類分析在市場分析、信息安全、金融、娛樂、反恐等方面都有很廣泛的套用。

相關詞條

相關搜尋

熱門詞條

聯絡我們