潘磊

摘 要：為了提高電力系統(tǒng)中故障預(yù)測效率及便捷性，提出一種基于FP-Growth算法的電力系統(tǒng)故障預(yù)測方法，無需先驗(yàn)知識及人工標(biāo)注，便可從海量歷史日志數(shù)據(jù)中快速提取出故障信息模式，并基于實(shí)時(shí)日志數(shù)據(jù)對未來可能發(fā)送的系統(tǒng)故障進(jìn)行預(yù)測。該方法首先根據(jù)電力系統(tǒng)不同類型的日志特征對原始數(shù)據(jù)進(jìn)行預(yù)處理，然后基于FP-Growth算法挖掘日志中與故障事件相關(guān)的關(guān)聯(lián)規(guī)則，并使用關(guān)聯(lián)規(guī)則進(jìn)行故障匹配，從而達(dá)到預(yù)測效果。算法經(jīng)過真實(shí)電力系統(tǒng)日志數(shù)據(jù)集測試，結(jié)果表明該故障預(yù)測方法平均準(zhǔn)確率為89.5%，平均召回率為79.8%，且執(zhí)行效率較高，節(jié)省了業(yè)務(wù)人員50%以上的時(shí)間。

關(guān)鍵詞：FP-Growth;電力系統(tǒng)日志;關(guān)聯(lián)規(guī)則;故障預(yù)測;日志挖掘

DOI：10. 11907/rjdk. 201852

中圖分類號：TP301文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2020）010-0152-04

Abstract：In order to improve the efficiency and convenience of fault prediction in the power system， a power system fault prediction method based on the FP-Growth algorithm is proposed by this paper. The method can extract fault prediction rules quickly from the massive power system history logs without any prior knowledge and manual annotation， and then predict future system failures based on the real-time logs. Firstly， the original logs are preprocessed according to the characteristics of the power system logs. Then the association rules related to the failure event in the log are mined based on the FP-Growth algorithm， and the association rules are used to match the failure. The algorithm has been tested on real power system log data sets. The results show that the average accuracy of the fault prediction method in this paper is 89.5%， the average recall rate is 79.8%， and the execution efficiency is high， saving more than 50% of the time of business staff.

Key Words：FP-Growth; power system log; association rule;fault prediction; log mining

0 引言

電力工業(yè)是我國國民經(jīng)濟(jì)發(fā)展中的支柱型產(chǎn)業(yè)，電力系統(tǒng)為電力工業(yè)穩(wěn)定運(yùn)行提供了保障。隨著電力系統(tǒng)規(guī)模的擴(kuò)大和復(fù)雜性的增加，系統(tǒng)故障發(fā)生已經(jīng)成為一種常態(tài)[1]。嚴(yán)重的系統(tǒng)故障可能導(dǎo)致重要信息丟失甚至系統(tǒng)癱瘓，造成難以預(yù)料的后果。精確高效的故障預(yù)測能夠降低嚴(yán)重故障所帶來的風(fēng)險(xiǎn)，提高電力系統(tǒng)可靠性[2]。

故障預(yù)測最常用模型主要有兩類：故障歷史數(shù)據(jù)分析模型和實(shí)時(shí)狀態(tài)監(jiān)控預(yù)測模型[3-4]。許多學(xué)者對其進(jìn)行了研究，馮士龍等[5]通過滑動(dòng)窗口方式將日志劃分為日志序列并將其向量化，從而進(jìn)行日志異常檢測;文獻(xiàn)[6]分別使用數(shù)據(jù)挖掘的分類預(yù)測思想和基于概率統(tǒng)計(jì)的方法，分析系統(tǒng)日志并建立故障預(yù)測模型;文獻(xiàn)[7]通過提取日志模板建立故障分類器模型，可動(dòng)態(tài)判斷當(dāng)前新增日志是否與故障有關(guān);王衛(wèi)華等[8]提出一種基于頻繁日志事件序列的聚類算法，挖掘與故障事件相關(guān)的事件序列，從而實(shí)現(xiàn)故障預(yù)測;年夫順[9] 對各領(lǐng)域設(shè)備故障預(yù)測關(guān)鍵技術(shù)進(jìn)行綜述，包括故障模型、狀態(tài)監(jiān)控和故障預(yù)測等。

系統(tǒng)故障往往不是獨(dú)立產(chǎn)生的，而是與其它事件相關(guān)聯(lián)[10]。因此，可以通過機(jī)器學(xué)習(xí)算法挖掘包含故障事件的頻繁日志序列，根據(jù)日志事件的相關(guān)性進(jìn)行故障預(yù)測[11-14]。在一般的機(jī)器學(xué)習(xí)問題中，F(xiàn)P-Growth方法通常被用來做關(guān)聯(lián)分析，而本文將其應(yīng)用于無監(jiān)督學(xué)習(xí)問題中，提出一種基于FP-Growth算法的電力系統(tǒng)故障預(yù)測方法，該方法在不需要先驗(yàn)知識和專家干預(yù)的前提下，分析電力系統(tǒng)歷史日志數(shù)據(jù)，以及與故障事件相關(guān)的頻繁日志序列并抽取出關(guān)聯(lián)規(guī)則，再根據(jù)關(guān)聯(lián)規(guī)則對系統(tǒng)故障進(jìn)行預(yù)測。該方法在真實(shí)數(shù)據(jù)集上進(jìn)行測試與評估，且在實(shí)際應(yīng)用中取得一定效果。

1 電力系統(tǒng)日志分析

1.1 日志結(jié)構(gòu)

通常情況下，電力系統(tǒng)日志記錄與電力系統(tǒng)設(shè)備、軟件相關(guān)的操作和狀態(tài)，如設(shè)備連接和斷開、操作成功和失敗等。由于不同電力系統(tǒng)的日志格式不統(tǒng)一，日志文本多為非結(jié)構(gòu)化文本，因此其語法和語義也不盡相同。本文以甘肅省電力投資集團(tuán)有限責(zé)任公司電力系統(tǒng)2018年1月到6月的日志數(shù)據(jù)為例，該電力系統(tǒng)日志示例如圖1所示。

由圖1可知，日志數(shù)據(jù)通常包括兩種類型的信息：一種是文本格式固定的日志語義信息;另一種是變量或參數(shù)，例如IP地址、時(shí)間、設(shè)備名稱等，用于表示信息的重要屬性。由于原始日志數(shù)據(jù)存在較多與語義無關(guān)的參數(shù)，或者是重復(fù)的日志數(shù)據(jù)，因此需要對電力系統(tǒng)日志進(jìn)行預(yù)處理。

1.2 日志預(yù)處理

參數(shù)類型的多樣性導(dǎo)致日志數(shù)據(jù)的數(shù)量非常多，海量的日志數(shù)據(jù)代表的事件數(shù)量卻有限，為了消除變量和參數(shù)對故障預(yù)測的影響，本文使用“X”替換日志數(shù)據(jù)中的IP地址、時(shí)間和設(shè)備名稱等變量，使得提取日志數(shù)據(jù)中所代表的事件更容易，同時(shí)方便后續(xù)的關(guān)聯(lián)規(guī)則挖掘。

系統(tǒng)集群出現(xiàn)故障時(shí)，往往會(huì)重復(fù)故障操作，例如重復(fù)要求連接等，此時(shí)相似或者相同的事件將被頻繁記錄到日志中，導(dǎo)致存在冗余日志。當(dāng)發(fā)現(xiàn)相同的日志數(shù)據(jù)重復(fù)出現(xiàn)時(shí)，本文只保留第一條記錄，刪除其它后續(xù)記錄，消除冗余日志對關(guān)聯(lián)規(guī)則挖掘的負(fù)面影響。

2 關(guān)聯(lián)規(guī)則挖掘

2.1 基本概念

關(guān)聯(lián)規(guī)則挖掘?qū)儆跀?shù)據(jù)挖掘的一種研究方法，用以發(fā)現(xiàn)事務(wù)及關(guān)聯(lián)項(xiàng)之間的關(guān)系[15]。設(shè)[I={a1，a2，...，an}]，其中a為n個(gè)不同的項(xiàng)，I稱為總項(xiàng)集，記N是事務(wù)處理S的集合，每個(gè)事務(wù)處理S是項(xiàng)的集合，則[S?I]。設(shè)X、Y是I的兩個(gè)不同非空子集，如果有[X→Y]，則稱其是一條關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則的衡量標(biāo)準(zhǔn)用支持度support和置信度confident描述。式（1）和式（2）為support和confident的定義。

其中，support表示X與Y同時(shí)在事務(wù)集中出現(xiàn)的次數(shù)與事務(wù)總數(shù)N的比率，confident表示X與Y同時(shí)出現(xiàn)的次數(shù)與X單獨(dú)出現(xiàn)次數(shù)的比率。關(guān)聯(lián)規(guī)則的支持度和置信度越高，說明規(guī)則的關(guān)聯(lián)性越強(qiáng)。

關(guān)聯(lián)規(guī)則挖掘的本質(zhì)就是給定事務(wù)集N，找出其中所有支持度不小于最小支持度min_support且置信度不小于最小置信度min_confident的關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則挖掘一般由兩步組成：①找出所有不小于最小支持度的項(xiàng)集，該項(xiàng)集稱為頻繁項(xiàng)集;②基于頻繁項(xiàng)集再生成不小于最小置信度的規(guī)則，該規(guī)則稱為強(qiáng)規(guī)則。

關(guān)聯(lián)規(guī)則挖掘經(jīng)典算法Apriori，是由候選頻繁項(xiàng)集產(chǎn)生規(guī)則的算法代表，但Apriori在進(jìn)行候選消除時(shí)，會(huì)產(chǎn)生大量的候選集，同時(shí)每次消除也可能重復(fù)掃描事務(wù)集，面對海量日志數(shù)據(jù)集時(shí)算法效率較低。FP-Growth是一種關(guān)聯(lián)規(guī)則挖掘算法，它通過兩次掃描事務(wù)集構(gòu)造頻繁項(xiàng)樹實(shí)現(xiàn)頻繁項(xiàng)集挖掘，整個(gè)挖掘過程不必產(chǎn)生候選頻繁項(xiàng)集合[15]。FP-Growth算法處理海量數(shù)據(jù)時(shí)效率很高，適合運(yùn)用在海量數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘中，因此本文采用它挖掘歷史日志數(shù)據(jù)并生成故障事件關(guān)聯(lián)規(guī)則。

2.2 FP-Growth算法概述

FP-Growth算法基于Apriori原理，通過將事務(wù)集存儲(chǔ)到FP-tree（Frequent Pattern tree，頻繁項(xiàng)樹），進(jìn)而挖掘頻繁項(xiàng)和關(guān)聯(lián)規(guī)則。FP-Growth算法挖掘關(guān)聯(lián)規(guī)則流程如圖2所示。

具體過程描述如下：

（1）掃描事務(wù)集N，找出所有頻繁模式下的頻繁項(xiàng)F1，將F1按支持度降序排序，生成頻繁項(xiàng)頭表。

（2）再次掃描事務(wù)集N，建立頻繁模式樹FP-tree并填寫頭表指針。FP-tree是一棵前綴樹，根節(jié)點(diǎn)是標(biāo)記為“NULL”的root，不表示任何項(xiàng)，其余節(jié)點(diǎn)包含頻繁項(xiàng)和該項(xiàng)在本條路徑上的支持度。一條路徑上的節(jié)點(diǎn)集合都是事務(wù)集中滿足最小支持度的頻繁項(xiàng)集合，其中節(jié)點(diǎn)按照項(xiàng)的支持度排列，支持度越高的項(xiàng)離根節(jié)點(diǎn)越近，從而使更多的項(xiàng)可共享前綴。建立樹之后，填寫頻繁項(xiàng)頭表的指針，指向樹中該項(xiàng)的節(jié)點(diǎn)。同時(shí)相同的頻繁項(xiàng)之間使用指針相連。

（3）從底部遍歷頻繁項(xiàng)頭表。當(dāng)遍歷未結(jié)束時(shí)，挖掘該項(xiàng)的頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則。當(dāng)遍歷完整個(gè)表之后，結(jié)束FP-Growth算法。

（4）提取頻繁項(xiàng)條件模式基。設(shè)此時(shí)遍歷的頻繁項(xiàng)為a，存在從root節(jié)點(diǎn)到節(jié)點(diǎn)a的路徑L，L上不包含a的部分所組成的路徑稱為a的前綴路徑Lp，a為Lp的后綴項(xiàng)。樹中可能存在多個(gè)a節(jié)點(diǎn)，則會(huì)得到多個(gè)前綴路徑，所有前綴路徑組成頻繁項(xiàng)a的條件模式基。

（5）判斷頻繁項(xiàng)a是否存在條件模式基，若其存在則繼續(xù)算法，否則返回到遍歷頻繁項(xiàng)頭表。

（6）得到頻繁項(xiàng)a的條件模式基后，將其作為新事務(wù)集建立一棵新的FP-tree，稱為a的條件模式樹。

（7）挖掘頻繁項(xiàng)集，生成關(guān)聯(lián)規(guī)則。首先在a的條件模式樹上挖掘頻繁項(xiàng)集，可得到與a相關(guān)的頻繁項(xiàng)集。若該頻繁項(xiàng)集中的任一項(xiàng)仍存在條件模式基，即遞歸重復(fù)地提取頻繁項(xiàng)集，直至所有頻繁項(xiàng)都沒有條件模式基，此時(shí)得到所有的頻繁項(xiàng)集。使用頻繁項(xiàng)集生成關(guān)聯(lián)規(guī)則，滿足最小置信度的規(guī)則即為有效規(guī)則。

3 故障預(yù)測

3.1 故障預(yù)測規(guī)則提取

電力系統(tǒng)日志數(shù)據(jù)經(jīng)過預(yù)處理后，對于每一類故障事件f，通過截取發(fā)生在f之前相同時(shí)間內(nèi)的日志序列，生成故障事件相關(guān)的日志序列，所有f的相關(guān)日志序列組成日志序列集合N。

對f的日志序列集N進(jìn)行分析，統(tǒng)計(jì)不同日志數(shù)據(jù)項(xiàng)生成總項(xiàng)集[I={a1，a2，...，an，f}]，a表示與事件f相關(guān)的日志數(shù)據(jù)。從總項(xiàng)集I中截取若干連續(xù)子序列[{am+1，am+2，...，] [am+j}]，生成故障預(yù)測規(guī)則[r={am+1，am+2，...，am+j}→f]。此時(shí)的項(xiàng)集[{am+1，am+2，...，am+j，f}]即為頻繁項(xiàng)集，預(yù)測規(guī)則即為滿足置信度要求的關(guān)聯(lián)規(guī)則，故可使用FP-Growth算法提取預(yù)測規(guī)則。

經(jīng)過詢問電力系統(tǒng)運(yùn)維專家和實(shí)驗(yàn)驗(yàn)證，本文使用的最小支持度min_support為0.6，最小置信度min_confident為0.8，提取的所有故障預(yù)測規(guī)則r組成預(yù)測規(guī)則集R。

3.2 預(yù)測步驟

得到預(yù)測規(guī)則集R后，可根據(jù)實(shí)時(shí)的最新日志數(shù)據(jù)對系統(tǒng)故障進(jìn)行預(yù)測。故障預(yù)測與時(shí)間緊密相關(guān)，假設(shè)T1表示預(yù)測模型預(yù)測故障f的時(shí)間，T2表示故障f實(shí)際發(fā)生時(shí)間，T3表示本次預(yù)測失效時(shí)間。若[T1

（1）生成待定規(guī)則集。對于故障預(yù)測規(guī)則[r={am+1，am+2，...，am+j}→f]，用[am+j]匹配當(dāng)前產(chǎn)生的日志數(shù)據(jù)，當(dāng)日志[am+j]產(chǎn)生時(shí)，選取以[am+j]結(jié)束的規(guī)則作為待定規(guī)則，所有待定規(guī)則組成待定規(guī)則集。

（2）生成驗(yàn)證規(guī)則集。截取日志[am+j]之前n行（這里n為參數(shù)）的日志數(shù)據(jù)序列段S，判斷S是否包含[{am+1，am+2，...，am+j-1}]規(guī)則集，若包含則匹配成功，將該待定規(guī)則加入驗(yàn)證規(guī)則集，并記錄預(yù)測時(shí)間T1。

（3）故障預(yù)測。對于驗(yàn)證規(guī)則集中的規(guī)則[r→f]，預(yù)測故障事件f應(yīng)在T3時(shí)間點(diǎn)之前發(fā)生。若f在時(shí)間點(diǎn)T3之前發(fā)生，則此次預(yù)測成功，否則預(yù)測失敗。

4 實(shí)驗(yàn)評估

本文獲取甘肅省電力投資集團(tuán)有限責(zé)任公司某電力系統(tǒng)中的50萬余條日志，日志時(shí)間范圍從2018年1月—2018年6月。在該日志數(shù)據(jù)集中，日志數(shù)據(jù)包含ERROR、FAIL、WRONG和FATAL等關(guān)鍵字，表示系統(tǒng)出現(xiàn)故障。本文將包含這4種關(guān)鍵詞的日志記錄標(biāo)識為故障事件，其它日志則標(biāo)識為正常事件。

本文使用了準(zhǔn)確率accuracy、召回率recall對模型的預(yù)測效果進(jìn)行評估。其中，準(zhǔn)確率的計(jì)算方法如式（3）所示，召回率如式（4）所示。

[accuracy=正確預(yù)測的次數(shù)總預(yù)測次數(shù)] （3）

[recall=正確預(yù)測的故障事件數(shù)量總故障事件數(shù)量] （4）

在評估預(yù)測效果時(shí)，本文限制預(yù)測的有效時(shí)間為T1后的30min內(nèi)，若被預(yù)測事件發(fā)生的時(shí)間T2滿足[T1

本文以2018年1-2月的日志作為訓(xùn)練集，利用FP-Growth算法挖掘這兩個(gè)月的日志，并產(chǎn)生故障事件預(yù)測規(guī)則集R。以3-6月的日志數(shù)據(jù)作為測試集進(jìn)行效果評估。算法評估結(jié)果如圖3所示，測試集中4個(gè)月的故障預(yù)測平均準(zhǔn)確率為89.5%，平均召回率為79.8%。在這4個(gè)月日志數(shù)據(jù)上進(jìn)行的預(yù)測結(jié)果相差不大，預(yù)測準(zhǔn)確率和召回率都較高，但是召回率低于準(zhǔn)確率。召回率較低的原因可能是，基于關(guān)聯(lián)規(guī)則挖掘提取的故障預(yù)測規(guī)則，只能預(yù)測與其它日志密切關(guān)聯(lián)的故障，同時(shí)該故障在訓(xùn)練集中出現(xiàn)過，不能預(yù)測與其它日志關(guān)聯(lián)性很低或者訓(xùn)練集中未出現(xiàn)的故障。3-6月的日志中可能出現(xiàn)關(guān)聯(lián)性很低的故障，或者電力系統(tǒng)在這段時(shí)間進(jìn)行升級或改進(jìn)，產(chǎn)生了訓(xùn)練集中沒有的故障，故而預(yù)測結(jié)果的召回率略低。

如圖4所示，算法整體運(yùn)行復(fù)雜度較低，與傳統(tǒng)的正則表達(dá)式匹配故障模式相比較，執(zhí)行效率較高。綜上，該算法在電力系統(tǒng)的故障預(yù)測中取得了一定效果。

5 結(jié)語

本文在不需要電力系統(tǒng)領(lǐng)域先驗(yàn)知識的前提下，提出一種基于FP-Growth算法的電力系統(tǒng)故障預(yù)測模型，挖掘系統(tǒng)歷史日志中的關(guān)聯(lián)規(guī)則并進(jìn)行故障預(yù)測。首先，分析電力系統(tǒng)日志特征，根據(jù)故障預(yù)測需要，對原始日志進(jìn)行替換和冗余過濾預(yù)處理;然后，介紹關(guān)聯(lián)規(guī)則挖掘和FP-Growth算法;再使用FP-Growth算法挖掘故障事件的預(yù)測規(guī)則，并生成待定規(guī)則集和驗(yàn)證規(guī)則集，實(shí)現(xiàn)故障預(yù)測;最后，在電力系統(tǒng)日志數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)評估，由預(yù)測模型的平均正確率及平均召回率可以看出該方法有效。

雖然該方法取得了一定效果，但目前仍存在一定缺陷，如預(yù)測的平均召回率較低、不能預(yù)測日志中未曾發(fā)生過的故障等。故障預(yù)測規(guī)則自學(xué)習(xí)可能是解決該問題的一種方法，也是未來基于歷史日志挖掘故障預(yù)測規(guī)則的研究方向。

參考文獻(xiàn)：

[1] 賈統(tǒng)，李影，吳中海. 基于日志數(shù)據(jù)的分布式軟件系統(tǒng)故障診斷綜述. 軟件學(xué)報(bào)，2020，31（7）：1997-2018.

[2] 李剛，陳怡瀟，黃沛爍.? 基于日志分析的信息通信網(wǎng)絡(luò)安全預(yù)警研究[J]. 電力信息與通信技術(shù)，2018，16（12）：1-8.

[3] 廖湘科，李?yuàn)檴?，董威，? 大規(guī)模軟件系統(tǒng)日志研究綜述[J]. 軟件學(xué)報(bào)，2016，27（8）：1934-1947.

[4] SALFNER F， LENK M， MALEK M. A survey of online failure prediction methods[J].? ACM Computing Surveys， 2010， 42（3）： 1-42.

[5] 馮士龍，臺憲青，馬治杰. 改進(jìn)的基于日志聚類的異常檢測方法[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2020，41（4）：1087-1092.

[6] 王振華. 基于日志分析的網(wǎng)絡(luò)設(shè)備故障預(yù)測研究[D]. 重慶：重慶大學(xué)，2015.

[7] 崔元. 面向大規(guī)模網(wǎng)絡(luò)日志的主動(dòng)故障檢測方法的研究[D]. 長春：東北師范大學(xué)，2017.

[8] 王衛(wèi)華，應(yīng)時(shí)，賈向陽，等. 一種基于日志聚類的多類型故障預(yù)測方法[J]. 計(jì)算機(jī)工程， 2018，44（7）：67-73.

[9] 年夫順. 關(guān)于故障預(yù)測與健康管理技術(shù)的幾點(diǎn)認(rèn)識[J]. 儀器儀表學(xué)報(bào)，2018，39（8）：1-14.

[10] 樊建昌，余粟. 基于決策樹的日志分析方法[J]. 軟件導(dǎo)刊，2020，19（1）：99-102.

[11] DU M， LI F，ZHENG G，et al. DeepLog： anomaly detection and diagnosis from system logs through deep learning[C]. ACM Sigsac Conference on Computer & Communications Security， 2017.

[12] LIN Q，ZHANG H，LOU JG，et al. Log clustering based problem identification for online service systems[C]. IEEE/ACM International Conference on Software Engineering Companion. IEEE，2016：102-111.

[13] TYAGI K， THAKUR S. Predictive classification of ECG parameters using association rule mining[J]. Advances in Computer and Computational Sciences ，2017：619-627.

[14] MENG W B， LIU Y， et al. LogAnomaly： unsupervised detection of sequential and quantitative anomalies in unstructured logs[C]. The Internationl Joint Conference on Artificial Intelligence，2019.

[15] 晏杰，亓文娟. 基于Aprior&FP-growth算法的研究[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用，2013，22（5）：122-125.

（責(zé)任編輯：孫 娟）