利用不相交集实现等价元素的聚类

说到聚类,相信大家最先想到的应该是k-means,但是我们知道k-means必须指定聚类的个数,而且聚类初始点的选取也很大影响最后聚类的效果。虽然有一些方法(如k-means++)可以设置较为合理的初始聚类点,但仍然需要指定聚类的个数,但有时我们并不知道一堆数据中有多少个类,这样就使得聚类变得没法下手。这里介绍一种利用一种树型数据结构——不相交集,实现的数据聚类方法。

不相交集(disjoint-set),也叫并査集(union-find)是保持一组不相交的动态集合。给定一系列数据,我们首先假设每个元素是一个集合,通过集合的查找合并实现等价元素的合并,从而实现相同类别的元素的聚类。这里两个元素等价的标准是由自己设定,取决于具体应用。例如目标检测中滑窗检测目标时用于聚合方框,其等价标准就是方框的重叠率的大小;再比如图像处理中联通区域标记的应用,其等价标准就是两个点是否联通。

Read More