关联规则 | 您所在的位置:网站首页 › 关联规则挖掘算法r煤炭分析 › 关联规则 |
一、关联规则简介
关联规则挖掘是一种基于规则的机器学习算法,该算法可以在大数据库中发现感兴趣的关系。它的目的是利用一些度量指标来分辨数据库中存在的强规则。也即是说关联规则挖掘是用于知识发现,而非预测,所以是属于无监督的机器学习方法。 Apriori算法是一种挖掘关联规则的频繁项集算法,其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。 关联规则的一般步骤: 1、找到频繁集; 2、在频繁集中通过可信度筛选获得关联规则。 关联规则应用: 1、Apriori算法应用广泛,可用于消费市场价格分析,猜测顾客的消费习惯,比如较有名的“尿布和啤酒”的故事; 2、网络安全领域中的入侵检测技术; 3、可用在用于高校管理中,根据挖掘规则可以有效地辅助学校管理部门有针对性的开展贫困助学工作; 4、也可用在移动通信领域中,指导运营商的业务运营和辅助业务提供商的决策制定。 关联规则算法的主要应用是购物篮分析,是为了从大量的订单中发现商品潜在的关联。其中常用的一个算法叫Apriori先验算法。 1、关联规则-概念关联分析(Association Analysis):在大规模数据集中寻找有趣的关系。 频繁项集(Frequent Item Sets):经常出现在一块的物品的集合,即包含0个或者多个项的集合称为项集。 支持度(Support):数据集中包含该项集的记录所占的比例,是针对项集来说的。 1、支持度(Support) 支持度揭示了A与B同时出现的概率。如果A与B同时出现的概率小,说明A与B的关系不大;如果A与B同时出现的非常频繁,则说明A与B总是相关的。 支持度: P(A∪B),即A和B这两个项集在事务集D中同时出现的概率。 首先我们把上面案例中的商品用 ID 来代表,牛奶、面包、尿布、可乐、啤酒、鸡蛋的商品 ID 分别设置为 1-6,上面的数据表可以变为: 首先,我们先计算单个商品的支持度,也就是得到 K=1 项的支持度: 在这个基础上,我们将商品两两组合,得到 k=2 项的支持度: 再筛掉小于最小值支持度的商品组合,可以得到: 通过上面这个过程,我们可以得到 K=3 项的频繁项集{1,2,3},也就是{牛奶、面包、尿布}的组合。 (3) Apriori 算法的递归流程:Apriori 算法的递归流程: 1、K=1,计算 K 项集的支持度; 2、筛选掉小于最小支持度的项集; 3、如果项集为空,则对应 K-1 项集的结果为最终结果。 否则 K=K+1,重复 1-3 步。 Apriori 的改进算法:FP-Growth 算法Apriori 在计算的过程中有以下几个缺点:1、可能产生大量的候选集。因为采用排列组合的方式,把可能的项集都组合出来了;2、每次计算都需要重新扫描数据集,来计算每个项集的支持度。所以 Apriori 算法会浪费很多计算空间和计算时间,为此人们提出了 FP-Growth 算法:1、创建了一棵 FP 树来存储频繁项集。在创建前对不满足最小支持度的项进行删除,减少了存储空间。2、整个生成过程只遍历数据集 2 次,大大减少了计算量。所以在实际工作中,我们常用 FP-Growth 来做频繁项集的挖掘,下面我给你简述下 FP-Growth 的原理。 (1)FP Tree数据结构为了减少I/O次数,FP Tree算法引入了一些数据结构来临时存储数据。这个数据结构包括三部分,如下图所示: 下面我们讲项头表和FP树的建立过程。 (2)项头表的建立FP树的建立需要首先依赖项头表的建立。首先我们看看怎么建立项头表。 我们第一次扫描数据,得到所有频繁一项集的的计数。然后删除支持度低于阈值的项,将1项频繁集放入项头表,并按照支持度降序排列。接着第二次也是最后一次扫描数据,将读到的原始数据剔除非频繁1项集,并按照支持度降序排列。 上面这段话很抽象,我们用下面这个例子来具体讲解。我们有10条数据,首先第一次扫描数据并对1项集计数,我们发现F,O,I,L,J,P,M, N都只出现一次,支持度低于20%的阈值,因此他们不会出现在下面的项头表中。剩下的A,C,E,G,B,D,F按照支持度的大小降序排列,组成了我们的项头表。 接着我们第二次扫描数据,对于每条数据剔除非频繁1项集,并按照支持度降序排列。比如数据项ABCEFO,里面O是非频繁1项集,因此被剔除,只剩下了ABCEF。按照支持度的顺序排序,它变成了ACEBF。其他的数据项以此类推。为什么要将原始数据集里的频繁1项数据项进行排序呢?这是为了我们后面的FP树的建立时,可以尽可能的共用祖先节点。 通过两次扫描,项头表已经建立,排序后的数据集也已经得到了,下面我们再看看怎么建立FP树。 有了项头表和排序后的数据集,我们就可以开始FP树的建立了。开始时FP树没有数据,建立FP树时我们一条条的读入排序后的数据集,插入FP树,插入时按照排序后的顺序,插入FP树中,排序靠前的节点是祖先节点,而靠后的是子孙节点。如果有共用的祖先,则对应的公用祖先节点计数加1。插入后,如果有新节点出现,则项头表对应的节点会通过节点链表链接上新节点。直到所有的数据都插入到FP树后,FP树的建立完成。 似乎也很抽象,我们还是用第二节的例子来描述。 首先,我们插入第一条数据ACEBF,如下图所示。此时FP树没有节点,因此ACEBF是一个独立的路径,所有节点计数为1, 项头表通过节点链表链接上对应的新增节点。 我们辛辛苦苦,终于把FP树建立起来了,那么怎么去挖掘频繁项集呢?看着这个FP树,似乎还是不知道怎么下手。下面我们讲如何从FP树里挖掘频繁项集。得到了FP树和项头表以及节点链表,我们首先要从项头表的底部项依次向上挖掘。对于项头表对应于FP树的每一项,我们要找到它的条件模式基。所谓条件模式基是以我们要挖掘的节点作为叶子节点所对应的FP子树。得到这个FP子树,我们将子树中每个节点的的计数设置为叶子节点的计数,并删除计数低于支持度的节点。从这个条件模式基,我们就可以递归挖掘得到频繁项集了。 实在太抽象了,之前我看到这也是一团雾水。还是以上面的例子来讲解。我们看看先从最底下的F节点开始,我们先来寻找F节点的条件模式基,由于F在FP树中只有一个节点,因此候选就只有下图左所示的一条路径,对应{A:8,C:8,E:6,B:2, F:2}。我们接着将所有的祖先节点计数设置为叶子节点的计数,即FP子树变成{A:2,C:2,E:2,B:2, F:2}。一般我们的条件模式基可以不写叶子节点,因此最终的F的条件模式基如下图右所示。 F挖掘完了,我们开始挖掘D节点。D节点比F节点复杂一些,因为它有两个叶子节点,因此首先得到的FP子树如下图左。我们接着将所有的祖先节点计数设置为叶子节点的计数,即变成{A:2, C:2,E:1 G:1,D:1, D:1}此时E节点和G节点由于在条件模式基里面的支持度低于阈值,被我们删除,最终在去除低支持度节点并不包括叶子节点后D的条件模式基为{A:2, C:2}。通过它,我们很容易得到F的频繁2项集为{A:2,D:2}, {C:2,D:2}。递归合并二项集,得到频繁三项集为{A:2,C:2,D:2}。D对应的最大的频繁项集为频繁3项集。
至此我们得到了所有的频繁项集,如果我们只是要最大的频繁K项集,从上面的分析可以看到,最大的频繁项集为5项集。包括{A:2, C:2, E:2,B:2,F:2}。 通过上面的流程,相信对FP Tree的挖掘频繁项集的过程也很熟悉了。 (5)FP Tree算法归纳这里我们对FP Tree算法流程做一个归纳。FP Tree算法包括三步: 1)扫描数据,得到所有频繁一项集的的计数。然后删除支持度低于阈值的项,将1项频繁集放入项头表,并按照支持度降序排列。 2)扫描数据,将读到的原始数据剔除非频繁1项集,并按照支持度降序排列。 3)读入排序后的数据集,插入FP树,插入时按照排序后的顺序,插入FP树中,排序靠前的节点是祖先节点,而靠后的是子孙节点。如果有共用的祖先,则对应的公用祖先节点计数加1。插入后,如果有新节点出现,则项头表对应的节点会通过节点链表链接上新节点。直到所有的数据都插入到FP树后,FP树的建立完成。 4)从项头表的底部项依次向上找到项头表项对应的条件模式基。从条件模式基递归挖掘得到项头表项项的频繁项集。 5)如果不限制频繁项集的项数,则返回步骤4所有的频繁项集,否则只返回满足项数要求的频繁项集。 (6)FP tree算法总结FP Tree算法改进了Apriori算法的I/O瓶颈,巧妙的利用了树结构,这让我们想起了BIRCH聚类,BIRCH聚类也是巧妙的利用了树结构来提高算法运行速度。利用内存数据结构以空间换时间是常用的提高算法运行时间瓶颈的办法。 在实践中,FP Tree算法是可以用于生产环境的关联算法,而Apriori算法则做为先驱,起着关联算法指明灯的作用。除了FP Tree,像GSP,CBA之类的算法都是Apriori派系的。 |
CopyRight 2018-2019 实验室设备网 版权所有 |