R--树结点自适应聚类分簇算法

《R--树结点自适应聚类分簇算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2013年3月第39卷第3期北京航空航天大学学报JournalofBeijingUniversityofAeronauticsandAstronauticsMarch2013Volt39NO．3R术-树结点自适应聚类分簇算法孙殿柱孙永伟李延瑞宋洋(山东理工大学机械_[程学院，淄博255091)摘要：为提高逆向工程中点云、三角网格等数据的索引效率，提出一种R‘一树结点自适应聚类分簇算法，采用均匀分布数据作为参考点集，基于间隙统计法及南-均值算法获得使结点相似度之和开始收敛的自然簇数，进而实现R+一树的结点自适应聚类分

2、簇．实验证明，该算法可实现各类复杂几何对象的R+．树结点分簇问题，并能降低R+一树结点分簇的参数依赖性，减少结点重合度，提高R4一树空间数据查询效率．关键词：R+一树；自适应聚类；结点分簇；结点相似度；间隙统计法；南一均值中图分类号：TP391．72文献标识码：A文章编号：1001-5965(2013)03—0344—05NodesplittingalgorithmofR+-treebasedonself-adaptationclusteringSunDianzhuSunYongweiLiYanruiSongYan

3、g(SchoolofMechanicalEngineering，ShandongUniversityofTechnology，Zibo255091，China)Abstract：AnodesplittingalgorithmofR+一treebasedonself—adaptationclusteringwasproposedtoim—provethespatialqueryefficiencyofthepointcloud，trianglemeshandetc．Pickingsomedatapointsasref

4、er·encepointsetwithuniformsampling．Thetruenumberofclusters，whichmadethetotalitycomparabilityvalueofnodestobecomeconvergence．wasobtainedbasedontheGapstatisticalmethodand

5、】}·meansalgorithm．Accordingtothetruenumberofclusters，thenodeofR‘treewassplitwithouthumanint

6、ervention．Experi—mentresultsprovethatthealgorithmcansolvethenodeclusteringproblemsforanycomplexgeometricobject，reducetheparametersdependenceandnodes’coincidencedegreeofnodesplittingofR‘tree，andimprovetheR+treespatialqueryefficiency．Keywords：R+一tree；self·adapta

7、tionclustering；nodesplitting；comparabilityvalue；gapstatistic；k-IneansR+一树是一种高度平衡树，允许结点相互重叠，具有优良的空间数据动态索引性能⋯，将其应用于逆向工程领域，可有效提高点云、三角网格等数据的处理效率卫。．R_树的构建关键在于结点的分裂与插入，而其结点分裂本质上是一个典型的聚类问题，可以基于现有成熟的聚类算法实现”～。．文献[1]采用穷举的思想列出各种符合要求的组合，从中选出MBR(MinimumBoundingRectangle)重叠

8、区域和MBR增量较小的组合，该算法时间复杂度较高，随着结点的数目增大，耗费时间呈指数上升．文献[4]采用矗一均值算法，将结点分簇由传统的两路分裂改进为由聚类技术支持的多路分裂，有效提高了R4一树空间查询性能，但在选择子树、结点分簇等过程中使用了结点MBR增量、重叠区域增量等评优指标，使得索引只对同维数据有效，若高维空间中存在低维数据(如多点共线、多点共面等)，会导致MBR各维度尺寸严重不均，使R’一树结点分簇失效p“。．文献[7—8]将几何对象统一表示为四维点对象，以结点包围盒外接球之问的重合度作为结点间的相似度，

9、并结合后一均值算法实现R+一树结点分簇；该算法可处理各种几何对象的结点分簇问题，但需要由收稿日期：2012-03-02；网络出版时间：2012-06一1510：12网络出版地址：www．cnki．net／kcms／detail／112625V．20I20615．1012．013．html基金项目：国家自然科学基金资助项目(51075247)；Ifj东省自然科