挖掘空间关联规则的前缀树算法设计与实现

《挖掘空间关联规则的前缀树算法设计与实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据第8卷(A版j第4期中国图象图形学报Vol·8(A)，No·42003年4月JournalofImageandGraphicsApr·2003挖掘空间关联规则的前缀树算法设计与实现刘君强”’“潘云鹤(浙江大学人工智能研究所．杭州310027)2’(杭州商学院计算机信息工程学院，杭州310035)摘要空间关联规则挖掘是在空间数据库中进行知识发现的一类重要问题．为此提出了挖掘空间关联规则的二阶段策略．通过多轮次单层布尔型关联规则挖掘，自顶向下逐步细化空间谓词的粒度．从而空间谓词的计算量大大减少．同时

2、，设计了一种基于前缀树的单层布尔型关联规则挖掘算法(FPTGenerate)，不需要反复扫描数据库，不产生候选模式集，并在关键优化技术上取得了突破．实验表明，以FPJr—Generate为挖掘引擎的空间关联规则发现系统的时间效率与空间可伸缩性远远优于以经典算法Apriori为引擎的系统．关键词数据库(520·4050)海量数据库空间数据挖掘地理信息系统空间关联规则中图法分类号：TP301．6TPl8文献标识码：A文章编号：1006—8961(2003)04—0476—05DesignandImpleme

3、ntationofFIPT—BasedSpatialAssociationRulesMiningAlgorithmI。1uJunqiang””-PANYun—he””(1nstitzaeofArtiflctalIntelligence，ZhejtangUniversity，Hangzhou310027)(sf^胛f¨，ComputerInformationEngineering，HangzhouUniv扩sityn，C蜊merce，Hangzhou310035)AbstractSpatialassoci

4、ationrulediscoveryinspatialdatabasesisaveryimportantdataminingtask．Inthispaper，atwo—stagestrategyforthediscoveryofspatialassociationrulesingeographicaldatabasesisproposed-Thespatialcomputationaloverheadisgreatlyreducedbytopdownrefinementofspatialpredicat

5、egranularitiesandmultiplerecursionsofsinglelevelbooleanassociationrulediscoverystep，whichisthekeystepofthealgorithm．Thesinglelevelbooleanassociationruleminingalgorithm，FPT—Generate．isdetailed．FPT—Generateusesthefrequentitemprefixtree。F1PT，tocompressandpr

6、ojectfrequentitemsets．anddiscoversassociationrulesbygrowingafrequentpatterntree。FPT，bydepthfirstsearch．ThealgorithmFPT—Generategeneratesassociationruleswithoutcandidategenerationandwithoutredundantscansofdatabases．Optimizingtechniquesfortheimplementation

7、，suchaspseudoprojectingandpruning，dynamicthreadingandhashing，anddiskbasedpartitioning．arealsodiscussed．ExperimentsshowthatspatialassociationdiscoverysystemspoweredbyFPTGeneratearemuchmoretimeefficientandspacescalablethanthosepoweredbytheclassicalalgorith

8、m，Apriori．Finally．aspatialassociationrulediscoverysystem，SmartMiner-uponthesupportofMaplnfoProfessional·isdeveloped．KeywordsDatabase，Verylargedatabases，Spatialdatamining．GIS，Spatialassociationrules0引言随着遥感技术和自动数据采集技术的广泛应用，特