基于流形距離的密度峰值快速搜索聚類算法

張嘉琪　張紅云

摘要：針對2014年6月發(fā)表在Science上的基于密度峰和快速搜索的聚類算法容易忽略無密度極值的簇的缺陷，提出了一種基于流形距離的密度峰值快速搜索聚類算法。算法利用流形距離彌補(bǔ)了傳統(tǒng)歐式距離對于復(fù)雜數(shù)據(jù)無法反應(yīng)聚類的全局一致性（即位于同一個(gè)類中的樣本點(diǎn)之間有較高的相似度）的缺陷，通過近鄰點(diǎn)充分挖掘復(fù)雜數(shù)據(jù)的流形結(jié)構(gòu)信息，使處于同一個(gè)流形中的樣本點(diǎn)之間相似性較高，從而正確找到密度極值點(diǎn)作為聚類中心點(diǎn)，完成聚類。本文算法能夠發(fā)現(xiàn)較復(fù)雜的流形結(jié)構(gòu)，在公開數(shù)據(jù)集上能取得較好的實(shí)驗(yàn)結(jié)果。

關(guān)鍵詞： 聚類；流形距離；密度極值；全局一致性；聚類中心

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）02-0179-04

Clustering by Fast Search and ?nd of Density Peaks Based on Manifold Distance

ZHANG Jia-qi1，2，ZHANG Hong-yun1，2

（1.Department of Computer Science and Technology， Tongji University， Shanghai 201804， China；2.Key Laboratory of Embedded Systems and Service Computing，Ministry of Education，Tongji University，Shanghai 201804， China）

Abstract：The clustering algorithm based on density peak and fast search， which was published on Science in June 2014， is easy to ignore the cluster which has no density extreme value.So We propose an algorithm based on manifold distance to solve this problem.Instead of Euclidean distance，the algorithm uses manifold distance to reflect the global consistency of samples，which means the samples in the same cluster have high similarity.We find manifold structure information of complex data by neighbor points ，so that samples in the same manifold have high similarity and the cluster center is easy to find. In this paper， we can find manifold structure of complex data， and obtain better results in the open data sets.

Key words：clustering；manifold distance；density peak； global consistency；clustering center

1 概述

聚類作為一種有效的數(shù)據(jù)分析手段，已成為模式識(shí)別，人工智能，數(shù)據(jù)挖掘等領(lǐng)域的研究熱點(diǎn)。在聚類分析過程中，不需要任何先驗(yàn)知識(shí)或者是假設(shè)，因此聚類是一種無監(jiān)督學(xué)習(xí)過程。聚類算法包括劃分式聚類方法、層次聚類方法、基于密度的聚類方法和基于網(wǎng)格的聚類方法，以及基于模型的聚類算法.K-means[1]是應(yīng)用范圍最廣的劃分式聚類算法.然而，K-means算法的聚類結(jié)果依賴于初始類簇中心的選取，而且傾向于發(fā)現(xiàn)凸形狀的簇，對噪聲點(diǎn)和離群點(diǎn)敏感，且聚類個(gè)數(shù)K需要事先設(shè)定.針對K-means的缺陷，出現(xiàn)了K-modes[2]算法等諸多改進(jìn)算法. DBSCAN[3]是一種比較典型的基于密度的聚類方法，要求聚類空間中的一定區(qū)域內(nèi)所包含對象（點(diǎn)或其他空間對象）的數(shù)目不小于某一給定閾值。DBSCAN算法的顯著優(yōu)點(diǎn)是聚類速度快且能夠有效處理噪聲點(diǎn)和發(fā)現(xiàn)任意形狀的空間聚類，與K-MEANS比較起來，不需要輸入要?jiǎng)澐值木垲悅€(gè)數(shù)。近鄰傳播聚類算法AP（affinity propagation）[4]將所有樣本看作網(wǎng)絡(luò)中的一個(gè)頂點(diǎn)，通過反復(fù)迭代交換近鄰樣本間的信息，尋找最優(yōu)的類代表點(diǎn)樣本集合，使所有樣本與最近類代表點(diǎn)樣本的相似度之和最大，發(fā)現(xiàn)數(shù)據(jù)集樣本的類簇分布.AP算法具有簡單、高效的優(yōu)點(diǎn)，特別是在類別數(shù)目較多情況下，該算法具有非常好的聚類效果，但是該算法不能發(fā)現(xiàn)任意形狀的簇. 基于層次的有CURE[5]、ROCK[6]、BIRCH[7]。層次的方法的缺陷在與錯(cuò)誤的累積，它不能更正錯(cuò)誤的決定。但是它能發(fā)現(xiàn)非凸的數(shù)據(jù)分布。

2014年6月Science發(fā)表了自動(dòng)確定類簇?cái)?shù)和類簇中心的新聚類算法CFSFDP （clustering by fast search and find of density peaks）[8]，該算法能快速發(fā)現(xiàn)任意形狀數(shù)據(jù)集的密度峰值點(diǎn)（即類簇中心），并高效進(jìn)行樣本點(diǎn)分配和離群點(diǎn)剔除，適用于大規(guī)模數(shù)據(jù)的聚類分析.但是該算法容易忽略不存在密度極值點(diǎn)的簇，導(dǎo)致該類簇被劃分到其他類中，造成錯(cuò)誤的聚類結(jié)果。

鑒于此，本文提出一種采用流形距離的密度峰值快速搜索聚類算法，利用流形距離來保證同一個(gè)簇中的樣本點(diǎn)相似性高，從而使每個(gè)簇中都存在密度極值，使算法能夠準(zhǔn)確發(fā)現(xiàn)簇中的聚類中心點(diǎn)，并完成聚類。

2 CFSFDP

CFSFDP是2014年發(fā)表在Science雜志上的一種聚類算法，因?yàn)樗乃枷牒啙崈?yōu)美，提出之后就受到了廣泛的關(guān)注。該算法的核心思想在于對聚類中心的確定上，作者認(rèn)為聚類中心同時(shí)具有以下兩點(diǎn)特征：

1.本身的密度大，周圍點(diǎn)的密度比他小

2.與其他密度更大的點(diǎn)的距離相對更大

因此為每個(gè)樣本點(diǎn)都引入兩個(gè)屬性：局部密度[ρi]和距離[δi]，由公式（1）（2）計(jì)算獲得。

[ρi=j∈IS＼{i}e-（dijdc）2] （1）

[δi=minj∈IiS{dij}，IiS不為空maxj∈IS{dij}，IiS為空] （2）

[IS]表示所有樣本點(diǎn)的下標(biāo)序號(hào)，[IiS]表示所有密度大于點(diǎn)i的樣本點(diǎn)的下標(biāo)序號(hào)。[dc]表示鄰域大小，根據(jù)所有點(diǎn)與點(diǎn)的歐式距離小于[dc]的占總樣本數(shù)的k%來確定，k為我們需要輸入的參數(shù)。[dij]表示兩個(gè)樣本點(diǎn)的歐式距離。如公式（1），（2）所示，對于局部密度[ρi]，該算法用高斯核來進(jìn)行密度的計(jì)算，用點(diǎn)i到比點(diǎn)i密度高的所有點(diǎn)的最短距離表示[δi]。

如圖1所示，圖1（a）是樣本集，樣本集的序號(hào)按照密度的大小降序排列，圖1（b）為以兩個(gè)屬性為橫縱坐標(biāo)的決策圖，顯然點(diǎn)1和點(diǎn)10為聚類中心。對于剩下的點(diǎn)，點(diǎn)的類別標(biāo)簽與高于當(dāng)前點(diǎn)密度的最近的點(diǎn)的標(biāo)簽一致。從而對所有點(diǎn)的類別進(jìn)行了指定。而且該算法利用臨界密度很好的過濾掉噪音點(diǎn)。

該算法僅需要輸入確定鄰域的參數(shù)k，且時(shí)間復(fù)雜度較K-means低，能識(shí)別部分復(fù)雜分布的樣本點(diǎn)，在人臉識(shí)別上也取得了較好的實(shí)驗(yàn)結(jié)果。但是該算法的有效性建立在一個(gè)隱性的假設(shè)，即數(shù)據(jù)集中屬于同一個(gè)類的數(shù)據(jù)點(diǎn)的密度分布有且僅有一個(gè)極值。倘若數(shù)據(jù)分布不含有這一特征，相對稀疏的類的聚類中心則容易被淹沒，例如圓環(huán)型數(shù)據(jù)集，CFSFDP就會(huì)得到錯(cuò)誤的結(jié)果[9]。

3 基于流形距離的相似性度量方法

在復(fù)雜數(shù)據(jù)聚類問題，由于數(shù)據(jù)的分布通常具有不可預(yù)期的復(fù)雜結(jié)構(gòu)，導(dǎo)致了傳統(tǒng)的基于歐氏距離相似性度量的聚類算法無法反映聚類的全局一致性（即位于同一流形上的數(shù)據(jù)點(diǎn)具有較高的相似性）.從圖2所示的例子中可以看出，在用歐式距離衡量樣本點(diǎn)之間的相似性時(shí)候，樣本點(diǎn)A與樣本點(diǎn)C的相似性要比樣本點(diǎn)A與樣本點(diǎn)B的相似性更大.因此A與C劃分到同一類的概率是要大于A與B劃分到同一類的概率的。但是，顯而易見，A與B是屬于同一個(gè)流形，也就是說A與B是屬于同一類的，用歐氏距離作為相似性度量根本無法反映圖中所示數(shù)據(jù)的全局一致性.因此，對于現(xiàn)實(shí)世界中復(fù)雜的聚類問題，簡單地采用歐氏距離作為相似性度量會(huì)嚴(yán)重影響聚類算法的性能。

流行距離又叫做測地距離（Geodesic distance），Isomap[10]降維算法為了在低維空間下保留數(shù)據(jù)在高維空間的相似性，引入了測地距離的概念。測地距離的基本思想是：當(dāng)兩點(diǎn)非常接近（k近鄰點(diǎn)）時(shí)，測地距離等于歐式距離，而當(dāng)兩點(diǎn)相對較遠(yuǎn)的時(shí)候，測地距離則根據(jù)近鄰點(diǎn)之間測地距離的累加實(shí)現(xiàn)，是一種迭代的距離度量方法[10]。例如圖2的聚類問題，若采用測地距離作為相似性度量的方法，A可以通過若干個(gè)k近鄰點(diǎn)迭代的計(jì)算與B之間的相似度，而與C的相似度為無窮小的，這種相似性度量方法比直接采用歐氏距離更加合理。

測地距離的計(jì)算過程如下[10]：

1.定義鄰域大小n，根據(jù)鄰域大小構(gòu)造測地距離

2.每個(gè)樣本與自己的n近鄰點(diǎn)的距離為歐氏距離，與其余點(diǎn)的距離為無窮大。即：

[dG（xi，xj）=dE（xi，xj），若xi，xj為近鄰∞，若xi，xj不為近鄰] （3）

3.使用其他點(diǎn)為媒介，計(jì)算每個(gè)樣本與其他所有點(diǎn)的距離：

[dG（xi，xj）=mindG（xi，xj），dG（xi，xt）+dG（xt，xj）] （4）

4 基于流形距離的密度峰值快速搜索聚類算法

流形距離能放大類間差異，使同一個(gè)流形上的樣本點(diǎn)能有更大的概率被劃分到同一類上，同時(shí)也保證了同一個(gè)流形上的樣本點(diǎn)有更高的相似性，也就是說流形上存在密度極值點(diǎn)。為了能使CFSFDP聚類算法能夠發(fā)現(xiàn)在歐式空間下容易被忽略的聚類中心，本文在原有CFSFDP聚類思想的基礎(chǔ)上，提出了一種基于流形距離的密度峰值快速搜索聚類算法，具體步驟如下：

輸入：高斯核參數(shù)[σ]，CFSFDP算法鄰域參數(shù)k，樣本點(diǎn)

輸出：聚類結(jié)果

第一步：近鄰個(gè)數(shù)可取3到6個(gè)[1]，計(jì)算第3節(jié)的流行距離，用高斯核計(jì)算點(diǎn)與點(diǎn)之間的相似度，獲得樣本點(diǎn)的相似度矩陣[A∈Rn×n]，對角線上的元素Aii = 0。

[Aij=e-dG（xi，xj）22σ2] （5）

第二步：按照公式（1）（2）計(jì)算每個(gè)樣本點(diǎn)的密度和距離屬性。

第三步：將每個(gè)點(diǎn)繪制到以密度為橫坐標(biāo)，距離為縱坐標(biāo)的坐標(biāo)軸上，根據(jù)第2節(jié)CFSFDP的步驟選取聚類中心。

第四步：對于剩下的點(diǎn)，點(diǎn)的類別標(biāo)簽與高于當(dāng)前點(diǎn)密度的最近的點(diǎn)的標(biāo)簽一致。

5 實(shí)驗(yàn)結(jié)果及分析

5.1 有效性實(shí)驗(yàn)

為了驗(yàn)證算法的有效性，采用公開數(shù)據(jù)集Jain，Pathbased，Spiral和人工數(shù)據(jù)集同心圓對算法進(jìn)行檢驗(yàn)。在相似性計(jì)算時(shí)，近鄰個(gè)數(shù)n根據(jù)文獻(xiàn)[12]取3，高斯核參數(shù)[σ]根據(jù)經(jīng)驗(yàn)取5，CFSFDP算法鄰域參數(shù)k取20。

如圖3所示，本文算法對于復(fù)雜分布的流形結(jié)構(gòu)都能取得正確的聚類結(jié)果。這是因?yàn)榱餍尉嚯x根據(jù)結(jié)構(gòu)信息使同一個(gè)流形中的樣本點(diǎn)相似性更加真實(shí)。每個(gè)簇中都存在密度極值點(diǎn)，便于CFSFDP算法發(fā)現(xiàn)該簇中的聚類中心點(diǎn)，彌補(bǔ)了在歐氏距離下容易忽略某些聚類中心的缺陷。

5.2 對比性實(shí)驗(yàn)

對比CFSFDP聚類算法，同樣利用四種數(shù)據(jù)集進(jìn)行對比性實(shí)驗(yàn)。實(shí)驗(yàn)需要使用的參數(shù)與5.1節(jié)一致。

（a） 3 circle

（b）pathbased

（c） spiral

（d）jain

圖4 CFSFDP算法實(shí)驗(yàn)結(jié)果

如圖4所示，CFSFDP較難在此類分部復(fù)雜的數(shù)據(jù)集上取得正確的聚類結(jié)果。這是因?yàn)樵谟脷W式距離衡量相似性的時(shí)候，該算法還是傾向于發(fā)現(xiàn)球狀的簇，導(dǎo)致某些密度小的類簇聚類中心被忽略，造成錯(cuò)誤的聚類結(jié)果。

6 結(jié)論

本文將流形距離和CFSFDP算法相結(jié)合，提出一種能處理復(fù)雜分布數(shù)據(jù)的聚類算法，并通過對聚類效果進(jìn)行分析，得到了若干有指導(dǎo)意義的結(jié)論。與現(xiàn)有典型的聚類算法相比，本文提出的算法能準(zhǔn)確找到聚類中心，穩(wěn)定的取得較好的聚類效果，且時(shí)間復(fù)雜度與原算法一致，為聚類問題的研究提供了新的思路。但是本文算法會(huì)隨著設(shè)置的鄰域個(gè)數(shù)變大，會(huì)出現(xiàn)過連通的問題，也就是不同類之間的點(diǎn)也存在最短路徑，如何確定鄰域個(gè)數(shù)，是一個(gè)值得深入研究的課題。

參考文獻(xiàn)：

[1]吳夙慧，成穎，鄭彥寧，等. K-means算法研究綜述[J]. 現(xiàn)代圖書情報(bào)技術(shù)， 2011（5）：28-35.

[2]梁吉業(yè)，白亮，曹付元. 基于新的距離度量的K-Modes聚類算法[J].計(jì)算機(jī)研究與發(fā)展，2010（10）：1749-1755

[3]馮少榮，肖文俊. DBSCAN聚類算法的研究與改進(jìn)[J].中國礦業(yè)大學(xué)學(xué)報(bào)，2008（1）：105-111。

[4]Local and global approaches of affinity propagation clustering for large scale data[J]. Journal of Zhejiang University（Science A：An International Applied Physics & Engineering Journal），2008（10）：1373-1381.

[5]馮興杰，黃亞樓. 增量式CURE聚類算法研究[J]. 小型微型計(jì)算機(jī)系統(tǒng)，2004（10）：1847-1849.

[6]趙雪，陳龍飛.基于MapReduce的ROCK聚類算法[J].河北科技師范學(xué)院學(xué)報(bào)， 2014，28（1）：26-32.

[7]蔣盛益，李霞.一種改進(jìn)的BIRCH聚類算法[J].計(jì)算機(jī)應(yīng)用，2009，29（1）：293- 296.

[8]Alex Rodriguez，Alessandro Laio.Clustering by fast search and find of density peaks.Science 344，1492（2014）.

[9]張文開.基于密度的層次聚類算法研究[D].中國科學(xué)技術(shù)大學(xué)，2015.

[10]Tenenbaum J B，Silva V，Langford J C.A global geometric framework for nonlinear dimensionality reduction[J].Science，2000，290（12）：2319-2323.

[11]陶新民，宋少宇，曹盼東，等.一種基于流形距離核的譜聚類算法[J].信息與控制，2012，41（3）：307-313.

[12]Luxburg U.A tutorial on spectral clustering[J].Statistics and Computing，2007，17（4）：395-416.