[發明專利]一種用于高維數據聚類的半監督降維方法

無效

• 申請號: 201110308490.8
• 申請日: 2011-10-12
• 公開（公告）號: CN102411610A
• 公開（公告）日: 2012-04-11
• 發明（設計）人: 劉海風;楊政;吳朝暉
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州天勤知識產權代理有限公司 33224
• 代理人: 胡紅娟

技術領域

本發明屬于數據處理技術領域，具體涉及一種用于高維數據聚類的半監督降維方法。?

背景技術

聚類是機器學習和數據挖掘中一種常見的多元統計分析方法，它討論的對象是大量的樣品，要求能按各自的特性來進行合理的分類，沒有任何模式可供參考或依循，即在沒有先驗知識的情況下進行的。目前，作為一種有效地數據分析手段，聚類方法被廣泛應用于各大領域：在商業上，聚類分析被用來發現不同的客戶群，并且通過購買模式刻畫不同的客戶群的特征；在生物上，聚類分析被用來動植物分類和基因進行分類，獲取對種群固有結構的認識；在地理上，聚類能夠幫助在地球中被觀察的數據庫上趨于的相似性；在保險行業上，聚類分析通過一個高的平均消費來鑒定汽車保險單持有者的分組，同時根據住宅類型，價值，地理位置來鑒定一個城市的房產分組；在互聯網應用中，聚類分析被用來對網絡中的文檔進行歸類，對虛擬社區中的用戶進行分組。?

常見的聚類分析方法主要包括如下幾種：?

(1)分裂法，又稱劃分方法，首先創建K個劃分，K為要創建的劃分的個數；然后利用一個循環定位的技術通過將對象從一個劃分移到另一個劃分來改善劃分質量。典型的劃分方法有：K均值聚類算法(Kmeans)、K中心聚類算法(Kmedoids)和聚類大應用程序算法(CLARA，Clustering?LARge?Application)等。?

(2)層次法，通過創建一個層次以分解給定的數據集。該方法可以分為自上而下(分解)和自下而上(合并)兩種操作方式。為彌補分解與合并的不足，層次合并經常要與其它聚類方法相結合，如循環定位。典型的層次方法有：基于平衡迭代降低的層次聚類算法(BIRCH，Balanced?Iterative?Reducing?andClustering?using?Hierarchies)、基于表達的聚類算法(CURE，Clustering?UsingREprisentatives)和基于動態模型的層次聚類算法(CHEMALOEN)等。?

(3)基于密度的方法，根據密度完成對象的聚類。它根據對象周圍的密度不斷增長聚類。典型的基于密度的方法有：基于密度的聚類算法(DBSCAN，Densit-based?Spatial?Clustering?of?Application?with?Noise)和基于對象排序識別聚類結構的聚類算法(OPTICS，Ordering?Points?To?Identify?the?Clustering?Structure)。?

(4)基于網格的方法，首先將對象空間劃分為有限個單元以構成網格結構，然后利用網格結構完成聚類。?

(5)基于模型的方法，它假設每個聚類的模型并發現適合相應模型的數據。?

這些傳統的聚類方法已經比較成功的解決了低維數據的聚類問題，但是由于實際應用中數據的復雜性，在處理許多高維數據時經常失效。因為傳統聚類方法對高維數據集中進行聚類時，主要遇到兩個問題：(1)高維數據集中存在大量無關的屬性使得在所有維中存在簇的可能性幾乎為零；(2)高維帶來的維度災難使得某些聚類算法的實用性幾乎為零。?

針對以上兩個問題，也就是為了解決維數災難和消除數據中對于聚類來說不必要的冗余信息，在進行聚類之前，先進行數據降維是非常必要的。目前主要的降維方法有：?

(1)主成分分析(Principal?Component?Analysis，PCA)：經典的無監督線性降維方法。其是一種掌握事物主要特征的方法，它可以從多元事物中解析出主要影響因素，揭示事物的本質，簡化復雜的問題。?

(2)線性判別分析(Linear?Discriminant?Analysis，LDA)：經典的有監督降維方法。這種方法能夠在低維子空間中保持類的相關結構，適用于以分類和識別為目的的降維，但重構效果不如PCA方法。?

(3)非負矩陣分解(Nonnegative?Matrix?Factorization，NMF)：非負矩陣分解法通過將數據矩陣分解為基矩陣V和系數矩陣H來達到降維的目的，在矩陣分解過程中非負矩陣分解保持了基矩陣和系數矩陣的非負性。?