基于改进DBSCAN算法的高性能计算中心用户分类的研究及应用

徐海啸, 麻 婧, 吴 旗

(吉林大学 a. 计算机科学与技术学院； b. 高性能计算中心, 长春 130012)

0 引 言

数据挖掘是指从数据库的大量数据中揭示出隐含的、 先前未知的并有潜在价值信息的非平凡过程。聚类分析则是数据挖掘中的一个研究方向。聚类的目标是将数据分类到不同的类或簇, 使同一簇中对象有很大的相似性, 而不同簇间的对象有很大的相异性。聚类分析可应用于各种用户数据的分类中, 如民航客户分类[1]以及电信客户分类[2]。

DBSCAN(Density Based Spatial Clustering of Applications with Noise)算法[3]是基于密度的聚类分析算法, 对噪声有抵抗性, 并且能发现任意形状的类簇,但却对初始参数E(邻域半径)和MPts(E邻域最小点数)非常敏感[4]。

针对这一缺点, 近些年出现了一些改进研究。文献[5]提出了K-dist图的思想, 主要解决了类之间包含和交叉关系。文献[6]采用对象投影的方法, 考察对象的临域平衡性, 使用平衡密度可达聚簇, 有效排除了边界稀疏对象的噪声。文献[7]采用选取核心对象邻域中的代表对象扩展类, 相比文献[5,6]算法, 提高了算法时间性能。其他聚类算法的改进思路也可应用到DBSCAN算法中, 如文献[8]提出的加速k-means算法, 利用迭代调整簇阈值的方法将簇中心迁移, 这一思路与文献[9]中通过构建网格密度矩阵划分密度阈值, 从而解决DBSCAN参数选取困难的方法相似。文献[9]中提到的MDBSCAN算法相比于上述算法能有效发现密度相差较大的簇, 但由于其使用了从密到疏的分阶段聚类方法, 对初始参数的依赖性依然很大。

为更大程度地降低初始参数的影响, 笔者提出了改进算法, 即在MDBSCAN[9]的基础上添加了簇排序队列。……