一种基于kd－tree的同位模式挖掘算法研究

《一种基于kd－tree的同位模式挖掘算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、计算机光盘软件与应用2010年第8期ComputerCDSoftwareandApplications工程技术一种基于KD—Tree的同位模式挖掘算法研究谭浩，张修如，孙博雅(中南大学信息科学与工程学院，长沙410075)摘要：空间同位模式挖掘是空间数据挖掘中一种重要的方法。空间同位模式是指在地理空间中，由于空间接近性而频繁的聚集在一起的空间特征的集合。提出了一种基于KD树的同位模式挖掘算法，算法可以分为两个基本步骤：邻域的确认和同位模式的剪枝过程。最后通过实验表明了算法的准确性与全面性。关键词：空间数据

2、挖掘；空间同位模式；KD树中图分类号：TP392文献标识码：A文章鳊号：1007—9599(2010)08-0111_o3Co-locationPatternMiningAlgorithmStudyBasedonKD-TreeTanHaoZhangXiuruSunBoya(InformationScience＆EngineeringCollege，CentralSouthUniversity，Changsha410075，China)Abstract：Co—locationpatternsminingis

3、animportantspatialdataminingmethod．Co—locationpatternsisdefinedgeographicspace，becauseofthespaceclosetonatureandfrequenttogetherasacollectionofspatialfeatures．KD—treebasedonthesamebitpatternminingalgorithm，thealgorithmcanbedividedintotwobasicsteps：Recogni

4、zedneighborhoodandpruningprocessofCO—locationpatmm．Theexperimentsshowthealgorithmaccuracyandcomprehensiveness．Keywords：Spatialdatamining；SpatialCO—locationpattern；KD—tree一、引言分子是f．的行实例在所有搜索到的行实例中出现次数，分母空间数据挖掘或者称为从空间数据库中发现知识，是数据挖是f；的所有实例数。式中乃是一个映射操作符，功能是去除重

5、复掘在空间数据库中的应用。这是发现和挖掘我们所感兴趣的或出现的实例。者说对我们有用的，但之前未知的知识的一个过程。由于空间数定义4参与索引据的复杂性和空间自相关性，从空间数据库中提取我们感兴趣的参与索引是空间同位模式挖掘中一个重要参数，用pi(c)知识模式比从传统数据库中提取相关知识模式更为复杂。表示。算式表示为：空间同位模式挖掘是当今空间数据挖掘研究的热点问题之pi(c)：m'lk1pr(c，)(2)一。空间同位是指在空间特征上其空间属性或非空间相近或相同引理1的空间对象。空间同位模式则是一些布尔型空间

6、特征的集合，这如果存在同位模式C和C，满足条件CcC且VfcNC些空间特征的实例频繁的聚集在同一邻域中。在二维或者三维则有下面不等式成立：空间中，不同位置的地理空间对象存在与否即是用布尔型空间特Pr(C，fi)≥pr(C，fi)(3)征来描述。在很多实际应用中，空间同位模式挖掘正发挥着越来Pi(C)≥p(C’)(4)越重要的作用。由此，空间同位模式挖掘可以以这样的形式描述：二、空间同位模式挖掘算法给定：k个布尔型空间特征的集合F={f，⋯，fk)以及他们空间同位模式挖掘是空间数据挖掘的一种重要方法，研究者

7、的实例集S=(i，⋯i)；将空间同位模式定义为：由于空间接近性而频繁的聚集在一起的(1)针对特定应用而设定的邻域关系R；空间特征的集合。。(2)最小普遍性度量值：minprey(即参与索引阀值)，以空间同位模式是指在地理空间中，布尔空间特征的实例频繁及最小条件概率阀值：mincond~rob。的聚集在一起。在这一部分中，我们主要介绍了一些基本的概念。_寻求：正确而全面的同位规则必须满足：以下首先给出几个重要的定义。(1)Pi(C)≥min_prev：定义1R-邻近关系(2)condAorod~mincon

8、dprob：给定一个布尔空间特征的集合F=(f，⋯，fk)及其实例集s。—约束条件：R一邻近关系这样定义：在邻域关系R下形成的区域内实例集I，(I)R是基于邻近关系的米制距离关系；其中I_cS，R邻域关系是基于其所应用的领域而定义，依据算法(2)在满足给定门槛阀值的基础上，正确有效的挖掘所有同的输入而定。同位模式C是布尔型空间特征的子集，有C_CF。以位规则；上涉及的邻域关系R包含三种：空间关系，距离关系，或二者的结(3)空间