• CN:11-2187/TH
  • ISSN:0577-6686

机械工程学报 ›› 2015, Vol. 51 ›› Issue (19): 131-137.doi: 10.3901/JME.2015.19.131

• 数字化设计与制造 • 上一篇    下一篇

扫码分享

R树上溢结点增量式k均值聚类优化分裂方法

李延瑞1, 孙殿柱2, 张英杰1, 聂乐魁2   

  1. 1.西安交通大学机械工程学院;
    2.山东理工大学机械工程学院
  • 出版日期:2015-10-05 发布日期:2015-10-05
  • 基金资助:
    国家自然科学基金资助项目(51075247)

Splitting Approach for Overflow Nodes in R-tree via Incremental k-means Clustering Optimization

LI Yanrui1, SUN Dianzhu2, ZHANG Yingjie1, NIE Lekui2   

  1. 1.College of Mechanical Engineering, Xi’an Jiaotong University;
    2.College of Mechanical Engineering, Shandong University of Technology
  • Online:2015-10-05 Published:2015-10-05

摘要: R树能较好地满足逆向工程、CAD/CAM、机器视觉等领域的动态数据维护及空间查询需求,而CR树是其优秀的变体之一。针对CR树的上溢结点分裂算法存在的聚类结果不理想以及计算代价过高等问题,提出一种主元分析导向的增量式k均值算法,可在既有分类中心附近的第一主元方向上搜索新的初始分类中心。将该算法与Silhouette指标相结合应用于求解由上溢结点分裂问题所转化的点集聚类问题,能以较小的计算代价自适应获取近似全局最优的点集聚类结果。试验结果表明,基于增量式聚类的R树上溢结点分裂算法在R树构建效率、存储利用率及空间查询等方面的综合性能优于CR树与RR*树。

关键词: R树, 动态空间索引, 上溢结点分裂, 增量式k均值算法, 主元分析

Abstract: R-tree is suitable for maintaining dynamic data and spatial query in many areas such as reverse engineering, CAD/CAM and machine vision, while CR-tree is an excellent variant of R-tree. Aiming at the deficiency in clustering result and compute cost for overflow nodes splitting algorithm of CR-tree, an incremental k-means algorithm via principal components analysis (PCA) is proposed, which can search the new cluster center along the first principal component directions in present clusters. Combining with Silhouette indicator, the algorithm is applied to solving the problem of point set clustering, which is converted from the problem of overflow nodes Splittin. Consequently the clustering results nearly global optimal can be obtained quickly. The experimental results show that the R-tree built with the algorithm based on incremental clustering is better than CR-tree and RR*-tree in synthetic performance in aspects such as the efficiency of building R-tree, storage utilization and spatial query.

Key words: dynamic spatial index, incremental k-means, overflow nodes splitting, principal components analysis, R-tree

中图分类号: