基于改进GMM聚类算法的Hilbert-R树构建方法研究

《基于改进GMM聚类算法的Hilbert-R树构建方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、：分类号：密级ＵＤＣ：编号：工程硕士学位论文基于改进ＧＭＭ聚类算法的Ｈ－ｉｌｂｅｒｔＲ树构建方法研究硕士研究生：姜子扬指导教师：张健沛教授企业导师：殷志伟高级工程师工程领域：计算机技术哈尔滨工程大学２０１８年５月分类号：密级：UDC：编号：专业硕士学位论文（工程硕士）基于改进GMM聚类算法的Hilbert-R树构建方法研究硕士研究生：姜子扬指导教师：张健沛教授企业导师：殷志伟高级工程师学位级别：工程硕士工程领域：计算机技术所在单位：黑龙江省交通信息中心论文答辩日期：2018年5月31日学位授予单位：哈尔滨工程

2、大学ClassifiedIndex:U.D.C:ADissertationfortheDegreeofM.EngBasedonimprovedGMMclusteringalgorithmResearchontheconstructionmethodofHilbert-RtreeCandidate:JiangZiYangSupervisor:Prof.ZhangJianPeiBusinessSupervisor:SeniorengineerYinZhiweiAcademicDegreeAppliedfor:MasterofEngineeringSpeci

3、alty:ComputerTechnologyDateofSubmission:Mar.23,2017DateofOralExamination:June.4,2017University:HarbinEngineeringUniversity摘要随着地理信息系统的快速发展，空间数据库在很多应用领域得到了发挥。空间数据具有复杂性、多样性、海量性等特征，基于B树的传统关系型数据库不能实现良好的存储和快速访问。因此，空间索引技术应运而生。如何能够实现良好的索引结构和减少冗余查询路径是当前空间数据库的研究热点和难点问题之一。R树是一种空间索引结构，用最小外包

4、矩形近似表示空间数据，能够对空间数据进行有效的存储和访问。Hilbert-R树是R树的变体之一，采用分形几何技术，对空间多维数据进行降维操作，减少计算量，达到快速构建索引的目的。但是Hilbert-R树中的数据经映射后，原本物理空间中邻近的对象可能不在一个叶子节点中，在最近邻查询时会出现误差或冗余路径，降低索引质量和效率。针对现有传统和改进的空间索引的不足，本文主要分以下三个方面进行研究：1、针对Hilbert-R树映射后物理空间邻近数据点可能不在一个节点的不足，首先采用聚类算法GMM(高斯混合模型)对空间数据进行预处理，GMM能够实现簇内数据相似性高

5、，簇间数据相似性低，使得邻近的数据在同一个叶子节点中。而且，由于节点间相似性低，从而降低MBR(Minimumboundingrectangle)的重叠度，提高索引效率。2、针对GMM算法中存在任意初始值和局部最优解的不足，提出利用层次聚类算法CURE对数据进行划分操作，经迭代数层后得到数据的期望和方差。此时的期望和方差由于不再具有任意性，可作为GMM算法的初始值，避免噪声点或离群点对簇的影响，提高聚类质量，进而使节点内数据分布更加紧凑，提高查询效率。采用蜂群算法弥补局部最优的不足，提升整个Hilbert-R树索引结构质量。3、针对现有空间不确定数据构

6、建索引的不足，利用基于改进的GMM算法生成Hilbert-R树，减少积分运算量。同时，由于采用自底向上的静态批处理方式，使得整个Hilbert-R树除根节点以外的数据都是满容量的，提高索引的空间利用率。良好的索引最终目的是有效的查询，因此本文提出聚类和Voronoi图相结合的方式，裁剪不确定数据，降低查找对象的时间，提高索引效率。关键字：空间数据库；Hilbert-R树；GMM算法；CURE；Voronoi图；不确定数据。IABSTRACTWiththerapiddevelopmentofgeo-informationsystem,spatialdat

7、abasehasplayedanimportantroleinmanyareas.Asspatialdatabearscharacteristicsofcomplexity,diversityandmagnanimity,thetraditionalrelationaldatabasebasedonBtreecannotachievegoodstorageandquickaccess.Thus,spatialindextechnologyemergesasthetimesrequire.Oneofthehotandtoughissuesinthecur

8、rentspatialdatabaseresearchishowtoachieveagoodi