论文部分内容阅读
随着多元分析、数据挖掘技术的不断发展,计算手段的日益更新,人们对数据挖掘的要求也愈来愈高。在实际应用中,为了找出感兴趣的知识,常会碰到带约束条件的问题。带约束的聚类问题是指:所分析的对象个体、聚类个体或者对象个体与聚类个体间存在着一种限制条件。带障碍距离的约束可以看做带约束聚类问题中,个体对象间约束的一个特例,也是带约束聚类问题里一个重要的研究方向。带障碍距离的聚类问题是指两个对象间的关系——空间距离,用带障碍距离代替普通聚类算法中的欧氏距离,并以之作为约束条件的一类聚类问题。本文以网格为基础,将DBSCAN聚类算法的寻找近邻对象的思路与计算机图形学中的种子填充着色算法相结合,提出了一个高效的带障碍聚类算法DCellO。它的执行时间基本与对象数量成线性关系;采用邻接网格的概念,因此能进行任意形状的聚类,同时,也将计算范围限制在局部区域内,提高了算法的执行速度;通过设定聚类的下限阈值,有效的消除了背景噪音对聚类质量的影响。对于海量数据,DCellO算法存在内存的瓶颈问题;此外,如果网格空间过大,也会导致内存不足的问题。针对这些缺陷,本文利用当前的热点技术——集群系统,结合密度聚类算法的局部性原理,提出了一个集群化的基于分区的带障碍聚类算法PDCellO。PDCellO算法通过分区的办法,将分析空间从大化小,然后将分区信息发往客户机,这就等于将服务器上的计算负荷转移到各个客户端上,同时也充分利用了闲置的计算资源。它能有效的处理海量数据,同时聚类效果也与串行DCellO完全一致。对提出的两个算法就时间复杂度和聚类结果的质量两方面进行了分析,并在模拟数据上进行了实验,验证了算法的正确性和有效性。