[發明專利]一種帶局域限制的矩陣概念分解方法

有效

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

技術領域

本發明屬于數據處理技術領域，具體涉及一種帶局域限制的矩陣概念分解方法。

背景技術

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

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

針對以上兩個問題，也是為了解決維數災難和消除數據中對于聚類來說不必要的冗佘信息，在進行聚類之前，先進行數據降維是非常必要的。數據的降維表示在模式識別、計算機視覺以及圖像處理等應用領域是一個基本問題。線性的數據表示方法，如矢量分解(Vector?Quantization，VQ)、主成分分析(Principal?Component?Analysis，PCA)、獨立成分分析(Independent?Component?Analysis，ICA)、稀疏編碼(Sparse?Coding)、矩陣分解(Matrix?Factorization，MF)等，已經被廣泛應用到這些數據分析的實際應用中。

在所有這些方法中，矩陣分解是最為頻繁使用的基本方法。矩陣分解的基本步驟是將原始數據矩陣分解成為兩個或兩個以上的因子矩陣，而分解所得因子矩陣的乘積可以有效地近似表示原始數據。一般矩陣分解所得的其中一個因子矩陣(或者幾個因子矩陣的乘積)可以看作原始數據的基，每組基向量都蘊含著一些數據的內在語義；其他的因子矩陣則看作系數矩陣，來表述原始數據與每組基向量的聯系，它相當于原始數據在低維空間下的新表示。在現實應用中，矩陣分解后找到的基的數量通常要遠小于數據的原始維度。因此矩陣分解可以有效地壓縮數據大小，為其他數據學習方案如聚類、分類等提供便利。

基于矩陣分解理論的非負矩陣分解(Non-negative?Matrix?Factorization，NMF)和概念分解(Concept?Factorization，CF)，已經被證實在圖像處理、人臉識別、文檔聚類以及生物信息化等數據分析應用中表現得十分出色。非負矩陣分解與其他矩陣分解方法的不同之處是，它要求原始數據矩陣非負(即矩陣的每個元素都是非負的)，并且分解所得的因子矩陣都是非負的。使用非負矩陣分解方法所得的基可以直觀地體現原始數據內蘊含的潛在語義關系，而且是對原始數據的稀疏編碼。而概念分解作為非負矩陣分解的一個變種，其使用了原始數據的線性組合來表示每組基，概念分解在繼承非負矩陣分解的數據降維表示能力的同時，還可以應用于任意數據集表示空間，因此概念分解可以使用核化方法來強化矩陣分解的效果。盡管以上這兩種方法都能達到稀疏性目標，卻無法保證局域限制。這兩種分解方法所得到的基可能與原始數據距離甚遠，使用這類基來進行數據表示顯然也不會是最優的。

發明內容

針對現有技術所存在的上述技術缺陷，本發明提供了一種帶局域限制的矩陣概念分解方法，能夠改善聚類分析的效果，提高聚類分析的判別能力。

一種帶局域限制的矩陣概念分解方法，包括如下步驟：

(1)獲取樣本集合，進而構建樣本集合的樣本特征矩陣；

所述的樣本特征矩陣為m×n維矩陣，m為特征個數，n為樣本個數，且m和n均為大于1的自然數，樣本特征矩陣中的任一元素值為對應樣本對應特征的特征值；

(2)根據所述的樣本特征矩陣，通過帶局域限制的迭代算法求解出基矩陣和系數矩陣；

(3)使所述的系數矩陣作為樣本特征矩陣的低維表示，并根據所述的基矩陣計算出樣本特征矩陣的基，以供聚類分析。

所述的步驟(2)中，帶局域限制的迭代算法基于以下迭代方程組：