电力大数据并行关联规则挖掘算法

吴 迪 刘国辉 刘 泉 王 丽

（国网黑龙江省电力有限公司信息通信公司，黑龙江 哈尔滨 150001）

目前，在我国政府“双碳”目标的战略部署下[1]，中国电力系统的“双高”（即对风电和光伏发电依赖程度高）、“双峰”（即峰值分别出现在早/晚2 个高峰期）特征也越来越明显。关联规则挖掘在数理信息学、图片分类和电力大数据应用等领域都具有重要意义。关联规则挖掘是挖掘事务数据集中相关的关联关系，包括数据集间肯定的关系即正关联规则和否定的关系即负关联规则。

相关学者在最小支持度的基础上提出了正负关联规则挖掘，并在相关性和对偶置信度的基础上提出了负关联规则挖掘方法。一些学者将算法在并行模型MapReduce 框架下实现，并成功地应用在负关联规则挖掘中，但仍需要多次扫描数据库[2]。该文提出了一种新的基于MapReduce 框架的负关联规则挖掘算法，并在电力大数据集及公共试验数据集上进行了相关试验，得出了令人满意的结果。

1 相关理论

1.1 正负关联规则描述

定义1（支持度）：存在项集X，该项集在事务数据库中出现的概率定义为支持度，记为Sup（X）。

负关联规则表示的是关联规则的否定集合[3]。如果存在正关联规则X→Y，其负关联规则包括以下X→¬Y、¬X→Y和¬X→¬Y共3 种。

Sup（¬X）为项集X 的否定规则支持度，计算如公式（1）所示。

式中：Sup（¬X）表示在事务数据库中项集X未出现的概率，使用已知项集X出现的概率Sup（X） 计算得到。

1.2 正负关联规则的评判标准

定义2（置信度）：项集X与项集Y的执行度记为Conf（X→Y）。计算方式如公式（2）所示。

式中：Conf（X→Y）代表当项集X出现时，项集Y同时出现的概率；Sup（X→Y）代表项集X和项集Y在事务数据库中同时出现的概率。

将项集X与项集Y的否定置信度记为Conf（X→¬Y），其计算如公式（3）所示。

式中：Conf（X→¬Y）代表在事物数据库中项集X出现时项集Y不出现的概率[4]，使用Sup（X→Y）和Sup（X）完成计算。

X与否定Y和否定X与Y规则的置信度的计算如公式（4）所示。

式中：Conf（¬X→Y）代表在事务数据库中项集X不出现时项集Y出现的概率[5]，利用项集X与项集Y的支持度、项集Y的支持度和项集X支持度完成计算。

1.3 新能源电力大数据挖掘分析

目前，电力行业在不断推进智能电网业务，并利用多数据挖掘等形式来提高发电厂发电效率及新能源发电设备的建设效率。电力企业也在通过挖掘电力大数据的来改进和完善各项决策方案，提高核心竞争力，实行企业精细化管理，支撑配用电业务。对新能源电力大数据的正负关联规则挖掘可挖掘出电厂运作过程中及其他外界因素与电力设备产电量之间的关联规则，并通过关联关系的相关程度为后期决策提供一定的信息。通过分布式计算框架，可对规模庞大的电力大数据进行高效挖掘。

2 MR-CEPNR 算法

2.1 概述

MR-CEPNR（MapReduce-based Closed set Eclat Positive and Negative Rules）算法是一个采用MapReduce 计算框架实现的算法，主要由预处理和计算频繁K（K≥2）-项集2 部分组成。预处理阶段将不同类型的数据库转换为算法所需的垂直数据库形式{itemID：TID}，预处理完成后将处理得到的满足算法过程需要的数据储存在HDFS 上。在计算频繁K-项集的过程中主要进行2 步操作。首先，计算频繁2-项集，只计算正项集；利用求交集的方式进行项集的事务序号的求交，将求交得到的项集的事务序号集合进行保存，利用保存的事务序号集合完成支持度的计算，将满足条件的项集进行保存，得到频繁2-项集。寻找K（K>2）-项集，包括计算正项集和负项集，项集需要同时满足用户设定的支持度、置信度和兴趣度3个条件，才能被认为是频繁项集。

2.2 预处理

预处理过程包括3 个部分，即转换数据库格式、过滤非频繁项集及使用位图保存TID。

转换数据库格式时，算法选择垂直数据库形式以减少扫描数据库次数[6]。垂直数据库是指数据库中的每条记录由一个项目及该项目出现过的所有事务记录的列表构成，在垂直数据库下进行计算可以取得简化计算过程的效果。在垂直数据库中，主要是从水平数据库转为垂直数据库。在水平数据库中，事务与项的对应关系为{TID：items}，在该类型的数据库中不出现TID，即数据项在水平数据库中按行出现，每行包括多个数据项的数据库不便于后续计算。转换为垂直数据库后，项与事务的对应关系变为{itemID：TID}，对每个项所在的事务进行统计，项对应该项本身所在的所有事务。垂直数据库中同时存储项和对应的事务，转换为该种形式更便于后续计算。

过滤非频繁项集时，因为频繁1-项集仅取正项集，只需项集满足支持度这一个约束条件即可。在计算正频繁K（K>2）-项集时使用位图对项集的TID 进行求交操作，加快算法过程中求交集操作的速度。在计算负频繁K（K>2）-项集时，采用的方式是将正项集对应的位图的每位取反，得到满足条件的负项集。

2.3 计算频繁2-项集

在频繁2-项集的计算过程中，运用算法Eclat 中求取交集的方式完成频繁2-项集的计算[7]。面对数据量庞大的数据集时，使用Eclat 进行频计算会消耗更多时间，因此计算频繁2-项集时，MR-CEPNR 算法使用对位图保存的TID 进行与计算，不使用交集运算。利用频繁1-项集计算频繁2-项集时，使用位图计算交集[8]。得到的所有项集支持度中，大于等于最小支持度的项集都保留，将支持度不满足条件的删除。

进行频繁2-项计算时，直接对所得的频繁1-项集进行操作。假设存在频繁1-项集A、B、C和D，这4 个频繁项集对应的存储在位图中的TID 分别为{1，2，3，4，5，6}、{1，2，3，4，5}、{1，2，3，4，5}和{4，5，6}。对这4 个频繁项集两两组合并利用位图中的TID 进行求交，得到的候选项集分别是{AB}、{AC}、{AD}、{BC}、{BD}和{CD}，这6 个候选项集对应的TID 分别是{1，2，3，4，5}、{1，2，3，4，5}、{5，6}、{1，2，3，4，5}、{4，5}和{4，5}。如果将支持度设定为2，则以上项集均满足条件。这些项集在事务数据库中的出现次数均大于等于2，得到的频繁项集即可表示为{AB：1，2，3，4，5}、{AC：1，2，3，4，5}、{AD：5，6}、{BC：1，2，3，4，5}、{BD：4，5}和{CD：4，5}。

2.4 分发表制作

定义3（分发表）：分发表是根据频繁2-项集制作的带有头项和尾项的表。其中头项是所有频繁2-项集中都包括的第一个项，又称为父项；尾项是频繁2-项集中除头结点外的所有项，又称为子项。

根据频繁2-项集的信息制作分发表是挖掘频繁K（K>2）-项集的主要步骤。在关联规则中，根据Apriori 的性质可以得到如下推论：某项集作为首项集推导得到的所有频繁项集中，必会在以其作为父项集的全部频繁2-项集中出现。

根据该推论和定义3，利用表格的形式对所有相同负项集的分发表进行记录。分发表是一个映射结构，从映射中可以清楚地知道原数据表中具有相同父项的2-项集的子项。以A为父项集的Reduce 计算过程，其中最小支持度为2，最小置信度为0.2。A的子项为B、C、D，分别在子项中求频繁2-项集，得到{{B，C}：{1，2，3，4，5}}，{{B，D}：{4，5}}，{{C，D}：{4，5}}。将2-项集{{B，C}：{1，2，3，4，5}}和父项合并，项集{A，B，C}的支持度为5 和置信度为1 都满足条件，计算得出兴趣度大于1，因此输出正频繁3-项集{A，B，C}；将2-项集{{B，D}：{4，5}}和父项合并，项集{A，B，D}的支持度为2，置信度为0.4 都满足条件，然而兴趣度小于1，因此要计算负项集。先将项{D}取反得到负项集{-D}，然后得到负2-项集{B，-D}，和父项合并得到负项集{A，B，-D}。负项集{A，B，-D}的支持度为3，置信度为0.6，都满足条件，因此得到负频繁3-项集{A，B，-D}。同样可以得到负频繁3-项集{A，C，-D}。上述过程是计算正负频繁3-项集的过程。子项得到的频繁2-项集{B，C}和{B，D}会继续执行分发过程，继续得到正负频繁K（K>3）-项集。

2.5 计算频繁K（K>2）-项集

计算频繁K（K>2）-项集时，需要计算正频繁K（K>2）-项集和负频繁K（K>2）-项集。无论当前子项集是正项集还是负项集，都先计算正K（K>2）-项集。如果是正频繁K（K>2）-项集，则保存；如果不是正频繁K（K>2）-项集，则对该项集中最后一个项取反，然后计算负K（K>2）-项集，如果是负频繁K（K>2）-项集，则保存。

读取预处理得到的存放在分发表的父（father）节点信息和频繁1-项集。计算频繁3-项集时，直接遍历频繁1-项集得到key1、val1、key2、val2，从而计算得到频繁2-项集。然后计算father节点的key和频繁2-项集合并后的支持度和置信度。如果支持度大于等于最小支持度、置信度大于等于最小置信度，则计算兴趣度corr。如果corr>1，则得到正频繁3-项集；如果corr<1，则计算负项集，即将key2和val2取反。对key取反就是在项集前加一个符号“-”，以和正项集作区分。这里val是用位图存放的，取反即将位图中0 的位置变成1，1的位置变成0。取反后再次计算支持度和置信度，来确定是否可以加入负频繁3-项集，如果可以则得到负频繁3-项集。

计算频繁i（i>3）-项集和计算频繁3-项集不同的是，需要将计算频繁（i-1）-项集中得到的频繁（i-2）-项集遍历，将频繁（i-2）-项集中的相同项单独拿出，作为又一父节点father1（同样是分发表信息），剩余部分和father1、father计算支持度和接受度，判断规则同计算频繁3-项集时相同，即可得到包括正项集和负项集的全部频繁项集。

3 试验结果与分析

3.1 数据集与试验环境

该文选用来自fimi[9]的chess 数据集、webdocs 数据集和黑龙江省某新能源发电机组监测数据集（New_energy 数据集）。New_energy 数据集为某新能源发电设备群的电力检测设备数据及设备群的天气监测数据，反映了发电设备群的真实发电情况及影响发电量的很多天气因素。在Hadoop 具体环境中采用Hadoop-2.5.1 版本，并将Hadoop 的堆大小设置为25G。JDK 采用jdk1.7.0_71[10]。开发工具选择Eclipse，版本为Mars.2 Release（4.5.2）。

3.2 试验结果

在试验过程中，频繁2-项集只计算了正项集部分，频繁K（K>2）-项集部分计算正项集和负项集，其中负项集的计算为X→┐Y形式，即当项集{A，B}不满足频繁项集时，计算{A，-B}是否满足频繁项集条件；项集{A，-B，C}不满足频繁项集时，计算{A，-B，-C}是否满足频繁项集条件。同时，将频繁关联规则的最大长度设置为5。

首先，对正负关联规则数进行比较。该文使用chess 数据集进行试验。当最小置信度设置为0.1 时，支持度分别设置为800、1000、1200。试验结果表明：算法中设定的接受度一定时，支持度的数值越小，算法就会得到更多的正关联规则数和负关联规则数。当最小支持度设置为800 时，置信度分别设置为0.1、0.2、0.3、0.4。试验结果表明：当支持度一定时，置信度越小，算法运行会得到更多的正关联规则数与负关联规则数。

其次，对算法的时间效率进行比较。该文使用webdocs 数据集进行试验。对该文提出的MR-CEPNR 算法和将Eclat 算法应用到挖掘负关联规则的nEclat 算法进行比较。1）将置信度设置为0.1 不变，支持度设置为1000、1200、1500。结果表明MR-CEPNR 算法的运行效率远高于nEclat 算法。2）支持度设置为300 不变，置信度设置为0.1、0.5、0.9。同时，随着置信度的减少，挖掘得到的关联规则数量越多，并且MR-CEPNR算法的运行效率远高于nEclat 算法。

整体试验结果表明，无论是支持度变化还是置信度变化，MR-CEPNR算法在大数据集webdocs下的效率都远高于nEclat算法。当支持度越小时，挖掘出的频繁项集越多，MR-CEPNR的时间效率越比nEclat 算法的时间效率高。因为MR-CEPNR算法使用基于位图的计算策略，即使数据量巨大，效率仍然较高，并使用频繁2-项集来生成分发表[11]，提高了集群利用率，从而提高了时间效率。

3.3 应用案例

为验证算法的实用性，在采集的新能源数据集New_energy中使用该文算法进行正负关联规则挖掘。数据来源于某风电厂运行调度日志和气象台的观测数据。气象数据包括阴晴状况、温度、湿度、风力以及风向等，各项数据采集的时间跨度为一年。试验的参数如下：最小支持度阈值为20，New_energy 事务总数为2260。最终挖掘所得的频繁3-项集结果实例见表1。

表1 在New_energy 中挖掘的频繁3-项集实例

从表1 中可以看出MR-CEPNR 算法在数据集New_energy中进行正负频繁3-项集挖掘的结果。负频繁项集{-4 级，50000，多云}表示当新能源发电机组在风力为4 级以下并且天气为多云情况下的发电量可达50000kW·h。该规则表明，风力较小且天气状况相对较差与新能源发电机组的发电量呈负相关关系。该规则的发现=可以帮助新能源机组工作人员对风电机组进行有效调整，使新能源机组在天气和风力相对较差的情况下不会发生机组电力消耗量大于机组电力生产量的问题。

该文算法能够对电力大数据集进行高效的正负关联规则挖掘的原因如下：在候选项集的生成过程中，通过项集相关性判断加入了负候选项集的生成及筛选，使算法可以同时挖掘电力大数据集中的正相关规则和负相关规则，并使该数据集中正相关和负相关的隐藏信息能够得到更全面、真实的体现，最大程度地发挥关联规则在电力大数据分析与应用领域中的指导意义。

4 结论

该文提出了一种并行正负关联规则挖掘算法-MRCEPNR，以满足对电力大数据进行高效挖掘的要求。挖掘某新能源发电机组监测真实数据集时，可以有效挖掘出隐藏在数据量庞大的电力大数据集中的隐藏规则，得出各天气指标对机组发电量的正相关关系和负相关关系。