R树上溢结点分裂问题的增量式聚类优化求解方法

摘要

本发明针对R树上溢结点的分裂算法存在的聚类结果不理想以及计算代价过高等问题，提出一种R树上溢结点分裂问题的增量式聚类优化求解方法，属于产品逆向工程技术领域。该方法采用主元分析导向的增量式k均值算法，可在既有分类中心附近的第一主元方向上搜索新的初始分类中心，将该算法与Silhouette指标相结合应用于求解由上溢结点分裂问题所转化的点集聚类问题，能以较小的计算代价自适应获取近似全局最优的点集聚类结果。基于增量式聚类的R树上溢结点分裂算法在R树构建效率、存储利用率及空间查询等方面的综合性能优于现有技术。

主权项

一种R树上溢结点分裂问题的增量式聚类优化求解方法，其特征在于步骤依次为：(1) 设上溢结点为E，M为R树结点所容许的子结点数上限值，将E的子结点集转化为点集P=，，计算公式为：其中表示的任一子结点e的包围盒，表示包围盒的中心点； (2) 结合E所在父结点的子结点数和M值确定聚类过程中的分类个数的上限值K；(3) 初始化：循环次数，最初的单一分类，初始聚类结果集合，分类归属记录，分类的中心，分类中心集合，其中表示计算点集的中心；(4) 采用主元分析导向的增量式k均值算法获取点集P第k+1次聚类结果；(5) 设表示第k次聚类结果的Silhouette指标值，若，跳转至(8)，否则；(6)；(7) 重复(4)至(6)，直至；(8) 根据步骤(1)中确定的子结点集P与E的双射关系以及中记录的中各点分类归属，对E的子结点进行划分，将所得结果作为E的分裂结果。