聚類算法概念

聚類分析又稱群分析，它是研究（樣品或指標）分類問題的一種統計分析方法，同時也是數據挖掘的一個重要算法。聚類（Cluster）分析是由若干模式（Pattern）組成的，通常，模式是一個度量（Measurement）的向量，或者是多維空間中的一個點。聚類分析以相似性為基礎，在一個聚類中的模式之間比不在同一聚類中的模式之間具有更多的相似性。

聚類的用途是很廣泛的。在商業上，聚類可以幫助市場分析人員從消費者數據庫中區分出不同的消費群體來，并且概括出每一類消費者的消費模式或者說習慣。它作為數據挖掘中的一個模塊，可以作為一個單獨的工具以發現數據庫中分布的一些深層的信息，并且概括出每一類的特點，或者把注意力放在某一個特定的類上以作進一步的分析；并且，聚類分析也可以作為數據挖掘算法中其他分析算法的一個預處理步驟。

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

聚類算法的分類

劃分法

劃分法（partitioning methods），給定一個有N個元組或者紀錄的數據集，分裂法將構造K個分組，每一個分組就代表一個聚類，K《N。而且這K個分組滿足下列條件：

（1） 每一個分組至少包含一個數據紀錄；

（2）每一個數據紀錄屬于且僅屬于一個分組（注意：這個要求在某些模糊聚類算法中可以放寬）；

對于給定的K，算法首先給出一個初始的分組方法，以后通過反復迭代的方法改變分組，使得每一次改進之后的分組方案都較前一次好，而所謂好的標準就是：同一分組中的記錄越近越好，而不同分組中的紀錄越遠越好。

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

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

層次法

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

例如，在“自底向上”方案中，初始時每一個數據紀錄都組成一個單獨的組，在接下來的迭代中，它把那些相互鄰近的組合并成一個組，直到所有的記錄組成一個分組或者某個條件滿足為止。

層次聚類方法可以是基于距離的或基于密度或連通性的。層次聚類方法的一些擴展也考慮了子空間聚類。層次方法的缺陷在于，一旦一個步驟（合并或分裂）完成，它就不能被撤銷。這個嚴格規定是有用的，因為不用擔心不同選擇的組合數目，它將產生較小的計算開銷。然而這種技術不能更正錯誤的決定。已經提出了一些提高層次聚類質量的方法。

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

密度算法

基于密度的方法（density-based methods），基于密度的方法與其它方法的一個根本區別是：它不是基于各種各樣的距離的，而是基于密度的。這樣就能克服基于距離的算法只能發現“類圓形”的聚類的缺點。

這個方法的指導思想就是，只要一個區域中的點的密度大過某個閾值，就把它加到與之相近的聚類中去。

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

圖論聚類法

圖論聚類方法解決的第一步是建立與問題相適應的圖，圖的節點對應于被分析數據的最小單元，圖的邊（或?。谧钚√幚韱卧獢祿g的相似性度量。因此，每一個最小處理單元數據之間都會有一個度量表達，這就確保了數據的局部特性比較易于處理。圖論聚類法是以樣本數據的局域連接特征作為聚類的主要信息源，因而其主要優點是易于處理局部數據的特性。

網格算法

基于網格的方法（grid-based methods），這種方法首先將數據空間劃分成為有限個單元（cell）的網格結構，所有的處理都是以單個的單元為對象的。這么處理的一個突出的優點就是處理速度很快，通常這是與目標數據庫中記錄的個數無關的，它只與把數據空間分為多少個單元有關。

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

模型算法

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

通常有兩種嘗試方向：統計的方案和神經網絡的方案。

基于密度DBSCAN的聚類算法

DBSCAN算法的原理

1、基本概念

DBSCAN（Density-BasedSpatialClusteringofApplicationwithNoise）是一種典型的基于密度的聚類算法，在DBSCAN算法中將數據點分為一下三類：

核心點。在半徑Eps內含有超過MinPts數目的點

邊界點。在半徑Eps內點的數量小于MinPts，但是落在核心點的鄰域內

噪音點。既不是核心點也不是邊界點的點

在這里有兩個量，一個是半徑Eps，另一個是指定的數目MinPts。

其他的概念

1）Eps鄰域。簡單來講就是與點p的距離小于等于Eps的所有的點的集合，可以表示為。

2）直接密度可達。如果p在核心對象q的Eps鄰域內，則稱對象p從對象q出發是直接密度可達的。

3）密度可達。對于對象鏈：，是從關于Eps和MinPts直接密度可達的，則對象是從對象關于Eps和MinPts密度可達的。

2、算法流程

實驗仿真

在實驗中使用了兩個測試數據集，數據集的原始圖像如下：

（數據集1）

（數據集2）

數據集1相對比較簡單。顯然我們可以發現數據集1共有兩個類，數據集2有四個類，下面我們通過DBSCAN算法實現數據點的聚類：

MATLAB代碼

主程序

%% DBSCAN

clear all;

clc;

%% 導入數據集

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

data = load（‘testData_2.txt’）;

% 定義參數Eps和MinPts

MinPts = 5;

Eps = epsilon（data， MinPts）;

［m，n］ = size（data）;%得到數據的大小

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

［m，n］ = size（x）;%重新計算數據集的大小

types = zeros（1，m）;%用于區分核心點1，邊界點0和噪音點-1

dealed = zeros（m，1）;%用于判斷該點是否處理過，0表示未處理過

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

number = 1;%用于標記類

%% 對每一個點進行處理

for i = 1:m

%找到未處理的點

if dealed（i） == 0

xTemp = x（i，：）;

D = dis（i，：）;%取得第i個點到其他所有點的距離

ind = find（D《=Eps）;%找到半徑Eps內的所有點

%% 區分點的類型

%邊界點

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

types（i） = 0;

class（i） = 0;

end

%噪音點

if length（ind） == 1

types（i） = -1;

class（i） = -1;

dealed（i） = 1;

end

%核心點（此處是關鍵步驟）

if length（ind） 》= MinPts+1

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

class（ind） = number;

% 判斷核心點是否密度可達

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%處理非噪音點

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

% 最后處理所有未分類的點為噪音點

ind_2 = find（class==0）;

class（ind_2） = -1;

types（ind_2） = -1;

%% 畫出最終的聚類圖

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

距離計算函數

%% 計算矩陣中點與點之間的距離

function ［ dis ］ = calDistance（ x ）

［m，n］ = size（x）;

dis = zeros（m，m）;

for i = 1:m

for j = i:m

%計算點i和點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函數

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）;

最終的結果

（數據集1的聚類結果）

（數據集2的聚類結果）

在上面的結果中，紅色的點代表的是噪音點，點代表的是邊界點，十字代表的是核心點。不同的顏色代表著不同的類。