摘要摘要在数据挖掘领域中，聚类分析是一项重要的研究课题。它既可以作为一个单独的工具用以发现数据库中数据分布的深层信息，也可以作为其他数据挖掘分析算法的一个预处理步骤，因此研究如何提高聚类算法的性能具有重要的意义。本文在分析现有聚类算法特别是基于密度的聚类算法优缺点的基础上，结合空间索引技术，提出了一种新的基于格网密度和空间划分树的聚类算法（ＣＧＤＳＰＴ）；在聚类实验系统上，通过对多个样本数据集的实验结果的分析和算法的实际应用，验证了ＣＧＤＳＰＴ算法的有效性。本文的主要Ｔ作包括：１、将现有聚类方法按照五大类进行了系统的评述，并对基于密度的几种经典算法做了详细的介绍。２、通过对空间索引结构的综述，结合空问划分的特性，提出了一种基于空间划分的索引结构ＳＰ—Ｔｒｅｅ。ＳＰ—Ｔｒｅｅ有效地保存了数据的空间位置信息，为空间区域的邻域查询提供了极大的方便；同时它只索引非空单元格，不仅节省了存储空间还降低了算法的时间复杂性。３、结合基于格网密度聚类算法的特性和空间索引的优点，文章提出一种基于格网密度和空间划分树的聚类算法。算法充分借助了网格和空间索引的优势，使算法的时间复杂度与数据规模近似呈现线性关系。同时该算法具有能发现任意形状的簇、对噪声数据和数据输入顺序不敏感等优良特性。４、针对算法的参数设置问题，本文提出了一种根据样本数据的统计特性自行调整参数的方法，能有效地降低参数设置的难度，获得了较好的聚类效果。５、针对聚类有效性评价问题，本文提出了一种基于簇密度的适合任意形状簇的聚类有效性指数，实验表明其能有效地指导用户调整参数以获得满意结果。６、建立了一个聚类实验系统。在此系统上，利用多个样本集对本文提出的聚类算法进行详细的性能分析；将算法应用到中国分区域人口多维综合死亡模式的聚类中，并对聚类结果的区域性等特征进行了详尽分析。关键词：聚类；网格密度；空间划分树ＡｂｓｔｒａｃｔＡｂｓｔｒａｃｔＣｌｕｓｔｅｒｉｎｇａｎａｌｙｓｉｓｉｓｍｉｎｉｎｇ．Ｉｔａｎｉｍｐｏｒｔａｎｔｒｅｓｅａｒｃｈｐｒｏｂｌｅｍｉｎｔｈｅｄｏｍａｉｎｏｆｄａｔａａｓａｃａｎｂｅｕｓｅｄｎｏｔｏｎｌｙｓｅｐａｒａｔｅｔｅｃｈｎｉｑｕｅｔｏｄｉｓｃｏｖｅｒｔｈｅｉｎｆｏｒｍａｔｉｏｎａｂｏｕｔｄａｔａｄｉｓｔｒｉｂｕｔｉｏｎ，ｂｕｔａｌｓｏｔｈｅｒｅｆｏｒｅｉｔｉｓｖｅｒｙａｌｇｏｒｉｔｈｍｓ．Ｔｈｉｓｔｈｅｓｉｓｍａｉｎｌｙｓｔｕｄｉｅｓａｓｔｈｅｐｒｅｐｒｏｃｅｓｓｉｎｇｏｆｏｔｈｅｒｄａｔａｍｉｎｉｎｇｏｐｅｒａｔｉｏｎｓ，ｍｅａｎｉｎｇｆｕｌｔｏｒｅｓｅａｒｃｈｈｏｗｔｏｂｏｏｓｔｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆｃｌｕｓｔｅｒｉｎｇａｎｅｗｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｔｈｅｇｒｉｄ－ｄｅｎｓｉｔｙｐｒｅｓｅｎｔｅｄａｎｄｔｈｅｓｐａｔｉａｌｐａｒｔｉｔｉｏｎｔｒｅｅ（ＣＧＤＳＰＤｔｈｒｏｕｇｈａｎａｌｙｚｉｎｇｍａｎｙｒｅｐｒｅｓｅｎｔａｔｉｖｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｓｅｓｐｅｃｉａｌｌｙｔｈｅｄｅｎｓｉｔｙ－ｂａｓｅｄｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ．Ｗｅｄｅｓｉｇｎａｎｄｒｅａｌｉｚｅａｃｌｕｓｔｅｒｉｎｇｅｘｐｅｒｉｍｅｎｔａｌｓｙｓｔｅｍ（ＭＯＤＥ—ＣＥＳ）ｗｉｔｈｔｈｅｃ撑ｄｅｖｅｌｏｐｍｅｎｔｔ００１．ＩｔｉｓｐｒｏｖｅｄｔｈａｔｔｈｅＣＧＤＳＰＴｉｓｅｆｆｉｃｉｅｎｔｂｙａｎａｌｙｚｉｎｇｅｘｐｅｒｉｍｅｎｔｓｏｆｍａｎｙｄａｔａｓｅｔｓ．Ｔｈｅｐｒｉｍａｒｙｒｅｓｅａｒｃｈｉｎｃｌｕｄｅａｓｆｏｌｌｏｗｓ：１．Ｔｈｅｐｒｅｓｅｎｔｅｄｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｓａｒｅｄｉｖｉｄｅｄｔｏｆｉｖｅｃｌａｓｓｅｓｓｙｓｔｅｍｉｃａｌｌｙ．Ａｎｄｓｏｍｅａｎｄｄｉｓｃｕｓｓｅｄｄｅｎｓｉｔｙ－ｂａｓｅｄａｒｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｓａｒｅｄｅｓｃｒｉｂｅｄｉｎｄｅｔａｉｌ．２．Ｔｈｅｓｐａｔｉａｌｉｎｄｅｘｅｓｉｓｄｅｓｃｒｉｂｅｄａｎｄａｎｏｖｅｌｓｐａｔｉａｌｉｎｄｅｘｓｔｒｕｃｔｕｒｅ（ＳＰ—Ｔｒｅｅ）ｐｒｅｓｅｎｔｅｄｂａｓｅｄｏｎｔｈｅｓｐａｔｉａｌｐａｒｔｉｔｉｏｎ．ＴｈｅＳＰ—Ｔｒｅｅｃａｎｋｅｅｐｔｈｅｓｐａｔｉａｌｌｏｃａｔｉｏｎｏｆｔｈｅｄａｔａｅｆｆｉｃｉｅｎｔｌｙｔｈａｔｍａｋｅｓｔｈｅｒｅｇｉｏｎｎｅｉｇｈｂｏｒｈｏｏｄｓｅａｒｃｈｂｅｃｏｍｅｆａｃｉｌｉｔａｔｉｖｅ．Ｍｅａｎｗｈｉｌｅｍｅｍｏｒｙｉｔｏｎｌｙｉｎｄｅｘｅｓｔｈｅｎｏｎ－ｅｍｐｔｙｃｅｌｌｓｉｎｔｈｅｐａｒｔｉｔｉｏｎｅｄｓｐａｃｅｔｈａｔｔｈｅｐｅｒｆｏｒｍａｎｃｅ．ａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｓａｖｅｓｔｈｅａｎｄｂｏｏｓｔｓ３．Ａｃｌｕｓｔｅｒｉｎｇｔｈｅｇｒｉｄ—ｄｅｎｓｉｔｙａｎｄｓｐａｔｉａｌｐａｒｔｉｔｉｏｎｔｒｅｅ（ＣＧＤＳＰＴ）ｉｓｐｒｅｓｅｎｔｅｄｂａｓｅｄ—ｇｒｉｄｂｙａｓｓｉｍｉｌａｔｅｓｔｈｅａｄｖａｎｔａｇｅｓｏｆｔｈｅｂａｓｅｄ—ｄｅｎｓｉｔｙａｎｄｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍａｎｄｔｈｅｓｐａｔｉａｌｉｎｄｅｘｓｔｒｕｃｔｕｒｅ．ＣＧＤＳＰＴｉｓａｈｉｇｈｐｅｒｆｏｒｍａｎｃｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｗｈｏｓｅｃｏｍｐｕｔａｔｉｏｎａｌｃｏｍｐｌｅｘｉｔｙｉｓｌｉｎｅａｒ－ｔｉｍｅ．Ｍｅａｎｗｈｉｌｅｒｏｂｕｓｔｔｏｔｈｉｓａｌｇｏｒｉｔｈｍｈａｖｅｍａｎｙｏｔｈｅｒｓｏｕｔｓｔａｎｄｉｎｇｃｈａｒａｃｔｅｒｉｓｔｉｃｓｓｕｃｈａｓｉｔｉｓｏｕｔｌｉｅｒｓ，ｃａｎｉｄｅｎｔｉｆｙｃｌｕｓｔｅｒｓｈａｖｉｎｇａｎｙｓｈａｐｅｓａｎｄｗｉｄｅｖａｒｉａｎｃｅｓｉｎｓｉｚｅ，ｎｏｎ—ｓｅｎｓｉｔｉｖｅｔｏｔｈｅｓｅｑｕｅｎｃｅｏｆｔｈｅｓａｍｐｌｅ．４．Ａｉｍｉｎｇａｔｔｈｅｉｓｓｕｅｏｆｓｅｔｔｈｅｐａｒａｍｅｔｅｒｓｃｏｒｒｅｃｔｌｙ，ｗｅｏｆｆｅｒａｎｏｖｅｌｍｅｔｈｏｄ，ｗｈｉｃｈｍａｋｅｓｔｈｅｐａｒａｍｅｔｅｒｓｂｅｃｈａｎｇｅｄｗｉｔｈｔｈｅｓｔａｔｉｓｔｉｃｃｈａｒａｃｔｅｒｉｓｔｉｃｏｆｔｈｅｄａｔａｓｅｔ．知识水坝为您整理
基于嘲格密度与空间划分树的聚类算法研究ｔｏｓｅｔｔｈｅｐａｒａｍｅｔｅｒｓ．Ｉｔｃａｎｒｅｄｕｃｅｔｈｅｄｉｆｆｉｃｕｌｔｙｏｆｔｈｅｓｅｔｔｉｎｇｐａｒａｍｅｔｅｒｓａｎｄｇｅｔｐｅｒｆｅｃｔｒｅｓｕｌｔ．５．Ａｉｍｉｎｇａｔｔｈｅｃｌｕｓｔｅｒｉｎｇｖａｌｉｄｉｔｙｐｒｏｂｌｅｍ，ｗｅｐｒｅｓｅｎｔａｎｅｗｃｌｕｓｔｅｒｉｎｇｖａｌｉｄｉｔｙｉｎｄｅｘｂａｓｅｄｏｎｔｈｅｄｅｎｓｉｔｙｏｆｔｈｅｃｌｕｓｔｅｒ，ｗｈｉｃｈｉｓｆｉｔｆｏｒａｎｙｓｈａｐｅｃｌｕｓｔｅｒ．ＡｎｄｔｈｅｅｘｐｅｒｉｍｅｎｔｓｉｎｄｉｃａｔｅｔｈａｔｔｈｉｓｉｎｄｅｘＣａｎｈｅｌｐｔｈｅＵＳｅｒａｄｊｕｓｔｔｈｅｐａｒａｍｅｔｅｒｓｉｎｏｒｄｅｒｔｏｇａｉｎｓａｔｉｓｆｉｅｄｃｌｕｓｔｅｒｉｎｇｒｅｓｕｌｔ．６．Ａｃｌｕｓｔｅｒｉｎｇｅｘｐｅｒｉｍｅｎｔａｌｓｙｓｔｅｍｉｓｂｕｉｌｔ．Ａｎｄｔｏｅｖａｌｕａｔｅｔｈｅｐｅｒｆｏｒｍａｎｃｅａｎｄｅｆｆｅｃｔｉｖｉｔｙｏｆｔｈｅａｌｇｏｒｉｔｈｍｐｒｏｐｏｓｅｄｉｎｔｈｉｓｔｈｅｓｉｓ，ｅｘｔｅｎｓｉｖｅｏｆｅｘｐｅｒｉｍｅｎｔｓｈａｖｅｂｅｅｎｄｏｎｅ．Ｍｅａｎｗｈｉｌｅ，ｗｅａｐｐｌｙｔｈｉｓａｌｇｏｒｉｔｈｍｔｏｔｈｅｃｌｕｓｔｅｒｉｎｇｏｆＣｈｉｎａｄｉｓｔｒｉｃｔｄｅａｔｈｐａｔｔｅｒｎ，ａｎｄａｎａｌｙｚｅｔｈｅｒｅｇｉｏｎａｌｉｔｙｃｈａｒａｃｔｅｒｏｆｔｈｅｃｌｕｓｔｅｒｉｎｇ—ｒｅｓｕｌｔＴｈｅｒｅｓｕｌｔｓｓｈｏｗｔｈａｔａｌｇｏｒｉｔｈｍ．ＯＵｒａｎｄＳＯｏｎ．ａｌｇｏｒｉｔｈｍｉｓａｂ５【ｇｈｐｅｒｆｏｒｍａｎｃｅａｎｄｅｆｆｉｃｉｅｎｔｃｌｕｓｔｅｒｉｎｇＫｅｙＷｏｒｄｓ：Ｃｌｕｓｔｅｒｉｎｇ；Ｇｒｉｄ－Ｄｅｎｓｉｔｙ；ＳｐａｔｉａｌＰａｒｔｉｔｉｏｎＴｒｅｅ知识水坝为您整理
基于网格密度和空间划分树的聚类算法研究(模式识别与智能系统专业优秀论文)
