基于多维数据频繁项挖掘的母机隐患排查

引言

本文首先通过“啤酒与尿布”的故事入手，介绍机器学习中常见问题——频繁项挖掘的应用背景；其次，简要介绍频繁项挖掘最常用的两种算法——Apriori算法和FP-growth算法；然后，对于高维度下频繁项数量爆炸的问题，提出几点建议；最后，笔者以多维母机指标为案例，简要介绍频繁项挖掘在腾讯云实际场景中的应用。

一、背景

啤酒与尿布的故事：在一家超市中，人们发现了一个特别有趣的现象：尿布与啤酒这两种风马牛不相及的商品居然摆在一起。但这一奇怪的举措居然使尿布和啤酒的销量大幅增加了。这可不是一个笑话，而是一直被商家所津津乐道的发生在美国沃尔玛连锁超市的真实案例。原来，美国的妇女通常在家照顾孩子，所以她们经常会嘱咐丈夫在下班回家的路上为孩子买尿布，而丈夫在买尿布的同时又会顺手购买自己爱喝的啤酒。这个发现为商家带来了大量的利润。

如何从浩如烟海却又杂乱无章的数据中，发现啤酒和尿布销售之间的联系呢？这又给了我们什么样的启示呢？这就是数据挖掘，对数据之间的关联规则进行分析获取我们想要的结果。

二、频繁项挖掘算法

频繁项集挖掘算法用于挖掘经常一起出现的item集合（称为频繁项集），通过挖掘出这些频繁项集，当在一个事务中出现频繁项集的其中一个item，则可以把该频繁项集的其他item作为推荐。

简单的说给定一个事务集list = {A,B,C,...}，一个数据集D的每条记录都是list 的子集，要找出数据集中频繁共同出现次数超过阈值t即支持度的所有组合。支持度指某频繁项集在整个数据集中出现的次数。如表1，假设数据集有 100 条记录，包含{'gloves '}的有 50 条记录，其支持度就是50。当然有些时候也会用百分比例来表示，本质是一样的）。

表1. 频繁项示例

Apriori算法

常见的频繁项集挖掘算法有两类，一类是Apriori算法，另一类是FP-growth算法。

Apriori算法是挖掘频繁项集的经典算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。Apriori通过不断的构造候选集、筛选候选集挖掘出频繁项集，需要多次重复扫描原始数据，当原始数据库较大时，反复读取的效率比较低下；而且Apriori能产生大量的候选集，这是Apriori算法的两大缺点。

算法大致流程：

1. 过单趟扫描数据库D；计算出各个1项集的支持度，得到频繁1项集的集合。

2. 从2项集开始循环，由频繁k-1项集生成频繁频繁k项集。

2.1 连接步：为了生成，预先生成,由2个只有一个项不同的属于的频集做一个（k-2）合并运算得到的。

2.2 剪枝步：由于是的超集，所以可能有些元素不是频繁的。舍弃掉子集不是频繁项集即不在频繁k-1项集中的项集

2.3 扫描数据库，计算2.3步中过滤后的k项集的支持度，舍弃掉支持度小于阈值的项集，生成频繁k项集。

3. 当当前生成的频繁k项集中只有一个项集时，循环结束。

图 1. Apriori算法示意图

FP-growth算法

FP-growth，即frequent pattern growth，通过FP-tree数据结构对原始数据进行压缩，效率较高。FPGrowth算法主要分为两个步骤：FP-tree构建、递归挖掘FP-tree。简单的说apriori是先产生一批候选项集，再通过原数据集去过滤非频繁项集：先找A、B、C，检查一下通过了，再找AB、AC、AB，检查又通过了，再到ABC... 这样的广度优先的方式。而fp-growth是先从数据集中找频繁的项，再从包含这个频繁项的子数据集中找其他的频繁项，把它们俩连起来也肯定是频繁的：先找A，再在找包含A的子数据库里，找到B，就得到AB是频繁，再再包含AB的子数据库里，找到C，ABC就是频繁了。

图2. FP-growth算法示意图

n优点：

1.因为 FP-growth 算法只需要对数据集遍历两次，所以速度比Apriori更快。

2.FP树将集合按照支持度降序排序，不同路径如果有相同前缀路径共用存储空间，使得数据得到了压缩。

3.不需要生成候选集。

n缺点：

1.FP-Tree第二次遍历会存储很多中间过程的值，会占用很多内存。

2.构建FP-Tree是比较昂贵的。

三、维度爆炸问题

不管采用Apriori还是FP-growth算法，最后挖掘的频繁项都有可能发生数量爆炸的问题。尤其是维度很高，即特征/属性数量较多时，频繁项数量呈指数型增长，程序也特别耗时和占用高内存。针对高维度下频繁项数量爆炸的问题，笔者提出以下几点建议：

1.单维度分析

初步分析时，可将最小频繁项阈值设置较高，查看高频特征。

如果某一维度下的某特征占据主导地位，比如100个购物事件中，某一维度下有99个的购物事件都是同一个类型，那么将该特征引入任何一个频繁项中都不会改变该频繁项的性质，即该频繁项依旧是频繁项。这样一来，这一维度对于所有的频繁项可有可无，则频繁项的数量可以是原来的两倍。同理，分析其他单维度的情况，对于某一维度下如果绝大多数都是某一类型，那么难以分析是否是其引发的故障，则该维度没有引入频繁项挖掘的必要。

注：具体在总事务集中出现多少次算是“占据主导地位”，这依赖于最小支持度阈值的设定。如果挖掘500个事件，最小支持度设置为5，那么某一维度下有等于甚至超过495个事件都是某一特征属性，那么这一维度显然可以视为“占据主导地位”。

2.相关性分析

对所有维度的指标做数值型转化，转换成数值型1234，并求出两两指标对之间的相关性。相关系数的绝对值越大，表面相关性越强：相关系数越接近于1或-1，相关度越强，相关系数越接近于0，相关度越弱。一般认为， pearson相关性系数大于0.8可视为高度相关。对于高度相关的指标对，选择其一引入频繁项挖掘即可。注： 0.8的阈值可以根据不同业务需求而不同。

当然，除了pearson相关性系数，其他衡量属性间相关性/相似度的指标还有如spearman系数，Eucledian 距离，Manhattan 距离，Minkowski 距离，Jaccard相似度等。

3.不同算法

频繁项挖掘的经典算法是Apriori，当前应用最广的是FP-growth。FP-growth算法表现的比Apriori更加高效快速。除此之外，同为递归搜索的Relim（Recursive Elimination algorithm by Christian Borgelt）算法也是一个不错的选择。当对最小支持度高或者频繁规则比较少的数据集进行挖掘时，Relim算法的运行速度往往比FP-growth算法要快。

Relim算法是在FP-growth算法的基础上提出的一种新的不需要候选项集的频繁项集挖掘算法。它具有算法结构简单，空间利用率高，易于实现等显著优点。但是和FP-growth不同的是：Relim算法在运行时不必创建频繁模式树，而是通过建立一个事务链表组(transaction lists)来找出所有频繁项集。

经笔者实践证明，该算法确实比FP-growth算法更加快速。

4.字符串匹配

匹配长字符串比匹配短字符串要耗时更长。因此可以考虑在挖掘频繁项之前把原始指标用类似于A1,A2,A3,B1,B2,C1的形式映射替换，然后在结果输出的时候反转显示具体指标及类别名称。

缺点是在中间过程调试时，不易分析结果，且提升效率不太明显，故除非字符串特别长，一般较少采用。

5.数据分解

一种是模式聚类，要先定义一种好的相似性度量，根据该度量对模式聚类，然后每个簇仅选择和输出一个代表模式。这比较依赖于专家经验和目标需求。

一种是数据库分解，分批次挖掘频繁项。将备选的维度指标根据重要性和优先级分类，优先考虑重要或优先的维度，不断地引入新的维度，或同时删除不再需要的维度。

6.数据缓存

程序性能分析和优化的目标：性能优化接近尾声的时候，剩下的大多数性能瓶颈都是有I/O关联的代码造成的。

优化一段代码（函数）最常用的手段，是函数返回值缓存。对于某些可能重复使用且体量较大的数据，可以先建立缓存库保存中间处理结果。后面使用数据时优先使用缓存，可以减少中间处理操作带来的时间消耗和资源占用。

一般来说，数据缓存库越大，速度越快，尤其是在高维度下、频繁项特别多时速度提升更明显。然而，缓存库越大，内存占用更多，具体如何权衡两者，是一个trade-off问题，可视情况而定。

7.明确需求

在选择特征维度时，注意回顾反思一个问题：倘若一条频繁项中出现了50个维度，那么专家又如何去分析所有的指标组合？人的肉眼和思维一次性可分辨、分析的维度是有限的。追求多维频繁项并不一定对业务具有实际可行的意义。

从需求的角度来说，一次性挖掘高维度的指标，可调高最小频繁项阈值；但是如果是为了结合专家经验去分析指标间的关系，分析每个指标对故障率可能的增长，维度不适宜设置过高。

归根结底，频繁项挖掘是为业务服务的。明确目标，明确需求，往往比探究如何快速挖掘频繁项更重要。

四、案例分析

腾讯云业务：基础IASS的可靠性是云服务质量的重要衡量标准。母机作为基础IASS中最为关键的部分，一旦宕机将直接影响到客户的子机，进而对客户的业务产生重大经济损失。因此分析母机故障的原因，降低母机故障率具有重要意义。如何通过频繁项挖掘出故障机器的共性指标，由此来排查隐患机器？如何在母机指标正常的平静表面下找到隐藏的汹涌暗流？即时定位问题，发现问题，这就是挖掘频繁项的意义所在。

1.目标

对于已经积累的母机故障工单，实现

1)通过过对多维度指标的自动聚合分析，发现批次共性隐患，

2)通过发觉故障母机具有哪些共性配置，比较精准地定位到导致故障率高的根因；

3)通过发现频繁故障的母机具有的潜在规律，进而从硬件、软件、环境相关配置上给运营人员在采购、运营和召回等方面提供决策支持。

2.主要步骤

图3. 主要步骤

3.结果

本案例采用某年某月份的母机故障工单，进行频繁项挖掘的演示。本案例仅提供参考，所用数据均为演示数据，非真实业务数据。

1)数据预处理：经过相关处理，剩下500条工单；

2)频繁项挖掘：选择'server_type','model', 'server_version', 'cpu_model', 'nic_model', 'bios_type', 'mem_pn'等维度指标。设置最小支持度阈值为5，选择FP-growth算法进行频繁项挖掘。

3)结果分析：结果有*条频繁项，部分结果展示如表2. 由第一条指标组合可见，当server_type为s1且 model为m1时，有**台母机发生了故障，根据在所有相同配置的总机数中占比计算故障率，由此运营人员可据此指标组合进行更进一步的故障排查。

表2. 部分频繁项展示

4)性能优化：采用数据缓存、relim算法挖掘对程序性能优化，对比结果如下表。在当前数据量下，采用数据缓存能明显减小程序用时；采用Relim算法代替FP-growth算法挖掘频繁项貌似优化不明显，但当维度更高时这一优势将更加明显。优化后，程序耗时主要是在数据的读取部分，最终程序的总耗时提升了21%，而内存的占用仅仅增长了0.12G。

表3. 性能优化对比

5)后续如果考虑进一步引入30个维度指标。由于维度较高，可先进行单维度分析和相关性分析。单维度分析部分结果如表4，发现cpu_num为n1 的工单有495条，在最小支持度为5时占据主导地位，故可剔除cpu_num维度。同理，如果将最小支持度设置为500-480=20，则platform维度也可认为被p1占据主导地位进而剔除。

表4. 单维度分析

对所有指标做数值型替换，求出两两指标间的相关性，统计pearson相关性系数大于0.8（可视为高度相关）的指标对如表5。由表可知，序号1、2的两个指标对的相关性系数极高，可认为是一个属性的发生能反映另一个属性的发生规律，保留其一即可。序号3、4、5、6等相关性系数较高，保留指标对其中一个指标对结果影响轻微。可视情况保留其中一个指标，如有需要再进一步分析另一个指标的分布情况。

表5. 相关性分析

后续

在频繁项集的基础上，我们可以进一步挖掘关联规则。通俗来说，就是如果 A 发生了，那么 B 也很有可能会发生。结合置信度可以探索对于A事件的发生，有多大的概率会导致B事件的发生。关联规则可以用来发现很多有趣的规律，笔者将在后续跟进。

以上内容基于个人工作的总结。感谢运营开发组的小伙伴们的帮助，感谢学长@simbazhou，导师@lelandwu和学姐@mengnizhang给予的指导和帮助。

笔者不才。如有错误，欢迎指正！

参考链接

1.https://blog.csdn.net/suibianshen2012/article/details/51530952

2.http://hanj.cs.illinois.edu/pdf/dami04_fptree.pdf (Data Mining and Knowledge Discovery)

3.https://blog.csdn.net/lgnlgn/article/details/7614892

4.https://www.ibm.com/developerworks/cn/analytics/library/machine-learning-hands-on2-fp-growth/index.html

5.https://blog.csdn.net/my_learning_road/article/details/79738036

6.https://www.ibm.com/developerworks/cn/analytics/library/machine-learning-hands-on2-fp-growth/index.html

7.《Keeping Things Simple: Finding Frequent Item Sets by Recursive Elimination》

8.https://machinelearninggao.readthedocs.io/zh/stable/12.%E4%BD%BF%E7%94%A8FP-growth%E7%AE%97%E6%B3%95%E6%9D%A5%E9%AB%98%E6%95%88%E5%8F%91%E7%8E%B0%E9%A2%91%E7%B9%81%E9%A1%B9%E9%9B%86/