基于动态关联规则的TApriori算法

2021-09-26 05:08李文锋陈俊贤
关键词:置信度事务关联

李文锋,陈俊贤

(1.金陵科技学院软件工程学院,江苏南京 211169 2.苏州工业园区服务外包职业学院信息工程学院,江苏苏州 215125)

随着我国轨道交通的快速建设,大量的系统设备已经步入运维管理阶段。然而,由于我国前期重点关注轨道交通系统的系统建设及建设人才的培养,导致现在轨道交通行业在检修运维技术尤其是故障诊断和寿命预测方面的能力差[1],依旧采用传统故障修、计划修手段进行故障判断及处理,维护决策多以人工经验为主,缺乏有效的数据支持和智能化指导[2]。随着大数据时代的到来,信息数据在生活中的作用越来越重要,人们需要高效自动化的数据分析技术对大量冗杂无规律的信息进行分类管理,数据挖掘技术[3-4]应运而生。

Apriori算法[5]是用于寻找给定数据集中元素之间的关联关系的经典算法。在应用过程中,最小支持度和最小置信度的值均是根据人的经验设定。当每个事务中元素数量多时,如果最小支持度、最小置信度设置太低,关联规则会特别多,得到的结果没有价值;当每个事务中的元素数量少时,如果最小支持度、最小置信度设置太高,关联规则会特别少,得到的结果也是没有价值。所以,确定合适的最小支持度和最小置信度的值非常重要。有关Apriori算法进行优化的相关研究成果不少,研究成果主要有对频繁项集进行优化和关联规则优化两个方面。文献[6-7]提出的优化频繁项集方法,对Apriori算法进行优化;文献[8]首先指定一个全局最小支持度 ,然后用该支持度与每步频繁项集的支持度进行比较 ,得到最小支持度。文献[9]采用贝叶斯算法对元素进行预估,得到动态的置信度。文献[10]使用更新的事务和前面阶段的挖掘结果,用Apriori类算法作为局部过程来产生频集。文献[11]利用趋势度方法挖掘出类关联规则集。但是,这些关联规则优化都是通过人工加入或利用历史数据统计最小支持度作为参考数据,在实际频繁项集过程中选用的最小支持度,其本质没有摆脱设定最小支持度和最小置信度值的问题。

轨道交通专用通信系统中的集中告警系统在运维过程中一旦出现故障,手工排除故障是当前轨道交通安全运营的唯一手段[12-14]。集中告警系统虽然采集了大量告警数据,但如何处理并利用相关数据分析预测设备状态和故障,目前还没有成熟的解决方案[15],须通过大数据、人工智能等技术提升设备监测和智能维修管理的能力。目前轨道交通设备的故障关联分析在综合监控专业、信号专业和车辆专业已经开始,但是在通信专业的相关研究刚刚起步。在综合监控专业方面,文献[16-17]主要利用专家知识库在发生的故障时,提供故障的快速定位和处理措施供值班员参考。文献[18]提出构建故障属性集建立样本空间,根据当前监测数据,推断可能跟此故障相关的新故障,供值班人员尽早发现风险隐患,降低运营风险。

本文在不引入历史经验数据及人工加入最小支持度和最小置信度的情况下,利用事务中呈现的数据,动态生成最小支持度及最小置信度,实现轨道交通专用通信系统中的集中告警系统进行故障分析。由于系统的故障跟时间是相关的,任何一条故障一定对应有一个时间属性,而且一些关联故障在时间上具有相近性,因此,本文利用时间属性作为关联故障的特征之一进行研究。

1 TApriori算法

1.1 算法描述

本算法是在Apriori算法的基础上对事务和子数据进行构建,根据给定的事务集的元素计算子数据集的最小支持度和最小置信度,然后计算数据集的最小支持度和最小置信度。具体描述如下:

(1)构建事务。根据事务中元素出现的时间,以固定时间为单位,将固定时间单位内的所有元素构成一个事务。以同样的方式构建其他所有的事务;

(2)建立子数据集。根据事务发生的时间顺序,以固定的连续的时间段为单位,构建子数据集。在建立子数据集时,如果出现某个事务与前后相邻的事务不连续,则其单独建立一个子数据集;

(3)扫描各子数据集事务中各元素的出现次数,计算其在当前子数据集中的最小置信度和最小支持度,找出对应的一元频集;将各子数据集的最小支持度和最小置信度分别求均值,计算出子数据集最小支持度和最小置信度;

(4)产生候选项集。前一频繁项集与自身连接产生候选当前项集;

(5)计算数据集的最小支持度和最小置信度,产生数据集的频繁集。

1.2 相关术语

假设数据集中共有n个元素,m个事务和l个子数据集,则元素、子数据集及数据集的定义如下:

元素,最小的表示单位。一条事务中可能包含一个或多个元素。 Tj= {I1,I2,I3,…,Ii,…,In},Tj表示第 j个事务 (j≤ m),Ii表示第 i个元素(i≤n)。

子数据集Dk。由多条事务组成的集合。

Dk= {T1,T2,T3,…,Tj,…,Tl},Dk表 示 第k(k≤l)个子数据集。

数据集D。是子数据集的集合。D={D1,D2,D3,…,Dk,…,Dl}。

1.3 事务 Tj的构建

构建每个事务时需要对元素进行分类,根据元素的时间属性值将他们划分到不同的事务中。实际在过程中,将第一个元素作为第一个事务的第一个元素,然后顺序取下一个元素,判定是否满足隶属本事务,如果隶属则继续下一条;否则,新构建事务。在事务构建时,首先构建事务T1,选取最早时间出现的元素I1,记录其时间属性值t1,然后选择下一个元素时间属性值与元素I1的时间属性值进行距离运算。用d1i(I1,Ii)表示第1个元素与第 i个元素之间的距离,则可以表示为

当计算结果 d1i(I1,Ii) 为 0,则说明第 1 个元素与第i个元素隶属于同一事务。当计算结果d1i(I1,Ii)不为0,则说明第1个元素与第i个元素隶属于不同的事务,此时构建事务T2,将第i个元素编号重新从1开始,依次重新排序后续元素编号,重复上述步骤,直到下一个事务的元素产生,以此类推,建立所有的事务。

1.4 子数据集 Dk的构建

事务构建结束后,需要进一步构建子数据集Dk,即将多个相似的事务归并在同一类,形成子数据集。在构建过程中,从第一个事务T1开始,计算所有事务Tj与第一个事务之间的距离,将相同距离的事务归为同一子数据集,直到所有事务归到子数据集。

假定每个事务Tj对应的时间属性为tj(j≤m),则任意两个事务 Ti,Tj之间的距离可以用 dij(Ii,Ij)表示

在子数据集Dk构建时,首先选取第一个事务Ti(i= 1) 与事务 Tj(j= 2) 的时间属性进行式(2)计算,如果 dij(Ii,Ij) ≤ C(C 为常量),则将事务 Ti,Tj合并到同一个子数据集中,然后取事务Tj(j=2)对应的下一个事务Tj(j=j+1),重复上述比较过程,直到出现 dij(Ii,Ij) ≥ C。 当出现 dij(Ii,Ij) ≥ C 时,构建下一个子数据集,则将此时的j值赋给i,j取下一个事务对应的值,重复执行上述比较过程,直到所有事务比较结束。

子数据集的数量取决于每个事务的时间属性及C常量。当C设置为60 s时,则将每个事务的时间属性相差间隔小于60 s内的所有事务构成一个数据子集,否则构成新的子数据集。

2 动态关联规则

2.1 子数据集Dk的最小支持度

子数据集Dk的最小支持度用 Sk(IX→ IY)表示,用同时出现IX,IY的事务次数/总的事务次数的比值表示

其中,σ(IX∪IY)表示子数据集中元素IX,IY出现的事务次数,N表示在子数据集中总的事务次数。

对于子数据集任意的IX事务出现的次数,可表示为

其中,Tj表示第j个事务,Dk表示事务的集合。

2.2 数据集的最小支持度

假定数据集D有l个子数据集,则数据集D的最小支持度用所有子数据集Dk的最小支持度Si(IX→IY)之和与子数据集Dk的总数的比值表示,有

用σsdi表示数据集D的最小支持度SD(IX→IY)与子数据集Dk的最小支持度Sk(IX→IY)的差,有

当σsdi<0时,表示子数据集Dk的最小支持度Si(IX→IY)达到数据集D的最小支持度,在生成频繁集时,要参与运算。当σsdi≥0时,表示子数据集Dk的最小支持度Sk(IX→IY)达不到数据集D的最小支持度,在生成频繁集时,不用运算。因此,在数据集D的 n个子数据集的最小支持度中,如果σsdi≥0的总数m越多,需要参与生成的元素数减少,算法运行时间也越短。

2.3 子数据集Dk的最小置信度

子数据集Dk的最小置信度Ck(IX→IY)定义为同时出现IX,IY的事务次数/IX出现的事务次数,有

2.4 数据集的最小置信度

假定数据集D有n个子数据集,则数据集D的最小置信度用所有子数据集Dk的最小支持度Ck(IX→IY)之和与子数据集Dk的总数的比值表示,有

用σcdi表示数据集D的最小置信度CD(IX→IY)与子数据集Dk的最小置信度Ck(IX→IY)的差,有

当σcdi<0时,表示子数据集Dk的最小置信度Ck(IX→IY)达到数据集D的最小置信度,在生成频繁集时,要参与运算。当σcdi≥0时,表示子数据集Dk的最小置信度Ck(IX→IY)达不到数据集D的最小置信度,在生成频繁集时,不用运算。因此,在数据集D的k个子数据集的最小置信度中,如果σcdi≥0的总数k越多,需要参与生成的元素数减少,算法运行时间也越短。

3 性能分析

3.1 频繁集的准确率

为了验证本算法改进后的效果,在实验环境为至强处理器E7、八核、装有Windows Server 2008操作系统的服务器上进行以下试验。利用Apriori算法和TApriori算法在相同的测试数据集基础上产生频繁集时的准确率进行比较,Apriori算法采用的最小支持度和最小置信度分别预先设定为10%、10%进行验证,TApriori算法则根据实际的数据情况动态产生的最小支持度和最小置信度得到各项目频繁集。如图1所示,实验结果表明,在大于2项频繁集时,TApriori算法比Apriori算法更快获得频繁集,且产生的频繁集相同。

图1 准确率比较

3.2 不同关联规则使用的时间

在服务器上分别运行两种算法在不同事务规则的情况下,测试两种算法的运行时间情况。分别假定事务数 5个、10个、100个、1 000个、10 000个,每个事务都有8个元素。实验结果如图2所示。

图2 同事务对应的运行时间

实验结果表明,在事务数量较小的情况下,TApriori算法运行时间与Apriori算法的运行时间相差不大。随着事务数量的增大,TApriori算法运行时间比Apriori算法的运行时间少。

3.3 子数据集Dk最小支持度对速度的影响

在数据集D的l个子数据集的最小支持度中,如果σsdi≥0的总数n越多,需要参与生成的元素数减少,算法运行时间也越短。测试结果如图3所示。

图3 子数据集Dk最小支持度对速度的影响

上图是数据集D中子数据集的个数l不变,减少σsdi≥0的总数n的情况下的实验结果。试验结果表明,随着总数n的增大,TApriori算法在运算过程中使用的时间比较稳定。

4 应用分析

将算法用于轨道交通通信专用系统集中告警系统上,通过对某地铁线路自2017年12月—2020年3月的告警分析。用TApriori算法进行事务的构建、子数据集的构建、数据集的构建,并利用动态关联规则分别计算事务、子数据集及数据集的最小支持度和最小置信度,对系统故障的分析,生成频繁集。表1为构建产生的事务集。

表1中事务列对应的事务序号,元素列对应具体事务中的元素,列表中的每一个字母或字母数字组合表示集中告警收集到的故障告警,每个事务中的元素先后顺序表示该元素产生的时间前后。如事务3中,两个元素A14表示相同时间内出现两次A14故障。事务列中只有一个元素,表示相同时间内当且仅当出现一次故障。其中,事务中元素W,X分别表示在2019-07-22 19:47:31同时出现的故障代码100474和100420故障。元素V表示在2019-07-22 19:47:42出现的故障代码1003CA故障。其他事务及元素表示含义类似。

表1 生成的事务集

通过对以上事务中元素的时间属性进行距离计算,构建子数据集。本实验中采用的固定时间段为3 d,即连续三天内产生的事务集构建成同一子数据组。不在连续三天之内的分别构建不同的子数据集。不同的子数据集通过D后面的数字表示第几个子数据集,事务对应表 1中的事务序号。用TApriori算法构建的子数据集如表2所示。

表2 生成的子数据集

最终生成的二元频繁集如表3所示。

表3 生成的二元频繁集

通过二元频繁集分析,可以知道经常发生故障分别为G、D,G、H,A9、A11 和F、G。 通过对发生的故障实际明细进行排查,由于某站在改造为换乘站后,本站专用电话系统、PIS系统、广播系统、电源系统、专用无线系统设备和系统受网络不稳定的影响,导致各子系统频繁出现故障。

5 结束语

在分析集中告警系统收集的告警数据具有清晰的时间性和地域性特点,本文将收集的告警信息根据时间进行分块,产生子数据集,分别计算各子数据集的最小支持度和最小置信度,然后计算数据集的最小支持度和最小置信度,为集中告警系统数据分析处理提供了动态的关联规则。通过实际线路的数据进行验证,结果表明用TApriori算法可以有效挖掘出系统间的故障关联关系,为系统的故障排除提供了可靠的手段。

猜你喜欢
置信度事务关联
基于数据置信度衰减的多传感器区间估计融合方法
北京市公共机构节能宣传周活动“云”彩纷呈北京市机关事务管理局
一种基于定位置信度预测的二阶段目标检测方法
基于改进乐观两阶段锁的移动事务处理模型
“一带一路”递进,关联民生更紧
奇趣搭配
一种Web服务组合一致性验证方法研究
Hibernate框架持久化应用及原理探析
智趣
校核、验证与确认在红外辐射特性测量中的应用