Question

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

3.1 DBSCAN 算法

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

2. 给定数据集 $ MathJax-Element-470 $ ， 定义：

   • $ MathJax-Element-397 $ -邻域： $ MathJax-Element-335 $ 。

     即： $ MathJax-Element-385 $ 包含了样本集 $ MathJax-Element-548 $ 中与 $ MathJax-Element-523 $ 距离不大于 $ MathJax-Element-339 $ 的所有的样本。

   • 核心对象core object：若 $ MathJax-Element-386 $ ，则称 $ MathJax-Element-523 $ 是一个核心对象。

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

   • 密度直达directyl density-reachable：若 $ MathJax-Element-523 $ 是一个核心对象，且 $ MathJax-Element-347 $ ， 则称 $ MathJax-Element-367 $ 由 $ MathJax-Element-523 $ 密度直达，记作 $ MathJax-Element-350 $ 。

   • 密度可达density-reachable：对于 $ MathJax-Element-523 $ 和 $ MathJax-Element-367 $ ， 若存在样本序列 $ MathJax-Element-353 $ ， 其中 $ MathJax-Element-354 $ ，如果 $ MathJax-Element-355 $ 由 $ MathJax-Element-356 $ 密度直达，则称 $ MathJax-Element-367 $ 由 $ MathJax-Element-523 $ 密度可达，记作 $ MathJax-Element-374 $ 。

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

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

   • 连接性 connectivity： 若 $ MathJax-Element-371 $ ，则 $ MathJax-Element-372 $ 。
   • 最大性maximality：若 $ MathJax-Element-373 $ ，且 $ MathJax-Element-374 $ ， 则 $ MathJax-Element-375 $ 。

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

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

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

5. DBSCAN算法：

   • 输入：

     • 数据集 $ MathJax-Element-470 $
     • 邻域参数 $ MathJax-Element-381 $

   • 输出： 簇划分 $ MathJax-Element-473 $

   • 算法步骤：

     • 初始化核心对象集合为空集： $ MathJax-Element-383 $

     • 寻找核心对象：

       • 遍历所有的样本点 $ MathJax-Element-384 $ ， 计算 $ MathJax-Element-385 $
       • 如果 $ MathJax-Element-386 $ ，则 $ MathJax-Element-387 $

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

6. 注意：

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

7. DBSCAN 算法的优点：

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

8. DBSCAN 算法的缺点：

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

3.2 Mean-Shift 算法

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

2. 给定 $ MathJax-Element-434 $ 维空间的 $ MathJax-Element-400 $ 个样本组成的数据集 $ MathJax-Element-544 $ ，给定一个中心为 $ MathJax-Element-459 $ 、半径为 $ MathJax-Element-462 $ 的球形区域 $ MathJax-Element-482 $ （称作兴趣域），定义其mean shift 向量为： $ MathJax-Element-405 $ 。

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

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

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

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

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

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

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

   

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

   定义高斯核函数为： $ MathJax-Element-409 $ ，则重新mean shift 向量定义为：

   $ \mathbf{\vec M}(\mathbf{\vec x}) = \mathbf{\vec m}(\mathbf{\vec x}) - \mathbf{\vec x},\quad \mathbf{\vec m}(\mathbf{\vec x})=\frac{\sum_{\mathbf{\vec x}_i\in \mathbb S}\mathbf{\vec x}_ig(||\frac{\mathbf{\vec x}_i-\mathbf{\vec x}}{h}||^2)} {\sum_{\mathbf{\vec x}_i\in \mathbb S}g(||\frac{\mathbf{\vec x}_i-\mathbf{\vec x}}{h}||^2)} $

   其中 $ MathJax-Element-462 $ 称做带宽。 $ MathJax-Element-411 $ 刻画了样本 $ MathJax-Element-523 $ 距离中心点 $ MathJax-Element-459 $ 相对于半径 $ MathJax-Element-462 $ 的相对距离。

5. Mean_Shift 算法：

   • 输入：

     • 数据集 $ MathJax-Element-470 $
     • 带宽参数 $ MathJax-Element-462 $
     • 迭代阈值 $ MathJax-Element-417 $ ，簇阈值 $ MathJax-Element-418 $

   • 输出： 簇划分 $ MathJax-Element-419 $

   • 算法步骤：

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

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

       将 $ MathJax-Element-482 $ 中的样本的簇标记设置为 $ MathJax-Element-426 $ （ 一个新的簇）。

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

       $ \mathbf{\vec x}\leftarrow \mathbf{\vec x}+\mathbf{\vec M}(\mathbf{\vec x})=\mathbf{\vec m}(\mathbf{\vec x})=\frac{\sum_{\mathbf{\vec x}_i\in \mathbb S}\mathbf{\vec x}_ig(||\frac{\mathbf{\vec x}_i-\mathbf{\vec x}}{h}||^2)} {\sum_{\mathbf{\vec x}_i\in \mathbb S}g(||\frac{\mathbf{\vec x}_i-\mathbf{\vec x}}{h}||^2)} $

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

     • 如果 $ MathJax-Element-427 $ ，则本次结束本次迭代。

     • 设已有簇中，簇 $ MathJax-Element-433 $ 的中心点 $ MathJax-Element-429 $ 与 $ MathJax-Element-459 $ 距离最近，如果 $ MathJax-Element-431 $ ，则将当前簇和簇 $ MathJax-Element-433 $ 合并。

       合并时，当前簇中的样本的簇标记重新修改为 $ MathJax-Element-433 $ 。

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

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

   在 $ MathJax-Element-434 $ 维欧式空间中，对空间中的点 $ MathJax-Element-459 $ 的概率密度估计为：

   $ \hat f(\mathbf{\vec x}) = \frac 1N\sum_{i=1}^N K_H(\mathbf{\vec x}-\mathbf{\vec x}_i),\quad K_H(\mathbf{\vec x})=|\mathbf H|^{-\frac 12}K(\mathbf H^{-\frac 12}\mathbf{\vec x}) $

   其中：

   • $ MathJax-Element-436 $ 表示空间中的核函数， $ MathJax-Element-437 $ 为带宽矩阵。
   • 通常 $ MathJax-Element-441 $ 采用放射状对称核函数 $ MathJax-Element-439 $ ， $ MathJax-Element-447 $ 为 $ MathJax-Element-441 $ 的轮廓函数， $ MathJax-Element-442 $ （一个正数）为标准化常数从而保证 $ MathJax-Element-443 $ 的积分为 1 。
   • 通常带宽矩阵采用 $ MathJax-Element-444 $ ， $ MathJax-Element-462 $ 为带宽参数。

   因此有： $ MathJax-Element-446 $ 。则有梯度：

   $ \nabla_{\mathbf{\vec x}}\hat f(\mathbf{\vec x}) =\frac {2c_k}{Nh^{n+2}}\sum_{k=1}^N(\mathbf{\vec x}-\mathbf{\vec x}_i)k^\prime(||\frac{\mathbf{\vec x}-\mathbf{\vec x}_i}{h}||^2) $

   记 $ MathJax-Element-447 $ 的导数为 $ MathJax-Element-448 $ 。取 $ MathJax-Element-449 $ 为新的轮廓函数， $ MathJax-Element-450 $ （一个正数）为新的标准化常数， $ MathJax-Element-451 $ 。

   则有：

   $ \nabla_{\mathbf{\vec x}}\hat f(\mathbf{\vec x}) =\frac {2c_k}{Nh^{n+2}}\sum_{i=1}^N(\mathbf{\vec x}-\mathbf{\vec x}_i)g(||\frac{\mathbf{\vec x}-\mathbf{\vec x}_i}{h}||^2)\\ = \frac {2c_k}{h^2c_g}\left[\frac{c_g}{Nh^n}\sum_{i=1}^Ng\left(||\frac{\mathbf{\vec x}-\mathbf{\vec x}_i}{h}||^2\right)\right]\left[\frac{\sum_{i=1}^N\mathbf{\vec x}_ig\left(||\frac{\mathbf{\vec x}-\mathbf{\vec x}_i}{h}||^2\right)}{\sum_{i=1}^Ng\left(||\frac{\mathbf{\vec x}-\mathbf{\vec x}_i}{h}||^2\right)}-\mathbf{\vec x}\right] $

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

   根据前面定义： $ MathJax-Element-454 $ ，则有： $ MathJax-Element-455 $ 。

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

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

7. Mean-Shift 算法优点：

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

8. Mean_Shift 算法缺点：

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