当前位置 博文首页 > Zhi Zhao的博客:MVO优化DBSCAN实现聚类
目录
一、MVO
1.基本概念
2.算法原理
3.算法的优缺点
4.算法流程
二、DBSCAN
1.基本概念
2.算法原理
3.算法的优缺点
4.算法流程
5.参数设置
6.MATLAB代码
三、MVO优化DBSCAN实现聚类
参考文献
MVO算法的思想启发于物理学中多元宇宙理论,通过对白/黑洞(宇宙)和虫洞等概念及其相互作用机理的数学化描述实现待优化问题的求解。
白洞:是一个只发射不吸收的特殊天体,并且是诞生一个宇宙的主要成分;
黑洞:刚好与白洞相反,它吸引宇宙中一切事物,所有的物理定律在黑洞中都会失效;
虫洞:连结白洞和黑洞的多维时空隧道,将个体传送到宇宙的任意角落,甚至是从一个宇宙到另一个宇宙,而多元宇宙通过白洞、黑洞、虫洞相互作用达到一个稳定状态。
MVO算法依据多元宇宙理论的3个主要概念:白洞、黑洞和虫洞来建立数学模型,定义候选解为宇宙,候选解的适应度为宇宙的膨胀率。迭代过程中,每一个候选解为黑洞,适应度好的宇宙依轮盘赌原理成为白洞,黑洞和白洞交换物质(维度更换),部分黑洞可以通过虫洞链接穿越到最优宇宙附近(群体最优附近搜索)。
3.1优点
主要的性能参数是虫洞存在概率和虫洞旅行距离率,参数相对较少,低维度数值实验表现出了相对较优异的性能。
3.2缺点
求解大规模优化问题的性能较差,算法缺乏跳出局部极值的能力,导致无法寻取全局最优解。
用MVO算法的伪代码描述其流程如下:
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是一种基于密度的聚类算法,它有两个重要的参数:Eps为定义密度时的领域半径,MinPts为定义核心点时的阈值。
(1) 核心点:在半径Eps内含有大于或者等于MinPts数目的点 。
(2) 边界点:在半径Eps内点的数量小于MinPts,但是落在核心点的邻域内 。
(3) 噪音点:既不是核心点也不是边界点的点。
cs