李捷，陳雁彬

（重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶 400044）

0 引言

在數(shù)據(jù)挖掘中，聚類算法占據(jù)重要地位，它是按照一定的規(guī)律和方法對事物進(jìn)行區(qū)分和歸類[1]，而聚類算法細(xì)分為基于層次的聚類方法、基于劃分的聚類算法、基于密度的聚類算法與基于網(wǎng)格的聚類算法，基于密度的聚類算法是聚類中的一個重要的研究分支，相比于其他算法，基于密度的聚類算法可以在有噪聲的數(shù)據(jù)中發(fā)現(xiàn)各種形狀與各種大小的類別，DBSCAN[4]是該方法中最典型的代表算法之一，其核心思想是首先發(fā)現(xiàn)具有高密度的點(diǎn)，然后將相鄰近的高密度點(diǎn)逐步的連接在一起，進(jìn)而形成各種簇；由于DBSCAN算法使用的是全局的密度閾值MinPts，只能發(fā)現(xiàn)密度不少于MinPts的點(diǎn)組成的簇，無法發(fā)現(xiàn)不同密度的簇，為了解決這些問題，OPTICS[5]（Ordering Points to Identify the Clustering Structure）算法將鄰域點(diǎn)按照密度大小進(jìn)行排序，最后使用可視化的方法來發(fā)現(xiàn)不同密度的簇，然而該方法需要在可視化的圖上查找“山谷”，進(jìn)而發(fā)現(xiàn)簇，因此算法性能直接受到這些可視化方法的約束；SNN（shared Nearest Neighbor）算法采用一種基于KNN方式計(jì)算相似度的方法來改進(jìn)DBSCAN，其核心思想是在空間中找出離其最近的k個點(diǎn)，兩個點(diǎn)的相似程度使用這兩個點(diǎn)的k鄰域范圍中共享的近鄰數(shù)量來度量，然而SNN算法需要設(shè)定近鄰個數(shù)k，且該算法的性能對k的取值很敏感。

基于以上分析，考慮到數(shù)據(jù)集中可能存在不同形狀、不同密度的簇，本文提出一種使用自然鄰居算法進(jìn)行改進(jìn)的DBSCAN算法，以后稱作NN-DBSCAN算法，首先對整體數(shù)據(jù)集使用自然鄰居算法得出該數(shù)據(jù)集中點(diǎn)的鄰域分布情況，然后使用核心點(diǎn)選取算法篩選整體數(shù)據(jù)集，得出核心點(diǎn)，然后對核心點(diǎn)集再次使用自然鄰居算法，得出核心點(diǎn)之間的關(guān)系，接著每個核心點(diǎn)使用最大逆鄰居距離作為該點(diǎn)的鄰域半徑值，若兩個核心點(diǎn)的距離都在其對應(yīng)的鄰域半徑之內(nèi)，則兩個核心點(diǎn)屬于同一個類別，對篩選掉的點(diǎn)，算法采用第一次使用自然鄰居算法得到的核心點(diǎn)的最大逆鄰居距離來歸類。

1 自然鄰居搜索算法

1.1 自然鄰居

自然鄰居是一種新的鄰居概念，它記錄了在k鄰域范圍內(nèi)，存在多少個點(diǎn)將已知點(diǎn)當(dāng)作鄰居的信息，在此同時也記錄了該點(diǎn)與k個鄰居點(diǎn)集合中的互為鄰居點(diǎn)的信息[15]；由此可知，在數(shù)據(jù)集中分布較為稀疏的部分，數(shù)據(jù)點(diǎn)擁有較少的自然鄰居點(diǎn)，反之，在分布較為集中的部分，數(shù)據(jù)點(diǎn)將擁有較多的自然鄰居[3]。

1.2 自然鄰居搜索算法

自然鄰居的核心思想是在一個連續(xù)的搜索范圍內(nèi)，遞增鄰域范圍值k，每次遞增都會查找每個點(diǎn)的自然鄰居，直到所有點(diǎn)都有自然鄰居或者沒有自然鄰居的點(diǎn)的數(shù)量在一定搜索次數(shù)內(nèi)不再發(fā)生改變[3]。

算法1：自然鄰居搜索算法

輸入：數(shù)據(jù)集D

輸出：自然鄰居特征值supk，數(shù)據(jù)點(diǎn)自然鄰居數(shù)量nb，數(shù)據(jù)點(diǎn)自然鄰居記錄NN

初始化supk=1，nbi=0，NN0(i)=?，RNN0(i)=?

While true

Foreachpiin D

使用kdtree搜索 pi點(diǎn)的第supk近鄰 pj

更新pj點(diǎn)自然鄰居數(shù)量nbj=nbj+1

NNsupk(i)=NNsupk-1(i)∪{j}

RNNsupk(j)=RNNsupk-1(j)∪{i}

Endfor

計(jì)算沒有逆鄰居的點(diǎn)的數(shù)量Numb

IfNumb未反生改變

Break；

Endif

supk=supk+1

Endwhile

supk=supk-1

輸出supk，nb，NNsupk

自然鄰居搜索算法采用kd樹進(jìn)行索引，該算法時間復(fù)雜度為O(nlogn+nsupk)，且通過大量實(shí)驗(yàn)可知，自然鄰居特征值supk遠(yuǎn)小于數(shù)據(jù)集規(guī)模n（一般在1到30之內(nèi)），所以該算法的時間復(fù)雜度為O(nlogn)。

2 NN-DBSCAN算法描述

NN-DBSCAN算法分為三步，首先使用自然鄰居算法得出數(shù)據(jù)集的中每個數(shù)據(jù)點(diǎn)的鄰域信息，然后使用這些鄰域信息選取出核心點(diǎn)集合；然后再次使用自然鄰居算法對核心點(diǎn)進(jìn)行處理，得出核心點(diǎn)之間的鄰域信息，使用這些信息計(jì)算出每個核心點(diǎn)的鄰域半徑值，并將互相處于自身鄰域半徑值范圍內(nèi)的兩個核心點(diǎn)劃歸為同一類別；最后，對每個非核心點(diǎn)，使用第一次自然鄰居算法得出的鄰域半徑，找出和其互在自身鄰域半徑范圍內(nèi)的核心點(diǎn)，取這些核心點(diǎn)中最近的點(diǎn)的類別作為該點(diǎn)的類別，對沒有歸類的非核心點(diǎn)，算法判定為噪聲點(diǎn)。

2.1 基于自然鄰居算法的核心點(diǎn)選取算法

在聚類過程中，本文采取的鄰域半徑值ε為各個數(shù)據(jù)點(diǎn)到其所有自然鄰居的距離的最大值，這個值很大程度上會受到噪聲點(diǎn)的干擾，因此需要一步粗處理來去除這些干擾點(diǎn)；干擾點(diǎn)去除算法的核心是判斷數(shù)據(jù)點(diǎn)i的自然鄰居數(shù)量是否不小于其supk鄰域內(nèi)數(shù)據(jù)點(diǎn)的平均自然鄰居數(shù)量，若是，則將數(shù)據(jù)點(diǎn)i放入核心點(diǎn)集合中，否則去除。

算法2：核心點(diǎn)選取算法

輸入：數(shù)據(jù)集D

輸出：核心點(diǎn)集合Core

初始化Core=?

對原始數(shù)據(jù)集D使用自然鄰居搜索算法得到supk和nb

Foreachpiin D

sum=0

Forj=1tosupk

使用kdtree搜索 pi點(diǎn)的第 j近鄰 pq

sum=sum+nb(q)

Endfor

Ifnb(i)≥sum/supk

Core=Core∪{i}

Endif

Endfor

輸出Core

核心點(diǎn)選取算法能夠?qū)⒋氐拇蟛糠诌吘夵c(diǎn)和幾乎所有的噪聲點(diǎn)都篩除掉，既保留了原始數(shù)據(jù)集中簇的結(jié)構(gòu)，也過濾掉了噪聲點(diǎn)的干擾；其時間復(fù)雜度為O(nlogn+nsupklogn)，由于supk遠(yuǎn)小于n，所以最終復(fù)雜度為O(nlogn）。

2.2 核心點(diǎn)聚類算法

核心點(diǎn)聚類算法的核心是使用自然鄰居算法對篩選之后的數(shù)據(jù)點(diǎn)集合進(jìn)行處理，得出篩選點(diǎn)之間的鄰域關(guān)系，然后使用每個保留點(diǎn)的最大逆鄰居距離判斷兩個保留點(diǎn)是否屬于同一個簇，若兩個保留點(diǎn)互在其對應(yīng)最大逆鄰居距離范圍之內(nèi)，則兩個點(diǎn)屬于同一類別，算法描述如下：

算法3：核心點(diǎn)聚類算法

輸入：核心點(diǎn)集合Core

輸出：核心點(diǎn)聚類結(jié)果Clusters

初始化N=num(Core)，Clusters=1 to N，MaxDisti=0

對核心點(diǎn)集合Core使用自然鄰居算法，得到nb，NNsupk

Foreachpiin Core

ForeachpjinNNsupk(i)

dist=EuclideanDist(pi,pj)

IfMaxDisti

MaxDisti=dist

Endif

Endfor

Endfor

Foreachpiin Core

對Core創(chuàng)建 kdtree，找出Core中距離 pi小于 MaxDisti的點(diǎn)集合SpPoint

ForeachpjinSpPoint

dist=EuclideanDist(pi,pj)

Ifdist

Clusters(f ind(C lusters==Clusters(j) ))=Clusters(i)

Endif

Endfor

Endfor

輸出Clusters

2.3 非核心點(diǎn)聚類算法

核心點(diǎn)選擇算法去除了幾乎所有的噪聲點(diǎn)和大部分簇邊界點(diǎn)，因此還需要對被篩除的點(diǎn)進(jìn)一步做歸類，歸類非核心點(diǎn)的思想是利用第一次對整個數(shù)據(jù)集使用的自然鄰居算法得出的信息，計(jì)算非核心點(diǎn)的最大逆鄰居距離，然后找出在該距離內(nèi)的所有的核心點(diǎn)，接著判非核心點(diǎn)是否也在核心點(diǎn)最大逆鄰居距離范圍內(nèi)，最后取距離最小的互在最大逆鄰居范圍內(nèi)的保留點(diǎn)的類別為非核心點(diǎn)的類別，算法描述如下：

算法4：非核心點(diǎn)聚類算法

輸入：核心點(diǎn)類別Clusters，核心點(diǎn)最大逆鄰居距離MaxDisti，非核心點(diǎn)集合AddtPoint，非核心點(diǎn)自然鄰居記錄NNA，核心點(diǎn)集合Core，原始數(shù)據(jù)集D

輸出：數(shù)據(jù)集D的聚類結(jié)果AllClusters

初始化N=num(D)，AllClusters=zeros(1 ,N)，AN=num(AddtPoint)，AMaxDisti=0，AllClusters(Core)=Clusters

ForeachpiinAddtPoint

dist=0

ForeachpjinNNA(i)

Ifdist

dist=EuclideanDist(pi,pj)

endif

Endfor

AMaxDisti=dist

對核心點(diǎn)創(chuàng)建kdtree，搜索在AMaxDisti范圍內(nèi)的所有核心點(diǎn)集合Set

ClusterInd=0

MinDist=Infinity

ForeachpjinSet

dist=EuclideanDist( )pi,pj

Ifdist

MinDist=dist

ClusterInd=Clusters(j)

Endif

Endfor

IfClusterInd<>0

AllClusters()i=ClusterInd

Endif

Endfor

輸出AllClusters

其中未被歸類的點(diǎn)即被認(rèn)為是噪聲點(diǎn)。

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

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

表1前三列是實(shí)驗(yàn)所用到的數(shù)據(jù)集以及對應(yīng)的類別數(shù)目：

表1 數(shù)據(jù)集和實(shí)驗(yàn)結(jié)果對比

這里以數(shù)據(jù)集Da6、d31為例子進(jìn)行核心點(diǎn)選取和聚類，圖1是Da6數(shù)據(jù)集的散點(diǎn)圖，圖2是d31數(shù)據(jù)集散點(diǎn)圖。

圖1

圖2

使用算法2得到的核心點(diǎn)結(jié)果如下圖，其中圖3是Da6數(shù)據(jù)集的核心點(diǎn)散點(diǎn)圖，圖4是d31數(shù)據(jù)集的核心點(diǎn)散點(diǎn)圖，可以看出核心點(diǎn)集合保留了整體數(shù)據(jù)集簇狀結(jié)構(gòu)，極大地弱化了簇邊緣和噪聲點(diǎn)的影響。

圖3

圖4

使用算法3得到的核心點(diǎn)聚類結(jié)果如下圖，其中圖5是Da6數(shù)據(jù)集核心點(diǎn)的聚類結(jié)果，圖6是d31數(shù)據(jù)集核心點(diǎn)聚類結(jié)果。

使用算法4對非核心點(diǎn)進(jìn)行歸類結(jié)果如下圖，其中圖7是Da6數(shù)據(jù)集的聚類效果，圖8是d31數(shù)據(jù)集聚類效果，其中“+”表示噪聲點(diǎn)，結(jié)果中可以看出大量噪聲點(diǎn)都被算法識別了出來。

3.2 NNDBSCAN算法對數(shù)據(jù)集聚類性能

表1后兩列是NN-DBSCAN與DBSCAN算法在實(shí)驗(yàn)數(shù)據(jù)集上的聚類效果與正確率的對比，在circle2數(shù)據(jù)集上，兩個算法都能取得最好的聚類效果，但是DBSCAN需要設(shè)定適當(dāng)?shù)泥徲虬霃街岛袜徲蜷撝?；由于db4和jain數(shù)據(jù)集樣本數(shù)目較少，類別分布較為稀疏，核心點(diǎn)選取算法難以選取到合適的核心點(diǎn)；在d31數(shù)據(jù)集上，由于簇邊界密度比簇內(nèi)部密度相差太大，算法在聚類非核心點(diǎn)時便難以保證非核心點(diǎn)與同類核心點(diǎn)互在自身的鄰域半徑值內(nèi)；綜合聚類數(shù)目和正確率，NN-DBSCAN使用了自然鄰居算法，自適應(yīng)得到了核心點(diǎn)和鄰域半徑值，在消除人工設(shè)定參數(shù)的同時也保證了正確率。

4 結(jié)語

本文提出了一種通過自然鄰居算法改進(jìn)的DBSCAN算法，聚類過程中首先篩除會干擾整體聚類效果的點(diǎn)，然后再用自然鄰居算法對核心點(diǎn)進(jìn)行處理，得到核心點(diǎn)之間的鄰域關(guān)系，接著使用核心點(diǎn)的最大逆鄰居距離替代了DBSCAN的鄰域半徑值ε，自適應(yīng)的得到了每個點(diǎn)之間的鄰域半徑值，對原始DBSCAN算法中的鄰域半徑值參數(shù)進(jìn)行分析，實(shí)際上是兩個核心點(diǎn)的距離互在其對應(yīng)的鄰域半徑之內(nèi)，才能認(rèn)定兩個核心點(diǎn)屬于同一個類別，基于該原理，算法聚類時選擇了核心點(diǎn)之間的距離互在其最大逆鄰居距離范圍之內(nèi)才認(rèn)定兩個核心點(diǎn)屬于同一類別，通過實(shí)驗(yàn)也驗(yàn)證了該方法的有效性。

圖5

圖6

圖7

圖8

[1]孫吉貴,劉杰,趙連宇.聚類算法研究[J].軟件學(xué)報,2008,19(1):48-61.

[2]張瑩.基于自然最近鄰居的分類算法研究[D].重慶大學(xué),2015.

[3]程東東.基于自然鄰的層次聚類算法研究[D].重慶大學(xué),2016.

[4]Ester M,Kriegel H,Jiirg S,et al.A Density Based Algorithm for Discovering Clusters in Large Spatial Databases[J]，1996.

[5]Ordering Points To Identify the Clustering Structure[C].International Conference on Management of Data，1999.

[6]Li D F,Hu W C,He Y X.Classifier Based on Shared Nearest Neighbor Clustering and Fuzzy Set Theory[J].Control&Decision,2006,21(10):1103-1108.

[7]Kaufman L,Rousseeuw P J.Finding Groups in Data.An Introduction to Cluster Analysis[J].Wiley,1990.

[8]Kaufman L.Rousseeuw PJ:Finding Groups in Data:An Introduction to Cluster Analysis[J].Machine Design,1990,74.

[9]Romesburg,Charles H.Cluster Analysis for Researchers[M].Lifetime Learning publications,1984.

[10]Jain A K.Data Clustering:a Review[J].ACM Computing Surveys,2000,31(3):264-323.

[11]周水庚,周傲英,曹晶,等.一種基于密度的快速聚類算法[J].計(jì)算機(jī)研究與發(fā)展，2000，37(11):1287-1292.

[12]賀玲,吳玲達(dá),蔡益朝.數(shù)據(jù)挖掘中的聚類算法綜述[J].計(jì)算機(jī)應(yīng)用研究，2007,24(1):10-13.

[13]Jain A K,Dubes R C.Algorithms for Clustering Data[J].Technometrics,1988,32(2):227-229.

[14]朱慶生,陳治,張程.基于自然鄰居流形排序圖像檢索技術(shù)研究[J].計(jì)算機(jī)應(yīng)用研究,2016,33(4):1265-1268.

[15]段浪軍.基于自然鄰居和最小生成樹的原型選擇算法研究[J].計(jì)算機(jī)科學(xué),2017,44(4):241-245.