开发者学堂课程【高校精品课北京理工大学数据仓库与数据挖掘(下)：Density- and Grid-Based Methods】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/1041/detail/15651
Density- and Grid-Based Methods
内容介绍：
一、基于密度的聚类方法中 DBSCAN 算法
二、DBSCAN 算法小结
三、基于网格的聚类
本课程继续数据仓库与数据挖掘的学习。主要介绍基于密度和基于网格的聚类方法。
一、基于密度的聚类方法中 DBSCAN 算法
首先来看一下基于密度的聚类方法。在基于密度的聚类算法中，会介绍 DBSCAN 算法。DBSCAN 算法是基于密度聚类算法的代表。首先回顾一下基于密度定义的蔟。基于密度定义的蔟指的是这个蔟是一个稠密的区域，这些稠密的区域是被密度比较低的区域分割得到的。在进于密度的定义的蔟中，一个蔟就是密度相连点的最大集合。DBSCAN 算法中，密度是用一个特定区间中数据对象的数目来代表。
1. DBSCAN 算法中使用参数
首先来看一下，在 DBSCAN 算法中所使用的参数。DBSCAN 中，需要设置两个参数，一个是 Eps（ξ）一个是 MinPts，Eps（ξ）指的是邻域半径，通过设置 Eps（ξ）半径可以指定一个范围大小。MinPts 的含义是最小密度，是点的数目，可以通过设置 MinPts 来确定，从一区域的密度。在 DBSCAN 算法中，一个点 q 的 Eps（ξ）邻域，指的是离这个点q的距离小 Eps（ξ）半径的所有点的集合。
2. DBSCAN 算法数据对象
DBSCAN 算法中所有的数据对象被划分为三类。
（1）、三类点
第一类是核心点。核心点指的是位于稠密区域的，一般指的是某一个蔟。对于核心点来说，指的是以这个点为中心，Eps（ξ）半径为邻域的范围内，它的密度是要大于 MinPts。
第二类点，是叫做边界点。就是下图中左上角的点。对于边界点来说。它是某一个核心点的邻居，但是对于边界点，以它为中心 Eps（ξ）为半径的邻域范围内数据对象的数目是小于 MinPts 的。在实际中边界点往往代表的是蔟的边缘地。而异常点指的是不属于任何蔟的点。
（2）、三类点例子
首先通过一个例子介绍三类点。设 MinPts 为7，Eps（ξ）半径为1 cm。对于 ABC三个点来说。以 a 点为中心，以1 cm 为半径的一个邻域范围内，点的数目是大于等于七的，所以对于 a 来说，它是一个核心点。
对于点 b 来说，它的 Eps（ξ）邻域范围内的数据密度是小于七的。但是可以看到 b 点落入到了核心点 a 的 Eps（ξ）邻域范围内，所以 b 这个点它是边界点。
对于点 c 来说，它的 Eps（ξ）邻域范围内的数据密度依然是小于 MinPts 的，而且对于点 c 来说，它不是任意核心对象的邻居，所以把点 c 划分为异常点。
（3）、三类点在聚类结果中表现
下图就展示了核心点，边界点和异常点，在聚类结果中的表现。左边的是数据的原始分布图。右边的是得到了聚类结果之后的图，其实可以看到绿色的这一部分表示的就是核心点，相当于是数据分布比较稠密的区域。而蓝色的点代表的就是边界点，它往往是位于蔟的边界，代表的是一些数据分布不那么稠密的点，但是这些点又是某一些核心点的邻居。那么此外红色这一部分就代表的是噪音，或者是异常点，它是不属于任何蔟的。
3. DBSCAN 算法中数据对象关系划分
通过 DBSCAN 算法，将数据对象之间的关系划分为三类。
（1）、直接密度可达
第一类是叫做直接密度可达。如果一个数据点 p 是另外一个数据点 q 的直接密度可达点，必须满足以下两个要求。
第一个要求就是 p 一定是属于 Eps（ξ）邻域的。第二个要求就是数据点 q 它一定是核心点，也就是以 q 为圆心，Eps（ξ）半径为邻域的一个范围内数据点的个数需要大于等于 MinPts 的。那么下图像一个 q 这个点，就是一个核心点，那么 p 点刚好落入到它的邻域范围，所以可以说点 p 是点 q 的直接密度可达点。那么对于点p，那么它可以是核心的也可以是边界的。
（2）、密度可达关系
再来看一下点和点之间的密度可达关系。那如果一个点 p 是另外一个点 q 的密度可达点，那么就一定会存在这样的一个序列 p1P2P3 一直到 pn，其中 p1 是等于 q的，pn 是等于 p 的。在这个序列中，任意一个点 pi+1 都是它前一个点pi的直接密度可达点，那么可以看到，那么 p2 是 q 点的直接密度可达点，那么同理 p 又是 p2 直接密度可达点，所以说 p 是 q 的密度可达点。
（3）、密度相关
第三种关系点和点之间的关系就是密度相连。如果一个点 p 和一个点 q 是密度相连的，那么一定会存在一个点 o，那其中 p 和 q 都是这个点 o 的密度可达点。
通过这样的三个关系的定义，那么对于一个蔟来说，它就是一个密度相连点的最大集合。
4. DBSCAN 算法过程
来看一下，对于 DBSCAN 算法的过程。DBSCAN 算法的过程很简单，它就是利用核心点，从每一个核心点去出发，找到一个最大的密度相连的区域。
那么首先，算法第一步就是随机的选择一个点 p，然后找到这个 p 点的所有的密度可达点，如果这个 p 是一个核心点，那么这样的一个从 p 点出发的一个蔟就找到了，如果 p 点它不是一个核心点，而是一个边界点，那么就可以选择下一个数据点，也就是从下一个点出发再去找一个最大的密度相连的区域。重复以上过程，一直到所有的数据对象都被反映完。
5. DBSCAN 算法的复杂度
对于 DBSCAN 算法的复杂度，如果数据对象被进行排序，那么它的算法复杂度是 O（nlongn）就是可以降低为 O（nlongn）程度，如果数据对象没有被建立索引，那么它的一般的复杂度是 O（n的平方）。
6.DBSCANDBSCAN 算法的特点
来看一下 DBSCAN 算法的特点。
（1）、设定两参数
对于 DBSCAN 算法来说，虽然它不需要去指定蔟的数目，但是它需要设定两个参数，就是 Eps（ξ）半径和最小密度 MinPts 。对于 DBSCAN 算法来说，它对于这两个参数是比较敏感的，可以看一下，下图展示的是使用不同的参数，对于这两个数据集的划分。
可以看到它的划分结果就是聚类结果差异性是比较大的。
（2）、可以解决噪音和形状问题
那么，对于 DBSCAN 算法来说，因为它的蔟是基于密度定义的，所以说，对于存在噪音的数据集 DBSCAN 算法能够工作得很好。而且如果蔟，比如是非突形状，甚至是相互缠绕的，DBSCAN 算法也是能够非常有效的去检测到一些不规则的蔟的形状。
（3）、DBSCAN 算法效果不好的情况
再来看一下，当什么情况下 DBSCAN 算法，它的效果不太好，首先，第一种情况就是如果数据及分布的密度变化比较大，那么这个时候 DBSCAN 算法的效果就不太好，那比如下图这两个聚类的参数差异是非常非常小的，但是得到的结果差异性很大，因为 DBSCAN 算法的参数主要是只设定了一个最小密度，所以说它认为就是所有数据对象的分布应该是尽可能的平均的，因此当数据集它的数据分布密度变化比较大或者是高维数据，那么这个时候 DBSCAN 算法它得到的聚类结果就不太理想。
7.合理设置参数
那既然讲到了 DBSCAN 算法，对于参数 Eps（ξ）邻域和最小密度 MinPts 很敏感，那怎么样去合理的设置这两个参数呢？一个长用的办法就是观察数据集中，所有数据对象，它的第k个最近邻的对象距离。那么比如下图就画出了一个数据集的第四个最近邻对象距离。
那么，如果数据集的分布是比较均匀的，那大部分数据对象的第 k 个最近的距离应该是差不多的，变化不大，那么有少部分数据对象，它的第 k 个的最近邻的距离可能会变化比较大，那么这些点可能就是少数的噪音点。图中大部分的数据对象，它的第四个最近零对象的距离，都是在一个4到8之间，极少部分数据的第四个最近邻的距离，就突然变得很大，所以说通过观察这样的数据集，所有数据对象的第 k 个最近邻的距离 k 的值为四，这个为四的这样的一个最近邻所对应的这样的一个距离就可以作为这样的 Eps（ξ）半径。
这就是在 DBSCAN 算法中如何去确定它的这两个参数的方法。
二、DBSCAN 算法小结
最后对基于密度的 DBSCAN 算法，做一个小结，对于 DBSCAN 算法来说，它的一个优势是不需要确定 k 值，也就是蔟的数目是不需要去确定的，而且，它能够发现任意形状的蔟，能够处理数据集中的噪音，只需要扫描一遍。
但是，它需要去确定这样的一个密度参数和一个邻域大小。
三、基于网格的聚类
再介绍一下基于网格的聚类。基于网格的聚类，它要依赖多分辨率的，网格数据结构。
1. 网格数据结构
首先介绍一下网格数据结构，网格数据结构就类似于一种金字塔的形状，那么它是将整个数据空间划分成为若干小方格，那么最上层的一个小方格会对应到它下一层的若干个小格，这个就是网格层次聚类算法中的多分辨率的网格数据结构。
有了这样的网格数据结构，那么每一层上的特征就是可以经过累计计算，比如假设用每一个小方格的它的落入到这个小方格中的数据对象的数目、均值、方差、最小最大值来作为这个方格的特点，那么它上一级的方格的这些特征值可以通过下一级方格，这种特征值的一些简单的代数运算得到。
2. 网格的聚类算法过程
最后来看一下基于网格的聚类算法的过程，首先第一步，就是要定义一个比较合适的多分辨率的网格数据结构，然后再定义了网格结构之后，要把数据对象合理的分配到每个网格中去，然后第三步，就是要设立一个合适的阈值τ，然后将一些数据分布对象比较稀疏的网格过滤掉，保留一些数据密度比较稠密的一些网格，最后一步，就是要检索出这些稠密网格所构成的连通区域，这些联通区域就是蔟。
关于基于密度的聚类算法和基于网格的聚类算法，就介绍到这里。
