当前位置：网站首页>深度解析智能運維下告警關聯頻繁項集挖掘算法原理

深度解析智能運維下告警關聯頻繁項集挖掘算法原理

2022-06-10 06:22:00 【雲智慧AIOps社區】

在智能運維領域，告警關聯中的頻繁項集挖掘（也被稱之為關聯規則挖掘）算法，在告警關聯分析、根因定比特以及告警降噪中經常使用。本篇內容我們將為大家介紹一種典型的頻繁項集挖掘算法：FP-Growth 算法。

一、告警關聯簡介

隨著大型公司系統架構複雜性、异構性的快速發展，故障定比特的效率和异常行為監測的准確度直接决定了公司內業務系統的穩定程度，並間接影響了公司的實際經濟效益。 因此，越來越多的公司開發出足够强大的監控中心，能够有效管理、監控和追踪系統中潜在的故障和已經發生的故障，並將其作為警報發送給運維人員。然而如何高效的處理大量警報，也由此成為了運維人員面臨的新挑戰。

理論上講，如果能够實時並百分百准確地實現對每個警報的根因定比特，那麼便能够有效解决這一問題。然而根據學術界目前的研究進展，在未來幾年內都很難實現這一目標，主要原因不僅在於研究本身的難度，也與警報的發送機制有關，很多情况下，根因警報反而在衍生警報之後發出，這使得實時根因分析不可能得到最正確的結果。因此，不論是學術界還是工程界最終都更傾向於從時間、文本、空間等維度挖掘警報之間的關聯關系，並根據這種關聯關系實現警報的分組，按照所含信息量及嚴重程度等信息劃分警報的優先級，以加速故障定比特的過程。

為此，我們提出了一種告警降噪的架構，並在其中詳細的定義了告警關聯這一問題，定義如下：根據關聯場景，將一定時間窗口內的多個警報按照時間、空間和語意相關性，關聯為描述當前場景中特定問題的集合，每個集合稱為一個事件。 基於這一定義，我們研發出了多種算法分析警報之間的關聯特性，其中 FP-Growth 算法便是一種典型的分析時間相關性的方法。

二、頻繁項集挖掘簡介

頻繁項集挖掘常用於購物記錄分析中，通過分析用戶經常一起購買的商品實現商品推薦功能。在這一場景中，頻繁項集挖掘是查找經常一起購買的商品組合的技術術語，而在告警關聯場景中，我們可以認為頻繁項集挖掘是指查找經常一起出現的警報組合，其中每一個警報以及上文中的每一件商品都可以被稱之為一個 “項”，比如警報 ID “A”、“B” 或者商品 “啤酒”、“雞蛋” 都可以被看作一個單獨的項。多個項組合在一起可以被成為一個項集，比如警報 ID 組成的項集 ["A"、"B"]，商品項集 ["啤酒"、"雞蛋"]。

這類問題的原始數據是多個項集組合成的數據庫，頻繁項集挖掘的目標是使用快速有效的算法識別其中頻繁一起出現的項與項的組合，最容易想到的解决方案是遍曆所有項，並列舉出所有可能存在的項集，這顯然需要消耗大量的時間，因此我們需要更好的解决方案。

三、Apriori 算法原理

FP-Growth 算法是該領域中最先進的算法之一，但為了更好的理解 FP-Growth 算法，我們將首先介紹該領域中最基本的算法，即 Apriori 算法，並借此引出頻繁項集挖掘這一領域的部分基本概念。

在 1994 年提出的文章《Fast Algorithms for Mining Association Rules》中，作者提出了 Apriori 算法用於解决這類問題，這一算法主要包含 7 個步驟：

計算項的支持度

頻繁項集挖掘算法基於支持度的概念，支持度可以被理解為在全部的項中，待計算項出現的概率， 具體的計算方法是統計待計算項出現在了幾個項集中，以及原始項集的總個數，求取比值作為當前待計算項的支持度。

假設啤酒、紙尿褲都被 4 個人購買，雞蛋只有 2 個人購買，則根據步驟 1，我們能够計算出三件商品的支持度。

確定支持度閾值

確定每個項的支持度後，需要一個標准用於過濾掉不常見的項，這個標准稱之為支持度閾值。 比如對於步驟 1 中的數據，假設我們並不希望關注購買人次不足 3 人次的商品，則可將支持度閾值設定為 0.3。

篩選頻繁項

確定支持度閾值後，支持度低於這一標准的項將作為不常見的項被過濾掉，也就不會參與到後續的分析步驟中。 在上文的案例中，雞蛋便是被過濾掉的不頻繁項。

計算頻繁項集的支持度

接下來的分析與上文相同，但分析的單元從單獨的項變成了項與項的組合也就是項集。比如上文提到的啤酒和雞蛋組合後可看作一個項集。可以想象，經過對頻繁項的篩選，需要生成的項集組合的數目比不經過頻繁項篩選時要少得多。針對這些新的項集組合，我們依然可以統計他們的出現頻次，計算所有組合出現頻次之和，並確定他們的支持度。

對新的項集重複上述步驟

經過步驟 1-4，我們已經實現了頻繁項的過濾與組合，以及支持度的統計，重複上述步驟，我們便可以獲得包含更多項的頻繁項集。

生成關聯規則並計算置信度

現在我們已經獲得了頻繁項集，在特定的場景下，僅僅是頻繁項集並不能够滿足使用者的需求，還需要將他們轉化為關聯規則，並針對這些關聯規則的可信程度進行評估。 關聯規則的格式為：項 X = > 項 Y，這意味著我們獲得了一條規則，規則的含義為在項 X 存在的情况下，有很大概率項 Y 也會存在。而置信度則是對這一規則的可信程度的考量，置信度 100% 意味著項 X 存在的情况下，項 Y 永遠存在，而 50% 則意味著項 X 存在時只有 50% 的概率同時出現項 Y。這一指標可通過計算項 X 和項 Y 的出現次數與項 X 單獨出現次數的比值獲得。

計算提昇度

在商品推薦等場景中，還存在有提昇度的概念，這一指標用於評價項與項之間關聯的强度，比如 "任何產品 =>X" 的置信度為 10%，"A=>X" 的置信度為 75%，則提昇度為 75%/10% = 7.5。如果最終結果小於 1，則可以認為這條關聯規則並不成立，規則內的項彼此獨立。

通過上述介紹，我們已經了解了告警關聯和頻繁項集挖掘的基本概念，並介紹了頻繁項集挖掘類算法的三個基本的評價指標，即支持度、置信度、提昇度。 而作為目前最先進的頻繁項集挖掘算法之一的 FP-Growth，相比與 Apriori 算法又有哪些改進呢？

四、FP-Growth 算法

與 Apriori 算法相似，FP-Growth 算法的基石同樣是從數據集中找出頻繁的項目集，並過濾掉不頻繁的部分，但為了更快的實現這一過程，FP-Growth 算法引入了樹結構代替項集，這種結構可以在更短的時間內掃描數據集並生成關聯規則。 算法的具體步驟如下：

計算項的支持度

FP-Growth 算法最初的步驟與 Apriori 算法相似，但為了更加直觀的展示這一過程，我們將從如下的示例數據入手：

統計原始數據中各項的支持度，為了更加直觀的展示實際效果，我們將項一共出現在了幾個項集中作為該項的支持度，比如對於項 “A”，在項集 1、2、4、5、7、8、9、10 中都出現過，共出現在了 8 個項集中，則 A 的支持度為 8，其餘各項的支持度如下。

確定支持度閾值

同樣的，FP-Growth 算法也需要確定支持度閾值，假定支持度閾值設定為 2。

篩選頻繁項

不滿足支持度閾值的項將被删去，則保留的項和支持度如下：

根據項的支持度對項集排序

為構建樹結構，需要將剩餘的項按照支持度進行排序，即按照 A、C、E、G、B、D、F 這一順序排序項集。（同支持度的項可按照項的出現順序進行排序，不同支持度的項按照支持度排序，比如 G 的支持度為 5，小於 E 的支持度，則排在 E 後）。

創建樹並逐個添加項集

獲得經過排序後的頻繁項集後，將建立項頭錶和 FP 樹，項頭錶可被認為是頻繁項以及節點鏈錶的組合，FP 樹可以被認為是將項集內的節點一一映射到樹中，樹上的每個節點為一個項，這些節點都可以通過項頭錶內的節點鏈錶訪問到，也可以通過樹的根節點訪問到。同樣的，為了直觀說明，我們給出了如下圖示，掃描項集編號為 1 的項集 [A、C、E、B、F] 後，可建立項頭標以及樹，項頭錶第一列為項的編號，第二列為該項的支持度，第三列為節點鏈錶的起始點。

重複上述步驟，直到掃描完成所有項集，可得如下結果，其中部分項無法僅用一個節點錶示，比如 G，在項集 2 和 5 中，項集分別為 [A、C、G] 和 [A、C、E、G、D]，因此需要采用鏈錶鏈接兩個節點：

掃描 FP 樹並獲得關聯規則

建立 FP 樹後，該如何挖掘關聯規則？這裏我們需要引入 FP-Growth 算法特有的條件模式基的概念，條件模式基是指某個項的前綴路徑的集合，通俗理解即是從根節點到該項所有節點走過的路徑組成的新的樹。舉例說明，假定我們希望挖掘與 D 有關的規則，則 D 的條件模式基為圖中的標紅部分。

獲得 D 的條件模式基後，我們可以看出共有兩個主要分支，即 A-C-E-G-D 和 A-C-D，由於末端節點 D 的出現次數都為 1，因此以上兩個分支的出現次數也為 1，這一點通過原始數據也可以看出。接著我們能够判斷其中的公共分支為 A-C-D，在兩個分支中各出現 1 次，一共出現了 2 次，由於我們的支持度閾值為 2，因此 [A、C、D] 為頻繁項集之一，其子集 [A，C], [A，D], [C，D] 也就都是頻繁項集。至此我們演示了如何挖掘頻繁項集。