基于片段聚类的序列数据关联规则挖掘方法

摘要

本发明涉及一种基于片段聚类的序列数据关联规则挖掘方法，属于计算机学科下的数据挖掘领域。实现步骤为：设定参数；使用滑动窗口算法，将原始序列数据划分为子序列集合，并将每一子序列进行归一化；使用k‑means算法对子序列进行聚类，聚类过程中使用DTW算法计算各子序列与中心点间的距离；对聚类结果进行合并，将聚类结果形成一个有序事务集T；基于事务集T，生成频繁项集，并生成关联规则；根据每一条关联规则的置信度，对关联规则进行筛选和应用。

说明书

技术领域

本发明属于计算机学科下的数据挖掘领域，具体涉及一种针对序列数据中具有相同变化趋势的序列片段间的关联规则挖掘方法。

背景技术

关联规则分析能从大量的事务集中挖掘其中的相关关系、揭示事务集中的潜在关联关系。关联规则挖掘能够关联规则挖掘发现大量数据中项集之间有趣的关联或者相互联系，但一般来说是对于事务自身数据的频繁项集进行挖掘。而时间序列预测一般采用回归预测的方法分析时间数列，从中寻找序列中随时间变化而变化的规律，但对于子序列间的相关和关联关系挖掘较少。

序列数据中的变化趋势指的是序列或者某些子序列中的数据升降变化的规律，如先升后降、升多降少等，具体来说序列的趋势就是对这些序列的进一步抽象，是一种更高层次的聚合，相同内容的多个事务，在不同的上下文中会表现出不同的趋势；同理，不同的多个事务序列，也可能表达相近的趋势。

在时间序列中，不同的变化趋势表达为不同的数据曲线形状，但经常会有多个序列具有非常相似的形状，但是这些形状在x轴上并不是对齐的，也就是说，相似的两段时间序列的长度可能并不相等，在这种情况下，使用传统的欧几里得距离无法有效地求的两个时间序列之间的距离。因此，在比较两个子序列间的相似度之前，需要将其中一个或者两个序列在时间轴下扭曲，以达到更好的对齐。DTW(Dynamic Time Warping，动态时间归整)算法可以通过找到这两个波形对齐的点，DTW通过把时间序列进行延伸和缩短，来计算两个时间序列之间的相似性。

本发明主要针对序列数据中具有相同或相近的变化趋势的不同序列片段，分析这些片段间是否具有一定的关联情况，以及序列中某个变化趋势或者多个变化趋势的发生是否能引起另外一个趋势的发生。但在现有文献中，针对序列数据进行片段化聚类并以此为基础进行关联规则挖掘的文献很少。

发明内容

有鉴于此，本发明提出一种基于片段聚类的序列数据关联规则挖掘方法，用于挖掘序列数据中的序列或子序列的趋势间的关联模式，将序列中的子序列片段进行聚类后，合并为几种序列趋势分类，然后对序列的趋势进行关联规则挖掘，最终找出不同序列的变化趋势中的关联或相关联系。

基于片段聚类的序列数据关联规则挖掘方法，实现的技术方案如下：

步骤一、设定滑动窗口大小w，聚类个数clusterNum、迭代次数num_iter、阈值mDtw；

步骤二、根据w，使用滑动窗口算法，将原始序列数据S划分为子序列集合subS；

步骤三、将每一个子序列进行归一化，归一化的方法如公式(1)所示，

其中，针对每一子序列，vMax和vMin为该子序列的最大值和最小值，v为子序列中的值；

步骤四、使用k-means算法对子序列进行聚类，聚类方法如下：

步骤4.1、随机选择clusterNum个中心点，命名第i个类的中心点为O

步骤4.2、令迭代次数k＝0；

步骤4.3、针对每个子序列，使用DTW算法计算该子序列与每一个中心点O

步骤4.4、将每个子序列分配给DTW距离最小的中心点所属的类；

步骤4.5、对每个类，计算该类中的所有子序列的均值O

步骤4.6、计算每个类的子序列均值O

步骤4.7、令k＝k+1，假如k大于等于num_iter，则执行步骤五；假如k小于num_iter，则执行步骤4.8；

步骤4.8、假如距离

步骤五、对聚类结果进行合并，将聚类结果形成一个有序事务集T；

步骤六、基于事务集T，生成频繁项集，并生成关联规则；

步骤七、根据每一条关联规则的置信度，对关联规则进行筛选和应用；

至此，基于片段聚类的序列数据关联规则挖掘方法结束。

有益效果：

本发明所提出的方法，能够针对序列数据中的变化趋势间的关系挖掘其关联规则，并将其应用于时间序列数据的片段关联性挖掘中。

附图说明

图1为本发明的流程图

图2为基于DTW算法的序列规整图

图3为滑动窗口w＝5，clusterNum＝9的聚类效果

图4为对表2中的第一行

具体实施方式

下面结合附图并举实施例，对本发明进行详细描述，以图1为例，实现基于片段聚类的序列数据关联规则挖掘方法的技术方案如下：

步骤一、设定滑动窗口大小w，聚类个数clusterNum、迭代次数num_iter、阈值mDtw；

本实施例中，所采用的数据集为空气质量数据，并选择PM2.5、PM10、NO2、CO、O3以及SO2六种特征形成多元序列数据，设定滑动窗口大小w＝5，聚类个数clusterNum＝9、迭代次数num_iter＝100、阈值mDtw＝0.1；

步骤二、根据w，使用滑动窗口算法，将原始序列数据S划分为子序列集合subS；

步骤三、将每一个子序列进行归一化，归一化的方法如公式(1)所示，

其中，针对每一子序列，vMax和vMin为该子序列的最大值和最小值，v为子序列中的值；

步骤四、使用k-means算法对子序列进行聚类，聚类方法如下：

步骤4.1、随机选择clusterNum个中心点，命名第i个类的中心点为O

步骤4.2、令迭代次数k＝0；

步骤4.3、针对每个子序列，使用DTW算法计算该子序列与每一个中心点O

步骤4.4、将每个子序列分配给DTW距离最小的中心点所属的类；

步骤4.5、对每个类，计算该类中的所有子序列的均值O

步骤4.6、计算每个类的子序列均值O

步骤4.7、令k＝k+1，假如k大于等于num_iter，则执行步骤五；假如k小于num_iter，则执行步骤4.8；

步骤4.8、假如距离

本实施例中，滑动窗口w＝5，clusterNum＝9的聚类效果如附图3所示；

步骤五、对聚类结果进行合并，将聚类结果形成一个有序事务集T；

本实施例中，把六种序列的聚类结果进行合并，形成一个事务集，具体格式如表1所示，

表1 合并的事务集格式

合并各个序列的聚类结果类似事务集dataSet＝[[4，4，1，8，0，7]，[4，4，1，8，0]，[4，4，2]，[4，4，8，2，3，2]，[8，6，7，1，2，4]，[8，6，7，5，1，4]，[8，6，1]，[5，6，0，5，0]，[0，5，6，0，5，0]，[0，5，6，0，3，0]，[0，5，6，0，3，0]，[0，5，6，6，3，0]，[0，3，5，0，4，0]，[0，5，5，0，7，0]]；

步骤六、基于事务集T，生成频繁项集，并生成关联规则；

本实施例中，最小支持度min_support＝0.07，最小置信度min_confidence＝0.6，对滑动窗口w＝5进行关联规则分析，由于产生的频繁项集较多，置信度最高的15项规则如表2所示，

表2 滑动窗口w＝5的部分关联规则表

步骤七、根据每一条关联规则的置信度，对关联规则进行筛选和应用；

本实施例中，对表2中的第一行进行趋势分析，如附图4所示，第2，3，5类同时发生的情况下第1类发生的置信度为1，表明该子序列趋势肯定会发生；同样对第三行进行趋势分析，第4，5类同时发生时第7类发生的置信度为0.818，表明该序列趋势发生的概率很大；

至此，基于片段聚类的序列数据关联规则挖掘方法结束。