基于网格的多密度聚类算法

提出了一种多密度网格聚类算法GDD。该算法主要采用密度阈值递减的多阶段聚类技术提取不同密度的聚类，使用边界点处理技术提高聚类精度，同时对聚类结果进行了人工干预。GDD  算法只要求对数据集进行一遍扫描。实验表明，该算法可扩展性好，能处理任意形状和大小的聚类，能够很好的识别出孤立点或噪声，在处理多密度聚类方面有很好的精度。关键词：密度阈值递减；多阶段聚类；边界点提取聚类是数据挖掘中的一种重要技术，它的目标是将数据集分成若干个子集，同一个子集中的对象是相似的，不同子集中的对象不相似。在几何方面，聚类是在整个数据集中确定由稀疏区域分开的密集区域。由于其无指导学习能力，聚类算法能在数据集中发现隐藏的数据模式，所以对聚类算法的研究一直很活跃。基于相似性已经有很多聚类算法，这些聚类算法大体上可分为基于划分的聚类算法、基于密度的聚类算法、基于层次的聚类算法和基于网格的聚类算法等。其中基于网格的聚类算法由于只考虑网格单元而不是考虑每个点，它的计算效率比较高。基于网格的聚类算法认为：当网格划分的比较细时，每个网格内的点可看作是相似的。但是对多密度的数据集，这些算法很难得到满意的聚类结果。本文的主要目的就是利用网格技术解决对多密度数据集的聚类。聚类分析所使用的数据集中，各个类的密集往往不尽相同，甚至差别很大。大多数现有的聚类算法都是致力于如何发现任意形状和大小的类，但很难有效的处理密度差别较大的数据集。能够处理多密度数据集的聚类算法有Chameleon[1]、共享近邻SNN  算法[2]、多阶段等密度线算法[3]等。Chameleon  算法可以用来处理多密度的数据集，但当数据集较大时其算法的时间复杂度太高。共享近邻SNN  算法的主要思想是：对于数据集中每个点，找出距离其最近的K  个邻近点，形成一个集合。然后考虑数据集中的任意两个点，若对应于这两个点的K  个邻近点集合交集部分的点数超过一个阈值，则将这两个点归于一类。SNN  算法的优点是可以对不同密度和形状的数据集进行聚类，缺点是在多密度聚类和处理孤立点或噪声方面精度都不高（见图1(a)和图2(a)）。多阶段等密度线算法采用多阶段的方式，利用等密度线的思想对数据集进行聚类，它的缺点是不能有效地分离出多个类。文献[2]给出了SNN  算法和一些现有的聚类算法的比较结果，结果表明SNN  算法表现出了较好的性能。本文只给出GDD  算法和SNN  算法聚类结果的比较，从比较结果可以看出GDD  算法在多密度聚类、孤立点或噪声处理方面显示出了很高的精度。现有的聚类算法大都忽视了聚类过程中的人工参与，很难在聚类过程中充分利用专家关于领域的知识指导聚类过程，所以得不到满意的聚类结果。在GDD  算法中，对聚类结果就进行了人工干预。