基于密度DBSCAN的聚類(lèi)算法

聚類(lèi)算法概念

聚類(lèi)分析又稱(chēng)群分析，它是研究（樣品或指標(biāo)）分類(lèi)問(wèn)題的一種統(tǒng)計(jì)分析方法，同時(shí)也是數(shù)據(jù)挖掘的一個(gè)重要算法。聚類(lèi)（Cluster）分析是由若干模式（Pattern）組成的，通常，模式是一個(gè)度量（Measurement）的向量，或者是多維空間中的一個(gè)點(diǎn)。聚類(lèi)分析以相似性為基礎(chǔ)，在一個(gè)聚類(lèi)中的模式之間比不在同一聚類(lèi)中的模式之間具有更多的相似性。

聚類(lèi)的用途是很廣泛的。在商業(yè)上，聚類(lèi)可以幫助市場(chǎng)分析人員從消費(fèi)者數(shù)據(jù)庫(kù)中區(qū)分出不同的消費(fèi)群體來(lái)，并且概括出每一類(lèi)消費(fèi)者的消費(fèi)模式或者說(shuō)習(xí)慣。它作為數(shù)據(jù)挖掘中的一個(gè)模塊，可以作為一個(gè)單獨(dú)的工具以發(fā)現(xiàn)數(shù)據(jù)庫(kù)中分布的一些深層的信息，并且概括出每一類(lèi)的特點(diǎn)，或者把注意力放在某一個(gè)特定的類(lèi)上以作進(jìn)一步的分析；并且，聚類(lèi)分析也可以作為數(shù)據(jù)挖掘算法中其他分析算法的一個(gè)預(yù)處理步驟。

聚類(lèi)分析的算法可以分為劃分法（Partitioning Methods）、層次法（Hierarchical Methods）、基于密度的方法（density-based methods）、基于網(wǎng)格的方法（grid-based methods）、基于模型的方法（Model-Based Methods）。

聚類(lèi)算法的分類(lèi)

劃分法

劃分法（partitioning methods），給定一個(gè)有N個(gè)元組或者紀(jì)錄的數(shù)據(jù)集，分裂法將構(gòu)造K個(gè)分組，每一個(gè)分組就代表一個(gè)聚類(lèi)，K《N。而且這K個(gè)分組滿(mǎn)足下列條件：

（1） 每一個(gè)分組至少包含一個(gè)數(shù)據(jù)紀(jì)錄；

（2）每一個(gè)數(shù)據(jù)紀(jì)錄屬于且僅屬于一個(gè)分組（注意：這個(gè)要求在某些模糊聚類(lèi)算法中可以放寬）；

對(duì)于給定的K，算法首先給出一個(gè)初始的分組方法，以后通過(guò)反復(fù)迭代的方法改變分組，使得每一次改進(jìn)之后的分組方案都較前一次好，而所謂好的標(biāo)準(zhǔn)就是：同一分組中的記錄越近越好，而不同分組中的紀(jì)錄越遠(yuǎn)越好。

大部分劃分方法是基于距離的。給定要構(gòu)建的分區(qū)數(shù)k，劃分方法首先創(chuàng)建一個(gè)初始化劃分。然后，它采用一種迭代的重定位技術(shù)，通過(guò)把對(duì)象從一個(gè)組移動(dòng)到另一個(gè)組來(lái)進(jìn)行劃分。一個(gè)好的劃分的一般準(zhǔn)備是：同一個(gè)簇中的對(duì)象盡可能相互接近或相關(guān)，而不同的簇中的對(duì)象盡可能遠(yuǎn)離或不同。還有許多評(píng)判劃分質(zhì)量的其他準(zhǔn)則。傳統(tǒng)的劃分方法可以擴(kuò)展到子空間聚類(lèi)，而不是搜索整個(gè)數(shù)據(jù)空間。當(dāng)存在很多屬性并且數(shù)據(jù)稀疏時(shí)，這是有用的。為了達(dá)到全局最優(yōu)，基于劃分的聚類(lèi)可能需要窮舉所有可能的劃分，計(jì)算量極大。實(shí)際上，大多數(shù)應(yīng)用都采用了流行的啟發(fā)式方法，如k-均值和k-中心算法，漸近的提高聚類(lèi)質(zhì)量，逼近局部最優(yōu)解。這些啟發(fā)式聚類(lèi)方法很適合發(fā)現(xiàn)中小規(guī)模的數(shù)據(jù)庫(kù)中小規(guī)模的數(shù)據(jù)庫(kù)中的球狀簇。為了發(fā)現(xiàn)具有復(fù)雜形狀的簇和對(duì)超大型數(shù)據(jù)集進(jìn)行聚類(lèi)，需要進(jìn)一步擴(kuò)展基于劃分的方法。

使用這個(gè)基本思想的算法有：K-MEANS算法、K-MEDOIDS算法、CLARANS算法；

層次法

層次法（hierarchical methods），這種方法對(duì)給定的數(shù)據(jù)集進(jìn)行層次似的分解，直到某種條件滿(mǎn)足為止。具體又可分為“自底向上”和“自頂向下”兩種方案。

例如，在“自底向上”方案中，初始時(shí)每一個(gè)數(shù)據(jù)紀(jì)錄都組成一個(gè)單獨(dú)的組，在接下來(lái)的迭代中，它把那些相互鄰近的組合并成一個(gè)組，直到所有的記錄組成一個(gè)分組或者某個(gè)條件滿(mǎn)足為止。

層次聚類(lèi)方法可以是基于距離的或基于密度或連通性的。層次聚類(lèi)方法的一些擴(kuò)展也考慮了子空間聚類(lèi)。層次方法的缺陷在于，一旦一個(gè)步驟（合并或分裂）完成，它就不能被撤銷(xiāo)。這個(gè)嚴(yán)格規(guī)定是有用的，因?yàn)椴挥脫?dān)心不同選擇的組合數(shù)目，它將產(chǎn)生較小的計(jì)算開(kāi)銷(xiāo)。然而這種技術(shù)不能更正錯(cuò)誤的決定。已經(jīng)提出了一些提高層次聚類(lèi)質(zhì)量的方法。

代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等；

密度算法

基于密度的方法（density-based methods），基于密度的方法與其它方法的一個(gè)根本區(qū)別是：它不是基于各種各樣的距離的，而是基于密度的。這樣就能克服基于距離的算法只能發(fā)現(xiàn)“類(lèi)圓形”的聚類(lèi)的缺點(diǎn)。

這個(gè)方法的指導(dǎo)思想就是，只要一個(gè)區(qū)域中的點(diǎn)的密度大過(guò)某個(gè)閾值，就把它加到與之相近的聚類(lèi)中去。

代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等；

圖論聚類(lèi)法

圖論聚類(lèi)方法解決的第一步是建立與問(wèn)題相適應(yīng)的圖，圖的節(jié)點(diǎn)對(duì)應(yīng)于被分析數(shù)據(jù)的最小單元，圖的邊（或?。?duì)應(yīng)于最小處理單元數(shù)據(jù)之間的相似性度量。因此，每一個(gè)最小處理單元數(shù)據(jù)之間都會(huì)有一個(gè)度量表達(dá)，這就確保了數(shù)據(jù)的局部特性比較易于處理。圖論聚類(lèi)法是以樣本數(shù)據(jù)的局域連接特征作為聚類(lèi)的主要信息源，因而其主要優(yōu)點(diǎn)是易于處理局部數(shù)據(jù)的特性。

網(wǎng)格算法

基于網(wǎng)格的方法（grid-based methods），這種方法首先將數(shù)據(jù)空間劃分成為有限個(gè)單元（cell）的網(wǎng)格結(jié)構(gòu)，所有的處理都是以單個(gè)的單元為對(duì)象的。這么處理的一個(gè)突出的優(yōu)點(diǎn)就是處理速度很快，通常這是與目標(biāo)數(shù)據(jù)庫(kù)中記錄的個(gè)數(shù)無(wú)關(guān)的，它只與把數(shù)據(jù)空間分為多少個(gè)單元有關(guān)。

代表算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法；

模型算法

基于模型的方法（model-based methods），基于模型的方法給每一個(gè)聚類(lèi)假定一個(gè)模型，然后去尋找能夠很好的滿(mǎn)足這個(gè)模型的數(shù)據(jù)集。這樣一個(gè)模型可能是數(shù)據(jù)點(diǎn)在空間中的密度分布函數(shù)或者其它。它的一個(gè)潛在的假定就是：目標(biāo)數(shù)據(jù)集是由一系列的概率分布所決定的。

通常有兩種嘗試方向：統(tǒng)計(jì)的方案和神經(jīng)網(wǎng)絡(luò)的方案。

基于密度DBSCAN的聚類(lèi)算法

DBSCAN算法的原理

1、基本概念

DBSCAN（Density-BasedSpatialClusteringofApplicationwithNoise）是一種典型的基于密度的聚類(lèi)算法，在DBSCAN算法中將數(shù)據(jù)點(diǎn)分為一下三類(lèi)：

核心點(diǎn)。在半徑Eps內(nèi)含有超過(guò)MinPts數(shù)目的點(diǎn)

邊界點(diǎn)。在半徑Eps內(nèi)點(diǎn)的數(shù)量小于MinPts，但是落在核心點(diǎn)的鄰域內(nèi)

噪音點(diǎn)。既不是核心點(diǎn)也不是邊界點(diǎn)的點(diǎn)

在這里有兩個(gè)量，一個(gè)是半徑Eps，另一個(gè)是指定的數(shù)目MinPts。

其他的概念

1）Eps鄰域。簡(jiǎn)單來(lái)講就是與點(diǎn)p的距離小于等于Eps的所有的點(diǎn)的集合，可以表示為。

2）直接密度可達(dá)。如果p在核心對(duì)象q的Eps鄰域內(nèi)，則稱(chēng)對(duì)象p從對(duì)象q出發(fā)是直接密度可達(dá)的。

3）密度可達(dá)。對(duì)于對(duì)象鏈：，是從關(guān)于Eps和MinPts直接密度可達(dá)的，則對(duì)象是從對(duì)象關(guān)于Eps和MinPts密度可達(dá)的。

2、算法流程

實(shí)驗(yàn)仿真

在實(shí)驗(yàn)中使用了兩個(gè)測(cè)試數(shù)據(jù)集，數(shù)據(jù)集的原始圖像如下：

（數(shù)據(jù)集1）

（數(shù)據(jù)集2）

數(shù)據(jù)集1相對(duì)比較簡(jiǎn)單。顯然我們可以發(fā)現(xiàn)數(shù)據(jù)集1共有兩個(gè)類(lèi)，數(shù)據(jù)集2有四個(gè)類(lèi)，下面我們通過(guò)DBSCAN算法實(shí)現(xiàn)數(shù)據(jù)點(diǎn)的聚類(lèi)：

MATLAB代碼

主程序

%% DBSCAN

clear all;

clc;

%% 導(dǎo)入數(shù)據(jù)集

% data = load（‘testData.txt’）;

data = load（‘testData_2.txt’）;

% 定義參數(shù)Eps和MinPts

MinPts = 5;

Eps = epsilon（data， MinPts）;

［m，n］ = size（data）;%得到數(shù)據(jù)的大小

x = ［（1:m）‘ data］;

［m，n］ = size（x）;%重新計(jì)算數(shù)據(jù)集的大小

types = zeros（1，m）;%用于區(qū)分核心點(diǎn)1，邊界點(diǎn)0和噪音點(diǎn)-1

dealed = zeros（m，1）;%用于判斷該點(diǎn)是否處理過(guò)，0表示未處理過(guò)

dis = calDistance（x（：，2:n））;

number = 1;%用于標(biāo)記類(lèi)

%% 對(duì)每一個(gè)點(diǎn)進(jìn)行處理

for i = 1:m

%找到未處理的點(diǎn)

if dealed（i） == 0

xTemp = x（i，：）;

D = dis（i，：）;%取得第i個(gè)點(diǎn)到其他所有點(diǎn)的距離

ind = find（D《=Eps）;%找到半徑Eps內(nèi)的所有點(diǎn)

%% 區(qū)分點(diǎn)的類(lèi)型

%邊界點(diǎn)

if length（ind） 》 1 && length（ind） 《 MinPts+1

types（i） = 0;

class（i） = 0;

end

%噪音點(diǎn)

if length（ind） == 1

types（i） = -1;

class（i） = -1;

dealed（i） = 1;

end

%核心點(diǎn)（此處是關(guān)鍵步驟）

if length（ind） 》= MinPts+1

types（xTemp（1，1）） = 1;

class（ind） = number;

% 判斷核心點(diǎn)是否密度可達(dá)

while ~isempty（ind）

yTemp = x（ind（1），：）;

dealed（ind（1）） = 1;

ind（1） = ［］;

D = dis（yTemp（1，1），：）;%找到與ind（1）之間的距離

ind_1 = find（D《=Eps）;

if length（ind_1）》1%處理非噪音點(diǎn)

class（ind_1） = number;

if length（ind_1） 》= MinPts+1

types（yTemp（1，1）） = 1;

else

types（yTemp（1，1）） = 0;

end

for j=1:length（ind_1）

if dealed（ind_1（j）） == 0

dealed（ind_1（j）） = 1;

ind=［ind ind_1（j）］;

class（ind_1（j））=number;

end

end

end

end

number = number + 1;

end

end

end

% 最后處理所有未分類(lèi)的點(diǎn)為噪音點(diǎn)

ind_2 = find（class==0）;

class（ind_2） = -1;

types（ind_2） = -1;

%% 畫(huà)出最終的聚類(lèi)圖

hold on

for i = 1:m

if class（i） == -1

plot（data（i，1），data（i，2），’.r‘）;

elseif class（i） == 1

if types（i） == 1

plot（data（i，1），data（i，2），’+b‘）;

else

plot（data（i，1），data（i，2），’.b‘）;

end

elseif class（i） == 2

if types（i） == 1

plot（data（i，1），data（i，2），’+g‘）;

else

plot（data（i，1），data（i，2），’.g‘）;

end

elseif class（i） == 3

if types（i） == 1

plot（data（i，1），data（i，2），’+c‘）;

else

plot（data（i，1），data（i，2），’.c‘）;

end

else

if types（i） == 1

plot（data（i，1），data（i，2），’+k‘）;

else

plot（data（i，1），data（i，2），’.k‘）;

end

end

end

hold off

距離計(jì)算函數(shù)

%% 計(jì)算矩陣中點(diǎn)與點(diǎn)之間的距離

function ［ dis ］ = calDistance（ x ）

［m，n］ = size（x）;

dis = zeros（m，m）;

for i = 1:m

for j = i:m

%計(jì)算點(diǎn)i和點(diǎn)j之間的歐式距離

tmp =0;

for k = 1:n

tmp = tmp+（x（i，k）-x（j，k））.^2;

end

dis（i，j） = sqrt（tmp）;

dis（j，i） = dis（i，j）;

end

end

end

epsilon函數(shù)

function ［Eps］=epsilon（x，k）

% Function： ［Eps］=epsilon（x，k）

%

% Aim：

% Analytical way of estimating neighborhood radius for DBSCAN

%

% Input：

% x - data matrix （m，n）; m-objects， n-variables

% k - number of objects in a neighborhood of an object

% （minimal number of objects considered as a cluster）

［m，n］=size（x）;

Eps=（（prod（max（x）-min（x））*k*gamma（.5*n+1））/（m*sqrt（pi.^n）））.^（1/n）;

最終的結(jié)果

（數(shù)據(jù)集1的聚類(lèi)結(jié)果）

（數(shù)據(jù)集2的聚類(lèi)結(jié)果）

在上面的結(jié)果中，紅色的點(diǎn)代表的是噪音點(diǎn)，點(diǎn)代表的是邊界點(diǎn)，十字代表的是核心點(diǎn)。不同的顏色代表著不同的類(lèi)。