基于频繁模式的数据有效性评估研究

王志刚，徐 越，梁永春，毛亚琼

(1.青海师范大学, 青海 西宁 810008; 2.华北科技学院, 河北 廊坊 101601)

0 引 言

关联规则最先是由Agrawal等人于1994年针对类似购物篮问题提出的对感兴趣关联模式挖掘的方法。它包括两部分内容，一部分是频繁项的挖掘，另一部分是关联规则的生成。

大数据随着计算机硬件与应用软件的不断更新发展，能够在服务的同时提供更多的内在关联信息，成为了当前知识研究的热点，如电子商城的兴趣推荐、基于用户行为的安全管理、疾病患者的症状预测治疗等等，而利用频繁模式的挖掘对数据有效的利用还没有专门的研究。物联网采集的监测数据为提高数据的有效性，目前有很多方法都对异常数据进行了清洗工作，如对空缺值得插补方法，Rubin利用贝叶斯Logistic进行多重插补。刘燕提出了基于回归的近邻择优补差的方法等。而利用数据产生的规则来研究数据是否存在异常现象具有很大的研究价值。

本文第一步针对数据的连续性与离散型的特点，将特点不同的数据进行离散化处理，得到模式挖掘的基本条件。文献[1]对四种离散化方法进行了比较，包括了贪心算法、基于信息熵、基于属性以及数据挖掘的聚类方法。文献[2]对聚类方法进行了改进，采用不完备集双聚类的方法进行数据处理。第二步是采用滑动窗口的模式对数据进行频繁模式的挖掘。文献[3]利用了数据流任意大小时间窗口关联规则挖掘的方法(mining sliding window，MSW)，是将频繁模式增长(frequent pattern growth,FP-growth)算法改进为频繁模式树算法FP-tree之后进行关联规则的挖掘。第三步是本文提出的对有效性的计算与评估。创新点在于，利用高斯公式对频繁模式的衰减因子计算的方法对窗口事务重要性进行衰减分析，结合时间衰减与窗口化频繁模式的方法退出对数据属性在关联规则基础上的数据可信评价的方法。

1 基于时间滑动窗口的频繁模式挖掘

主要介绍了频繁项集与关联规则的基本概念，并对物联网监测数据的滑动窗口提出物联网数据流的滑动窗口树(internet of things sliding window tree,ISW-tree)。

1.1 概念

(1)项、项集与频繁项集定义：项表示数据源监测指标的某个取值或某个区间段的统称；项集是项的集合，包含N个项的项集称为N项集；支持度大于最小支持度阈值的项集称为频繁项集。

(2)支持度定义：支持度是两个项或项集是否频繁的有效监测指标，计算公式为：

式中，Support(X⟹Y)表示X,Y同时发生的支持度，Support_count(X∩Y)表示X,Y一起出现的记录数量，Total_count表示数据记录总数。

(3)置信度(Confidence)定义：置信度是衡量两个项或项集之间的关联程度的有效监测指标。

Confidence(X⟹Y)

有效关联规则的提取是需要事先确认最小支持度min_sup与最小置信度min_con。并且在数据有效性可信度分析中，监测指标的各个项都是非空值，因为这在常规的数据异常处理都会填充可信任数值或者直接判断为无效数据。

1.2 离散化数据

利用关联规则无法直接处理连续型数据，若为连续型数据则需要对此类数据进行离散化处理。有行业规则的根据行业规则对指标区间符号化，无行业规则数据需要进一步探索来划分。聚类算法可以适用于大部分数据源分类情况，优点是能够根据需求聚类出相似相近的数据集合。采用K-means聚类算法计算每个数据区间的权重，算法步骤如下：

第一步，将监测指标X的取值划分为K个数据区间，即将指标离散化为{X1,X2,…,Xi…XK}，由K个指标项组成的建模数据。

第二步，从某指标整体数据中随机找出K个数据做为K个数据初始区间的重心；再根据这些重心的欧几里得距离对所有对象聚类；如果数据x距重心Xi最近，将x归为Xi所代表的那个区间，并记为xiTi，据值j是对应每一次出现的数据标号，范围为[0,n]。

第三步，重新计算各区间的重心，并利用新的重心重新聚类所有样本。

第四步，数据源中的数值xiTi表示在Xi这个离散化区间的某一个数。那么分布在Xi这个区间的数量为num(Xi)，Sum(Xi)为数据源的数据落在监测指标X的所有区间的总数量：

1.3 滑动窗口内的频繁模式

采用基于数据流的滑动窗口对频繁模式的挖掘，利用对频繁模式树结构算法FP-tree的改进和利用提出的滑动窗口树结构ISW-tree ，更新了存储结构，具体有以下两点不同：

(1)在频繁模式FP-tree上包括根节点(Root)、单独事务(item)、事务数(count)，现在此基础上增加时间戳的记录标识(TID)；(2)在FP-tree树结构节点都按照事务的支持数的采用降序排列，针对传统物联网数据采集指标的特殊性，ISW-tree采用的排列方式即指标列表的固定排序方式。

正是由于这种固定的节点排序方式，使得节点之间的排列数序固定不变。这对基于时间的物联网监测的数据流来说，能够保证不用维护像FP-tree树结构基于节点支持数采用流动窗口时需要不断变化动态结构，因此ISW-tree能够更好地减少不断改变结构付出的代价。其次，虽然FP-tree的结构在寻找频繁项集上比Apriori更少地对数据库进行扫描，但对于庞大的数据来说，扫描两次数据库仍然会对系统带来很大的负荷，而ISW-tree由于固定指标节点顺序，为此可立即将新的数据流加载到滑动窗口。

2 衰减模型的应用

依据数据流的动态特性特点，传统的挖掘方法并不能适应于这样的流环境中[2]，有以下三点原因：(1)处理数据的设备内存空间有限，数据量很大就不能实现将所有的频繁模式都挖掘出来；(2)不能体现实时性，数据量的大小不能合理控制，导致精度和自适应能力差；(3)不能够获得数据流的先验模式，不具有模式指导意义。因此要通过窗口与时间衰减模型的结合来适应在动态环境下的高效挖掘方法。

采用时间衰减模型TDM(time decay model)对窗口的旧事务的支持数占有的权重进行衰减操作，以此来降低历史事务对产生新模式支持数的影响。当任意单位时间内的事务到达窗口时，其单位时间内的衰减程度系数用f(拉姆达)来表示，范围为(0,1]。那么模式P在任意时间点到达的支持度计数可以表示为fre(P,Ti),此时当第i个事务到达窗口时，新的模式支持度计数可以用下面式子表示，即：

衰减因子的确定关系到衰减程度的大小，是基于时间滑动窗口筛选频繁项集确定支持度计数的重点。文献[4]中对比了目前的衰减因子不同计算方法的优劣，并且得出采用高斯函数的方法最能强调最近事务的重要性，并分析了高斯函数中参数的设置方法，为此采用高斯衰减因子fg满足物联网采集数据有效规则分析的实时性要求。如表1与图1是关联规则树结构ISW-tree算法示例：

表1 规则示例表

Itemscountx11.8x22.0406y13.541824y21z12.44z22.2096

图1 频繁模式树

3 关联规则的有效可信系数的划分与规则可信评估

利用ISW-tree通过构造滑动窗口的树结构将项集列出来，首先找出所有的频繁模式，然后利用本研究所需的对某一指标的置信度需求，找出所有支持Xi的所有条件集合，且数量总数记为m。

例，集合U是上述示例数据源7条基于时间序列的项集，求X1在Y1Z1条件下的可信度：

U1={(x11y11z11)，(x12y12z12)，(x13y13z13)，(x21y14z14)}，此时X2Y1的衰减支持数为最新的计数1.64，Z2支持数1，从而置信度为：

这就是求得的一条规则的置信度结果，而在大量数据中会出现多个支持规则Z2的集合，单个集合表示为Uk，若总共有m个，下面将对这m个规则不同置信度结果进行可信系数的划分。

首先对置信度的区间进行划分，求得的置信度范围在区间[0,1]，将此区间再划分为三个区间，即不可信区间UI(Untrusted interval)，弱可信区间WCI(Weak confidence interval)，可信区间CI(Confidence interval)。根据不同用户对置信度的要求高低，可对置信度区间取值范围进行伸缩设置。

可信系数定义，即根据项集规则挖掘时置信度的结果不同，对支持某个监测指标出现在三个不同置信区间时进行系数划分，得到的系数即为可信系数CC(Confidence coefficient)，取值范围为[-1,1]。利用可信系数的正负值划分来进一步确认指标有效的可信程度。

单个项集的可信系数用CC来表示。因此，当规则存在于可信区间CI时，且置信度越高， 越接近1。反之，在UI区间时，得到的可信系数越接近-1，对即将计算的有效可信度也越低。对于处于弱可信区间WCI的收集规则数据来说，大多接近于0，可信度在模糊区间，因此需要用其它方法来进一步验证有效性。

利用CC表示某一指标值下所有支持该指标值的集合的可信系数，那么区间数据的可信系数和SOC(Sum of Coefficients)可表示为：

那么，监测指标X的整体基于关联规则的有效可信度结果表示为：

4 结束语

通过频繁项集的引入，利用数据关联规则的可信度来对数据关联关系有效性评估进行研究。重点利用了对采集物联网数据的滑动窗口ISW-tree以及在流动的时间序列下的采用高斯函数的衰减支持度计数方法，对物联网数据有效内在隐性规律挖掘。本理论依然具有可拓展性和进一步探索的方向，一是对数据关联规则的研究可拓展到多个邻居节点或者是逻辑相邻节点进行研究；二是在可信区间划分并没有确切可靠的区间定位，往往由专业人员根据需求辅助确定，也可通过机器学习以及博弈论等方法对不同领域对区间提出划分方法，权衡付出的代价和得到的收益并进一步计算出最优结果，提高数据有效性。数据有效性是提高数据质量的基础，数据只有在较高的可信度和可靠度的情况下才能为社会带来巨大的效益。