需要源码请点赞关注收藏后评论区留言私信~~~
基于密度的聚类
基于划分和聚类和基于层次的聚类往往只能发现凸型的聚类簇,为了更好的发现任意形状的聚类簇,提出了基于密度的聚类算法
算法原理
基于密度的聚类算法的主要思想是:只要邻近区域的密度(对象或数据点的数目)超过某个阈值 ,就把它加到与之相近的聚类中。也就是说,对给定类中的每个数据点,在一个给定范围的区域中必须至少包含某个数目的点
基于密度的聚类算法代表算法有:DBSCAN算法、OPTICS算法及DENCLUE算法等
DBSCAN算法涉及2个参数5个定义
2个参数:
Eps: 邻域最大半径
MinPts: 在 Eps 邻域中的最少点数
五个定义如下图所示
定义1(Eps邻域) 给定一个对象 p ,p 的Eps 邻域 NEps(p)定义为以 p 为核心,以Eps为半径的d 维超球体区域,即: 其中,D为d维实空间上的数据集, dist ( p, q)表示D中的2个对象p和q之间的距离。
定义2(核心点与边界点)对于对象p∈D,给定一个整数MinPts,如果p的Eps邻域内的对象数满足|NEps(p)|≥MinPts ,则称p为(Eps,MinPts ) 条件下的核心点;不是核心点但落在某个核心点的Eps 邻域内的对象称为边界点
定义3(直接密度可达) 如图所示,给定 (Eps,MinPts ) ,如果对象 p 和 q 同时满足如下条件: p∈ NEps(q) ; |NEps(q)|≥MinPts (即q是核心点), 则称对象 p 是从对象 q 出发,直接密度可达的。
定义4(密度可达)
如图所示,给定数据集D,当存在一个对象链 p1,p2,p3,…,pn, 其中 p1 = q , p N= p,对于 pi ∈D ,如果在条件(Eps,MinPts ) 下 pi+1从pi 直接密度可达,则称对象p从对象q在条件 (Eps,MinPts )下密度可达。密度可达是非对称的,即p从q密度可达不能推出q也从p密度可达
定义5(密度相连)
如图所示,如果数据集D中存在一个对象o,使得对象p和q是从o在 (Eps,MinPts )条件下密度可达的,那么称对象p和q在 (Eps,MinPts )条件下密度相连。密度相连是对称的
可视化密度可达 密度不可达等等情况如下
DBSCAN算法流程图如下
DBSCAN需要对数据集中的每个对象进行考察,通过检查每个点的参数
邻域寻找聚类,将具有足够高密度的区域划分为簇,并可以在带有“噪声”的空间数据库中发现任意形状的聚类
但是,DBSCAN算法对用户设置的参数敏感,Eps和MinPts的设置会影响聚类的效果。针对这一问题,OPTICS(Ordering Points to Identify the Clustering Structure)算法被提出,它通过引入核心距离和可达距离,使得聚类算法对输入的参数不敏感
DBSCAN算法实现如下
聚类效果如下
部分代码如下
from sklearn import datasets import numpy as np import random import matplotlib.pyplot as plt def findNeighbor(j,X,eps): N = [] for p in range(X.shape[0]): #找到所有邻域内对象 temp = np.sqrt(np.sum(np.square(X[j]-X[p]))) #欧氏距离 if(temp<=eps): N.append(p) return N def dbscan(X,eps,min_Pts): k = -1 NeighborPts = [] #array,某点领域内的对象 Ner_Nex for x in range(len(X))] #初始所有点标为未访问 cluster = [-1 for y in range(len(X))] while len(gama)>0: j = random.choice(gama) gama.remove(j) #未访问列表中移除 fil.append(j) #添加入访问列表 NeighborPts = findNeighbor(j,X,eps) if len(NeighborPts) < min_Pts: cluster[j] = -1 #标记为噪声点 else: k = k+1 cluster[j] = k for i in NeighborPts: if i not in fil: gama.remove(i) fil.append(i) Ner_NeighborPts=findNeighbor(i,X,eps) if len(Ner_NeighborPts) >= min_Pts: for a in Ner_NeighborPts: if a not in NeighborPts: NeighborPts.append(a) if (cluster[i]==-1): cluster[i]=k return cluster X1, y1 = datasets.make_circles(n_samples=1000, factor=.6,noise=.05) X2, y2 = datasets.make_blobs(n_samples = 300, n_features = 2, centers = [[1.2,1.2]], cluster_st C = dbscan(X,eps,min_Pts) plt.figure(figsize = (12, 9), dpi = 80) plt.scatter(X[:,0],X[:,1],c = C) plt.show()
创作不易 觉得有帮助请点赞关注收藏~~~