基于改进聚类的hilbertr树空间索引算法研究

《基于改进聚类的hilbertr树空间索引算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、河南大学硕士学位论文基于改进聚类的HilbertR树空间索引算法研究姓名：王宝祥申请学位级别：硕士专业：应用数学指导教师：张连堂2011-05摘要随着信息社会的快速发展，地理信息系统(GIS)和空间数据库被广泛应用于水利、环境、测量、交通、海洋、土地、区域规划等领域。空间索引技术作为GIS和空间数据库的关键性技术，现已成为当前相关领域中极为重要的研究课题。针对空间数据的日益海量化及其自身复杂性等特点，进行合理的数据组织并建立与之相适应的高效的空间索引，已成为满足人们不断提高数据检索和查询要求的重要途径和方法。首先，本文在研究空间数据库

2、和空间索引技术相关理论的基础上，对当前在空间索引技术中被广泛应用的经典算法进行了分析和对比，研究其优势和不足，并探讨空间索引技术的优化和改进方向。其次，为在聚类分析的基础上建立高效的空间索引，鉴于传统k均值聚类算法在某些领域应用中所显现出来的局限和性能的不足，在传统算法的基础上提出一种改进的k均值聚类算法。该算法具有自适应地确定聚类数量和聚类中心的特点，它采用最大距离法选取合理的聚类中心，依据有效的评估准则来确定较理想的聚类个数，使得聚类数k的值选定更合理、聚类结果更加稳定，特别适用于对空间数据的聚类。最后，鉴于大多数实际问题中空间对

3、象通常分布不均匀的客观现实，若直接建立HilbertR树索引，部分叶结点面积较大，易产生大量重叠，导致多路查询而影响检索效率。为了在对该类对象的处理中取得更好的实际效果，本文尝试将前述改进的k均值聚类算法与HilbertR树算法相融合，在HilbertR树索引的建立过程中引入改进的k均值算法的理念，提出了基于改进k均值聚类的HilbertR树索引算法。算法的改进思路是建树前先对分布不均的空间对象进行有效聚类，并在聚类基础上对数据进行合理组织，根据相关规则生成叶结点和中间结点，继而建立高效的HilbertR树。该算法实现了对分布稠密和稀

4、疏空间对象的分置处理，使得叶结点面积更小、分配更合理，有效解决相邻数据的聚类存放，较大程度上减少了中间结点之间的重叠，最终提高了索引的性能。关键词：空间数据，空间索引，聚类，HilbertR树IABSTRACTWiththedevelopmentofinformationsociety,GeographicInformationSystem(GIS)andspatialdatabasearewidelyusedinwater,evironment,traffic,ocean,land,regionalplanningandsoon.A

5、sthekeytechnologyofGISandspatialdatabase,spatialindexstructurehasnowalreadybecometheveryimportantresearchtopicintheinterelatedfieldsatpresent.Duetothemassiveincreaseofspatialdataandcomplexityofitself,ithasbecometheimportantmethodtosatisfytheneedsofconstantlyincreaseddat

6、aindexingandqueryingbyreasonabledataorgnizationandconstructingthehighefficientspatialindexstructure,whichissuitablefororganization.Firstly,basedontheconcerningtheoryofresearchesonthespatialdatabaseandspatialindextechnology,bythecomparisonandanalysisamongthewidelyusedand

7、classicalgorithmsinthecurrentspatialindexstructure,thepaperdoesresearchesontheadvantagesanddeficienciesofthosealgorithmsandmakesdiscussionaboutdirectionofimprovementanddesigningideasofappliedalgorithmsinspatialindex.Secondly,accordingtothelimitationsanddeficienciesofper

8、formanceintraditionalK-meansclusteringalgorithmsappliedinsomefields,animprovedK-meansclusteringalgorithmwhichc