非层次聚类的两种方法及相关理论

# 非层次聚类的两种方法及相关理论 ## 1. 有限集划分集的相关理论 在有限集的划分问题中，我们引入了一些重要的概念和定理。设 $V$ 和 $W$ 代表两个划分，其中 $V$ 在 $O_1$ 上与 $X$ 一致，在 $O_2$ 上与 $Y$ 一致；$W$ 在 $O_1$ 上与 $Y$ 一致，在 $O_2$ 上与 $X$ 一致。$V$ 和 $W$ 是 $X$ 和 $Y$ 之间的中间划分，因为满足 $X + Y = V + W$。 有如下定理：当 $X$ 和 $Y$ 是不可比的划分时，考虑 $X$ 和 $Y$ 在集合 $H$ 上的限制 $X|_H$ 和 $Y|_H$，这里 $H$ 是 $O$ 中与 $X$ 类和 $Y$ 类都相同的子集的并集 $G$ 关于 $O$ 的补集。那么 $X \land Y$ 成立的充要条件是 $(X|_H) \lor (Y|_H) = \{H\}$，即 $H$ 的单元素划分。 通常情况下，给定一个划分的相邻划分数量是非常多的。 ## 2. 非层次聚类方法概述 非层次聚类方法在数据处理中具有重要地位。这里将介绍两种截然不同的非层次聚类方法： - **“中心划分”方法**：由 S. Régnier 提出。 - **“动态聚类方法”**：由 E. Diday 及其合作者提出，它是 K - means 方法的广泛推广，K - means 方法由 Forgy 和 Jancey 开创。 这两种方法的一个重要共同点是，都用一个中心来概括位于具有距离函数空间中的有限集 $E$。对于中心划分方法，$E$ 是有限对象集上的一组划分；对于动态聚类方法，$E$ 是有限对象集的元素簇，或者更一般地，是对象集 $O$ 上的有限结构集。在本文的例子中，待聚类的集合 $O$ 由几何空间 $\mathbb{R}^p$ 中的点表示，其中 $\mathbb{R}$ 表示实数集，$p$ 是给定的正整数。 ## 3. 中心划分方法 ### 3.1 数据结构 为了描述对象集 $O$，我们建立了一组名义分类属性 $A = \{a_m|1 \leq m \leq p\}$。设 $C_m$ 是属性 $a_m$ 的值集，$1 \leq m \leq p$。用向量属性 $\mathbf{a} = (a_1, a_2, \ldots, a_m, \ldots, a_p)$ 来描述对象，映射关系为： $\mathbf{a} \to C = C_1 \times C_2 \times \cdots \times C_m \times \cdots \times C_p$ $x \mapsto \mathbf{a}(x) = (a_1(x), a_2(x), \ldots, a_m(x), \ldots, a_p(x))$ 其中 $x \in O$，$a_m(x)$ 是 $x$ 所具有的 $a_m$ 的类别，$1 \leq m \leq p$。集合 $C_m$ 是有限的，且没有特定结构。每个属性 $a_m$ 都会在对象集 $O$ 上诱导出一个划分 $P_m$，$1 \leq m \leq p$。如果 $K_m$ 是 $P_m$ 的类数，那么 $P_m$ 可以表示为： $P_m = \{O_m^1, O_m^2, \ldots, O_m^k, \ldots, O_m^{K_m}\}$ 其中 $O_m^k \subset O$ 由具有属性 $a_m$ 的第 $k$ 个值的对象组成，$1 \leq k \leq K_m$，$1 \leq m \leq p$。因此，数据由划分向量 $(P_1, P_2, \ldots, P_m, \ldots, P_p)$ 定义。 要与划分族 $P_m$（$1 \leq m \leq p$）进行比较的划分 $P$，将表示为具有 $p$ 个相同分量 $P$ 的划分向量：$(P, P, \ldots, P, \ldots, P)$。 ### 3.2 中心划分的概念 设 $P = (P_m|1 \leq m \leq p)$ 是对象集 $O$ 上的一组划分序列。中心划分的概念需要在所有划分的集合 $\mathcal{P}$ 上定义一个距离 $\delta$。中心划分 $\hat{P}$ 定义为： $\hat{P} = \text{Arg}\left\{\min_{P \in \mathcal{P}}\left[\frac{1}{p}\sum_{1 \leq m \leq p}\delta(P_m, P)\right]\right\}$ 这里的乘法因子 $\frac{1}{p}$ 可以省略，但为了体现均值的概念，我们保留它。 当 $P$ 和 $Q$ 是 $O$ 的两个划分时，S. Régnier 定义 $\delta(P, Q)$ 为 $O \times O$ 中与 $P$ 和 $Q$ 相关联的等价关系的图的对称差的基数。$P_m$ 相关联的等价关系的图为： $\text{gr}(P_m) = \{(x, y)|(x, y) \in \bigcup_{1 \leq k \leq K_m}O_m^k \times O_m^k\}$ 这样，需要最小化的准则变为： $\delta[(P_1, P_2, \ldots, P_m, \ldots, P_p), (P, P, \ldots, P, \ldots, P)] = \frac{1}{p}\sum_{1 \leq m \leq p}\text{card}(\text{gr}(P_m) \triangle \text{gr}(P))$ 其中 $\triangle$ 表示对称差。 我们可以在无序不同对象对的集合 $F = P_2(O)$ 层面考虑等价关系的图的表示，这种表示比在 $O \times O$ 中更简洁，且 $O \times O$ 的对角线上的元素不参与新的表示。此时，距离指标 $\delta(P, Q)$ 可以简化为 Rand 相似性指标，即 $\delta(P, Q) = n(1 - \text{Rand}(P, Q))$，其中 $n = \text{card}(O)$。 ### 3.3 分类（聚类）准则分析 将划分 $P$ 在 $O \times O$ 中的表示与一个指示函数 $\varpi$ 相关联： $\forall (x, y) \in O \times O$，$\varpi(x, y) = 1$ 当 $x$ 和 $y$ 在 $P$ 的同一类中；$\varpi(x, y) = 0$ 当 $x$ 和 $y$ 在 $P$ 的不同类中。 将集合 $O$ 用前 $n$ 个整数集合 $I = \{1, 2, \ldots, i, \ldots, n\}$ 编码，划分 $P$ 可以用立方体 $\{0, 1\}^