聚类分析中的指标与马氏数据聚类方法

### 聚类分析中的指标与马氏数据聚类方法 在聚类分析中，选择合适的聚类数量以及比较不同的聚类划分是两个关键问题。下面将详细介绍相关的指标和方法。 #### 1. 选择具有最合适聚类数量的划分 在聚类分析中，我们常常需要确定一个数据集最合适的聚类数量。为了实现这一目标，有多种指标可供使用，下面将详细介绍这些指标及其应用。 ##### 1.1 CH和DB指标 CH（Calinski-Harabasz）和DB（Davies-Bouldin）指标是用于评估聚类质量的常用指标。以一个示例来说明，对集合A应用AGNES算法，从特定的划分开始，使用相似度度量和LS距离函数，可以得到不同划分下的CH和DB指标值，如下表所示： | Index | (2) | (3) | (4) | (5) | (6) | (7) | | --- | --- | --- | --- | --- | --- | --- | | CH | 17.76 | 33.65 | 30.34 | 26.97 | 21.78 | 18.31 | | DB | 0.50 | 0.42 | 0.36 | 0.38 | 0.25 | 0.18 | 从表中可以看出，CH指标表明 (3) 是具有最可接受聚类数量的划分，而DB指标则表明 (7) 是最合适的划分。这说明不同的指标可能会给出不同的结论。 ##### 1.2 轮廓宽度准则（SWC） SWC是聚类分析中非常流行的准则。对于一个通过距离函数d得到的k - LOPart ⋆ = {π⋆1, ..., π⋆k }，其计算步骤如下： 1. 对于每个 ai ∈ π⋆r，计算： - αir = 1/|π⋆r | ∑(b∈π⋆r) d(ai, b) - βir = min(q≠r) 1/|π⋆q| ∑(b∈π⋆q) d(ai, b) 2. 计算SWC(k) = 1/m ∑(i = 1 to m) (βir - αir) / max{αir, βir}，其中 1 < k < m。 更紧凑且分离度更好的聚类会得到更大的SWC值，具有最大SWC指标的划分被认为是最合适的划分。由于计算SWC指标的数值过程较为复杂，通常会使用简化的轮廓宽度准则（SSWC）。SSWC使用元素与聚类中心的距离来代替上述平均距离，计算公式为： SSWC(k) = 1/m ∑(i = 1 to m) (βir - αir) / max{αir, βir}，其中αir = d(ai, c⋆r)，βir = min(q≠r) d(ai, c⋆q)，同样 1 < k < m。具有最大SSWC指标的划分被视为最合适的划分。 ##### 1.3 邓恩指数（Dunn Index） 邓恩指数是由J. C. Dunn提出的，经过了多次改进和调整。对于一个通过距离函数d得到的最优k - 划分 ⋆ = {π⋆1, ..., π⋆k }，其计算步骤如下： 1. 计算每对聚类之间的分离度：D(π⋆i, π⋆j ) = min(a∈π⋆i, b∈π⋆j ) d(a, b) 2. 计算每个聚类的内部紧凑度，即直径：diam π⋆i = max(a, b∈π⋆i ) d(a, b) 3. 计算邓恩指数：Dunn(k) = min(1≤i<j≤k) D(π⋆i, π⋆j ) / max(1≤s≤k) diam π⋆s，其中 1 < k < m。 更内部紧凑且相互分离度更好的聚类划分会有更小的邓恩指数值，具有最小邓恩指数的划分被认为是最合适的划分。 以集合A为例，使用CH、DB、SSWC和邓恩指数来确定最可接受的聚类数量，结果如下表所示： | k | CH | DB | SSWC | Dunn | | --- | --- | --- | --- | --- | | 2 | 2202 | 0.62 | 0.84 | 0.027 | | 3 | 2357 | 0.67 | 0.82 | 0.037 | | 4 | 3447 | 0.63 | 0.87 | 0.027 | | 5 | 3751 | 0.65 | 0.88 | 0.017 | | 6 | 5554 | 0.60 | 0.90 | 0.016 | | 7 | 5263 | 0.80 | 0.86 | 0.015 | | 8 | 4824 | 0.93 | 0.81 | 0.014 | | 9 | 4562 | 1.06 | 0.78 | 0.008 | | 10 | 4430 | 1.14 | 0.76 | 0.013 | 从表中可以看出，CH、DB和SSWC指标正确地表明 ⋆6 是具有最可接受聚类数量的划分，而在这种情况下，邓恩指数错误地表明最可接受的划分是 ⋆9。需要注意的是，这些指标在数据符合其构建假设时才能给出可接受的结论，对于数据量相对较小的集合，结论可能不够可靠，而且基于这些指标得出的关于最可接受聚类数量的结论并不总是明确的。 #### 2. 比较两个划分 在实际应用中，我们常常需要比较两个不同的划分，例如比较通过某种方法得到的划分与原始划分。可以使用兰德（Rand）和杰卡德（Jaccard）指标，或者计算两个划分的聚类中心集合之间的豪斯多夫距离来实现这一目标。 ##### 2.1 兰德指数 兰德指数用于衡量两个划分的相似度。设 (1) = {π(1)1, ..., π(1)k } 和 (2) = {π(2)1, ..., π(2)ℓ} 是集合A的两个划分，定义如下： 1. 设 C = {(ai, aj) ∈ A × A : 1 ≤ i < j ≤ m}，如果 ai 和 aj 属于 (1) 中的同一个聚类，则称 (ai, aj) 在 (1) 中是成对的，类似地定义在 (2) 中“成对”的概念。 2. 定义 C 的四个子集： - C1：所有在 (1) 和 (2) 中都成对的对 (ai, aj) - C2：所有在 (1) 中成对但在 (2) 中不成对的对 (ai, aj) - C3：所有在 (1) 中不成对但在 (2) 中成对的对 (ai, aj) - C4：所有在 (1) 和 (2) 中都不成对的对 (ai, aj) 设