空间关联规则的增量维护

开篇：润墨网以专业的文秘视角，为您筛选了一篇空间关联规则的增量维护范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：

为了得到有趣且有效的空间关联规则通常需要多次执行挖掘操作，可以使用增量维护算法来提高挖掘效率。然而，能够直接使用空间数据的关联规则增量更新算法尚属空白。为解决这一问题，对挖掘阈值改变和空间数据集更新后通过筛选或增量挖掘等方法实现规则维护的策略进行了分析，并提出适用于支持度阈值减小和空间图层增加这两类情况的增量挖掘算法——ISA。ISA算法不依赖于空间事务表的构建与更新，可以直接使用空间图层作为输入数据。在基于实际数据的实验中，采用ISA算法所得结果与类Apriori算法一致，耗时则相对缩短20.0%至71.0%；此外，对1372772条规则进行了基于筛选的更新，耗时低于0.1s。实验结果表明，所提出的空间关联规则增量维护策略和算法是可行、正确且高效的。

关键词：

空间数据；关联规则；增量更新；空间分析；数据挖掘

0引言

空间关联规则挖掘是一种带有探索性和时效性的知识发现任务：一方面，为了得到较为理想的挖掘结果可能需要尝试多种挖掘阈值；另一方面，随着时间的推移，空间数据要不断进行更新，对更新后的数据重新进行挖掘才能保证结果的时效性。显然，为了得到有趣且有效的知识，往往需要采用接近的阈值对部分相同的数据进行多次挖掘。

由于空间关联规则挖掘依赖于复杂度较高的空间分析操作，多次执行挖掘算法总代价很大，在已有初步的挖掘结果时可以用增量维护算法取代挖掘算法以提高效率。然而，已有的增量式算法大多关注的是如何应对事务表中记录、字段的增删以及挖掘阈值的变化[1-10]，解决的是传统关联规则而不是空间关联规则的更新问题；文献[11-12]分析了时态关联规则以及空间同位模式的增量更问题，同样仅具有参考意义；文献[13]针对空间事务表中记录追加问题提出一种空间关联规则增量更新算法，但该算法难以处理基于空间分析的挖掘算法的挖掘结果，因为这类算法不依赖于空间事务表的构建与更新[14-15]；目前能够直接使用矢量及栅格等常见空间数据类型[16]，同时考虑了数据变化和阈值变化的空间关联规则增量更新算法尚属空白。为解决这一具有实用价值的问题，本文对文献[17]中直接从空间图层中提取关联规则的算法进行了改进，提出增量挖掘算法——ISA（Incremental Spatial Apriori）。下面首先对其原理进行介绍。

1增量维护策略

1.1阈值的变化

最小支持度阈值sup_min和最小置信度阈值conf_min是空间关联规则挖掘中的两个基本参数。其中，sup_min对整个挖掘过程都极为重要，因为其取值决定着频繁谓词集的内容与数量，进而限定了可能提取出的关联规则的范畴；相对地，conf_min取值不会对频繁谓词集提取阶段造成影响，但实际提取出的规则的内容与数量是由该参数决定的。

首先考虑sup_min变化的情况。问题描述为：假定挖掘对象不变，已知sup_min取s时的频繁谓词集为f，如何对f进行更新得到sup_min取s′时的频繁谓词集 f′。根据s与s′的关系，可以分为以下3种情况[3]：

1）当s′=s时， f′=f；

2）s′>s时， f′是f的子集，只需要将f中支持度小于s′的谓词集剔除即可得到 f′；

3）当s′

显然，前两种情况下不必访问数据就可以实现频繁谓词集更新，第3种情况下则相对复杂。在第3种情况下，差集 f′-f是sup_min取s时的非频繁谓词集的子集，它们在新阈值变为了频繁谓词集。对于这种情况，需要再次进行挖掘，但所有已知的频繁谓词集不必重新测试。

然后考虑conf_min变化的情况。问题描述为：假定挖掘对象和sup_min不变，已知conf_min取c时的规则集r（含频繁谓词集f），如何对r进行更新得到conf_min取c′时的规则集r′。类似的，c与c′的关系也可以分为3种情况：c′=c、c′>c以及c′

对于sup_min和conf_min都改变的情况不妨分步处理，即首先更新频繁谓词集，然后重新执行规则生成子程序。需要注意的是，在s′≥s且c′≥c的情况下，只需要剔除支持度小于s′且置信度小于c′的规则即可完成规则的更新，即整个过程都可以通过筛选操作实现。

1.2图层的变化

文献[17]中挖掘算法的输入数据是一组空间图层。对于一组空间图层，其变化不外乎3种：增添新图层、删除已有图层和更改已有图层。其中：图层增删是最基本的变化，图层更改可以利用二者的合成来实现（即删除更改前的图层，然后添加更改后的图层）。此时问题描述为：假定sup_min不变，已知图层集l在给定参数下的频繁谓词集f，如何对f进行更新得到图层集合l′对应的频繁谓词集 f′（l l′或l′ l）。

首先考虑图层删除的情况。从l中移除任意一个图层（对应谓词为p）不会对其他图层的内容造成影响，也就是说由其他图层对应谓词组成的谓词集的支持度不会发生改变；另一方面，由于l被删除，p不应该出现在 f′中，因为p和包含p的谓词集已经不在新的挖掘任务的考察范围之内了。此时只需要将f中所有包含p的谓词集删除即可得到 f′。对于删除多个图层的情况以上结论仍适用，删除不在考虑范围内的频繁谓词集就能实现结果的更新。

然后是图层增加的情况。由于引入了新谓词，必须进行增量式挖掘才能对频繁谓词集更新。新增图层不会对原有谓词组成的谓词集频繁性造成影响。由于已知原有谓词集中哪些是频繁的哪些是非频繁的，增量式挖掘过程中不必重复测试。

对于同时发生图层的增添和删除的情况，原则上应该先针对删除问题对频繁谓词集进行更新，这样可以将不必要的图层排除，减少针对图层增加的增量式挖掘耗时。

2增量式挖掘算法——ISA

当支持度减小或图层增加时必须通过增量式挖掘才能完成结果更新任务，下面给出适用于这两种情况的挖掘算法——ISA（Incremental Spatial Apriori）：

3实验与分析

3.1实验数据

本文选用加利福尼亚州资源保护局（California Department of Conservation）提供的阿拉米达县（Alameda County，见图1）1984到2002年的10幅覆被分类图作为实验数据，这些分类图记录着7种覆被在偶数年份中的分布情况。为进行关联规则挖掘，依据覆被类型对分类图进行了分割，分割结果以年份加类别缩写命名，采用栅格格式存储。经过以上处理总共得到10组（每组7个，共70个）分辨率为20m，高度和宽度分别为2545和3939像素的栅格图层。

3.2实验方案

本文实验主要包括两部分，分别对支持度变化和数据变化这两种情况对下增量挖掘算法进行检验。

第一部分的目的是对比支持度发生变化的情况下ISA算法与类Apriori算法的挖掘结果与性能。由于ISA算法依赖于已有挖掘结果，故在对比实验之前先取sup_min为10-1用类Apriori算法进行了规则挖掘。之后，依次取10-2，10-3，…，10-7作为sup_min，分别用ISA和类Apriori算法对实验数据进行了规则挖掘。ISA算法总是使用最新的挖掘结果作为输入，例如在提取sup_min为10-3时的规则时使用sup_min为10-2时得到的规则作为输入。

第二部分的目的是对比图层增加的情况下ISA算法与类Apriori算法的挖掘结果与性能，相关实验sup_min均为10-7。首先采用2组图层作为输入用类Apriori算法进行了规则挖掘来获取ISA算法的输入；然后依次取3到10组图层作为输入数据，分别用ISA和类Apriori算法进行了规则挖掘。ISA算法仍然是使用最新的挖掘结果作为输入，例如提取4组图层对应规则时使用3组图层对应的挖掘结果作为输入。

作为补充，在完成实验的主要部分后，对最小支持度和置信度阈值为10-7时的规则进行筛选，以考察不需要执行挖掘时规则维护耗时情况。

本文实验均在CPU为Xeon E31230 V2、内存16GB、操作系统为Windows Server 2012的工作站上进行，挖掘算法以Java语言实现，空间分析操作通过调用GDAL（Geospatial Data Abstraction Library）完成。

3.3结果与分析

实验中相同数据、相同阈值下两种算法挖掘结果均完全相同，这证明了ISA算法的正确性。由于频繁谓词集提取是规则挖掘算法的主要任务，本文主要依据两种算法频繁谓词集提取耗时来分析ISA算法是否有效（见表1～2）。

表1列出了第一部分实验的结果，即最小支持度阈值从10-2减小到10-7的过程中两种算法测试的候选谓词集个数、得到的频繁谓词集个数以及算法执行耗时对比。作为补充，表1第1行给出了类Apriori算法在支持度阈值为10-1时的相关数据。在表1中，不论是类Apriori算法还是ISA算法，随着支持度阈值的减小，挖掘过程中测试的候选谓词集总数、得到的频繁谓词集总数以及挖掘耗时都在增大。由于ISA算法可以使用已有挖掘结果，不必重复测试已知结果中的频繁谓词集，故挖掘耗时相对较少。但是需要注意，ISA算法累计耗大于类Apriori算法耗时（非累计），这主要是因为支持度阈值逐步减小时多次执行ISA算法会重复计算部分候选谓词集的支持度。

表2列出了第二部分实验的结果，即图层数从21（3组）增长到70（10组）的过程中两种算法测试的候选谓词集个数、得到的频繁谓词集个数以及算法执行耗时对比。类似的，表2第1行给出了类Apriori算法在图层数为14（2组）时的相关数据作为补充。表2中，随着图层数的增加，候选集数、频繁集数、耗时都不断增长，完成同样的任务ISA算法仍然是耗时较少。ISA算法在随着图层增加递进式执行的过程中不存在重复测试相同候选谓词集的问题，故其累计耗时与类Apriori算法相近。

一般来说，对于相同的任务，用原算法得到初步结果再用增量维护算法对结果进行更新不会比直接使用原算法直接完成该任务更有效。所以考察增量式算法的有效性主要是分析该算法能否充分利用已有结果来缩短任务耗时。ISA算法可以利用已有结果中所有的频繁谓词集来实现增量式挖掘，在应对图层增加的情况时甚至可以使用未显式包含在结果中的信息（候选谓词集），实验中不同情况下该算法执行耗时相对于类Apriori算法可缩短20.0%到71.0%，证明了其有效性。

在补充实验中，对239476个频繁谓词集和1372772条规则进行了筛选，提取出支持度和置信度阈值为10-6时的挖掘结果（共含207252个频繁谓词集和1182401条规则，与直接挖掘和增量式挖掘结果一致），耗时低于0.1s。显然，更新已有挖掘结果时应优先考虑采用代价极小的筛选操作来实现。

4结语

数据类型的多样性和挖掘效率是空间数据挖掘的两个重要主题[19]，本文着眼于这两点，对如何直接使用空间数据实现关联规则的增量维护这一问题进行了初步的系统研究，并给出了对应的增量式挖掘算法。但是，目前还有一些问题有待进一步探讨。首先，在sup_min减小的过程中增量挖掘必然会重复计算一些非频繁谓词集的支持度，可以考虑构建缓存来缩短挖掘耗时，但怎样才能取得较好的效费比需要结合具体情况进行分析；其次，文献[17]中的挖掘算法在挖掘过程中可以保存频繁谓词集对应的图层，如何利用这些图层来提高更新效率是下一步的研究内容；此外，为了确保挖掘结果的正确性和实用性，如何利用规则内在的逻辑联系对其进行精简，如何利用主客观评价指标、专家或用户定义模板以及可视化工具对其进行筛选也是进行规则增量维护时应当考虑的重要问题。

参考文献：

[1]

CHEUNG D W， HAN J， NG V T， et al. Maintenance of discovered association rules in large databases： an incremental updating technique [C]// Proceedings of the Twelfth International Conference on Data Engineering. Piscataway： IEEE Press， 1996： 106-114.

[2]

李斌，马戈，孙志挥.项目集发生变化的关联规则增量式更新算法[J].计算机应用，2004，24（12）：105-107.

[3]

冯玉才，冯剑琳.关联规则的增量式更新算法[J].软件学报，1998，9（4）：301-306.

[4]

温蕴.一种基于阈值变化的增量式更新算法研究[J].计算机科学，2008，35（8）：247-248，261.

[5]

吴立锋，侯睿，王江晴.基于关联规则的增量更新算法[J].武汉理工大学学报，2010，32（20）：151-155.

[6]

陈煜，徐维祥.基于逆向搜索的关联规则更新算法[J].计算机工程，2011，37（8）：25-27.

[7]

GENG X， CHU X， ZHANG Z. An association rule mining and maintaining approach in dynamic database for aiding productservice system conceptual design [J]. The International Journal of Advanced Manufacturing Technology， 2012， 62（1/2/3/4）： 1-13.