基于Apriori算法的時序關(guān)聯(lián)關(guān)系數(shù)據(jù)挖掘裝置的實現(xiàn)?

國悅婷 劉 磊 張 星

（華中科技大學(xué)自動化學(xué)院 武漢 430074）

1 引言

隨著互聯(lián)網(wǎng)公司業(yè)務(wù)規(guī)模的快速增長，運維正面臨著更為頻繁的故障告警［1］。在大規(guī)模網(wǎng)絡(luò)的運維工作中，每周海量的接警信息對運維工作人員而言工作量過大且難以及時查看，也會給短信網(wǎng)關(guān)帶來較大壓力，進一步影響故障的根因定位［2］，致使核心告警延遲甚至遺漏，造成重大損失［3］。因此，需要對海量告警信息進行告警收斂，以獲取真正有價值的告警信息［4］。

目前，國內(nèi)工業(yè)界針對以上問題，多采用的是告警合并策略［5］。首先，對告警進行分類，通常分為對業(yè)務(wù)有直接影響的告警［6］（如在線下降、服務(wù)器ping不通、業(yè)務(wù)進程崩潰、業(yè)務(wù)進程日志中出現(xiàn)致命字符串等）和預(yù)警（如在線波動、CPU和內(nèi)存異常等）［7］，其次，完成告警的去重、合并和聚合，最后，通過規(guī)則庫過濾進行告警收斂［8］，對于誤報、連鎖告警、大量告警等現(xiàn)象，會進行根因定位分析等，并做可視化數(shù)據(jù)呈現(xiàn)［9］。然而，采用簡單的時間窗口合并、服務(wù)組織合并等方式的告警合并策略無法實現(xiàn)大量告警精準(zhǔn)歸類的目標(biāo)，且合并效率較低［10］。

從歷史告警數(shù)據(jù)中看，一個故障往往會引發(fā)很多相關(guān)策略的告警，這些告警在時序上存在一定的關(guān)聯(lián)，所以我們可以從歷史數(shù)據(jù)中挖掘不同策略間的時序關(guān)聯(lián)關(guān)系，從而確定哪些規(guī)則是可以合并的，在告警的時候?qū)㈥P(guān)聯(lián)策略合并展示，可以有效的減少告警條數(shù)、更清晰的接收故障信息［11］。本文從實際運維場景的需求出發(fā)，對Apriori算法作出相應(yīng)改進，并在運維告警的時序信息場景中進行了實際應(yīng)用，結(jié)果表明在告警合并的結(jié)果和效率上均獲得了顯著的改善效果。

2 問題定義

傳統(tǒng)的關(guān)聯(lián)關(guān)系挖掘方法使用支持度挖掘頻繁項集，然后從頻繁項集中產(chǎn)生規(guī)則，根據(jù)各規(guī)則置信度，給出關(guān)聯(lián)規(guī)則。

定義1 告警序列

告警序列S是由告警類型集合E上的多個有序的告警組成，表示為S=（s，Ts，Te），s為序列，Ts為序列起始時間，Te為序列終止時間。例如在圖1中，Ts=0，Te=600，告警序列s由多個有序的告警向量（A，t）組成（其中A為告警監(jiān)控項，t為告警發(fā)生的時間，A∈E）。告警序列實例如圖1所示。

圖1 告警序列實例

定義2 時間窗口

告警序列S=（s，Ts，Te）上的一個告警子項，可以表示成W=（w，ts，te），ts＜t＜ te，其中 w=te-ts稱為時間窗口。

定義3 告警串行關(guān)系

?Ai(Ai∈E) ，?Aj(Aj∈E) ，如 果 Ai≠Aj，f∶Ai→ Aj或者f∶Aj→ Ai，則 Ai，Aj之 間 是 串 行 關(guān)系。告警情景a由告警事件A和B組成，且告警A會導(dǎo)致告警B出現(xiàn)，則A與B為串行關(guān)系。

3 Apriori算法及改進

Apriori算法是最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的經(jīng)典算法。

Apriori算法中，使用的是一種稱為逐層搜索的迭代方法，通過遍歷數(shù)據(jù)庫累計每個項的計數(shù)，并收集滿足最小支持度的項，找出頻繁項集的集合L1［12］。然后不斷迭代直至不能找到頻繁項集。其中，候選集產(chǎn)生的過程分為連接和剪枝兩個部分。采用這種方式，使得所有的頻繁項集既不會遺漏又不會重復(fù)。為提高頻繁項集逐層產(chǎn)生的效率，Apriori算法利用了一種稱為先驗性質(zhì)的重要性質(zhì)用于壓縮搜索空間［13］。Apriori算法流程如圖2所示。

圖2 Apriori算法流程圖

先驗性質(zhì) 頻繁項集的所有非空子集也一定是頻繁的。

在運維場景中，告警在時序上存在一定的關(guān)聯(lián)，如Rule1→Rule2，呈現(xiàn)一對一串行的特點。因此可對Apriori算法進行簡化，去掉迭代過程以提升運行效率，其過程是先建立帶時間窗口的支持度表，然后計算得出計數(shù)表，最后在得到置信度表的時候，對置信度的計算做調(diào)整，避免頻繁報警項作為分母時引起置信度值失真。因此將置信度的公式調(diào)整為式（3）。

由 Card（ A∪B ）=Card（A）+Card（B）-Card（A∩B），置信度公式在矩陣計算中可記為式（4）：

如果項集S的置信度滿足預(yù)定義的最小置信度閾值min_conf，如滿足式（5）：

又因為規(guī)則由頻繁項集產(chǎn)生，因此每個規(guī)則都自動地滿足最小支持度。同時滿足最小支持度閾值和最小置信度閾值的規(guī)則稱為強規(guī)則，則S是頻繁項集，規(guī)則A→B為強規(guī)則。

4 實驗內(nèi)容

為達到對告警信息合并收斂的效果，設(shè)計并實現(xiàn)了數(shù)據(jù)挖掘裝置，其整體框架分為三部分：抓取模塊、模型訓(xùn)練模塊和測試評估模塊。該框架支持歷史數(shù)據(jù)的爬取存儲、挖掘訓(xùn)練和測試，并將三個模塊的代碼解耦，并具有高內(nèi)聚、低耦合的特點。

數(shù)據(jù)抓取部分從各個存儲系統(tǒng)中抓取告警數(shù)據(jù)，經(jīng)過數(shù)據(jù)清洗存入本地磁盤，模型訓(xùn)練部分使用相應(yīng)的策略訓(xùn)練數(shù)據(jù)模型，得到挖掘規(guī)則，模型測試部分根據(jù)本地磁盤的數(shù)據(jù)和挖掘規(guī)則，得到測試結(jié)果。系統(tǒng)結(jié)構(gòu)如圖3所示。

圖3 數(shù)據(jù)挖掘裝置框架圖

實驗過程共分為三個步驟：1）告警歷史數(shù)據(jù)抓?。?）挖掘算法訓(xùn)練；3）測試評估結(jié)果。

第一步，需對歷史數(shù)據(jù)進行抓取，該過程包括從各個存儲系統(tǒng)中抓取離線數(shù)據(jù)和將清洗后的數(shù)據(jù)存入本地磁盤兩個步驟。以圖1的告警序列為例，采用60s的時間窗口，將抓取的告警數(shù)據(jù)整理為表1。

表1 帶時間窗口的告警序列

對時序數(shù)據(jù)流的數(shù)據(jù)挖掘采用約定起始時間和固定時間間隔的滑動窗口，規(guī)定時間窗口為1個時間單位，以Rule1 → Rule4為例，W1?W2，W4?W5，W7?W8，W9?W10這四個相鄰的時間窗口均支持Rule1→Rule4的關(guān)聯(lián)關(guān)系，因此Rule1→Rule4的支持度計數(shù)為4。依此規(guī)則，計算所得如表2所示。

第二步，對時序關(guān)系進行模型訓(xùn)練。關(guān)聯(lián)關(guān)系的挖掘包含兩個過程：1）找出所有的頻繁項集；2）由頻繁項集產(chǎn)生強關(guān)聯(lián)（強規(guī)則）。

根據(jù)步驟一，遍歷表1統(tǒng)計每個規(guī)則出現(xiàn)的次數(shù)，得出所有規(guī)則的支持度計數(shù)，如表3所示。

表2 帶時間窗口的支持度計數(shù)表

表3 支持度計數(shù)

由式（4），得出置信度表如表4所示。

表4 置信度

對于S的每個非空子集s，如果

則輸出規(guī)則A?B。

由經(jīng)驗min_conf設(shè)置為0.3，則強規(guī)則為Rule1→ Rule5，Rule2→ Rule1，Rule3→ Rule4，Rule3 →Rule5，Rule4→ Rule3，Rule4→ Rule5，Rule5→Rule4。

第三步，根據(jù)訓(xùn)練得到的關(guān)聯(lián)關(guān)系進行數(shù)據(jù)測試。當(dāng)遇到有關(guān)聯(lián)關(guān)系的告警項時，將其收斂為同一條告警信息，并計算出收斂率。

5 結(jié)果及分析

本文采用python編程實現(xiàn)算法，操作系統(tǒng)為Linux，配置CPU頻率為2400.084MHz。實驗中采用某公司網(wǎng)管數(shù)據(jù)庫連續(xù)一個月的原始告警數(shù)據(jù)做為測試數(shù)據(jù)，大約200萬條告警記錄。

將訓(xùn)練數(shù)據(jù)的時間設(shè)定為2016年9月1日到2016年10月1日，并將測試數(shù)據(jù)時間設(shè)定為2016年11月1日到2016年12月1日，輸出如表5。

表5 告警收斂結(jié)果

結(jié)果顯示，通過算法的合并使得原始告警數(shù)量有了較大程度的削減。功能上完成了對有關(guān)聯(lián)關(guān)系的規(guī)則的合并，起到了告警收斂的作用，減少了冗余告警數(shù)量。對于最小自信度閾值的選取，既不能過小，不然會使數(shù)據(jù)關(guān)聯(lián)度增大，本來沒有關(guān)聯(lián)的數(shù)據(jù)進行合并后，對告警信息報警的準(zhǔn)確率有一定干擾，也不能選擇太大，不然會削弱告警合并的效果，無法達到理想的合并效果。

6 結(jié)語

本文通過對Apriori算法的改進和置信度公式的優(yōu)化，設(shè)計并實現(xiàn)了時序關(guān)聯(lián)關(guān)系數(shù)據(jù)挖掘裝置，并將其用于大規(guī)模網(wǎng)絡(luò)告警合并場景，從而減少了冗余告警數(shù)量，減輕了短信網(wǎng)關(guān)的壓力，為海量告警信息故障的根因定位起到了積極的作用，減少了核心告警延遲和遺漏的情況。根據(jù)告警場景的實際情況，改進后的Apriori算法能更好地挖掘出關(guān)聯(lián)關(guān)系規(guī)則，進而提高了該算法的實用性。本文的方法對已發(fā)生的告警起到了有效的合并作用，下一步的工作是對告警數(shù)量進行預(yù)測，對未來預(yù)期時間的告警數(shù)量進行預(yù)測，當(dāng)超過該預(yù)測值的時候，則認(rèn)為疑似出現(xiàn)大規(guī)模告警，然后利用本文的方法對告警信息進行合并展示。

［1］Dattatraya V K，Shaila D A.A Universal Object Oriented Expert System Frame Work for Fault Diagnosis［J］.Inter?national Journal of Intelligence Science，2012，2（3）：63-70.

［2］李彤巖.基于數(shù)據(jù)挖掘的通信網(wǎng)告警相關(guān)性分析研究［D］.成都：電子科技大學(xué)，2010.

LI Tongyan.Research on alarm correlation analysis of com?munication network based on Data Mining［D］.Chengdu：University of Electronic Science and technology，2010.

［3］鄧歆，孟洛明.基于貝葉斯學(xué)習(xí)的告警相關(guān)性分析［J］.計算機工程，2007，33（12）：40-42.

DENG Xin，MENG Luoming.Alarm correlation analysis based on Bayesian learning［J］.Computer Engineering，2007，33（12）：40-42.

［4］田志宏，張永錚，張偉哲，等.基于模式挖掘和聚類分析的自適應(yīng)告警關(guān)聯(lián)［J］.計算機研究與發(fā)展，2009，46（8）：1304-1315.

TIAN Zhihong，ZHANG Yongzheng，ZHANG Weizhe，et al.Adaptive alarm correlation based on pattern mining and clustering analysis［J］.Journal of Computer research and development，2009，46（8）：1304-1315.

［5］J.Han，M.Kamer.數(shù)據(jù)挖掘概念與技術(shù)［M］.2版.北京：機械工業(yè)出版社，2007.

J.Han，M.Kamer.Data mining concepts and techniques［M］.Second Edition，Beijing：China machine press，2007.

［6］Unil Y.Efficient Mining of Weighted Interesting Patterns with a Strong Weight and/or Support Affinity［J］.Informa?tion Sciences，2007，177（17）：3477-3499.

［7］蔡偉杰，張曉輝，朱建秋，等.關(guān)聯(lián)規(guī)則挖掘綜述［J］.計算機工程，2001，（05）：31-33，49.

CAI Weijie，ZHANG Xiaohui，ZHU Jianqiu，et al.Survey of Association Rule Generation［J］.Computer Engineer?ing，2001，（05）：31-33，49.

［8］吳揚揚，陳懷南.基于關(guān)聯(lián)規(guī)則的通信網(wǎng)絡(luò)告警相關(guān)性分析模型［J］.通訊和計算機，2004，12（1）：57-63.

WU Yangyang，CHEN Huainan.Alarm correlation analy?sis model of communication network based on association rules［J］.Journal of Communication and Computer，2004，12（1）：57-63.

［9］夏海濤，詹志強.新一代網(wǎng)絡(luò)管理技術(shù)［J］.北京郵電大學(xué)出版社，2003，05.

XIA Haitao，ZHAN Zhiqiang.New generation network management technology［J］.Beijing University of Posts and Telecommunications Press，2003，05.

［10］楊芬.基于約束的關(guān)聯(lián)規(guī)則挖掘［D］.武漢：華中科技大學(xué)，2004.

YANG Fen.Association Rules Mining Based on Con?straints［D］.Wuhan：Huazhong University of Science and Technology，2004.

［11］Pang-Ning Tan Michael Steinbach Vipin Kumar.Intro?duction to Data Mining［M］.March 25，2006.

［12］Zhen Yun Liao，Xiu Fen Fu，Ya Guang Wang.The Re?search of Improved Apriori Algorithm［J］.Applied Me?chanics and Materials，2013，2171（263）.

［13］Gao H S，Li Y M.An Efficient Communication Network SDH Alarm Association Rule Mining Algorithm［J］.Ad?vanced Materials Research，2014.

［14］N.Badal，Shruti Tripathi.Frequent Data Itemset Mining Using VS_Apriori Algorithms［J］.International Journal on Computer Science and Engineering，2010，2（4）.

［15］Li Rong Tong，Jun Zhang，Lei Ma，Li Xin，Shuang Hu，Ji?an Feng He.An Improved Apriori Algorithm Based on LinkedList for the Prevention of Clinic Pharmaceutical Conflict［J］.Applied Mechanics and Materials，2014，2987（513）.