面向多源異構信息的頻繁項集挖掘算法

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

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

面向多源異構信息的頻繁項集挖掘算法

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

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

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

智能調度；頻繁項集；組合理論；Hadoop

0 引 言

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

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

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

1 基于大數據的智能調度多源異構數據分析模型

智能調度大數據分析的主要思想為使用適當的大數據工具，抽取和集成多源異構數據，按照分析需求的統一格式存儲預處理后的數據，采用數據分析和數據挖掘技術對存儲的數據進行分析和深度挖掘，以提取出隱藏在數據中的知識，并根據智能調度的新需求，形成新的智能應用。

1.1 智能調度多源異構數據特點分析

調度環節的數據在傳統電網基礎上，數據來源、種類、規模都有了極大的擴充和豐富[10]，這些來自于不同系統的數據彼此之間有一定的關聯性，不完全獨立，這些數據結構復雜、數據量很大，彼此之間存在著復雜的關系。根據大數據的基本特征和電網調度的具體特點，智能調度多源異構數據具有以下特征：

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

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

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

(3)數據的真實性和安全性高[11]。高質量電網調度數據對于數據分析和挖掘至關重要；調度是電網的中樞神經，數據的安全性是電網穩定、安全和可靠運行的前提條件。

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

1.2 基于大數據的多源異構數據分析模型建立

與傳統數據分析的主要區別在于：智能調度中大數據分析的數據往往包括大量的結構化、半結構化和非結構化數據。從數據來源到數據應用整個數據分析過程中，每個環節均能利用大數據處理平臺Hadoop、MapReduce[12]等方式進行并行處理。根據智能調度多源異構數據的特征和大數據思想，建立了基于大數據的智能調度多源異構數據分析模型，如圖1所示。

圖1 基于智能調度多源異構數據分析模型

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

2 FIMBB算法

圖2 FIMBB算法流程

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

算法主要步驟為：

(1)將電網故障事務數據庫的事務記錄逐條讀入；

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

(3)根據組合學原理，完成調整后的事務中項的組合；

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

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

3 實驗與結果分析

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

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

圖4 運行時間隨事務數據量的變化趨勢

從圖3可以看到，FIMM和FIMBB算法的運行時間基本不受支持度閾值的影響，而Apriori算法的運行時間和支持度閾值的變化有很大關系，原因在于隨著支持度的增大，Apriori算法產生的候選項集數目變少，從候選集中找出真正的頻繁項集相應所需的時間就變少。

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

表1 FIMBB加速比

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

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

從以上分析可知：對于大量的事務數據，FIMBB算法的性能優于FIMM和Apriori算法，且具有很好的可擴展性，適用于智能調度中大量故障事務的頻繁項集挖掘。

4 結束語

調度數據分析和處理是實現智能調度的關鍵，在分析智能調度數據特點的基礎上，根據智能調度大數據的需求，構建基于大數據的智能調度多源異構數據分析模型，實現了通過大數據挖掘技術，將調度控制系統中的多源異構數據轉化成智能調度的有價值信息。FIMBB算法是一種針對大量電網調度事務數據的頻繁項集挖掘算法。該算法將分布式計算的思想引入挖掘頻繁項集中。

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

[1] 劉振亞．智能電網技術[M]．北京：中國電力出版社,2010．

[2] 辛耀中,石俊杰,周京陽,等.智能電網調度控制系統現狀與技術展望[J].電力系統自動化,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] 張東霞,苗 新,劉麗平,等.智能電網大數據技術發展研究[J].中國電機工程學報,2015,35(1):2-12.

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

[11] 彭小圣,鄧迪元,程時杰,等.面向智能電網應用的電力大數據關鍵技術[J].中國電機工程學報,2015,35(3):503-511.

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

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

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

Frequent Itemset Mining Algorithm for Multi-source Heterogeneous Information

LIU Zi-li1，FAN 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 網絡出版時間：2017-04-28

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

劉自力(1969-)，男，電力高級工程師，研究方向為電力通信技術及網絡規劃。

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