基于单元格的多密度gmdbscan聚类算法

《基于单元格的多密度gmdbscan聚类算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、兰州大学硕士学位论文基于单元格的多密度GMDBSCAN聚类算法姓名：敏玉芳申请学位级别：硕士专业：计算机软件与理论指导教师：陈晓云20080501：鸷埘虫警基于单元格的多密度G如BscAN聚类算法兰州大学硕士学位论文摘要聚类分析作为数据挖掘领域中的一个重要分支，研究数据对象的分类问题，在模式识别、图像处理、市场研究以及生命科学等众多学科领域具有广泛的应用前景。DBSCAN算法因为可以发现任意形状的聚类，排除噪声干扰等优点而备受关注。但是该算法只是简单的使用全局参数，参数的设置缺乏针对性，将会导致对多密度的数

2、据集的聚类效果不理想；在对大数据集进行聚类时，算法时间复杂度较高，对大数据集适用性较差。本文结合空间索引技术，提出了一种基于单元格的多密度聚类算法G加BSCAN，并对多个样本数据集进行了实验，实验结果验证了GMDBSCAN算法的有效性。本文的主要工作如下：提出了一种基于单元格的多密度聚类算法GMDBSCAN。从聚类质量和复杂度两方面改进了DBSCAN算法。GMDBSCAN算法引入了基于空间的划分技术划分数据空间，以每个单元格作为一个局部区域，根据每个单元格的密度确定局部的MinPts参数；根据类间的相似度合

3、并类；用基于距离的方法处理边界，提高了算法的聚类质量。GMDBSCAN算法引入了SP．Tree空间索引结构，保存了数据的空间位置信息，为空间区域的邻域查询提供了极大的方便，同时它只索引非空单元格，不仅节省了存储空间还降低了算法的时间复杂性。本文还提出用位图存储数据的邻域关系，避免了反复查询和计算。本文对GMDBSCAN算法的时间复杂度和空间复杂度进行分析。在模拟数据集和真实数据集上进行了GIVIDBSCAN算法的性能测试，并对实验结果进行了分析。关键词：数据挖掘；聚类；单元格密度；sP．Tree：局部Min

4、Pts；多密度萄埘虫尊基于单元格的多密度G彻BScAN聚类算法兰州大学硕士学位论文AbstractAsanimportantandactivebranchofdatamining，clusteringattempttodiscovervaluableknowledgefromhugeunknowndatabase．Furthermore，clustednghasbeenbroadlyapplyinginpatternrecognition,imageprocessing,marketresearch,lif

5、escienceandSOon．DBSCANisoneofthemostpopularalgorithmsinclusteranalysis．ItCalldiscoveranyclusterswitharbitraryshapeandseparatenoise．Butthisalgorithmdoesn’tchooseparameteraccordingtodistributingofdataset．ItjustusestheglobalMinPtsparameterofdatasetsimply,SOth

6、attheclusteringresultofvaryingdensitydatabaseisinaccurate．AndwhenWeuseittoclusterlargedatabases，wewillcosttoomuchtime．Inordertofixtheseproblems，weproposeGMDBSCANalgorithmbasedonspatialindexand鲥dtechnique．Theprimaryresearchincludeasfollows：‘‘Aclusteringalgo

7、rithmbasedontheunit鲥ddensityandspatialpartitiontreeispresentedforimprovingtheperformanceandclusteringqualityofDBSCANalgorithm．Atthepartofclusteringquality：Weestimatethedensitydistributingofdatasetaccordingtogriddensity,anddecidethelocal_density．ThenWeclust

8、erthelocaldata．setbyDBSCANalgorithm。Atlast,Wecombineallclassesanddealwithboundary．Atthepartofperformance：webuildindexforthepartitionednon-emptyunit鲥dwithSP-Tree．TheSP—Treecankeepthespatiallocationofthedataeff