精华内容
下载资源
问答
  • 频繁模式挖掘——概述
    2021-03-08 09:15:58

    频繁模式挖掘(Frequent Pattern Mining)

    1. 基本概念
      a. 频繁模式(frequent pattern)是频繁地出现在数据集中的模式(如项集、子序列或子结构)。
      例如:
      i. 频繁同时出现在交易数据集中的商品(如牛奶和面包)的集合是频繁项集。
      ii. 一个序列如首先购买PC、然后是数码相机、再后是内存卡,如果它频繁地出现再购物历史数据中,则称它为一个频繁序列模式(FTM)。
      iii. 一个子结构可能涉及不同的结构形式,如子图、子树或子格,它可能与项集或子序列结合在一起。如果一个子结构频繁地出现,则称它为频繁结构模式(FSM)。
      b. 项(item)、项集(itemset)、频繁项集(frequent itemset)
      项(item)表示一种研究对象(例如购物篮实例里的商品)。设I={I_1,I_2,…,I_m}是项的集合,称为项集(itemset)。设任务相关的数据D是数据库事务的集合,其中每个事务T是一个非空项集,满足TϵI。每一个事务都有一个标识符,称为TID。
      c. 关联规则、支持度(support)、置信度(confidence)
      关联规则是形如A⇒B的蕴含式,其中A⊂I,B⊂I,A≠∅,B≠∅,并且A∩B≠∅。规则A⇒B在事务集D中具有支持度s,其中s是D中事务包含A∪B(集合A和B的并)的百分比。规则A⇒B在事务集D中具有置信度c,其中c是D中在包含A事务的前提下包含B事务的百分比。同时满足最小支持度阈值(min_sup)和最小置信度阈值(min_conf)的规则称为强规则。
      support(A⇒B)=P(A∪B)
      confidence(A⇒B)=P(B│A)=(support(A∪B))/(support(A))=(support_count(A∪B))/(support_count(A))
      如果项集I的支持度s满足预定义的最小支持度阈值,则I是频繁项集。频繁k项集的集合通常记为L_k。
      d. 挖掘过程
      上式表明A⇒B的置信度容易从A和A∪B的支持度计数推出。挖掘关联规则的问题可以归结为挖掘频繁项集。
      一般关联规则的挖掘可以分为两步:
      (1)找出所有的频繁项集。根据定义,这些项集的支持度至少与预定义的最小支持度阈值一样。
      (2)由频繁项集产生强关联规则。根据定义,这些规则必须满足最小支持度和最小置信度。
      *一个例子。下图为5次交易的数据,每行代表一个事务,每个事务包好几个项。数据内隐含着内在关联。

    事务:由事务号和项集组成。事务是一次购买行为。
    项:最小处理单元,即购买的物品。
    项集:由一个或多个项组成。
    支持度计数:包含某个项集的事务数。
    关联规则:A和B都是项集,A⇒B(s,c)。这里假设A={Milk,Diaper},B={Beer}。
    支持度:包含某个项集的事务数的比例
    s=(|Milk,Diaper,Beer|)/(|T|)=2/5=0.4
    置信度:在所有包含X项集的事务中包含Y项集事务的比例
    s=(|Milk,Diaper,Beer|)/(|Milk,Diaper|)=2/3=0.67
    关联规则评估:
    {Milk,Diaper}⇒{Beer}(0.4,0.67)
    支持度不小于指定阈值,并且置信度不小于指定阈值,则为强关联规则。
    2. 相关算法
    2.1 Apriori算法(经典的频繁项集挖掘算法)
    a. 算法核心思想
    (1)如果一个集合是频繁项集,则它的所有子集都是频繁项集;
    (2)如果一个集合不是频繁项集,则它的所有超集都不是频繁项集。
    b. 算法流程
    i. 找到频繁的一维项集L1;
    ii. 从频繁的L_k维项集生成k+1维项集C_(k+1);(下面详细说明)
    iii. 找到C_(k+1)中的频繁项集L_(k+1);
    iv. k=k+1,循环执行i和ii,直到k+1=n,n为最大项集;或产生的项集为空,即不存在更大的频繁项集;
    v. 输出各维度的频繁项集。

    *说明如何从L_k生成 C_(k+1)的方法,k>1
    i. 假设在L_k中的所有items都是排序好的(例如alphabetical)。
    ii. 连接(joining)。将L_k与自身连接(L_k⋈L_k)从而产生C_(k+1),具体方法是:设l_1和l_2是L_k中的项集,l_1 [j]表示l_1的第j项。则称l_1和l_2是可连接的,如果〖(l〗_1 [1]=l_2 [1])∧〖(l〗_1 [2]=l_2 [2])∧…∧〖(l〗_1 [k-1]=l_2 [k-1])∧〖(l〗_1 [k]<l_2 [k])。连接的结果是生成一个k+1项集,〖{l〗1 [1],l_1 [2],…,l_1 [k],l_2 [k]}。
    iii. 剪枝(pruning)。删除生成的C
    (k+1)中的某个项集,如果这个项集满足,它存在一个k维子项集,且这个子项集不在L_k中。(为了减小时间复杂度,通过基本思想的第二点可以直接删除某些非频繁项集)。

    *一个例子。下表表示一个事务数据库D,每一行都是一个事务T,包含TID和项集。目标是找出满足min_sup=2的所有维度的频繁项集。

    最终产生了三个维度的频繁项集,L_1,L_2,L_3。我们可以根据频繁项集来得到相应的关联规则。

    2.2 提高Apriori算法效率
    基于散列的技术/事务压缩/划分/抽样/动态项集计数等。

    2.3 Apriori算法存在的问题
    主要还是开销问题。
    (1)需要产生大量候选项集;
    (2)需要重复扫描整个数据库,通过模式匹配检查一个很大的候选集合。
    已有的解决方法:
    FP-growth,将代表频繁项集的数据库压缩到一棵频繁模式树(FP树)上。通过把事务映射到FP树上的一条路径上来构造,由于不同事务可能会有若干相同的项,因此它们的路径可能部分重叠。路径相互重叠越多,使用FP树结构获得的压缩效果越好。

    FP增长采用分治策略将一个子问题分解为较小的子问题,从而发现以某个特定后缀结尾的所有频繁项集。

    2.4垂直数据格式挖掘
    Apriori和FP-growth算法都是以{TID: itemset}的事务集中挖掘频繁模式。这种格式是水平数据格式。也可以通过{item:TID_set}这种数据格式来挖掘频繁模式,这种称为垂直数据格式。
    3. 模式评估方法

    1. 支持度-置信度框架。可能存在的问题:有可能一个强关联规则并不能很好的表示A和B之间的关系(即A和B有可能是负相关的)。
    2. 相关性分析。A⇒B[support,confidence,correlation]。
      a. 提升度(lift)。
      lift(A,B)=(P(A∪B))/(P(A)P(B))
      值为1代表A和B是独立的;
      值小于1代表A和B负相关,意味着一个的出现可能导致另一个不出现。
      值大于1代表A和B正相关,意味着一个的出现都蕴含着另一个的出现。

    b. χ^2相关性度量
    χ2=∑_(i=1)c▒∑_(j=1)r▒〖(o_ij-e_ij)〗2/e_ij
    上述两种指标不是零不变的(度量值不受零事务的影响,零事务是指不包含任何考察项集的事务)。
    c. 全置信度
    all_conf(A,B)=(sup⁡(A⋃B))/(max⁡{sup⁡(A),sup⁡(B)})=min{P(A|B),P(B|A)}
    d. 最大置信度
    max⁡_conf(A,B)=max{P(A|B),P(B|A)}
    e. Kulc度量
    Kulc(A,B)=1/2(P(A│B)+P(B|A))
    f. 不平衡比(Imbanlance Ratio, IR),用来评估规则蕴含式中两个项集A和B的不平衡程度。
    IR(A,B)=(|sup⁡(A)-sup⁡(B)|)/(sup⁡(A)+sup⁡(B)-sup⁡(A⋃B))
    结论,采用Kulc度量和不平衡比配合使用最好。
    4. 频繁子图挖掘(Frequent Sub-graph Mining - FSM)

    Graph mining研究情况:

    (1)基本概念
    • Discovery of graph structures that occur a significant number of times across a set of graphs
    - Support is some integer or frequency 分为单图挖掘&多图挖掘

    • Frequent graphs occur more than support number of times.

    • Ex.: Common occurrences of hydroxide-ion
    • Other instances:

    • Finding common biological pathways among species.
    • Recurring patterns of humans interaction during an epidemic.
    • Highlighting similar data to reveal data set as a whole.
      (2)主要难点
      a. 图重构。
      b. 子图重构。
      这些问题都是NP-Complete。
      (3)一些方法
      a. 传统frequent pattern mining方法
      可以说是Apriori算法的变形。
      General Process:
      candidate generation: which patterns will be considered? For FSM,
      candidate pruning: if a candidate is not a viable frequent pattern, can we exploit the pattern to prevent unnecessary work?
      *subgraphs and subsets exponentiate as size increases!
      support counting: how many of a given pattern exist?
      DFS or BFS
      Joins smaller frequent sets into larger ones.
      Checks the frequency of larger sets.

    b. gSpan

    • complete frequent subgraph mining
    • Apriori扩展,使用DFS和candidate pruning来提升性能。
      编码方式

    c. SUBDUE

    • approximate frequent subgraph mining
    • 使用图压缩的方法来决定频繁模式。
      d. SLEUTH
    • complete frequent subgraph mining
    • built specifically for trees

    (4)算法评价
    • Apriori-based Approach (Traditional):

    • Strength: Simple to implement
    • Weakness: Inefficient
      • gSpan (and other Pattern Growth algorithms):
      Strength: More efficient than Apriori
      Weakness: Still too slow on large data sets
      • SUBDUE
      Strength: Runs very quickly
      Weakness: Uses a heuristic(启发式), so it may miss some frequent subgraphs
      • SLEUTH:
    • Strength: Mines embedded trees, not just induced, much quicker than more general FSM
    • Weakness: Only works on trees… not all graphs

    Reference
    [1]. Yan, X. and Han, J.W. 2002. gSpan: Graph-based Substructure pattern mining, In Proceedings of International Conference on Data Mining, 721–724.
    [2]. Yan, X. and Han, J. 2003. CloseGraph: Mining Closed Frequent Graph Patterns, In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 286–295, Washington D.C., USA.
    [3]. C Jiang, F Coenen, M Zito - Knowledge Engineering, A Survey of Frequent Subgraph Mining Algorithms, 2013 - livrepository.liverpool.ac.uk, The Knowledge Engineering Review, Vol. 00:0, 1–31

    更多相关内容
  • 为解决传统频繁模式挖掘算法效率不高的问题,提出了一种改进的基于FP-tree (Frequent pattern tree)的Apriori频繁模式挖掘算法.首先,在Apriori算法的连接步加入连接预处理过程;其次,对CP-tree (Compact ...
  • 频繁模式挖掘 LDA在由来自5个域的会议论文的标题组成的数据集上运行。 使用LDA的结果,为每个标题的每个单词分配一个主题。 每个主题代表计算机科学的五个领域之一:数据挖掘(DM),机器学习(ML),数据库(DB),...
  • 频繁模式挖掘.docx

    2021-11-10 16:51:46
    简述频繁模式挖掘
  • 频繁模式挖掘

    2014-10-04 09:31:19
    频繁模式挖掘的基本算法,不错的ppt,数据挖掘领域的基础方法,入门必学
  • 基于Apriori、FP-Growth及Eclat算法的频繁模式挖掘源程序 一、DataMiningApriori程序 用eclipse打开,把三个测试数据mushroom、accidents和T10I4D100K放置 在F:\DataMiningSample\FPmining文件夹下面,即可运行 ...
  • 传统数据挖掘算法在处理多表时,需要物理连接...为了解决这一问题,提出了一种多关系频繁模式挖掘算法。该算法利用元组ID传播的思想,使多表间无须物理连接,就可以直接挖掘频繁模式。实验表明,此算法具有较高的效率。
  • 在对FP-树进行改造的基础上提出基于划分思想的频繁项集挖掘算法UPM.算法的项集频度计算和非频繁项目裁剪都基于空间划分的思想。性能实验表明,与FP-Growth算法相比,UPM算法的时空效率有较大提高。
  • 采用垂直二进制位图映射事务数据库,提出了用二进制位图生成一种新的NBFP-Tree结构,并据此提出了一种新的频繁模式挖掘算法NBFP-mine.该算法不产生候选集,对NBFP-Tree结构进行深度优先遍历一次,就可从 NBFP-Tree...
  • Frequent Pattern Mining Algorithms: A Survey. 作者:Charu C. Aggarwal, Mansurul A. Bhuiyan and Mohammad Al Hasan。 频繁模式挖掘算法:调查
  • 这是频繁模式挖掘的一个经典例子——"啤酒和尿布"。简单来说,频繁模式就是当出现物品A时也经常出现物品B,比如在分析超市的购物清单时,发现买啤酒的人经常也买尿布。 购物篮分析(或是亲密性分析)是介绍...

    1.理论背景

            在美国,著名的沃尔玛超市发现啤酒与尿布总是共同出现在购物车中,于是沃尔玛超市经过分析发现许多美国年轻的父亲下班之后经常要去购买婴儿的尿布,而在购买尿布的同时,他们往往会顺手购买一些啤酒;因此沃尔玛超市将啤酒与尿布放在相近的位置,方便顾客购买,并明显提高了销售额。这是频繁模式挖掘的一个经典例子——"啤酒和尿布"。简单来说,频繁模式就是当出现物品A时也经常出现物品B,比如在分析超市的购物清单时,发现买啤酒的人经常也买尿布。

            购物篮分析(或是亲密性分析)是介绍频繁模式挖掘的最佳案例,它是众所周知的频繁模式挖掘应用之一。购物篮分析试图从消费者加入购物篮的商品中挖掘出某种模式或者关联,可以是真实的购物篮,也可以是虚拟的,并且给出支持度或是置信度。这一方法在用户行为分析中存在巨大的价值。将购物篮分析推而广之就成了频繁模式挖掘,实际上它与分类非常类似,只是通过相互的关联预测属性或是属性的组合(不仅仅是预测类别)。因为关联不需要有标签的数据集,所以它属于无监督式学习

     2.基本概念

    2.1频繁模式定义

            频繁模式指的就是频繁出现在数据集中的模式,比如子序列、项集、子结果。研究频繁模式的目的是得到关联规则和其他的联系,并在实际中应用这些规则和联系。比如,频繁地同时出现在交易数据集中的商品(比如牛奶和面包)的集合是频繁项集;频繁的出现的一个购买顺序(先买笔记本,再买杀毒软件)是频繁子序列。

    2.2相关概念定义

           频繁项集一般是指频繁地在事务数据集中一起出现的商品的集合,如小卖部中被许多顾客频繁地一起购买的牛奶和面包。

            频繁子序列,如顾客倾向于先购买便携机,再购买数码相机,然后再购买内存卡这样的模式就是一个(频繁)序列模式。

           频繁子结构是指从图集合中挖掘频繁子图模式。子结构可能涉及不同的结构形式(例如,图、树或格),可以与项集或子序列结合在一起。如果一个子结构频繁地出现,则称它为(频繁)子结构模式。

           关联规则是形如X \Rightarrow Y的蕴含式,其中X \subseteq l,\quad Y \subseteq ll且X \cap Y=\varnothing,则X称为规则的条件,Y称为规则的结果。如果事务数据库D中有s%的事务包含X \cup Y,则称关联规则X \Rightarrow Y的支持度为s%。例如 牛奶=>鸡蛋【支持度=2%,置信度=60%】。关联规则意味着元素项之间“如果…那么…”的关系。

           事务是由一组物品组成,可看作一个订单中的物品集合。
           支持度是某几个物品一起出现在事物中的次数或在数据库中所占的比例。

           置信度是在出现A时出现B的概率,就是P(B|A) = P(A B) / P(A)

           频繁项集是满足最小支持度要求的项集,它给出经常在一起出现的元素项。

           项集表示包含0个或者多个项的集合。如果一个项集包含k个项,则称为k项集 。

           强关联规则表示同时满足最小支持度和最小置信度阈值要求的所有关联规则。

           例如:假设最小置信度阈值为30%,最小置信度阈值为70%,而关联规则:购买面包⇒购买牛奶[支持度=50%,置信度=100%]的支持度和置信度都满足条件,则该规则为强关联规则。 

    2.3先验性质

    • 关联规则挖掘的任务

            ①根据最小支持度阈值,找出数据集中所有的频繁项集;

            ②挖掘出频繁项集中满足最小支持度和最小置信度阈值要求的规则,得到强关联规则;

            ③对产生的强关联规则进行剪枝,找出有用的关联规则。

    • 频繁项集的先验性质

            1.如果某个项集是频繁的,那么它的所有子集也是频繁的。例如如果{B,C}是频繁的,那么{B},{C}也一定是频繁的。

            2.如果一个项集是非频繁集,那么它的所有超集(包含该非频繁集的父集)也是非频繁的。如果{A, B}是非频繁的,那么{A, B, C},{A, B, C, D}也一定是频繁的。

    2.4 关联规则挖掘的步骤

    1. 找出所有频繁项集,即大于或等于最小支持度阈值的项集。
    2. 由频繁项集产生强关联规则,这些规则必须大于或等于最小支持度阈值和最小置信度阈值。

    3 Apriori算法

    3.1算法概述

           Apriori算法是布尔关联规则挖掘频繁项集的原创性算法,该算法使用频繁项集性质的先验知识。Apriori使用一种称作逐层搜索的迭代方法,k项集用于探索(k+1)项集。首先,通过扫描数据库,累积每个项(数据集不重复的元素)的计数,并收集满足最小支持度的项,找出频繁1项集的集合,并将集合记作L1。然后,L1用于找频繁2项集的集合L2,L2用于找L3,如此迭代,直到不能再找到频繁k项集。找每个Lk需要一次数据库全扫描。

    3.2实现原理

            算法实现过程分为两步,一步是连接,一步是剪枝

            输入:项集I,事务数据集D,最小支持度计数阈值Min_sup

            输出:D中的所有频繁项集的集合L。

            实现步骤:

            (1)求频繁1项集L1 首先通过扫描事务数据集D,找出所有1项集并计算其支持度,作为候选1项集C1 然后从C1中删除低于最小支持度阈值Min_sup的项集,得到所有频繁1项集的集合L1 。

            (2)For k=2,3,4,分别得到L2、L3、L4...Lk。

            (3)连接:将Lk-1进行自身连接生成候选k项集的集合Ck,连接方法如下:对于任意p,q∈Lk-1,若按字典序有p={p1,p2,…,pk-2,pk-1}, q={p1,p2,…,pk-2,qk-1},且满足pk-1<qk-1,则把p和q连接成k项集   {p1,p2,…,pk-2,pk-1,qk-1}作为候选k项集Ck中的元素。

            (4)剪枝:删除Ck中的非频繁k项集,即当Ck中一个候选k项集的某个k-1项子集不是Lk-1中的元素时,则将它从Ck中删除。

            (5)计算支持数:通过扫描事务数据集D,计算Ck中每个k项集的支持数。

            (6)求Lk:删除Ck中低于最小支持度阈值Min_sup的k项集,得到所有频繁k项集的集合Lk。         (7)若Lk=Ø,则转第(9)步

            (8)END FOR

             (9)另L=L1∪L2∪…∪Lk,并输出L。

            强关联规则的生成过程包括两个步骤:

            ①对于所有频繁项集的集合L中的每个频繁项集X,生成X所有的非空真子集Y;

            ②对于X中的每一个非空真子集Y,构造关联规则Y⇒(X−Y) 。 构造出关联规则后,计算每一个关联规则的置信度,如果大于最小置信度阈值,则该规则为强关联规则。

     --------------------------------------------------------------------------------------------------------------------------------

             【注意】可以通过枚举频繁项集生成所有的关联规则,并通过计算关联规则的置信度来判断该规则是否为强关联规则。但当一个频繁项集包含的项很多时,就会生成大量的候选关联规则,1个频繁项集X能够生成2^{|X|}-2个(即除去空集及自身之外的子集)候选关联规则。

     3.3案例分析

            假设使用表中的事务数据,该数据库具有9个事务,设最小支持度为2,试使用Apriori算法挖掘表1的事务数据中的频繁项集。

    TID

    Items

    1

    面包、可乐、麦片

    2

    牛奶、可乐

    3

    牛奶、面包、麦片

    4

    牛奶、可乐

    5

    面包、鸡蛋、麦片

    6

    牛奶、面包、可乐

    7

    牛奶、面包、鸡蛋、麦片

    8

    牛奶、面包、可乐

    9

    面包、可乐

    实现过程:

             对于上述例子中L中的频繁3项集{牛奶,面包,麦片},可以推导出非空子集:

            {{牛奶},{面包},{麦片},{牛奶,面包},{牛奶,麦片},{面包,麦片}}。

            可以构造的关联规则及置信度如下:

             {牛奶} ⇒ {面包,麦片},置信度=2/6=33%

            {面包} ⇒{牛奶,麦片},置信度=2/7=29%

            {麦片} ⇒ {牛奶,面包},置信度=2/4=50%

            {牛奶,面包} ⇒ {麦片},置信度=2/4=50%

            {牛奶,麦片} ⇒ {面包},置信度=2/2=100%

            {面包,麦片} ⇒ {牛奶},置信度=2/4=50%

            如果令最小置信度为70%,则得到的强关联规则有:

            {牛奶,麦片} ⇒ {面包},置信度=2/2=100%

    3.4算法特点

    3.5算法Python实现

    可以通过模块efficient_apriori实现apriori算法,需要另外安装,输入如下命令安装,模块链接

    pip install efficient-apriori
    • 案例1 
    from efficient_apriori import apriori
    transactions = [('eggs', 'bacon', 'soup'),
                    ('eggs', 'bacon', 'apple'),
                    ('soup', 'bacon', 'banana')]
    itemsets, rules = apriori(transactions, min_support=0.5, min_confidence=1)
    print(rules)  # [{eggs} -> {bacon}, {soup} -> {bacon}]

    【注意】在每笔有鸡蛋的交易中,也有培根。 因此,规则 {eggs} -> {bacon} 以 100% 的置信度返回。

    • 案例2
    from efficient_apriori import apriori
    transactions = [('eggs', 'bacon', 'soup'),
                    ('eggs', 'bacon', 'apple'),
                    ('soup', 'bacon', 'banana')]
    itemsets, rules = apriori(transactions, min_support=0.2, min_confidence=1)
    
    # Print out every rule with 2 items on the left hand side,
    # 1 item on the right hand side, sorted by lift
    rules_rhs = filter(lambda rule: len(rule.lhs) == 2 and len(rule.rhs) == 1, rules)
    for rule in sorted(rules_rhs, key=lambda rule: rule.lift):
        print(rule)  # Prints the rule and its confidence, support, lift, ...

    可以对返回的关联规则列表进行筛选和排序。

    • 案例3
    rom efficient_apriori import apriori
    transactions = [('eggs', 'bacon', 'soup'),
                    ('eggs', 'bacon', 'apple'),
                    ('soup', 'bacon', 'banana')]
    itemsets, rules = apriori(transactions, output_transaction_ids=True)
    print(itemsets)
    # {1: {('bacon',): ItemsetCount(itemset_count=3, members={0, 1, 2}), ...

    可以自己编写apriori算法实现过程,参考代码如下:

    # -*- coding: utf-8 -*-
    #加载数据集
    def loadDataSet():
        return [[1,3,4],[1,3,5],[2,3,4,5],[3,5],[2,3,5],[1,2,3,5],[2,5]]
    
    #选取数据集的非重复元素组成候选集的集合C1
    def createC1(dataSet):
        C1=[]
        for transaction in dataSet: #对数据集中的每条购买记录
            for item in transaction: #对购买记录中的每个元素
                if [item] not in C1: #注意,item外要加上[],便于与C1中的[item]对比
                    C1.append([item])
        C1.sort()
        return list(map(frozenset,C1)) #将C1各元素转换为frozenset格式,注意frozenset作用对象为可迭代对象
    
    #由Ck产生Lk:扫描数据集D,计算候选集Ck各元素在D中的支持度,选取支持度大于设定值的元素进入Lk
    def scanD(D,Ck,minSupport):
        ssCnt={}
        for tid in D: #对数据集中的每条购买记录
            for can in Ck: #遍历Ck所有候选集
                if can.issubset(tid): #如果候选集包含在购买记录中,计数+1
                    ssCnt[can]=ssCnt.get(can,0)+1
        numItems=float(len(D)) #购买记录数
        retList=[] #用于存放支持度大于设定值的项集
        supportData={} #用于记录各项集对应的支持度
        for key in ssCnt.keys():
            support=ssCnt[key]/numItems
            if support>=minSupport:
                retList.insert(0,key)
            supportData[key]=support
        return retList,supportData
    
    #由Lk产生Ck+1
    def aprioriGen(Lk,k): #Lk的k和参数k不是同一个概念,Lk的k比参数k小1
        retList=[]
        lenLk=len(Lk)
        for i in range(lenLk):
            for j in range(i+1,lenLk): #比较Lk中的每一个元素与其他元素
                L1=list(Lk[i])[:k-2];L2=list(Lk[j])[:k-2]
                L1.sort();L2.sort()
                if L1==L2: #若前k-2项相同,则合并这两项
                    retList.append(Lk[i]|Lk[j])
        return retList
    
    #Apriori算法主函数
    def apriori(dataSet,minSupport=0.5):
        C1=createC1(dataSet)
        D=list(map(set,dataSet))
        L1,supportData=scanD(D,C1,minSupport)
        L=[L1]
        k=2
        while len(L[k-2])>0: #当L[k]为空时,停止迭代
            Ck=aprioriGen(L[k-2],k) #L[k-2]对应的值是Lk-1
            Lk,supK=scanD(D,Ck,minSupport)
            supportData.update(supK)
            L.append(Lk)
            k+=1
        return L,supportData
    
    # 主函数,由频繁项集以及对应的支持度,得到各条规则的置信度,选择置信度满足要求的规则为关联规则
    # 为了避免将所有数据都对比一遍,采用与上述相同的逻辑减少计算量——一层一层计算筛选
    def generateRules(L,supportData,minConf=0.7):
        bigRuleList=[]
        for i in range(1,len(L)):
            for freqSet in L[i]:
                H1=[frozenset([item]) for item in freqSet] # H1是频繁项集单元素列表,是关联规则中a->b的b项
                if i>1:
                    rulesFromConseq(freqSet,H1,supportData,bigRuleList,minConf)
                else:
                    calConf(freqSet,H1,supportData,bigRuleList,minConf)
        return bigRuleList
    
    # 置信度计算函数
    def calConf(freqSet,H,supportData,brl,minConf=0.7):
        prunedH=[] # 用于存放置信度满足要求的关联规则的b项,即“提纯后的H”
        for conseq in H:
            conf=supportData[freqSet]/supportData[freqSet-conseq]
            if conf>=minConf:
                print (freqSet-conseq,'-->',conseq,'conf:',conf)
                brl.append([freqSet-conseq,conseq,conf])
                prunedH.append(conseq)
        return prunedH
    
    # 关联规则合并函数
    def rulesFromConseq(freqSet,H,supportData,brl,minConf=0.7):
        m=len(H[0])
        if len(freqSet)>(m+1): #查看频繁项集freqSet是否大到可以移除大小为m的子集
            Hmp1=aprioriGen(H,m+1) # 从Hm合并Hm+1
            Hmp1=calConf(freqSet,Hmp1,supportData,brl,minConf)
            if len(Hmp1)>1: #若合并后的Hm+1的元素大于1个,则继续合并
                rulesFromConseq(freqSet,Hmp1,supportData,brl,minConf)
    
    dataset=loadDataSet()
    C1=createC1(dataset)
    D=list(map(set,dataset))
    L1,supportData0=scanD(D,C1,0.5)
    L,supportData=apriori(dataset,minSupport=0.5)
    print(L)
    
    L,supportData=apriori(dataset,minSupport=0.5)
    rules=generateRules(L,supportData,minConf=0.5)

    4 FP-growth算法

    4.1 算法概述

            作为一个挖掘频繁项集的算法,Apriori算法需要多次扫描数据,I/O是很大的瓶颈。FP-growth算法是基于Apriori原理的,通过将数据集存储在FP(Frequent Pattern)树上发现频繁项集,但不能发现数据之间的关联规则。FP树是一种存储数据的树结构,如右图所示,每一路分支表示数据集的一个项集,数字表示该元素在某分支中出现的次数。如下图所示:

    于是FP-Growth算法发现频繁项集的过程是:

    (1)项头表的建立; 

    (2)构建FP树;

    (3)从FP树中挖掘频繁项集。

    【注意】无论多少数据,只需要扫描两次数据集,因此提高了算法运行的效率。

    4.2 算法描述

     4.3实现过程

    第1步:项头表的建立。

    第2步:FP 树的建立。

            有了项头表和排序后的数据集,就可以开始FP树的建立。      

            开始时FP树没有数据,建立FP树时我们一条条的读入排序后的数据集,插入FP树,插入时按照排序后的顺序,插入FP树中,排序靠前的节点是祖先节点,而靠后的是子孙节点。        

            如果有共用的祖先,则对应的共用祖先节点计数加1。插入后,如果有新节点出现,则项头表对应的节点会通过节点链表链接上新节点。直到所有的数据都插入到FP树后,FP树的建立完成。

     详细的实现过程如下:

    第3步:从FP树里挖掘频繁项集。

            得到了FP树和项头表以及节点链表,我们首先要从项头表的底部项依次向上挖掘。对于项头表对应于FP树的每一项,我们要找到它的条件模式基。所谓条件模式基是以我们要挖掘的节点作为叶子节点所对应的FP子树。得到这个FP子树,我们将子树中每个节点的的计数设置为叶子节点的计数,并删除计数低于支持度的节点。从这个条件模式基,我们就可以递归挖掘得到频繁项集。

     

     

     

     FP-growth算法实现步骤:

     4.4案例分析

            该数据集具有9个事务,设最小支持度为2,频繁项集的极大长度为3。试使用FP-growth算法挖掘表2的事务数据中的频繁项集。

    TID

    Items

    1

    面包、可乐、麦片

    2

    牛奶、可乐

    3

    牛奶、面包、麦片

    4

    牛奶、可乐

    5

    面包、鸡蛋、麦片

    6

    牛奶、面包、可乐

    7

    牛奶、面包、鸡蛋、麦片

    8

    牛奶、面包、可乐

    9

    面包、可乐

     

     

     

     

    4.5算法特点

     4.6 FP-Growth算法Python实现

     根据算法实现步骤,不调用模块实现Fp-growth算法参考代码:

    # -*- coding: utf-8 -*-
    
    import operator
    class treeNode:
        def __init__(self,nameValue,numOccur,parentNode):
            self.name=nameValue #节点名
            self.count=numOccur #节点元素出现次数
            self.nodeLink=None #存放节点链表中,与该节点相连的下一个元素
            self.parent=parentNode
            self.children={} #用于存放节点的子节点,value为子节点名
        
        def inc(self,numOccur):
            self.count+=numOccur
        
        def disp(self,ind=1):
            print("   "*ind,self.name,self.count) #输出一行节点名和节点元素数,缩进表示该行节点所处树的深度
            for child in self.children.values():
                child.disp(ind+1) #对于子节点,深度+1
    
    # 构造FP树
    # dataSet为字典类型,表示探索频繁项集的数据集,keys为各项集,values为各项集在数据集中出现的次数
    # minSup为最小支持度,构造FP树的第一步是计算数据集各元素的支持度,选择满足最小支持度的元素进入下一步
    def createTree(dataSet,minSup=1):
        headerTable={}
    
        #遍历各项集,统计数据集中各元素的出现次数
        for key in dataSet.keys():
            for item in key:
                headerTable[item]=headerTable.get(item,0)+dataSet[key] 
                
        #遍历各元素,删除不满足最小支持度的元素
        for key in list(headerTable.keys()):
            if headerTable[key]<minSup:
                del headerTable[key]
        freqItemSet=set(headerTable.keys())
        
        #若没有元素满足最小支持度要求,返回None,结束函数
        if len(freqItemSet)==0:
            return None,None
        for key in headerTable.keys():
            headerTable[key]=[headerTable[key],None] #[元素出现次数,**指向每种项集第一个元素项的指针**]
        retTree=treeNode("Null Set",1,None) #初始化FP树的顶端节点
        
        for tranSet,count in dataSet.items():
            localD={} #存放每次循环中的频繁元素及其出现次数,便于利用全局出现次数对各项集元素进行项集内排序
            for item in tranSet:
                if item in freqItemSet:
                    localD[item]=headerTable[item][0]
            if len(localD)>0:
                orderedItems=[v[0] for v in sorted(localD.items(),key=operator.itemgetter(1),reverse=True)] #根据元素全局出现次数对每个项集(tranSet)中的元素进行排序
                updateTree(orderedItems,retTree,headerTable,count) #使用排序后的项集对树进行填充
        return retTree,headerTable
    
    
    #树的更新函数
    #items为按出现次数排序后的项集,是待更新到树中的项集;count为items项集在数据集中的出现次数
    #inTree为待被更新的树;headTable为头指针表,存放满足最小支持度要求的所有元素
    def updateTree(items,inTree,headerTable,count):
        #若项集items当前最频繁的元素在已有树的子节点中,则直接增加树子节点的计数值,增加值为items[0]的出现次数
        if items[0] in inTree.children: 
            inTree.children[items[0]].inc(count)
        else:#若项集items当前最频繁的元素不在已有树的子节点中(即,树分支不存在),则通过treeNode类新增一个子节点
            inTree.children[items[0]]=treeNode(items[0],count,inTree)
            #若新增节点后表头表中没有此元素,则将该新增节点作为表头元素加入表头表
            if headerTable[items[0]][1]==None: 
                headerTable[items[0]][1]=inTree.children[items[0]]
            else:#若新增节点后表头表中有此元素,则更新该元素的链表,即,在该元素链表末尾增加该元素
                updateHeader(headerTable[items[0]][1],inTree.children[items[0]])
        #对于项集items元素个数多于1的情况,对剩下的元素迭代updateTree
        if len(items)>1:
            updateTree(items[1::],inTree.children[items[0]],headerTable,count)
    
    
    #元素链表更新函数
    #nodeToTest为待被更新的元素链表的头部
    #targetNode为待加入到元素链表的元素节点
    def updateHeader(nodeToTest,targetNode):
        #若待被更新的元素链表当前元素的下一个元素不为空,则一直迭代寻找该元素链表的末位元素
        while nodeToTest.nodeLink!=None: 
            nodeToTest=nodeToTest.nodeLink #类似撸绳子,从首位一个一个逐渐撸到末位
        #找到该元素链表的末尾元素后,在此元素后追加targetNode为该元素链表的新末尾元素
        nodeToTest.nodeLink=targetNode
    #加载简单数据集
    def loadSimpDat():
        simpDat = [['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']]
        return simpDat
    
    #将列表格式的数据集转化为字典格式
    def createInitSet(dataSet):
        retDict={}
        for trans in dataSet:
            retDict[frozenset(trans)]=1
        return retDict
    
    #由叶节点回溯该叶节点所在的整条路径
    #leafNode为叶节点,treeNode格式;prefixPath为该叶节点的前缀路径集合,列表格式,在调用该函数前注意prefixPath的已有内容
    def ascendTree(leafNode,prefixPath):
        if leafNode.parent!=None:
            prefixPath.append(leafNode.name)
            ascendTree(leafNode.parent,prefixPath)
            
    #获得指定元素的条件模式基
    #basePat为指定元素;treeNode为指定元素链表的第一个元素节点,如指定"r"元素,则treeNode为r元素链表的第一个r节点
    def findPrefixPath(basePat,treeNode):
        condPats={} #存放指定元素的条件模式基
        while treeNode!=None: #当元素链表指向的节点不为空时(即,尚未遍历完指定元素的链表时)
            prefixPath=[]
            ascendTree(treeNode,prefixPath) #回溯该元素当前节点的前缀路径
            if len(prefixPath)>1:
                condPats[frozenset(prefixPath[1:])]=treeNode.count #构造该元素当前节点的条件模式基
            treeNode=treeNode.nodeLink #指向该元素链表的下一个元素
        return condPats
    
    #有FP树挖掘频繁项集
    #inTree: 构建好的整个数据集的FP树
    #headerTable: FP树的头指针表
    #minSup: 最小支持度,用于构建条件FP树
    #preFix: 新增频繁项集的缓存表,set([])格式
    #freqItemList: 频繁项集集合,list格式
    
    def mineTree(inTree,headerTable,minSup,preFix,freqItemList):
        #按头指针表中元素出现次数升序排序,即,从头指针表底端开始寻找频繁项集
        bigL=[v[0] for v in sorted(headerTable.items(),key=lambda p:p[1][0])] 
        for basePat in bigL:
            #将当前深度的频繁项追加到已有频繁项集中,然后将此频繁项集追加到频繁项集列表中
            newFreqSet=preFix.copy()
            newFreqSet.add(basePat)
            print("freqItemList add newFreqSet",newFreqSet)
            freqItemList.append(newFreqSet)
            #获取当前频繁项的条件模式基
            condPatBases=findPrefixPath(basePat,headerTable[basePat][1])
            #利用当前频繁项的条件模式基构建条件FP树
            myCondTree,myHead=createTree(condPatBases,minSup)
            #迭代,直到当前频繁项的条件FP树为空
            if myHead!=None:
                mineTree(myCondTree,myHead,minSup,newFreqSet,freqItemList)
    
    simpDat=loadSimpDat()
    dataSet=createInitSet(simpDat)
    myFPtree1,myHeaderTab1=createTree(dataSet,minSup=3)
    myFPtree1.disp(),myHeaderTab1
    freqItems=[]
    mineTree(myFPtree1,myHeaderTab1,3,set([]),freqItems)
    freqItems

     5 压缩频繁项集

     5.1 真超集与真子集

            如果一个集合S2中的每个元素都在集合S1中,且集合S1中可能包含S2中没有的元素,则集合S1就是S2的一个超集,反过来,S2是S1的子集。 S1是S2的超集,若S1中一定有S2中没有的元素,则S1是S2的真超集,反过来S2是S1的真子集

    5.2 频繁闭项集

            如果在数据集中不存在频繁项集X的真超项集Y,使得X、Y的支持度相等,那么称项集X是这个数据集的频繁闭项集

    5.3极大(最大)频繁项集

            如果在数据集中不存在频繁项集X的真超项集Y,使得X属于 Y并且Y也是频繁项集,那么称项集X是这个数据集的极大(最大)频繁项集

            可以推导出极大频繁项集是闭频繁项集,而闭频繁项集不一定是极大频繁项集。

    6关联模式评

    6.1支持度与置信度

            支持度用于筛选出频繁项集,但是该度量有一个缺点,一些支持度较低、但让人感兴趣的模式会被忽略掉,模式毕竟是只出现在部分数据中的,因此使用支持度度量可能会出现这种情况。

            置信度用于评估规则的可信程度,但是该度量有一个缺点,没有考虑规则后件的支持度问题。

    6.2相关性分析

     

    5.3模式评估度量

     

     

    【参考资料】

    [1]Apriori | 挖掘关联规则

    [2]FP-Growth|高效挖掘频繁项集

    [3]FP Tree算法原理总结

    [4]Apriori算法原理总结

    [5]天津大学公开课:数据分析与数据挖掘

    展开全文
  • 因此,为有效检测Android平台未知的恶意应用,提出了一种基于权限频繁模式挖掘算法的Android恶意应用检测方法,设计了能够挖掘权限之间关联性的权限频繁模式挖掘算法—PApriori。基于该算法对49个恶意应用家族进行...
  • 巩固频繁模式挖掘的基本算法原理及特点,设计程序,基于不同特征的数据集比较不同方法的优缺点,并基于算法原理和特点分析造成这种现象的原因。 二、算法原理 1 Apriori 对于Apriori算法,通过限制候选产生发现...

    注:参考多篇CSDN文章所得

    一、实验内容

    巩固频繁模式挖掘的基本算法原理及特点,设计程序,基于不同特征的数据集比较不同方法的优缺点,并基于算法原理和特点分析造成这种现象的原因。

    二、算法原理

    1 Apriori

    对于Apriori算法,通过限制候选产生发现频繁项集,使用支持度来作为判断频繁项集的标准。Apriori算法的目标是找到最大的K项频繁集。这里有两层意思,首先,我们要找到符合支持度标准的频繁集。但是这样的频繁集可能有很多。第二层意思就是我们要找到最大个数的频繁集。比如我们找到符合支持度的频繁集AB和ABE,那么我们会抛弃AB,只保留ABE,因为AB是2项频繁集,而ABE是3项频繁集。

    Apriori算法采用了迭代的方法,先搜索出候选1项集及对应的支持度,剪枝去掉低于支持度的1项集,得到频繁1项集。然后对剩下的频繁1项集进行连接,得到候选的频繁2项集,筛选去掉低于支持度的候选频繁2项集,得到真正的频繁二项集,以此类推,迭代下去,直到无法找到频繁k+1项集为止,对应的频繁k项集的集合即为算法的输出结果。

    2.FP-growth

    FP-growth算法是基于Apriori原理的,通过将数据集存储在FP(Frequent Pattern)树上发现频繁项集,但不能发现数据之间的关联规则。FP-growth是一种以自底向上方式探索树,由FP树产生频繁项集的算法,通过模式增长挖掘频繁模式。给定上面构建的FP树,算法首先查找以e结尾的频繁项集,接下来是b,c,d,最后是a,由于每一个事务都映射到FP树中的一条路径,因为通过仅考察包含特定节点(例如e)的路径,就可以发现以e结尾的频繁项集,使用与节点e相关联的指针,可以快速访问这些路径。

    算法发现频繁项集的过程是:(1)构建FP树;(2)从FP树中挖掘频繁项集。

    FPGrowth算法的主要思想:1. 构造频繁1项集:遍历初始数据集构造频繁1项集,并作为项头表,建立将指向fpTree节点对应元素的引用 2. 构造FPTree:再次遍历初始数据集,对于每一条事务中的元素,根据频繁1项集中元素的顺序排序, 由此建立FPTree,记录每条事务的节点在同一条路径上出再的节点次数;  3. 逆序遍历在步骤1中构造的项头表,根据其提供的引用指针,找出fpTree中由该节点到根节点的路径, 即生成每个频繁元素的条件模式基 4.根据每个频繁元素对应的条件模式基,生成其对应的条件fpTree,并删除树中节点记数不满足给定的最小支持度的节点  5.对于每一颗条件fpTree,生成所有的从根节点到叶子节点的路径,由路径中的集合生成其所有非空子集 ,所有这些非空子集和每一个频繁1项集中的元素共同构成了原始数据集中的频繁集。

    3.Eclat

    Eclat算法使用垂直格式挖掘频繁项集。其过程为:(1)通过扫描一次数据集,把水平格式的数据转换成垂直格式;(2)项集的支持度计数简单地等于项集的TID集的长度;(3)从k=1开始,可以根据先验性质,使用频繁k项集来构造候选(k+1)项集;(4)通过取频繁k项集的TID集的交,计算对应的(k+1)项集的TID集。(5)重复该过程,每次k增加1,直到不能再找到频繁项集或候选项集。Eclat算法加入了倒排的思想,具体就是将事务数据中的项作为key,每个项对应的事务ID作为value。只需对数据进行一次扫描,算法的运行效率会很高。

    主要步骤:将数据倒排{ item:TID_set },然后通过求频繁k项集的交集来获取k+1项集。特点:仅需要一次扫描数据库,TID集合很长的话需要消耗大量的内存和计算时间。

    4.不同算法的特点

    Apriori算法:需要多次扫描数据库,对于大规模数据效率很低。

    FPGrowth算法:两次扫描数据库,采用分治的策略有效降低了搜索开销。

    Eclat算法:仅需要一次扫描数据库,如果TID集合很长,需要消耗大量的内存和计算时间。


    三、算法代码实现

    1.Apriori

    def init_c1(data_set_dict, min_support):
        c1 = []
        freq_dic = {}
        for trans in data_set_dict:
            for item in trans:
                freq_dic[item] = freq_dic.get(item, 0) + data_set_dict[trans]
        # 优化初始的集合,使不满足最小支持度的直接排除
        c1 = [[k] for (k, v) in freq_dic.iteritems() if v >= min_support]
        c1.sort()
        return map(frozenset, c1)
    
    def scan_data(data_set, ck, min_support, freq_items):
        """
        计算Ck中的项在数据集合中的支持度,剪枝过程
        :param data_set:
        :param ck:
        :param min_support: 最小支持度
        :param freq_items: 存储满足支持度的频繁项集
        :return:
        """
        ss_cnt = {}
        # 每次遍历全体数据集
        for trans in data_set:
            for item in ck:
                # 对每一个候选项集, 检查是否是 term中的一部分(子集),即候选项能否得到支持
                if item.issubset(trans):
                    ss_cnt[item] = ss_cnt.get(item, 0) + 1
        ret_list = []
        for key in ss_cnt:
            support = ss_cnt[key]  # 每个项的支持度
            if support >= min_support:
                ret_list.insert(0, key)  # 将满足最小支持度的项存入集合
                freq_items[key] = support  #
        return ret_list
    
    
    def apriori_gen(lk, k):
        """
        由Lk的频繁项集生成新的候选项集  连接过程
        :param lk:  频繁项集集合
        :param k:  k 表示集合中所含的元素个数
        :return: 候选项集集合
        """
        ret_list = []
        for i in range(len(lk)):
            for j in range(i+1, len(lk)):
                l1 = list(lk[i])[:k-2]
                l2 = list(lk[j])[:k-2]
                l1.sort()
                l2.sort()
                if l1 == l2:
                    ret_list.append(lk[i] | lk[j])  # 求并集
        # retList.sort()
        return ret_list
    
    def apriori_zc(data_set, data_set_dict, min_support=5):
        """
        Apriori算法过程
        :param data_set: 数据集
        :param min_support: 最小支持度,默认值 0.5
        :return:
        """
        c1 = init_c1(data_set_dict, min_support)
        data = map(set, data_set)  # 将dataSet集合化,以满足scanD的格式要求
        freq_items = {}
        l1 = scan_data(data, c1, min_support, freq_items)  # 构建初始的频繁项集
        l = [l1]
        # 最初的L1中的每个项集含有一个元素,新生成的项集应该含有2个元素,所以 k=2
        k = 2
        while len(l[k - 2]) > 0:
            ck = apriori_gen(l[k - 2], k)
            lk = scan_data(data, ck, min_support, freq_items)
            l.append(lk)
            k += 1  # 新生成的项集中的元素个数应不断增加
        return freq_items

    2.FP-growth

    def create_tree(data_set, min_support=1):
        """
        创建FP树
        :param data_set: 数据集
        :param min_support: 最小支持度
        :return:
        """
        freq_items = {}  # 频繁项集
        for trans in data_set:  # 第一次遍历数据集
            for item in trans:
                freq_items[item] = freq_items.get(item, 0) + data_set[trans]
    
        header_table = {k: v for (k, v) in freq_items.iteritems() if v >= min_support}  # 创建头指针表
        # for key in header_table:
        #     print key, header_table[key]
    
        # 无频繁项集
        if len(header_table) == 0:
            return None, None
        for k in header_table:
            header_table[k] = [header_table[k], None]  # 添加头指针表指向树中的数据
        # 创建树过程
        ret_tree = treeNode('Null Set', 1, None)  # 根节点
    
        # 第二次遍历数据集
        for trans, count in data_set.items():
            local_data = {}
            for item in trans:
                if header_table.get(item, 0):
                    local_data[item] = header_table[item][0]
            if len(local_data) > 0:
                ##############################################################################################
                # 这里修改机器学习实战中的排序代码:
                ordered_items = [v[0] for v in sorted(local_data.items(), key=lambda kv: (-kv[1], kv[0]))]
                ##############################################################################################
                update_tree(ordered_items, ret_tree, header_table, count)  # populate tree with ordered freq itemset
        return ret_tree, header_table
    
    def update_tree(items, in_tree, header_table, count):
        '''
        :param items: 元素项
        :param in_tree: 检查当前节点
        :param header_table:
        :param count:
        :return:
        '''
        if items[0] in in_tree.children:  # check if ordered_items[0] in ret_tree.children
            in_tree.children[items[0]].increase(count)  # incrament count
        else:  # add items[0] to in_tree.children
            in_tree.children[items[0]] = treeNode(items[0], count, in_tree)
            if header_table[items[0]][1] is None:  # update header table
                header_table[items[0]][1] = in_tree.children[items[0]]
            else:
                update_header(header_table[items[0]][1], in_tree.children[items[0]])
        if len(items) > 1:  # call update_tree() with remaining ordered items
            update_tree(items[1::], in_tree.children[items[0]], header_table, count)
    
    def update_header(node_test, target_node):
        '''
        :param node_test:
        :param target_node:
        :return:
        '''
        while node_test.node_link is not None:  # Do not use recursion to traverse a linked list!
            node_test = node_test.node_link
        node_test.node_link = target_node
    
    def ascend_tree(leaf_node, pre_fix_path):
        '''
        遍历父节点,找到路径
        :param leaf_node:
        :param pre_fix_path:
        :return:
        '''
        if leaf_node.parent is not None:
            pre_fix_path.append(leaf_node.name)
            ascend_tree(leaf_node.parent, pre_fix_path)
    
    def find_pre_fix_path(base_pat, tree_node):
        '''
        创建前缀路径
        :param base_pat: 频繁项
        :param treeNode: FP树中对应的第一个节点
        :return:
        '''
        # 条件模式基
        cond_pats = {}
        while tree_node is not None:
            pre_fix_path = []
            ascend_tree(tree_node, pre_fix_path)
            if len(pre_fix_path) > 1:
                cond_pats[frozenset(pre_fix_path[1:])] = tree_node.count
            tree_node = tree_node.node_link
        return cond_pats
    
    def mine_tree(in_tree, header_table, min_support, pre_fix, freq_items):
        '''
        挖掘频繁项集
        :param in_tree:
        :param header_table:
        :param min_support:
        :param pre_fix:
        :param freq_items:
        :return:
        '''
        # 从小到大排列table中的元素,为遍历寻找频繁集合使用
        bigL = [v[0] for v in sorted(header_table.items(), key=lambda p: p[1])]  # (sort header table)
        for base_pat in bigL:  # start from bottom of header table
            new_freq_set = pre_fix.copy()
            new_freq_set.add(base_pat)
            # print 'finalFrequent Item: ',new_freq_set    #append to set
            if len(new_freq_set) > 0:
                freq_items[frozenset(new_freq_set)] = header_table[base_pat][0]
            cond_patt_bases = find_pre_fix_path(base_pat, header_table[base_pat][1])
            my_cond_tree, my_head = create_tree(cond_patt_bases, min_support)
            # print 'head from conditional tree: ', my_head
            if my_head is not None:  # 3. mine cond. FP-tree
                # print 'conditional tree for: ',new_freq_set
                # my_cond_tree.disp(1)
                mine_tree(my_cond_tree, my_head, min_support, new_freq_set, freq_items)
    
    
    def fp_growth(data_set, min_support=1):
        my_fp_tree, my_header_tab = create_tree(data_set, min_support)
        # my_fp_tree.disp()
        freq_items = {}
        mine_tree(my_fp_tree, my_header_tab, min_support, set([]), freq_items)
        return freq_items

    3.​​​​​Eclat

    import sys
    import time
    type = sys.getfilesystemencoding()
    
    
    def eclat(prefix, items, min_support, freq_items):
        while items:
            # 初始遍历单个的元素是否是频繁
            key, item = items.pop()
            key_support = len(item)
            if key_support >= min_support:
                # print frozenset(sorted(prefix+[key]))
                freq_items[frozenset(sorted(prefix+[key]))] = key_support
                suffix = []  # 存储当前长度的项集
                for other_key, other_item in items:
                    new_item = item & other_item  # 求和其他集合求交集
                    if len(new_item) >= min_support:
                        suffix.append((other_key, new_item))
                eclat(prefix+[key], sorted(suffix, key=lambda item: len(item[1]), reverse=True), min_support, freq_items)
        return freq_items
    
    
    def eclat_zc(data_set, min_support=1):
        """
        Eclat方法
        :param data_set:
        :param min_support:
        :return:
        """
        # 将数据倒排
        data = {}
        trans_num = 0
        for trans in data_set:
            trans_num += 1
            for item in trans:
                if item not in data:
                    data[item] = set()
                data[item].add(trans_num)
        freq_items = {}
        freq_items = eclat([], sorted(data.items(), key=lambda item: len(item[1]), reverse=True), min_support, freq_items)
        return freq_items

    四、不同规模、最小支持度以及方法对结果的影响及适用性

    1.不同规模大小数据对各方法结果影响

    1)数据集:unxiData8     规模:900-1500

     

    2)数据集:kosarakt    规模:6000-10000

     

    结论:一般情况下,数据规模越大,Apriori算法效率越低。因为该算法需要多次扫描数据库,数据量越大,扫描数据库带来的消耗越多。

    2.最小支持度大小对各方法结果的影响

    1)数据集:unixData8    支持度:4% - 20%

     

    2)数据集:kosarakt    支持度:1% - 2%

     

    结论:

    1)最小支持度越小,各个算法所花费的时间越多,且Apriori算法效率最差;Apriori算法候选项集较多,扫描数据库次数较多;FP-Growth算法FP树较茂盛,求解模式更多;Eclat算法求交集次数较多

    2)随着最小支持度的增加,各个算法的效率逐渐接近,相当于数据量较小的情况。

    3.不同方法对长事务数据的适用性分析

    数据集:movieItem          DataSize = 943

    结论:对于长事物的数据集来说

    1)最小支持度较大时,生成的FP树深度较大,求解的子问题较多,FP算法性能显著下降,适用性降低;

    2)最小支持度较小时,Apriori算法生成大量候选项,扫描数据库次数显著增加,Apriori算法性能显著下降,适用性降低

     

    五、实验总结及结果讨论分析

    1、Apriori算法的效率最低,因为其需要很多次的扫描数据库;

    2、FP—Growth算法在长事物数据上表现很差,因为当事物很长时,树的深度也很大,需要求解的子问题就变得特别多,因此效率会迅速下降;

    3、Eclat算法的效率最高,但是由于我们事先使用了递归的思想,当数据量很大的时候会给系统带来巨大的负担,因此不适合数据量很大的情况

     

    展开全文
  • 基于Apriori、FP-Growth及Eclat算法的频繁模式挖掘源程序 一、DataMiningApriori程序 用eclipse打开,把三个测试数据mushroom、accidents和T10I4D100K放置 在F:\DataMiningSample\FPmining文件夹下面,即可运行 二、...
  • 提出维吾尔文组词的新概念,将数据挖掘中的频繁模式挖掘方法引入到维吾尔文组词中,再结合维吾尔文的语言文字特点,将无先验知识的模式挖掘问题转化为特定模式的匹配问题,提出了一种快速高效的频繁模式挖掘算法,来获取...
  • 提出一种自适应的频繁模式挖掘算法: AD2M ine 算法. 该算法采用超结构, 根据计算机可用内存自动确定一 次性产生超结构的大小, 能够自动适应各类不同特性的数据, 进行高效率的频繁模式挖掘工作. 同时提出了一种...
  • 频繁模式挖掘是数据挖掘的一个基本问题,其模式本身和相应计数都有可能泄露隐私信息。当前,差分隐私通过添加噪音使数据失真,有效实现了隐私保护的目的。首先介绍了差分隐私保护模型的理论基础;其次,详细综述了差...
  • python频繁模式挖掘完整代码以及结果图片
  • 频繁模式挖掘-FP-Growth

    2021-02-24 16:49:29
    FP-Growth是频繁模式挖掘的一种算法,由韩家炜等在2000年提出,算法通过建立一棵频繁项集树来实现频繁项集的搜索,同时能实现事务的压缩,相比Apriori能减少数据的扫描次数。 算法逻辑 1、扫描数据,统计项目...

    目录

    算法简介

    算法逻辑

    案例

    Spark程序实现例子(Java语言)


     

    算法简介

    FP-Growth是频繁模式挖掘的一种算法,由韩家炜等在2000年提出,算法通过建立一棵频繁项集树来实现频繁项集的搜索,同时能实现事务的压缩,相比Apriori能减少数据的扫描次数。

    算法逻辑

    1、扫描数据,统计项目(item)在数据集中出现的频数,例如苹果出现(被购买)了4次、牛奶出现(被购买)了5次等

    2、再次扫描数据,构建频繁树(FP-Tree),并生成头表。将每条事物中的项目按照步骤1中的频数由高到底排列后,依次放到树中,并用头表记录每个项目在树中的位置

    3、依据头表和支持度,在频繁树种搜索频繁项集

    案例

    数据:

    交易ID(TID)item(项)
    1苹果,牛奶,香蕉
    2苹果,烤串
    3牛奶,香蕉,啤酒
    4牛奶,啤酒
    5香蕉,啤酒,尿布
    6香蕉
    7苹果,牛奶,香蕉,啤酒,尿布,烤串
    8香蕉
    9牛奶
    10啤酒

    1、扫描数据,统计项目的频数,按照频数由大到小排序结果如下:

    item(项)频数
    香蕉6
    牛奶5
    啤酒5
    苹果3
    烤串2
    尿布2

    2、再次扫描数据,构建频繁树(FP-Tree),并生成头表。构建FP-Tree时首先建立根节点root(或者叫NULL),根节点不保存数据

    TID=1:苹果,牛奶,香蕉

    根据频数对事务中的项目进行排序,得到:香蕉,牛奶,苹果

    根据排序后的事务创建FP-Tree:根据频数倒序生成,香蕉紧跟在root节点后面,然后是牛奶在香蕉后面,苹果在牛奶后面,并在节点上记录项目的频数,生成头表指向各节点,如下图:

    TID=2:苹果,烤串

    根据频数对事务种项目进行排序,得到:苹果,烤串

    插入到FP-Tree中,因root节点只有一个香蕉节点,没有苹果节点,因此root下面新增一个苹果节点;苹果节点之间增加指针,增加烤串指针

    TID=3:牛奶,香蕉,啤酒

    根据频数对事务种项目进行排序,得到:香蕉,牛奶,啤酒

    插入到FP-Tree中,相同节点上的频数相加,如下图黑色文字部分

    TID=4:牛奶,啤酒

    根据频数对事务种项目进行排序,得到:牛奶,啤酒

    插入到FP-Tree中,从root节点下面新增“牛奶”节点,建立啤酒之间的指针,如下图黑色文字部分

     

    TID=5:香蕉,啤酒,尿布

    根据频数对事务种项目进行排序,得到:香蕉,啤酒,尿布

    插入到FP-Tree中,如下图黑色文字部分

    TID=6:香蕉

    插入到FP-Tree中,香蕉节点的频数由3增加到4,如下图黑色文字部分

    TID=7:苹果,牛奶,香蕉,啤酒,尿布,烤串

    根据频数对事务种项目进行排序,得到:香蕉,牛奶,啤酒,苹果,烤串,尿布

    插入到FP-Tree中,如下图黑色文字部分

     

    TID=8:香蕉

    插入到FP-Tree中,如下图黑色文字部分

     

    TID=9:牛奶

    插入到FP-Tree中,如下图黑色文字部分

    TID=10:啤酒

    插入到FP-Tree中,如下图黑色文字部分。完整的FP-Tree如下图,从root开始生长的一棵频繁树,除root节点外,每个节点存储一个item(项目),以及item(项目)在事务数据中的频数,以及指向相同项目其他节点的指针;还有一张存储节点指针的头表。

    3、挖掘频繁模式

    从头表底部开始,由下到上挖掘频繁模式,最底部是尿布,在频繁树中,有两条路径:(香蕉6-牛奶3-啤酒2-苹果1-烤串1-尿布1)、(香蕉6-啤酒1-尿布1);

    假如最小支持度设为2,即项目或项目组合大于等于2才算是频繁项,则以上两条路径被裁剪为(香蕉6-啤酒2-尿布1)、(香蕉6-啤酒1-尿布1)。苹果、烤串和尿布组合的数量只有1 ,不满足最小支持度,因此被裁剪掉;建立如下子树:

    根据子树,得到频繁项集:以“尿布”结尾的频繁项集有:(尿布)(尿布,啤酒)(尿布,香蕉)(尿布,啤酒,香蕉)

    然后根据指针的头表,继续向上挖掘以“烤串”、“苹果”,“啤酒”,“牛奶”,“香蕉”结尾的频繁项集
     

     

    Spark程序实现例子(Java语言)

    Spark中实现了FP-Growth算法,官方例子点这里,下面是代码

    
    public class JavaFPGrowthExample {
      public static void main(String[] args) {
        //创建SparkSession
        SparkSession spark = SparkSession
          .builder()
          .appName("JavaFPGrowthExample")
          .master("local")
          .getOrCreate();
    
        // 创建List数据
        List<Row> data = Arrays.asList(
          RowFactory.create(Arrays.asList("1 2 5".split(" "))),
          RowFactory.create(Arrays.asList("1 2 3 5".split(" "))),
          RowFactory.create(Arrays.asList("1 2".split(" ")))
        );
        StructType schema = new StructType(new StructField[]{ new StructField(
          "items", new ArrayType(DataTypes.StringType, true), false, Metadata.empty())
        });
        // 创建DataFrame
        Dataset<Row> itemsDF = spark.createDataFrame(data, schema);
        // 显示原始数据
        System.out.println("原始数据在同一列里面,这是Spark的规则,数据框如下:");
        itemsDF.show(false);
    
        // 创建FPGrowth实例
        FPGrowthModel model = new FPGrowth()
          .setItemsCol("items") // 设置输入列,交易数据需要进行拆分后,将项目(item)数据放在同一列中,这是Spark的要求
          .setMinSupport(0.5) // 设置最小支撑度
          .setMinConfidence(0.6) // 设置最小置信度
          .fit(itemsDF);  // 拟合数据,返回一个FPGrowthModel
    
        // 展示频繁项
        System.out.println("频繁项集如下,第一列是项集组合,第二列是频数:");
        model.freqItemsets().show();
    
        // 生成关联规则
        System.out.println("关联规则如下,第一列是前项,第二列是后项,第三列是置信度");
        model.associationRules().show();
    
        //
        System.out.println("得到模型后,可以调用模型的transform方法,对数据集进行预测,得到规则。第一列是项集,第二列是推出的结果");
        model.transform(itemsDF).show();
        System.out.println("例如:1、2组合能够推出5");
        // $example off$
    
        spark.stop();
      }
    }

    执行代码后得到以下结果

     

    原始数据在同一列里面,这是Spark的规则,数据框如下:
    +------------+
    |items       |
    +------------+
    |[1, 2, 5]   |
    |[1, 2, 3, 5]|
    |[1, 2]      |
    +------------+
    
    2021-03-02 17:16:57 WARN [org.apache.spark.mllib.fpm.FPGrowth] - Input data is not cached.
    频繁项集如下,第一列是项集组合,第二列是频数:
    +---------+----+
    |    items|freq|
    +---------+----+
    |      [5]|   2|
    |   [5, 1]|   2|
    |[5, 1, 2]|   2|
    |   [5, 2]|   2|
    |      [1]|   3|
    |   [1, 2]|   3|
    |      [2]|   3|
    +---------+----+
    
    关联规则如下,第一列是前项,第二列是后项,第三列是置信度
    +----------+----------+------------------+
    |antecedent|consequent|        confidence|
    +----------+----------+------------------+
    |    [1, 2]|       [5]|0.6666666666666666|
    |    [5, 1]|       [2]|               1.0|
    |       [2]|       [5]|0.6666666666666666|
    |       [2]|       [1]|               1.0|
    |       [5]|       [1]|               1.0|
    |       [5]|       [2]|               1.0|
    |       [1]|       [5]|0.6666666666666666|
    |       [1]|       [2]|               1.0|
    |    [5, 2]|       [1]|               1.0|
    +----------+----------+------------------+
    
    得到模型后,可以调用模型的transform方法,对数据集进行预测,得到规则。第一列是项集,第二列是推出的结果
    +------------+----------+
    |       items|prediction|
    +------------+----------+
    |   [1, 2, 5]|        []|
    |[1, 2, 3, 5]|        []|
    |      [1, 2]|       [5]|
    +------------+----------+
    
    例如:1、2组合能够推出5
    

     

     

     

     

    展开全文
  • 针对当前频繁模式挖掘算法效率不高的问题,结合Apriori和FP-growth算法,提出一种基于事务映射区间求交的频繁模式挖掘算法(interval interaction and transaction mapping,IITM)。只需扫描数据集两次来生成FP树,...
  • 基于最大频繁模式挖掘算法进行书目推荐系统的设计与实现
  • FP-Growth频繁模式挖掘

    2015-01-30 11:06:52
    用Python实现了FP-Growth频繁模式挖掘,文件中包含完整程序和测试数据。之前我还以为代码量相对较大,最后写完了发现只有一百多行,所以理解起来也相对容易
  • 为提高不确定数据集上频繁模式挖掘的效率,针对已有算法在判断是否需要为头表中的某项创建子头表时的计算量比较大的问题,给出一个近似挖掘策略AAT-Mine,以损失小部分频繁项集为代价,提高整个算法的挖掘效率。...
  • 频繁模式挖掘过程中能够动态改变约束的算法比较少。提出了一种基于约束的频繁模式挖掘算法 MCFP。 MCFP首先按照约束的性质来建立频繁模式树,并且只需扫描一遍数据库,然后建立每个项的条件树,挖掘以该项为 前缀的...
  • 针对经典频繁模式挖掘算法存在的不足,提出了一种基于复合粒度计算的频繁模式挖掘算法。该算法借助复合粒度计算方法双向搜索频繁模式,即首先通过二进制的按位取反运算获得复合粒度内涵的像,然后构建复合粒度计算...
  • 什么是频繁模式(Frequent Pattern )分析? 频繁模式:在数据集中频繁出现的模式(项集,子序列,子结构等) 项目集:牛奶和面包经常一起出现 子序列:购买PC,然后购买数码相机 子结构:大图中的频繁子图 在频繁项...
  • 位置不确定移动时空轨迹频繁模式挖掘
  • 数据流的无限性、高速性使得经典的频繁模式挖掘方法难以适用到数据流中。针对数据流的特点,对数据流中频繁模式挖掘问题进行了研究,提出了数据流频繁模式挖掘算法FP-SegCount。该算法将数据流分段并利用改进的FP-...
  • 各种频繁模式挖掘算法,有CloSpan,PrefixSpan,BIDE,MaxSP等

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,239
精华内容 8,895
关键字:

频繁模式挖掘

友情链接: VectorControl.zip