一種面向高維數(shù)據(jù)的密度峰值聚類模型

蔡旭芬，靳聰，胡飛，張勤

(中國(guó)傳媒大學(xué) 信息工程學(xué)院，北京 100024)

?

一種面向高維數(shù)據(jù)的密度峰值聚類模型

蔡旭芬，靳聰，胡飛，張勤

(中國(guó)傳媒大學(xué) 信息工程學(xué)院，北京 100024)

聚類是大數(shù)據(jù)時(shí)代對(duì)海量數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘與分析的重要工具。本文基于密度峰值聚類算法提出了針對(duì)高維數(shù)據(jù)的聚類模型，以直接簡(jiǎn)單的形式實(shí)現(xiàn)六維度以上數(shù)據(jù)的任意形狀聚類。該模型實(shí)現(xiàn)了自動(dòng)預(yù)處理過(guò)程，以局部密度較大且距離其他局部密度較大點(diǎn)較遠(yuǎn)的點(diǎn)作為聚類中心，最后引入?yún)?shù)調(diào)整。實(shí)驗(yàn)結(jié)果表明，該模型不僅對(duì)低維數(shù)據(jù)聚類實(shí)用，在高維數(shù)據(jù)的聚類效果也非常顯著。

高維；密度峰值；聚類中心；數(shù)據(jù)挖掘

1 引言

聚類是對(duì)物體或抽象對(duì)象的集合分成由類似的對(duì)象組成的多個(gè)類，在數(shù)據(jù)挖掘領(lǐng)域發(fā)揮重要作用，同時(shí)也獲得了研究機(jī)構(gòu)與學(xué)者的廣泛關(guān)注。前人在聚類算法這一領(lǐng)域也做出了重要貢獻(xiàn)。如傳統(tǒng)的聚類算法中，K-means算法和K-medoids算法[1]原理容易理解，實(shí)現(xiàn)也方便快捷，但不足之處是對(duì)異常值較為敏感；層次聚類算法[2]和劃分式聚類算法[3]聚類快，但僅適用于凸形的聚類簇；DBSCAN算法(Density-based Spatial Clustering of Applications with Noise)[6]和OPTICS算法(Ordering Points to identify the clustering structure)[7]這類基于密度聚類的算法恰恰解決了以上兩類算法的缺陷。相比于通常用距離聚類中心的距離和來(lái)不斷優(yōu)化的算法[4][5]，基于密度的聚類算法采取一種更巧妙地方是：在整個(gè)樣本空間點(diǎn)中，各目標(biāo)類簇是由一群的稠密樣本點(diǎn)組成的，而這些稠密樣本點(diǎn)被低密度區(qū)域(噪聲)分割，而算法的目的就是要過(guò)濾低密度區(qū)域，發(fā)現(xiàn)稠密樣本點(diǎn)。DBSCAN算法將簇定義為密度相連的點(diǎn)的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在噪聲的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的聚類，但該算法對(duì)初始參數(shù)過(guò)于敏感。OPTICS算法克服了DBSCAN算法存在的問題得到了更好的結(jié)果，但該算法的問題在于實(shí)現(xiàn)很復(fù)雜，實(shí)踐應(yīng)用中操作性不強(qiáng)。文獻(xiàn)[8]提出了密度峰值聚類(density peak cluster，DPC)算法巧妙地避免了以上問題，以一種更為直接簡(jiǎn)潔的方式完成了聚類。然而，該算法只在低維數(shù)據(jù)上有著優(yōu)越的性能，但隨著數(shù)據(jù)維數(shù)的增加，聚類效果急劇下降。因此，本文基于密度峰值聚類算法提出了針對(duì)高維數(shù)據(jù)的聚類模型，以直接簡(jiǎn)單的形式實(shí)現(xiàn)六維度以上數(shù)據(jù)的任意形狀聚類。該模型實(shí)現(xiàn)了自動(dòng)預(yù)處理過(guò)程，以局部密度較大且距離其他局部密度較大點(diǎn)較遠(yuǎn)的點(diǎn)作為聚類中心，最后引入?yún)?shù)調(diào)整。

2 密度峰值聚類

密度峰值聚類(DPC)算法本質(zhì)上屬于密度算法。其基本思想是假設(shè)要求每一類的中心由一些局部密度比較低的點(diǎn)包圍，并且這些點(diǎn)距離其他局部密度高的點(diǎn)的距離較大。

2.1 密度聚類算法

假設(shè)有n個(gè)樣本點(diǎn){1，2，3，…，n}，構(gòu)造距離矩陣D，

(1)

其中dij表示點(diǎn)i和點(diǎn)j的距離。然后，定義樣本點(diǎn)i局部密度：

(2)

且

(3)

其中，dc是一個(gè)自定義閾值(thresh)，點(diǎn)i的局部密度即為所有距離點(diǎn)i的距離小于該閾值的點(diǎn)的個(gè)數(shù)。該閾值的選取，直接決定了局部密度的大小。

另外，定義關(guān)于點(diǎn)i的函數(shù)δ：

ii.否則δi=max{dij}

此時(shí)，δ即為所有局部密度比其大的點(diǎn)與該點(diǎn)的最小距離。聚類中心的選取基于以下一個(gè)簡(jiǎn)單的原則：聚類中心的局部密度較大，且距離其他聚類中心較遠(yuǎn)。計(jì)算出所有樣本點(diǎn)的局部密度值ρ和δ之后，選取其中δ較大且ρ局部較大的點(diǎn)為聚類中心(cluster centers)。由算法的假設(shè)，可以知道，局部密度最大的點(diǎn)是一個(gè)中心點(diǎn)。在確定了聚類中心之后，其它樣本點(diǎn)按照距離已判斷點(diǎn)的點(diǎn)的集合從近到遠(yuǎn)依次判斷該點(diǎn)的所屬的類別；判斷的準(zhǔn)則為每個(gè)點(diǎn)的類別為該點(diǎn)鄰域內(nèi)最近的局部密度高于該點(diǎn)的點(diǎn)的所屬的類別。

2.2 面向高維數(shù)據(jù)的密度聚類模型

本文提出的面向高維數(shù)據(jù)的密度聚類模型包括三個(gè)部分。首先是進(jìn)行自動(dòng)預(yù)處理選取初始聚類中心，實(shí)現(xiàn)方法為歸一化ρ、δ，計(jì)算μ=ρ*δ，找出μ高于均值一個(gè)方差的異常點(diǎn)作為初始的聚類中心；然后進(jìn)行聚類，最后進(jìn)行參數(shù)調(diào)整，修正異常點(diǎn)。具體步驟如圖1所示。

圖1 密度聚類步驟

數(shù)據(jù)初始化后模型開始計(jì)算距離矩陣，確定相應(yīng)的閾值thresh。然后再計(jì)算所有點(diǎn)的ρ、δ并對(duì)ρ、δ進(jìn)行歸一化，找出δ*ρ大于平均值一個(gè)標(biāo)準(zhǔn)差的點(diǎn)作為初始的聚類中心；再對(duì)聚類中心作近鄰合并，標(biāo)識(shí)分類；按照距離已分類點(diǎn)的遠(yuǎn)近，由近到遠(yuǎn)逐個(gè)標(biāo)記分類；最后修正標(biāo)注ρ較小，δ較大的異常點(diǎn)，合并相近的類。

通過(guò)所提出的模型推理本文還得到了局部密度最大的點(diǎn)必定滿足δ局部最大這一結(jié)論，證明如下。

命題 設(shè)r為鄰域的閾值。對(duì)于任意k∈{k，dik

故δk<δi，證畢。

事實(shí)上，由該命題的證明過(guò)程我們可以發(fā)現(xiàn)，局部密度最大的點(diǎn)的δ大于所有非局部密度最大點(diǎn)的δ。故而δ已經(jīng)足夠能夠反映出該聚類中心的選取方法，故而聚類中心的選取只需要考慮δ即可。

本文選取了文獻(xiàn)[8]提供的聚類數(shù)據(jù)庫(kù)使用該模型對(duì)二維數(shù)據(jù)進(jìn)行測(cè)試結(jié)果如圖2所示。其中閾值按照所提出的條件選?。核悬c(diǎn)的平均近鄰數(shù)量為總個(gè)數(shù)的1%到2%之間。圖2(a)的數(shù)字分別表示二維點(diǎn)局部密度從大到小的順序，圖2(b)為所有點(diǎn)的density-delta圖，橫軸表示局部密度，縱軸表示δ。在圖2(b)中，點(diǎn)1和點(diǎn)10同時(shí)有較高的δ，又有局部較高的密度，故選為聚類中心點(diǎn)。對(duì)于未賦值的點(diǎn)2，距離點(diǎn)2最近的密度高于該點(diǎn)的點(diǎn)為點(diǎn)1，故點(diǎn)2的類別標(biāo)記為與1點(diǎn)相同。

(a) (b)圖2 二維數(shù)據(jù)集聚類

定義邊界區(qū)域包含屬于該類但是距離其他類的點(diǎn)的距離小于閾值的點(diǎn)。令一類邊界區(qū)域的局部密度最大的點(diǎn)的局部密度為ρb，該類中所有局部密度大于ρb的點(diǎn)被認(rèn)為可靠性的點(diǎn)，其余的點(diǎn)被認(rèn)為是異常點(diǎn)，也就是噪音。

3 實(shí)驗(yàn)結(jié)果與分析

本文提供了數(shù)據(jù)獲取方法和數(shù)據(jù)集，闡述了實(shí)驗(yàn)搭建環(huán)境及實(shí)驗(yàn)設(shè)置，并展示了實(shí)驗(yàn)結(jié)果與分析。

3.1 實(shí)驗(yàn)搭建

本文實(shí)驗(yàn)環(huán)境是在一臺(tái)linux操作系統(tǒng)臺(tái)式機(jī)電腦基于Matlab平臺(tái)實(shí)現(xiàn)的。系統(tǒng)配置為6核Intel Xeon Processor X4860，CPU 2.26 GHz 64 GB內(nèi)存。本文的實(shí)驗(yàn)中，還利用了爬蟲技術(shù)在真實(shí)網(wǎng)絡(luò)環(huán)境中爬取了大量的基于web的消費(fèi)者月消費(fèi)水平數(shù)據(jù)，對(duì)本文提出的模型進(jìn)行測(cè)試。該數(shù)據(jù)包含多個(gè)維度的數(shù)據(jù)信息，通過(guò)該模型對(duì)各個(gè)維度信息的分析可以很好地指導(dǎo)實(shí)際應(yīng)用中如對(duì)廣告精準(zhǔn)投放、客戶定向推薦等。

3.2 實(shí)驗(yàn)結(jié)果

本文實(shí)驗(yàn)根據(jù)不同歸一化處理方法進(jìn)行數(shù)據(jù)的DPC聚類，其中作z-score歸一化處理可以將數(shù)據(jù)轉(zhuǎn)換成正態(tài)分布的數(shù)據(jù)。當(dāng)對(duì)數(shù)據(jù)只作z-score歸一化處理時(shí)效果不好；只作數(shù)據(jù)線性歸一化處理效果不好；先作線性歸一化再做z-score處理效果也不好；作對(duì)數(shù)處理，效果得到改善。在對(duì)數(shù)據(jù)進(jìn)行逐步分析，其中出現(xiàn)了一類點(diǎn)，該類中有相當(dāng)?shù)狞c(diǎn)局部密度遠(yuǎn)高于其他的局部密度，這導(dǎo)致了其δ盡管小于其他點(diǎn)，μ依然較大，使得部分聚類中心的μ不在均值的一個(gè)標(biāo)準(zhǔn)差之上。實(shí)驗(yàn)擴(kuò)大聚類中心的尋找范圍，調(diào)整減小初始聚類中心選擇條件中的下限限定，聚類可以得到明顯的變化。但是在對(duì)源數(shù)據(jù)作相關(guān)實(shí)驗(yàn)時(shí)候，對(duì)權(quán)重作小幅度調(diào)整的時(shí)候?qū)垲惤Y(jié)果并無(wú)影響。也就是說(shuō)在部分?jǐn)?shù)據(jù)中均值加一個(gè)標(biāo)準(zhǔn)差已經(jīng)足夠選取到合適的中心點(diǎn)。圖3為六維數(shù)據(jù)局部密度圖。而且該模型對(duì)于處理非凸包類型的數(shù)據(jù)聚類效果顯著。聚類效果如圖4所示。

圖3 六維數(shù)據(jù)局部密度-δ圖

(a)三維數(shù)據(jù)集聚類 (b)六維數(shù)據(jù)集聚類

(c)七維數(shù)據(jù)集聚類 (d)七維以上數(shù)據(jù)集聚類圖4 數(shù)據(jù)集各維數(shù)聚類效果

4 結(jié)論

本模型在對(duì)各種高維數(shù)據(jù)非規(guī)則圖形聚類的處理效果良好，但是要注意該算法的前提：每一類的中心由一些局部密度比較低的點(diǎn)包圍，并且這些點(diǎn)距離其他局部密度高的點(diǎn)的距離較大。該模型還存在的問題是對(duì)于不同類別數(shù)量級(jí)差別較大的聚類效果不夠理想，有待進(jìn)一步研究與改進(jìn)。

[1]Luncien M，Cam L，Neyman J.Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability[J].University of California，1967.

[2]Johnson S C.Hierarchical clustering schemes[J].Psychometrika，1967，32(3)：241-254.

[3]Hand D J，Mannila H，Smyth P.Principles of data mining[M].MIT press，2001.

[4]Frey B J，Dueck D.Clustering by passing messages between data points[J].Science，2007，315(5814)：972-976.

[5]H?ppner F.Fuzzy cluster analysis：methods for classification，data analysis and image recognition[J].John Wiley & Sons，1999.

[6]Ester M，Kriegel H P，Sander J，Xu X.Density-based spatial clustering of applications with noise[J].In Int Conf Knowledge Discovery and Data Mining，Vol 240，1996.

[7]Ankerst M，Breunig M M，Kriegel H P，Sander J.OPTICS：ordering points to identify the clustering structure[J].In ACM Sigmod Record，28(2)：49-60，1999.

[8]Rodriguez A，Laio A.Clustering by fast search and find of density peaks[J].Science，2014，344(6191)：1492-1496.

[9]Fu L，Medico E.FLAME，a novel fuzzy clustering method for the analysis of DNA microarray data[J].BMC bioinformatics，2007，8(1)：3.

[10]Zahn C T.Graph-theoretical methods for detecting and describing gestalt clusters[J].Computers，IEEE Transactions on，1971，100(1)：68-86.

[11]Chang H，Yeung D Y.Robust path-based spectral clustering[J].Pattern Recognition，2008，41(1)：191-203.

(責(zé)任編輯：宋金寶)

A High Dimension Data Based Density Peak Cluster Model

CAI Xu-fen，JIN Cong，HU Fei，ZHANG Qin

(Information Engineering School，Communication University of China，Beijing 100024，China)

Clustering is an important tool for data mining and analysis for massive data in big data era.This paper proposes a clustering model in terms of high dimension data based on density peak cluster algorithm and realizes clustering data above six dimension with arbitrary shape simply and directly.This model achieves automatically pre-process and takes local points with larger density and far away from other local points as the clustering center followed by introducing the fine-tuning.Experimental results suggest that our model not only work for low dimension data，but also achieving promising performance for high dimension data.

high dimension；density peak；clustering center；data mining

2016-03-04

蔡旭芬(1989-)，女(漢族)，湖北咸寧人，中國(guó)傳媒大學(xué)媒介音視頻教育部重點(diǎn)實(shí)驗(yàn)室博士研究生， E-mail：xufen.cai.whu@gmail.com.

TM153

A

1673-4793(2016)05-0029-05