Press "Enter" to skip to content

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

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

来源:知乎专栏

 

链接: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。

 

上述三个步骤:

 

 

计算每个数据的最近邻

 

根据公式计算邻接矩阵

 

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

 

 

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

Be First to Comment

发表评论

邮箱地址不会被公开。 必填项已用*标注