程汝峰， 刘奕志， 梁永全,2

(1.山东科技大学 计算机科学与工程学院 山东 青岛 266590； 2.山东省智慧矿山信息技术重点实验室 山东 青岛 266590)

基于互近邻相对距离的最小生成树聚类算法

程汝峰1， 刘奕志1， 梁永全1,2

(1.山东科技大学 计算机科学与工程学院 山东 青岛 266590； 2.山东省智慧矿山信息技术重点实验室 山东 青岛 266590)

针对互近邻距离的不足，提出了互近邻相对距离的概念，同时设计实现了一种新的最小生成树聚类算法.针对某些数据的不平衡问题，提出了兼容不平衡数据的最小生成树分割方法.算法设计简单，易于实现.实验结果表明，该算法能够聚类任意形状数据和兼容处理不均衡数据.对于具有良好几何形状的数据，该算法能够达到非常好的聚类效果，总体性能优于其他算法.

聚类； 互近邻相对距离； 最小生成树； 不平衡数据

0 引言

聚类是数据挖掘领域的重要研究内容之一，在识别数据的内在结构方面具有极其重要的作用.文献[1-4]对相关算法进行了研究.划分方法中经典的有K-means算法[5]、K-medoids算法[6]等；层次方法中经典的有CHAMELEON算法[7]、BIRCH算法[8]等；基于密度的方法中经典的有DBSCAN算法[9]、OPTICS算法[10]等；基于网格的方法中经典的有STING算法[11]等.

近几年，研究者从不同角度提出了许多优秀的算法.例如，文献[12]将密度的思想和距离相结合，提出一种快速的密度峰值聚类(DPC)算法.文献[13-14]在DPC算法的基础上，提出两种基于K近邻的样本分配策略.文献[15]提出一种基于数据点间信息传递的聚类算法(AP).针对……