基于空间中位数的非参数聚类停止规则：在多变量数据中实现鲁棒性聚类数目确定

本文提出了一种基于空间中位数（Spatial Median）的非参数聚类停止规则算法（BWDM），通过最大化类间与类内变异比值并调整聚类数目（K）与观测数（n），有效平衡类内同质性与类间异质性。该算法具有强鲁棒性，对分布假设和异常值不敏感，在模拟与真实数据集（如Old Faithful、Financial和Iris数据）中验证了其稳定性与有效性，且在与其他13种传统聚类算法的比较中，BWDM在聚类数目确定方面优于其中11种。

　　

摘要

本研究引入了一种基于空间中位数的非参数聚类停止规则算法，旨在实现类内同质性与类间异质性之间的平衡。该方法通过最大化类间变异与类内变异的比率，并在计算过程中调整聚类数目和观测数量，从而有效识别最优聚类数目。算法对分布假设具有鲁棒性，且能够抵抗异常值的干扰。通过模拟数据验证了算法的有效性，并在三个真实数据集（Old Faithful、Financial和Iris）上评估了其稳定性与效能。此外，本研究还将所提出模型与13种传统聚类算法进行比较，发现在聚类数目确定方面，BWDM算法优于其中11种方法。结果表明，该算法为多变量数据聚类数目的确定提供了一种可靠的非参数替代方案。

亮点

• •

  提出基于空间中位数的非参数聚类停止规则算法；

• •

  考虑类内同质性和类间异质性的平衡；

• •

  最大化类间与类内变异比；

• •

  调整聚类数目和观测数的影响；

• •

  在聚类分析中优于13种传统算法中的11种。

1. 引言

确定数据集中聚类数目的问题在多个学科中均具有重要地位，例如商业、心理学、统计学、医学、计算机科学和工程学。聚类停止规则（亦称索引）的核心是计算不同聚类解的函数值，并选择能够表征最显著聚类划分的解。以往研究多基于参数统计方法，利用均值等经典参数度量进行类内与类间变异的衡量。而非参数度量，如空间中位数和空间秩，为多变量数据中聚类数目的确定提供了另一种思路。

在许多统计研究中，空间中位数因其计算简便性和对异常值的鲁棒性而受到特别关注。空间中位数具有50%的崩溃点，意味着在受到高达50%的异常值污染时仍能保持稳定。相比之下，传统基于质心的聚类索引中所使用的均值崩溃点为0%，对单个异常值也极为敏感。因此，使用空间中位数的BWDM方法能够产生对异常值和偏态分布具有鲁棒性的聚类评估结果。

2. 定义

2.1. 样本单变量中位数

设x₁,…,x_n是来自单变量分布F的样本，其顺序统计量为x₍₁₎≤x₍₂₎≤…≤x_(n)，则单变量中位数定义为该分布的二分之一分位数。也可通过单变量符号函数求解中位数值。

2.2. 空间中位数

设x₁,…,x_n∈R^d，其中d为变量数，n为观测数。通过将单变量中位数中的绝对值替换为欧几里得范数，可以定义样本空间中位数。

3. 方法

3.1. 类间与类内中位数距离比（BWDM）

假设x₁,…,x_n∈R^d是一个d维数据集，样本量为n。对于某个聚类解，设总聚类数为K，k_i表示第i个聚类的大小，SM_i表示第i个聚类的空间中位数。则类间中位数距离平均值（ABDM）定义为所有可能聚类对之间中位数距离的平均值。类内中位数距离平均值（AWDM）则定义为每个观测值与其所在聚类中位数距离的平均值。

基于ABDM和AWDM，提出BWDM指数作为调整后的比值：

BWDM(K) = [ABDM(K)/(K-1)] / [AWDM(K)/(n-K)]

通过选择使BWDM(K)最大化的K值来确定最优聚类数目。

3.2. BWDM算法

计算BWDM统计量的步骤如下：

1. 1.

   对每个聚类解，计算ABDM(K)；

2. 2.

   计算AWDM(K)；

3. 3.

   计算BWDM(K)比值；

4. 4.

   重复步骤1-3直至K=K_max；

5. 5.

   选择使BWDM(K)最大的K值作为最优聚类数。

3.3. 理论性质：最优性与收敛性

假设数据来自K个明显分离的聚类群体，每个群体具有有限二阶矩和唯一的空间中位数。随着样本量n→∞，BWDM(K)概率收敛于真实聚类数K。证明基于空间中位数的相合性、大数定律以及聚类算法的渐近正确分配假设。

4. 数值示例

4.1. 模拟数据示例

通过三个模拟场景评估算法性能：

• •

  模拟数据1：来自两个双变量正态分布的混合，权重为0.7和0.3；

• •

  模拟数据2：来自三个双变量正态分布的混合，权重为0.3、0.3和0.4；

• •

  模拟数据3：来自四个双变量正态分布的混合，权重各为0.25。

在所有情况下，BWDM均能正确识别真实聚类数。

4.2. 真实数据集示例

4.2.1. Old Faithful数据

包含喷发间隔时间和喷发持续时间两个变量，明显形成两个聚类。BWDM正确识别K=2。

4.2.2. Financial数据

包含三个变量的投资基金数据，形成两个聚类（股票型基金和平衡型基金）。BWDM成功识别K=2。

4.2.3. Iris数据

包含四个变量的鸢尾花数据，虽然包含三个品种，但Setosa与其他两个品种更容易分离。BWDM识别K=2与实际聚类情况一致。

5. 与其他聚类算法的比较

将BWDM与13种传统聚类算法在三个真实数据集上进行比较。结果表明，只有PAM和WSR两种算法与BWDM一样在三个数据集上均表现正确。其他算法如GMM、K-means、HDDC、DBSCAN、KMD、DDC、SNN和densityClust等只能在部分数据集上正确识别聚类数。

6. 结论

本研究提出的基于空间中位数的聚类停止规则算法，通过平衡类内同质性与类间异质性，为多变量数据聚类数目的确定提供了一种鲁棒的非参数方法。算法对异常值和分布假设不敏感，在模拟和真实数据集中均表现出色。与传统方法相比，BWDM在聚类数目确定方面具有明显优势。未来的研究方向包括扩展算法以适应更复杂的聚类结构（如重叠聚类）以及应用于功能数据等更复杂的数据类型。