基于密度的聚类之Dbscan算法
一.算法概述
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同,它将簇定义为密度相连的点的最大集合,能够把具有足够高密度的区域划分为簇,并可在噪声的空间数据库中发现任意形状的聚类(笔者认为是因为他不是基于距离的,基于距离的发现的是球状簇)。
该算法利用基于密度的聚类的概念,即要求聚类空间中的一定区域内所包含对象(点或其他空间对象)的数目不小于某一给定阈值。DBSCAN算法的显著优点是聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类。但是由于它直接对整个数据库进行操作且进行聚类时使用了一个全局性的表征密度的参数,因此也具有两个比较明显的弱点:
(1)当数据量增大时,要求较大的内存支持I/O消耗也很大;
(2)当空间聚类的密度不均匀、聚类间距差相差很大时,聚类质量较差(有些簇内距离较小,有些簇内距离很大,但是Eps是确定的,所以,大的点可能被误判断为离群点或者边界点,如果Eps太大,那么小距离的醋内,可能会包含一些离群点或者边界点,KNN的k也存在同样的问题)。
(1)与K-MEANS比较起来,不需要输入要划分的聚类个数;
(2)聚类簇的形状没有偏倚(这个不明白啥意思);
(3)可以在需要时输入过滤噪声的参数;
二.算法基本定义
三.算法描述
3.1 算法前提
DBSCAN算法基于一个事实:一个聚类可以由其中的任何核心对象唯一确定。等价可以表述为:任一满足核心对象条件的数据对象p,数据库D中所有从p密度可达的数据对象o所组成的集合构成了一个完整的聚类C,且p属于C。
3.2 算法流程
四.算法实现
%% DBSCAN
clear all;
clc;
%% 导入数据集
% data = load('testData.txt');
data = randn(50,2);
% 定义参数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
么么哒.............
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);
注意:prod是数组内元素的乘积,A^n是A*A*....*A,A.^n是A中每个元素的n次方。
相关文章
- Python opencv图像处理基础总结(七) 基于分水岭算法的图像分割
- 文献阅读(基于TrAdaBoost- LSTM算法对大规模连续水质缺失值)与TradaBoost算法的学习
- python svm原理和实现,svm相关算法
- 人工智能-损失函数-优化算法:牛顿法的背后原理【二阶泰勒展开】
- 异常检测:TODS工具库(与PyOD类似)【包含多种时间序列上的异常检测算法】
- 基于蚂蚁优化算法的BP神经网络在负荷预测中的应用研究(Matlab完整代码实现)
- 【风光场景生成】基于改进ISODATA的负荷曲线聚类算法(Matlab代码实现)
- 基于粒子群优化算法的电动汽车充放电V2G研究(Matlab代码实现)
- 【配电网优化】基于串行和并行ADMM算法的配电网优化研究(Matlab代码实现)
- 【单目标优化算法】蜣螂优化算法(Dung beetle optimizer,DBO)(Matlab代码实现)
- 【工程应用一】 多目标多角度的快速模板匹配算法(基于NCC,效果无限接近Halcon中........)
- A.机器学习入门算法(九): 基于线性判别模型的LDA手写数字分类识别
- [Python]基于K-Nearest Neighbors[K-NN]算法的鸢尾花分类问题解决方案
- 基于灰度世界、完美反射、动态阈值等图像自动白平衡算法的原理、实现及效果
- 基于 flashtext 模块使用 FlashText 算法进行字符串查找和替换
- 03【C语言 & 趣味算法】(值得品味的一道题)打鱼还是晒网?结构体的简单应用。函数的应用。判断闰年的应用。求指定日期距1990年1月1日的天数。
- 基于麻雀算法ssa的测试函数Eggholder优化,测试函数的100求解方法之11
- 实战 | 粘连物体分割与计数应用(二)--基于距离变换+分水岭算法 Halcon/OpenCV实现比较
- 《算法图解》第八章之贪婪算法
- 计算机视觉系列-轻松掌握 MMDetection 中常用算法 YOLOF(一)
- Mahout 系列之--canopy 算法
- 读<大数据日知录:架构与算法>有感