闵可夫斯基加权K-Means初始化方法研究

### 闵可夫斯基加权 K-Means 初始化方法研究 在数据聚类领域，准确地将实体分组到同质的簇中是一项具有挑战性的任务。K-Means 算法是最知名的聚类算法之一，它通过迭代最小化实体与簇质心之间的距离来实现聚类。然而，K-Means 算法在处理包含噪声特征的数据集时表现不佳，因为它对所有特征一视同仁。为了解决这个问题，研究者们提出了加权 K-Means（WK-Means）和闵可夫斯基加权 K-Means（MWK-Means）算法。 #### 1. K-Means 与 MWK-Means 算法概述 K-Means 算法的目标是将数据集划分为 K 个不重叠的簇，使每个实体 $y_i$ 被分配到一个簇 $S_k$ 中，通过迭代最小化以下准则： \[W(S, C) = \sum_{k=1}^{K} \sum_{i \in S_k} d(y_i, c_k)\] 其中，$d(y_i, c_k)$ 是实体 $y_i$ 与其所属簇 $S_k$ 的质心 $c_k$ 之间的距离。K-Means 算法允许使用任何距离函数，本文主要关注闵可夫斯基度量，其在 V 维实体 $y_i$ 和 $c_k$ 之间的定义为： \[d_p(y_i, c_k) = (\sum_{v=1}^{V} |y_{iv} - c_{kv}|^p)^{\frac{1}{p}}\] 当 $p = 1$ 和 $p = 2$ 时，闵可夫斯基度量分别等价于曼哈顿度量和欧几里得度量。 由于 K-Means 算法对所有特征同等对待，在处理包含噪声特征的数据集时准确性较低。为了解决这个问题，Huang 等人提出了加权 K-Means（WK-Means）算法，旨在为不太相关的特征分配较低的权重。在此基础上，研究者进一步改进，提出了闵可夫斯基加权 K-Means（MWK-Means）算法，该算法迭代最小化以下准则： \[W_p(S, C, w) = \sum_{k=1}^{K} \sum_{i \in S_k} \sum_{v=1}^{V} w_{kv}^p |y_{iv} - c_{kv}|^p\] 其中，$w_{kv}$ 是特征 $v$ 在簇 $k$ 中的权重，$p$ 是用户定义的参数，可以通过半监督学习方法找到。 MWK-Means 算法继承了 K-Means 算法的一些弱点，例如其准确性在很大程度上取决于初始质心的选择，K 值需要事先确定，并且不能保证准则函数达到全局最小值。本文主要关注初始质心选择对 MWK-Means 算法准确性的影响。 #### 2. MWK-Means 算法中的闵可夫斯基度量 MWK-Means 算法通过两种方式扩展了 Huang 等人的工作：一是将特征权重转换为特征缩放因子，二是引入闵可夫斯基度量。为了考虑特征权重，调整了闵可夫斯基距离度量，计算实体 $y_i$ 和质心 $c_k$ 之间的距离： \[d_p(y_i, c_k) = \sum_{v=1}^{V} w_{kv}^p |y_{iv} - c_{kv}|^p\] 从上述公式推导出新的准则函数（2），并满足 $\sum_{v=1}^{V} w_v = 1$ 且无部分隶属关系。特征权重 $w_{kv}$ 的计算如下： \[w_{kv} = \frac{1}{\sum_{u \in V} [D_{kv} / D_{ku}]^{\frac{1}{p - 1}}}\] 其中，$D_{kv} = \sum_{i \in S_k} |y_{iv} - c_{kv}|^p$ 是簇特定的。 MWK-Means 算法的迭代步骤如下： 1. 获取初始的 K 个质心和每个质心的 V 个权重（或设置 $v_{ik} = \frac{1}{V}$）。 2. 使用最小距离规则和公式（3）将所有实体分配到最近的质心。 3. 将所有质心更新为其所属簇的闵可夫斯基中心。如果质心不再移动，则停止。 4. 使用公式（4）更新特征权重，然后返回步骤 2。 闵可夫斯基中心可以通过最速下降算法找到。 #### 3. 初始质心选择算法 由于 MWK-Means 算法的输出随 $p$ 值变化，因此在选择初始质心的算法时受到一定限制。本文对六种不需要准则函数输出即可找到质心的初始化方法进行了实验，除随机初始化外，其他五种方法均应用了闵可夫斯基度量。 以下是六种初始化方法的介绍： - **随机初始化**：在实验中，将 MWK-Means 算法运行 100 次，每次随机从数据集中选取初始质心。由于簇区域的密度可能较高，随机选取的初始质心更有可能来自实际的簇。 - **Hartigan 算法**：该算法旨在避免在实体初始分配到质心后形成空簇。具体步骤如下： 1. 相对于数据集的重心对所有 N 个实体进行排序。 2. 对于每个簇 $k = \{1, 2, ..., K\}$，将其质心设置为第 $1 + (k - 1) * [N / K]$ 个实体。 - **Ward 算法**：层次聚类算法与 K-Means 算法不同，它生成的是簇的层次结构，而不是单一的标签集。Ward 算法是一种层次聚合算法，用于找到 K-Means 算法的初始质心，具体步骤如下： 1. 将每个实体视为一个单独的簇。 2. 计算所有簇之间的 Ward 距离，并合并距离最近的两个簇 $S_{w1}$ 和 $S_{w2}$。 3. 用新创建的簇 $S_{w1 \cup w2}$ 替换合并的两个簇的引用。 4. 如果 $K > K^*$（$K^*$ 是期望的簇数量），则返回步骤 2。 - **Build 算法**：Partition Around Medoids（PAM）算法使用数据集中的实体作为中心点（medoids），而不是合成的质心。Build 算法通常用于 PAM 算法的初始化，具体步骤如下： 1. 选择最接近数据集重心的实体 $c_1$，并将其放入集合 $C$ 中。 2. 选择距离 $c_1$ 最远的实