摘要：基于密度的聚类是聚类分析中的一种，其主要优点是发现任意形状的聚类和对噪音数据不敏感．文章提出了一种新的基于网格密度和空间划分树的CGDSPT（Clustering based on Grid—Density and Spatial Partition Tree）聚类算法．其创新点在于，将数据空间划分成多个体积相等的单元格，然后基于单元格定义了密度、簇等概念，对单元格建立了一种基于空间划分的空间索引结构（空间划分树）来对数据进行聚类，CGDSFT算法保持了基于密度的聚类算法的上述优点，而且CGDSPT算法具有线性的时间复杂性，因此CGDSFT算法适合对大规模数据的挖掘．理论分析和实验结果也证明了CGDSFT算法的优点。

关键词：聚类 网格密度 空间划分树 

单位：厦门大学信息科学与技术学院模式识别与智能系统研究所 厦门361005 浙江大学公共管理学院 杭州310027