快速发现任意形状的聚类

摘要

提出FFCAS(Fast Finding the Clusters of Arbitrary Shape)聚类算法, 用于快速发现任意形状的聚类.先将每个对象分配到很小的ε-邻域,即原子聚类,然后找出高浓度的核心原子聚类,再消除所有的冗余原子聚类,仅用边界来表示聚类,大大减小了存储空间.因为ε是一个很小的值,原子聚类能自然地描述聚类.该算法最坏时间复杂度为O(n log n)(n为数据库中的对象个数),只需访问一次数据库.实验表明,FFCAS运行时间与数据库中的对象数目成线性关系,能发现任意形状的聚类,对异类的敏感性低,对大型、高维数据库也有效.