Shape Analysis课程笔记19-Clustering and Segmentation
这个系列是MIT 6.838: Shape Analysis的同步课程笔记。本课程会介绍几何方法在图形学、机器学习、计算机视觉、医疗图像以及建筑设计等相关领域的原理和应用。本节主要介绍聚类和分割问题。
Clustering and Segmentation
聚类(clustering)是机器学习中的经典问题，而在CV和几何处理中聚类问题也可以理解为是分割(segmentation)。
本节课中我们会关注几何视角下的聚类问题，同时也会基于几何的视角来对它进行处理。
Applications
除了无监督学习外，聚类在CAD、医学成像以及CG中都有着广泛的应用。
然而在处理聚类问题时的难点在于如何去定义一个好的分割。很多时候这个定义是非常模糊的，因此我们一般会结合实际的任务需求来进行考虑。
Semantic Segmentation
语义分割(semantic segmentation)是CV中的经典问题。在语义分割中我们希望能够对图片上每个像素的类别进行标记，从而得到有意义的分割。
尽管在今天语义分割已经有很多很成熟的处理方法，本节课我们会介绍一些基于几何的算法。
k-Means
k-means是最基本的聚类算法。从几何的角度来看，k-means等价于寻找数据集上的k个聚类中心使得每个数据点\(\mathbf{x}\)到最近中心的距离之和最小。可以证明所需的聚类中心恰好为该类数据点的几何中心。
k-means算法的难点在于如何去初始化这些聚类中心。而当聚类中心确定后我们只需要把每个样本标记到最近的中心，然后更新聚类中心的坐标即可。从几何的角度来看，这一过程等价于构造Voronoi图(Voronoi diagram)，即k-means算法可以理解为使用Voronoi图对空间进行划分。
k-Means++
k-means算法的一个缺陷在于它高度依赖于初始化聚类中心的选择。k-means++算法中使用样本到最近中心的距离平方作为概率密度函数，然后通过抽样来初始化聚类中心。
k-means++的基础上很多现代方法提出了更好的初始化和抽样策略。
The Gap Statistic
k-means算法的另一个难点在于如何选取距离中心的数量k。除了根据实际需求进行设置外也可以利用gap statistic这样的技术来自动计算。
k-Means Applications
尽管k-means算法非常简单，但在工程中有着非常广泛的应用。比如说基于k-means进行颜色聚类或是对网格进行分割。
当然k-means算法的随机性也往往会对聚类结果产生扰动，很难说这是算法的bug还是它的特性。
Semidiscrete Transport
从最优运输的角度来考虑，k-means还可以理解成半离散运输。实际上通过设计不同的权重，我们可以推导出不同的k-means算法。
如此定义最优运输问题后，就可以使用一些标准的解法进行处理。
Geometry of k-Means
到目前位置我们都假定了k-means算法的样本都分布在欧式空间中，而当样本不满足这样的假定时k-means的效果就会非常差。因此我们需要对k-means进行推广，使得它能够处理更一般的问题。
对于如何定义样本的均值的问题，这里可以使用Fréchet mean来对欧式空间中的均值进行推广。可以证明在欧式空间中Fréchet mean与我们通常意义下的均值是相同的。
而在更一般的度量空间中，Fréchet mean会具有一些几何上的意义。
Fréchet mean甚至对如何训练神经网络也有一定的启发。
除此之外，Fréchet mean在很多需要计算均值的算法中都有一定的应用。
k-Medioids
如果我们把更新聚类中心的步骤修改为的中心点就可以得到k-Medioids算法，不过此时就无法使用Fréchet mean了。
对于形状聚类这样的任务，k-Medioids算法是非常有意义的。
这里我们引入Gromov-Hausdorff距离(Gromov-Hausdorff distance)的概念，它可以描述两个度量空间的距离。利用Gromov-Hausdorff距离就可以比较不同形状的差异，不过需要注意的是Gromov-Hausdorff距离本身是非常难以计算的。
Techniques for Clustering
除了k-means之外，其它常用的聚类算法还包括agglomerative clustering、flood fill等。
Clustering in Feature Space
前面介绍过的算法都是直接对数据进行聚类，而实际上我们还可以在特征空间上来进行处理。
Optimality
到目前为止我们在介绍各种算法时都没有涉及「最优」的问题。我们当然希望算法能够取得全局最优，不过这很可能是做不到的。
Spectral Clustering
谱聚类(spectral clustering)是一种基于局部信息的聚类方法，它可以实现一定程度上的全局最优。
Normalized Cuts
接下来我们介绍normalized cuts算法，它的目标是最小化分割代价同时尽可能地保证分割后两部分的大小是相同的。
通过一系列复杂的数学推导可以证明normalized cuts等价于求解一个广义特征值问题。因此尽管normalized cuts的推导比较复杂，但在实现时却很容易。
标准normalized cuts算法只能处理把数据分成两团的情况，对于更多的聚类中心则需要结合其它的算法。
Graph Partition
在介绍Laplace算子的性质时我们提到过Fiedler向量(Fiedler vector)，它是Laplace算子第二小的特征值所对应的特征向量同时描述了图的连通性和聚类性质。
把类似的技术推广到曲面上则可以对曲面进行分割和聚类。
Additional Issues
目前绝大多数的分割算法都存在不一致的问题。当不同的曲面之间存在关联时，分割算法往往无法识别出这些关联而会得到不同的分割结果。
这表明分割可能不仅仅是一个纯粹的几何问题，我们还需要考虑到人的认知过程以及实际的需求。
Supervised Learning
因此目前学术界的热点是借助机器学习尤其是监督学习的方式来处理分割问题，相关的技术我们会在后面进行更加详细的介绍。
