共计 4051 个字符，预计需要花费 11 分钟才能阅读完成。
在智能运维畛域，告警关联中的频繁项集开掘（也被称之为关联规定开掘）算法，在告警关联剖析、根因定位以及告警降噪中常常应用。本篇内容咱们将为大家介绍一种典型的频繁项集开掘算法：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] 也就都是频繁项集。至此咱们演示了如何开掘频繁项集。
- 生成关联规定并计算置信度
对于关联规定置信度的计算方法，频繁项集开掘类算法基本一致，可参考 Apriori 算法中的第 6 步骤，这里不再赘述。
五、总结
在本篇文章中，咱们介绍了频繁项集开掘算法，解说了根底算法 Apriori 和目前较为先进的算法 FP-Growth，并详细描述了相干概念及实现步骤，下期咱们将会就如何将这一算法利用到告警关联场景中，进而实现告警降噪的性能进行进一步的阐明，敬请期待。
开源福利
云智慧已开源数据可视化编排平台 FlyFish。通过配置数据模型为用户提供上百种可视化图形组件，零编码即可实现合乎本人业务需要的炫酷可视化大屏。同时，飞鱼也提供了灵便的拓展能力，反对组件开发、自定义函数与全局事件等配置，面向简单需要场景可能保障高效开发与交付。
点击下方地址链接，欢送大家给 FlyFish 点赞送 Star。参加组件开发，更有万元现金等你来拿。
GitHub 地址：https://github.com/CloudWise-…
Gitee 地址：https://gitee.com/CloudWise/f…
万元现金流动： http://bbs.aiops.cloudwise.co…
微信扫描辨认下方二维码，备注【飞鱼】退出 AIOps 社区飞鱼开发者交换群，与 FlyFish 我的项目 PMC 面对面交换～