资源描述：
《并行层次聚类技术研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、湖南大学硕士学位论文并行层次聚类技术研究姓名：郭里申请学位级别：硕士专业：@指导教师：李仁发20061210硕士学位论文摘要聚类分析是数据挖掘的重要研究领域之一，在工程、商业、生命科学、社会科学以及其他许多领域得到了广泛的应用。但由于聚类对象在高维特征空间分布的复杂性，聚类效果评价的不确定性和灵活性，以及聚类作为一个优化问题求解的高计算复杂性，聚类算法仍然面临着众多的问题和挑战。目前，研究者提出了大量的聚类算法。其中层次聚类算法是其中的主要方法之一，受到了大量学者的密切关注。目前最好的串行算法的时间复杂性可达到O(n2),但依然难于处理生物信息学或入侵检测中的海量数据；并行
2、算法目前多基于CREW-PRAM或CRCW-PRAM模型，其运行成本不低于O(n2)。这些算法多使用随机或概率算法，而且算法中的处理器数目无法根据运行环境改变，也没有考虑各并行处理器对共享存储器的存储冲突。本文通过利用完全图求欧几里德最小生成树算法和无存储冲突的连通分支确定算法，提出一种基于EREW-SIMD共享存储模型的无存储冲突并行层次聚类算法，其成本为O(n2)。通过与其他算法性能比较，比较结果说明本文提出的算法在保证存储无冲突的前提下，能以最优的成本在最弱的PRAM－EREW模型运行，且处理器可根据实际可用的计算资源动态调整。为了验证本文算法的性能，利用基准测试数据集
3、在高性能计算中心的IBMP690机器上进行了计算实验。实验结果表明：本文算法在计算时间和空间上具有一定的比较优势，对大规模数据集具有较强的可扩展性。关键词：层次聚类；存储冲突；并行算法；EREW-SIMD；高性能计算 I并行层次聚类技术研究 AbstractClusteringanalysisisoneoftheimportantareasinthedataminingresearch.Especially,itisapplicableinmanyfields,suchasengineering,business,biology,socialsciencesandothers
4、.However,becauseofthecomplexityofthedistributionofclusteringobjectathighdimensionalfeaturespace,theuncertaintyandtheflexibilityoftheevaluationofclusteringresultsandhighcomputingcomplexityofclusterproblemasanoptimizedproblem,clusteringalgorithmstillareconfrontedwithlotsofproblemsandchallenge
5、s.Atpresent,researchersputforwardlotsofclusteringalgorithms.Therein,hierarchicalclusteringalgorithmsasamainkind,arepaidmuchattention.SofartimecomplexityofthebestsequentialalgorithmsisuptoO(n2),buthugedatainbiologicalinformationorintrusiondetectionishardforthemtoprocess;mostoftheparallelalgo
6、rithmsusetheCRCW-PRAMorCREW-PRAMmodelsofcomputing,thecostofthesealgorithmsareO(n2)orlarger,mostarerandomizedorprobabilityalgorithms,unabletoautomaticallyadapttothenumberofprocessors,andnottakeaccountofsharingmemoryconflicts.Thispaperproposedanewparalleladaptivedeterministicalgorithmwithoutm
7、emoryconflictsbasedonEREW-SIMDsharedmemorymodelbyuseofcompletegraphandEuclideanminimumspanningtree,withcostofO(n2).Throughperformancecomparisonwithotheralgorithms,itisdemonstratedthatonguaranteeofnomemoryconflicts,thealgorithmcanrunontheweakestPRAM-EREWm
