基于支持度矩阵Apriori 算法的钻井隐患关联挖掘

2022-04-23黄丹李文璟

西南石油大学学报(自然科学版) 2022年2期

王兵，黄丹，李文璟

西南石油大学计算机科学学院，四川成都610500

引言

钻井是石油开采的重要过程之一，在作业过程中存在着较多可能导致意外事故的安全隐患，随着科学技术的进步和生产力水平的提高，石油安全生产也得到了高度关注和重视[1]。钻井作业安全隐患是导致事故发生的重要因素之一，系统化的钻井安全隐患管理应用越来越广泛。在日常安全检查、隐患排查以及标准化建设过程中积累了大量的隐患数据信息。然而，“数据丰富，信息匮乏”的问题依然存在，在实际作业中，大多数企业仅能利用这些数据进行指导隐患整改工作[2]。为了从海量的安全隐患数据中提取出有用的安全管理信息，解决人工分析数据效率低、主观性强等问题，为管理者提供针对性的辅助决策，将数据挖掘技术应用于事故隐患预警过程中[3]。

关联规则挖掘算法是数据挖掘领域中一个重要的研究方法，其目的是挖掘事务数据库项目集之间的隐藏信息，为用户在决策时提供理论支撑[4-5]。Apriori 算法是数据挖掘算法中关联规则发现的经典算法，是挖掘布尔型关联规则频繁项集的最重要算法之一。该算法采用逐层搜索的迭代方法，利用k-项集探索（k+1）-项集来生成频繁项集，并引入了频繁项集性质的先验知识以减少搜索空间。但该算法存在两个性能瓶颈：一是数据库需频繁扫描导致I/O 负载过大；二是会产生大量的候选项集，且处理候选项集的时间开销大，使算法效率降低[6]。

针对以上问题，许多学者提出算法的改进方法。Han 等提出了基于模式增长的FP-Growth算法[7]，该算法参考Huffman 树结构，将数据集存储于FP 树结构上后挖掘频繁项集,只需扫描两次数据库，在一定程度上提高了算法的执行效率；但随着项集数目的增加，构建FP 树的难度增加。Yang 等提出了基于矩阵的Apriori 算法[8-9]，只需扫描一次数据库来生成布尔矩阵，算法的剪枝操作都在矩阵上实现，减少计算成本。杨秋翔等提出了一种基于权值向量矩阵约简的Apriori 算法[10]，通过引入权值和矩阵约简的方法，降低了源数据及候选项集的规模；但该算法在执行前需要对源数据进行筛选，前期工作量较大。Wang 等提出了基于压缩矩阵的改进Apriori 算法[11-15]，利用矩阵有效地表示数据库中的事务，并使用“与”运算处理矩阵，该算法只需扫描一次数据库且减少了候选项集的数量；但由于在压缩矩阵过程中数据丢失的问题，将导致频繁项集遗漏的问题。

为此，提出了支持度矩阵优化频繁项集的改进Apriori算法—MM-Aprior（iMatrix Multiplication Apriori）算法。该算法使用布尔矩阵来表示事务数据库，利用事务矩阵乘法来构造支持度矩阵，进而获得支持度计数，简化了支持度的计算方法，并改变了原算法的自连接方式，在解决频繁项集遗漏问题的同时进一步提高了算法的执行效率。

1 基于关联算法的钻井隐患挖掘

1.1 Apriori算法

Apriori 用于挖掘频繁项集并生成关联规则。该算法运用逐层搜索的迭代方式，通过连接和剪枝两步，由频繁k-项集探索生成频繁（k+1）-项集，直至找到最大频繁项集[16]。Apriori 算法包含了支持度和置信度两个重要的概念，支持度是指在所有事务中频繁出现项集的频率，P(X∪Y)表示事件X和Y同时发生的概率，它反映了此关联规则的重要性。置信度是指事件X发生时事件Y也同时发生的概率P(Y|X)，它是关联规则准确性的度量[17]。同时满足最小支持度及最小置信度的规则在关联规则挖掘中称为强关联规则。通常分为频繁项集的生成及由频繁项集产生强关联规则两个主要步骤。

Apriori 算法的具体操作[18-19]步骤为：

（1）扫描初始事务数据库，计算出每个项目支持度，满足最小支持度的项目生成频繁1-项集L1。

（2）连接步骤操作：利用Lk自连接生成候选k-项集Ck。

（3）剪枝步骤操作：利用先验性质对Ck进行剪枝操作，若候选k-项集的（k−1）-项的子集不在Lk−1中，则该候选k-项集也不是频繁项集，因此可从Ck中直接删除。

（4）反复迭代操作，直至不能找到频繁k-项集为止。

（5）产生规则：从得到的频繁项集中找出所有满足最小置信度的规则。

1.2 钻井隐患数据关联挖掘

为实现石油钻井生产过程中不同的安全决策需求，通过传统关联算法（如Apriori 算法、FP-rowth算法）来挖掘钻井事故和复杂情况关联规则，且将获得的关联规则作为钻井预警与分析模块的知识，为钻井事故和复杂情况的预防和处理提供很好的依据，钻井安全隐患关联挖掘流程如图1所示。

图1 钻井安全隐患关联挖掘流程Fig.1 Flow chart of associated mining of drilling safety hazards

钻井历史隐患数据具有海量性与复杂性的特点，因此在利用数据挖掘技术前，首先，要对数据进行数据预处理；其次，使用关联算法挖掘钻井隐患事务中的关联规则，进而获得潜在的强关联规则；最后，分析强关联规则进行关联隐患挖掘，根据频繁前项发生再映射到对应关联规则，从而预测频繁后项的发生，以此获取预测知识。

2 改进算法MM-Apriori

2.1 算法改进思想

改进算法的相关定义：

定义1设矩阵，则为矩阵A与B的Hadamard 积。

定义2矩阵乘法。在迭代过程中，给定一个布尔矩阵，通过该矩阵的转置乘以矩阵Ak（k=1，2，···），得到对称矩阵Dk，记作，其中矩阵Dk中的第i行第j列元素可以表示为：，则矩阵Dk中的第i行第j列元素的值表示对应项集的支持度计数，特别的，对角线上的值为各k-项集的支持度计数。因此，Dk也称为支持度矩阵。

定义3设事务数据库包含n个事务和m个项目，则可构造布尔矩阵，也称为初始事务矩阵A1，即项集的矩阵表示为

定义4若有事务项的长度小于2，则可以将事务矩阵中所对应的行向量删除[20]。

定义5若某频繁k项集集合中项集的个数小于k+1，则该频繁项集为最大频繁项集[21]。

改进思想如下：

（1）利用支持度矩阵得到频繁项集。基于传统的矩阵改进Apriori算法中利用向量的逻辑“与”运算来计算支持度的思想，引入了支持度矩阵来得到支持度。利用定义2中的矩阵乘法，可一次性得到矩阵中所有项集向量的支持度计数。扫描事务数据库得到事务矩阵A1，在迭代过程中，通过该事务矩阵的转置乘以矩阵Ak，得到支持度矩阵Dk。支持度矩阵Dk中的值表示各个项集的支持度计数，特别的，对角线上的值为各k-项集的支持度计数。其中，将各k-项集的支持度计数与设置最小支持度阈值比较可得到频繁k-项集Lk。支持度矩阵Dk上三角（下三角）中的值满足最小支持度计数的（k+1）-项集即为频繁（k+1）-项集Lk+1。

（2）连接操作。在迭代过程中，使用频繁项集Lk+1及事务矩阵，构造出两个矩阵，将得到的两个矩阵利用定义1通过Hadamard 积运算，即可得到事务矩阵Ak+1。

（3）矩阵的约简。通过m×n的事务矩阵Ak+1乘以m×1的全1矩阵，得到各个事务的事务长度。再根据定义4若事务长度小于2时，删除该事务所对应的行，从而简化事务矩阵，得到Ak+1′。

通过上述操作，达到了不产生候选项集直接生成频繁项集且逐步简化事务矩阵的目的，极大地提高算法的效率及生成频繁项集的速度。

2.2 算法流程

算法流程如下：

（1）生成频繁1-项集。①扫描初始事务数据库，并用布尔矩阵来表示，其中行表示事务，列表示项目，得到挖掘对象事务矩阵A1。②根据用户设定的最小支持度，确定最小支持度计数。利用事务矩阵A1的转置乘以事务矩阵A1，即得到支持度矩阵D1。支持度矩阵D1的对角线上的值对应为各1-项集的支持度计数，提取出满足最小支持度计数的1-项集，从而得到频繁1-项集L1。

（2）生成频繁2-项集。①提取支持度矩阵D1的上三角（下三角）中满足最小支持度计数的2-项集，从而得到频繁2-项集L2。②使用频繁2-项集及矩阵A1构造两个矩阵C1与C1′。将矩阵C1与C1′进行Hadamard 运算，即A2=C1°C1′，得到事务矩阵A2。③通过m×n矩阵A2乘以n×1的全1矩阵，可计算出各个事务的事务长度。再根据定义4对矩阵A2进行简化，从而得到矩阵A2′。

（3）生成频繁k-项集。①利用矩阵A2′的转置A2′T乘以矩阵A2′得到支持度矩阵D2，即提取D2的上三角（下三角）中满足最小支持度计数的的3-项集，从而得到频繁3-项集L3。使用频繁3-项集及矩阵构造A2′两个矩阵C2与C2′。将矩阵C2与C2′进行Hadamard 积运算，即A3=C2°C2′，可得到事务矩阵A3。②通过m′×n′的矩阵A3乘以n′×1的全1矩阵，可计算出各个事务的事务长度。再根据定义4 对矩阵A3行简化，从而得到矩阵A3′。③重复以上步骤，直到某频繁k项集集合中项集的个数小于k+1，则该频繁项集为最大频繁项集，算法结束。

（4）所有的频繁项集即为各频繁k-项集的并。再根据最小置信度筛选出强关联规则。

2.3 性能分析

与Apriori 算法、基于压缩矩阵的Apriori算法[12]相比，改进后的算法有以下优点：

（1）改进后的算法仅需扫描一次事务数据库，运行效率明显提高。若将生成对应的事务矩阵记为An×m，该算法的时间复杂度为O(n2mk)。Apriori 算法的时间复杂度为O(Nk+1)，N代表事务数据库中事务的个数，其值远大于n。由于利用先验性质进行剪枝，Apriori 算法的时间复杂度降低了不少，但改进算法的时间复杂度仍然优于Apriori 算法。

（2）改进后的算法与基于压缩矩阵的Apriori 算法都使用布尔矩阵表示事务数据库，减少了I/O负载。与基于压缩矩阵的Apriori 算法不同的是：①改变了计算支持度的方法。不再使用事务矩阵中项集向量逐个进行循环求“与”运算，再计算“1”的个数来得到个项目的支持度计数。而是引入了自定义的支持度矩阵，只需扫描支持度矩阵的上三角（下三角）来得到支持度，简化了支持度的计算方法，减少了计算频繁项集的时间开销，提高了算法的效率。②算法的连接方法不同。在迭代过程中，不需要矩阵中项集向量逐个进行逻辑“与”操作来得到新的事务矩阵。而是只需利用上一次产生的频繁项集及事务矩阵来得到新的事务矩阵。因此，能极大地减少计算量。

在生成频繁项集的过程中由于引入的支持度矩阵，避免了大量冗余的候选项集的产生，提高了频繁项集的生成效率。并且在迭代过程中，实时地约简事务矩阵的规模，频繁k项集对应的事务矩阵Ak结构会随着k值的增长而变得愈简单，从而简化了矩阵规模，降低矩阵运算的复杂程度，减少了空间的占用。

3 实验及结果分析

3.1 实验分析步骤

MM-Apriori 算法对表1所示的事务数据库进行关联挖掘，获取频繁项集。事务T={T1,T2,···,T10}，对应的项目集I={I1,I2,I3,I4,I5}，假设最小支持度（Smin_support）为0.2，则最小支持度计数为ceiling(Sminsup_count)=ceiling(Smin_support×|T|)=2。

表1 事务数据库Tab.1 Transaction database

（1）扫描初始事务数据库，生成事务矩阵A1，其中行表示事务，列表示项。再得出对应的转置矩阵。

（2）生成L1。通过，得到支持度矩阵D1。D1中的值表示各项集的支持度计数，其中，对角线上的值表示各1-项集的支持度计数。比较D1中对角线上各1-项集的支持数与最小支持度计数的大小，提取出满足最小支持度计数的项目集。由于每一项都满足最小支持度计数从而得到频繁1-项集，即

（3）生成L2。将对称矩阵D1的上三角（下三角）中的各2-项集的计数与最小支持度计数进行比较，提取出满足最小支持度计数的项目集从而得到频繁2-项集。即

利用频繁2-项集及矩阵A1构造两个矩阵，通过两个矩阵的Hadamard 积的方法得到事务矩阵A2。首先，拆分频繁2-项集{I1|I2}，{I1|I3}，{I1|I4}，{I1|I5},{I2|I3}，{I2|I4}，{I2|I5}，{I3|I4}，{I3|I5}，左边的项集放入C1，右边的项集放入C1′；然后，扫描矩阵A1，可得到矩阵C1与C1′，将矩阵C1与C1′进行Hadamard 积运算，即A2=C1°C1′；最后，可得到事务矩阵A2。

事务矩阵A2乘以9×1 的全1 矩阵，可得到AAA2中对应的事务长度，根据定义4 简化矩阵，可得到简化后的事务矩阵A2′。

（4）生成L3。通过D2=A2′TA2′得到支持度矩阵D2。

将D2的上三角（下三角）中的各3-项集的计数与最小支持度计数进行比较，提取出满足最小支持度计数的项目集（不重复提取）从而得到频繁3-项集。即L3={{I1I2I3},{I1I2I4},{I1I2I5},{I1I3I5},{I2I3I4},{I2I3I5}}。

利用频繁3-项集及矩阵A2′构造两个矩阵，通过两个矩阵的Hadamard 积可得到事务矩阵A3。

将频繁3-项集拆分{I1I2|I2I3}，{I1I2|I2I4}，{I1I2|I2I5}，{I1I3|I3I5}，{I2I3|I3I4}，{I2I3|I3I5}，左边的项目放入矩阵C2，右边的项目放入矩阵C2′，再通过扫描矩阵A2′，得到矩阵C2与C2′，将矩阵C2与C2′进行Hadamard 积运算，即A3=C2°C2′，可得到事务矩阵A3。

事务矩阵A3乘以6×1 的全1 矩阵，可以得到A3中对应的事务长度，根据定义4，对矩阵简化得到矩阵A3′。

（5）生成L4。通过D3=A3′TA3′的上三角（下三角）中的各4-项集的计数与最小支持度计数进行比较，提取出满足最小支持度计数的项目集（不重复提取）从而得到频繁4-项集，即L4={I1I2I3I5}。

式中，Ci为重金属i在土壤中的实测含量(mg/kg)；Bi为重金属i在土壤中的背景值(mg/kg)。通常对于重金属i：Igeo≤0，土壤无污染；0 5，土壤极强污染。

（6）根据定义5 判断，L4中的项集个数小于5个，所以频繁4-项集为最大频繁项集，算法终止。输出频繁项集L=L1∪L2∪L3∪L4。

由频繁项集的挖掘结果可知，使用MM-Apriori算法获得的频繁项集与基于压缩矩阵的Apriori 算法[12]及Apriori 算法生成的频繁项集结果一致，验证了算法的可行性。

3.2 标准数据集验证

为验证改进算法的性能，对Apriori、基于压缩矩阵的Apriori 算法、MM-Apriori 算法在相同的实验环境下进行实验。实验环境：CPU 为Inter Core i7-4770K CPU @ 3.5 GHz、内存32 GB 和Windows 10 专业版操作系统。程序采用python3.6实现。实验数据来源于UCI 公共数据集中的蘑菇（Mushroom）数据集，共8 124 条事务，119 个项。

实验一：比较在不同支持度下3 种算法生成的频繁项集个数，如图2 所示。

图2 不同支持度下的3 种算法产生的频繁项集个数Fig.2 The number of frequent item sets produced by three algorithms with different support degrees

图2 描述了在不同支持度下的3 种算法产生的频繁项集个数，该实验的事务数目为8 124，项目数为112。由图2 可知，当设置相同支持度阈值时，MM-Apriori 算法与Apriori 算法生成的频繁项集数量相同，且比基于压缩矩阵的Apriori 算法生成的频繁项集数量多，随着支持度阈值的提高，3 种算法的频繁项集个数趋于相等。MM-Apriori 算法在不同支持度下均无频繁项集丢失的问题。

实验二：通过分别设置不同的最小支持度、不同的事务数目及不同的项目数目来比较算法的性能，实验结果如图3∼图5 所示。

图3 描述了在不同最小支持度的情况下3 种算法的执行时间，该实验的事务数目为6 500，项目数为112。由图3 可知，改进后，MM-Apriori 算法与基于压缩矩阵的Apriori 算法的执行时间都比Apriori算法短，但MM-Apriori 算法的执行效率是3 种算法中最优的。

图3 不同最小支持度下的3 种算法执行时间Fig.3 Execution time of two algorithms with different minimum support thresholds

图4 不同事务数下的3 种算法执行时间Fig.4 Execution time of three algorithms under different transaction numbers

图5 描述了在不同项目数目的情况下3 种算法的执行时间，该实验的事务数目为8 124，最小支持度为0.3。由图5 可知，当项目数目较小时，3 种算法的执行时间差距不大，但随着项目数目规模的增大，MM-Apriori 算法的执行效率明显优于Apriori算法。

图5 不同项目数下的3 种算法执行时间Fig.5 Execution time of two algorithms under different number of projects

综上所述，MM-Apriori 算法的有效性且不存在频繁项集遗漏的问题，与Apriori 及基于压缩矩阵的Apriori 算法[12]相比，具有更好的性能：无论事务数目、项目数目或最小支持度如何变化，该算法仍能稳定地快速运行，有效地提高了算法的效率。

3.3 钻井隐患数据应用分析

钻井隐患记录以数据库的形式存储，可以对隐患记录进行相关性分析，挖掘数据间的关联规则。为石油钻井作业的安全管理决策提供指导意见，有助于提高安全管理的效率，对预防事故的发生起到积极作用。以某石油钻探公司65 536 条包含107 个属性的历史安全隐患记录进行方法可行性的验证。

为准确高效地对隐患数据进行挖掘分析，先对隐患数据进行预处理，进而易于分析和挖掘的知识。钻井隐患数据为文字型数据，需将隐患属性数据转换为布尔型变量值来进行规则挖掘，发生该项隐患标识为1，未发生标识为0。表2 为处理好的钻井隐患数据片段。

表2 中的隐患数据使用MM-Apriori 算法进行关联挖掘。针对钻井作业隐患属性指标间错综复杂的问题，为提高挖掘准确度，引入了Kulc 和IR（不平衡比参数）两个相关性度量值[22-23]，来过滤伪强关联规则，使挖掘出的规则在保证效率的情况下更具有使用价值（为提升风险评估的实用性，仅选择后项为1 的关联规则）。设定最小支持度为0.5，最小置信度为0.8；最小Kulc 值为0.5，最大IR 值为0.5。实验挖掘的部分关联规则结果如表3所示。

表2 处理后的钻井隐患数据片段Tab.2 Data fragments of drilling hazards after treatment

对表3 的规则进行分析，可得到如下解释：由规则1、2 可看出，“井控设备配套不全或不符合设计要求”与“设备摆放不合理”很大概率会同时出现。提醒监督人员在安全隐患排查中若发现设备摆放不合理，那么将同时着重检查井控设备配套的完整性与是否符合设计要求。由规则3、4 可看出，当“点火装置缺陷”出现时，大约会有70%的概率发生“安全防护装置、连锁装置、安全附件缺失或失效”、“液气分离器缺陷”的问题。规则5 可看出，当出现“通风不良”时，监督人员应注重安全附件的校验。通过以上规则可发现，井控设备配套不全或不符合设计要求”与“设备摆放不合理”出现的频率很高，反映出设备维护人员工作职责不到位，在日常工作中管理者重点应督促设备维护人员及时对设备进行维护。