[發明專利]基于拉格朗日對偶的半正定譜聚類方法

有效

• 申請號: 201210445602.9
• 申請日: 2012-11-08
• 公開（公告）號: CN102982342A
• 公開（公告）日: 2013-03-20
• 發明（設計）人: 嚴嚴;沈華森;王菡子
• 申請（專利權）人: 廈門大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 廈門南強之路專利事務所 35200
• 代理人: 馬應森

技術領域

本發明涉及一種譜聚類方法，特別是涉及一種基于拉格朗日對偶的半正定譜聚類方法。

背景技術

聚類分析是統計數據分析和處理領域最流行的技術之一。目前已廣泛地應用于圖像分析、模式識別、機器學習和信息檢索等。聚類分析的目標是有效地區分數據集中不同的數據類別（稱為“簇”），使得相同簇內數據的相似度大，而不同簇數據之間數據的相似度小。近年來，譜聚類方法已快速發展成為一類有效的聚類技術。譜聚類方法建立在譜圖理論的基礎上，主要利用數據集的相似度矩陣的特征向量進行有效聚類。與傳統的聚類方法（如k-均值聚類等）相比，譜聚類方法有很多優點，其不僅實現簡單，與維數無關，而且能夠在任意形狀的數據分布上聚類并收斂于全局的最優解，因此得到了廣泛的應用。

譜聚類方法把聚類看成是一個圖分割問題。一般情況下，譜聚類方法首先建立一個基于所有數據點的圖模型（相似度矩陣），圖中的邊用來表征不同數據點之間的距離。然后在特定的誤差度量下對相似度矩陣進行歸一化，最后對歸一化矩陣的特征值分解得到的低維數據利用簡單的聚類方法（如k均值聚類）進行有效聚類。譜聚類方法中相似度矩陣的建立和歸一化是影響最終譜聚類性能的關鍵因素。

給定一個相似度矩陣，最簡單的圖分割方法就是解決最小割（min-cut）問題。最小割的目的是最小化子圖的邊的權重（即子圖中樣本之間的相似度和）。然而由于子圖大小沒有限制，通常最小割的聚類結果并不有效。通過在圖分割的問題中引入子圖大小的約束條件，比率割（Ratio-Cut）（P.K.Chan,M.D.F.Schlag,and?J.Y.Zien,“Spectral?k-way?ratiocutpartitioning?and?clustering,”IEEE?Trans.Comput.-Aided?Des.Integr.Circuits?Syst.,vol.13,no.9.pp.1088-1096,1994.）和歸一化割（Normalized-Cut）（J.Shi?and?J.Malik,“Normalized?cutsand?image?segmentation,”IEEE?Trans.Pattern?Anal.Mach.Intell.,vol.22,no.8,pp.888-905,2000.）可以有效的解決這個問題。比率割和歸一化割的本質都是希望達到不同簇之間的平衡分割。

理論已證明，比率割和歸一化割的關鍵區別是相似度矩陣歸一化的不同。相似度矩陣歸一化實際上是一個尋找雙隨機（doubly-stochastic）矩陣（非負，對稱和F1=1）的過程。不同的譜聚類算法實際都可以看成是尋找在不同的誤差度量下的一種近似。比率割是基于L₁錯誤度量下的歸一化，而歸一化割是基于相對熵（也稱為的Kullback-Leibler散度）錯誤度量下的歸一化。Zass等人（R.Zass?and?A.Shashua,“Doubly?stochastic?normalization?forspectral?clustering,”in?Proc.Adv.Neural?Inf.Process.Syst.,Vancouver,B.C.,Canada,2006,pp.1569–1576.）提出了一種基于Frobenius范數尋找雙隨機矩陣的有效歸一化方法（簡稱FSC方法）。FSC方法通常被認為是目前有效的一種相似度矩陣歸一化方法。然而Frobenius歸一化的主要問題是半正定約束條件被忽略。這使得該方法得到的雙隨機矩陣并不準確。另一方面，加入半正定條件的Frobenius歸一化優化問題是一種半正定規劃問題。為了求解該優化問題，傳統的基于內點法的求解算法的效率很低，時間復雜度高達（O(n^6.5)），其中n是數據的數目，只能應用在小規模的數據集上。

發明內容

本發明的目的在于提供可以非常方便地利用現有的特征值分解和梯度下降法來解決半正定規劃問題，可以在多項式時間內找到全局最優解，且其時間復雜度僅為（O(t^·n³)，其中t為迭代次數，通常約250次）的基于拉格朗日對偶的半正定譜聚類方法。