对数据进行聚类的方法、设备和系统

摘要

本发明公开了一种对数据进行聚类的方法、设备和系统。首先创建分级生成树，然后进行迭代图缩减和约束图切分；并且最后实现了分级式分割。通过分割的子图来获得聚类结果。本发明的计算成本低，处理速度快，聚类精度高，并且鲁棒性强。聚类的结果具有较好的统计特征。本发明可以用于各种数据分类系统。

主权项

一种对数据进行聚类的方法，包括步骤：针对输入的数据点创建分级式生成树；对创建的分级式生成树执行迭代式图缩减，以便缩减分级式生成树上的边缘点；对缩减后的分级式生成树执行受约束的图切分处理，以计算分级式生成树中每个边的切分值；以及选择具有最大切分值的边作为要切分的位置来将分级式生成树切分成子树来获得聚类结果；其中，所述针对输入的数据点创建分级式生成树的步骤包括：从包括多个数据点的列表中取一个数据点，并且计算它与列表中的其他数据点的距离；将彼此之间的距离小于第一距离阈值的所有数据点放在一个超球内；从列表中移除彼此之间的距离小于第二距离阈值的所有数据点，其中第一距离阈值大于第二距离阈值；针对所述超球，创建最小生成树；对于具有重叠数据点的任意两个超球，将最接近的数据点链接起来；在所有超球中，将超球看作数据点，删除一些边，从而使得将所有超球链接在一起的剩余边形成针对这些超球的最小生成树，作为所述分级式生成树；其中所述对创建的分级式生成树执行迭代式图缩减的步骤包括：重复如下过程来缩减分级式生成树：删除与分级式生成树的边缘点联系的边；将分级式生成树的所有的边缘点收缩到分级式生成树上；以及融合新的边缘点。