基于滴水原理的关联聚类算法

来源：计算机科学与探索杂志2018年第6期北京时间：

作者：华佳林，于剑

单位：1. 北京交通大学 计算机与信息技术学院，北京 1000442. 交通数据分析与挖掘北京市重点实验室，北京 100044

摘要：随着各种新兴媒体的发展，在数据挖掘领域出现了越来越多的新问题和新任务，关联聚类问题就是其中之一，最近受到越来越多的关注。现实中有很多问题可以使用关联聚类技术来处理，比如图像分割和垃圾邮件过滤等。大规模有符号图的出现越来越频繁，虽然之前有很多关联聚类算法被提出，但是很少算法能够处理规模很大的有符号图。提出了一个基于滴水原理的算法来处理大规模有符号图的聚类问题。算法过程包括：根据滴水原理来收缩图的规模，将一个水流上的所有点看成是一个新的点，这样可以极大地减小图的规模；在新的图中选出重要的点，并根据整数线性规划来判断邻居点是否合并。实验结果表明，该算法能够快速有效地进行大规模有符号图的聚类。

关键词：滴水原理,有符号图,关联聚类,整数线性规划