基于有序树的时空关联规则数据挖掘的应用

杨井荣，柳 军

(成都理工大学 工程技术学院，四川 乐山 614007)

0 引 言

目前Apriori算法仍是具有影响力的典型数据挖掘算法，在文献[1]中全面化、系统化、深入化地介绍了该算法，Apriori算法中的两个设计缺陷被发现，这两个缺陷都是与性能效率有关。在算法执行过程中，对于事务数据库的多次读取写入操作，内外存之间频繁进行数据交互导致执行效率大大降低；在算法的中间阶段，候选项集的大量产生，算法的中间过程过于庞大，无论时间消耗是空间消耗都是巨大的。

针对Apriori算法存在的性能问题，研究人员纷纷提出了改进算法。在众多改进算法中，如文献[2]介绍的Partition算法，影响算法的执行效率的关键是如何设定划分后的阈值；文献[3]介绍的Hash算法，影响算法空间效率在于需要建立Hash表；文献[4]介绍的FP-tree(频繁增长模式树)算法，影响算法效率在于存储空间的限制，因为频繁模式增长树的生成随着数据库规模的增大而增大；另外，文献[5]中还介绍了压缩数据的改进算法，算法的依据是按频繁项集的先验性质。

1 关联规则数据挖掘概念及原理

1.1 关联规则

设I={i1,i2,…,im}是一个属性(字段)集合，事务数据库D={t1,t2,…,tn}是一个集合，它的元素全部是集合，即关键字标识TID的集合，每个事务ti(i=1,2,…,n)是I中一组属性集合，即ti∈I，其所含属性个数称为事务长度。关联规则[6]在离散数学中，定义为X=>Y的蕴涵式，其中X⊆I，Y⊆I，X∩Y=∅。关联规则的蕴涵式X=>Y成立的条件有2个:

第一，它要具有支持度support(X=>Y)=count(X∪Y)/‖D‖，在定义中，‖D‖为集合D的基数。count(X)代表项集X在D中出现的次数。最小支持度的定义：由用户确定的一个百分比，即项集A的基数与集合D的基数的百分比，记作Minsupport(最小支持度)。

第二，它要具有置信度C=confidence(X=>Y)=P(Y|X)=P(X∪Y)/P(X)，这个等式的中心意思是在数据库D中包含Y元组的充分条件是包含X元组。根据上面的等式，引出最小置信度定义:由用户定义一个百分比，即同时包含蕴含式前后项的个数与只包含蕴含式前项的个数的百分比。在两个条件同时成立的关联规则中，不小于最小支持度和置信度阈值的规则记为强关联规则。

1.2 频繁项目集概念

进行关联规则挖掘之前，指定I为全局属性集，D为事务数据库。若属性集合L⊆I，L≠∅，L的支持度超过(可以等于)最小支持度，当support(L)≥Minsupport时，属性集合L称为频繁项集，记为Lk，表示k-项频繁集(文中遵照此约定)。

1.3 频繁项目集的理论推理及相关性质

性质1：一个属性集L是频繁的充分条件是它的所有超集(包括本集合)是频繁的属性集。

推理1：一个属性集L是非频繁的是属性集L的超集也是非频繁的充分条件。根据此条件，L不会不是频繁项集的元素，L的超集也不是频繁项集的元素。

性质2：如果可以删除Lk，则说明一个事务长度不大于k,此事务不会包含k-项频繁集。

1.4 经典Apriori算法设计思路

在文献[7]中，Apriori算法的思路如下:

步骤1:第一次扫描数据库，计算出所有支持度大于等于最小支持度的字段，所有这些字段形成的集合即频繁1-项集，构成一个数据表，记为L1。

步骤2(连接步):对于第一次扫描的结果构成数据表Lk-1时进行全自连接生成候选项集Ck(k≥2)。

步骤3(剪枝步):对候选项集数据表Ck(k≥2)，按照频繁项目集的相关性质和相关推理进行处理，删除掉不满足条件的项集，合并满足条件的子集。

步骤4:通过步骤3的处理生成频繁k-项集Lk。

步骤5:对于步骤2到步骤4进行循环操作，循环结束的条件是：不能产生频繁项集。

步骤6:通过上述1到5步生成的频繁项集来计算关联规则，根据具体的项目含义来判定出有决策力的强关联规则。

在此算法中，中间的循环部分，每次生成频繁集Lk都需要存储海量的候选项集Ck，空间效率低，并且不断地重复扫描数据库D，时间效率也不高，并且形成了巨大的输入输出负载。

2 时空数据挖掘主要挖掘任务

根据挖掘数据的研究现状，时空数据挖掘的挖掘任务或角度是根据时空数据的种类来分的。目前的挖掘主要集中在频繁模式挖掘、预测挖掘、分类挖掘和聚类挖掘。按图1把挖掘任务细分成子任务。

图1 时空数据的挖掘任务

文献[8]介绍了一种关联模式挖掘，挖掘时空关联规则是基于旋转的方法来进行多任务挖掘。文献[9]介绍了一种在时空域扩展应用的经典的Apriori算法。文献[10]介绍了一种关联规则STAR-Miner算法，针对特定项目随时间跨区域移动变换的时空数据，能够快速解决空间区域中不同区域大小的问题。在2009年，Leong等构造了一种动态分析的架构模式，主要应用在两个方面，一是用来挖掘两个相异区域间的相互作用模式，二是用来挖掘空间相同但时间却相异的频繁关联规则模式。夏英等在2011年对Apriori算法进行了改进，提出了一种STApriori算法，这个算法的长处主要是在分析时空数据时，能够把无关冗杂的数据全部过滤掉，在时空数据中应用非常有效，并对时空数据的空间关系、时间关系有效性进行了高效地分析。由于时空数据的变化性，在2016年李围成等着眼于挖掘出强的时空关联规则，在基于FP-tree的数据结构中，提出了一种时空关联规则算法，将时空数据运算在FP-tree上。时空关联规则在气候科学、神经科学、环境科学、精准农业、医疗保健、社交媒体、交通动态、太阳物理学等领域都有应用。

3 关联规则挖掘算法(canonical-order tree，CAN-tree)

3.1 算法衍生过程

Leung等人提出了一种基于树结构来改进关联规则的算法—CAN-tree(canonical-order tree)。该算法不再考虑候选项集，解决了FELINE和AFPIM所存在的弊端。CAN-tree的构建只需对数据库进行一次扫描，这一点与扫描两次数据库的FPTree算法完全不同。在CAN-tree中，项是按照一种序列排好序的，序列的设定，可以由用户在挖掘过程之前或者挖掘过程中根据实际情况进行设定。

3.2 CAN-tree的构建

首先，要对原始数据库的事务项构建树结构，构建过程描述如下：

(1)用户指定某一特定的自然序列(可以是自然序、字母序或者用户自己设定的序列)设计为一个项目头表。

(2)创建根节点root。

(3)扫描数据库，并将每一条事务的记录按照项目头表进行排序，接着对每一个数据项data进行树的节点插入操作，操作过程如步骤(4)。

(4)按照顺序结构访问与data同名节点的文件位置。当访问到data对应的已经建立的同名节点的父节点时，如果检查到与已经存在的事务中项data的前项名相同，计数器自加。如果不同，则创建一个新的节点newnode1，新节点newnode1的父节点应该与插入事务中的data项的前项名相同；返回步骤(4)，全部事务插入完成访问结束。

3.3 频繁项的挖掘过程

文中算法设置了一个项头数据表，与FP-Growth算法一样，该表中的关系模式(关系型)，第一包含基本实体信息，有关全部数据库项目的信息及其计数，第二还包含链接信息，指向CAN-tree中项目的第一个节点和最后一个节点的逻辑地址。为了可以从树中提取频繁模式，还附加了一个频繁项目列表，通过对表的访问实现频繁模式挖掘运算。按照算法的顺序结构，本算法的流程分为三步。按照顺序从前往后描述，第一步是从CAN-tree的项头表中选择符合最小支持度阈值的项目为初始频繁项目；第二步是对上一步得到的频繁项目排序，排序规则是按照访问计数升序排列，重新存储到频繁项目列表；第三步是从已有频繁项目列表的最不频繁(最小频繁数)的项目(首条记录)开始，在树中找到对应的第一个节点，目的是为了提取结束点为这个节点的频繁模式。在处理完第一个节点之后，包含相同项目的同级别节点被传入。算法的复杂性体现于，要对包含该项目的每个节点执行，挖掘过程重复进行。挖掘操作从树叶向树根进行，使用向上移动函数，提取出以当前项结束的频繁模式，挖掘操作从当前节点向根进行移动，每向上移动一次，树会增长，因为要将它们存储在条件模式列表中。并且还要对已经添加到条件模式列表中的以当前项目结束的频繁项目集构建新的CAN-tree，直到CAN-tree不再增长。

从上述算法的步骤可以看到，在执行CAN-tree子树时，按项集自己的特点能够插入树中的项目才是频繁的项目，这是该挖掘算法的优点，提高了挖掘效率，降低了时间复杂度。算法总的执行过程是按树的结构向树根部移动的过程中，函数(向上移动)会不断检查每个节点，以便判断这个节点是否存在于频繁项目列表中，也就是说，该项目达到频繁与否。为了检测新树中的频繁模式，重复执行挖掘算法。发现没有出现在频繁模式列表中的属性或属性集时，将当前项目追加到这些模式的表中。当前项目末尾的所有频繁模式都被添加到频繁模式列表中，这是结束挖掘的条件。

具体挖掘过程如下：

(1)从CAN-tree自下而上挖掘，首先找到最下面的item(项)，构建每个item(项)的条件模式基。顺着CAN-tree树，找出所有包含该item(项)的条件模式基(CPB)，即前缀路径；所有这些CPB的频繁度(总数)为该路径上item的频繁度(总数)。

(2)定义一个计数器，保存每个CPB上的item的频繁度个数，排除低于阈值的属性列表，构建FP-tree。

(3)用不断迭代的方法访问每个条件FP-tree，对后缀频繁项集进行累加，迭代的终止条件有两个，第一是找到整个CAN-tree为空，第二是CAN-tree只有一条路径。第二种情况下，所有在路径上item的组合都是频繁项集，如图2所示。

图2 频繁项的挖掘过程

4 实验与性能分析

4.1 实验数据及方法

实验数据爬取自网站，文中所用的数据集，通过用户签到就可以分享他们的位置。取自用户从2012年 1月至2013年1月共12个月的信息，即一个自然年的信息。实验过程是用离线挖掘的模式。对于爬取的数据，经过预处理，生成了1 200 000条数据，数据涉及到的用户有200 000个，256 000个位置点。影响挖掘方案的性能有几个方面，如何设置好各个方面对挖掘性能影响的权重是相对复杂的问题。如区域网格化、置信度、数据增量、支持度对性能都有影响。对于离线模式的数据挖掘，主要找到具有最大置信度的关联规则。为了提高数据挖掘的实验效果，能够选择最大规则数量，文中将支持度的阈值设置为总访问请求数的0.000 16，即s=p=0.06%，置信度阈值为1.2%，即s=p=1.2%，进行实验，以确定不同的区域网格化水平评估指标的变化，同时增加输入数据集来提高测试增量下算法的性能。进行实验验证之后，将文中提出的CSAR挖掘算法与文献[11]提出的FPPN算法和文献[12]提出的APFTC算法进行了比较。

4.2 实验结果和分析

从表 1可以看出，当网格级别增加时，相同数据数量下，程序的执行时间递减的速度由迅速变缓慢。这是因为按照地理位置关系进行数据的划分，区域的划分必将导致不相邻数据单元之间关联规则的丢失，也就是挖掘出关联规则数会减少。无论进行哪个类型，哪种数据的挖掘，都要根据实际应用场景对挖掘的数据进行最恰当的划分级别设置。

表1 网格级别与整体挖掘时间关系

表2中，实验数据的变化以万级数据为单位。在数据量不同的情况下，对算法进行了执行时间的对比。由于区域间的数据的关联规则数据的减少，为了保证一定的关联规则数量，实验中对划分级别全部都是选择的10行×10列。从表2中可以看出，CSAR的执行效率比FPPN、APFTC[13]要高100到200秒。算法之间的差距会随着数据量的增大而增大。原因在于FPPN、APFTC算法[14]有一个项头表，新加入数据后项头表要重新进行排序，所以花费时间较CSAR多。从表1和表2的实验对比来看，提出的CSAR算法，对于时空增量数据处理的效率有一定的提高和改善。

表2 三种挖掘算法在数据增量下的时间效率对比 s

5 结束语

提出的CSAR算法，是一种基于CAN-tree的时空关联规则挖掘算法。在文中详细阐述了算法的实现过程[15]、设计思路、执行流程，最后验证了该算法的有效性。概括来描述，首先将用户访问请求的历史数据抽象到时空分量范围内，然后使用区域网格划分的方法操作空间分量数据，算法结合了CAN-tree，在减少计算量的基础上，对关联规则动态变化问题进行解决。另一方面，还在时间分量上考虑了时间分量值的衰减[16]，挖掘出的规则更具有实际参考价值。在验证本算法的基础上，与FPPN、APFTC算法进行对比分析。最后通过表格对比列出验证结果。所提出的CSAR算法对于时空数据领域的增量问题起到了一定的作用[17]，在时空数据分量的挖掘时间[18]效率上有所提高，可以显著减少用户，为决策者对数据的分析判断做了相应的准备工作[19]。

CAN-Tree显著减少了运算时间，因为它查找可合并的路径比较简单，且只需要向上的路径遍历。构建CAN-Tree的运算时间是O(mn)，m是事务项的最大长度，n是事务的个数。尽管CAN-Tree提供了一个简单的单次构建过程，与FP-Tree相比，显然占的空间还是比较大的。为了缩减树的大小，在后续的过程分类中树的调整过程可以被实施。通过分布式运算分类，CAN-Tree的这种构建方式可以有效地减少运算时间。