基于Wasserstein距离的最优输运聚类

0变分Wasserstein聚类0Liang Mi 1，Wen Zhang 1，Xianfeng Gu 2，Yalin Wang 101 亚利桑那州立大学，美国Tempe 2 Stony Brook大学，美国Stony Brook{liangmi,wzhan139,ylwang}@asu.edu gu@cs.stonybrook.edu0摘要。我们提出了一种基于最优输运的新的聚类方法。我们讨论了最优输运与k-means聚类的联系，用变分原理解决了最优输运问题，并研究了使用功率图作为运输计划将任意域聚合成固定数量的簇的方法。我们通过调整功率图来驱动目标域中的聚类质心，同时保持最小的聚类能量。因此，我们同时追求聚类和质心与目标域之间的Wasserstein距离，从而得到一种保度量映射。我们在合成数据和真实数据上展示了我们的方法在领域适应、重网格化和学习表示方面的应用。0关键词：聚类，离散分布，k-means，保度量，最优输运，Wasserstein距离01 引言0将分布数据聚合成簇在计算机视觉和机器学习中具有广泛的应用。一个连续的例子是无监督图像分类和检索，其中相似的图像在图像空间或描述符空间中靠近彼此，并且它们被聚类在一起形成一个特定的类别。一个离散的例子是文档或语音分析，其中具有相似含义的单词和句子经常被分组在一起。k-means是最著名的聚类算法之一，它旨在将经验观察分成k个簇，其中每个观察值与其所属簇的均值之间的距离最近。它最初是为了解决信号处理中的量化问题而开发的，在2000年代初，研究人员发现它与另一个经典问题最优输运的联系，最优输运寻求一种最小化概率测度之间的运输成本的运输计划。自从最优输运问题诞生以来，它就受到了极大的关注。许多应用，如颜色转换和形状检索，都受益于解决概率分布之间的最优输运。此外，通过将最小运输成本（Wasserstein距离）视为一种度量，研究人员能够计算多个分布的重心，例如[5,6]，用于各种应用。大多数研究人员将最优输运视为寻找两个概率之间的最优耦合，因此每个样本都可以被分配到多个位置。02 Liang Mi等人0映射到多个位置。它通常被称为坎托罗维奇的最优输运。除此之外，一些研究者将最优输运视为分布之间的保度量映射，因此样本不能被分割。这被称为蒙日-布雷尼尔的最优输运。在本文中，我们提出了一种基于蒙日-布雷尼尔方法的聚类方法。我们的方法基于Gu等人提供的蒙日-布雷尼尔最优输运问题的变分解。我们称之为变分最优输运，并将我们的方法命名为变分Wasserstein聚类。我们利用Wasserstein距离和聚类误差函数之间的联系，并通过使用功率Voronoi图同时追求Wasserstein距离和k-means聚类。给定目标概率分布的经验观察，我们从稀疏离散测度作为质心的初始条件开始，交替更新分区和更新质心，同时保持最优输运计划。从计算的角度来看，我们的方法解决了Wasserstein重心问题的特殊情况，当目标是一维测度时。这样的问题也被称为Wasserstein均值问题。我们展示了我们的方法在领域适应、重网格化和表示学习等三个不同任务上的应用。在合成数据的领域适应中，我们与Kantorovich的OT方法中的D2和JDOT取得了竞争性的结果。我们的方法相对于基于Kantorovich公式的方法的优势在于：（1）它是一个局部微分同胚；（2）它不需要预先计算成对距离；（3）它避免在乘积空间中搜索，从而大大减少了参数的数量。本文的其余部分组织如下。在第2和第3节中，我们提供了相关工作和最优输运以及k-means聚类的基础知识。在第4节中，我们提出了解决最优输运的变分原理。在第5节中，我们介绍了在变分Wasserstein距离下的k-means聚类问题的公式化。在第6节中，我们展示了我们的方法在不同任务上的实验和结果。最后，在第7节中，我们总结了我们的工作并展望了未来的方向。02 相关工作02.1 最优输运0最优输运（OT）问题最初由蒙日[11]在18世纪提出，旨在寻找一种最小成本的运输方案来匹配分布数据。1941年，康托罗维奇[12]引入了一种放松版本并证明了其存在性和唯一性。康托罗维奇还提供了一种基于线性规划的优化方法，这已成为主导方向。传统的解决康托罗维奇OT问题的方法依赖于预定义的测量点之间的成本，例如[13]，而最近的研究人员则开发了快速近似方法，将计算成本纳入其框架中，例如[6]。0变分Wasserstein聚类30与此同时，另一条研究线路遵循蒙日的OT，并在1987年取得突破，当时Brenier[14]发现了最优输运与凸几何之间的内在联系。根据Brenier的理论，M´erigot[15]，Gu等人[9]和L´evy[16]开发了他们的解决方案来解决蒙日的OT问题。M´erigot和L´evy的OT公式是非凸的，他们利用阻尼牛顿和拟牛顿分别解决它们。Gu等人提出了OT的凸公式，特别适用于凸域，其中纯牛顿方法有效，然后提供了一种变分方法来解决它。02.2 Wasserstein距离0Wasserstein距离是最优输运计划引起的最小成本。它满足所有度量公理，因此常常被用于测量概率分布之间的相似性。运输成本通常来自两个样本点之间的测地线距离及其测度的乘积。我们称之为p-Wasserstein距离，以指定计算测地线时的指数p[17]。1-Wasserstein距离或地球移动距离（EMD）在图像和形状比较中受到广泛关注[18,19]。随着深度学习在众多领域的兴起，1-Wasserstein距离已被采用多种方式设计损失函数，因为它优于其他度量方法[20,21,22,23]。2-Wasserstein距离虽然需要更多计算，但由于其几何特性（如重心），在图像和几何处理中也很受欢迎[4,6]。在本文中，我们专注于2-Wasserstein距离。02.3 K-means聚类0K-means聚类方法可以追溯到Lloyd[1]和Forgy[2]。它与1、2-Wasserstein度量的联系分别在[8]和[24]中得到利用。其基本思想是使用稀疏离散点集来对较密集或连续的分布数据进行聚类，与原始数据和稀疏表示之间的Wasserstein距离等效，这相当于找到单个分布的Wasserstein重心[5]。其他一些工作也通过提出快速优化方法来解决这个问题，例如[7]。在本文中，我们从变分原理的角度来解决k-means问题。因为我们利用功率Voronoi图来计算最优输运，所以我们同时追求Wasserstein距离和k-means聚类。我们通过实证实验将我们的方法与其他方法进行比较，并展示其在计算机视觉和机器学习研究的不同领域中的应用。03 准备工作0我们首先介绍最优输运（OT）问题，然后展示它与k-means聚类的联系。我们用X和Y表示两个Borel概率测度，M表示它们的紧致嵌入空间。04 梁米等人03.1 最优输运0假设P（M）是M上所有Borel概率测度的空间。不失一般性，假设X（x，µ）和Y（y，ν）是两个这样的测度，即X，Y∈P（M）。那么，我们有1 = �0Mν(y)dy，其中支撑集ΩX = {x} = {m ∈ M | µ(m) > 0}和ΩY = {y} = {m ∈ M | ν(m)> 0}。如果任意子集B的测度等于B在X中的原像的测度，即µ(T^(-1)(B)) = ν(B)，�B �Y，则将映射T:X(x, µ) → Y(y, ν)称为保测度映射。我们可以将T视为两个测度的耦合π(x,y)，每个测度都是相应的边缘µ = π(∙, y)，ν = π(x,∙)。然后，所有的耦合都是乘积空间中的概率测度，π ∈ �(M ×M)。给定一个运输成本c:M × M → R+，通常是到幂次p的测地线距离，c(x, y) = d(x,y)^p，最优输运问题是找到使总成本最小化的映射πopt:x → y，0Wp(µ, ν) def = � inf π ∈ �(µ,ν)0M × M c(x, y)dπ(x, y) � 1 /p，(1)0其中p表示幂次。我们称最小总成本为p-Wasserstein距离。由于我们处理的是无法分割质量的Monge的OT问题，我们有约束条件dπ(x, y) = dπT(x, y) ≡ dµ(x)δ[y =T(x)]，推断出0πTopt = Topt = arg min T0M c(x, T(x))dµ(x). (2)0在本文中，我们遵循公式（2）。最优输运问题的细节以及Wasserstein距离的性质可以在[25,23]中找到。为简单起见，我们用π表示最优输运映射。03.2 K-means聚类0给定概率分布X(x, µ)的经验观测{(xi,µi)}，k-means聚类问题旨在以使得误差函数（3）达到最小值的方式将聚类质心（或原型）yj = y(xi)，标记为j = 1, ...,0yj = y(xi)µi。它等价于在嵌入空间M中找到一个分割V = {(Vj,yj)}。如果M是凸的，那么Vj也是凸的。0arg min y0xi µi d(xi, y(xi)) p ≡ arg min V0K �0j = 10xi ∈ Vj µi d(xi, y(Vj)) p. (3)0当ν固定时，这样的聚类问题（3）等价于当y的支撑是稀疏且不固定时的Monge的OT问题（2），因为π和V相互诱导，即π � V。因此，方程（3）的解来自于搜索空间P(π,y)中的优化。注意，当ν不固定时，这样的问题变成了Wasserstein重心问题，即在P(π,y, ν)中寻找最小值，这在[4,5,7]中进行了研究。������̸0变分Wasserstein聚类50�  �0��0（a）（b）0�0�0图1.（a）功率Voronoi图。红点是Voronoi单元或聚类的质心。功率距离根据单元的权重有一个偏移。（b）计算Hessian矩阵的相邻单元的交叉点在2D和3D中的交集。04变分最优输运0我们提出了解决最优输运问题的变分原理。给定度量空间M，Borel概率测度X(x,µ)及其紧支撑Ω = supp µ = {x ∈ M | µ(x) > 0}，我们考虑具有Dirac测度Y(y, ν) = {(yj,νj > 0)}的稀疏支撑点集，j = 1, ..., k。（严格来说，经验测度X(x,µ)也是一组Dirac测度，但在本文中我们将X称为经验测度，将Y称为Dirac测度以便清楚。）我们的目标是找到一个最优输运计划或映射（OT-map），π：x →y，使得推前测度π#µ = ν。这就是半离散OT。我们引入一个向量h = (h1, ...,hk)T，一个在M上的超平面，γj(h)：�m, yj� + hj = 0，并引入一个分段线性函数：0θh（x）=max{�x，yj�+hj}，j=1，...，k。0定理1.（Alexandrov[26]）假设Ω是Rn中具有非空内部的紧凸多面体，y1，...，yk�Rn是k个不同的点，ν1，...，νk>0，使得�kj=1νj=vol（Ω）。存在唯一的向量h=(h1，...，hk)T∈Rk0除了一个平移因子（c，...，c）T，使得分段线性凸函数θh（x）=max{�x，yj�+hj}满足vol（x∈Ω|�θh（x）=yj）=νj。0此外，Brenier0Ω∥x−θh（x）∥2。因此，给定X和Y，h本身就引起了OT。根据[27]，我们知道与分段线性凸函数uh（x）相关联的凸细分等于功率沃罗诺伊图或功率图。M�Rn上的典型功率图可以表示为：0Vjdef={m∈M∥m−yj∥2−rj2�∥m−yi∥2−ri2}，�j≠i。0然后，我们可以进行简单的计算得到0m∙yj−102（yj∙yj+rj2）�m∙yi−102（yi∙yi+ri2），̸22(4)̸̸̸̸(6)06 Liang Mi et al.0算法1：变分最优输运0函数（X（x，µ），Y（y，v），�）0h←0。重复0用（y，h）更新功率图V。计算单元权重w（h）={�0m∈Vjµ（m）}。0计算梯度�E（h）和Hessian矩阵H，使用方程（5）和（6）。h←h−λH−1�E（h）。//根据（7）更新最小化器h，直到|�E（h）|<�。返回V，h。结束0其中m∙yj=�m，yj�，wj表示功率距离的偏移，如图1（a）所示。另一方面，超平面πj（h）的图形是0Ui def={m∈M|�m，yj�−hj��m，yi�−hi}，�j≠i。02。我们用测度X（x）代替M（m）。在我们的公式中，Brenier的梯度映射�θh：Vj（h）→yj“运输”每个Vj（h）到特定点yj。Vj（h）的总质量表示为：wj（h）=�0x∈Vj（h）µ（x）。现在，我们引入一个能量函数0E（h）def=�0Ωθh（x）µ（x）dx−0j=1νihj0≡ � hk �0j=1wj（ξ）dξ−0j=1νihj。0E对h可微分[9]。其梯度和Hessian矩阵分别为0�E（h）=(w1（h）−ν1，...，wk（h）−νk)T，（5）0H = ∂0∂hi∂hj=0� � � �  � 0� � �0�0l0∥yl−yi∥，i=j，�l，s.t.fil≠�，0−0∥yj−yi∥，i≠j，fij≠�，00，i≠j，fij=�，0fijµ（x）dx=vol（fij）是相邻两个单元之间交集fij的体积。图1（b）说明了几何形状̸0变分Wasserstein聚类70算法2：迭代保度量映射0函数 迭代保度量映射（X（x，µ），Y（y，ν））0x∈Vjµixi��0重复0直到y收敛。返回y,V。结束0V(h) ← Variational-OT(x, µ, y, ν)。// 1.更新Voronoi分区yj ← �0Hδh = �E(h)，(7)0x∈Vjµi。// 2. 更新y05 变分Wasserstein聚类0关系。Hessian H是正半定的，其零空间中仅有常数函数由向量(1, ...,1)T张成。因此，E在h中是严格凸的。通过牛顿法，我们解一个线性系统，0f(h, y) =0和更新h(t+1) ← h(t) + δh(t)。能量E(4)受Theorem1的启发，该定理寻求解决vol(x∈Ω|�θh(x) = yj) =νj的方案。将右侧移至左侧并对h进行积分，然后它变为E(4)。因此，当梯度趋近于0时，最小化(4)给出了解。我们在Alg. 1中展示了获得OT-Mapπ：X→Y的完整算法。0j =10算法3：变分Wasserstein聚类Since the first step preserves the measure and the second step updates the mea-sure, we call such a mapping an iterative measure-preserving mapping. Our al-gorithm repeatedly updates the partition of the space by variational-OT andcomputes the new centroids until convergence, as shown in Alg. 2. Furthermore,because each step reduces the total cost (8), we have the following propositions.0K08 梁密等。0y(t+1)j ← �µix(t)i0输入：经验测量X M(x, µ)和Y N(y, ν) 输出：保持测度的映射π：X→Y，表示为(y,V)。开始0对于每个Vj，都是一个功率Voronoi单元。通过迭代更新h和y，可以实现方程(8)的解。虽然我们可以使用Alg. 1来计算h，但更新y可以遵循以下规则：0命题1. Alg. 2单调地最小化目标函数(8)。0证明。我们只需要证明对于任意t ≥ 0，我们有0f(h(t+1), y(t+1)) ≤ f(h(t), y(t)). (10)0根据我们的OT公式的凸性，f(h(t+1), y(t)) ≤ f(h(t),y(t))，根据更新过程本身最小化均方误差的特性，f(h(t+1), y(t+1)) ≤ f(h(t+1),y(t))，因此上述不等式是成立的。0推论1. 算法2在有限次迭代中收敛。0证明。我们借用了k-means的证明。给定N个经验样本和一个固定的k，有kN种聚类方式。在每次迭代中，算法2仅基于前一个聚类规则产生一个新的聚类规则。如果新规则与前一个规则不同，则新规则引起更低的成本；如果新规则与前一个规则相同，则成本保持不变。由于定义域是一个有限集，迭代必定最终进入一个循环，其长度不会大于1，否则就违反了成本单调下降的事实。因此，循环的长度为1，此时算法2在有限次迭代中收敛。0推论2. 算法2对方程（8）产生唯一的（局部）解。0证明。初始条件y的质心位置是确定的。算法2的每一步都产生一个唯一的结果，无论是通过变分OT更新h还是通过加权平均更新y。因此，算法2产生一个唯一的结果。455055606570561712575151237VWCPCAYy,ν =argminY ∈P (M)π∈P (M×M)k�j=1�yj=π(xi)µi∥xi − yj∥2, s.t. νj =�yj=π(xi)µi.(11)infY ∈P (M)π∈P (M×M)k�j=1�yj=π(xi)µi∥xi − yj∥2 =infY ∈P (M)W 22 (X, Y ).(12)̸0变分Wasserstein聚类0图2.给定源域（红点）和目标域（灰点），源样本的分布被驱动到目标域并形成一个功率Voronoi图。0AD和NC的分类准确率0图3.VWC和PCA在AD和NC上的分类准确率与质心数量的关系。0现在，我们介绍变分Wasserstein聚类的概念。对于一个子集M �R^n，令P(M)为所有Borel概率测度的空间。假设X(x, µ) ∈P(M)是一个已有的测度，我们要将其聚合成k个由另一个测度Y(y, ν) ∈ P(M)和分配y_j= π(x)表示的聚类。因此，我们有π ∈ P(M ×M)。在固定ν的情况下，我们的目标是找到这样的Y和π的组合，使得目标函数最小化：0根据[5]中的讨论，方程（11）对y不是凸的。因此，我们通过迭代更新π和y来解决它。当更新π时，由于y是固定的，方程（11）变成了一个最优输运问题。因此，解方程（11）等价于逼近X和Y之间的2-Wasserstein距离的下确界：0假设域是凸的，我们可以应用迭代保测映射（算法2）来获得y和h，从而引起π。如果X和Y不在同一个域中，即Y(y, ν) ∈ P(N)，N � R^n，N ≠M，或者域不一定是凸的，我们利用谐映射[28,29]将它们映射到一个凸的规范空间。我们在算法3中总结了我们的完整算法。图2展示了一个聚类结果。给定一个源高斯混合（红点）和一个目标高斯混合（灰点），我们用源样本对目标域进行聚类。每个样本在每个域中具有相同的质量，以简化问题。因此，我们得到了一个无权重的Voronoi图。在下一节中，我们将展示涉及不同质量的示例。我们使用C/C++实现了我们的算法，并采用Voro++[30]来计算Voronoi图。代码可在https://github.com/icemiliang/vot上获得。10Liang Mi et al.0(a)0(e)0(b) (c)0(f) (g)0(d)0(h)0图4. 领域自适应的SVM RBF边界。 (a) 目标域中的灰色点和两个类别的源域中的红色和蓝色点; (b)通过使用VWC对质心进行映射; (c,d) VWC的线性和RBF核的边界; (e) k-means ++[32]无法产生模型; (f) 在重新调整源域和目标域之后，k-means ++ 产生可接受的边界; (g) D2 [7];(h) JDOT [10]，最终质心不可用。06 应用0尽管k-means聚类问题在计算机视觉和机器学习的许多任务中普遍存在，但我们提出了在领域自适应、重网格和表示学习中使用我们方法的方法。06.1 在合成数据上的领域自适应0领域自适应在知识传递中起着基础性的作用，并且已经在场景理解和图像风格转换等许多不同领域中受益。一些工作通过转换分布以关闭其与某个度量之间的差距来处理领域自适应。近年来，Courty等人[31]首次将最优输运应用于领域自适应。在这里，我们重新审视了这个想法，并根据变分Wasserstein聚类提供了我们自己的解决方案，用于无监督的多对一领域自适应。考虑一个二维欧几里德空间中的两类分类问题。源域由红色和蓝色点示出，如图4(a)所示，每个类别有30个样本。目标域有另外两个具有不同均值和方差的独立高斯分布，每个分布有1500个样本。它们由更密集的灰色点表示，以模拟未知变换后的源域。我们采用具有线性和径向基函数（RBF）核的支持向量机（SVM）进行分类。RBF的核尺度为5。可以注意到，直接将从源域学习到的RBF分类器应用于目标域会得到较差的分类结果（59.80%）。图4(b)显示了通过VWC从源域得到的样本的最终位置，(c)和(d)分别显示了线性核和RBF核的SVM的决策边界。在(e)和(f)中，我们展示了经典的k-means ++方法[32]的结果。在(e)中，k-means++无法将未标记的样本聚类到原始源域中，并产生了一个极其偏倚的模型，准确率为50%。只有在我们重新调整源域和目标域后，k-means ++才能产生更好的结果，如(f)所示。为了进行更多比较，我们测试了另外两种方法-D2 [7]和JDOT[10]。从D2得到的最终源位置如(g)所示。因为D2解决了一般的重心问题，并且还更新了源样本的权重，所以它在能够找到一些位置时就会收敛，这些位置的权重也能满足最小聚类损失。因此，在(g)中，大多数源样本都进入了右侧更密集的区域，而那些向左移动的样本则具有较大的权重。我们在(h)中展示了从JDOT[10]获得的决策边界。JDOT不会更新质心，因此我们只显示其决策边界。在这个实验中，我们的MongeOT方法和KantorovichOT方法[10,7]都能够在不同领域之间有效地传递知识，而传统方法[32]只能在两个领域之间具有先验知识的情况下工作，例如线性偏移。详细的性能报告在表1中。Triangle meshes is a dominant approximation of surfaces. Refining triangle meshesto best represent surfaces have been studied for decades, including [33,34,35].Given limited storage, we prefer to use denser and smaller triangles to representthe areas with relatively complicated geometry and sparser and larger trianglesfor flat regions. We follow this direction and propose to use our method to solvethis problem. The idea is to drive the vertices toward high-curvature regions.We consider a surface S2 approximated by a triangle mesh TS2(v). To drivethe vertices to high-curvature positions, our general idea is to reduce the areasof the triangles in there and increase them in those locations of low curvature,producing a new triangulation T ′S2(v) on the surface. To avoid computing thegeodesic on the surface, we first map the surface to a unit disk φ : S2 → D2 ⊂ R20变分Wasserstein聚类110三角网格是表面的主要近似方法。几十年来，已经研究了将三角网格细化以最好地表示表面的方法，包括[33,34,35]。在有限的存储空间下，我们更喜欢使用更密集和较小的三角形来表示相对复杂几何的区域，而使用稀疏和较大的三角形来表示平坦区域。我们遵循这个方向，并提出使用我们的方法来解决这个问题。我们的一般思路是将顶点驱动到高曲率区域。我们考虑一个由三角网格TS2(v)近似的表面S2。为了将顶点驱动到高曲率位置，我们的想法是在那些位置上减小三角形的面积，在低曲率位置上增加三角形的面积，从而在表面上产生一个新的三角剖分TS2(v)。为了避免在表面上计算测地线，我们首先将表面映射到一个单位圆φ:S2→D2�R206.2 变形三角网格0表1. 合成数据领域适应的分类准确率0k-means++ [32] � k-means++ r D2 [7] JDOT [10] VWC0Kernel Linear/RBF Linear RBF Linear RBF Linear RBF Linear RBF0Acc. 50.00 97.88 99.12 95.85 99.25 99.03 99.23 98.56 99.310Sen. 100.00 98.13 98.93 99.80 99.07 98.13 99.60 98.00 99.070Spe. 0.00 97.53 99.27 91.73 99.40 99.93 98.87 99.07 99.530�：极度偏见的模型，将所有样本标记为同一类；r：重新居中后。012 Liang Mi et al.0(e)0(a)0(h)0(b) (c) (d)03D曲率02D面积 3D曲率0增强的2D面积0原始网格0变形网格0(g) (f)0图5.基于曲率的三角剖分重分布。原始网格(a)被映射到单位圆盘(b)上。3D网格上的平均曲率(c)被复制到圆盘(f)上。通过将曲率C纳入2D顶点区域A的“增强”度量µ(e)，例如µ = 0.4A +0.6C。具有较大曲率C的顶点y为了保持其原始度量A，将收缩自己的聚类。结果是顶点在高曲率区域(g)中坍塌。通过逆映射，网格将被拉回到3D(h)。0并为其配备欧几里得度量。为简单起见，我们省略了上标2。为了明确符号，我们使用TS ( v )表示表面S上的原始三角剖分；T D ( v )表示其在D上的对应物；T ′ D ( v)表示D上的目标三角剖分；T ′ S ( v)表示S上的目标三角剖分。图5(a)和(b)说明了谐波映射前后的三角剖分。我们的目标是重新排列D上的三角剖分，然后以下组合给出了表面上的所需三角剖分：0T S ( v ) φ −−→  T D ( v ) π −−→  T ′ D ( v ) φ − 1−−−−→  T ′ S ( v ) .0π是我们应用方法的地方。假设我们有一个原始三角剖分T sub, S ( v)和一个初始下采样版本T S ( v )，我们将它们分别映射到T sub, D ( v )和T D ( v)。顶点区域A D ：v →a在D上是源（Dirac）度量。我们计算（绝对值的平方根）平均曲率C sub, S ：v sub→ c sub在S上，以及区域A sub, D ：v sub → asub在D上。在归一化a和c之后，加权求和给出了目标度量，µ sub, D = (1 - λ) a sub,D + λ c sub, D。我们从源度量(v, a)开始，通过使用我们提出的方法对目标度量(v sub,µ sub)进行聚类。直觉是：如果λ = 0，则µ i,sub = ai,sub处处，那么简单的非加权Voronoi图（它是T D ( v)的对偶）将满足等式(12)。随着λ的增加，高曲率(c sub, D)位置上的聚类V j (v j, aj)将需要更小的区域(a sub, D)来满足a j = �0v i,sub ∈ V j µ i,sub .0变分Wasserstein聚类130(a) (b) (c) (d)0图6.脑图像被投影到由脑表面生成的四面体网格(a)上。通过谐波映射，网格被变形为单位球(b)。球内的稀疏均匀分布(c)被初始化，并显示为初始Voronoi图。我们从(c)作为初始质心开始，并使用我们提出的方法将(b)作为经验度量进行聚类。 (d)显示了结果质心和图。0我们将我们的方法应用于人脸验证，并在图5中展示结果。在左半部分，我们展示了重网前后的比较。由于高曲率，鼻尖有更多的三角形，而额头由于相对较平而变得稀疏。图5的右半部分显示了我们计算用于移动顶点的不同度量。(c)显示了3D表面上的平均曲率。我们将具有曲率的三角剖分映射到平面圆盘空间上(f)。(d)说明了平面三角剖分的顶点区域，(e)是3D曲率和2D面积的加权组合。最后，我们将区域(d)视为源域，将“增强”区域(e)视为目标域，并应用我们的方法来获得圆盘空间上顶点的新排列(g)。然后，我们将其拉回到3D表面(h)。结果，顶点被吸引到高曲率区域。请注意，变形网格(g,h)的边界在聚类后发生了变化。如果需要，我们可以限制边界顶点在单位圆上移动。在此之后，从新顶点重建Delaunay三角剖分也是一个可选步骤。06.3 学习大脑图像的表示0大脑图像中包含的数百万个体素给计算机辅助诊断带来了效率问题。良好的学习技术可以提取原始数据的更好表示，从而降低维度和/或增强进一步处理的重要信息。在本节中，我们从Wasserstein聚类的角度来处理大脑图像的学习表示，并在磁共振成像（MRI）上验证我们的算法。在高层次上，给定一个大脑图像X（x，µ），其中x表示体素，µ表示它们的强度，我们的目标是使用已知的稀疏分布Y（y，ν）对其进行聚类。我们认为每个大脑图像是3D欧几里得空间中的子流形，M �R3。为了准备数据，对于每个图像，我们首先去除头骨并使用Freesurfer[36]提取脑体积的表面，然后使用Tetgen[37]从表面创建四面体网格。然后，我们将其投影到单位球中的离散均匀分布Y（y，ν）上，如图所示。014 Liang Mi等人0通过找到最近邻居并进行谐波映射，将图像变形为单位球，如图6（a）和（b）所示。现在，按照算法3，我们在单位球中设置一个离散均匀分布，如图6（c）所示。从这个分布开始，我们学习一个新的y，使得表示映射π：x→y的成本最小（12）。因此，我们可以将这个过程看作是从输入到潜在空间P（y）的非参数映射，其中k是聚类的数量，n指定原始嵌入空间的维数，例如脑图像的维数为3。图6（d）显示了得到的质心和相应的功率图。我们将我们的方法与主成分分析（PCA）进行比较，以展示其在降维方面的能力。我们将这两种方法应用于100个MRI图像，其中50个标记为阿尔茨海默病（AD），50个标记为正常对照（NC）。在获得低维特征后，我们直接在它们上应用线性SVM分类器进行5折交叉验证。图3中的图表显示了我们方法的优越性。众所周知，患有AD的人会出现脑萎缩，导致图像的群体偏移[38]。结果显示了VWC在将脑图像嵌入到低维空间中的潜力。我们还可以通过手工设计初始质心来进一步将ROI等先验知识纳入VWC中。07 讨论0由于其在许多领域中的稳健性和可扩展性，最优输运近年来越来越受到关注。在本文中，我们讨论了最优输运与k均值聚类的关系。基于变分最优输运，我们提出了一种通过求解迭代保度量映射的聚类技术，并展示了其在领域自适应、重网格和学习表示方面的应用。我们方法目前的一个限制是计算高维Voronoi图。这需要复杂的几何处理，导致效率和内存问题。解决这个问题的一个方法是使用梯度下降法进行变分最优输运，因为我们只需要图中相邻凸包的交点来计算Hessian矩阵。从图中获得的每个经验观测的分配可以通过最近搜索算法来确定。这超出了本文的范围，但可能会导致更多的实际应用。我们的重网格方法可以扩展到紧凑的2维流形上的一般特征重分布问题。未来的工作还可以在质心更新过程中添加正则化，以扩展其在计算机视觉和机器学习中的适用性。我们对Wasserstein均值的推广到重心的公式值得进一步研究。0致谢该研究部分得到了美国国立卫生研究院（R21AG043760，RF1AG051710和R01EB025032）和美国国家科学基金会（DMS-1413417和IIS-1421165）的支持。0变分Wasserstein聚类150参考文献01. Lloyd, S .: PCM中的最小二乘量化。IEEE信息理论交易28（2）（1982）129-137 2. Forgy,E.W .:多元数据的聚类：分类的效率与可解释性。生物统计学21（1965）768-769 3. Graf,S.，Luschgy, H .:概率分布的量化基础。Springer（2007）4. Agueh, M.，Carlier, G .:Wasserstein空间中的重心。SIAM数学分析杂志43（2）（2011）904-924 5. Cuturi,M.，Doucet, A .:快速计算Wasserstein重心。在：国际机器学习会议上。 （2014）685-693 6.Solomon, J.，De Goes, F.，Peyr´e, G.，Cuturi, M.，Butscher, A.，Nguyen, A.，Du,T.，Guibas, L.:卷积Wasserstein距离：几何域上的高效最优输运。ACM图形学交易（TOG）34（4）（2015）66 7. Ye, J.，Wu, P.，Wang, J.Z.，Li, J.:使用稀疏支持的Wasserstein重心进行快速离散分布聚类。IEEE信号处理杂志65（9）（2017）2317-2332 8. Ho, N.，Nguyen, X.，Yurochkin, M.，Bui, H.H.，Huynh, V.，Phung, D.:通过Wasserstein均值进行多级聚类。arXiv预印本arXiv：1706.03883（2017）9. Gu, X.，Luo,F.，Sun, J.，Yau, S.T.:Minkowski类型问题，离散最优输运和离散Monge-Ampere方程的变分原理。arXiv预印本arXiv：1302.5472（2013）10. Courty, N.，Flamary, R.，Habrard, A.，Rakotomamonjy, A.:域自适应的联合分布最优输运。在：神经信息处理系统的进展。 （2017）3733-3742 11.Monge, G .:关于填方和挖方理论的论文。巴黎皇家科学院历史（1781）12. Kantorovich, L.V.:关于质量迁移的论文。在：Dokl. Akad. Nauk SSSR。卷37。 （1942）199-201 13. Cuturi, M .:Sinkhorn距离：最优输运的高速计算。在：神经信息处理系统的进展。 （2013）2292-2300 14.Brenier, Y .:极化因子化和矢量值函数的单调重排。纯粹和应用数学通信44（4）（1991）375-41715. M´erigot, Q .:一种多尺度的最优输运方法。在：计算机图形学论坛。卷30.，Wiley OnlineLibrary（2011）1583-1592 16. L´evy, B.:三维L2半离散最优输运的数值算法。ESAIM：数学建模和数值分析49（6）（2015）1693-171517. Givens, C.R.，Shortt,R.M.，等。：一类概率分布的Wasserstein度量。密歇根数学杂志31（2）（1984）231-240 18.Rubner, Y.，Tomasi, C.，Guibas, L.J.:作为图像检索度