2024机器学习Apriori与FP-growth算法

Apriori与FP-growth算法Apriori和FP-growth算法是我们介绍的第一批关联算法，它们也属于无监督算法，可以自动从数据中挖掘出潜在的关联关系。尿布和啤酒的故事几乎是大数据科普文章中出现效率最高的成功案例，结合这个故事来介绍Apriori算法的基本概念，及基本的使用方式。然后介绍FP-growth算法的基本概念及其应用。目录TOC\o"1-1"\h\u296411Apriori算法概述 373292示例：helloworld！Apriori 8327213示例：使用Apriori算法挖掘XSS参数 9114634FP-growth算法概述 1249285示例：helloworld！FP-growth 1612736示例：使用FP-growth僵尸主机 17Apriori算法概述关联规则挖掘通常是无监督学习，通过分析数据集，挖掘出潜在的关联规则，最典型的一个例子就是尿布和啤酒的故事（见图11-1）。相传沃尔玛的数据分析人员通过分析大量购物清单发现，相当一部分消费者会同时购买尿布和啤酒，结果他们把尿布和啤酒赫然摆在一起出售，结果销量双双增长。关联规则分析的结果是客观现象的体现，有的显而易见，比如同时购买三文鱼和芥末，有的勉强可以解释，比如尿布和啤酒，有的就匪夷所思，比如打火机和奶酪。关联算法中最著名的就是Apriori算法。首先介绍三个基本概念：支持度、置信度、频繁k项集。支持度，P（A∩B），既有A又有B的概率，它表现的是A和B两个事件相对整个数据集合同时发生的频繁程度，比如尿布和啤酒的支持度是0.2，表明有20%的消费清单中，消费者同时购买了尿布和啤酒。置信度，P（B|A），在A发生的事件中同时发生B的概率P（AB）/P（A），它表现的是在AB两个事件的相关程度，和整个数据集合的大小没有关系，比如尿布和啤酒的置信度为0.8，表明在同时购买了两者的消费者中，购买尿布的80%又购买了啤酒。图11-1 沃尔玛经典案例尿不湿和啤酒的故事需要特别说明的是，P（A∩B）=P（B∩A），但是P（B|A）和P（A|B）是两回事。如果事件A中包含k个元素，那么称这个事件A。为k项集事件A。满足最小支持度阈值的事件称为频繁k项集。Apriori算法就是挖掘同时满足最小支持度阈值和最小置信度阈值的关联规则。Apriori算法使用频繁项集的先验知识，使用一种称为“逐层搜索”的迭代方法，k项集用于探索（k+1）项集。首先，通过扫描事务（交易）记录，找出所有的频繁1项集，该集合记做L1，然后利用L1找频繁2项集的集合L2，L2找L3，如此下去，直到不能再找到任何频繁k项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。其中，Apriori算法具有这样一条性质：任一频繁项集的所有非空子集也必须是频繁的。因为假如P（I）<最小支持度阈值，当有元素A添加到I中时，结果项集（A∩I）不可能比I出现次数更多，因此A∩I也不是频繁的。主流的机器学习库对Apriori支持很少，不过Apriori的实现的确比较简单，网上资源很多，建议看PeterHarrington的《机器学习实战》，完整演示代码请见本书GitHub上的11-1.py。下面介绍Apriori算法的基本步骤。假设数据库中存在下面四条购物记录：·ACD·BCE·ABCE·BE扫描数据库并计数，计算每个商品对应的支持度，如图11-2所示。图11-2 Apriori算法第一步根据设置的支持度筛选满足需求的L1，如图11-3所示。两两连接，获得新的数据集合，并重新扫描计数。如图11-4所示。图11-3 Apriori算法第二步图11-4 Apriori算法第三步如此循环，直到出现满足设置的支持度的全部集合出现。完整演示代码请见本书GitHub上的11-1.py。示例：helloworld！AprioriApriori实现后封装的函数如下，其中support代表支持度，minConf代表置信度：L,suppData=Apriori(myDat,support=0.5)rules=generateRules(L,suppData,minConf=0.5)假设我们需要从下列数据中挖掘频繁项集：myDat=[[1,3,4],[2,3,5],[1,2,3,5],[2,5]]满足的条件为支持度为0.5，置信度为0.7：L,suppData=apriori(myDat,0.5)rules=generateRules(L,suppData,minConf=0.7)print'rules:\n',rules输出结果为：frozenset([1])-->frozenset([3])conf:1.0frozenset([5])-->frozenset([2])conf:1.0frozenset([2])-->frozenset([5])conf:1.0rules:[(frozenset([1]),frozenset([3]),1.0),(frozenset([5]),frozenset([2]),1.0),(frozenset([2]),frozenset([5]),1.0)]示例：使用Apriori算法挖掘XSS参数在安全领域，Apriori的应用非常广泛，凡是需要挖掘潜在关联关系的都可以尝试使用，比如关联WAF的accesslog与后端数据库的sqllog，识别SSH操作日志中异常操作等。我们这里以分析accesslog为例子，完整演示代码请见本书GitHub上的11-2.py。我们从xssed网站的样例以及WAF的拦截日志中提取XSS攻击日志作为样本，示例日志如下：/0_1/?%22onmouseover='prompt(42873)'bad=%22%3E/0_1/api.php?op=map&maptype=1&city=test%3Cscript%3Ealert%28/42873/%29%3C/script%3E/0_1/api.php?op=map&maptype=1&defaultcity=%e5%22;alert%28/42873/%29;//我们目标是分析出潜在的关联关系，然后作为SVM、KNN等分类算法的特征提取依据之一。机器没有办法直接识别日志，需要逐行将日志文本向量化，最简单的方式就是按照一定的分割符切割成单词向量，示例代码如下：myDat=[]withopen("xss-train.txt")asf:forlineinf:tokens=re.split('\=|&|\?|\%3e|\%3c|\%3E|\%3C|\%20|\%22|<|>|\\n|\(|\)|\'|\"|;|:|,',lmyDat.append(tokens)f.close()切割后的向量示例如下：['/0_1/','','onmouseover','','prompt','42873','','bad','','','','']['/0_1/api.php','op','map','maptype','1','city','test','script','alert%28/4我们以十分严格的置信度来运行，试图找到关联关系接近100%的情况：L,suppData=Apriori(myDat,0.1)rules=generateRules(L,suppData,minConf=0.99)有趣的现象出现了：frozenset(['//','1'])-->frozenset(['','alert'])conf:1.0frozenset(['1','script'])-->frozenset(['','/script'])conf:1.0frozenset(['a','c'])-->frozenset(['','m'])conf:1.0frozenset(['1','/','script'])-->frozenset(['','/script'])conf:1.0frozenset(['1','alert','script'])-->frozenset(['','/script'])conf:1.0frozenset(['alert','/','script'])-->frozenset(['','/script'])conf:0.99741602frozenset(['1','alert','/','script'])-->frozenset(['','/script'])conf:1.0有些结果容易理解，比如'script'和'1'、'alert'出现的话，会100%地导致'/script'。有些结果匪夷所思，比如'a'和'c'出现的话，会100%地导致'm'。我们进一步降低门槛，将支持度也下降到0.001，这意味着即使对应的关联关系出现的概率只有千分之一，只要它对应的是强关联，置信度超过0.99，我们也认为这是一种有价值的关联：L,suppData=Apriori(myDat,0.001)rules=generateRules(L,suppData,minConf=0.99)这个学习过程会比较慢，我们选取了部分结果：frozenset(['version'])-->frozenset(['','base64','0FEBF34C4A2EBF825F60025D6C0576frozenset(['signMsg'])-->frozenset(['','object','0FEBF34C4A2EBF825F60025D6C0576frozenset(['0FEBF34C4A2EBF825F60025D6C0576F2'])-->frozenset(['','object','signM我们通过关联挖掘识别一种潜在的关联关系：'object''base64''data''text/html'。通过分析20万条XSS攻击样本数据，完全通过机器学习的方式挖掘潜在的关联关系，得到的结果举例如下。'object''base64''data''text/html'对应举例：/0/252/admin/receive.php?signMsg=0FEBF34C4A2EBF825F60025D6C0576F2&version=%3Cobjectalertscript1对应举例：/0/252/include/dialog/select_media.php?adminDirHand=%22/%3E%3C/script%3E%3Cscript%3scriptprompt对应举例：/0_1/?callback=%3Cscript%3Eprompt(42873)%3C/script%3Escriptsvgonloadalert对应举例：/commonDetail.asp?infotype=1"'></textarea></script><svgonload=alert`43873`>&id=46textareaautofocusonfocusalert对应举例：/index.php?siteid=1&a=sg"'></textarea></script><textareaautofocusonfocus=alert(20srcjavascriptiframe对应举例：/%22/e/?xss_test%3Ciframe%20src=javascript:this[%22%5Cx61%5Cx6c%5Cx65%5Cx72%5Cx74%2styleexpressionalert对应举例：/144/user.php?back_act=%22style=x:expression(alert(42873))%3EFP-growth算法概述FP-growth算法基于Apriori构建，但采用了高级的数据结构减少扫描次数，大大加快了算法速度。FP-growth算法只需要对数据库进行两次扫描，而Apriori算法对于每个潜在的频繁项集都会扫描数据集判定给定模式是否频繁，因此FP-growth算法的速度要比Apriori算法快。FP-growth算法发现频繁项集的基本过程如下：·构建FP树；·从FP树中挖掘频繁项集。FP-growth算法将数据存储在一种称为FP树的紧凑数据结构中。FP代表频繁模式。一棵FP树看上去与计算机科学中的其他树结构类似，但是它通过链接来连接相似元素，被连起来的元素项可以看成一个链表。图11-5给出了FP树的一个例子。图11-5 FP树结构举例与搜索树不同的是，一个元素项可以在一棵FP树种出现多次。FP树辉存储项集的出现频率，而每个项集会以路径的方式存储在数中。存在相似元素的集合会共享树的一部分。只有当集合之间完全不同时，树才会分叉。树节点上给出集合中的单个元素及其在序列中的出现次数，路径会给出该序列的出现次数。相似项之间的链接称为节点链接，用于快速发现相似项的位置。假设数据库中存在下面六条购物记录：·r，z，h，j，p·z，y，x，w，v，u，t，s·z·r，x，n，o，s·y，r，x，z，q，t，p·y，z，x，e，q，s，t，m元素项z出现了5次，集合{r，z}出现了1次。于是可以得出结论：z一定是自己本身或者和其他符号一起出现了4次。集合{t，s，y，x，z}出现了2次，集合{t，r，y，x，z}出现了1次，z本身单独出现1次。就像这样，FP树的解读方式是读取某个节点开始到根节点的路径。路径上的元素构成一个频繁项集，开始节点的值表示这个项集的支持度。我们可以快速读出项集{z}的支持度为5、项集{t，s，y，x，z}的支持度为2、项集{r，y，x，z}的支持度为1、项集{r，s，x}的支持度为1。FP树中会多次出现相同的元素项，也是因为同一个元素项会存在于多条路径，构成多个频繁项集。但是频繁项集的共享路径是会合并的，如上图中的{t，s，y，x，z}和{t，r，y，x，z}和之前一样，我们取一个最小阈值，出现次数低于最小阈值的元素项将被直接忽略。最小支持度设为3，所以q和p没有在FP中出现如图11-6所示。图11-6 FP树构建过程示例：helloworld！FP-growth算法有大量的开源实现，其中名气较大的是pyfpgrowth。完整演示代码请见本书GitHub上的11-3.py。pyfpgrowth的安装非常简单：pipinstallpyfpgrowthpyfpgrowth实现后封装的函数如下，其中support代表支持度，minConf代表置信度：patterns=pyfpgrowth.find_frequent_patterns(transactions,support)rules=pyfpgrowth.generate_association_rules(patterns,minConf)假设我们需要从下列数据中挖掘频繁项集：transactions=[[1,2,5],[2,4],[2,3],[1,2,4],[1,3],[2,3],[1,3],[1,2,3,5],[1,2,3]]满足的条件为支持度为2，置信度为0.7：patterns=pyfpgrowth.find_frequent_patterns(transactions,2)rules=pyfpgrowth.generate_association_rules(patterns,0.7)输出结果为：{(1,5):((2,),1.0),(5