空间关联规则的增量维护

Incremental maintenance of discovered spatial association rules

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

Executing spatial association rule mining repeatedly is often necessary to get interesting and effective rules. Though incremental maintenance algorithms can be introduced to improve the efficiency of association rule mining, currently there exists no such algorithm that can use spatial datasets directly. To solve this problem, the update strategy of the discovered rules was discussed. Both threshold changes and spatial datasets updates were taken into consideration, and an incremental mining algorithm called Incremental Spatial Apriori （ISA） was suggested. ISA algorithm aimed to update frequent predicate sets and association rules after the minimum support threshold decreased or new spatial layers added. This algorithm did not rely on the creation and update of spatial transaction tables; it directly used spatial layers as input data. In experiments with real-world data, the mining result extracted by ISA and Apriori-like algorithms are identical, but ISA can save 20.0% to 71.0% time comparatively. Besides, 1 372 722 rules were successfully updated with the filtering method, costing less than 0.1 seconds. These results indicate the incremental update strategy and algorithm for spatial association rules suggested in this paper are correct, efficient and applicable.