【www.zhangdahai.com--其他范文】
荀亚玲，王林青，蔡江辉，2*，杨海峰
（1.太原科技大学 计算机科学与技术学院，太原 030024；
2.中北大学 计算机科学与技术学院，太原 030051）
信息大爆炸的时代，带时间标签的时序数据广泛出现在各个行业，如：股票价格、网站点击流、工业传感器数据、车联网等。时序数据就是在时间上分布的一系列数值，它具有如下特征［1］：1）所有交易记录都按照它们发生的顺序排序；
2）连续的交易集之间可以存在时间间隔；
3）多个交易集可以共用一个时间戳。这3 个属性将时序数据库与广泛研究的事务性数据库区分开。
近年来，高效地分析时序数据，使之产生业务价值成为一个热门话题［2］。部分周期模式是时序数据库中存在的一类重要的规则，与全模式周期相比，部分周期模式只描述时序数据中某些点的周期特征，是一种松散周期模式，在实际应用中更具普遍性。在时序数据库中发现部分周期模式在分析顾客消费行为［3-5］、基因序列分析［6］等众多领域具有重要意义。
时序数据因其产生频率快、严重依赖于采集时间、测点多、信息量大等特性给探索动态增长时序数据库中的部分周期模式提出了挑战。Tanbeer 等［5］给出了在事务数据库中周期性频繁模式（Periodic Frequent Pattern，PFP）的定义，并设计了一种称为PF-Tree（Frequent Pattern-Tree）的模式增长算法来识别这种模式，指出如果间隔（连续出现之间的事务数）始终小于用户定义的最大间隔周期阈值，则模式是周期性的，该定义已在多项研究［7-10］中得到使用。然而，这种定义过于严格，一些研究［1，11］对该定义做了改进，将最小支持阈值和最大周期阈值与每个项目相关联，更公平地衡量每个项目的周期性。然而，这将导致用户需设置的参数数量变得非常大，虽然可以使用一个函数自动设置所有阈值，但选择适当的函数为每个项目分配阈值并避免丢失感兴趣的模式却很困难。
模式组合爆炸的问题给发现有用的周期模式提出了挑战。针对该问题，Likhitha 等［12］提出了一种可能存在于时间数据库中的封闭周期性频繁模式的新模型。封闭的周期频繁模式［13］是一个简洁的无损子集表示，唯一地保存了数据库中所有周期频繁模式的完整信息，同时一种高效的深度优先搜索算法，即CPFP-Miner（Closed Periodic-Frequent Pattern Miner）被提出，用于查找数据库中所有需要的模式。Fournier-Viger 等［8］提出了PFPM（Periodic Frequent Pattern Miner）算法，该算法允许用户使用三种周期性度量（最小周期性、最大周期性和平均周期性）来发现周期性频繁模式，为用户提供了更多的灵活性，从而可以更精确地指定用户感兴趣的模式类型。PFPM 和许多其他研究一样，均假设模式的周期性随时间保持稳定［14］，但在现实生活中，模式的周期性行为可能会随着时间的推移而改变。因此，一些研究［15］试图发现模式的频率或效用可能发生变化的概念漂移点（变化点），但依赖于非常严格的最大周期模型。
部分周期模式作为一种更为松散的周期模式，对它的研究更具普适意义。Kang 等［16］基于部分周期的概念，先后提出了类Apriori 和最大子模式命中的部分周期模式挖掘算法，其中最大子模式命中集将时间序列模式子集存入最大命中子模式树中，在挖掘部分周期模式时只需要扫描两次时序数据库；
同时，基于Apriori 特性和变通的时间序列部分周期模式挖掘算法还可以挖掘多周期的时间序列部分周期模式。Upadhyay 等［17］将频繁部分周期模式应用到发现物体的运动规律，使用部分周期模式树来递归地寻找所有物体运动规律，但在跟踪和定位物体的过程中会出现不确定性问题，因此，引入了一个时空概率来表示物体位置不确定性。Kiran等［7］发现确定项目集中每个候选模式的周期性使得部分周期频繁模式挖掘成为一个计算代价很高的过程，因此，采用贪婪搜索来确定模式的周期性，通过消除次优解的非周期模式来发现所有的部分周期频繁模式。
上述传统的部分周期模式挖掘方法有着很强的局限性：1）不具备可扩展性；
2）面对时序数据来源广泛，且具有大体量、多源性、连续采样、价值密度低、动态性强等特点，导致目前的传统挖掘方法在处理增量数据集时所耗时间巨大。一些研究［18-20］对动态增长的模式挖掘进行了研究，主要关注以下两方面：1）避免对原始数据库重新扫描；
2）生成并调整大的树结构。因此，本文通过结合多尺度理论，提出一种新的适应动态增长时序数据部分周期模式挖掘算法（Multi-Scale Incremental Partial Periodic Frequent Pattern，MSIPPPGrowth）。在MSI-PPPGrowth 中，利用时序数据客观存在多尺度特性，首先将数据集进行更细粒度的划分获取到基准尺度数据集，在基准尺度数据集上利用PPPGrowth（Partial Periodic Pattern-Growth）算法挖掘相应的部分周期模式；
然后通过不同尺度数据间的相似度完成跨尺度推导，将单一尺度数据集上的关系通过尺度上推，转化成目标尺度上的关系，实现一次挖掘即可得到多层次的知识。其中，考虑时序周期性，基于克里金（Kriging）法［21］设计了一个新的函数Periodic-Jaccard 来有效解决尺度转换过程中的缺失计数补全问题。
1.1 部分周期模式
时序数据库中可能存在的部分周期模式的基本模型［1］如下：I={i1，i2，…，in}（n≥1）是出现在数据库中的n个项目集合。项目X⊆I的集合称为模式，一个模式包含k个项目称为k模式，这个模式的长度为k。一个事务tr包含事务识别符、时间戳和一个模式，可以表示成tr=(tid，ts，Y)，tid代表着事务的识别符，ts∈R+代表事务的到达时间或时间戳，Y是一个模式。一个时序数据库表示为TDB，TDB是有序事务集的集合TDB={tr1，tr2，…，trm}，m=|TDB|表示为时序数据库的大小（或者事务集的总个数）。令，是模式X出现在TDB中的事务的时间戳有序列表。
例1 考虑表1 所示的时序数据库，项目集I={a，b，c，d，e，f，g，h}，这个时序数据库包含12 个事务，因此这个数据库的大小为|TDB|=12。在此时序数据库中，每个事务都由事务的识别符、时间戳和一个模式组成。项目a 和b表示成{a，b}简称为ab，是一个模式并且这个模式包含两个项目，称为2 模式，模式ab 出现在第1 个事务里，因此第1 次出现的时间戳为=1，由此可得在表1 中所有包含模式ab的事务集所出现的时间戳的集合为TSab={1，3，4，5，9，11，12}。
表1 时序数据库示例表Tab.1 Example of time series database
定义1模式X的周期出现。
定义2模式X的周期支持度。
定义3频繁部分周期模式。
模式X是频繁的部分周期模式，当且仅当PS(X) ≥minPS，minPS表示用户指定的最小周期支持度。
1.2 多尺度理论
多尺度研究的本质是根据概念分层将数据集分割成多个尺度，并且从一个尺度得出结论再转变到其他尺度。尺度转变包括尺度上推和尺度下推：尺度上推是将小尺度数据集结论转变成大尺度数据集结论；
反之则被称为尺度下推。本文关注利用尺度上推实现频繁周期模式的增量挖掘。
概念分层H是一个偏序关系集(H，≺)，其中H为有限概念集，“≺”表示H所包含概念之间的一种偏序关系，表示概念涉及范围、粒度的相对大小或者时间幅度的相对长短，那么称此概念分层(H，≺)具有多尺度特性。以具备多尺度特性的概念分层为标准进行数据集的划分，便可以形成多尺度数据集。
时序数据库TDB以概念分层(H，≺)中的概念hi为数据尺度，按照数据尺度划分后的结果，所有子数据集为时序数据库TDB在数据尺度hi下的元尺度数据集。若其他尺度数据集可以由该元尺度数据集合并或分解得到，那么该元尺度数据集称为基准尺度数据集BS，相应地通过概念hi划分的上层尺度数据集称为目标尺度数据集TS。尺度上推转换，即通过基准尺度集结果推导出目标尺度数据集对应的近似结果，而不对目标尺度数据集TS进行直接挖掘，达到快速更新频繁的部分周期模式目的。
PFIi和PFIj分别代表着基准尺度数据集BSi和BSj的频繁部分周期模式。在兄弟尺度间和尺度上推的过程中都常有项目周期支持度计数缺失的情况，因此，基于克里金法［21］提出一个估计缺失周期支持度计数模型。
克里金法是一种基于最小二乘法的随机插值技术，用方差矩阵作为权重函数，可应用于通过其他点数据来估算地表上任意点，估算公式如式（1）所示。克里金法中随机场（如图1 所示）中随机场所对应的指数集通常为地理坐标，而随机场内每一个点的测度都是一个随机变量，服从特定的概率分布。
图1 克里金模型Fig.1 Model of Kriging
式中：s0为未知点，{s1，s2，…，sn}为随机场的样本点；
a为克里金权重，由样本点与未知点间的协方差矩阵确定；
μ为随机过程{Y(t)}的期望；
(s0)是Y在未知点s0处的估计；
ε为任意常数，用于估计值的误差修正。
MSI-PPPGrowth 将空间场降维到平面场，如图2 所示，需要通过1、2、3、4 这4 个已知点来推测待估值点5。
图2 平面场模型Fig.2 Model of plane field
考虑到周期性和时间维度，设计了一个估计缺失计数的模型PJK-EstimateCount。式（2）给定了一个权重系数（wc），反映了在tsmin到tsmax时间段内，有效周期支持度计数比：
其中：minPS为最小周期支持度，maxPer为最大周期间隔，tsmin、tsmax表示尺度数据集中最小时间和最大时间。
缺失项集计数利用式（3）进行估算：
其中：est_percounti是用来估计在基准尺度数据集BSi中未知项目计数，percountj是基准尺度数据集BSj中项目的精确周期支持度计数，Sij代表着基准尺度数据集BSi和BSj间的相似度，m表示每个基准尺度数据集BS中非零精确支持度的个数。值得注意的是当时est_percounti的值应该设置为minPS。因为在基准尺度数据集BS中项目的周期计数为0 代表着它并不是一个频繁部分周期模式，因此它的周期支持度计数不能超过minPS。
由于时序数据库中允许连续的事务之间存在时间间隔和存在公共时间戳的事务，因此在衡量周期性时不能只考虑项目的频率，还需要考虑它在数据库中到达的时间，以便准确地确定项目集的周期性。基于传统树结构的挖掘方法因其未考虑到时间参数的影响而且只考虑单个项目频率，并不能直接应用于部分周期模式挖掘。PPPGrowth［1］通过在树结构中添加时间和周期频率两个属性（被称为PPP-Tree）可有效度量项目的周期性；
但PPP-Growth 需要频繁遍历树结构，在挖掘时序数据的部分周期模式过程中造成的时间消耗令人难以接受。因此，MSI-PPPGrowth 将多尺度理论引入PPPGrowth 算法，避免了频繁遍历树结构的严重开销。
图3 展示了PPPGrowth 算法基于表2 所示数据集对应的树结构构造过程，图中pf 为部分周期支持度，每个树节点包含部分周期频繁项目本身及其在事物集中出现的时间戳，以方便计算周期间隔。PPPGrowth 的挖掘过程如下：从每个部分周期项（作为初始后缀项集）开始，构造条件模式库（一个子数据库，由与后缀项集共现的PPP 树中的前缀路径的集合组成），然后构造条件PPP 树，并在树上递归地执行挖掘。通过将后缀项集与从条件PPP 树生成的部分周期项集连接来实现模式增长。
图3 构建PPP-TreeFig.3 Construction of PPP-Tree
算法1 描述了在基准尺度数据集BS中挖掘频繁部分周期模式，并利用函数来补全缺失的部分后期支持度计数的过程。
算法1 基准尺度数据集挖掘。
输入 基准尺度数据集BS，最小周期支持度minPS，最大周期间隔maxPer；
输出 所有频繁部分周期模式（D1）。
算法2 描述了在增量数据集TS中挖掘频繁的部分周期模式，通过三种情况来将BS与TS的结果更新，获取时序数据更新后的最终部分周期模式。
算法2 增量数据集挖掘。
输入 增量数据集TS，最小周期支持度minPS，最大周期间隔maxPer；
输出 更新后的频繁项目集。
以下将结合具体的实例来描述MSI-PPPGrowth 算法的挖掘过程。
算法1 的第1）步将公司一年的销售数据按照对应于尺度“季”的属性划分为dseason1、dseason2、dseason3、dseason4四个尺度。从概念层次来看，可以看到“年”是4个季节的上层尺度TS，4个季节是“年”的基准尺度BS，也就是说dyear=dseason1⋃dseason2⋃dseason3⋃dseason4。4个尺度的数据集如表2～5所示。
表2 dseason1尺度数据集Tab.2 Scale dataset of dseason1
表3 dseason2尺度数据集Tab.3 Scale dataset of dseason2
表4 dseason3尺度数据集Tab.4 Scale dataset of dseason3
表5 dseason4尺度数据集Tab.5 Scale dataset of dseason4
表6 这部分的数据集被当作增量数据集对待，记为dIncremental。最小周期支持度minPS设为2，最大周期间隔maxPer设为2。
表6 dIncremental尺度数据表Tab.6 Scale dataset of dIncremental
利用PPP-Tree 根据算法1 中第2）、第3）和第5）步，按最小支持度阈值挖掘基准尺度数据集BS来获得周期频繁项目，并且存储所有的频繁周期项目和他们所对应的支持度计数到候选集项目信息表Can_info，如表7 所示。
相似矩阵M是在基准数据集BS间利用Jaccard 相似性计算所得，具体见算法1 第6）步。根据上述Can_info，相似矩阵计算结果如下：
算法1 的7）～19）用以估计项目及未知的周期支持度计数，例如，对表7season1 中的”a“项缺失值进行估计，根据式（2）所计算的结果为est_percounta==1.631 7，est_percounta≤minPS=2，所以est_percounta的最终结果为1.631 7。
表7 候选项目集信息Tab.7 Candidate itemset information
频繁项集的更新仅通过挖掘新的尺度数据集和尺度变换来实现。对于不同的基准尺度数据集更新时，采用算法2来具体实现。首先，根据算法2 的第1）步得到所对应的部分周期频繁项目集｛a，b，c，d，e，ab，ad，bd，cd，de，abd｝（如表7所示）；
再通过测量原始BS数据集的频繁项集与新添加数据集的频繁项集之间的相似性，从而更新相似性矩阵M。
当新的频繁项集与原始数据集的周期频繁项进行比较时，将发生以下三种情况，对应的处理过程见算法2 中4）～28）行：情况一，在两个数据集中都是频繁的部分周期模式，比如项目ab、ad、bd、abd，只需要通过添加项集的原始计数和新计数来更新每个频繁项集的支持计数。情况二，项目集在原始数据集中是频繁的，但在新添加的数据中并不频繁，如bc。新数据中那些不频繁的项集的计数需要根据新数据与每个BS数据集之间的相似性，来估计缺失的周期支持度计数。为了提高估计精度，以所有BS数据集的估计值的平均值作为最终估计结果。情况三，项目集在原始数据集BS中不是频繁项集，但在增量数据集TS中却是频繁的，如de。Can_info包含了每个BS数据集中频繁项集候选信息，因此首先在Can_info中搜索该项集：如果Can_info中存在这个项集，则直接读取其计数；
否则必须估计每个项集的周期支持度计数基于相似性的BS数据集。将每个BS数据集中的计数添加到新数据中的计数中，估计完后周期支持度计数总和为更新后的项集的最终结果。
为验证本文算法的有效性，所有实验均在电脑配置为CPU：Intel Core i7-4850HQ CPU @ 2.30 GHz，内存16 GB，操作系统为macOS 11.6.1上基于Python 3.8.2实现。实验使用的数据集如表8所示，其中T10I4D100K是稀疏数据集而T15I1KD300K、accident 和Bible 为稠密数据集。对比算法选择了未考虑时间尺度特性的PPPGrowth算法［1］与PPF-DFS算法［22］。
表8 数据集参数Tab.8 Parameters of datasets
为了验证本文所提算法的有效性，将各数据集划分成11 份，前10 份作为基准尺度数据集，第11 份作为增量尺度数据集。
3.1 参数对算法效率的影响
3.1.1 最大周期间隔maxPer对算法性能的影响
该组实验分别在稀疏和稠密数据上验证了maxPer对算法性能的影响（最小周期支持度minPS=100，maxPer变化范围为10～320），实验结果见图4。
图4 maxPer对运行时间的影响Fig.4 Influence of maxPer on running time
从图4 可以看出，随着maxPer的增大运行时间也随之增加，这是由于maxPer越大，满足条件的部分周期频繁模式也将越多，导致需要频繁调用补全缺失周期支持度计数函数，而在稀疏数据集上，这种调用会更频繁，因此在稀疏数据集上的增长趋势相比稠密数据集更为明显。在稠密数据集上的运行时间要高于在稀疏数据集的运行时间，因为稠密数据集对应的PPP-Tree 构建和频繁树结构调整代价更高。总体而言，所设计的增量挖掘算法在所耗时间上明显少于PPPGrowth 与PPF-DFS 算法。MSI-PPPGrowth 较上述两种对比算法在稀疏集T10I4D100K中的提升效率分别为7.4%与5.5%，在稠密集T15I1KD300K、accident 和Bible 中提升效率分别为10.9%与6.3%，9.7%与4.3%和7.5%与5.8%。
3.1.2 最小周期支持度minPS对算法性能的影响
该组实验分别在稀疏和稠密数据上验证了minPS对算法性能的影响（maxPer=80，minPS从50～150），实验结果见图5。图5 展示了随着minPS的增加，满足条件的部分周期模式越少，因此计算缺失计数过程和调整树结构代价明显减小，从而使得运行时间减少。在稀疏数据集T10I4D100K 和稠密数据集T15I1KD300K、accidents、Bible 上，所提算法的挖掘时间均少于PPPGrowth 算法与PPF-DFS 算法，效率分别提升约为7%与12%、11.3%与8%、3.2%与5.9%和5.6%与5.2%。其主要原因在于，数据集更新后，MSI-PPPGrowth 算法不需要重新扫描数据集或频繁调整树结构，只需要根据所设计的相关函数来估计所缺失的周期支持度。可见，MSI-PPPGrowth能够很好地应对各种类型的数据集，具有广泛的适用性。
图5 minPS对运行时间的影响Fig.5 Influence of minPS on running time
3.2 尺度划分对精度的影响
从第2 章的增量挖掘算法处理过程中可以看出，由于采用估值函数来补全项目集未知的周期支持度计数，MSIPPPGrowth 算法可能会产生两种错误：1）假正项集（不常见的项目由于估计误差，导致在目标尺度数据集中被推断为频繁的项集）；
2）假负项集（目标尺度数据集中频繁出现但在增量数据集中数据缺失）。因此，使用精度（precision）来衡量提出的算法的准确性（如式（4）所示）。精度反映了假正项集和假负项集对实验结果准确性的影响。
在这组实验中，将评估稀疏数据集T10I4D100K 和稠密数据集T15I1KD300K、accidents、Bible 下的尺度划分（如表9所示）对MSI-PPPGrowth 算法精度的影响。
表9 数据集尺度划分Tab.9 Size division of datasets
从图6 观察到，尺度的划分对算法性能有着重要的影响，但无论在密集型数据集还是稀疏性数据集上，MSIPPPGrowth 算法的精度均保持在80%以上。具体而言，稠密数据集由于其更平滑的数据分布使其效果更优于稀疏数据集，且尺度划分得越细，根据估值函数所得到的周期支持度越能接近真实值，从图6 可以看出，当尺度大小为SIZE4 时，算法的精度都达到91.5%以上。总体而言，MSI-PPPGrowth算法虽然在精度上存在着一定的误差，但这种误差和换取的效率提升是值得的，尤其对于大型密集数据集而言，整体的效率最高提高了12%。因此，通过一定精度的损失来抵消挖掘过程中所消耗的时间是可行且有效的。
图6 不同尺度划分造成的精度影响Fig.6 Influence of different scale divisions on accuracy
本文提出了一种结合多尺度理论的时间序列部分周期模式挖掘算法（MSI-PPPGrowth），充分利用了时序数据的多尺度特性，大幅降低了传统动态时序数据在部分周期模式挖掘过程中频繁数据库扫描和调整树结构的开销。实验结果表明本文算法具有广泛的适应性和高效性，在稀疏数据集和稠密数据集上运行效率分别提升了近7%和12%。本文算法尤其适应于大规模数据集，因此，以期对大规模动态数据的并行挖掘做进一步的研究。
猜你喜欢项集时序尺度基于Sentinel-2时序NDVI的麦冬识别研究中国农业信息(2021年3期)2021-11-22财产的五大尺度和五重应对内蒙古民族大学学报（社会科学版）(2020年2期)2020-11-06不确定数据的约束频繁闭项集挖掘算法天津科技大学学报(2018年4期)2018-08-22基于FPGA 的时序信号光纤传输系统电子制作(2017年13期)2017-12-15一种毫米波放大器时序直流电源的设计电子制作(2016年15期)2017-01-15宇宙的尺度太空探索(2016年5期)2016-07-129时代英语·高三(2014年5期)2014-08-26DPBUS时序及其设定方法河南科技(2014年15期)2014-02-27一种新的改进Apriori算法*网络安全与数据管理(2010年1期)2010-05-18分布式数据库的精简频繁模式集及其挖掘算法*浙江师范大学学报（自然科学版）(2010年2期)2010-01-11本文来源：http://www.zhangdahai.com/shiyongfanwen/qitafanwen/2023/0916/654899.html
