基于随机kNN图的批量边删除聚类算法

来源：软件学报杂志2018年第12期北京时间：

作者：雷小锋,陈皎,毛善君,谢昆青

单位：雷小锋，中国矿业大学 计算机科学与技术学院, 江苏 徐州 22111611,陈皎，中国矿业大学 计算机科学与技术学院, 江苏 徐州 22111602,毛善君，北京大学 遥感与地理信息系统研究所, 北京 10087103,谢昆青，北京大学 信息科学技术学院 智能科学系, 北京 10087104

摘要：建立邻接图上的批量边删除聚类算法通用框架，提出基于高斯平滑模型的批量边删除判定准则，定义了适于聚类的邻接图的一般性质，提出并证明在kNN图基础上引入随机因子构造的随机kNN图，可以增强顶点之间的局部连通性，使聚类结果不再强烈依赖于某条边或某些边的保留或删除.RkNNClus算法简洁高效，依赖参数少，无需指定类簇数目，模拟和真实数据上的实验均有证明.

关键词：邻接图;批量边删除聚类;随机kNN图;边删除准则;局部高斯平滑

基金资助：国家科技重大专项（2016YFC0801800）；国家自然科学基金（41471315）