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

2019 年 12 月 9 日 极市平台

加入极市专业CV交流群，与6000+来自腾讯，华为，百度，北大，清华，中科院等名企名校视觉开发者互动交流！更有机会与李开复老师等大牛群内互动！

同时提供每月大咖直播分享、真实项目需求对接、干货资讯汇总，行业技术交流。关注 极市平台 公众号，回复 加群，立刻申请入群~

来源：知乎专栏

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

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

论文： Efﬁcient 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。

上述三个步骤：

计算每个数据的最近邻
根据公式计算邻接矩阵
根据邻接矩阵得到有向图，从而完成一次聚类

可以将数据进行第一次聚类，上面的例子中，此聚类算法一次就聚类得到了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）很有优势。

-End-

*延伸阅读

CV细分方向交流群

添加极市小助手微信（ID : cv-mart），备注：研究方向-姓名-学校/公司-城市（如：目标检测-小极-北大-深圳），即可申请加入目标检测、目标跟踪、人脸、工业检测、医学影像、三维&SLAM、图像分割、OCR、姿态估计等极市技术交流群（已经添加小助手的好友直接私信），更有每月大咖直播分享、真实项目需求对接、干货资讯汇总，行业技术交流，一起来让思想之光照的更远吧~