A 密度聚类

• 考察样本间基于密度的可连接性，并不断拓展聚类簇形成聚类结构。
• 代表算法：
  • Density-Based Spatial Clustering of Applications with Noise (DBSCAN)。
  • OPTICS
  • DENCLUE
• 优点：

  • 不要求簇在样本空间中的几何是凸的，可以处理如下图所示的数据。

    

A1 DBSCAN 方法

• 定义算法参数

  1. $\epsilon$ 邻域半径：考察的 ε-邻域的半径。
     • 邻域样本集 $N_{\epsilon} (\boldsymbol x) = \{ \boldsymbol u \in X \ | \ {\rm dist} (\boldsymbol x, \boldsymbol u) \le \epsilon \}$
       • 一般只考察样本的邻域，即 $\boldsymbol x \in X$。
  2. $M$ 核心阈值：任意样本的 ε-邻域中如果至少有 $M$ 个样本，称其为核心对象 (core object)。
     • 核心样本集 $S = \{ \boldsymbol x \in X \ | \ |N_\epsilon(\boldsymbol x)| \ge M \}$。

• 定义可连接性

  1. 密度直达：若 $\boldsymbol x \in S$，$\boldsymbol u \in N_\epsilon (\boldsymbol x)$，称 $\boldsymbol u$ 由 $\boldsymbol x$ 直达，记为 $\boldsymbol x \Rightarrow u$。自己一定直达自己。
  2. 密度可达：对于 $\boldsymbol x \in S$，$\boldsymbol u \in X$，如果存在样本序列 $\boldsymbol p_1, \boldsymbol p_2, \cdots , \boldsymbol p_P \in X$ 使得 $\boldsymbol x \Rightarrow \boldsymbol p_1 \Rightarrow \boldsymbol p_2 \Rightarrow \cdots \to\boldsymbol p_P \Rightarrow \boldsymbol u$，称 $\boldsymbol u$ 由 $\boldsymbol x$ 可达，记为 $\boldsymbol x \rightarrow \boldsymbol u$。直达一定可达。
  3. 密度相连：对于 $\boldsymbol x \in S$，$\boldsymbol u_1, \boldsymbol u_2 \in X$，如果 $\boldsymbol x \rightarrow \boldsymbol u_1$ 且 $\boldsymbol x \rightarrow \boldsymbol u_2$，称 $\boldsymbol u_1, \boldsymbol u_2$ 相连。

• 定义簇

  • 簇 $C \subseteq X$（$C \neq \emptyset$）满足如下性质：
    1. 连接性：若 $\boldsymbol u, \boldsymbol v \in C$，则 $\boldsymbol u, \boldsymbol v$ 相连；
    2. 最大性：若 $\boldsymbol x \in C$，$\forall \, \boldsymbol u (\boldsymbol x \to \boldsymbol u)$ 都有 $\boldsymbol u \in C$。
  • 簇的求法：

    • 对于一个核心样本 $\boldsymbol x \in S$ 而言，其可达的所有样本组成的集合记为 $X(\boldsymbol x) = \{ \boldsymbol u \in X \ | \ \boldsymbol x \to \boldsymbol u \}$，可以证明 $X(\boldsymbol x)$ 是满足连接性与最大性的簇。

    • 所以每次随机选择核心样本 $\boldsymbol x$ 求解其可达集合 $X(\boldsymbol x)$，并不再考虑已经入簇的核心样本，就可以划分出各个簇了。

    • 然而这样的话仍不够，仍可能有某些可达样本会被不同核心样本多次触及（如有 $\boldsymbol x_1 \to \boldsymbol u, \ \boldsymbol x_2 \to \boldsymbol u$，但没有 $\boldsymbol x_1 \to \boldsymbol x_2$ 或 $\boldsymbol x_2 \to \boldsymbol x_1$，如下图），所以还需要一个未访问节点集。

      

• 求解方法

  • 样本集复制一份为未访问节点集 $V$。
  • 求出核心样本集 $S$，复制一份为活动核心样本集 $T$。
  • 循环进行如下操作，直到 $T = \emptyset$。
    1. 随机选出一个核心样本 $\boldsymbol t \in T$。$V^{(new)} = V - \boldsymbol t$。
    2. 求出 $C = X(\boldsymbol t)\cap V$ 即求出一个簇。
    3. $T^{(new)} = T / C$，$V^{(new)} = V / C$。

B 层次聚类

• 试图形成一个树形结构。
• 方法：①自底向上；②自顶向下。
• 算法例子：
  • Agglomerative Nesting (AGNES) 是一种自底向上的层次聚类算法。
  • DIANA 采用自顶向下的分拆策略。
  • BIRCH、ROCK 等方法会回溯调整已经合并 / 分拆的聚类簇。

B1 AGNES 方法

• 十分直白的流程：

  • 初始：将每个样本看作一个初始聚类簇；
  • 迭代：每一次迭代找到距离「最近」的两个簇进行合并；
  • 结束：重复直到合并达到预设的簇数目。

• 树状图

  

  • 在树状图的特定层次上进行分割就可以得到一个划分结果。

• 优化：

  • 优化的要点是可以存储每对簇之间的距离，合并时只需求出新簇和其他簇之间的距离即可。

• 不同的距离类型（下面的二范数距离都可以换成别的距离）：

  • 最小距离：最近点之间的距离。被称为「单链接 (single-linkage)」算法。

    $$ d_{\rm min} = \min_{\boldsymbol x \in X} \min_{\boldsymbol y \in Y} {\rm dist} \| \boldsymbol x - \boldsymbol y \| _2 $$

  • 最大距离：最远点之间的距离。被称为「全链接 (complete-linkage)」算法。

    $$ d_{\rm max} = \max_{\boldsymbol x \in X} \max_{\boldsymbol y \in Y} {\rm dist} \| \boldsymbol x - \boldsymbol y \| _2 $$

  • 平均距离：每对点间的平均距离。被称为「均链接 (average-linkage)」算法。

    $$ d_{\rm avg} = \frac {1}{|X| |Y|} \sum_{\boldsymbol x \in X} \sum_{\boldsymbol y \in Y} {\rm dist} \| \boldsymbol x - \boldsymbol y \| _2 $$

  • 豪斯多夫 (Hausdorff) 距离：若要定义双向豪斯多夫距离 $d_{\rm H}$，先定义单向豪斯多夫距离 $d_{\rm h}$。

    $$ d_{\rm H} (X, Y) = \max (d_{\rm h} (X, Y), d_{\rm h} (Y, X)), \\

    d_{\rm h} (X, Y) = \max_{\boldsymbol x \in X} \min_{\boldsymbol y \in Y} \| \boldsymbol x - \boldsymbol y \| _2 $$

    • 单向豪斯多夫距离 $d_{\rm h}(X, Y)$ 定义了这样的最小距离，此集合 $X$ 任一点出发通过这段距离都能到达目标集合 $Y$。

    

C 其他聚类方法