通用关联规则挖掘框架的设计与实现

地理空间信息GEOSPATIALINFORMATION2015年8月第13卷第4期Aug.,2015Vol.13,No.4doi:10.3969/j.issn.1672-4623.2015.04.收稿日期：2014-07-23。项目来源：国家自然科学基金资助项目（41171313）;苏州市科技计划2013年应用基础研究计划资助项目（SYG201319）。通用关联规则挖掘框架的设计与实现董 林1，舒 红1（1.武汉大学测绘遥感信息工程国家重点实验室，湖北武汉430079）摘 要：对适用于多种数据类型的关联规则挖掘框架进行了研究。从概率论出发讨论了支持度计算问题，提出利用有限测度计算项集支持度的方法，分析了Apriori性质的本质，提出通用关联规则挖掘算法的设计思路。在此基础上，设计并实现了通用关联规则挖掘框架，使用该框架进行了事务、空间和时空数据的挖掘实验，验证了其可行性、通用性及正确性。关键词：关联规则；空间关联规则；时空关联规则；支持度；测度；通用框架中图分类号：P208文献标志码：B文章编号：1672-4623（2015）04-0068-04025关联规则挖掘是一种用于分析事物和现象之间内在联系的数据挖掘方法，挖掘的对象可以是数据库或数据仓库中的事务数据[1]，也可以是空间、时态或时空数据[2-4]，随着研究与应用的发展，更多种类的数据将成为关联规则挖掘的对象。多样化的数据带来了对多样化挖掘算法的需求，研究适用于多种数据类型的算法框架对加速新算法的设计与实现有重要意义。为此，提出一种通用关联规则挖掘框架GARMF（generalassociationruleminingframework）。1 理论基础要设计适用于多种数据类型的通用挖掘框架，必须解决2个问题：①将针对不同数据类型的项集支持度计算方法纳入统一框架；②找出通用的关联规则挖掘算法。关联规则挖掘是从数据中提取频繁模式（频繁项集和关联规则）的过程，模式频繁与否是根据其支持度（即对应事件发生的概率）进行判断的，因此支持度计算是关联规则挖掘中最重要的操作。同时，关联规则挖掘是一种复杂度较高的计算。为了确保挖掘效率，必须选用合理的挖掘算法。以概率论为基础，GARMF利用有限测度之比以及经典Apriori算法的框架来解决这2个问题，下面对其原理进行介绍。1.1 基本概念定义1σ域。由非空集合X的一些子集组成的集合称为X上的集合系。满足以下3个条件的集合系F称为σ域（也称作σ代数）：1）X∈F；2）A∈F⇒Ac∈F；3）An∈F，n=1，2，…⇒'∞n=1An∈F。定义2测度。设E是X上的集合系且∅∈E，如果E上的非负集函数μ有可列可加性且有μ（∅）=0，则称之为E上的（σ可加）测度（measure）。称（X，F，μ）为测度空间，其中X是一个给定的非空集合，F是X上的σ域，μ是F上的测度。定义3概率。对于测度空间（X，F，P），如果P（X）=1，则可以称之为概率空间，称P为概率测度，称集合A∈F为事件A，称P（A）为事件A发生的概率。若X是一个有限集，F是X的幂集（是σ域），定义P（A）=A/X（即A的势与X的势之比），则（X，F，P）是在初等概率论中称为古典概型的概率空间[5]。定义4项集。对于有限集I={i1，i2，…，in}，称其中每个元素为一个项，称2I中的元素为项集，称包含n个项的项集为n-项集。称一个非空点集Ω为基本事件空间。给定一个映射f：I2Ω，对于任意项A∈I，称f（i）为i的对应事件。例如，对于事务数据来说，基本事件空间Ω是用所有事务记录的集合，一个项的对应事件即其对应字段取真值的事务记录的集合。对任意项集A={a1，a2，…，am}（A⊂I），称Ae=(i=1mf（ai）为其对应事件，称P（Ae）为其支持度。定义5关联规则。用A，B⊂I（A(B=∅）组成的蕴含式A⇒B来表述条件概率P（Be|Ae），称这个蕴含式为关联规则，称这个条件概率为该规则的置信度。称A'B为规则对应的项集，那么Be(Ae就是规则对应的事件，P（Be(Ae）就是规则的支持度。1.2 支持度是有限测度之比基于事务表的关联规则挖掘算法大多是利用古典概型的概率公式计算支持度的。对于一个由m条事务记录组成的事务表，如果满足某项集的事务有m条，则该项集的支持度为m/n[2]。这是目前占主导地位的支持度计算方法。一些文献采取了基于几何概型的计算·69·第13卷第4期方法[6-9]，例如Estivill-Castro[7]利用面积之比来计算支持度：假设满足某项集的区域面积为a，研究区域总面积为A，则该项集的支持度为a/A。虽然两种方法有区别，但本质上又是相同的：计算的都是项集对应事件的概率，并且这个概率都是用一个除式得到的。基于古典概型的计算方法使用的是总事务数n和满足项集的事务数m，它们的本质是计数测度，这是一个有限测度；在基于几何概型的计算方法中，研究区域总面积A和满足某项集的区域的面积a，本质上是面积测度，同样是有限测度。显然，这两种方法实际上是用有限测度的比值来计算项集的支持度。对于基本事件空间Ω，假设存在定义于2Ω上的有限测度m，则任意项集A的支持度（即其对应事件Ae∈2Ω的概率，）可以用如下公式计算：support()()()()APAmmAeeX==(1)m（Ω）/m（Ω）=1，由此可知：1）m/m（Ω）是一个定义在2Ω上的概率测度；2）m（Ae）/m（Ω）可称作事件Ae的概率；3）m（Ae）/m（Ω）作为A的支持度是合理的。式中，m（Ω）为数据总量；m（Ae）为项集A的支持度计数；项集的支持度等于其支持度计数与数据总量之比。对于任意一类描述事件域内一组事件的数据，只要能找到可计算的有限测度m，就可对其进行关联规则挖掘。1.3 Apriori性质的本质绝大多数关联规则挖掘算法会利用Apriori性质来提高挖掘效率。所谓Apriori性质，即任意频繁项集的子集必然是频繁的，或者说，任意项集的支持度不低于其超集的支持度。从概率论的角度来看，对于任意项集A、B（A，B⊂I），如果A⊂B则Be⊂Ae，那么对于任意概率测度P都有P（Be）≤P（Ae）。显然，Apriori性质的本质是概率测度的非负性和可列可加性，是支持度固有的数学性质，而不是由事务数据的逻辑或存储结构带来的。因此，基于Apriori性质的经典Apriori算法[10]虽然是针对事务数据设计的，但将具体的支持度计算操作（即遍历事务表）抽象为一般的支持度计算操作，就可以得到一个通用于各种数据类型的关联规则挖掘算法。2 框架的设计与实现2.1  GARMF的架构关联规则挖掘主要涉及数据、算法和挖掘结果这3类要素，GARMF将它们抽象为数据类、通用挖掘算法类和挖掘结果类，如图1所示。㭞㈾#䇱㻿⥃Ⱙm:2Ą-R+ェ㰄㭞㈾䓽㑠m(Ą)+ェ㰄A⭥䐈⧷Ⱙェ㭞m(A)+㼏⭞㬣ミ⭥䇔㪅f:I-2Ą㵉䇤㵻㉓㰄ⳉ+㵻㉓㠖Ⳓ㼏ゐ+㪛⧪㣠⹹㑋⺇䋓㵻㉓ㆂ⺜+㠖Ⳓ㼏ゐ+㣠⹹㑋⺇䋓ⰵ㼔Ⳟⳉ㚠⭥图1 GARMF架构图1）数据类。数据类是对可以用于关联规则挖掘的数据的抽象。不论挖掘对象为何种类型的数据，不论采用何种挖掘算法，用于关联规则挖掘的数据总是描述项的对应事件的数据，项集的支持度也总是利用有限测度m来计算。2）通用挖掘算法类。现有的关联规则挖掘算法大都是针对某些具体的数据类型设计的，集成了访问数据计算支持度的操作。在GARMF框架中，这一操作则由数据类负责，这使得挖掘算法与具体的数据类型相对独立，具有较强的通用性。3）挖掘结果类。挖掘结果类的功能是存储频繁项集和关联规则。之所以还要保存频繁项集是因为一些应用所需的是频繁项集，并且很多评价方法和增量挖掘算法要用到频繁项集（及其支持度）。2.2 GARMF的实现本文将GARMF框架实现了一个Java类库（称作GARMF类库），该类库核心的3个类如图2所示。DataDefaultAprioriAssociationRules11图2 GARMF类库的核心类1）数据类（Data）。使用抽象类Data来表述可用于关联规则挖掘的数据（如图3所示）。Data类最重要的3个属性是miner、recordCount和items，分别为关联规则挖掘算法、数据总量以及项集到对应数据的映射；最重要的2个方法是mine和getSupportCount，即进行关联规则挖掘和获取指定项集的支持度计数。需要指出的是，虽然数据总量和支持度计数实际上是用同一个有限测度求出的，但对于一组数据其总量是恒定的，只需要求一次，而要计算支持度计数的项集则有很多个，因此数据总量recordCount被作为属性来处董 林等：通用关联规则挖掘框架的设计与实现地理空间信息·70·第13卷第4期理，getSupportCount则是作为方法。2）挖掘结果（AssociationRules）。使用AssociationRules类来存储挖掘结果，包括挖掘所使用的最小支持度和置信度阈值、挖掘得到的频繁项集和关联规则。挖掘阈值对挖掘结果的影响很大，并且是进行增量式挖掘的必要信息。3）通用挖掘算法（DefaultApriori）。将Apriori算法[10]的核心抽取出来，得到了通用关联规则挖掘算法DefaultApriori。该算法的输入为Data对象，输出为AssociationRules对象，与具体的数据类型无关。需要指出，该算法输入的Data对象负责数据总量及支持度的计算。Data类是一个抽象类，应当根据具体的数据类型创建其实例，主要工作就是实现用于计算数据总量和支持度计数的有限测度。为了便于使用，还实现了一些用于挖掘结果查看和持久化的类，并针对一些常用数据类型设计了Data的子类（部分见图3），包括基于文件的/基于数据库的/加权/模糊事务数据、空间数据（矢量/栅格）以及时空数据（快照序列）。这些虽然不是核心类，但对GARMF类库的实用性有重要意义。TransactionDataSpatialDataFeatureDataRasterDataSpatiotemporalData#miner:Algorithm+recordCount:double+items+mine(..):AssociationRules+getSupportCount(Itemsetiset):doubleData图3 GARMF类库中的数据类3 实验验证用GARMF对事务数据、栅格数据、矢量数据以及快照序列数据进行关联规则挖掘实验以检验其可行性与正确性。为了便于对比分析，本文使用与文献[11]相同的实验数据。该类库以及实验数据均可在作者网站下载（含API文档，完成软件著作权登记后将开放全部开源代码）。3.1 数据准备本文实验所使用的是美国地质调查局（USGS）覆被变化趋势项目网站（）上提供的威拉米特河谷生态区（WillametteValleyEcoregion）第3号样本区（图4）的覆被序列数据，由5幅大小为167×167像素、分辨率为60m的栅格格式的覆被分类图组成，分别对应于该样本区1972、1979、1985、1992和2000年的覆被状态。数据涉及的覆被类型及它们在各个时期的状况见表1。图4 威拉米特谷生态区第3号样本区的地理位置[11]表1 数据涉及的覆被类型及出现情况像素值覆被类型（简记）颜色197219791985199220001Water(WT)蓝√√√√√2Developed/Urban(DU)红√√√√√3Mechanicallydisturbed(MD)品红---√√4Mining(MN)黑√√√√√5Naturalbarren(NB)灰√√√√√6Forest/Woodland(FW)绿√√√√√7Grassland/Shrubland(GS)黄----√8Agriculture(AG)橙√√√√√9Wetlands(WL)青√√√√√要进行关联规则挖掘，必须先选定项的集合。本文以时间与覆被类型的组合作为项，例如“19