Meta
一篇CVPR14，作者在valse的演讲视频在专题侠客群论剑-20151223 。
我是看了视频之后再看论文的，只看论文的话貌似有点摸不着头脑。
作者在视频中隐晦地提到，选坑很重要，作者用Transitive Distance也是有贵人相助，看来机遇很重要，啊。
这篇文章基于二作的一篇07年的文章 Clustering with Transitive Distance and K-Means Duality,即transitive distance和k-means duality这个概念的运用。本文即可认为是这篇文章的拓展（其实看摘要蛮像的，这两篇文章有很高的重复率）。
我发现谱聚类的效果挺好的，此坑可入啊。
由这篇文章发现的两个可看的东西：
- On Spectral Clustering: Analysis and an algorithm
- 一篇博客：谱聚类算法概述
Abstract
首先，硬扯上spectral clustering，降低了复杂度。
目前对谱聚类不太了解，难道只要用上graph就算谱聚类？
算法特点：用上了一个_Transitive Distance_，还有其 k-means duality 特性。
Introduction
指导聚类算法design的一个根本原则
Consistency. Data within the same cluster are close to each other, while data in different clusters are relatively far away
层次聚类(the hierarchy approach)是bottom-up的，因此完全取决于local data structure，很容易出现multi-scale clusters的error。
k-means and EM 假设的数据分布太简单了（Euclidean / Mahananobis distances）因此无法hold 住data with manifold or irregularly shaped clusters
谱聚类很好啊，但eigendecompostion的复杂度太高 $O(n^3)$. 因此得解决scalability
problem。
本文的算法规避了eigendecomposition ，因此降到了$O(n^2)$
此算法的 philosophy 和 Kernel k-means: spectral clustering and normalized cuts（where spectral clustering is unified to the kernel k-means framework） 一样，但上面这篇文章还得解eigenproblem。
本文的贡献是三点： efficiency，straightforwardness，flexibility。
flexibility就是易扩展，efficiency就是运算复杂度低了。
straightforwardness不太好理解，就是规避了discrete-to-continuous relaxations这么一个步骤。
文章内容
transitive distance的概念古已有之
很明显，它定义在另外一个距离 $d(.,.)$ 之上，这个 $d(.,.)$ 可以是欧氏距离，也可以是卡方距离（6.4节的图像分割用的用到了）。
有人证明了transitive distance是一种ultrametric，然后本文搞出一个Theorem 1（证明在附录A）
这个定理的underlying intuition很简单，就是在影射后的新空间 $V’$ ，可以直接用Kmeans，即比原空间 $V$ 的聚类更容易。
即我们得到了一个具有良好特性的 kernel mapping。
但问题来了，正如通常的kernel trick，这个影射之后啊，咱只有点与点之间在新空间的距离（即距离矩阵），没有其绝对坐标啦，这还咋玩儿。
（啊，用kernel kmeans的套路不行么？）
作者用k-means duality特性来解决此问题。
即直接将距离矩阵的行进行距离即可（看视频是这么说的，论文的这一部分没有看懂啊）
第五节试算法描述部分要构造一个minimum spanning tree。
实验部分
好多奇形怪状的形状，还有 Iris and Ionosphere datasets。
在第六页的Figure 5中，本文的算法以及NJW algorithm都能hold住很复杂的形状，这些形状貌似能hold住Data clustering: 50 years beyond K-means的Fig.2？
先试一下NJW吧
对于Image segmentation，先搞superpixel（用G. Mori. Guiding Model Search Using Segmentation. ICCV, 2005.的方法），用 $\chi^2$ distance.
总结
尽管此文有理论支撑，但有了理论之后，其各种假设也就明显了起来。
在transitive distance的定义中， 是不允许类间重叠的，但在Figure 5中，貌似这个假设也没事啊？