摘要??聚類算法對解決空間數(shù)據(jù)中的分類問題很有吸引力故觅，然而，大型空間數(shù)據(jù)對聚類算法產(chǎn)生了下列需求：減少輸入?yún)?shù)所需要的領(lǐng)域知識，對不規(guī)則形狀進(jìn)行聚類以及在大數(shù)據(jù)上的高效率聚類碰酝。目前廣為人知的聚類算法無法滿足上述需求胀滚。本文提出一種新的聚類方法趟济，叫做DBSCAN，是一個基于密度聚類的概念咽笼，可以用來解決不規(guī)則形狀的聚類問題顷编。DBSCAN只需要一個輸入?yún)?shù)且支持用戶自定義一個合適的值。我們用SEQUIOIA2000基準(zhǔn)集的合成數(shù)據(jù)以及真實數(shù)據(jù)對DBSCAN的有效性和效率進(jìn)行了評估剑刑。實驗結(jié)果證明（1）DBSCAN在不規(guī)則形狀聚類上的表現(xiàn)顯著優(yōu)于著名的CLARANS算法（2）DBSCAN就效率而言超過CLARANS 100倍媳纬。
2 Clustering Algorithms
有兩種基本類型的聚類：partitioning（分區(qū)）和hierarchical（分層）算法。
1.?Partitioning algorithms.?Partitioning algorithms構(gòu)建了一個數(shù)據(jù)集D的一個分區(qū)施掏，將它的n個物體分成k個集合钮惠。k是這些算法的輸入?yún)?shù)。
Partitioning algorithm通常開始于一個初始化的區(qū)塊D其监，然后用迭代控制策略優(yōu)化目標(biāo)函數(shù)萌腿，每個類用該類的重力中心表示（k-mean）或者用接近中心的object（k-medoid algorithms）。因此抖苦，partitioning algorithms使用連個步驟：首先毁菱，決定最小化目標(biāo)函數(shù)的k米死，然后，將每個對象分配給具有代表性“最近”的集群贮庞。第二步意味著分區(qū)等同于voronoi圖峦筒，并且每個簇包含在一個voronoi單元中，因此窗慎，通過分區(qū)算法找到的所有聚類的形狀是凸的物喷，這是非常受限的。
2.?Hierarchical algorithms（分層算法）創(chuàng)建了D的層次分解遮斥。層次分解用一個dendrogram表示峦失，一個樹，迭代地把D分解成較小的子集术吗，直到每個子集只包含一個對象尉辑。在這樣的層次下，每個書借點代表D的一個類较屿。dendrogram可以從葉節(jié)點向上到根節(jié)點構(gòu)建隧魄，也可以從根節(jié)點向下到葉節(jié)點構(gòu)建，構(gòu)建方式是通過每一步合并或者拆分聚類隘蝎。和partitioning algorithms不同的是购啄，分層聚類不需要k作為輸入。但是嘱么，必須指定終止條件狮含，在合并或拆分是作為終止標(biāo)志。聚類方法終止條件的一個例子是設(shè)置Q的每個類的臨界距離Dmin拱撵。
3 A Density Based Notion of Clusters
看圖1繪制的樣本點辉川，我們可以很容易看出聚類點以及不屬于任何類的噪聲點。我們能識別出類的主要原因是拴测，同一個區(qū)域乓旗，能看出明顯的高密度點群，比其他類外面的類密度要高集索。此外屿愚，同一區(qū)域的噪聲密度也比外面低。
核心方法是對聚類的每個點务荆，給定半徑的鄰域必須包含至少一個最小值數(shù)目的點妆距。例如，鄰域的密度必須超過一些閾值函匕。鄰域的形狀由兩個點p和q的一個距離函數(shù)決定娱据，記為dist(p,q)。例如盅惜，當(dāng)使用2D空間中的曼哈頓距離是中剩，聚類的形狀會是長方形忌穿。注意，為了對給定的應(yīng)用能提供一個合適的距離函數(shù)结啼，我們的方法適用于各種距離函數(shù)掠剑。為了更好地可視化，所有的用例都以二維空間的歐式距離為例郊愧。
一種簡單的方法是需要聚類的每個點朴译，至少在1個Eps-neighborhood中有MinPts個點∈籼可是這種方法行不通眠寿，因為這里有兩種點，在類內(nèi)的點（core points）和在類邊界的點（border points）红选。通常來講澜公，邊界點的Eps-neighborhood區(qū)域內(nèi)的點明顯少于core points的Eps-neighborhood的點。因此喇肋，為了包含屬于同一類的所有點，我們必須將最少點數(shù)設(shè)置為一個相對較小的值迹辐。但是這個值對一些集群來說不是特別相符——尤其是在存在噪聲的情況下蝶防。因此，我們需要對類C里的每個點p明吩，都有一個點q屬于C间学，使p在q的Eps-neighborhood中，
明顯印荔，core points的直接密度可達(dá)是對稱的低葫。通常來講，如果一個core point和它的一個邊界點的密度可達(dá)是不對稱的
定義3:(density-reachable密度可達(dá)) 一個點p與點q是密度可達(dá)的仍律，當(dāng)Eps和MinPts能形成一條鏈p1嘿悬，...，pn水泉，p1=q善涨，pn=p，pi+1是pi的直接密度可達(dá)草则。
密度可達(dá)是直接密度可達(dá)的典型擴(kuò)展钢拧。這中相關(guān)性是可傳遞的，但不是對稱的炕横。圖3描述了一些樣本點源内，尤其是不對稱的情況。盡管通常是不對稱的份殿，但是很明顯core points的密度可達(dá)是對稱的膜钓。
同一個類C的2個邊界點困難彼此不是密度可達(dá)的塔鳍，因為core point condition對它們可能不成立。但是呻此，C中一定有一個core point轮纫，從它出發(fā)一定更有兩個邊界點密度可達(dá)。因此焚鲜，我們介紹了密度連通性的概念掌唾，它涵蓋了邊界點的這種關(guān)系。
定義4:（density-connected密度連通行）一個點p到點q（with respect to Eps和MinPts）是密度連通的忿磅，有一個點o（with respect to Eps和MinPts）糯彬，從它出發(fā)使p和q密度可達(dá)。
密度連通性是一種對稱關(guān)系葱她。對于密度可達(dá)的點撩扒，密度連通性的關(guān)系也是自反的（見圖3）。
現(xiàn)在吨些，我們可以定義一個類的基于密度的概念進(jìn)行定義了搓谆。直覺上看，一個類的定義是一系列密度連通的點豪墅，擁有最大化的密度可達(dá)性泉手。對于給定的類，噪聲也隨即被定義偶器，即D中不屬于任何類的點就是噪聲點斩萌。
（1）對于所有p，q屏轰，如果p輸入C颊郎，q是p（with respect to Eps&MinPts）的密度可達(dá)，則q屬于C（Maximality）
（2）對于所有p霎苗，q屬于C：p是q(with respect to Eps & MinPts)的密度連通點（Connectivity）
定義6:（noise）讓C1姆吭，...，Ck為D的一系列聚類（with respect to Eps & MinPts）叨粘，i=1猾编，...，k升敲。然后我們把D中不屬于任何聚類Ci的點定義為噪聲答倡。
4 DBSCAN：Density Based Spatial Clustering of Applications with Noise
這一部分，我們提出了算法DBSCAN驴党，用于在空間數(shù)據(jù)中根據(jù)定義5和定義6來發(fā)現(xiàn)聚類和噪聲瘪撇。理想地，我們必須知道每個聚類的合適的參數(shù)Eps和Minpts，一直相應(yīng)聚類中的至少一個點倔既。然后恕曲，我們用合適的參數(shù)取出所有從給定點密度可達(dá)的點。但是并沒有好的方法給所有聚類提前獲得這些信息渤涌。但是佩谣，有一個簡單高效的方法heuristic（在4.2節(jié)提出），能確定Eps和MinPts的“thinnest”,如數(shù)據(jù)庫中的最小密度和類实蓬。因此茸俭，DBSCAN使用全局的Eps和MinPts，即所有類都適用同一個值安皱〉鼢蓿“thinnest”類的密度參數(shù)是這個全局Eps和MinPts的值的最佳候選，定義了不是噪聲點的最小密度酌伊。
4.1 The Algorithm
為了找到聚類腾窝，DBSCAN從任意一個p點開始，去從p出發(fā)的所有密度可達(dá)點(with respect Eps & MinPts)居砖。如果p是core points虹脯，這個過程產(chǎn)生一個聚類。如果p是邊界點悯蝉，從p出發(fā)沒有密度可達(dá)點归形，則DBSCAN選取數(shù)據(jù)集中的下一個點。
因為我們使用了一個全局的Eps和MinPts值鼻由，如果不同密度的類彼此很“接近”，DBSCAN可能根據(jù)定義5將兩個類合并為一個類厚棵。定義兩個點集的距離為S1和S2蕉世，記為dist(S1, S2)=min{dist(p,q)|p屬于S1，q屬于S2}婆硬。然后狠轻，當(dāng)且僅當(dāng)兩個點集的距離大于Eps，這兩個含有thinnest cluster密度的點集才會被拆分成兩個集群彬犯。所以向楼，可能需要遞歸調(diào)用DBSCAN，才會發(fā)現(xiàn)MinPts更高的類谐区。然而湖蜕，這不是缺點，因為DBSCAN的遞歸調(diào)用產(chǎn)生了非常有效的基本算法宋列。此外昭抒，只有在易于檢測的條件下才需要對簇的點進(jìn)行遞歸聚類。
4.2 Determining the Parameters Eps and MinPts
在這一部分，我們用了一種簡單但是很有效的heuristic（啟發(fā)式）算法來確定數(shù)據(jù)集中“thinest”cluster的Eps和MinPts的Eps和MinPts參數(shù)灭返。這種啟發(fā)式算法是基于下面的observation盗迟。定義d為p到它的第k個最近鄰的距離，那么幾乎所有的點p的d-neighborhood都包含k+1個點熙含。只有一些點到p的距離完全一樣罚缕，d-neighborhood才會包含大于k+1個點，這種情況是幾乎不可能的怎静。此外邮弹，在一個類內(nèi)更換一個點的k值不會導(dǎo)致d有太大的變化，除非p的第k個近鄰k=1消约，2肠鲫，3，...都位于一條直線上或粮，但是這種情況通常不存在导饲。
對于給定的k，定義函數(shù)k-dist為實數(shù)氯材，代表將每個點到距離它第k個最近鄰居的距離渣锦，對k-dist的值降序排序，這個函數(shù)圖會給一些數(shù)據(jù)集密度的提示氢哮。我們把這個圖叫做sorted k-dist graph袋毙。如果我們選擇任意一個點p，設(shè)置參數(shù)Eps為k-dist(p)冗尤，設(shè)置MinPts為k听盖，所有相等或小于k-dist的點都是core points。如果我們能在“thinnest”cluster中找到一個有最大k-dist的閾值裂七，就會得到我們想要的參數(shù)皆看。這個閾值點就是排序過的k-dist圖中第一個山谷值，見圖4.所有k-dist較大的點（閾值左邊）都認(rèn)為是噪聲背零，所有閾值右邊的點認(rèn)為是一些cluster腰吟。
通常來講，很難自動發(fā)現(xiàn)第一個“山谷值”徙瓶，但是在圖像化后毛雇，人工看出山谷值會相對容易。因此侦镇，我們建議采用交互式方法來確定閾值點灵疮。
DBSCAN需要兩個參數(shù)，Eps和MinPts虽缕。但是始藕，我們的實驗證明蒲稳，k>4的k-dist圖和4-dist圖沒有明顯的差別，此外伍派，它們還需要更大的計算量江耀。因此，我們通過將所有數(shù)據(jù)庫（對于2維數(shù)據(jù)）設(shè)置為4來消除參數(shù)MinPts诉植。我們用下面的交互式方法決定DBSCAN的Eps：
系統(tǒng)計算并繪制數(shù)據(jù)集的4-dist圖
如果用戶能估計一定百分比的噪聲祥国，則輸入此百分比，系統(tǒng)從中獲取閾值點的建議晾腔。
用戶可以選擇接受建議或者用其他的閾值點舌稀。4-dist閾值被用作DBSCAN的Eps
5 Performance Evaluation
這一部分，我們評估了DBSCAN的表現(xiàn)灼擂。我們將它與CLARANS進(jìn)行比較壁查，因為它是為KDD設(shè)計的第一且唯一的聚類算法。在我們后續(xù)的研究中剔应，將會與經(jīng)典的基于密度的聚類算法進(jìn)行比較睡腿。我們用C++實現(xiàn)了基于R*-tree的DBSCAN，所有實驗在HP 735/100 工作站峻贮。我們使用了SEQUQIA2000基準(zhǔn)集上的合成樣本數(shù)據(jù)集席怪。
為了比較DBSCAN和CLARANS的有效性（準(zhǔn)確率），我們使用三個樣本數(shù)據(jù)集纤控，見圖1挂捻。因為DBSCAN和CLARANS是不同類型的聚類算法，它們沒有統(tǒng)一的分類準(zhǔn)確度的定量測量方法船万，因此我們通過視覺評估兩者的準(zhǔn)確率刻撒。在樣本數(shù)據(jù)集1，有4個形狀的明顯大小不一的聚類耿导。樣本數(shù)據(jù)2包含4個非凸形狀的聚類疫赎。樣本數(shù)據(jù)集3有4個不同形狀的類，還有一些噪聲碎节。為了展示兩種聚類算法的結(jié)果，我們用不同顏色可視化了每個cluster（見第6章后面的www availability）抵卫。為了讓CLARANS表現(xiàn)好一些狮荔，我們將參數(shù)k設(shè)置為4。CLARANS發(fā)現(xiàn)的聚類見圖5.
圖5 CLARANS聚類結(jié)果
對DBSCAN介粘，我們給樣本集1和樣本集2設(shè)置0%的噪聲殖氏，給樣本3設(shè)置10%的噪聲。DBSCAN的聚類結(jié)果見圖6.
圖6 DBSCAN聚類結(jié)果
DBSCAN發(fā)現(xiàn)了所有的cluster姻采，且檢測到了噪聲點雅采。但是CLARANS把一些相對大的cluster或者和其他類很近的cluster進(jìn)行了拆分。此外，CLARANS沒有區(qū)分出噪聲婚瓜，而是所有點都分配給了它們最接近的medoid宝鼓。
為了測試DBSCAN和CLARANS的效率，我們使用SEQUOIA2000基準(zhǔn)數(shù)據(jù)集巴刻。SEQUOIA2000使用了地球科學(xué)中用的實數(shù)集愚铡。有4種類型的數(shù)據(jù)：柵格數(shù)據(jù)，點數(shù)據(jù)胡陪，多邊形數(shù)據(jù)和有向圖數(shù)據(jù)沥寥。點數(shù)據(jù)有62584個Californian的地標(biāo)名稱以及它們的位置，取自US Geological Survey's Geographic Names Information System柠座。點數(shù)據(jù)大概有2.1M邑雅。因為CLARANS在整個數(shù)據(jù)上運行時間很長，所以我們?nèi)EQUIOA2000的子集進(jìn)行實驗妈经，包含2%到20%的代表性數(shù)據(jù)淮野。DBSCAN和CLARANS的運行時間比較見表1.
表1 運行時間比較（秒）
實驗結(jié)果顯示，DBSCAN的運行時間略高于線性數(shù)點狂塘。而CLARANS的運行時間接近二次方點录煤。結(jié)果顯示DBSCAN比CLARANS表現(xiàn)要好，隨著數(shù)據(jù)集的增長荞胡，表現(xiàn)好250～1900倍妈踊。
6 Conclusions
聚類算法在解決空間數(shù)據(jù)分類問題中很常用±崞可是廊营，眾所周知的算法在應(yīng)用于大型空間數(shù)據(jù)庫時有嚴(yán)重的缺陷。本文提出一種聚類算法DBSCAN萝勤，依賴于clusters的密度概念露筒。它只需要一個輸入?yún)?shù)，支持用戶自定義它的值敌卓。我們在SEQUOIA2000基準(zhǔn)數(shù)據(jù)集上對其進(jìn)行了評估慎式。實驗結(jié)果證明DBSCAN發(fā)現(xiàn)任意形狀的聚類效果要明顯好于CLARANS。此外趟径，實驗還證明了DBSCAN效率比CLARANS至少高100倍瘪吏。
后續(xù)研究將考慮以下方向：首先，我們只考慮了點數(shù)據(jù)蜗巧≌泼撸可是空間數(shù)據(jù)集還有一些擴(kuò)展對象，如四邊形數(shù)據(jù)幕屹。我們需要發(fā)現(xiàn)四邊形數(shù)據(jù)集在Eps-neighborhood上的密度蓝丙，對DBSCAN進(jìn)行泛化级遭。其次，DBSCAN對高緯特征空間的應(yīng)用也應(yīng)該研究渺尘，特別是必須探索這種應(yīng)用中k-dist圖的形狀挫鸽。
