吳 迪 劉國(guó)輝 劉 泉 王 麗
(國(guó)網(wǎng)黑龍江省電力有限公司信息通信公司,黑龍江 哈爾濱 150001)
目前,在我國(guó)政府“雙碳”目標(biāo)的戰(zhàn)略部署下[1],中國(guó)電力系統(tǒng)的“雙高”(即對(duì)風(fēng)電和光伏發(fā)電依賴程度高)、“雙峰”(即峰值分別出現(xiàn)在早/晚2 個(gè)高峰期)特征也越來越明顯。關(guān)聯(lián)規(guī)則挖掘在數(shù)理信息學(xué)、圖片分類和電力大數(shù)據(jù)應(yīng)用等領(lǐng)域都具有重要意義。關(guān)聯(lián)規(guī)則挖掘是挖掘事務(wù)數(shù)據(jù)集中相關(guān)的關(guān)聯(lián)關(guān)系,包括數(shù)據(jù)集間肯定的關(guān)系即正關(guān)聯(lián)規(guī)則和否定的關(guān)系即負(fù)關(guān)聯(lián)規(guī)則。
相關(guān)學(xué)者在最小支持度的基礎(chǔ)上提出了正負(fù)關(guān)聯(lián)規(guī)則挖掘,并在相關(guān)性和對(duì)偶置信度的基礎(chǔ)上提出了負(fù)關(guān)聯(lián)規(guī)則挖掘方法。一些學(xué)者將算法在并行模型MapReduce 框架下實(shí)現(xiàn),并成功地應(yīng)用在負(fù)關(guān)聯(lián)規(guī)則挖掘中,但仍需要多次掃描數(shù)據(jù)庫[2]。該文提出了一種新的基于MapReduce 框架的負(fù)關(guān)聯(lián)規(guī)則挖掘算法,并在電力大數(shù)據(jù)集及公共試驗(yàn)數(shù)據(jù)集上進(jìn)行了相關(guān)試驗(yàn),得出了令人滿意的結(jié)果。
定義1(支持度):存在項(xiàng)集X,該項(xiàng)集在事務(wù)數(shù)據(jù)庫中出現(xiàn)的概率定義為支持度,記為Sup(X)。
負(fù)關(guān)聯(lián)規(guī)則表示的是關(guān)聯(lián)規(guī)則的否定集合[3]。如果存在正關(guān)聯(lián)規(guī)則X→Y,其負(fù)關(guān)聯(lián)規(guī)則包括以下X→?Y、?X→Y和?X→?Y共3 種。
Sup(?X)為項(xiàng)集X 的否定規(guī)則支持度,計(jì)算如公式(1)所示。
式中:Sup(?X)表示在事務(wù)數(shù)據(jù)庫中項(xiàng)集X未出現(xiàn)的概率,使用已知項(xiàng)集X出現(xiàn)的概率Sup(X) 計(jì)算得到。
定義2(置信度):項(xiàng)集X與項(xiàng)集Y的執(zhí)行度記為Conf(X→Y)。計(jì)算方式如公式(2)所示。
式中:Conf(X→Y)代表當(dāng)項(xiàng)集X出現(xiàn)時(shí),項(xiàng)集Y同時(shí)出現(xiàn)的概率;Sup(X→Y)代表項(xiàng)集X和項(xiàng)集Y在事務(wù)數(shù)據(jù)庫中同時(shí)出現(xiàn)的概率。
將項(xiàng)集X與項(xiàng)集Y的否定置信度記為Conf(X→?Y),其計(jì)算如公式(3)所示。
式中:Conf(X→?Y)代表在事物數(shù)據(jù)庫中項(xiàng)集X出現(xiàn)時(shí)項(xiàng)集Y不出現(xiàn)的概率[4],使用Sup(X→Y)和Sup(X)完成計(jì)算。
X與否定Y和否定X與Y規(guī)則的置信度的計(jì)算如公式(4)所示。
式中:Conf(?X→Y)代表在事務(wù)數(shù)據(jù)庫中項(xiàng)集X不出現(xiàn)時(shí)項(xiàng)集Y出現(xiàn)的概率[5],利用項(xiàng)集X與項(xiàng)集Y的支持度、項(xiàng)集Y的支持度和項(xiàng)集X支持度完成計(jì)算。
目前,電力行業(yè)在不斷推進(jìn)智能電網(wǎng)業(yè)務(wù),并利用多數(shù)據(jù)挖掘等形式來提高發(fā)電廠發(fā)電效率及新能源發(fā)電設(shè)備的建設(shè)效率。電力企業(yè)也在通過挖掘電力大數(shù)據(jù)的來改進(jìn)和完善各項(xiàng)決策方案,提高核心競(jìng)爭(zhēng)力,實(shí)行企業(yè)精細(xì)化管理,支撐配用電業(yè)務(wù)。對(duì)新能源電力大數(shù)據(jù)的正負(fù)關(guān)聯(lián)規(guī)則挖掘可挖掘出電廠運(yùn)作過程中及其他外界因素與電力設(shè)備產(chǎn)電量之間的關(guān)聯(lián)規(guī)則,并通過關(guān)聯(lián)關(guān)系的相關(guān)程度為后期決策提供一定的信息。通過分布式計(jì)算框架,可對(duì)規(guī)模龐大的電力大數(shù)據(jù)進(jìn)行高效挖掘。
MR-CEPNR(MapReduce-based Closed set Eclat Positive and Negative Rules)算法是一個(gè)采用MapReduce 計(jì)算框架實(shí)現(xiàn)的算法,主要由預(yù)處理和計(jì)算頻繁K(K≥2)-項(xiàng)集2 部分組成。預(yù)處理階段將不同類型的數(shù)據(jù)庫轉(zhuǎn)換為算法所需的垂直數(shù)據(jù)庫形式{itemID:TID},預(yù)處理完成后將處理得到的滿足算法過程需要的數(shù)據(jù)儲(chǔ)存在HDFS 上。在計(jì)算頻繁K-項(xiàng)集的過程中主要進(jìn)行2 步操作。首先,計(jì)算頻繁2-項(xiàng)集,只計(jì)算正項(xiàng)集;利用求交集的方式進(jìn)行項(xiàng)集的事務(wù)序號(hào)的求交,將求交得到的項(xiàng)集的事務(wù)序號(hào)集合進(jìn)行保存,利用保存的事務(wù)序號(hào)集合完成支持度的計(jì)算,將滿足條件的項(xiàng)集進(jìn)行保存,得到頻繁2-項(xiàng)集。尋找K(K>2)-項(xiàng)集,包括計(jì)算正項(xiàng)集和負(fù)項(xiàng)集,項(xiàng)集需要同時(shí)滿足用戶設(shè)定的支持度、置信度和興趣度3個(gè)條件,才能被認(rèn)為是頻繁項(xiàng)集。
預(yù)處理過程包括3 個(gè)部分,即轉(zhuǎn)換數(shù)據(jù)庫格式、過濾非頻繁項(xiàng)集及使用位圖保存TID。
轉(zhuǎn)換數(shù)據(jù)庫格式時(shí),算法選擇垂直數(shù)據(jù)庫形式以減少掃描數(shù)據(jù)庫次數(shù)[6]。垂直數(shù)據(jù)庫是指數(shù)據(jù)庫中的每條記錄由一個(gè)項(xiàng)目及該項(xiàng)目出現(xiàn)過的所有事務(wù)記錄的列表構(gòu)成,在垂直數(shù)據(jù)庫下進(jìn)行計(jì)算可以取得簡(jiǎn)化計(jì)算過程的效果。在垂直數(shù)據(jù)庫中,主要是從水平數(shù)據(jù)庫轉(zhuǎn)為垂直數(shù)據(jù)庫。在水平數(shù)據(jù)庫中,事務(wù)與項(xiàng)的對(duì)應(yīng)關(guān)系為{TID:items},在該類型的數(shù)據(jù)庫中不出現(xiàn)TID,即數(shù)據(jù)項(xiàng)在水平數(shù)據(jù)庫中按行出現(xiàn),每行包括多個(gè)數(shù)據(jù)項(xiàng)的數(shù)據(jù)庫不便于后續(xù)計(jì)算。轉(zhuǎn)換為垂直數(shù)據(jù)庫后,項(xiàng)與事務(wù)的對(duì)應(yīng)關(guān)系變?yōu)閧itemID:TID},對(duì)每個(gè)項(xiàng)所在的事務(wù)進(jìn)行統(tǒng)計(jì),項(xiàng)對(duì)應(yīng)該項(xiàng)本身所在的所有事務(wù)。垂直數(shù)據(jù)庫中同時(shí)存儲(chǔ)項(xiàng)和對(duì)應(yīng)的事務(wù),轉(zhuǎn)換為該種形式更便于后續(xù)計(jì)算。
過濾非頻繁項(xiàng)集時(shí),因?yàn)轭l繁1-項(xiàng)集僅取正項(xiàng)集,只需項(xiàng)集滿足支持度這一個(gè)約束條件即可。在計(jì)算正頻繁K(K>2)-項(xiàng)集時(shí)使用位圖對(duì)項(xiàng)集的TID 進(jìn)行求交操作,加快算法過程中求交集操作的速度。在計(jì)算負(fù)頻繁K(K>2)-項(xiàng)集時(shí),采用的方式是將正項(xiàng)集對(duì)應(yīng)的位圖的每位取反,得到滿足條件的負(fù)項(xiàng)集。
在頻繁2-項(xiàng)集的計(jì)算過程中,運(yùn)用算法Eclat 中求取交集的方式完成頻繁2-項(xiàng)集的計(jì)算[7]。面對(duì)數(shù)據(jù)量龐大的數(shù)據(jù)集時(shí),使用Eclat 進(jìn)行頻計(jì)算會(huì)消耗更多時(shí)間,因此計(jì)算頻繁2-項(xiàng)集時(shí),MR-CEPNR 算法使用對(duì)位圖保存的TID 進(jìn)行與計(jì)算,不使用交集運(yùn)算。利用頻繁1-項(xiàng)集計(jì)算頻繁2-項(xiàng)集時(shí),使用位圖計(jì)算交集[8]。得到的所有項(xiàng)集支持度中,大于等于最小支持度的項(xiàng)集都保留,將支持度不滿足條件的刪除。
進(jìn)行頻繁2-項(xiàng)計(jì)算時(shí),直接對(duì)所得的頻繁1-項(xiàng)集進(jìn)行操作。假設(shè)存在頻繁1-項(xiàng)集A、B、C和D,這4 個(gè)頻繁項(xiàng)集對(duì)應(yīng)的存儲(chǔ)在位圖中的TID 分別為{1,2,3,4,5,6}、{1,2,3,4,5}、{1,2,3,4,5}和{4,5,6}。對(duì)這4 個(gè)頻繁項(xiàng)集兩兩組合并利用位圖中的TID 進(jìn)行求交,得到的候選項(xiàng)集分別是{AB}、{AC}、{AD}、{BC}、{BD}和{CD},這6 個(gè)候選項(xiàng)集對(duì)應(yīng)的TID 分別是{1,2,3,4,5}、{1,2,3,4,5}、{5,6}、{1,2,3,4,5}、{4,5}和{4,5}。如果將支持度設(shè)定為2,則以上項(xiàng)集均滿足條件。這些項(xiàng)集在事務(wù)數(shù)據(jù)庫中的出現(xiàn)次數(shù)均大于等于2,得到的頻繁項(xiàng)集即可表示為{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}。
定義3(分發(fā)表):分發(fā)表是根據(jù)頻繁2-項(xiàng)集制作的帶有頭項(xiàng)和尾項(xiàng)的表。其中頭項(xiàng)是所有頻繁2-項(xiàng)集中都包括的第一個(gè)項(xiàng),又稱為父項(xiàng);尾項(xiàng)是頻繁2-項(xiàng)集中除頭結(jié)點(diǎn)外的所有項(xiàng),又稱為子項(xiàng)。
根據(jù)頻繁2-項(xiàng)集的信息制作分發(fā)表是挖掘頻繁K(K>2)-項(xiàng)集的主要步驟。在關(guān)聯(lián)規(guī)則中,根據(jù)Apriori 的性質(zhì)可以得到如下推論:某項(xiàng)集作為首項(xiàng)集推導(dǎo)得到的所有頻繁項(xiàng)集中,必會(huì)在以其作為父項(xiàng)集的全部頻繁2-項(xiàng)集中出現(xiàn)。
根據(jù)該推論和定義3,利用表格的形式對(duì)所有相同負(fù)項(xiàng)集的分發(fā)表進(jìn)行記錄。分發(fā)表是一個(gè)映射結(jié)構(gòu),從映射中可以清楚地知道原數(shù)據(jù)表中具有相同父項(xiàng)的2-項(xiàng)集的子項(xiàng)。以A為父項(xiàng)集的Reduce 計(jì)算過程,其中最小支持度為2,最小置信度為0.2。A的子項(xiàng)為B、C、D,分別在子項(xiàng)中求頻繁2-項(xiàng)集,得到{{B,C}:{1,2,3,4,5}},{{B,D}:{4,5}},{{C,D}:{4,5}}。將2-項(xiàng)集{{B,C}:{1,2,3,4,5}}和父項(xiàng)合并,項(xiàng)集{A,B,C}的支持度為5 和置信度為1 都滿足條件,計(jì)算得出興趣度大于1,因此輸出正頻繁3-項(xiàng)集{A,B,C};將2-項(xiàng)集{{B,D}:{4,5}}和父項(xiàng)合并,項(xiàng)集{A,B,D}的支持度為2,置信度為0.4 都滿足條件,然而興趣度小于1,因此要計(jì)算負(fù)項(xiàng)集。先將項(xiàng){D}取反得到負(fù)項(xiàng)集{-D},然后得到負(fù)2-項(xiàng)集{B,-D},和父項(xiàng)合并得到負(fù)項(xiàng)集{A,B,-D}。負(fù)項(xiàng)集{A,B,-D}的支持度為3,置信度為0.6,都滿足條件,因此得到負(fù)頻繁3-項(xiàng)集{A,B,-D}。同樣可以得到負(fù)頻繁3-項(xiàng)集{A,C,-D}。上述過程是計(jì)算正負(fù)頻繁3-項(xiàng)集的過程。子項(xiàng)得到的頻繁2-項(xiàng)集{B,C}和{B,D}會(huì)繼續(xù)執(zhí)行分發(fā)過程,繼續(xù)得到正負(fù)頻繁K(K>3)-項(xiàng)集。
計(jì)算頻繁K(K>2)-項(xiàng)集時(shí),需要計(jì)算正頻繁K(K>2)-項(xiàng)集和負(fù)頻繁K(K>2)-項(xiàng)集。無論當(dāng)前子項(xiàng)集是正項(xiàng)集還是負(fù)項(xiàng)集,都先計(jì)算正K(K>2)-項(xiàng)集。如果是正頻繁K(K>2)-項(xiàng)集,則保存;如果不是正頻繁K(K>2)-項(xiàng)集,則對(duì)該項(xiàng)集中最后一個(gè)項(xiàng)取反,然后計(jì)算負(fù)K(K>2)-項(xiàng)集,如果是負(fù)頻繁K(K>2)-項(xiàng)集,則保存。
讀取預(yù)處理得到的存放在分發(fā)表的父(father)節(jié)點(diǎn)信息和頻繁1-項(xiàng)集。計(jì)算頻繁3-項(xiàng)集時(shí),直接遍歷頻繁1-項(xiàng)集得到key1、val1、key2、val2,從而計(jì)算得到頻繁2-項(xiàng)集。然后計(jì)算father節(jié)點(diǎn)的key和頻繁2-項(xiàng)集合并后的支持度和置信度。如果支持度大于等于最小支持度、置信度大于等于最小置信度,則計(jì)算興趣度corr。如果corr>1,則得到正頻繁3-項(xiàng)集;如果corr<1,則計(jì)算負(fù)項(xiàng)集,即將key2和val2取反。對(duì)key取反就是在項(xiàng)集前加一個(gè)符號(hào)“-”,以和正項(xiàng)集作區(qū)分。這里val是用位圖存放的,取反即將位圖中0 的位置變成1,1的位置變成0。取反后再次計(jì)算支持度和置信度,來確定是否可以加入負(fù)頻繁3-項(xiàng)集,如果可以則得到負(fù)頻繁3-項(xiàng)集。
計(jì)算頻繁i(i>3)-項(xiàng)集和計(jì)算頻繁3-項(xiàng)集不同的是,需要將計(jì)算頻繁(i-1)-項(xiàng)集中得到的頻繁(i-2)-項(xiàng)集遍歷,將頻繁(i-2)-項(xiàng)集中的相同項(xiàng)單獨(dú)拿出,作為又一父節(jié)點(diǎn)father1(同樣是分發(fā)表信息),剩余部分和father1、father計(jì)算支持度和接受度,判斷規(guī)則同計(jì)算頻繁3-項(xiàng)集時(shí)相同,即可得到包括正項(xiàng)集和負(fù)項(xiàng)集的全部頻繁項(xiàng)集。
該文選用來自fimi[9]的chess 數(shù)據(jù)集、webdocs 數(shù)據(jù)集和黑龍江省某新能源發(fā)電機(jī)組監(jiān)測(cè)數(shù)據(jù)集(New_energy 數(shù)據(jù)集)。New_energy 數(shù)據(jù)集為某新能源發(fā)電設(shè)備群的電力檢測(cè)設(shè)備數(shù)據(jù)及設(shè)備群的天氣監(jiān)測(cè)數(shù)據(jù),反映了發(fā)電設(shè)備群的真實(shí)發(fā)電情況及影響發(fā)電量的很多天氣因素。在Hadoop 具體環(huán)境中采用Hadoop-2.5.1 版本,并將Hadoop 的堆大小設(shè)置為25G。JDK 采用jdk1.7.0_71[10]。開發(fā)工具選擇Eclipse,版本為Mars.2 Release(4.5.2)。
在試驗(yàn)過程中,頻繁2-項(xiàng)集只計(jì)算了正項(xiàng)集部分,頻繁K(K>2)-項(xiàng)集部分計(jì)算正項(xiàng)集和負(fù)項(xiàng)集,其中負(fù)項(xiàng)集的計(jì)算為X→┐Y形式,即當(dāng)項(xiàng)集{A,B}不滿足頻繁項(xiàng)集時(shí),計(jì)算{A,-B}是否滿足頻繁項(xiàng)集條件;項(xiàng)集{A,-B,C}不滿足頻繁項(xiàng)集時(shí),計(jì)算{A,-B,-C}是否滿足頻繁項(xiàng)集條件。同時(shí),將頻繁關(guān)聯(lián)規(guī)則的最大長(zhǎng)度設(shè)置為5。
首先,對(duì)正負(fù)關(guān)聯(lián)規(guī)則數(shù)進(jìn)行比較。該文使用chess 數(shù)據(jù)集進(jìn)行試驗(yàn)。當(dāng)最小置信度設(shè)置為0.1 時(shí),支持度分別設(shè)置為800、1000、1200。試驗(yàn)結(jié)果表明:算法中設(shè)定的接受度一定時(shí),支持度的數(shù)值越小,算法就會(huì)得到更多的正關(guān)聯(lián)規(guī)則數(shù)和負(fù)關(guān)聯(lián)規(guī)則數(shù)。當(dāng)最小支持度設(shè)置為800 時(shí),置信度分別設(shè)置為0.1、0.2、0.3、0.4。試驗(yàn)結(jié)果表明:當(dāng)支持度一定時(shí),置信度越小,算法運(yùn)行會(huì)得到更多的正關(guān)聯(lián)規(guī)則數(shù)與負(fù)關(guān)聯(lián)規(guī)則數(shù)。
其次,對(duì)算法的時(shí)間效率進(jìn)行比較。該文使用webdocs 數(shù)據(jù)集進(jìn)行試驗(yàn)。對(duì)該文提出的MR-CEPNR 算法和將Eclat 算法應(yīng)用到挖掘負(fù)關(guān)聯(lián)規(guī)則的nEclat 算法進(jìn)行比較。1)將置信度設(shè)置為0.1 不變,支持度設(shè)置為1000、1200、1500。結(jié)果表明MR-CEPNR 算法的運(yùn)行效率遠(yuǎn)高于nEclat 算法。2)支持度設(shè)置為300 不變,置信度設(shè)置為0.1、0.5、0.9。同時(shí),隨著置信度的減少,挖掘得到的關(guān)聯(lián)規(guī)則數(shù)量越多,并且MR-CEPNR算法的運(yùn)行效率遠(yuǎn)高于nEclat 算法。
整體試驗(yàn)結(jié)果表明,無論是支持度變化還是置信度變化,MR-CEPNR算法在大數(shù)據(jù)集webdocs下的效率都遠(yuǎn)高于nEclat算法。當(dāng)支持度越小時(shí),挖掘出的頻繁項(xiàng)集越多,MR-CEPNR的時(shí)間效率越比nEclat 算法的時(shí)間效率高。因?yàn)镸R-CEPNR算法使用基于位圖的計(jì)算策略,即使數(shù)據(jù)量巨大,效率仍然較高,并使用頻繁2-項(xiàng)集來生成分發(fā)表[11],提高了集群利用率,從而提高了時(shí)間效率。
為驗(yàn)證算法的實(shí)用性,在采集的新能源數(shù)據(jù)集New_energy中使用該文算法進(jìn)行正負(fù)關(guān)聯(lián)規(guī)則挖掘。數(shù)據(jù)來源于某風(fēng)電廠運(yùn)行調(diào)度日志和氣象臺(tái)的觀測(cè)數(shù)據(jù)。氣象數(shù)據(jù)包括陰晴狀況、溫度、濕度、風(fēng)力以及風(fēng)向等,各項(xiàng)數(shù)據(jù)采集的時(shí)間跨度為一年。試驗(yàn)的參數(shù)如下:最小支持度閾值為20,New_energy 事務(wù)總數(shù)為2260。最終挖掘所得的頻繁3-項(xiàng)集結(jié)果實(shí)例見表1。
表1 在New_energy 中挖掘的頻繁3-項(xiàng)集實(shí)例
從表1 中可以看出MR-CEPNR 算法在數(shù)據(jù)集New_energy中進(jìn)行正負(fù)頻繁3-項(xiàng)集挖掘的結(jié)果。負(fù)頻繁項(xiàng)集{-4 級(jí),50000,多云}表示當(dāng)新能源發(fā)電機(jī)組在風(fēng)力為4 級(jí)以下并且天氣為多云情況下的發(fā)電量可達(dá)50000kW·h。該規(guī)則表明,風(fēng)力較小且天氣狀況相對(duì)較差與新能源發(fā)電機(jī)組的發(fā)電量呈負(fù)相關(guān)關(guān)系。該規(guī)則的發(fā)現(xiàn)=可以幫助新能源機(jī)組工作人員對(duì)風(fēng)電機(jī)組進(jìn)行有效調(diào)整,使新能源機(jī)組在天氣和風(fēng)力相對(duì)較差的情況下不會(huì)發(fā)生機(jī)組電力消耗量大于機(jī)組電力生產(chǎn)量的問題。
該文算法能夠?qū)﹄娏Υ髷?shù)據(jù)集進(jìn)行高效的正負(fù)關(guān)聯(lián)規(guī)則挖掘的原因如下:在候選項(xiàng)集的生成過程中,通過項(xiàng)集相關(guān)性判斷加入了負(fù)候選項(xiàng)集的生成及篩選,使算法可以同時(shí)挖掘電力大數(shù)據(jù)集中的正相關(guān)規(guī)則和負(fù)相關(guān)規(guī)則,并使該數(shù)據(jù)集中正相關(guān)和負(fù)相關(guān)的隱藏信息能夠得到更全面、真實(shí)的體現(xiàn),最大程度地發(fā)揮關(guān)聯(lián)規(guī)則在電力大數(shù)據(jù)分析與應(yīng)用領(lǐng)域中的指導(dǎo)意義。
該文提出了一種并行正負(fù)關(guān)聯(lián)規(guī)則挖掘算法-MRCEPNR,以滿足對(duì)電力大數(shù)據(jù)進(jìn)行高效挖掘的要求。挖掘某新能源發(fā)電機(jī)組監(jiān)測(cè)真實(shí)數(shù)據(jù)集時(shí),可以有效挖掘出隱藏在數(shù)據(jù)量龐大的電力大數(shù)據(jù)集中的隱藏規(guī)則,得出各天氣指標(biāo)對(duì)機(jī)組發(fā)電量的正相關(guān)關(guān)系和負(fù)相關(guān)關(guān)系。