现在的位置: 首页 > 综合 > 正文

DBSCAN聚类算法的实现

2017年12月19日 ⁄ 综合 ⁄ 共 558字 ⁄ 字号 评论关闭

设有N个样本,样本为p维,

(1)计算距离矩阵D,时间复杂度为O(N*N*p);

(2)对距离矩阵的每一行进行从小到大排序,得到SD(sorted D),时间复杂度为O(N*N*log(N));

(3)根据Eps与MinPts,标注核心点、边界点和噪声点。

首先比较SD(:,MinPts)与Eps的大小,若前者小于后者,则为核心点,反之为非核心点。

对于非核心点,检验其Eps邻域中是否包含核心点,若包含,则为边界点,否则为噪声点。

(4)对于核心点和边界点,建立连接矩阵C(connect),若两点的距离小于Eps,则对应位置为1,反之为0。

特别地,C的对角线的元素取0。

(5)关键步:根据连接矩阵C,确定哪些点为一簇(cluster)。用数学的语言来说,就是找出集合的等价类。

算法

从C(1,1)出发,先沿着行往右走,遇到0继续向右,遇到1时,记录所在列的指标,然后开始沿着该列往下走,也是遇到0继续向下,遇到1,记录所在行的指标,然后换成沿着行往右走,直到行或者列的指标为N。

在上述的搜索过程中,设置标识变量flag,每次转换行列,将flag设为0,若移动一次,即遇到1,则flag不变,否则flag=移动一次后所在的列。若一次迭代后,flag=0,说明所有的点都已经分好簇,否则下次从C(flag,flag)处开始搜索。

抱歉!评论已关闭.