机器学习（十五）

2023-08-13 11:25| 来源: 网络整理| 查看: 265

原创不易，转载前请注明博主的链接地址：Blessy_Zhu https://blog.csdn.net/weixin_42555080 本次代码的环境：运行平台： Windows Python版本： Python3.x IDE： PyCharm 　

一从K-Means到DBSCAN

在认识DBSCAN之前，首先看一下它是要解决什么样的问题的！在文章机器学习（九）-k-means算法及优化和Python已经介绍了K-Means的基本用法，但是K-Means的局限性却是：  （1）当聚类的大小、密度、形状不同时，K-means 聚类的结果不理想  （2）数据集包含离群点时，K-means 聚类结果不理想  （3）两个类距离较近时，聚类结果不合理通过下面几幅图可以清晰的看到K-Means的局限性。　

针对上面的问题，提出了DBSACN模型。DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。什么是基于密度的聚类算法？直白翻译就是带有噪声应用的基于密度的空间聚类。

二 DBSCAN算法简介 2.1 DBSCAN中的几个定义

 （I ）密度 = 邻域(以Eps为半径)中点的个数  （II）核心点（ core point ）：如果该点的给定邻域内的点的个数超过给定的阈值MinPts（用户指定的参数）  （III）核心点是一个聚类的内部点  （IV）边界点（ border point ）：非核心点（它的EPS邻域中的点的个数少于MinPts），但它在落在某个核心点的邻域内  （V ）噪声点（ noise point ）：一个点既不是核心点也不是边界点　

2.2 DBSCAN的执行步骤

基本思想是：只要一个邻域中的点的密度大于域值MinPts ，就把它加到与之相近的聚类中去。（聚类使用密度可达的概念） DBScan需要二个参数：扫描半径 (eps)和最小包含点数(minPts)。任选一个未被访问(unvisited)的点开始，找出与其距离在eps之内(包括eps)的所有附近点。如果附近点的数量 ≥ minPts，则当前点与其附近点形成一个簇，并且出发点被标记为已访问(visited)。然后递归，以相同的方法处理该簇内所有未被标记为已访问(visited)的点，从而对簇进行扩展。如果附近点的数量 < minPts，则该点暂时被标记作为噪声点。如果簇充分地被扩展，即簇内的所有点被标记为已访问，然后用同样的算法去处理未被访问的点。　

2.3 DBSCAN算法描述

输入: 包含n个对象的数据库，半径e，最少数目MinPts; 输出:所有生成的簇，达到密度要求。 (1)Repeat (2)从数据库中抽出一个未处理的点； (3)IF抽出的点是核心点 THEN 找出所有从该点密度可达的对象，形成一个簇； (4)ELSE 抽出的点是边缘点(非核心对象)，跳出本次循环，寻找下一个点； (5)UNTIL 所有的点都被处理。 DBSCAN对用户定义的参数很敏感，细微的不同都可能导致差别很大的结果，而参数的选择无规律可循，只能靠经验确定。在这里插入图片描述

2.4 DBSCAN的时间空间复杂度 DBSCAN的时间复杂度 DBSCAN的基本时间复杂度 O(mX找出Eps邻域中的点所需要的时间) 其中m是点的个数在最坏情况下，时间复杂度是O(m2)在低维空间, 使用kd树可以有效地检索特定点给定距离内的所有点,时间复杂度可以降低到O(m log m)DBSCAN的空间复杂度为O(m) 对每个点, 只需要维持少量数据, 即簇标号和每个点是核心点、边界点还是噪声点的标识 2.5 DBSCAN: 确定 Eps和MinPts 点的第k个最近邻的距离称为k-距离，即Eps确定MinPts的基本思想簇中的诸点的k-距离一般很小噪声点的k-距离一般很大. 计算每个点的k-距离, 并由小到大排序, 绘制k-距离曲线预料该曲线某处, k-距离的急剧变化该处的k-距离对应于Eps 　　在这里插入图片描述

这种方法决定的Eps值依赖于k，但并不随k改变而剧烈变化 2.6 基于密度的聚类的优缺点优点：能识别任意形状、不同大小的聚类，对噪声数据不敏感在这里插入图片描述

缺点：算法复杂度大，需扫描整个数据集，查询每个数据对象，当数据量大时会造成频繁的I/O操作（可建立空间索引来降低计算量）对数据维数的伸缩性较差参数难以选择，聚类结果对参数敏感不能发现多密度聚类聚类的边界可能丢失不适合高维数据密度定义困难不适合多密度数据和变化密度的数据

如下图，A、B周围噪声的密度与C、D密度相同（用明暗表示）　

EPS小，可以发现C、D，但A、B和噪声为一个簇；EPS大，可以发现A、B，及周围噪声，但C、D及周围点都标记为噪声

三 DBSCAN的Python实例

用sklearn.datasets库中的方法，绘制了6000个二维样本点，然后利用DBSCAN算法实现样本点的聚类：

from sklearn import datasets import numpy as np import random import matplotlib.pyplot as plt import time plt.rcParams['font.sans-serif']=['SimHei'] plt.rcParams['axes.unicode_minus']=False 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(temp0: j=random.choice(gama) gama.remove(j) #未访问列表中移除 fil.append(j) #添加入访问列表 NeighborPts=findNeighbor(j,X,eps) if len(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 def generatorData(): X1, y1=datasets.make_circles(n_samples=5000, factor=.6, noise=.05) X2, y2 = datasets.make_blobs(n_samples=1000, n_features=2, centers=[[1.2,1.2]], cluster_std=[[.1]], random_state=9) X = np.concatenate((X1, X2)) return X if __name__=='__main__': eps=0.08 min_Pts=10 begin=time.time() X = generatorData() C=dbscan(X,eps,min_Pts) end=time.time() plt.figure(figsize=(12, 9), dpi=80) plt.scatter(X[:,0],X[:,1],c=C) plt.show() print("DBSCAN算法用时:",end-begin)

结果：在这里插入图片描述 DBSCAN算法用时:328.9198133945465

可以说DBSCAN的算法是非常吃GPU和CPU的，运行上述代码时，我的联想小新V1000系列的电脑嗡嗡作响！！！！主要是，该算法，首先要计算每个点的欧氏距离，然后在计算进行比较，时间复杂度较大！！！

四总结

可以说，虽然DBSCAN在解决密度和噪声点问题上较为优秀，但是实际上DBSCAN HAS A LONG WAY TO GO！！！！！比如：减少参数、参数的自动化；合适密度函数（高斯、混合密度、反向K近邻等）；如何对多密度、变化密度的数据集聚类；如何提高聚类的精度；高维、大规模数据集聚类技术等这篇文章就到这里了，欢迎大佬们多批评指正，也欢迎大家积极评论多多交流。

参考文章

1 DBSCAN算法简介及Python实现 2 鸢尾花三种聚类算法（K-means,AGNES,DBScan）的python实现

【本文地址】

机器学习（十五）

机器学习（十五）

今日新闻

推荐新闻