三、密度聚类

1. 密度聚类density-based clustering假设聚类结构能够通过样本分布的紧密程度确定。
2. 密度聚类算法从样本的密度的角度来考察样本之间的可连接性，并基于可连接样本的不断扩张聚类簇，从而获得最终的聚类结果。

3.1 DBSCAN 算法

1. DBSCAN是一种著名的密度聚类算法，它基于一组邻域参数 来刻画样本分布的紧密程度。

2. 给定数据集 ， 定义：

   • -邻域： 。

     即： 包含了样本集 中与 距离不大于 的所有的样本。

   • 核心对象core object：若 ，则称 是一个核心对象。

     即：若 的 -邻域中至少包含 个样本，则 是一个核心对象。

   • 密度直达directyl density-reachable：若 是一个核心对象，且 ， 则称 由 密度直达，记作 。

   • 密度可达density-reachable：对于 和 ， 若存在样本序列 ， 其中 ，如果 由 密度直达，则称 由 密度可达，记作 。

   • 密度相连density-connected：对于 和 ，若存在 ，使得 与 均由 密度可达，则称 与 密度相连 ，记作 。

3. DBSCAN算法的簇定义：给定邻域参数 ， 一个簇 是满足下列性质的非空样本子集：

   • 连接性 connectivity： 若 ，则 。
   • 最大性maximality：若 ，且 ， 则 。

   即一个簇是由密度可达关系导出的最大的密度相连样本集合。

4. DBSCAN算法的思想：若 为核心对象，则 密度可达的所有样本组成的集合记作 。可以证明 ： 就是满足连接性与最大性的簇。

   于是 DBSCAN算法首先任选数据集中的一个核心对象作为种子seed，再由此出发确定相应的聚类簇。

5. DBSCAN算法：

   • 输入：

     • 数据集
     • 邻域参数

   • 输出： 簇划分

   • 算法步骤：

     • 初始化核心对象集合为空集：

     • 寻找核心对象：

       • 遍历所有的样本点 ， 计算
       • 如果 ，则
     • 迭代：以任一未访问过的核心对象为出发点，找出有其密度可达的样本生成的聚类簇，直到所有核心对象都被访问为止。

6. 注意：

   • 若在核心对象 的寻找密度可达的样本的过程中，发现核心对象 是由 密度可达的，且 尚未被访问，则将 加入 所属的簇，并且标记 为已访问。
   • 对于 中的样本点，它只可能属于某一个聚类簇。因此在核心对象 的寻找密度可达的样本的过程中，它只能在标记为未访问的样本中寻找 （标记为已访问的样本已经属于某个聚类簇了）。

7. DBSCAN 算法的优点：

   • 簇的数量由算法自动确定，无需人工指定。
   • 基于密度定义，能够对抗噪音。
   • 可以处理任意形状和大小的簇。

8. DBSCAN 算法的缺点：

   • 若样本集的密度不均匀，聚类间距差相差很大时，聚类质量较差。因为此时参数 和 的选择比较困难。
   • 无法应用于密度不断变化的数据集中。

3.2 Mean-Shift 算法

1. Mean-Shift 是基于核密度估计的爬山算法，可以用于聚类、图像分割、跟踪等领域。

2. 给定 维空间的 个样本组成的数据集 ，给定一个中心为 、半径为 的球形区域 （称作兴趣域），定义其mean shift 向量为： 。

3. Mean-Shift 算法的基本思路是：

   • 首先任选一个点作为聚类的中心来构造兴趣域。

   • 然后计算当前的mean shift 向量，兴趣域的中心移动为： 。

     移动过程中，兴趣域范围内的所有样本都标记为同一个簇。

   • 如果mean shift 向量为 0 ，则停止移动，说明兴趣域 已到达数据点最密集的区域。

   因此Mean-Shift 会向着密度最大的区域移动。

   下图中：蓝色为当前的兴趣域，红色为当前的中心点 ；紫色向量为mean shift 向量 ，灰色为移动之后的兴趣域 。

   

4. 在计算mean shift 向量的过程中假设每个样本的作用都是相等的。实际上随着样本与中心点的距离不同，样本对于mean shift 向量的贡献不同。

   定义高斯核函数为： ，则重新mean shift 向量定义为：

   

   其中 称做带宽。 刻画了样本 距离中心点 相对于半径 的相对距离。

5. Mean_Shift 算法：

   • 输入：

     • 数据集
     • 带宽参数
     • 迭代阈值 ，簇阈值

   • 输出： 簇划分

   • 算法步骤：

     迭代，直到所有的样本都被访问过。迭代过程为（设已有的簇为 ）：

     • 在未访问过的样本中随机选择一个点作为中心点 ，找出距它半径为 的兴趣域，记做 。

       将 中的样本的簇标记设置为 （ 一个新的簇）。

     • 计算当前的mean shift 向量，兴趣域中心的移动为：

       

       在移动过程中，兴趣域内的所有点标记为访问过，并且将它们的簇标记设置为 。

     • 如果 ，则本次结束本次迭代。

     • 设已有簇中，簇 的中心点 与 距离最近，如果 ，则将当前簇和簇 合并。

       合并时，当前簇中的样本的簇标记重新修改为 。

     当所有的样本都被访问过时，重新分配样本的簇标记（因为可能有的样本被多个簇标记过）：若样本被多个簇标记过，则选择最大的那个簇作为该样本的簇标记。即：尽可能保留大的簇。

6. 可以证明：Mean_Shift 算法每次移动都是向着概率密度函数增加的方向移动。

   在 维欧式空间中，对空间中的点 的概率密度估计为：

   

   其中：

   • 表示空间中的核函数， 为带宽矩阵。
   • 通常 采用放射状对称核函数 ， 为 的轮廓函数， （一个正数）为标准化常数从而保证 的积分为 1 。
   • 通常带宽矩阵采用 ， 为带宽参数。

   因此有： 。则有梯度：

   

   记 的导数为 。取 为新的轮廓函数， （一个正数）为新的标准化常数， 。

   则有：

   

   定义 ，则它表示基于核函数 的概率密度估计，始终为非负数。

   根据前面定义：，则有： 。

   因此 正比于 ，因此mean shift 向量的方向始终指向概率密度增加最大的方向。

   上式计算 时需要考虑所有的样本，计算复杂度太大。作为一个替代，可以考虑使用 距离 内的样本，即兴趣域 内的样本。即可得到： 。

7. Mean-Shift 算法优点：

   • 簇的数量由算法自动确定，无需人工指定。
   • 基于密度定义，能够对抗噪音。
   • 可以处理任意形状和大小的簇。
   • 没有局部极小值点，因此当给定带宽参数 时，其聚类结果就是唯一的。

8. Mean_Shift 算法缺点：

   • 无法控制簇的数量。
   • 无法区分有意义的簇和无意义的簇。如：在Mean_Shift 算法中，异常点也会形成它们自己的簇。