基于混合蚁群关联规则挖掘的危险源分析算法

佘雅莉，周 良

(南京航空航天大学 计算机科学与技术学院，江苏 南京 210016)

0 引 言

在民用航空空中交通安全管理体系中，危险源识别和风险评估是重要的组成部分。对危险源进行详细地分析并得到其产生的原因和作用机理，是相关部门对风险进行有效准确评估的前提。在传统的危险源分析体系中，使用事件树分析法、蝶形分析法、危险与可操作性分析法进行危险源的分析；现在，国内外专家和学者提出了很多不同的分析方法，但大都在传统的分析体系上建立。Katrina Groth等提出了一种混合的分析方法，将事件树、故障树和事件序列图相结合对危险源中决定性因果路径进行分析[1]，并利用贝叶斯网络对非决定性因果关系进行分析；Leon Purton等在蝶形分析法的基础上[2]，引入技术完整性的概念，在危险链中引入技术生命周期：设计、生产和维护。这些方法可以从不同的侧面对危险源的原因进行分析，但是缺乏全面性。为此，需要一种能够较全面且客观分析危险源的方法。

危险源原因分析的过程就是在危险源数据库中找到不安全事件X，使得X与危险源Y之间满足X→Y的蕴涵关系。根据关联规则的定义可知，这恰恰就是在危险源数据库中对危险源与不安全事件进行关联规则挖掘的过程，因此可以借助关联规则挖掘实现对危险源的原因分析。关联规则挖掘是数据挖掘中的一个重要领域，它能够发现数据库中项目之间的隐含关系。自1993年被提出后，人们提出了很多相关算法，这些算法通过发现数据库中的频繁项目集来发现关联规则[3]。Apriori算法[4]、频繁模式树算法[5]等都是传统的经典关联规则挖掘算法，但它们存在频繁扫描数据库、产生大量候选集等不可避免的缺陷。因此，许多改进算法被提出。例如，Du等[6]提出了一种改进的Apriori算法，通过重构数据库中的数据，增强项目集之间的联系，使得算法能够直接通过剪枝操作得到候选集，从而减少对候选集的验证过程。不仅如此，具有较高搜索效率的群智能算法也被应用到关联规则的挖掘中，Jitendra Agrawa等利用基于集的粒子群优化算法挖掘数据库中的正关联规则和负关联规则[7]；Zhou等将粒子群优化算法与引力搜索算法相结合挖掘关联规则[8]；文献[9]提出结合遗传算法和蚁群算法进行关联规则挖掘，其中心思想是利用遗传算法优化蚁群算法的参数。该方法确实取得了较好的性能，但是蚁群算法的初始信息素浓度仍然没有确定，使蚂蚁在初始时刻没有方向，消耗较多时间。

随着混合智能算法的兴起，加上蚁群算法易于与其他算法结合的特点，文中设计了一种基于混合蚁群关联规则挖掘的危险源分析方法。在该方法中将危险源事务数据库进行预处理，转换为一个二进制矩阵，利用粒子群挖掘出定量的频繁项集，从而确定蚁群的初始信息素浓度，进而进行最大频繁项集挖掘，并由最大频繁项集产生强关联规则，分析危险源原因。

1 HA-MACR算法总体思路

在国际民航组织安全管理手册和国内民航空中交通管理安全管理体系(SMS)建设指导手册中，危险源的原因分析都是对不安全事件的分析，在人为因素分析的基础上，对不安全行为、不安全行为的前提条件、设备设施、监督管理和组织因素等方面进行分析。关联规则有如下定义：设I={i1,i2,…,in}是一个项目集，事务数据库为D，事务数据库中的每个事务T都是项目集的一个子集T⊆I，关联规则具有如下形式X→Y，其中X⊆I，Y⊆I并且X∩Y=∅。由定义可以看出，关联规则就是发现事务数据库中项目的隐含模式，当某些项目X出现时，另一组项目Y也会同时出现。这个过程可以与危险源的原因分析相结合，因此，文中提出利用关联规则分析危险源原因。

HA-MACR算法将该分析过程分为3部分：一是危险源状态信息预处理过程；二是挖掘最大频繁项集；三是产生强关联规则从而得到导致危险源的不安全事件。关联规则挖掘过程主要分为两个步骤——发现频繁项目集和产生强关联规则[10]。其中，发现频繁项目集是关键，对算法的性能有着决定性的影响，故考虑在该步骤进行优化。于是，在第二步中先由粒子群找出固定数量的频繁项集，从而确定蚁群算法的初始信息素浓度，以期改善单纯用蚁群算法进行挖掘的盲目性，再利用蚁群算法挖掘最大频繁项集。整个算法流程如图1所示。

图1 HA-MACR算法流程

1.1 数据预处理

算法开始前，需要对原始数据进行预处理，将其转换为一个二进制矩阵。在危险源原因分析中，给定事务数据库为包含危险源和不安全事件的危险源事务数据库，将其记作D。在预处理阶段，将D中每条记录转换成0-1向量，这样便于计算支持度与置信度，同时可以提高数据库扫描速度。下面以图2为例具体解释转换方法。图2左边是原始数据，共有4条记录，可以看出数据库中共有五个项目集，向量长度为5。以T1为例，它包含I1，I2和I5，因此，I1，I2和I5对应位置置1，I3和I4对应位置置0。以此类推，最终构成一个4行5列的二进制矩阵。

图2 数据预处理

1.2 信息素初始浓度确定

蚁群算法的参数确定一直是其应用中需要解决的一个问题，尤其是初始信息素浓度的设置对算法性能有着重要影响。为了在一定程度上避免盲目性和提升搜索效率，HA-MACR算法首先借助粒子群的更新迭代，得到一定量的频繁项集，从而更合理地设置本算法的初始信息素浓度。将项集看作粒子群中的粒子，对应于数据预处理后的二进制矩阵，把粒子位置设为0-1向量。随机生成粒子的初始位置和速度，但需要注意的是，必须保证粒子代表的项集是频繁的，若不是则需要重新生成。

综合考虑频繁项集的项目个数和支持度计数两个因素，粒子的适应度函数设计如下：

(1)

其中，|x|为粒子向量维数，即对应项集的项目个数；count(x)表示该项集的支持度计数；参数W1、W2分别用于控制这两个因素对于适应度函数的影响程度。

由于粒子群算法中每个粒子都有记忆功能，可以记忆自己从初始时刻到当前时刻适应度最好时的位置。个体极值就是粒子彼时的适应度函数值，而全局极值就是所有粒子个体极值中的最优值。按式1计算粒子适应度函数并更新粒子个体极值xpbest和全局极值xgbest。有了个体最优位置和全局最优位置，就可以更新t时刻粒子位置，公式为：

k2r2[xgbest(t)-xj(t)]

(2)

xj(t+1)=xj(t)+vj(t+1)

(3)

其中，vj(t)和xj(t)分别是第j个粒子迭代t次后的速度和位置；w是惯性系数，随迭代次数增加而减小；k1、k2是学习因子。

但是，这样得到的位置不是0-1向量，所以还需要用式4进行转换。

(4)

其中，r3为[0,1]之间均匀分布的随机数；sig()为sigmoid函数。

重复上述过程，直至迭代结束或达到最大迭代次数，输出所有xgbest(t)。由此计算危险源和不安全事件组成的项集中项集i、j同时被选择的次数，即2-项集支持度计数，由此确定信息素初始浓度，如式5所示。

τij(0)=τmax-τmin+scij

(5)

其中，τmax和τmin分别表示信息素上限和信息素下限。

1.3 挖掘最大频繁项目集

在上一阶段，主要完成了对蚁群算法的初始信息素浓度的确定，接下来可以开始用针对危险源原因分析改进的蚁群算法挖掘关联规则中的最大频繁项目集。类似于用蚁群算法寻找最优路径[11]的过程，用一个禁忌表(Tabu)存放蚂蚁在后续搜索中不能选择的数据项，用一个可选表(Allowed)存放它还可以选择的数据项。初始时刻，将各个蚂蚁随机地置于不同数据项作为出发点，并将该数据项添加到存放已选数据项的集合fk中和禁忌表中。然后，计算出剩余所有可选数据项的概率转移函数值，如式6所示，并据此选择下一个项。

(6)

其中，τj(t)是t时刻的信息素浓度；ηj(t)为启发函数。

τij(t)=(1-ε)·τij(t)+ε·Δτij(t)

(7)

(8)

(9)

若加入j后fk不是频繁项集，则把j从fk中删除，并根据式10决定是否继续搜索。

(10)

其中，p是[0,1]上的随机数；p0是[0,1]间的一定值。若stop(k)=1，则停止搜索；若stop(k)=0，将项目集j放入禁忌表并从allowed表中剔除后继续搜索。当所有的蚂蚁都完成了一次遍历后，记录本次遍历所找到的最大频繁项集。这样就完成了一次迭代。

但是在下一轮迭代开始之前还有一项很重要的工作要做，那就是信息素的全局更新，这正是蚁群算法具有正反馈性的关键。蚂蚁完成一次搜索后，对于本次迭代中最优频繁项集中的点所构成的边进行信息素更新[12-13]，方式如下：

(11)

1.4 产生规则

得到最大频繁项集后，便可以很容易地产生其对应的强关联规则，主要分为两步：

(1)求出最大频繁项集的所有非空真子集；

(2)设X、Y为步骤1中所得任意子集，若X∩Y=∅且count(X∪Y)/count(X)≥min_conf，则有强关联规则X→Y。

2 实验结果与分析

实验采用民航空管局安全管理系统的危险源事务数据库，并按1.1节所述数据预处理过程进行二进制转换。从算法运行时间和产生的规则质量两个角度对算法进行对比实验，实验环境为Intel core i7 2.6 GHz Window7及MatLab 2014Ra。为了保证算法初始随机性对结果的影响，取20次实验的平均结果进行衡量。运行时间很好衡量，而规则质量，参考文献[14]中对规则质量的计算方法，比值越大，质量越好。最终得到的危险源原因分析结果如表1所示。

表1 危险源原因分析结果

由于HA-MACR算法中有一些参数不确定，这些参数对算法性能有一定程度的影响，故在不同取值下分别对算法执行20次，选取平均结果较好的参数组合，实验结果如表2所示。由结果可知，当α=2，β=1时，算法效果较好，故以下实验将设为该值。

表2 参数组合

同时根据文献[15-16]，算法其余参数设置如表3所示。

表3 参数取值

实验比较了不同支持度下Apriori算法和HA-MACR算法的平均规则质量，结果如图3所示。可以看出，HA-MACR产生的规则质量均较好。

图3 规则质量比较

另外，实验比较了不同支持度下Apriori算法和HA-MACR算法的平均运行时间，结果如图4所示。可以看出，HA-MACR算法运行速度远远快于Apriori算法，而且Apriori算法随支持度降低运行时间大幅上涨，变化很大，这是由于产生的候选项集增多引起的计算量增大。而HA-MACR算法由于先利用粒子群合理设置了信息素浓度，而后蚁群算法挖掘最大频繁项集时也受到信息素的指导，所以不会出现这种情况，运行时间较稳定，即使支持度阈值设置得很小也不会出现运行时间剧增的情况。

图4 运行时间比较

3 结束语

针对危险源原因分析中存在的分析主要依赖人的参与和传统关联规则挖掘算法中候选集过多影响挖掘效率的问题，提出了一种基于混合蚁群关联规则挖掘的危险源原因分析算法HA-MACR。该算法通过引入粒子群优化蚁群初始信息素浓度，根据频繁项集来确定，避免了蚁群算法初始时的盲目性，有效提高了危险源原因分析的效率与质量。实验结果表明，该算法充分利用了蚁群优化算法的寻优能力和正反馈性，将其应用于对危险源原因的分析过程中，通过挖掘到的最大频繁项集产生质量较好的关联规则，进而得到分析结果，不仅提高了关联规则的挖掘效率，同时也能有效提高危险源原因分析的准确性和执行效率。