基于网格密度和空间划分树的聚类算法研究

《基于网格密度和空间划分树的聚类算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、厦门大学硕士学位论文基于网格密度和空间划分树的聚类算法研究姓名：曾东海申请学位级别：硕士专业：模式识别与智能系统指导教师：米红20060401摘要在数据挖掘领域中，聚类分析是一项重要的研究课题。它既可以作为一个单独的工具用以发现数据库中数据分布的深层信息，也可以作为其他数据挖掘分析算法的一个预处理步骤，因此研究如何提高聚类算法的性能具有重要的意义。本文在分析现有聚类算法特别是基于密度的聚类算法优缺点的基础上，结合空间索引技术，提出了一种新的基于格网密度和空间划分树的聚类算法(CGDSPT)；在聚类实验系统上，通过对多个样本数据集的实验结果的分析和算法的实际应用，验证了CGDSPT算法的有

2、效性。本文的主要T作包括：1、将现有聚类方法按照五大类进行了系统的评述，并对基于密度的几种经典算法做了详细的介绍。2、通过对空间索引结构的综述，结合空问划分的特性，提出了一种基于空间划分的索引结构SP—Tree。SP—Tree有效地保存了数据的空间位置信息，为空间区域的邻域查询提供了极大的方便；同时它只索引非空单元格，不仅节省了存储空间还降低了算法的时间复杂性。3、结合基于格网密度聚类算法的特性和空间索引的优点，文章提出一种基于格网密度和空间划分树的聚类算法。算法充分借助了网格和空间索引的优势，使算法的时间复杂度与数据规模近似呈现线性关系。同时该算法具有能发现任意形状的簇、对噪声数据和数

3、据输入顺序不敏感等优良特性。4、针对算法的参数设置问题，本文提出了一种根据样本数据的统计特性自行调整参数的方法，能有效地降低参数设置的难度，获得了较好的聚类效果。5、针对聚类有效性评价问题，本文提出了一种基于簇密度的适合任意形状簇的聚类有效性指数，实验表明其能有效地指导用户调整参数以获得满意结果。6、建立了一个聚类实验系统。在此系统上，利用多个样本集对本文提出的聚类算法进行详细的性能分析；将算法应用到中国分区域人口多维综合死亡模式的聚类中，并对聚类结果的区域性等特征进行了详尽分析。关键词：聚类；网格密度；空间划分树AbstractClusteringanalysisisanimporta

4、ntresearchprobleminthedomainofdatamining．Itcanbeusednotonlyasaseparatetechniquetodiscovertheinformationaboutdatadistribution,butalsoasthepreprocessingofotherdataminingoperations，thereforeitisverymeaningfultoresearchhowtoboosttheperformanceofclusteringalgorithms．Thisthesismainlystudiesanewclusteri

5、ngalgorithmbasedonthegrid-densityandthespatialpartitiontree(CGDSPDthroughanalyzingmanypresentedrepresentativeclusteringalgorithmsespeciallythedensity-basedclusteringalgorithm．Wedesignandrealizeaclusteringexperimentalsystem(MODE—CES)withthec撑developmentt001．ItisprovedthattheCGDSPTisefficientbyanal

6、yzingexperimentsofmanydatasets．Theprimaryresearchincludeasfollows：1．Thepresentedclusteringalgorithmsaredividedtofiveclassesanddiscussedsystemically．Andsomedensity-basedclusteringalgorithmsaredescribedindetail．2．Thespatialindexesaredescribedandanovelspatialindexstructure(SP—Tree)ispresentedbasedon

7、thespatialpartition．TheSP—Treecankeepthespatiallocationofthedataefficientlythatmakestheregionneighborhoodsearchbecomefacilitative．Meanwhileitonlyindexesthenon-emptycellsinthepartitionedspacethatsavesthememoryandboostst