[發明專利]一種基于局部密度和測地距離的分層譜聚類方法

在審

• 申請號: 201510233619.1
• 申請日: 2015-05-08
• 公開（公告）號: CN104778480A
• 公開（公告）日: 2015-07-15
• 發明（設計）人: 葛洪偉;張濤;蘇樹智;楊金龍
• 申請（專利權）人: 江南大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明屬于聚類分析技術領域，涉及譜聚類中改進親合矩陣的構造方法。具體地說是一種基于局部密度和測地距離的分層譜聚類方法，可用于圖像分割、文本挖掘、機器學習等領域。

背景技術

譜聚類算法主要是對數據對象進行分析處理，將其分為多個簇，同一個簇內具有較高的相似性，不同簇間具有較低的相似性。譜聚類算法是建立在譜圖理論的基礎上，其本質就是將傳統的聚類問題轉換為圖的最優劃分問題。首先根據給定的數據集，計算親合矩陣(相似度矩陣)以描述數據點之間的相似性，并計算規范化的拉普拉斯矩陣的特征值和特征向量，通過選擇合適的特征向量對不同的數據點進行聚類。傳統的聚類分析方法(如k-means算法、EM算法等)，是建立在凸球形的樣本空間，不適用于任意形狀的樣本空間聚類，算法容易陷入局部最優；而譜聚類算法只與樣本的個數有關，與數據樣本的維數無關，能夠識別任意形狀的樣本空間且能收斂全局最優，因此被廣泛應用于計算機視覺、圖像分割、文本挖掘、VISI設計、語音識別、機器學習等領域。

近年來，Shi和Malik根據譜圖理論建立了基于2-way劃分的規范割(Ncut)目標函數，設計用于圖像分割的譜聚類算法。經Ng等人研究，發展成為k-way劃分的NJW算法。這些算法中都是采用歐氏距離決定的高斯核函數作為相似度矩陣，其中核參數需要人工確定增加了算法的不確定性；同時采用歐氏距離的方法很難反應樣本之間真實的相似關系，尤其是對具有復雜分布結構的任意形狀的數據集而言，無法有效的表示類內和類間的相似性。

在相似度方面的研究，目前出現了許多改進的方法，如自調節的譜聚類方法(簡稱STSC，參見：Zelnik-Manor?L,Perona?P.《Self-tuning?spectral?clustering》，Advances?in?neural?information?processing?systems.2004:1601-1608)、基于流行排序定義親和圖的方法(簡稱ROM-MSC，參見：Xia?T,Cao?J,Zhang?Y,et?al.《On?defining?affinity?graph?for?spectral?clustering?through?ranking?on?manifolds》.Neurocomputing,2009,72(13):3203-3211)。2014年Yan等人提出了基于密度敏感距離測度和歐氏距離的相似函數，其中需要計算最短路徑的密度敏感距離測度相似性函數的譜聚類方法(簡稱DSSC，參見：Yan?J,Cheng?D,Zong?M,et?al.《Improved?Spectral?Clustering?Algorithm?Based?on?Similarity?Measure》，Advanced?Data?Mining?and?Applications.Springer?International?Publishing,2014:641-654)通過放大不同高密度區域內數據點間距離，同時縮短同一高密度區域內數據點間距離，發現復雜數據分布的空間特征；這些方法雖然在一定程度上改善了譜聚類方法的聚類性能，但并未能解決粘連數據集如何構造相似度矩陣問題。傳統的測地距離采用K近鄰圖計算方法，當K值較小的時候，將原來流形結構分為多個不連通的子流形結構；K值過大又會導致不同類間具有較強連通性。所以當樣本點的K個近鄰點大部分是同類內的點，測地距離可以更好的反映樣本的分布；當存在樣本點的K個近鄰點中大部分屬于不同類的時候，測地距離無法有效的反映不同類間的真實關系。因此，在解決粘連數據集聚類問題時，基于傳統測地距離計算的譜聚類(Spectral?clustering?based?on?geodesic?distance，簡稱GSC)和DSSC等譜聚類方法都無法獲取良好的效果。

發明內容

本發明的目的在于克服上述背景技術中存在的問題，提出一種基于局部密度和測地距離的分層譜聚類方法，通過對局部密度有向圖剪枝生成的邊緣點和非邊緣點構造無向連通圖，并計算測地距離和相似度矩陣，使得聚類結果更加準確。尤其針對粘連數據集時，其優勢更加明顯。

實現本發明的技術關鍵是：一種基于局部密度和測地距離的分層譜聚類方法。具體實現步驟包括如下：

(1)輸入數據集X＝{x₁,x₂,...,x_n}∈R^d，x_n表示數據集中的第n個樣本，n為樣本個數，d為樣本維數；

(2)局部密度計算：