论文部分内容阅读
随着计算机的普及和物联网的发展,信息大爆炸的时代已经来临。每天的数据以TB、PB甚至更大的单位更新。数据的不断增大,促使数据获取技术和数据存储技术,也实现了突飞猛进的发展,但是如何处理这些数据,从这些数据中获取有用信息,给研究者们带来了巨大的挑战。数据挖掘技术由此应运而生,已经成为越来越多的学者研究的热点。数据挖掘技术就是在大规模的含有噪声的数据中,学习包含在数据中的知识,获取有用的信息,然后把这些信息应用到生活科研等各个领域。聚类分析是数据挖掘技术领域内的重要研究方向之一,并在数据挖掘领域已得到广泛应用。通过对传统的聚类算法的研究,有很多经典的算法以及针对经典算法的改进,改进方面包括算法对数据的适应性、降低算法的时间复杂度,弱化算法对参数的敏感、提高算法对噪声点的识别能力、削弱算法对先验知识的依赖等。但是还是不可避免的在某些方面有所欠缺。例如基于密度的聚类算法,虽然可以在含有噪声的数据中识别出任意形状的簇,然而效率不高限制了其处理大规模数据的能力且处理多密度数据有待完善;基于网格的聚类算法把数据空间划分成有限个单元网格,处理的对象由网格单元为单位代替数据对象为单位,一般情况下,网格数量是远远小于数据对象个数的。这种方法的优点大大降低了处理对象的个数,而且聚类结果与数据的输入顺序无关,处理对象的减少意味着算法的时间复杂度降低,有较高的运算效率。但是现有的基于网格的聚类算法通常只有在数据集分布较为均匀的情况下才能够得到较好的聚类效果,对于数据对象在空间分布不均匀的情况聚类结果的精度还有较大的提升空间。针对以上问题,本文的主要研究工作如下:作为经典基于密度的聚类算法DBSCAN聚类算法能够在含有噪声的数据里识别任意形状的簇,但由于使用固定的Eps和Minpts,使得对于多密度的数据聚类效果不理想。针对此问题提出一种改进的DBSCAN多密度聚类算法。该算法先对数据集做预处理,使每个对象多一个属性,该属性用来记录该对象在给定半径的邻域内数据的密度,并以此属性对数据集排序;根据此密度自适应的生成适合该密度的密度阈值参数。该算法能够有效处理多密度数据,而且数据预处理技术能够有效避免数据输入顺序对聚类结果的影响。为了提高基于网格相对密度差的扩展聚类算法(ECRGDD)的聚类精确度,提出了基于动态的网格相对密度差聚类算法(CDGRDD),此算法把初始单元网格密度定义为动态,有效解决了ECRGDD对于中心密度大、边缘密度稀疏的类聚类效果不佳的问题,另一方面,在密度相似相邻的网格合并时加入距离判断条件,由此减少网格合并的盲目性。多次实验结果表明,CDGRDD能够较为高效的处理多密度数据。网格划分能够提高效率,把这种思想用在DBSCAN聚类算法中,提出一种基于区域划分的DBSCAN多密度聚类算法。该算法利用网格相对密度差把数据空间划分成密度不同的区域,根据每一区域的不同密度自动生成不同的Eps参数,并利用DBSCAN算法对每一个区域进行聚类。该思想使得DBSCAN算法在查找密度相连时只在本区域查找,避免了对所有数据的遍历。有效的提升DBSCAN聚类算法精确度;区域划分较多时算法效率也能得到有效提高。