|
阅读：5312回复：0
OPTICS聚类算法
在聚类分析时，对于簇形状不规则的数据，像k-means这类基于划分的方法就不再适用了，因为它们划分方法都是用于发现“球状簇”的。所以在解决任意簇形状的聚类问题时，会把大量的噪声或者离群点也包含在簇中。
为解决这种任意簇形状的聚类问题，可以采用一种与划分聚类或者层次聚类不同的聚类方法——基于密度聚类。 DBSCAN算法概念 DBSCAN聚类、OPTICS聚类等都是基于密度的聚类方法。在说OPTICS之前，需要先介绍关于DBSCAN算法的一些专门定义的概念。 核心对象：一个数据点可被称为核心对象，如果以这个数据点为球心，以长度ϵϵ为半径的超球面区域内，至少有MinPtsMinPts个数据点。为了后面叙述简单，我将这个核心对象称为(ϵ,MinPts)(ϵ,MinPts)-核心对象，将它的这个球面区域称为核心对象的ϵϵ-邻域。 直接密度可达：对于(ϵ,MinPts)(ϵ,MinPts)-核心对象O1O1和对象O2O2，我们说O2O2是从O1O1直接密度可达的，如果O2O2在O1O1的ϵϵ-邻域内。注意，这里只要求O1O1是核心对象，而O2O2可以是任意对象（数据点）。也就是说，定义“A从B（或从B到A）直接密度可达”中，作为出发点的BB一定得是核心对象。 密度可达：从核心对象O1O1到对象OnOn（这里同样不要求OnOn是核心对象）是密度可达的，如果存在一组对象链{O1,O2,…,On}{O1,O2,…,On}，其中OiOi到Oi+1Oi+1都是关于(ϵ,MinPts)(ϵ,MinPts)直接密度可达的。实际上，从这个定义我们不难看出，{O1,O2,…,On−1}{O1,O2,…,On−1}都必须是核心对象。 密度相连：两个对象O1,O2O1,O2（注意，这里不要求是核心对象）是密度相连的，如果存在一个对象pp，使得pp到O1O1，pp到O2O2都是密度可达的。这个定义是对称的，即O1O1与O2O2是密度相连的，则O2O2与O1O1也是密度相连的。 上面4个定义中，后两个容易混淆。其实可以这样想，所谓密度可达，是说可以“一条道”走过去；而所谓密度相连，是说可以找到一个中间点，从这个中间点出发，可以分别“一条道”走到两边。 关于密度相连的理解是整个DBSCAN算法的核心，他实际代表的意义可以这样理解：对于任意形状的簇来说，一定存在这样一个点，使得组成这个簇的点都能从这个点出发，通过一条“稠密”的路径到达。换句话说，簇中的点一定是相互密度相连的。 还有两个区别于“核心对象”的概念，那就是“噪声对象”和“边缘对象”。在用DBSCAN对数据做聚类分析时，“噪声对象”也是一个非常重要的结果。所以，最好的算法是在给出聚好的类之外，也给出噪声点。为了让整个算法看起来清晰，在讲算法步骤之前，先给出“噪声对象”和“边缘对象”的定义。 噪声对象：不是核心对象，且也不在任何一个核心对象的ϵϵ-邻域内； 边缘对象：顾名思义是类的边缘点，它不是核心对象，但在某一个核心对象的ϵϵ-邻域内； 总之，对于数据集中的任意一个点，它要么是核心对象，要么是噪声对象，要么是边缘对象。 DBSCAN算法思路 DBSCAN 算法有两个参数：半径 eps 和密度阈值 MinPts，具体步骤为： 1、以每一个数据点 xi 为圆心，以 eps 为半径画一个圆圈。这个圆圈被称为 xi 的 eps 邻域 2、对这个圆圈内包含的点进行计数。如果一个圆圈里面的点的数目超过了密度阈值 MinPts，那么将该圆圈的圆心记为核心点，又称核心对象。如果某个点的 eps 邻域内点的个数小于密度阈值但是落在核心点的邻域内，则称该点为边界点。既不是核心点也不是边界点的点，就是噪声点。 3、核心点 xi 的 eps 邻域内的所有的点，都是 xi 的直接密度直达。如果 xj 由 xi 密度直达，xk 由 xj 密度直达。。。xn 由 xk 密度直达，那么，xn 由 xi 密度可达。这个性质说明了由密度直达的传递性，可以推导出密度可达。 4、如果对于 xk，使 xi 和 xj 都可以由 xk 密度可达，那么，就称 xi 和 xj 密度相连。将密度相连的点连接在一起，就形成了我们的聚类簇。 用更通俗易懂的话描述就是如果一个点的 eps 邻域内的点的总数小于阈值，那么该点就是低密度点。如果大于阈值，就是低密度点。如果一个高密度点在另外一个高密度点的邻域内，就直接把这两个高密度点相连，这是核心点。如果一个低密度点在高密度点的邻域内，就将低密度点连在距离它最近的高密度点上，这是边界点。不在任何高密度点的 eps 邻域内的低密度点，就是异常点。 DBSCAN优点： 1、对噪声不敏感。这是因为该算法能够较好地判断离群点，并且即使错判离群点，对最终的聚类结果也没什么影响。 2、能发现任意形状的簇。这是因为DBSCAN 是靠不断连接邻域呢高密度点来发现簇的，只需要定义邻域大小和密度阈值，因此可以发现不同形状，不同大小的簇。 DBSCAN 缺点： 1、对两个参数的设置敏感，即圈的半径 eps 、阈值 MinPts。 2、DBSCAN 使用固定的参数识别聚类。显然，当聚类的稀疏程度不同，聚类效果也有很大不同。即数据密度不均匀时，很难使用该算法。 3、如果数据样本集越大，收敛时间越长。 OPTICS算法 如此可见，DBSCAN算法的缺点是：（1）无法对密度不同的样本集进行很好的聚类；（2）该算法需要用户输入半径和阀值.。 于是有人提出了OPTICS算法，这个算法有效的解决了密度不同导致的聚类效果不好的问题，并且它并不显示地产生数据集聚类，而是为聚类分析生成一个增广的簇排序（如以样本点输出次序为横轴，以可达距离为纵轴的坐标图）。它代表了各样本点基于密度的聚类结构，它包含的信息等价于从一个广泛的参数设置所获得的基于密度的聚类。换句话说，从这个排序中可以得到基于任何半径和任何阀值的聚类。 具体步骤如下 输入：样本集D, 邻域半径E, 给定点在E领域内成为核心对象的最小领域点数MinPts 输出：具有可达距离信息的样本点输出排序 1、创建两个队列，有序队列和结果队列。（有序队列用来存储核心对象及其该核心对象的直接可达对象，并按可达距离升序排列；结果队列用来存储样本点的输出次序。你可以把有序队列里面放的理解为待处理的数据，而结果队列里放的是已经处理完的数据）； 2、如果所有样本集D中所有点都处理完毕，则算法结束。否则，选择一个未处理（即不在结果队列中）且为核心对象的样本点，找到其所有直接密度可达样本点，如过该样本点不存在于结果队列中，则将其放入有序队列中，并按可达距离排序； 3、如果有序队列为空，则跳至步骤2（重新选取处理数据）。否则，从有序队列中取出第一个样本点（即可达距离最小的样本点）进行拓展，并将取出的样本点保存至结果队列中(如果它不存在结果队列当中的话)。然后进行下面的处理。 3.1.判断该拓展点是否是核心对象，如果不是，回到步骤3（因为它不是核心对象，所以无法进行扩展了。那么就回到步骤3里面，取最小的。这里要注意，第二次取不是取第二小的，因为第一小的已经放到了结果队列中了，所以第二小的就变成第一小的了。）。如果该点是核心对象，则找到该拓展点所有的直接密度可达点； 3.2.判断该直接密度可达样本点是否已经存在结果队列，是则不处理，否则下一步； 3.3.如果有序队列中已经存在该直接密度可达点，如果此时新的可达距离小于旧的可达距离，则用新可达距离取代旧可达距离，有序队列重新排序(因为一个对象可能直接由多个核心对象可达，因此，可达距离近的肯定是更好的选择)； 3.4.如果有序队列中不存在该直接密度可达样本点，则插入该点，并对有序队列重新排序； 4、迭代2，3。 5、算法结束，输出结果队列中的有序样本点。 其核心思想在于：1、较稠密簇中的对象在簇排序中相互靠近； 2、一个对象的最小可达距离给出了一个对象连接到一个稠密簇的最短路径。 参考 https://blog.csdn.net/u014593570/article/details/77746904 https://blog.csdn.net/guoziqing506/article/details/80318529 https://blog.csdn.net/denghecsdn/article/details/82793940 https://blog.csdn.net/z962013489/article/details/86593031 |
|
