[發明專利]基于Self-tuning的局部密度譜聚類相似度量算法

在審

• 申請號: 201410498330.8
• 申請日: 2014-09-25
• 公開（公告）號: CN104318241A
• 公開（公告）日: 2015-01-28
• 發明（設計）人: 陳雷霆;蔡洪斌;邱航;關亞勇;曹躍;崔金鐘;盧光輝
• 申請（專利權）人: 東莞電子科技大學電子信息工程研究院
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 成都中亞專利代理有限公司 51126
• 代理人: 何淵

技術領域

本發明數據聚類分析技術領域，具體涉及一種基于Self-tuning的局部密度譜聚類相似度量算法，可用于對數據、圖片等信息進行聚類分析。

背景技術

聚類分析是一種重要的無監督分析方法，譜聚類則是一種新的聚類方法，基于譜聚類好的聚類效果和完善的理論推導，已被廣泛的應用到數據聚類分析問題中。傳統的聚類算法，如k-means算法，GMM算法等適用于凸球形的樣本空間，對于樣本空間為非凸時，算法會陷入局部最優，但譜聚類方法能夠很好地收斂到全局最優，且在沒有對數據的原始結構做任何假設的情況下，無論對于常規的密集型數據，還是一些任意結構的數據，譜聚類都能夠表現出很好的聚類效果。

譜聚類方法主要將數據的聚類問題轉化為圖譜的分割問題，進而對數據進行劃分。在譜聚類算法中，關鍵的處理部分主要有三個：相似性度量的方法選取、拉普拉斯矩陣的構建和特征向量的選取。其中拉普拉斯矩陣的構建是直接基于相似矩陣進行操作的，相似矩陣的好壞直接影響到最后的聚類效果，所以如何進行相似性度量一直是譜聚類方法中備受研究的一個話題。

原始的譜聚類方法提出來的相似性度量是采用高斯核的方法進行構建，但其參數σ需要根據數據的實際規模來設定，不同的σ值會產生不同的聚類效果，波動較大，很難找到一個最優的值。Lihi?Zelnik.Manor等人提出的Self-Tuning?Spectral?Clustering方法利用局部尺度參數來代替全局的尺度參數，該方法能夠很好的應對多尺度的數據，但其構造的相似矩陣不能夠表示出數據點之間的局部密度信息，導致在一些真實數據集上不能達到理想的聚類效果；XianchaoZhang等人中提出了基于公共近鄰的方法來反映兩個數據點之間的局部密度，并且通過全局的σ參數來表示數據之間的粘連效果，但該方法需要手工設定參數σ來反映數據的結構規模，波動較大，且公共近鄰半徑選取意義不明確，導致在一些結構復雜的數據集上不能夠達到聚類的效果。

發明內容

基于以上方法的思想和存在問題，我們提出了一種改進的譜聚類方法即基于Self-tuning的局部密度譜聚類相似度量算法，主要解決了兩個方面的問題：(1).自適應的計算尺度參數σ，不需要手工設定參數的值；(2).自適應的計算樣本數據的局部密度，增強屬于同一聚類的數據點之間的權重值。

在基于Self-tuning的局部密度譜聚類相似度量算法(以下簡稱SC-STLD算法)中，相似矩陣的構造公式如下：

AL(xixj)=exp(-d2(xixj)σiσj(CNN(xi,xj)+1))---(1)]]>

σ_i＝d(x_i，x_k)(2)