基于密度的并行聚类算法研究

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

1、湖南大学硕士学位论文基于密度的并行聚类算法研究姓名：毛韶阳申请学位级别：硕士专业：计算机应用技术指导教师：李肯立20070514高教硕士学位论文摘要随着现代生物技术的不断发展特别是基因组计划的实施，人们不断的获得大量基因序列数据，互联网上的基因数据正呈指数增长，这些内涵丰富的数据为人们分析和研究基因的组成与功能之间的关系提供了基础。现代信息技术的发展尤其是超级计算机的飞速发展所带来的高速计算能力正引导着算法研究者们不断研究出新的并行聚类算法，以解决高维海量基因序列数据的计算问题。大量事实说明，一个准确、高效的并行聚类算法对生物计算尤其是基因序列数据计算的影响力是不可估量

2、的。本文首先对目前的几种典型的串行聚类算法就适用数据属性范围、时间复杂度等方面进行了分析，提出了对基因序列数据采用基于密度聚类的观点，提出了一种和基因序列数据相匹配的密度函数计算方法及一个相适应的邻域半径计算公式。通过对并行计算模型的研究，设计了一种基于密度的并行聚类算法，通过32nn次时间复杂度为O()的并行运算，能使并行聚类过程的时间复杂度变为O()。PP比较传统的基于密度的聚法算法而言，增加了一次计算，以增加一次计算为代价来减少计算机操作上的开销。最后在计算机群上对本文所提算法进行了验证，实验结果表明：此算法对高维海量基因序列数据有着很好的聚类效果，簇内数据收敛度

3、高，展示了良好的时间优越性。关键词：并行算法；聚类算法；消息传递；基因序列；密度函数I基于密度的并行聚类算法研究ABSTRACTWiththecontinuousdevelopmentofmodernbiologytechnology,especiallytheimplementoftheHumanGenomeProject,peoplehaveacquiredquantitiesofgenesequencedata,thegene'sdataintheInternetispresentingexponentialincrease,whichsuppliesbasisf

4、orpeople'sanalyzingandresearchtherelationshipofgene'scomposingandfunctions.Thedevelopmentofthemoderninformationtechnicalespeciallythesupercomputerhasbroughthigh-speedcomputeability,itcanguidetheresearcherstofindnewclusteringalgorithmforthehighdimensionthousandsgenesequencedataanalyses.Lo

5、tsofexperimentsshowthatanaccurateandefficientparallelalgorithmisimpossibletoestimatetheinfluencetothebiologycomputeespeciallytothegenesequencedata.Firstly,thispaperanalyzedsometypicalserialclusteringalgorithmaboutdatapropertyandthetimecomplexity,putforwardapointthatthegenesequencedataclu

6、steringmaybaseonthedensity,andproposeamethodofcomputingaboutthedensityfunctionandtheneighborarearadius.Secondly,thispaperstudiedtheparallelalgorithmmodel,anddesignedaparallelclusteringalgorithmbasedonthedensity,itcanmaketheparallelclusteringntimecomplexityintoO()throughthreetimecomputing

7、withthetimecomplexityP2nofO().Comparetothetraditionalclusteringalgorithm,itaddedoncecompute.PTakeaddingoncecalculationaspricetoreducetheprocessingexpense.Finally,validatedthisalgorithmoncomputerclusters,theexperimentshowthattheparallelclusteringalgorithmhasefficientcluste