基于MPI的层次聚类算法的研究及实现

《基于MPI的层次聚类算法的研究及实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于MPI的层次聚类算法的研究及实现摘要数据挖掘领域涉及很多方面的知识，聚类分析是该领域中的技术之～，也是该领域中重点研究内容之一。聚类分析实际上是对数据集进行分类、分组的一种方法。聚类分析应用广泛，在机器学习、生物学、统计学、市场营销等等很多领域都被用到，在这些领域中聚类分析起到了至关重要的作用，做出了不小的贡献。聚类算法是聚类分析中起着决定性作用的部分，聚类分析的中的聚类算法有很多，其中层次聚类算法是主要算法之一。层次聚类算法的特点是结构简单、运行时速度快，并且在遇到大规模数据集的时候，它能够对其进行有效的处理。该算法是实际应用中聚类分析的支柱。层次聚类算法在运行时，会对所有待聚类数

2、据进行距离计算，得到距离矩阵，然后按照矩阵中元素的值对类进行合并操作，产生新的类，但是每一次合并操作之后，要再次对需所有类进行类间距离的计算，这样的操作使得计算的时间复杂度很高。随着数据规模的不断递增，提高聚类效率和聚类质量也是一个刻不容缓的研究方向。基于上述分析，针对层次聚类算法存在的问题，本文对传统层次聚类算法进行了改进，通过把类之间的距离按照一定顺序进行排序，以此来解决合并类后还要重新计算距离的问题，在此基础上本文又结合了最小生成树的算法，即克鲁斯卡尔算法对层次聚类算法做了进一步改进，总体上使得算法可伸缩性得到提高，计算复杂性得到降低。为进一步提高算法执行效率，论文同时研究了并行层

3、次聚类算法的并行实现。选用局域网环境，并行虚拟机PVM和LINUX，共同搭建的机群系统作为并行计算平台。在并行程序的模型上采用了基于MPI消息传递接口的模型。论文在时间复杂度问题上，进行了理论分析，并且进行了实验，从这两个方面对并行算法进行了评价。实验结果表明：基于MPI的层次聚类算法的聚类结果与串行算法相同，但执行效率得到了很大的提高。关键词聚类分析；层次聚类；排序；并行算法；MPI哈尔滨理工大学工学硕士学位论文ResearchandImplementationofHierarchicalClusteringAlogithmBasedonMul邱leProgramAbstractClu

4、steranalysiswhichbelongtothefieldofdataminmgisallimportantresearchdirection,theclusteranalysisisactuallyaclassificationofthedataset,apacket．Clusterarlalymiswidelyusedinmanya硝鞠sofmac2遗eteammg,biology,statistics,market,marketing,etc．playanimportantrole．Theclusteringalgoriuanistophyadecisiveroleinth

5、edusteranalysis，hierarchicalclusteringalgorithmisolleofthemainalgorithm．Hierarchicalclusteringalgorithmissimpleandfaster,isapillarofclusteranalysis．Hierarchicalclusteringalgorithmneedtocalculatethedistancebetweenallclasses，andmergedasses笋butWemustrecalculatethedistancebetweentheclass,thehi曲comple

6、xityofthiscalculationtime；Withthecontinuouslyincreasingdatasizeandimprovetheefficiencyofclusteringisalsoallimportantresearchquestion．ProblemsofthehierarchicalclusteringalgorithmbasedOntheaboveanalysis，thisarticleonthetraditionalhierarchicalclusteringalgorithmhasbeenimprovedbythedistancebetweenthe

7、classaccordingtoacertainordertosort,inordertoresolvethemergeclassevellafterre-caleulatingthedistancconthisbasis，thisarticlealsocombhlestheKruskalminimunlspanningtreealgorithmofhierare牺ealclustea圣ngalgorithmtofurtherimp