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

何 望，林果園

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

1 引言

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

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

2 云服務器故障數據分析

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

2.1 云服務器相關數據的獲取與整合

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

Table 1 Mining index parameters

2.2 云服務器數據分析方法

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

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

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

(1)

(2)

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

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

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

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

3 FP-Growth改進算法

3.1 FP-Growth以及關聯規則介紹

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

3.2 基本概念

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

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

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

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

定義4設有in<…

定義5給定已生成的索引FP-Tree，假設存在對應的約束子樹，取約束子路徑所對應的樹節點，那么統計該節點在樹中的出現頻度之和即為約束子路徑的支出度計數，記支持度計數為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 對照組實施傳統健康教育 對照組采用傳統健康教育，具體如下：①入院宣教：向家屬介紹患兒病情及注意事項。②飲食指導：根據患兒的年齡、飲食習慣制定個性化飲食方案，避免偏食。③運動指導：合理安排運動時間，掌握好適宜的運動量。④出院指導：真確監測血糖，并記錄血糖值及胰島素用量，為調整治療方案提供依據。

證明給定一個項集為頻繁項集，若其所有超集都為非頻繁項集，那么由性質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算法

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

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

3.4 算法流程

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

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

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

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

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

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

4.for(allRinMLS) do{

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

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

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

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

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改進算法在云服務器故障數據中的分析應用

4.1 改進FP-Growth算法實驗

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

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

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

Figure 2 Rule numbers of two algorithms圖2 2個算法的規則數變化圖

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

4.2 挖掘結果分析

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

Figure 3 Association rule results(partial)圖3 關聯規則結果圖(部分)

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

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

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

5 結束語

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