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

来源：机械工程学报杂志2015年第19期北京时间：

作者：李延瑞, 孙殿柱, 张英杰, 聂乐魁

单位：1.西安交通大学机械工程学院;2.山东理工大学机械工程学院

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

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

基金资助：国家自然科学基金资助项目(51075247)