DBSCAN算法的过程是(),关于k值和dbscan的比较

　　对DBSCAN算法1的理解。dbscan(含噪声应用的基于密度的特殊聚类)介绍，基于密度聚类算法。密度可以理解为样本点的紧密度，紧密度需要用半径和最小样本量来评价。如果实际样本大小在指定半径内超过给定的最小样本大小阈值，则认为是高密度对象。DBSCAN密度聚类算法可以非常方便地发现样本集中的离群点，因此通常可以用来检测离群点。它可以发现任意形状的样本簇，具有很强的抗噪声能力。

　　1.1密度聚类相关概念

点的 epsilon 领域

:在某一点p p p给出其半径后得到的覆盖区域。

核心对象

:对于给定的最小样本量，如果某个点PP的 epsilon域至少包含M i n P t s MinPts MinPts个样本点，那么这个点p p p就是核心对象。

直接密度可达

:假设点p p为核心对象，点Q Q存在于点p p p的域中，则从点P P到点Q Q是直接密度可达的。

密度可达

:假设有一系列对象链P1、P2、P N P _ 1，P _ 2，P2 P1，PN，若p i p_i pi约为半径的直接密度和最小样本点M I in P t s min pts min pts可达P I 1 (I=1，2，n) P _ {I 1} (I=1，2，n) PI 1 (I=1，2，n)，那么p 1 p_1 p1即p 1，p2，p3，p4都是核心对象，它们是直接密度可达的。此时，在p4的区域中直接密度可达的点p5对于p1、p2和p3是密度可达的。

密度相连

:假设O点为核心对象，从O点出发，可以得到两个具有密度的点P和Q，那么P点和Q点是密度连通的。

聚类的簇

:群集包含由最大密度连接的样本点。

边界点

:假设P点为核心对象，B点包含在其定义域内。如果B点是非核心物体，则称为p点的边界点。

异常点

:不属于任何分类的采样点。

　　1.2密度聚类的步骤密度聚类的过程有点像“贪婪的蛇”，从某一点开始，不断向外扩展，直到获得一个最大密度连接，从而形成一个样本聚类。具体步骤如下：

　　(1)为密度聚类算法 epsilon 设置合理的半径，以及epsilon字段中包含的最小样本大小M i n P t s MinPts MinPts。

　　(2)从数据集中随机选择一个样本点p p p，检查其是否包含域中指定的最小样本量，如果包含，则将其定义为核心对象，形成一个聚类C C C C；否则，复制并选择一个采样点。

　　(3)对于核心对象p p p覆盖的其他样本点q q q，如果点q q q对应的 Epsilon域仍包含最小样本量M i n P t s MinPts MinPts，则其覆盖的所有样本点将归属于簇C C C

　　(4)重复步骤(3)，将最大密度连接中包含的样本点聚类成一类，形成一个大簇。

　　(5)步骤(4)完成后，返回步骤(2)，重复步骤(3)和(4)，直到没有新的样本点生成新的聚类时算法结束。

　　1.3 Python中的算法实现，可以直接调用sklearn子模块集群中的DBSCAN类实现。该类的语法和参数如下：

　　Cluster.dbscan (EPS=0.5，min _ samples=5，metric= educational ，metric _ params=none，algorithm= auto ，leaf _ size=30，p=none，n _ jobs=1) EPS:用于在密度聚类中设置 epep。Min_samples:用于设置 epsilon域的最小样本量；默认值为5。Metirc:用于指定计算点之间距离的方法。默认值是欧几里得距离。Metric_params:用于指定metirc对应的其他参数值。算法：在计算点间距离的过程中，用来指定搜索最近邻样本点的算法。默认值为“自动”，这意味着密度聚类将自动选择适当的搜索方法。如果是‘ball _ tree’，表示使用球树搜索最近邻。如果是‘KD _ tree’，则表示使用K-D树搜索最近邻。Leaf_size:参数算法为“ball_tree”或“kd_tree”时，用于指定一本书的叶子节点所包含的最大样本量，默认为30；该参数将影响搜索树的构建和搜索最近邻的速度。p:当参数‘公制’为酷笔距离时，p=1，表示计算点之间的曼哈顿距离；P=2，表示计算点之间的深情黄蜂距离；该参数的默认值为2。N_jobs:用于设置密度聚类算法并行计算所需的CPU数量。默认值为1，表示只使用一个CPU运行参数，即不使用并行运算功能。在DBSCAN类中，需要同时调整参数eps和min_samples，即通常指定几个候选值，从候选值中选择一个合理的阈值。当参数eps固定时，参数min_samples越大，形成的核心对象越少，会误判很多离群点，聚类数增加。反之，会产生大量的核心对象，导致聚类数据较少。在参数min_samples固定的情况下，参数eps越大，落入 epsilon域的点越多，导致核心对象越多，最终减少指称簇的数量。反而会导致核心对象大量减少，集群数量增加。当参数eps和min_samples不合理时，增加或减少聚类数总是错误的。

　　k均值和密度聚类的比较：

　　Kmeans聚类的缺点是不能对非球形聚类进行聚类，也非常容易出现极值，而密度聚类可以弥补其缺点。

　　1.4最近邻搜索算法1.4.1 KD树1.4.2球形树1.5相关知识点总结1.1什么是DBSCAN DBSCAN是一种基于密度的空间聚类算法。它不是定义聚类的个数，而是将足够高密度的区域划分成聚类，在有噪声的数据中寻找任意形状的聚类。在该算法中，聚类被定义为具有连通密度的最大点集。

　　这种密度算法一般假设可以通过样本分布的紧密程度来确定类型。同一类别的样本之间是紧密相连的，也就是说，离那个类别的任何一个样本不远的地方，必然有同一个类别的样本。通过将紧密连接的样本分类为一类，获得聚类类别。通过将所有紧密相连的样本分组到不同的类别中，我们最终得到所有聚类类别的结果。

　　2.优点和缺点：

　　可以对任意形状的密集数据集进行聚类，但是Kmeans一般只适合凸(球形)数据集。

　　它可以在聚类的同时发现离群点，并且对数据集中的离群点不敏感。

　　聚类效果不像Kmeans那样受初始值的影响。

　　缺点：

　　不适用于样本集密度不均匀，聚类间距差异很大的情况。此时聚类效果较差。

　　当样本数据较大时，聚类收敛时间较长。此时，在搜索最近邻时建立的KD树或球形树的规模可以是有限的。

　　Kmeans的参数调整相对复杂，需要联合调整距离阈值和域内最小样本数阈值。不同的参数组合对最终的聚类效果影响很大。