快速且不需要超参的无监督聚类方法

来源：知乎专栏

链接：https://zhuanlan.zhihu.com/p/69855313

本文已由作者授权转载，未经允许，不得二次转载

论文： Efficient Parameter-free Clustering Using First Neighbor Relations

链接： https://arxiv.org/abs/1902.11266

代码： https://github.com/ssarfraz/FINCH-Clustering

此文是CVPR2019的oral文章。 两个字评价： 快！ 好！

方法

本文提出了一种parameter-free，并且效果卓越，效率奇高的无监督聚类方法。 聚类的方法非常简单，简单到一个公式就可以说清聚类的方法：

其中  代表第 个点的最近邻点。   是 数据的邻接矩阵。

观察上述邻接的计算方式可以发现，只要在符合以下情况时，邻接矩阵中的值为1：

• ： 对于第i个点来说，我的最近邻就是第j个点。

• ： 对于第i个点来说，我是第j个点的最近邻。

• ： 第i个点的最近邻点和第j个点的最近邻点相同。

例子

以太阳为例，解释整个聚类的过程：

我们知道太阳系中各个行星的最近邻（与当前行星距离最近的行星）关系如下：

根据这些行星的最近邻情况，以及上述公式的计算方法可以得到邻接矩阵：

以第一行为例（i=1， 即Mercury），

• 条件1：    ，在第i个行星的最近邻的处标上1； Mercury的最近邻是Moon，其id为4，所以（1，4）为1。

• 条件2： ，谁的最近邻是我，那就在谁那儿标1，结果发现没有行星的最近邻是Mercury，所以不标1。

• 条件3：  ，谁的最近邻和我的最近邻一样（即谁的最近邻也是Moon），那就在谁那儿标1。 发现Mars的最近邻也是Moon，其id为5，所以在（1，5）处也标记为1。

根据上述的过程，最终得到的邻接矩阵是个对称矩阵。 并且，根据这个邻接矩阵可以得到如下一个有向图：

通过这个图可以明显看出，所有的行星被分为了三个cluster。

上述三个步骤：

1. 计算每个数据的最近邻

2. 根据公式计算邻接矩阵

3. 根据邻接矩阵得到有向图，从而完成一次聚类

可以将数据进行第一次聚类，上面的例子中，此聚类算法一次就聚类得到了3个cluster。

接下来可以对每个图结构重新进行特征计算，比如上面的三个cluster可以通过求均值的方式得到三个cluster center，这个三个center可以认为是三个样本数据，然后重复上述的三个步骤，就可以对这三个cluster进行进一步的聚类。 最终，所有的样本都会被聚成一个cluster。

在这一步步聚类的过程中，不同的step可以得到不同的聚类中心个数，我们只要选取适合我们的聚类中心个数，并把那一步的聚类结果拿出来就可以了。

总结

1、parameter-free： 本文是一种parameter-free的无监督聚类方法，同时也是一种层级聚类方法（ Hierarchical Clustering ）。 在聚类的过程中不需要指定cluster数量。 当然，作者也在文中给出了指定cluster数量的聚类方法，具体可以看论文中的描述。

假设一开始有共有10000个样本，那么一开始认为有10000个cluster，在经过第一个聚类后，变成了2000个cluster，再一次聚类后变成了400个cluster，直到最后变成了一个cluster。 而我们只需要根据聚类效果，选取某个cluster个数就可以了，比如聚类成400个cluster效果不错，那我们就把这一步的聚类结果拿出来就可以了。

作者给出了一些数据集中cluster个数和聚类step的关系图：

2、快速： 本文的方法不需要计算所有sample之间的距离，只需要找到每个sample的最近邻即可。 而寻找最近邻的方法有现成的快速的方法，比如（FLANN）等。 下图是一张聚类时间表，可以看出本文方法（FINCH）很有优势。