面向多源異構(gòu)信息的頻繁項集挖掘算法

劉自力，范軍麗，陳文偉，吳潤澤

(1.國網(wǎng)山西省電力公司 晉城供電公司，山西 晉城 048000； 2.北京國電通網(wǎng)絡(luò)技術(shù)有限公司，北京 100070； 3.華北電力大學(xué) 電氣與電子工程學(xué)院，北京 102206)

面向多源異構(gòu)信息的頻繁項集挖掘算法

劉自力1，范軍麗2，陳文偉3，吳潤澤3

(1.國網(wǎng)山西省電力公司 晉城供電公司，山西 晉城 048000； 2.北京國電通網(wǎng)絡(luò)技術(shù)有限公司，北京 100070； 3.華北電力大學(xué) 電氣與電子工程學(xué)院，北京 102206)

電網(wǎng)調(diào)度運行過程中產(chǎn)生海量復(fù)雜度高的多源異構(gòu)數(shù)據(jù)，利用數(shù)據(jù)挖掘?qū)⑦@些數(shù)據(jù)轉(zhuǎn)化為知識是調(diào)度智能化發(fā)展的必然趨勢。為此，構(gòu)建了基于調(diào)控大數(shù)據(jù)的多源異構(gòu)數(shù)據(jù)分析模型，提出了一種能夠處理大數(shù)據(jù)的頻繁項集挖掘算法，將分布式統(tǒng)計引入到頻繁項集挖掘過程。該算法根據(jù)組合學(xué)原理，利用MapReduce掃描一次數(shù)據(jù)庫從原始事務(wù)數(shù)據(jù)庫中完成頻繁項集的整個挖掘過程；且在支持度閾值改變的情況下無需重新掃描數(shù)據(jù)庫進行挖掘，改進了現(xiàn)有頻繁項集挖掘算法多次掃描事務(wù)數(shù)據(jù)庫和挖掘效率低的問題。通過利用Hadoop平臺對故障信息事務(wù)庫進行處理，將所提出的算法與其他頻繁項集挖掘算法進行了對比驗證實驗。實驗結(jié)果表明，所提出的算法不受支持度閾值的影響，處理海量事務(wù)數(shù)據(jù)算法時間開銷小，可為實現(xiàn)以準確、安全、經(jīng)濟等目標綜合最優(yōu)的調(diào)度智能化分析和決策提供有益的知識。

智能調(diào)度；頻繁項集；組合理論；Hadoop

0 引 言

當(dāng)前信息通信技術(shù)(ICT)的高速發(fā)展推動了智能電網(wǎng)的全面建設(shè)，ICT和電網(wǎng)建設(shè)的深度融合催生了智能電網(wǎng)大數(shù)據(jù)的爆炸性增長。這些數(shù)據(jù)不僅規(guī)模大，其結(jié)構(gòu)也多樣化，構(gòu)成了智能電網(wǎng)中的海量多源異構(gòu)大數(shù)據(jù)。海量多源異構(gòu)大數(shù)據(jù)的高效快速處理和深度挖掘分析為建設(shè)堅強可靠、穩(wěn)定運行的智能電網(wǎng)提供基礎(chǔ)[1]。電網(wǎng)調(diào)度控制系統(tǒng)中產(chǎn)生的大數(shù)據(jù)是智能電網(wǎng)大數(shù)據(jù)的主要來源，這些數(shù)據(jù)隱藏著電網(wǎng)運行中的實時狀態(tài)信息。而數(shù)據(jù)挖掘是實現(xiàn)將實時數(shù)據(jù)和沉淀的歷史數(shù)據(jù)轉(zhuǎn)化為有用知識的有效方法，為電網(wǎng)調(diào)度運行提供輔助性決策和科學(xué)性建議[2]。智能調(diào)度中的數(shù)據(jù)來源豐富，人們從不同的數(shù)據(jù)源獲取的信息也越來越多，而且這些數(shù)據(jù)創(chuàng)造的價值也被人們所接受，但是這些數(shù)據(jù)源之間形成了眾多的“信息孤島”。因此，有必要采用大數(shù)據(jù)思想，對智能調(diào)度中的數(shù)據(jù)進行分析和挖掘，來實現(xiàn)數(shù)據(jù)共享，為智能調(diào)度的實現(xiàn)提供參考。關(guān)聯(lián)分析是數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的重要技術(shù)之一。關(guān)聯(lián)規(guī)則算法主要用來挖掘事務(wù)數(shù)據(jù)庫中有意義或用戶感興趣的規(guī)則。1993年，美國的R.Agrawal等首次提出關(guān)聯(lián)規(guī)則算法[3]，其主要思想是從原始事務(wù)數(shù)據(jù)庫中找出滿足一定支持度和置信度要求的項集。其中滿足用戶定義的最小支持度的項集稱為頻繁項集，從頻繁項集中找出滿足最小置信度的頻繁項集，將其轉(zhuǎn)化成最終的強關(guān)聯(lián)規(guī)則形式完成關(guān)聯(lián)規(guī)則挖掘。將頻繁項集轉(zhuǎn)化成關(guān)聯(lián)規(guī)則的過程較為簡單，所以頻繁項集挖掘是關(guān)聯(lián)規(guī)則挖掘的重點和關(guān)鍵。

Apriori算法是由R.Agrawal等提出的經(jīng)典頻繁項集算法，該算法通過連接和剪枝方法完成，能夠有效挖掘出用戶需要的關(guān)聯(lián)規(guī)則，但是存在產(chǎn)生大量的候選項集和重復(fù)多次掃描事務(wù)數(shù)據(jù)庫的缺陷。為了克服這些缺陷，Han Jiawei等在Apriori算法的基礎(chǔ)上提出了FP-growth算法[4]。該算法建立了樹結(jié)構(gòu)，用來保存每項的支持度計數(shù)，在建立頻繁模式樹的過程中只需掃描兩次事務(wù)數(shù)據(jù)庫，并且不產(chǎn)生候選項集。盡管該算法提高了頻繁項集的挖掘效率，但是針對大量且事務(wù)比較長的事務(wù)數(shù)據(jù)庫，其挖掘效率較低。為了提高頻繁項集的挖掘效率，文獻[5-8]基于磁盤存儲的算法改進了挖掘大量事務(wù)數(shù)據(jù)庫和內(nèi)存有限的問題，但其算法復(fù)雜度較高。文獻[9]的FIMM算法在挖掘頻繁項集的過程中其運行時間不受支持度閾值的影響，改善了算法的計算復(fù)雜度；然而，事務(wù)數(shù)據(jù)庫數(shù)據(jù)量很大時，其結(jié)果也不理想。

針對以上問題，在分析智能調(diào)度中數(shù)據(jù)特點的基礎(chǔ)上，建立了智能調(diào)度多源異構(gòu)數(shù)據(jù)分析模型，實現(xiàn)了多源異構(gòu)數(shù)據(jù)為智能調(diào)度創(chuàng)造價值。根據(jù)該模型中的關(guān)聯(lián)分析，根據(jù)組合學(xué)原理，結(jié)合MapReduce思想，提出基于大數(shù)據(jù)的頻繁項集挖掘算法(Frequent Itemset Mining Based on Big data，F(xiàn)IMBB)。該算法只掃描一次原始事務(wù)數(shù)據(jù)庫來完成整個頻繁項集的挖掘過程；利用大數(shù)據(jù)中的MapReduce平臺并行挖掘出最終的所有目標頻繁項集，整個流程采用了分布式和并行的思想，挖掘效率得到有效提高。

1 基于大數(shù)據(jù)的智能調(diào)度多源異構(gòu)數(shù)據(jù)分析模型

智能調(diào)度大數(shù)據(jù)分析的主要思想為使用適當(dāng)?shù)拇髷?shù)據(jù)工具，抽取和集成多源異構(gòu)數(shù)據(jù)，按照分析需求的統(tǒng)一格式存儲預(yù)處理后的數(shù)據(jù)，采用數(shù)據(jù)分析和數(shù)據(jù)挖掘技術(shù)對存儲的數(shù)據(jù)進行分析和深度挖掘，以提取出隱藏在數(shù)據(jù)中的知識，并根據(jù)智能調(diào)度的新需求，形成新的智能應(yīng)用。

1.1 智能調(diào)度多源異構(gòu)數(shù)據(jù)特點分析

調(diào)度環(huán)節(jié)的數(shù)據(jù)在傳統(tǒng)電網(wǎng)基礎(chǔ)上，數(shù)據(jù)來源、種類、規(guī)模都有了極大的擴充和豐富[10]，這些來自于不同系統(tǒng)的數(shù)據(jù)彼此之間有一定的關(guān)聯(lián)性，不完全獨立，這些數(shù)據(jù)結(jié)構(gòu)復(fù)雜、數(shù)據(jù)量很大，彼此之間存在著復(fù)雜的關(guān)系。根據(jù)大數(shù)據(jù)的基本特征和電網(wǎng)調(diào)度的具體特點，智能調(diào)度多源異構(gòu)數(shù)據(jù)具有以下特征：

(1)數(shù)據(jù)來自各調(diào)度中心，每個調(diào)度中心的數(shù)據(jù)又來源于多個系統(tǒng)，包括SCADA、EMS、WAMS、AMI、OMS、GIS等。每個系統(tǒng)采集到的數(shù)據(jù)模型、格式、特點不完全相同。

(2)數(shù)據(jù)規(guī)模大，維度多，實時性強。晉城供電公司SCADA系統(tǒng)大概總共有80 000個遙測點，采樣間隔按4 s計算，每年將產(chǎn)生11.014 TB的數(shù)據(jù)。具體計算公式為:

11.014 TB=(12字節(jié)/幀×0.4幀/s×80 000遙測點×86 400 s/天×365天)/240

(3)數(shù)據(jù)的真實性和安全性高[11]。高質(zhì)量電網(wǎng)調(diào)度數(shù)據(jù)對于數(shù)據(jù)分析和挖掘至關(guān)重要；調(diào)度是電網(wǎng)的中樞神經(jīng)，數(shù)據(jù)的安全性是電網(wǎng)穩(wěn)定、安全和可靠運行的前提條件。

(4)數(shù)據(jù)源之間的關(guān)聯(lián)性強，集成全面分析產(chǎn)生的結(jié)果具有很大的經(jīng)濟和社會價值。例如，負荷預(yù)測[12]是智能調(diào)度中的一個關(guān)鍵應(yīng)用，其預(yù)測主要以負荷數(shù)據(jù)為主，但是負荷預(yù)測與氣象、地理、人口、經(jīng)濟等方面的數(shù)據(jù)有一定關(guān)聯(lián)，若利用大數(shù)據(jù)技術(shù)，將這些相關(guān)的數(shù)據(jù)源進行全面負荷預(yù)測，將為電力用戶創(chuàng)造極大的價值。

1.2 基于大數(shù)據(jù)的多源異構(gòu)數(shù)據(jù)分析模型建立

與傳統(tǒng)數(shù)據(jù)分析的主要區(qū)別在于：智能調(diào)度中大數(shù)據(jù)分析的數(shù)據(jù)往往包括大量的結(jié)構(gòu)化、半結(jié)構(gòu)化和非結(jié)構(gòu)化數(shù)據(jù)。從數(shù)據(jù)來源到數(shù)據(jù)應(yīng)用整個數(shù)據(jù)分析過程中，每個環(huán)節(jié)均能利用大數(shù)據(jù)處理平臺Hadoop、MapReduce[12]等方式進行并行處理。根據(jù)智能調(diào)度多源異構(gòu)數(shù)據(jù)的特征和大數(shù)據(jù)思想，建立了基于大數(shù)據(jù)的智能調(diào)度多源異構(gòu)數(shù)據(jù)分析模型，如圖1所示。

圖1 基于智能調(diào)度多源異構(gòu)數(shù)據(jù)分析模型

圖1描述了將電網(wǎng)智能調(diào)度的數(shù)據(jù)轉(zhuǎn)化為對調(diào)度管理和決策有益的知識的過程，打破了調(diào)度控制系統(tǒng)中各系統(tǒng)之間的信息孤島。在異構(gòu)數(shù)據(jù)源層，SCADA、WAMS等系統(tǒng)都會產(chǎn)生海量數(shù)據(jù)，這些系統(tǒng)彼此不相同，數(shù)據(jù)類型復(fù)雜，因此需要首先對數(shù)據(jù)源的數(shù)據(jù)進行ETL預(yù)處理，保證數(shù)據(jù)質(zhì)量及可靠性。NoSQL[13]數(shù)據(jù)庫技術(shù)是一種分布式數(shù)據(jù)存儲方式，具有良好的可擴展性，解決了海量數(shù)據(jù)的存儲難題。其中代表性的包括Google的BigTable和Amazon的Dynamo等。在云計算[14]平臺上，完成智能調(diào)度海量信息的可靠存儲和快速并行處理。對存儲后的數(shù)據(jù)通過數(shù)據(jù)挖掘等數(shù)據(jù)分析技術(shù)，將廣泛的異構(gòu)數(shù)據(jù)分類，這樣多源異構(gòu)數(shù)據(jù)源通過數(shù)據(jù)預(yù)處理和分析挖掘轉(zhuǎn)化成了面向主題的、集成的調(diào)度全景大數(shù)據(jù)，如設(shè)備基礎(chǔ)數(shù)據(jù)倉庫、告警類數(shù)據(jù)倉庫等統(tǒng)一數(shù)據(jù)模型，從而為系統(tǒng)提供全面的數(shù)據(jù)共享。將各類電網(wǎng)內(nèi)外部數(shù)據(jù)和相應(yīng)的調(diào)度業(yè)務(wù)數(shù)據(jù)進行結(jié)合，形成新的智能調(diào)度大數(shù)據(jù)應(yīng)用場景。關(guān)聯(lián)分析在智能調(diào)度數(shù)據(jù)分析挖掘中具有廣泛應(yīng)用，分析歷史故障數(shù)據(jù)，找出故障之間的相關(guān)性，為快速找出根源故障，提供故障預(yù)測參考。

2 FIMBB算法

圖2 FIMBB算法流程

Mapping階段算法的主要思想是：首先將輸入的故障事務(wù)數(shù)據(jù)轉(zhuǎn)化成程序中的統(tǒng)一格式，設(shè)置頻繁項集挖掘的最小支持度閾值和k頻繁項集的上限；讀取每一條處理后的事務(wù)數(shù)據(jù)，將每條數(shù)據(jù)在滿足項數(shù)上限的條件下組合事務(wù)，輸出〈Key,Value〉。

算法主要步驟為：

(1)將電網(wǎng)故障事務(wù)數(shù)據(jù)庫的事務(wù)記錄逐條讀入；

(2)每條事務(wù)記錄按照自然項進行處理；

(3)根據(jù)組合學(xué)原理，完成調(diào)整后的事務(wù)中項的組合；

(4)根據(jù)項的組合集合以〈Key,Value〉的形式輸出，其中Key為事務(wù)記錄項的組合，Value為1。

在Reducing階段，將Map階段的輸出當(dāng)作輸入，合并相同的項集的計數(shù)。具體步驟為：當(dāng)讀到非空項集時，將項集的計數(shù)累加，然后統(tǒng)計其支持度；如果其支持度大于等于其最小支持度閾值，輸出該項集。

3 實驗與結(jié)果分析

實驗分析中，采用人工隨機電網(wǎng)調(diào)度中的故障信息事務(wù)集Datafile進行實驗，其中故障事務(wù)中包含10個不同的故障信息項，并和Apriori、FIMM算法進行性能比較。FIMBB算法是基于臺式機搭建的Hadoop平臺，該平臺由三臺計算機集群組成。其中，兩臺機器作為DataNodes和TaskTrackers，這兩臺計算機配置了N3700核心處理器(主頻1.6 GHz)和4 GB內(nèi)存；第三臺計算機作為NameNode和JobTracker，其配置了G3260雙核處理器(主頻3.3 GHz)和4 GB內(nèi)存。網(wǎng)絡(luò)環(huán)境為同一局域網(wǎng)。實驗結(jié)果如圖3和圖4所示。

圖3 三種算法運行時間隨著支持度閾值的變化趨勢

圖4 運行時間隨事務(wù)數(shù)據(jù)量的變化趨勢

從圖3可以看到，F(xiàn)IMM和FIMBB算法的運行時間基本不受支持度閾值的影響，而Apriori算法的運行時間和支持度閾值的變化有很大關(guān)系，原因在于隨著支持度的增大，Apriori算法產(chǎn)生的候選項集數(shù)目變少，從候選集中找出真正的頻繁項集相應(yīng)所需的時間就變少。

從圖4可以看到，F(xiàn)IMM算法運行時間與事務(wù)數(shù)據(jù)量大小基本呈線性關(guān)系：當(dāng)事務(wù)數(shù)據(jù)量小于600時，F(xiàn)IMM的運行時間小于FIMBB；當(dāng)事務(wù)數(shù)大于600時，F(xiàn)IMBB運行效率明顯高于FIMM。因為FIMBB算法在事務(wù)數(shù)據(jù)量較少時花費在配置運行環(huán)境和節(jié)點間通信上的時間占很大比例，當(dāng)事務(wù)數(shù)據(jù)量較大時，F(xiàn)IMBB算法的運行效率具有很大優(yōu)勢。在事務(wù)數(shù)較多時，Apriori算法的運行效率明顯要低于其他兩種算法，原因在于事務(wù)數(shù)據(jù)量越大，Apriori算法將產(chǎn)生大量的候選集且需要多次掃描原始事務(wù)數(shù)據(jù)庫，因此耗時較多。當(dāng)對不同數(shù)據(jù)量的事務(wù)進行挖掘時，F(xiàn)IMBB算法的加速比如表1所示。

表1 FIMBB加速比

根據(jù)理想加速比公式得到集群中機器臺數(shù)分別為2和3的理想加速比為2和3。從表1可以看出，在實際運行中得到的加速比往往和理想的差別很大。主要是由每臺機器的硬件性能不完全相同造成的。另外，加速比計算公式為：

其中，Tq、Ts分別為集群和單機運行算法的時間開銷；c1、c2為兩者的系統(tǒng)開銷。當(dāng)事務(wù)數(shù)據(jù)量很大時，計算加速比可忽略系統(tǒng)開銷。

從以上分析可知：對于大量的事務(wù)數(shù)據(jù)，F(xiàn)IMBB算法的性能優(yōu)于FIMM和Apriori算法，且具有很好的可擴展性，適用于智能調(diào)度中大量故障事務(wù)的頻繁項集挖掘。

4 結(jié)束語

調(diào)度數(shù)據(jù)分析和處理是實現(xiàn)智能調(diào)度的關(guān)鍵，在分析智能調(diào)度數(shù)據(jù)特點的基礎(chǔ)上，根據(jù)智能調(diào)度大數(shù)據(jù)的需求，構(gòu)建基于大數(shù)據(jù)的智能調(diào)度多源異構(gòu)數(shù)據(jù)分析模型，實現(xiàn)了通過大數(shù)據(jù)挖掘技術(shù)，將調(diào)度控制系統(tǒng)中的多源異構(gòu)數(shù)據(jù)轉(zhuǎn)化成智能調(diào)度的有價值信息。FIMBB算法是一種針對大量電網(wǎng)調(diào)度事務(wù)數(shù)據(jù)的頻繁項集挖掘算法。該算法將分布式計算的思想引入挖掘頻繁項集中。

根據(jù)組合學(xué)原理，利用MapReduce掃描一次數(shù)據(jù)庫從原始事務(wù)數(shù)據(jù)庫中完成頻繁項集的整個挖掘過程；且在支持度閾值改變的情況下無需重新掃描數(shù)據(jù)庫進行挖掘，提高了頻繁項集的挖掘效率。實驗結(jié)果表明，該算法不受支持度閾值的影響，且對于大量事務(wù)數(shù)據(jù)，運行效率高，適用于智能調(diào)度大數(shù)據(jù)的關(guān)聯(lián)分析。大數(shù)據(jù)在智能調(diào)度中的應(yīng)用價值不可估量，但是，要加速智能調(diào)度化的進程，需要在多源數(shù)據(jù)融合和全景數(shù)據(jù)深度分析方面有所突破。

[1] 劉振亞．智能電網(wǎng)技術(shù)[M]．北京：中國電力出版社,2010．

[2] 辛耀中,石俊杰,周京陽,等.智能電網(wǎng)調(diào)度控制系統(tǒng)現(xiàn)狀與技術(shù)展望[J].電力系統(tǒng)自動化,2015,39(1):2-8.

[3] Agrawal R， Imieliński T， Swami A．Mining association rules between sets of items in large databases[C]//Proceedings of the ACM SIGMOD conference on management of data．Washington，D C：ACM，1993：207-216．

[4] Han Jiawei，Pei Jian，Yin Yiwen．Mining frequent patterns wi-thout candidate generation[C]//Proceedings of the ACM SIGMOD conference on management of data．Dallas，TX：ACM，2000：1-12．

[5] Baralis E， Cerquitelli T， Chiusano S，et al．Scalable out-of-core itemset mining[J]．Information Sciences，2015，293(4)：146-162．

[6] Baralis E，Cerquitelli T，Chiusano S．A persistent HY-Tree to efficiently support itemset mining on large datasets[C]//Proceedings of the 2010 ACM symposium on applied computing．New York：ACM，2010：1060-1064．

[7] Adnan M，Alhajj R．DRFP-tree:disk-resident frequent pattern tree[J]．Applied Intelligence，2009，30(2)：84-97．

[8] Buehrer G，Parthasarathy S，Ghoting A．Out-of-core frequent pattern mining on a commodity PC[C]//Proceedings of the 12th ACM SIGKDD international conference on knowledge discovery and data mining．New York：ACM，2006：86-95．

[9] 張東霞,苗 新,劉麗平,等.智能電網(wǎng)大數(shù)據(jù)技術(shù)發(fā)展研究[J].中國電機工程學(xué)報,2015,35(1):2-12.

[10] 宋亞奇,周國亮,朱永利.智能電網(wǎng)大數(shù)據(jù)處理技術(shù)現(xiàn)狀與挑戰(zhàn)[J].電網(wǎng)技術(shù),2013,37(4):927-935.

[11] 彭小圣,鄧迪元,程時杰,等.面向智能電網(wǎng)應(yīng)用的電力大數(shù)據(jù)關(guān)鍵技術(shù)[J].中國電機工程學(xué)報,2015,35(3):503-511.

[12] 李建江,崔 健,王 聃,等.MapReduce并行編程模型研究綜述[J].電子學(xué)報,2011,39(11):2635-2642.

[13] 孟小峰,慈 祥.大數(shù)據(jù)管理:概念、技術(shù)與挑戰(zhàn)[J].計算機研究與發(fā)展,2013,50(1):146-169.

[14] 吳凱峰,劉萬濤,李彥虎,等.基于云計算的電力大數(shù)據(jù)分析技術(shù)與應(yīng)用[J].中國電力,2015(2):111-116.

Frequent Itemset Mining Algorithm for Multi-source Heterogeneous Information

LIU Zi-li1，F(xiàn)AN Jun-li2，CHEN Wen-wei3，WU Run-ze3

(1.Jincheng Power Supply Company,State Grid Shanxi Electric Power Company,Jincheng 048000,China; 2.Beijing Guodiantong Network Technology Co.，Ltd.,Beijing 100070,China; 3.School of Electrical and Electronic Engineering,North China Electric Power University,Beijing 102206,China)

Power grid dispatching has produced large amount of multi-source heterogeneous data with high complexity,and it is the inevitable development trend of intelligent dispatching that power data are transformed into knowledge by data mining.An analysis model of multi-source heterogeneous data based on big data in power dispatching and control system has been established and a frequent item set mining algorithm for processing big data has been proposed.The distributed statistics has been introduced into mining frequent item sets.Combining MapReduce programming and combinatorics,the target frequent item set mining has been completed via scanning transaction database with the proposed algorithm and thus there is no need to scan database again for mining while support degree is under variation.This algorithm has been promoted to solve the problem of multiple scanning transaction database and low mining efficiency.Compared with other frequent item set mining,the algorithm takes advantage of Hadoop in dealing with fault information transaction database.Experimental results show that the proposed algorithm performs well in expansibility and has less time cost with large transaction database and that the method adopted has provided useful knowledge for intelligent analysis and decision making with comprehensive optimal objectives of accuracy,security,economic and others,which single data source could not achieve.

intelligent dispatching;frequent itemsets;combinatorics;Hadoop

2016-06-20

2016-09-22 網(wǎng)絡(luò)出版時間：2017-04-28

國家自然科學(xué)基金資助項目(51507063)

劉自力(1969-)，男，電力高級工程師，研究方向為電力通信技術(shù)及網(wǎng)絡(luò)規(guī)劃。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170428.1702.028.html

TP39

A

1673-629X(2017)06-0076-05

10.3969/j.issn.1673-629X.2017.06.016