学位论文 > 优秀研究生学位论文题录展示

基于最小包围盒及自适应聚类的三维R~*-树索引结构

作　者: 孙永伟
导　师: 孙殿柱
学　校: 山东理工大学
专　业: 机械电子工程
关键词: 逆向工程 R*OA-树 R*-树最小包围盒结点分裂 k-均值自适应聚类分簇间隙统计法
分类号: TP311.12
类　型: 硕士论文
年　份: 2011年
下　载: 29次
引　用: 0次
阅　读: 论文下载

内容摘要

针对目前逆向工程中索引结构在进行空间数据存储、管理和查询时存在的自适应性差、空间利用率低等问题,提出一种基于最小包围盒及自适应聚类分簇的三维R*-树索引结构(R*OA-树),该索引结构根据不同点云分布特点将其分为正态分布点云和非正态分布点云,分别采用主元分析算法和最小二乘圆柱拟合算法构建散乱点云最小包围盒,基于最小包围盒获取数据局部坐标系,并在局部坐标下建立索引结点轴向包围盒,有效提高了索引结点空间利用率,降低了结点间重合度；同时基于间隙统计法获取结点分裂最佳簇数,采用k-均值算法实现最佳簇数下结点分裂,实现R*OA-树的结点自适应聚类分簇,提高了结点分裂质量及自适应性。本课题提出一种高效稳定的空间索引结构R*OA-树,以满足逆向工程领域对数据的空间存储、管理和查询需要,主要研究内容及成果如下：1.针对目前间隙统计法获取最佳聚类簇数时存在的计算繁琐、运行效率低等问题,对传统间隙统计法进行了优化,提出了间隙量计算的数学表达式,解决了以往根据随机采样获取参考数据带来的计算误差,提高了基于间隙统计法获取聚类最佳簇数的精度；同时简化了间隙统计算法计算步骤,提高了获取最佳聚类次数的效率。2.针对目前结点分裂过程中存在的参数依赖性强等问题,提出了结点自适应聚类分簇算法,基于聚类评价函数及间隙统计函数获取最佳聚类簇数,采用k-均值算法进行最佳聚类簇数下的结点分裂,实现结点自适应聚类分簇,降低了聚类的参数依赖性,解决了用户设置簇数与最佳簇数不一致所造成的聚类质量下降,并能有效防止聚类陷入局部最优。3.针对目前R*-树结点重合度高、空间利用率低等问题,提出整体最小包围盒、局部轴向包围盒的R*OA-树构建算法,根据点云集合分布状态,将其划分为正态分布和非正态分布两类数据,分别采用主元分析和最小二乘圆柱拟合算法计算最小包围盒,并基于最小包围盒获取点集局部坐标系,进而实现局部坐标系下的R*OA-树构建。本课题通过对R*-树索引结构结点分裂、全局优化等步骤进行优化研究,形成了新的索引结构R*OA-树,基于该索引结构可有效提高各类数据的空间查询效率及其在逆向工程领域的适用性。

全文目录

摘要  3-4
ABSTRACT  4-5
目录  5-7
第一章绪论  7-12
  1.1 课题研究意义  7
  1.2 索引结构研究现状  7-10
  1.3 存在问题  10-11
  1.4 本文研究方案  11-12
第二章最小包围盒求解  12-22
  2.1 引言  12
  2.2 正态分布数据最小包围盒  12-17
    2.2.1 建立初始坐标系  13
    2.2.2 旋转初始坐标系  13-14
    2.2.3 求解最小包围盒  14-15
    2.2.4 时间复杂度分析  15
    2.2.5 应用实例  15-17
  2.3 非正态分布数据最小包围盒  17-20
    2.3.1 建立初始坐标系  18
    2.3.2 旋转初始坐标系  18-19
    2.3.3 求解最小包围盒  19
    2.3.4 时间复杂度分析  19
    2.3.5 应用实例  19-20
  2.4 结论  20-22
第三章结点轴向包围盒自适应聚类分簇  22-46
  3.1 结点的轴向包围盒表示  23
  3.2 结点相似度  23-24
  3.3 聚类分簇的概念  24-27
    3.3.1 聚类的概念  24
    3.3.2 聚类方法的分类  24
    3.3.3 k-均值聚类分簇  24-27
  3.4 结点自适应聚类分簇  27-42
    3.4.1 聚类总体相似度  28-29
    3.4.2 间隙统计法  29-33
    3.4.3 间隙统计法的优化  33-38
    3.4.4 结点自适应聚类  38-42
  3.5 时间复杂度分析  42
  3.6 应用实例  42-45
  3.7 结论  45-46
第四章 R*OA-树的构建及基本运算  46-57
  4.1 R*OA-树空间索引基本概念  46-49
    4.1.1 轴向包围盒(MBR,Minimum Bounding Rectangle)  46-47
    4.1.2 R*OA-树的定义  47-49
  4.2 R*OA-树的构建  49-51
    4.2.1 局部坐标系的建立  49-50
    4.2.2 R*OA-树构建流程  50-51
  4.3 R*OA-树的基本算法  51-54
    4.3.1 结点查询  51
    4.3.2 结点插入  51-52
    4.3.3 结点调整  52
    4.3.4 结点自适应聚类分簇  52
    4.3.5 结点强制重新插入  52
    4.3.6 结点删除  52-53
    4.3.7 全局优化  53-54
  4.4 时间复杂度分析  54
  4.5 应用实例  54-56
  4.6 总结  56-57
第五章全文总结与展望  57-59
  5.1 总结  57
  5.2 展望  57-59
参考文献  59-63
攻读硕士学位期间的科研成果  63-65
致谢  65

基于最小包围盒及自适应聚类的三维R~*-树索引结构

内容摘要

全文目录

相似论文