電力大數據并行關聯規則挖掘算法

吳 迪 劉國輝 劉 泉 王 麗

（國網黑龍江省電力有限公司信息通信公司，黑龍江 哈爾濱 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，以滿足對電力大數據進行高效挖掘的要求。挖掘某新能源發電機組監測真實數據集時，可以有效挖掘出隱藏在數據量龐大的電力大數據集中的隱藏規則，得出各天氣指標對機組發電量的正相關關系和負相關關系。