p2p系统中聚类算法的研究

《p2p系统中聚类算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号密级UDC编号桂林电子科技大学硕士学位论文题目:P2P系统中聚类算法的研究(英文)ResearchonClusteringAlgorithminP2PSystem研究生姓名：刘天鹏指导教师姓名、职务：周娅教授申请学科门类：工学硕士学科、专业：计算机软件与理论提交论文日期：2008年3月28日论文答辩时间：2008年6月17日2008年3月28日万方数据独创性（或创新性）声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果

2、；也不包含为获得桂林电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签名：日期：关于论文使用授权的说明本人完全了解桂林电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属桂林电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为桂林电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、

3、缩印或其它复制手段保存论文。（保密的论文在解密后遵守此规定）本学位论文属于保密在年解密后适用本授权书。本人签名：日期：导师签名：日期：万方数据摘要摘要随着P2P技术的不断发展，P2P系统已经成为储存海量数据的容器，如何在这样一个包含丰富数据的容器中发现知识成为越来越多的学者研究的内容。P2P技术最大的特点是没有中心节点，系统完全分布，这虽然使得P2P系统具有健壮性和可扩展性，但也加大了设计适用于P2P系统的数据挖掘算法的难度。聚类是一种常用的数据挖掘技术。本文在分析了不同P2P拓扑结构特点的基础上，通过深入研究了不同聚类算法的聚类过程，总结了P2P

4、系统中的聚类算法需要满足的条件，并在此基础上设计了KIPN（K-meanInP2pNetworks）聚类算法和SOC（StructureOverlayClustering）聚类算法分别用于非结构化拓和结构化拓扑P2P系统的聚类。KIPN算法是一个非结构化拓扑P2P系统的k-mean算法，通过扩展经典k-mean算法的迭代过程，在每个节点只与其直接相邻节点交换信息的情况下通过有限次迭代使每个节点上的局部数据在全局视图下聚类。经实验数据分析验证KIPN算法可以适应P2P系统中的节点动态变化，并与集中式聚类算法有相似的聚类结果。SOC算法利用结构化CAN

5、系统中数据严格按照规律分布的特点，将系统坐标空间与聚类数据空间重叠，使相邻数据存储在同一(或相邻)节点上。用系统坐标空间划分的逆过程进行凝聚型层次聚类，使CAN系统数据聚类达到与集中式聚类算法相同的结果。通过分析SOC算法的聚类过程得到在数据维数一定的情况下算法的时间复杂度与系统中的节点数呈线性关系。本文的另一个工作是设计并实现了一个P2P聚类算法的仿真实验系统，并在该系统中对两个算法进行仿真实验。系统设计时使用了设计模式中的思想，使两个算法能够方便在同一框架下实现。关键词：对等网；数据挖掘；层次聚类；k-mean算法.{I{万方数据桂林电子科技大

6、学学位论文{II{万方数据AbstractAbstractWiththerapiddevelopmentofP2Ptechnology,P2Psystemhasbecomeamassivedatastoragecontainer.Moreandmorescholarsconcernedabouthowtodiscoveryknowledgefromsuchacontainers.ThegreatestfeatureofP2Ptechnologyisnocentralnode,andentirelydistribution.Thisnotonlyma

7、kesP2Psystemrobustandscalable,butalsoincreasesthedi±cultyofdataminingalgorithmdesignbasedonP2Psystem.Byanalyzingthecharacteristicsofdi®erentP2Ptopologyandin-depthstudyingofdi®erentclusteringalgorithm,thisthesissummarizesrequirementsofdataminingalgorithmdesignbasedonP2Psystem,a

8、nddesignsKIPN(K-meanInP2PNetworks)algorithmsandSOC(StructureO