状态转移模式的三支增量挖掘

曾圣超， 张智恒， 闵 帆， 张紫茵

(1. 西南石油大学 计算机科学学院 四川 成都 610500； 2. 四川旅游学院 信息与工程学院 四川 成都 610100)

0 引言

作为决策粗糙集[1]的核心思想之一，三支决策理论近年来在各方面[2-11]均取得了长足的进展。各种先进的理论如形式三支粒计算、三支概念分析、三支认知计算、三支模糊集方法、三支决策空间[2-7]等均受到三支决策的启发。此外，在三支决策基础上又实践了多种机器学习技术，如三支推荐系统、三支主动学习、三支聚类[8]、三支邻域覆盖约简[9]、三支垃圾邮件过滤[10]、项集三支增量挖掘[11]等。

增量算法利用已有的知识和增量数据得到最新的知识[11]，能够极好地适应大数据场景。对于模式发现问题，人们针对购物数据提出了频繁项集的增量算法如三支决策更新模式方法(three-way decision update pattern，TDUP)[11]和快速更新算法(fast update，FUP)[12]。对于各种序列数据，如股价、文本、基因，设计了频繁闭合序列挖掘算法(incremental bide，BideInc)[13]。对于最一般的时序交互数据[14]，如出行轨迹、购物清单、观影评分[15]等，大量的增量算法如增量序列提取(incremental sequence extraction，ISE)[16]和增量更新序列(incrementally updating sequences，IUS)[17]被提出来获得频繁的事件/行为序列。多元时序数据(multivariant time series,MTS)如空气质量、工业设备、人体健康数据上的频繁模式[18]挖掘同样受到了广泛关注[19-20]。然而，MTS上的频繁模式增量挖掘算法还有待丰富。

本文提出了MTS数据上状态转移模式(state transition pattern，STAP)[20]的三支增量挖掘算法(three-way incremental updating method of state transition pattern，3IU-STAP)。该算法由4个阶段组成。第一，增量更新频繁状态。它们是构成STAP的基本分量元素，其集合可被视为构成STAP的字母表。第二，构造候选STAP以及增补数据db′。任意候选STAP均是由两个更短的频繁STAP链接而来。从原始数据DB截取的尾部长度是由候选序列的长度和通配符区间的上界来确定的。对于所有长度相同的候选STAP，所截取的尾部是一致的。因此，在最坏情况下，构建增补数据的次数为MTS数据的长度；而在平均情况下，其构建次数与最长频繁STAP的长度一致。第三，通过判断候选STAP在DB和db′上频繁或不频繁的表现，将所有候选模式划分进3个互不相交的集合中，即正域(positive region，POS)、负域(negative region，NEG)和边界域(boundary region，BND)。当一个候选STAP在DB和db′上均频繁，则它一定是频繁的，令其属于正域。当一个候选STAP在DB和db′上均不频繁，则它一定是不频繁的，令其属于负域。否则，将其划入边界域，通过重新扫描DB或db′获得准确的支持度，并判断该STAP是否频繁。第四，算法依靠所获得的频繁模式来构造更长的候选模式，直到生成候选模式集合为空时终止。

对环境工程、工业设备、石油工程等领域的4个真实数据集进行实验，结果表明，增量算法与批量算法相比，时间性能提高了5.3～649倍，且增量越小，效率越高。

1 基础知识

本章首先介绍MTS的数据模型。在此基础上描述状态、STAP及其支持度。

1.1 数据模型

在模式挖掘过程中，人们通常关注符号型的MTS数据。对于传感器网络采集的数值型数据，需要进行离散化。

1.2 状态转移模式

定义3[20]给定两个状态转移模式P=s1Δs2…si，P′=s′1Δs′2…s′j，i,j≥1，它的增长操作是P⊗P′=s1Δs2…siΔs1′Δs2′…sj′。

其中|EP|表示模式P在DB上出现的次数。因此，P在DB上的支持度是

sup(P,DB)=(|EP|/|E|)∈[0,1]。

当时间序列DB给定时，可以简写成sup(P)。由此可给出频繁STAP的定义。

定义7[20]给定阈值ρd，频繁STAP的集合为

F={∀P∈F|sup(P)≥ρd}。

2 本文算法

本节首先提出STAP的增量挖掘问题并分析其时间复杂度。其次，提出了解决该问题的三支增量模型。然后，基于模型提出了3IU-STAP算法设计与实现。

2.1 问题描述

问题： 增量挖掘频繁STAP。

输出：FDB∪db={P|sup(s∈P,DB∪db)≥ρw,sup(P,DB∪db)≥ρd}。FDB∪db是在更新后的数据集上所有满足阈值ρw和ρd的频繁STAP的集合。

虽然问题的时间复杂度是指数级的，但可通过引理1描述的向下封闭性质来大大减少实际运行时间。

引理1假设ρd是STAP的序列阈值。如果P⊆P′，则sup(P′)≤sup(P)。

2.2 3IU-STAP算法

2.2.1三支增量模型 对于任意给定的候选模式P(由定义3可得)以及支持度，根据它在原始数据DB和增补数据db′上是否频繁，提出了判断候选模式是否频繁的三支划分模型，如式(1)所示，

(1)

图1给出了针对这3个区域的处理技术。正域中的候选模式P一定是频繁的，直接接受并存储。负域中的候选模式P一定是不频繁的，直接拒绝并抛弃。边界域中的模式P需要延迟决策，即扫描数据集计算最新的支持度。当一个候选STAP在DB上频繁，而在db′上不频繁，即sup(P,DB)≥ρd且sup(P,db′)<ρd，扫描db′；当该模式在DB上不频繁，而在db′上频繁，即sup(P,DB)<ρd且sup(P,db′)≥ρd，扫描DB。

最后，基于式(1)与图1所示模型导出引理2和引理3，以有效降低算法对数据集的扫描。

图1 STAP增量挖掘三分而治示意图Figure 1 Tri-partition and actions

图2 构造增补数据Figure 2 Construct supplementary data

引理2若P是存在于正域中的候选模式，则模式P在DB∪db上频繁。

证明

(2)

由于|EDB|>0且|Edb|>0,则有

(3)

(4)

不等式同号可相加，由式(3)+式(4)得

(5)

则可得到

因此P在DB∪db上频繁。

引理3若P是存在于负域中的候选模式，则模式P在DB∪db上不频繁。

证明与引理2同理。

2.2.2算法描述 算法1给出了频繁状态转移模式三支增量挖掘算法的伪代码实现。其输入由7部分组成，即原始数据DB及其频繁状态集W和频繁STAP集FDB、增量数据db、通配符区间Δ、以及两种阈值ρw和ρd，ρw被用于判断一个状态是否频繁，ρd被用于判断一个STAP是否频繁。其输出为更新后的数据集DB∪db上的频繁STAP集合FDB∪db。

算法1状态转移模式三支增量挖掘。

输入：DB，db，ρd，ρw，Δ，FDB，W;

输出：FDB∪db。 ∥最新的频繁STAP

方法名：3IU-STAP

1. 根据W, DB, db以及ρw增量更新频繁状态集，记为W*;

2. 初始化1-FDB∪db←{s|sup(s)≥ρd≥ρw}⊆W*, k←2, FDB∪db←∅;

3. while ((k-1)-FDB∪db≠∅) do

4. k-FDB∪db←∅;∥正域中所有长度为k的STAP集合

5. 根据tail和db构造增补数据db′; ∥将tail作为db的头部

6. 构建候选模式集k-O=(k-1)-FDB∪db⊗1-FDB∪db; ∥笛卡尔积

7. for each P∈k-O do

8. if sup(P，db′)≥ρdthen

9. if P∈FDBthen k-FDB∪db=k-FDB∪db∪{P}; ∥将频繁模式P存入正域

10. else isFrequent=delayDecision(DB, P,ρd,Δ); ∥扫描DB，返回布尔值

11. if isFrequent then k-FDB∪db=k-FDB∪db∪{P};

12. else ∥在db′上不频繁

13. if P∈FDBthen isFrequent=delayDecision(db′, P,ρd,Δ); ∥扫描db′，返回布尔值

14. if isFrequent then k-FDB∪db=k-FDB∪db∪{P};

15. else continue; ∥此时P属于负域，一定不频繁，直接抛弃

16. return FDB∪db。

第6行描述了两个频繁STAP集合的笛卡尔积。对任意模式P∈(k-1)-FDB∪db以及P′∈1-FDB∪db，长度为k的候选模式通过P⊗P′获得。第8～9行组成的条件对应了式(1)中正域判定条件，其候选STAP属于正域可直接存储。第12、15行对应了式(1)中负域划分条件直接抛弃。第10～11行及13～14行分别描述了两种延迟决策技术。

算法2实现了delayDecision方法以重新扫描DB并获得新的支持度信息。如果这个新支持度不小于指定阈值ρd，则再将其划入正域，否则抛弃。

算法2扫描数据集以更新支持度。

输出：TRUE or FALSE。

方法名：delayDecision

1. occ=0;

2. for i=1;i<|T|-k;i++ do

5. else return FALSE。

算法3实现了方法count。其中α表示匹配到了DB中第α个时间点，β表示匹配到了模式P中第β个状态。

算法3统计以ti开头的所有匹配次数。

输出：occ。

方法名：count

1. if β等于k then return 1; ∥P中所有的状态都完成了一次匹配

2. occ=0;

5. return occ。

3 实验

本章节通过实验对两方面展开了讨论：1) 3IU-STAP性能与频繁阈值ρd的关系；2) 3IU-STAP性能与增量大小的关系。

3.1 数据集与预处理

实验环境为CPU：i5-7500 3.40 GHz；内存6 GB；操作系统：Windows 10；IDE：Eclipse，Java。

表1展示了数据集的基本信息。依次来自UCI、全国数学建模比赛(半开放)、中国海洋石油公司(油井维护数据)。采用的离散化方案参见文献[20]。

3.2 结果分析

如图3所示，在各数据集中，增量算法分别比批量算法快7.7倍、12倍、649倍、5.3倍。其中，Δ=[3, 6]，增量划分比例为10%，Apriori-STAP是批量算法。

表1 数据集的基本信息Table 1 Basic information of data set

图3 批量算法与3IU-STAP算法时间性能Figure 3 Batch algorithm and 3IU-STAP algorithm time performance

图4为基于不同增量数据划分比例(r)的算法性能表现。当划分比例较小时，运行时间少。随着r的增加，运行时间增加。因为增量越大，边界域所耗费的时间越大。

图4 增量大小对时间性能的影响Figure 4 The effect of incremental size on time performance

4 结论

本文基于三支决策理论，提出了一种多元时序数据上状态转移模式的三支增量模型与挖掘算法3IU-STAP。在插入增量数据时，通过三支划分模型将大量的候选模式划分为正域和负域，从而减少扫描数据集的次数。通过构造增补数据集来确保扫描结果的完备性。理论分析与大量实验结果表明，3IU-STAP能准确高效地获得结果。