1. 引言

在数据挖掘、机器学习和模式识别等领域，分类技术扮演着核心角色。分类技术的核心目标在于构建一个能够根据数据集的特征将未知样本准确划分到预定义类别中的分类函数或模型，通常这个模型也被称作分类器。分类方法主要包括有监督分类、无监督分类、半监督分类。有监督分类是最常见的分类方法之一，它依赖于带有标签的训练数据来构建模型。在这种方法中，算法通过学习输入特征和输出标签之间的关系，以便能够对新的数据进行准确的预测。无监督分类是一种在没有预先标签或分类信息的情况下，将数据集中的样本划分为若干个组或类别的分类方法。半监督分类介于有监督和无监督分类之间，它使用一部分标注数据和大量未标注数据来训练模型，这种方法适用于标注数据难以获得或成本高昂的情况。

常见的分类算法有K-近邻、决策树、支持向量机(SVM)等。K-近邻算法是一种基于实例的学习算法，其核心思想是对于一个新的输入实例，算法会在训练数据集中寻找与其最近的K个实例，然后根据这些最近邻的类别或输出值来预测新实例的类别或输出值。K-近邻算法简单直观，易于理解和实现，但其性能很大程度上依赖于K值的选择、距离度量和分类决策规则[1] [2]。决策树是一种监督学习算法，通过在特征空间中构建树状结构来进行决策。它通过递归地选择最优特征进行分割，构建出能够映射数据特征到决策结果的树模型。决策树简单直观，易于理解和解释，适用于分类和回归任务[3] [4]。然而，决策树容易过拟合，尤其是在面对复杂数据时，可能需要剪枝等技术来控制模型复杂度。支持向量机是一种强大的分类算法，可用于线性和非线性数据的分类。SVM的核心思想是在特征空间中寻找一个最优的超平面，这个超平面能够最大化地分开不同类别的数据点，即最大化两类数据点之间的间隔。SVM通过引入核技巧，能够处理非线性可分的数据。它在高维空间中表现良好，适用于复杂的分类问题[5] [6]。

在实际应用中，为了降低不确定性并提高测量结果的可靠性，常常会采用多次测量或重复实验的方法[7]。例如在水质评价领域，由于季节性波动和区域差异，如降雨量变化导致污染物浓度波动或突发性污染事件，水质数据往往带有一定的不确定性[8]。为了减少这种不确定性，通常会进行多次重复测量[9]，从而获得多个特征向量来描述单个样本，进而产生了基于集合的分类学习任务。目前，处理这类基于集合的分类问题主要有两种方法：一种是通过计算原始数据的统计量[10] [11]，如均值、中位数等，将集合转换为向量形式以进行分析，这种方法在多种算法中得到了应用[12]-[14]。但集合被转换为向量时会丢失大量的原始信息，进而产生误差，影响分类结果。另一种方法是直接开发基于集合的分类器。例如，Arandjelovic等[15]将每个集合建模为参数分布，并引入K-L散度来计算分布间的相似性。这种方法要求对参数分布进行估计，但在实际应用中，由于样本量通常不足以获得准确的估计，在很多场景并不适用。

为了克服现有算法处理集值型数据时存在的不足，本文将Wasserstein距离引入K-means聚类算法，以实现对集值型数据的分类。Wasserstein距离源自最优传输问题[16]，作为一种衡量概率分布之间差异的方法，能够准确地捕捉集值型数据之间的关系，实现分类。同时，Wasserstein距离对极端指标不敏感，不会因为个别极端值而影响分类结果，具有较好的鲁棒性。此外，Wasserstein距离的计算本质上是一个优化问题，这使得它可以通过优化算法进行高效求解。

本文的创新点如下：

(1) 不同于传统的分类方法只适宜处理向量值数据，本文提出的基于Wasserstein距离的K-means聚类算法能够直接对集值型数据进行聚类处理，不需要计算原始数据的统计量，避免了原始信息的遗漏。

(2) 得益于熵正则项的特殊结构，利用Sinkhorn-Knopp算法有效提升了算法的效率。

(3) 在UCI数据集及邯郸市滏阳河水质数据中验证了算法处理集值型数据的有效性。

本文结构如下：第二章为预备知识，介绍了聚类分析、最优传输理论和Sinkhorn-Knopp算法的相关理论。第三章设计了Wk-means算法，并给出了算法的实现过程和流程图。第四章为实验部分，分别在UCI数据集和滏阳河水质数据集上进行了实验和对比。第五章为结论与展望，总结了全文并对未来进行展望。

2. 预备知识

2.1. 聚类分析

聚类分析(Cluster Analysis)是一种重要的无监督学习方法，其核心目标是将数据集中的样本划分为若干组(簇)，使得同一簇内的样本具有较高的相似度，而不同簇间的样本相似度较低。在数据挖掘、模式识别等领域得到广泛应用。

K-means算法是最经典的聚类算法之一，该算法于1967年提出，以简单直观、易于实现的特点在实际应用中占据重要地位[17]。K-means算法的核心思想是最小化每个点到其聚类中心的距离之和。基本步骤包括：

(1) 初始化：随机选择K个样本点作为初始聚类中心。

(2) 分配：将每个样本分配到距离最近的聚类中心所对应的簇。

(3) 更新：重新计算每个簇的中心点(各维特征的均值)。

(4) 迭代：重复步骤(2)和(3)，直至达到终止条件。

K-means算法原理简单，时间复杂度较低，适合处理大规模数据，且算法可解释性强，但仍存在如对异常点敏感，可能陷入局部最优等不足。

2.2. 最优传输理论

最优传输(Optimal Transport，简称OT)理论最初由法国数学家Gaspard Monge于1781年正式提出[18]。Monge问题的核心在于，在给定代价函数的情况下，寻找两个概率分布之间的最优传输映射，如图1所示。这一问题可以直观地理解为：如何以最经济的方式将一堆沙子从一个分布形态转移到另一个分布形态，即填补一个坑洞。Monge问题的数学表述是寻找一个映射T，使得传输成本最小化，同时满足质量守恒的条件，具体定义如下所示：

$\underset{T}{\min }\left\{{\displaystyle \underset{i}{\sum }c\left(x_i,T\left(x_i\right)\right):T_{\#}\alpha =\beta }\right\}$ (1)

其中 $c$ 为代价函数， $\alpha$ 和 $\beta$ 为两个概率测度， $\#$ 为push forward算子。

Figure 1. The optimal mapping between the two distributions

图1. 两个分布之间的最优映射

苏联数学家Leonid Kantorovich在1942年提出了Monge问题的松弛形式[19]，即Kantorovich问题，并将其应用于经济问题的研究。Kantorovich对Monge问题的主要改进在于，他将寻找最优传输映射的问题转变为寻找最优传输计划的问题。

不同于Monge问题中质量只能被移动不能被分割，Kantorovich问题允许质量的分割和重组，即允许从一点到多点的质量传输。离散形式的Kantorovich问题可以描述为如下形式的线性优化问题：

$L_C\left(a,b\right)=\underset{P\in U\left(a,b\right)}{\min }\langle C,P\rangle =\underset{P\in U\left(a,b\right)}{\min }{\displaystyle \underset{i,j}{\sum }{C}_{i,j}{P}_{i,j}}$ (2)

其中 $U\left(a,b\right)=\left\{P\in R_{+}^{n\times m}:P{1}_m=a,P^{\text{T}}{1}_n=b\right\}$ ，a和b为两个离散概率分布，C为代价矩阵，常表示为 $C_{i,j}={\Vert x_i-y_j\Vert }^2$ 。

Kantorovich问题的数学表述是：给定两个概率测度a和b，以及一个代价函数C，寻找一个联合概率测度P，使得该联合分布的边际分布分别为a和b，并且传输成本最小化。

Kantorovich问题的提出，不仅在理论上推进了最优传输理论的发展，而且在实际应用中也展现出了广泛的适用性[20]-[22]。重要的是，它使得最优传输问题的求解变得更加可行，尤其是在处理离散概率测度时，Kantorovich问题可以转化为线性规划问题，从而可利用现有的算法进行有效求解。

Wasserstein距离是最优传输理论中的一个重要概念，它定义了概率测度空间上的一个度量，并在数学、统计学、物理学和机器学习等多个领域中得到了应用[23]-[25]。对于两个概率分布a和b，Wasserstein距离 $W\left(a,b\right)$ 是将一个分布转换为另一个分布所需的最小成本。数学上，两个离散概率测度a和b的p阶Wasserstein距离由下式给出：

$W_p\left(a,b\right)=L{\left(a,b\right)}^{\frac{1}{p}}=\underset{P\in U\left(a,b\right)}{\min }{\left({\displaystyle \underset{i,j}{\sum }{C}_{i,j}{P}_{i,j}}\right)}^{\frac{1}{p}}$ (3)

这里 $C_{i,j}={\Vert x_i-y_j\Vert }^p$ 为代价矩阵，P为指派矩阵。

2.3. Sinkhorn-Knopp算法

Sinkhorn-Knopp算法是一种用于求解最优传输问题的迭代算法，它通过在目标函数中加入熵正则化项，将复杂的线性规划问题转化为在平滑可行域上的求解过程[26]-[28]。该算法的核心思想是在代价函数上加入熵正则化项，从而将问题转化为一个更易于求解的形式，即求解如下熵正则最优传输问题：

$W_{Entropy}\left(a,b\right)=\underset{P\in U\left(a,b\right)}{\min }\langle C,P\rangle +\epsilon H\left(P\right)$ (4)

其中 $H\left(P\right)={\displaystyle \underset{i}{\sum }{P}_i\log P_i}$ 。

Sinkhorn-Knopp算法的数学表述是：给定两个概率向量a和b，目标是找到一个矩阵P，使得P的行和等于向量a，P的列和等于向量b。算法的迭代步骤包括：

行归一化：对矩阵P的每一行进行缩放，使得行和接近目标向量a；

列归一化：对矩阵P的每一列进行缩放，使得列和接近目标向量b。

这个过程不断重复，逐步调整矩阵P的元素，使其行和和列和分别逼近a和b。Sinkhorn-Knopp算法的收敛性基于迭代过程的单调性、均匀缩放的性质和正则化项的引入，确保了算法在合理的迭代次数内收敛到一个满足约束条件的非负矩阵。

3. 基于Wasserstein距离的无监督聚类方法Wk-Means

本文提出了一种基于Wasserstein距离的K-means聚类算法(Wk-means)，该算法在传统K-means的框架下引入Wasserstein度量，有效提升了算法处理概率分布数据的能力。算法1展示了主要计算过程，给定集值型数据集 $X\in {ℝ}^{N\times M\times d}$ ，参数 $\epsilon$ 和最大迭代次数Maxiter，其中N表示样本个数，每个样本都是一个 $M\times d$ 维的矩阵。算法的核心目标是将这N个样本划分为K个类别，使得类内的Wasserstein距离之和最小。

接下来，为说明Wk-means算法的有效性，本文给出如下收敛性命题。

命题1 Wk-means算法收敛。

证明：给定如下损失函数

$J={\displaystyle \underset{k=1}{\overset{K}{\sum }}{\displaystyle \underset{i=1}{\overset{N}{\sum }}{W}^2\left(X_i,X_k^c\right)}}$ (5)

为证明Wk-means算法收敛，首先证明随算法迭代损失函数J的函数值呈下降趋势。

Wk-means算法主要分为两步：第一步，对每一个样本 $X_i$ ，根据其与类中心 $X_i^c$ 的Wasserstein距离 $W\left(X_i,X_k^c\right)$ 来分配 $X_i$ 的类别，第二步重新计算类中心 $X_i^c$ 并再次分配 $X_i$ 的类别。

第一步，计算每个样本与其类中心的Wasserstein距离，可得当前的损失函数值J。

第二步，对每个样本而言，若 $X_i$ 的类别不变，显然其与类中心 $X_i^c$ 的Wasserstein距离 $W\left(X_i,X_k^c\right)$ 不变；若 $X_i$ 类别改变，记新类别为 $X_k^{c*}$ ，由于类中心应为距离所有同类样本点最近的样本，此时显然有

$\begin{array}{c}{W}^2\left(X_1,X_k^c\right)\ge W^2\left(X_1,X_k^{c*}\right)\\ W^2\left(X_2,X_k^c\right)\ge W^2\left(X_2,X_k^{c*}\right)\\ \cdots \\ W^2\left(X_N,X_k^c\right)\ge W^2\left(X_N,X_k^{c*}\right)\end{array}$ (6)

此时新的损失函数

$\begin{array}{c}{J}^{*}={\displaystyle \underset{k=1}{\overset{K}{\sum }}{\displaystyle \underset{X_i\in R}{\sum }{W}^2\left(X_i,X_k^{c*}\right)}}\\ =W^2\left(X_1,X_k^{c*}\right)+W^2\left(X_2,X_k^{c*}\right)+\cdots +W^2\left(X_N,X_k^{c*}\right)\\ \le W^2\left(X_1,X_k^c\right)+W^2\left(X_2,X_k^c\right)+\cdots +W^2\left(X_N,X_k^c\right)\\ ={\displaystyle \underset{k=1}{\overset{K}{\sum }}{\displaystyle \underset{X_i\in R}{\sum }{W}^2\left(X_i,X_k^c\right)}}\\ =J\end{array}$ (7)

故损失函数J单调不增。此外，将N个样本分配到K个类别的划分方式有限( $K^N$ )，即J一定存在最小值。综上可知损失函数J单调不增且有下界，由单调有界定理可知损失函数J一定收敛，故Wk-means算法一定收敛，命题得证。

图2给出了Wk-means算法的具体流程，可以看出，Wk-means算法的核心思想在于利用计算的Wasserstein距离矩阵进行聚类，从而实现对集值型数据的分类。

结合流程图，Wk-means聚类算法主要包含以下4个步骤：

1) 在初始化阶段，首先输入集值型数据集X以及Sinkhorn-Knopp算法中的熵正则项参数 $\epsilon$ ，最大迭代次数Maxiter，类别个数K，并确定算法的初始化中心点选取策略：随机选取(random)、均匀选取(uniform)和均值选取(mean)。

2) 在迭代优化阶段，算法交替执行样本分配和中心点更新两个步骤：首先计算每个样本到各类中心的Wasserstein距离，将样本分配给距离最近的类；然后重新计算每个类的中心点，通过不断迭代，实现聚类。

3) 算法的收敛基于目标函数值的变化，具体终止于以下情况：目标函数值不再显著下降；达到预设最大迭代次数。

4) 空聚类处理策略。针对实际应用中可能出现的空聚类问题，提供两种处理方案：直接删除(drop)或创建单点聚类(singleton)。前者简单地忽略空聚类，这可能导致最终得到的类别少于预期类别个数。而后者则从现有聚类中选择最远的点作为新的聚类中心。在后续实验中，本文采取了单点聚类策略，以保证聚类完整性。

为提高算法的计算效率，本方法采用Sinkhorn-Knopp算法，通过引入熵正则项，将原本的最优传输问题转化为一个可以快速求解的近似问题，显著提高算法计算效率。与传统的基于欧氏距离的K-means相比，Wk-means通过考虑数据的概率分布特性，能够更好地捕获数据间的本质差别，对具有分布特征的数据具有更强的分类适应性，更重要的是，Wk-means能够直接对集值型数据进行聚类处理，而不必从原始数据中提取统计量再进行聚类分析。

Figure 2. Flowchart of the Wk-means algorithm

图2. Wk-means算法流程图

4. 实验

本节将在UCI数据集和河北省邯郸市滏阳河水质数据中验证算法的有效性，实验是在一台拥有英特尔酷睿i5-13500HX处理器，16GB内存的计算机上运行的，在MATLAB R2023b中进行仿真。算法中熵正则项参数 $\epsilon$ 见表1，最大迭代次数Maxiter为10,000，聚类个数K选取与数据集有关，在UCI数据集中，K的个数与实际相同，在滏阳河数据中K的个数为水质等级个数。

4.1. UCI数据集

为了对Wk-means算法进行检验，本文首先利用UCI数据集来生成新的集值型数据进行模型测试。具体生成方式为：向原始数据中的样本添加高斯噪声，使得每个样本生成10个包含高斯噪声的样本，从而形成一个集值样本。所有的样本汇总就得到了新的集值型数据集。以Yeast数据集为例，该数据集包含1484个样本，即可生成1484个数据 $A_i,i=1,2,\cdots ,1484$ ，每个数据 $A_i$ 为一个集值样本，汇总起来就能得到一个包含1484个数据 $A_i=\left\{x_{ik},k=1,2,\cdots ,10\right\},i=1,2,\cdots ,1484$ 的集值型数据集。数据集特征如表1所示，本文选取的数据集覆盖不同样本个数、特征个数及类别个数。

Table 1. UCI datasets and characteristics

表1. UCI数据集及特征

我们对比了Wk-means方法与其他方法的表现，包括用于处理不确定数据的二阶锥规划(SOCP)方法[29]、基于正则化外壳的图像集协同表示和分类(RHISCRC) [30]和用于集合分类的稀疏近似最近点(SANP) [31]，以及基于核特征选择的广义预测集方法(GPS) [32]，结果如表2~4所示。从表2中可以看出，Wk-means在多数的数据集上表现良好，尤其是在大样本数据集，如Yeast和Glass数据集上，Wk-means预测精度要显著优于其他四个方法。而在运行效率方面，Wk-means虽略低于SOCP方法，但与RHISCRC时间相近，且远优于SANP和GPS方法。表4则展示了5种方法预测的标准差，Wk-means在多数数据集上标准差更小，即预测更稳定，波动更小。

为了能够更直观地展示不同方法之间的差异，我们进行了十折交叉验证，将数据分为10份分别计算准确率，然后将得到的结果进行t检验：

$t=\frac{\left({\bar{x}}_1-{\bar{x}}_2\right)-\left({\mu }_1-{\mu }_2\right)}{\sqrt{\frac{s_1^2}{n_1}+\frac{s_2^2}{n_2}}}$ (8)

其中 ${\bar{x}}_1$ ， $s_1$ 分别为使用Wk-means方法计算的准确率的均值和标准差， ${\bar{x}}_2$ ， $s_2$ 为其他方法计算的准确率的均值和标准差， $n_1=n_2=10$ 。

Table 2. Comparison of the accuracy of different methods on UCI datasets

表2. 不同方法在UCI数据集上的准确率对比

Table 3. Comparison of running time of different methods on UCI datasets

表3. 不同方法在UCI数据集上的运行时间对比

Table 4. Comparison of standard deviations of different methods on UCI datasets

表4. 不同方法在UCI数据集上的标准差对比

Table 5. Comparison of different methods at 0.05 significance level

表5. 0.05显著性水平下的不同方法对比

表5展示了在显著性水平为0.05的情况下，不同方法间的对比结果。其中1表示有显著差异，0表示没有显著差异。可以看出，在数据集Glass、Iris和Yeast上，Wk-means不仅准确率远优于其他数据集，且与大多数方法均有显著性差异。而在部分小样本数据集如Wine上，Wk-means虽然准确性没有达到最好，但与其差距很小，仍具有一定竞争性。

4.2. 滏阳河水质数据

滏阳河，如图3所示，源出河北省邯郸市峰峰矿区滏山南麓，流经邯郸、邢台、衡水，最终在沧州地区的献县与滹沱河汇合，形成子牙河，汇入渤海。全长415公里，流域面积达2.8万平方公里。滏阳河不仅是邯郸市的主要水源，也是该地区农业灌溉的重要依托，对于维持当地生态平衡和促进农业发展具有重要意义。

滏阳河的水质状况直接关系到邯郸市及其下游地区的水资源安全。近年来，随着工业化和城市化的快速发展，对滏阳河水质进行分类研究，不仅有助于监测和评估水质状况，还能为水资源管理和污染控制提供科学依据。

Figure 3. Fuyang river basin map

图3. 滏阳河流域图

为对滏阳河水质进行分类，共设置84个采样点，且为了降低水质数据的不确定性，每个采样点测量10次，即得到84个数据 $A_i,i=1,2,\cdots ,84$ ，分别属于5个不同等级(I, II, III, IV, V)。每个数据 $A_i$ 由10个向量 $x_{i1},x_{i2},\cdots ,x_{i10}$ 组成，即 $A_i=\left\{x_{i1},x_{i2},\cdots ,x_{i10}\right\},i=1,2,\cdots ,84$ 。每个向量 $x_{ik},k=1,2,\cdots ,10$ ，包含11个特征：pH，DO，CODcr，NH-N，TN，N03，N02，PO4，D0，TP，CODmn。其中DO、NH-N、TN、N03、N02、PO4、TP和CODmn的测量单位均为“mg/L”，如表6所示，表中的数据已经过归一化处理。

Table 6. Some water quality data and characteristics

表6. 部分水质数据及特征

Table 7. Comparison of results of different methods on water quality data

表7. 不同方法在水质数据上的结果对比

与上一个实验相同，我们将所提的Wk-means方法与其他分类方法进行比较，表7展示了预测准确率和运行所需时间。从表7中可以看出，Wk-means方法在预测精度和运行效率均达到了最优，具体表现在以下两个个方面：分类准确率有明显的提升，Wk-means方法达到69%的准确率，比次优的SOCP方法高出3个百分点，相比RHISCRC、SANP和GPS方法，准确率提升更为显著，分别高出28、62、23个百分点；计算效率显著提升，Wk-means方法耗时1.94秒，相比SOCP方法(7.74秒)和GPS方法(8.73)分别节省了约75%和78%的计算时间，较RHISCRC、SANP和GPS方法分别节省了44%和56%的运行时间。

5. 结论与展望

本文提出了一种基于Wasserstein距离的无监督聚类方法，用于集值型数据的分类问题，克服了传统欧氏距离无法处理集值型数据的局限性。在公开数据集的交叉验证实验中，尤其在大样本数据集(如Yeast和Glass)上，Wk-means分类准确率显著优于SOCP、RHISCRC和SANP等传统的集值数据处理方法，与新型集值数据处理方法GPS相比也有明显的提升，统计显著性检验进一步验证了算法性能的可靠性和稳定性。在滏阳河水质数据集上的实验表明，Wk-means方法相比传统方法精度更高，运行时间更短。Wk-means算法展现出优异的分类准确率，同时兼顾了计算效率，为处理大样本、复杂的集值型数据提供了一种新的技术解决方案。

在未来研究中，我们考虑在算法优化方面进行进一步深入研究，并将该方法推广到其他类型的集值数据中，如空气质量分类、土壤污染评估等。

基金项目

河北省中央引导地方科技专项项目(246Z1825G)；河北省高等学校科学研究项目(QN2020188, ZD2020185)；河北省“三三三人才工程”资助项目(C20221026)。

NOTES

^*通讯作者。

参考文献