基于FP-Growth改進算法的云服務器故障數(shù)據(jù)分析*

何 望，林果園

(1.中國礦業(yè)大學計算機科學與技術學院，江蘇 徐州 221000;2.礦山數(shù)字化教育部工程研究中心，江蘇 徐州 221000)

1 引言

近年來，由于本地化服務器的種種限制，越來越多的企業(yè)更傾向于將數(shù)據(jù)存儲和業(yè)務部署等任務安放于云平臺上。由于云平臺服務種類多樣，集群數(shù)量過大并且結構復雜，發(fā)生故障則是在所難免。商業(yè)云平臺在實際使用時采取了容錯備份機制以及緊急恢復機制[1]，主要目的在于用戶使用云平臺服務器時，即使發(fā)生了故障也可以保證云服務器的正常運行。但是，容錯以及緊急恢復并不能保證云服務器完全可靠。因此，我們還需對云服務器運行時的數(shù)據(jù)指標進行關聯(lián)性分析挖掘，協(xié)助云平臺精準預測可能發(fā)生的云服務器故障。

FP-Growth算法是由頻繁模式樹FP-Tree生成頻繁項集，將所掃描得到的數(shù)據(jù)庫分成眾多條件數(shù)據(jù)集，再從中挖掘關聯(lián)規(guī)則[2]。針對該算法挖掘過程中的時空消耗問題，研究人員提出了許多算法，如 Agrawal 等人[3]提出的樹-投影算法，Bhandari等人[4]提出的基于頻繁模式樹的改進Apriori算法,Rathee等人[5]提出的基于分布式Spark平臺的FP-Growth算法改進研究。此類相關改進算法較多的優(yōu)化改進策略在于如何在生成條件FP-tree的過程中降低時空消耗，在一定程度上有效地提高了算法的實際效率。但是，面臨較大規(guī)模數(shù)據(jù)集時，條件FP-tree的生成過程本身就是最大的時空消耗，因此本文引入數(shù)組標記策略，對條件FP-tree在生成FP-tree之前進行剪枝降維，在實際挖掘過程中無需生成條件FP-tree，減少了時空消耗，提升了實際使用效率，使其適用于云服務器故障數(shù)據(jù)分析。

2 云服務器故障數(shù)據(jù)分析

對云服務器供應商而言，保障云服務器的正常運行是極為關鍵的[6 - 9]。而如何在用戶使用云服務器的過程中盡可能早地檢測出潛在的云服務器故障錯誤，是云平臺企業(yè)面臨的難題。在用戶租用云服務器的過程中，云服務器供應商采集了大量的云服務器運行數(shù)據(jù)以及實時監(jiān)控數(shù)據(jù)。本文的主要思想在于如何利用改進的FP-Growth關聯(lián)規(guī)則對云服務器運行數(shù)據(jù)進行數(shù)據(jù)挖掘，找出云服務器運行數(shù)據(jù)與云服務器故障類型引發(fā)原因之間的關聯(lián)規(guī)則，根據(jù)關聯(lián)規(guī)則對云服務器運行調整作出合理推薦。

2.1 云服務器相關數(shù)據(jù)的獲取與整合

云服務器運行數(shù)據(jù)是用戶在租用云服務器時產(chǎn)生的相關數(shù)據(jù)，包括硬件資源狀態(tài)，如CPU、內(nèi)存以及網(wǎng)絡帶寬等使用量，其中資源狀態(tài)以時間節(jié)點作為區(qū)分與云服務器實際運行狀態(tài)相關聯(lián)。如某一時刻下某一云服務器的運行狀態(tài)對應該服務器資源的使用情況。其中云服務器的運行狀態(tài)為歷史數(shù)據(jù)中對云服務器過去某個時段的實際使用情況記錄，在本文研究中，算法模型即以云服務器各個時間節(jié)點的運行狀態(tài)為數(shù)據(jù)，挖掘數(shù)據(jù)與云服務器故障類型之間的關聯(lián)規(guī)則。具體數(shù)據(jù)從操作系統(tǒng)層面、云服務器連接層面和請求響應層面3個維度進行采集。操作系統(tǒng)層面數(shù)據(jù)包括CPU利用率、內(nèi)存利用率、云服務器端口占用情況、云服務器監(jiān)聽狀態(tài)和I/O速率；云服務器連接層面數(shù)據(jù)包括云服務器連接的使用情況以及假死狀態(tài)連接的比例；請求響應層面數(shù)據(jù)包括請求數(shù)/響應數(shù)、請求響應成功率和最近的請求在隊列中等待時間。具體挖掘指標參數(shù)和指標符號如表1所示。

Table 1 Mining index parameters

2.2 云服務器數(shù)據(jù)分析方法

云服務器使用過程中產(chǎn)生的各種數(shù)據(jù)存儲在云服務商對應的各類數(shù)據(jù)存儲系統(tǒng)中，這些多源異構數(shù)據(jù)需要集中獲取并整合為結構化數(shù)據(jù)，從而用于數(shù)據(jù)挖掘。同時我們根據(jù)云服務器的運行時特征，將云服務器運行狀態(tài)分別預分類為響應異常RE(Response Exception)、系統(tǒng)異常SE(System Exception)和正常運行ON(Operation Normal)。其中，ON狀態(tài)為云服務器正常運行，RE與SE為運行異常，運行異常類別為表1中指標參數(shù)的挖掘目標；SE按級別層面分為3類目標，即操作系統(tǒng)層面SEO、Web連接層面和請求響應層面SEA。具體相關檢測指標如下所示：

(1)RE:響應異常是系統(tǒng)處于非健康狀態(tài)情況中的一種，有異常行為的特征，不能正常響應用戶的請求，根據(jù)云服務器運行時的特征及請求響應過程，將云服務器端口占用情況以及云服務器監(jiān)聽狀態(tài)抽象為RE異常中的聚類指標，即定義RE={〈P,L〉}。

(2)SE:系統(tǒng)異常是危險信號，說明系統(tǒng)存在異常的可能性較高。將云服務器的這種運行狀態(tài)記為SE狀態(tài)。其中對應的聚類指標有：CPU利用率、內(nèi)存利用率、I/O 速率、Web連接的使用情況、假死狀態(tài)連接的比例、請求響應比、請求響應成功率及最近請求等待時間，即SE={〈C,M,I,N,B,RR,RS,RW〉}。但是，在云服務器正常使用過程中需要考慮各指標之間的相互影響問題，如當CPU和內(nèi)存的占用率都同時過高超出閾值范圍時，那么此時的最近請求等待時間同樣較大可能也會超過閾值。對SE錯誤再按級別層面劃分為3類，其中操作系統(tǒng)層面SEO={〈C,M,I〉}，Web連接層面SEW={〈N,B〉}，請求響應層面SEA={〈RP,RS,RW〉}，此時重新定義SE下3種錯誤指標聚類方法如式(1)所示。

(1)

(2)

(1)以毫秒為單位采集n個時刻的運行狀態(tài)數(shù)據(jù)，每個時刻包含有對應的m個屬性參數(shù)，attri=(P1,P2,…,Pm),0

(2)用n個時刻的屬性均值作為每個屬性的正常水平，記為avg。

(3)用式(2)中的Tj衡量某時刻中第j個屬性的異常程度。

(3)ON:安全信號，表示當前云服務器正常安全運行的可能性較高，無異常信號發(fā)生，對應信號集為空，系統(tǒng)處于健康狀態(tài)。定義ON={ }，即ON為空集。

3 FP-Growth改進算法

3.1 FP-Growth以及關聯(lián)規(guī)則介紹

FP-Growth最早將頻繁模式樹(FP-Tree)這種樹狀結構引入頻繁項挖掘[10]，樹狀圖中的每個節(jié)點都對應頻繁項集中的一個項， 同時，頻繁事務集中的某一條事務對應樹中由根到其子孫節(jié)點的某條路徑，又因為其中部分路徑會出現(xiàn)重疊，那么FP-Tree可以生成共享節(jié)點，由同一節(jié)點延伸來減少數(shù)據(jù)保存所需空間。FP-Tree本身的數(shù)據(jù)結構包含3個部分：原始數(shù)據(jù)、項頭表(Htable)和節(jié)點鏈表。項頭表分為2個域：項目名稱(Item-Name)和項目支持數(shù)(Item-Pointer)[11]。項頭表的生成能極大地幫助建立節(jié)點鏈表，節(jié)點鏈表本身由4個部分組成：節(jié)點名稱(NodeName)、節(jié)點計數(shù)(NodeCount)、節(jié)點鏈(NodeLink)(用于指向樹中具有相同節(jié)點名稱的下一個節(jié)點)和根節(jié)點指針(RootNode)。給定原始云服務器故障數(shù)據(jù)集D以及所設定的最小支持度閾值mt，那么我們可以通過2次遍歷生成所需要的FP-Tree。主要步驟為：(1)第1次掃描原始云服務器故障數(shù)據(jù)集D,得到所有頻繁1-項集，同時刪除低于最小支持度閾值的項，根據(jù)支持度計數(shù)降序排列后存入項頭表，并記為Ld。(2)創(chuàng)建根節(jié)點“NULL”并第2次掃描原始云服務器故障數(shù)據(jù)集D,對應每項事務按支持度計數(shù)降序創(chuàng)建對應分支，若考慮為某個事務增加分支時，可以在其父節(jié)點上將其節(jié)點計數(shù)加1，再按左右子樹處理相同根節(jié)點的子樹創(chuàng)建問題。

3.2 基本概念

設基本指標參數(shù)項i為云服務器運行數(shù)據(jù)集的單條數(shù)據(jù)，DS={i1,i2,…,im}為m個不同參數(shù)項的集合。設事務X為DS的項目子集，即X?DS，則稱X為一條事務集。事務集X中項的個數(shù)稱為事務集X的維數(shù)或長度，若其長度為k，則稱為k-項事務集。

定義1對于給定的最小支持度min_sup，若所求項集支持度大于或等于最小支持度min_sup，則稱該項集滿足最小支持度min_sup；同時，如果所求項集滿足最小支持度，那么稱其為頻繁項集。記所得頻繁k-項集為Lk。

定義2對于給定的云服務器故障數(shù)據(jù)集D={T1,T2,…，Tn}，Ti即為數(shù)據(jù)集中的某一條數(shù)據(jù)，1-項集L1={i1，i2，…，im},如果{i1，i2}是頻繁2-項集，那么稱i2是i1的頻繁延伸項，所有i1的頻繁延伸項組成的集合稱為i1的頻繁延伸項集。

定義3在給定的FP-Tree中，取根節(jié)點的子樹中最靠前且可能存在頻繁延伸項集的子樹，記作第1棵子樹。

定義4設有in<…

定義5給定已生成的索引FP-Tree，假設存在對應的約束子樹，取約束子路徑所對應的樹節(jié)點，那么統(tǒng)計該節(jié)點在樹中的出現(xiàn)頻度之和即為約束子路徑的支出度計數(shù)，記支持度計數(shù)為sup。

性質1由頻繁項集所得的子集必是頻繁的，反之，若項集的子集為頻繁的，那么它所對應的所有超集未必頻繁，若子集為非頻繁，那么其所對應的所有超集都必定不頻繁。

證明取任一頻繁k-項集Lk:

(1)由Lk剪枝所得的直接子集Lk-1仍為頻繁項集。且重復剪枝，得其所有子集都為頻繁項集。

(2)由于剪枝所得子樹對應的項集Li為頻繁項集，無法推斷其延伸樹仍為頻繁項集。設存在頻繁項集項頭表為{1，2，…，n}，如果存在頻繁m-項集L={1，2，…，m}，那么以m為結尾生成的不包括L的所有項集必為非最大頻繁項集，即其超集未必頻繁。而若Li不頻繁，那由其所得的延伸樹必有這一段不頻繁，故其本身不頻繁，證畢。

□

性質2最大頻繁項集必定為邊界頻繁項集。

1.2.1 對照組實施傳統(tǒng)健康教育 對照組采用傳統(tǒng)健康教育，具體如下：①入院宣教：向家屬介紹患兒病情及注意事項。②飲食指導：根據(jù)患兒的年齡、飲食習慣制定個性化飲食方案，避免偏食。③運動指導：合理安排運動時間，掌握好適宜的運動量。④出院指導：真確監(jiān)測血糖，并記錄血糖值及胰島素用量，為調整治療方案提供依據(jù)。

證明給定一個項集為頻繁項集，若其所有超集都為非頻繁項集，那么由性質1可得，該項集必為邊界頻繁項集。

□

性質3假設k-項集Lk中存在非頻繁t-項集Nt，則由Lk生成的頻繁項集必在以Nt分割后的n個(k-1)-項集子集中。

證明給定k-項集{a1,a2,…,ak}，若{a1,a2}為頻繁集，那么頻繁集可能會在{a1,a2,…,ak}或{a2,a3,…,ak}中，若不存在，則與性質1矛盾。

□

3.3 改進的FP-Growth算法

相對于經(jīng)典的FP-Growth算法而言，在直接挖掘時是通過循環(huán)遍歷，將產(chǎn)生的各個新候選項集加入條件中，在此不僅僅是對于維數(shù)較高的項集，同時對于維數(shù)較低但其遍歷過程中的最大頻繁項集過多的項集，經(jīng)典算法都會產(chǎn)生大量的候選項集。如若在較低維數(shù)數(shù)據(jù)集長度|DP|=10,Dmax(MFS)=2，那么由此產(chǎn)生的候選項集量接近10!，這樣對于計算的時間和空間消耗都是極大的。

本文算法在生成FP-Tree的同時，以云服務器故障運行數(shù)據(jù)為事務集，先挖掘第1棵子樹，然后將第1棵子樹的所有子樹與其他分支合并，同時刪除第1棵子樹，繼續(xù)對新的逆向FP-tree遞歸調用挖掘過程，直至樹只有1棵子樹，且已經(jīng)挖掘完該子樹。同時，在逆向挖掘匹配中，可以很直觀地看到，在刪除剩余子樹的同時，仍舊需要遞歸生成過多的條件樹，而這一部分也是算法所占用時空最多的部分，那么可以將FP-tree的生成過程改為單向并且只保留指向對應父節(jié)點的指針，舍棄了生成樹空間的同時引入約束子樹的模式，可以節(jié)省1/3的空間占用，而同時減少了生成樹的冗余結構，這樣可以大大提升挖掘效率。FP-tree的基本數(shù)據(jù)結構包括原始數(shù)據(jù)，節(jié)點鏈表和FP-tree 3個部分。設in<…

3.4 算法流程

算法1逆向子樹挖掘最大頻繁項集算法

輸入：原始云服務器故障數(shù)據(jù)集D的頻繁模式樹HFP,項頭表Header(記項頭表為HLd={1,2,…,t},t=|HLd|)，最小支持度閾值mt。

輸出:原始云服務器故障數(shù)據(jù)集D中的最大頻繁項集MLS,邊界頻繁延伸項集BLS。

1.MLS=?,BLS=?,BULS={1,2,…,endItem};/*BULS中可能為邊界頻繁項集，加入endItem保證其完備性*/

2.R為MLS的子集,設有非空集CLS;

3.root=find(fptree);/*找到第1棵子樹的根節(jié)點Root,挖掘子樹中所有的分支*/

4.for(allRinMLS) do{

5.CLS=CLS∪{R};/*根據(jù)性質1，遍歷合并頻繁子樹*/

6.MLSi={k|k∈MLS&k的最后一項為i};

7.MLS=MLS-MLSi;/*連接剪枝尋找非頻繁項集步驟*/

8. DELETER/*刪除合并后的剩余子樹,計算項集在原始數(shù)據(jù)中的支持度計數(shù)*/

9. for alln∈MLSdo{

10. ifn.supinD

11.MLS=MLS∪{n}

12. }

13. else{

14. ifn.sup==1 then{

15.BLS=BLS∪{n}

16. for(h=nmax;h≤t;h++)do{

17. ifh+n?MLS的子集 then{

18.MLS=MLSU{h+n};

19. }

20. }

21. }

22. }

23. }

24.}

4 FP-Growth改進算法在云服務器故障數(shù)據(jù)中的分析應用

4.1 改進FP-Growth算法實驗

為了評估改進后的FP-Growth算法的性能，與同為高效模式挖掘的改進的BICA算法[12]進行對比。改進BICA算法是一種快速可擴展的ADTree構建算法。利用以上算法在云服務器運行分析數(shù)據(jù)集上進行實驗，根據(jù)實驗結果對改進的FP-Growth算法進行時間評估，同時對改進前后的FP-Growth規(guī)則數(shù)進行對比實驗。實驗環(huán)境CPU為Intel Xeon E5，內(nèi)存為64 GB，操作系統(tǒng)為 Windows Server 2012。

圖1為FP-Growth算法改進前后和改進BICA算法隨著最小支持度的變化，3個算法所用時間的對比結果圖。通過實驗結果可以看出，隨著最小支持度的不斷增大，改進FP-Growth算法的時間性能總體優(yōu)于改進的BICA算法，經(jīng)計算，改進FP-Growth算法運行時間相比改進的BICA算法平均少了12.5 s，相比于原FP-Growth算法運行時間平均節(jié)省24.4 s。使用改進BICA算法進行數(shù)據(jù)分析時，最終只能得到一個二分樹，利用該二分樹的每一個節(jié)點與分支進行分析，才能得出云服務器運行狀態(tài)相關的一些結論，有時改進的BICA得出的二叉樹并不能包含全部結果，會遺漏部分參數(shù)的影響。而FP-Growth算法挖掘給出的是一條條關聯(lián)規(guī)則，只要給出確定的支持度與置信度，就能得到符合要求的全部規(guī)則，沒有遺漏。通過關聯(lián)規(guī)則能夠更加直觀與清晰地看出參數(shù)間的關聯(lián)關系，對進一步的分析也更加方便。

Figure 1 Running time comparison of three algorithms圖1 3個算法運行時間對比圖

Figure 2 Rule numbers of two algorithms圖2 2個算法的規(guī)則數(shù)變化圖

圖2給出了FP-Growth算法改進前后生成的規(guī)則數(shù)。通過實驗結果可以看出，隨著最小支持度的不斷增大，規(guī)則數(shù)不斷減少， 經(jīng)實驗計算可知，改進后的FP-Growth算法對無效規(guī)則的消除率最高可達37%。在實際應用分析時，用戶往往需要耗費不小的精力去剔除這些無效規(guī)則，而利用本文算法，不僅可以避免用戶在無效規(guī)則上的時間浪費，同時還極大地降低了用戶對結果分析的難度。

4.2 挖掘結果分析

通過FP-Growth算法得出的關聯(lián)規(guī)則能夠幫助我們進行云服務器運行故障檢測數(shù)據(jù)分析。以表1中數(shù)據(jù)為參數(shù)指標采集對應云服務器運行狀態(tài)數(shù)據(jù)，該數(shù)據(jù)集可用樣本數(shù)為308 880，其中，狀態(tài)標記為ON的數(shù)據(jù)量為306 471，出現(xiàn)RE或SE狀態(tài)的數(shù)據(jù)量為2 409，異常率約為0.78%。根據(jù)4.1節(jié)中性能評估結果可以看出，若支持度選擇較小會導致算法運行時間過長，而支持度選擇較大則雖然算法運行時間縮短，但是結果對應的有效關聯(lián)規(guī)則數(shù)則會過少。為此在對支持度閾值進行選擇時既要保證得到一定數(shù)量的關聯(lián)規(guī)則，又要生成的關聯(lián)規(guī)則便于進行針對性分析，因此實驗設置支持度為0.25，置信度為0.35。根據(jù)改進FP-Growth算法的挖掘結果，對數(shù)據(jù)進行回查，查詢挖掘出的關聯(lián)規(guī)則中的頻繁項對云服務器運行故障的影響。得到的關聯(lián)規(guī)則結果如圖3所示。

Figure 3 Association rule results(partial)圖3 關聯(lián)規(guī)則結果圖(部分)

圖3中結果采用[items(前項)，items(后項)，置信度]的輸出形式對關聯(lián)規(guī)則進行效用性分析。對結果進行粗略分析可以看出，所發(fā)生的錯誤情況較多是由RP故障引起的，而引起的故障類型較多是SEA故障。對各個關聯(lián)規(guī)則如“RP+RS+RW→SEA”的置信度為0.62進行分析，可得出若針對SEA問題解決請求訪問堵塞的情況，則可更好地保障云服務器高效安全地運行。

通過對結果的綜合分析， 此時段云服務器運行數(shù)據(jù)故障較多是由于RW、RS和RP的請求響應層面問題引起的，請求堵塞的同時增加了服務器運行壓力，引起CPU以及內(nèi)容使用率的增大，導致服務器無法正常使用，此時則應更好地采取如增加帶寬的措施來解決云服務器請求響應層面的問題。

限于篇幅，若對實驗結果進一步討論可繼續(xù)追蹤故障源，縮小數(shù)據(jù)集目標，引入服務器故障發(fā)生時間作為參數(shù)比較，同時對周期性服務器故障進行不同時間的數(shù)據(jù)對比。根據(jù)時間點查看服務器對應運行日志，還可更明確地找出引起云服務器故障問題的軟件所在或是哪些訪問目標及訪問來源引發(fā)的訪問激增從而導致訪問請求阻塞，再解決目標程序的具體問題。

5 結束語

本文針對經(jīng)典FP-Growth算法在構建以及挖掘過程所涉及的問題提出了改進優(yōu)化策略，優(yōu)化了FP-Growth在生成FP-Tree時的樹狀結構，引入數(shù)組約束標記，提升了算法的實際挖掘效率。改進后的FP-Growth算法有效提升了對云服務器運行時各項異常數(shù)據(jù)的關聯(lián)分析效率，并且適用于大數(shù)據(jù)量的數(shù)據(jù)挖掘。該算法通過關聯(lián)分析產(chǎn)生的頻繁項集，能夠較為準確地預測出云服務器運行狀態(tài)的變化可能性情況，幫助云服務供應商提高服務質量，減少用戶在使用時可能發(fā)生的云服務器故障。