一种改进的快速聚类算法及并行化研究

《一种改进的快速聚类算法及并行化研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、兰州大学硕士学位论文一种改进的快速聚类算法及并行化研究姓名：祁小丽申请学位级别：硕士专业：计算机科学与技术、计算机软件与理论指导教师：陈晓云20090501兰州大学硕：L学位论文一种改进的快速聚类算法及并行化研究摘要聚类分析是数据挖掘领域中的一个重要分支，研究数据对象的分类问题，广泛地应用于模式识别、图像处理、市场研究以及生命科学等众多领域，所以对聚类算法的研究具有重要意义。为了解决聚类算法普遍存在的参数难以确定，效率低下，聚类质量较差等问题，本文对基于密度的聚类算法进行了深入的探索性的研究，提出了一个新的快

2、速聚类算法，并将该算法并行实现。主要研究工作及取得的创新性成果有以下几个方面：本文在LDBSCAN的基础上，提出了一种改进的快速聚类算法GLDBSCAN。改进算法设计了一种新的对数据空间进行划分的网格划分方法，并采用空间索引SP-Tree来组织网格结构，它保存了数据的空间位置信息，并只索引非空网格，不但节省了存储空间还降低了算法的时间复杂性。算法同时提出用网格中心对象来代表网格包含的对象集合进行聚类，从而降低聚类时间和I／O消耗，实现快速聚类。为了进一步提高聚类算法的执行效率及可扩展性，本文对并行GLDBSC

3、AN算法进行了研究，通过运用SPMD的并行算法设计思想，设计了一种高性能计算集群环境下基于数据交叠分区的并行聚类算法PGLDBSCAN。该并行算法采用了基于对等模型的数据并行策略和基于消息传递的异步通信策略。并行GLDBSCAN能够大幅度提高算法的效率，同时降低算法对内存的较高要求，增强了算法的可扩展性。本文从理论分析和实验两个方面验证了算法GLDBSCAN及其并行实现PGLDBSCAN的高效性，可用性及可扩展性。关键词：聚类；密度；网格；SP-Tree；LDBSCAN；并行；交叠分区兰州大学硕士学位论文一种

4、改进的快速聚类算法及并行化研究ABSTRACTClusteranalysisisaveryimportantresearchdirectionofthedatamining．Thegoalofclusteringalgorithmsistodecomposeadatasetintoasetofmeaningfulgroups．Itiswidelyusedinpatternrecognition，imageprocessing，marketresearch，llfescience．eto．Therefore，t

5、heresearchontheclusteringalgorithmshasgreatsignificanceandbroadprospects．However,existingclusteringalgorithmsmostlyhasdrawbacksincludingbadefficiencyandqualityofclusteringresult，andhardtodetermineparameters．Inordertosolveaboveproblems，thispapermadeadeepstud

6、yondensity-basedclusteringalgorithms，andpresentedallimprovedfastclusteringalgorithmanditsparallelimplementation．Themainresearchworkandtheinnovativeresultsa佗asfollowing：AfastclusteringalgorithmGLDBSCANisproposedinthispaper,whichconsiderablyspeedsuptheorigina

7、lLDBSCAN．Thenewalgorithmpresentsanovelapproachfor鲥dgenerationandadoptsthespatialindexstructureSP-Treetoorganizethegrids．TheSP-Trcepreservesthespatiallocationinformationoftheobjects，andonlyindexesthenon-emptygrids，itnotonlysavesstoragespacebutalsoreducesthet

8、imecomplexityofthealgorithm．Inaddition，GLDBSCANchoosestherepresentativeobjectinagridtorepresentallobjectsinthegridtocluster,whichreducestheexecutionfrequencyandFOcostdramatically．Inordertofurtherimprov