MVO優化DBSCAN實現聚類

Create random universes (U)
Initialize WER,TDR,Best_universe
SU=Sorted universes 
NI=Normalize inflation rate (fitness) of the universes
while the end criterion is not satisfied
      Update WEP and TDR; 
      Evaluate the fitness of all universes 
      for each universe indexed by i 
          Black_hole_index=i;
          for each object indexed  by  j 
              r1=random([0,1]);
              if r1<NI(Ui) 
                 White_hole_index=RouletteWheelSelection(-NI); 
                 U(Black_hole_index,j)=SU(White_hole_index,j); 
              end if

              r2=random([0,1]); 
              if r2<Wormhole_existance_probability 
                    r3= random([0,1]); 
                    r4= random([0,1]); 
                    if  r3<0.5         
                        U(i,j)=Best_universe(j)+Travelling_distance_rate*(( ub(j) -lb(j))*r4 + lb(j)); 
                    else   
                        U(i,j)=Best_universe(j)-Travelling_distance_rate*(( ub(j) -lb(j))*r4+lb(j));
                    end if 
              end if
          end for 
      end for
end while

有關MVO演算法的詳細介紹請參考：(中文版)MVO演算法詳解及其虛擬碼

二、DBSCAN

1.基本概念

DBSCAN是一種基於密度的聚類演算法，它有兩個重要的引數：Eps為定義密度時的領域半徑，MinPts為定義核心點時的閾值。

(1) 核心點：在半徑Eps內含有大於或者等於MinPts數目的點。

(2) 邊界點：在半徑Eps內點的數量小於MinPts，但是落在核心點的鄰域內。

(3) 噪音點：既不是核心點也不是邊界點的點。

圖1 核心點、邊界點、噪音點

(4) 密度直達：若 $\large x_{j}$ 位於核心點 $\large x_{i}$ 的Eps領域內，則稱 $\large x_{j}$ 由 $\large x_{i}$ 密度直達。

(5) 密度可達：對 $\large x_{j}$ 與 $\large x_{i}$ ，若存在序列 $\large p_{1},p_{2},...,p_{n},$ 其中 $\large p_{1}=x_{i},p_{n}=x_{j}$ 且 $\large p_{i+1}$ 由 $\large p_{i}$ 密度直達,則稱 $\large x_{j}$ 由 $\large x_{i}$ 密度可達。

(6) 密度相連：對 $\large x_{j}$ 與 $\large x_{i}$ ，若存在 $\large x_{k}$ ，使得 $\large x_{j}$ 與 $\large x_{i}$ 均由 $\large x_{k}$ 密度可達，則稱 $\large x_{j}$ 與 $\large x_{i}$ 密度相連。

圖2 密度直達、密度可達、密度相連

如圖2所示，虛線代表的是Eps領域， $\large x_{1}$ ~ $\large x_{5}$ 均為核心點， $\large x_{2}$ 、 $\large x_{4}$ 分別由 $\large x_{1}$ 密度直達， $\large x_{3}$ 、 $\large x_{5}$ 分別由 $\large x_{1}$ 密度可達， $\large x_{3}$ 與 $\large x_{5}$ 密度相連。

2.演算法原理

演算法先根據引數Eps和MinPts找出所有核心點，然後以任一核心點為出發點，找出由其密度可達的樣本生成聚類簇，直到所有核心點均被訪問過為止。

3.演算法的優缺點

3.1優點

（1）不需要事先指定聚類的類別數；

（2）可以發現任意形狀的類；

（3）能找出資料中的噪音點，且對噪音點不敏感。

3.2缺點

（1）演算法的聚類效果依賴於距離公式的選取，由於高維資料存在維數災難，會對距離的度量標準產生影響；

（2）當資料集中的資料密度不均勻時，引數Eps和MinPts的選取較困難，從而影響聚類的效果。

4.演算法流程

圖3 DBSCAN演算法流程圖

5.引數設定

(1)Eps：DBSCAN演算法原文中通過定義K-距離圖選擇Eps的值。K-距離圖的定義：給定k鄰域引數，對於資料中的每個點，計算對應的第k個最近鄰域距離，並將資料集所有點對應的第k個最近鄰域距離按照降序方式排序，並繪製成降序排列的k距離圖。在K-距離圖中第一個谷值點位置對應的k距離值設定為DBSCAN的Eps，能得到較好的聚類效果。

說明：一般將K-距離圖中引數k的值設為4。

(2)MinPts：該引數的選取有一個準則，MinPts≥dim+1，其中dim表示待聚類資料的維度。

MinPts設定為1時，每個獨立點都是核心點，都可以形成一個簇；MinPts≤2時，與層次距離最近鄰域結果相同。因此，MinPts必須選擇大於等於3的值。

6.MATLAB程式碼

%%% 用DBSCAN實現聚類
clear;
close all;
clc;
tic;
%% 待聚類資料集
% 第一組資料
mu1=[0 0];  %均值
S1=[0.1 0;0 0.1];  %協方差
data1=mvnrnd(mu1,S1,100);   %產生高斯分佈資料
%第二組資料
mu2=[1.25 1.25];
S2=[0.1 0;0 0.1];
data2=mvnrnd(mu2,S2,100);
% 第三組資料
mu3=[-1.25 1.25];
S3=[0.1 0;0 0.1];
data3=mvnrnd(mu3,S3,100);
data=[data1;data2;data3];

%%
% KNN k distance graph, to determine the epsilon
% 對每個資料求第K個最近領域距離，一般將k值設為4.
numData=size(data,1);
Kdist=zeros(numData,1);
[~,Dist]=knnsearch(data(2:numData,:),data(1,:),'dist','euclidean','k',4);
Kdist(1)=Dist(1);
for i=2:numData
    [~,Dist] = knnsearch(data([1:i-1,i+1:numData],:),data(i,:));   % 除i行以外的其他行與i進行計算.
    Kdist(i)=Dist;        % 矩陣Dist與k的個數有關，大小始終為(1*K).
end
[sortKdist,~]=sort(Kdist,'descend');% 將資料集所有點對應的最近領域距離按照降序方式排列,sortKdist是降序排列後的資料.
distX=(1:numData)';

%% 畫圖
figure(1);
plot(distX,sortKdist,'r+-','LineWidth',2);
grid on;
% 將引數和資料代入DBSCAN函式
epsilon=0.2;
MinPts=  4   ;
labels=DBSCAN(data,epsilon,MinPts);

figure(2);
PlotClusterinResult(data, labels);
title(['DBSCAN Clustering (\epsilon = ' num2str(epsilon) ', MinPts = ' num2str(MinPts) ')']);
toc;

三、MVO優化DBSCAN實現聚類

雖然可以通過定義K-距離圖選擇Eps的值，但該方法本身的k值也需要人為設定，導致Eps的值得不到較好的選取。針對Eps值的選取問題，本部落格通過MVO優化DBSCAN實現聚類，利用MVO的尋優效能找到合適的Eps值，從而使聚類效果達到最優。

MVO優化DBSCAN實現聚類的原始碼包括MVO演算法，DBSCAN演算法的原始碼，以及MVO優化DBSCAN的過程。

程式碼地址:MVO-DBSCAN

參考文獻

[1]Mirjalili S, Mirjalili S M, Hatamlou A. Multi-verse optimizer: A nature-inspired algorithm for global optimization[J]. Neural Computing and Applications, 2016,27(2): 495-513.

[2]趙世傑,高雷阜,徒君等.耦合橫縱向個體更新策略的改進MVO演算法[J].控制與決策,2018,33(8):1423.

[3]來文豪,周孟然,李大同等.無監督學習AE和MVO-DBSCAN結合LIF在煤礦突水識別中的應用[J].光譜學與光譜分析,2019,39(8):2439.

[4]劉小龍.改進多元宇宙演算法求解大規模實值優化問題[J].電子與資訊學報,2019,41(7):1667.

[5]聚類方法：DBSCAN演算法研究（1）--DBSCAN原理、流程、引數設定、優缺點以及演算法

[6]聚類演算法初探（五）DBSCAN

「其他文章」