精华内容
下载资源
问答
  • 提出一种分布式全局最大频繁项集挖掘算法(DMFI),该算法含局部挖掘与全局挖掘2个阶段。提出一个基于FP-tree的改进频繁模式树(IFP-tree)来存储数据信息。在局部挖掘阶段,先在各站点上分别建立该模式树,并使用有序方式...
  • 满足差分隐私的频繁项集挖掘算法的设计与实现,李正义,双锴,本文专注于提出一种满足差分隐私的频繁项集挖掘算法,在提供高数据可用性的同时提供高强度的隐私保护。由于数据库中可能存在长度
  • 虽然已有的最大频繁项集挖掘算法在结构和技术上已经做了很多改进,但还是存在挖掘速度慢、效率低的缺点,在此提出了图的四叉链表存储结构和基于该存储结构的最大频繁项集挖掘算法,该结构具有一次生成多次使用,不必...
  • Apriori 采用广度优先的搜索方式,缩小搜索空间用到了一个称为apriori的性质,其性质为:频繁项集的所有非空子集必然也是频繁的。这是很显然的,比如 同时包含项AB的记录条数肯定比只包含A的记录少。这条性质反过来...

    **

    Apriori算法

    **
    Apriori 采用广度优先的搜索方式,缩小搜索空间用到了一个称为apriori的性质,其性质为:频繁项集的所有非空子集必然也是频繁的。这是很显然的,比如 同时包含项AB的记录条数肯定比只包含A的记录少。这条性质反过来也可以这么说:如果一个项集是非频繁的,那么它的超集必然也是非频繁的

    算法过程如下:

    输入:数据集D,支持度minsup
    
     输出:满足支持度的所有项集的集合L
    
     L1 = 发现1-项集(D); 
    
     for (k=2;Lk-1 ≠Φ ;k++) {
    
          Ck = 连接剪枝生成(Lk-1, minsup)
    
          扫描D,为Ck中每个项集c 统计 c.count
    
          保留Lk ={c ∈ Ck|c.count≥min_sup}
    
          L = L ∪ Lk  
    
     }
    
     Return L
    
    

    其中算法精华在于 连接剪枝生成(Lk-1, minsup) 这一步, 包含连接步和剪枝步两个动作:

    1. **连接步:**长度k-1的项连接成长度k的项;具体就是对两个k-1长的项L1和L2,必须满足前k-2个项都相同才能连接,最后把L1和L2剩下的最后一项加起来,形成k的长度的项。

    2. **剪枝步:**k项连接完成后,检查其所有k-1子集是否是频繁的,如果是,才保留作为候选项。

    可以通过一张截图来演示一下apriori的过程:
    在这里插入图片描述
    对应第一张图,连接步是从第k层的项集,向下扩展一层的候选项集,剪枝步能够通过apriori性质过滤掉那些肯定非频繁的项集。

    Apriori的框架其实很小,但是可以想象得到主要的两个步骤: 连接+剪枝(也就是候选集生成),以及,候选集统计是很耗费时间的。

    剪枝步也需要对每个k-候选项集的k-1子集都进行一次检测,也很耗费时间;统计频繁次数是必须的,因此需要扫描数据库,经历I/O。那么有必要剪枝,直接统计会不会更好呢,虽然没有试验过,但我估计还是剪枝以后减少候选集的统计更划算。而这两个耗时的步骤在实现上如果能使用到技巧,对算法时间影响最直接。比如剪枝步中k-1候选项集需要逐一向已有的k-1频繁项集查询,这用什么数据结构最好?又如扫描数据库的时候是否能过进行一些压缩,相同的记录进行合并减少遍历次数,以及过滤掉对统计没用的记录

    **简单的说apriori是先产生一批候选项集,再通过原数据集去过滤非频繁项集:先找A、B、C,检查一下通过了,再找AB、AC、AB,检查又通过了,再到ABC… 这样的广度优先的方式。

    fp-growth

    fp-growth是一个挖掘方式和apriori完全不一样的算法。fp-growth先从数据集中找频繁的项,再从包含这个频繁项的子数据集中找其他的频繁项,把它们俩连起来也肯定是频繁的:先找A,再在找包含A的子数据库里,找到B,就得到AB是频繁,再再包含AB的子数据库里,找到C,ABC就是频繁了。**

    fp-growth采用了一个叫fp-tree 的数据结构去压缩存储数据集,放到内存里,这样以后过问原数据集的事就不必经过IO了。

    Fp-tree主要是一种前缀树,和字典树(trie)接近,并且节点把项的次数也记录下了。字符的顺序有所不同,trie用的是字母表顺序,fp-tree (frequent pattern tree)用的是字母表的频率降序,这样的好处是出现次数多的项作为共享前缀的概率也大,fp-tree的压缩率就高(后面还会提到),根据apriori性质,非频繁的项没用,因此fp-tree上可以没有它们。

    根据前面提到fp-growth步骤,需要找数据库上包含某个项的子数据库,不能从树根开始搜索,因此为了方便,需要把fp-tree中所有枝干、叶子上相同的项全串一起,这样项从一个起点开始,向树根遍历,就能得到包含这个项的子数据库了。这些起点和串起相同节点的链就是fp-tree的另一个部分:头表和兄弟链。头表包含树上所有的单项,并是兄弟链的起点,那么fp-tree不仅完整记录了数据库里所需的信息,还能找到对任一项找到包含了它的子数据库。
    在这里插入图片描述
    有了fp-tree,挖掘频繁项集就变得直观了。首先是压缩数据库,过滤非频繁项,得到一棵fp-tree 1号,对于一个项,比如A,通过兄弟链,遍历树找出 包含A的子树(库),又称A的条件模式树(库),英文原文叫condition pattern tree(base)。然后把这个子库当做一个新的数据库2号,过滤2号库非频繁项,建立一个小点的fp-tree 2号,那么那个A与这个2号树里的所有项,连起来肯定也是频繁的;比如有B,同理把B的条件树找出,也建立个fp-tree 3号,就能得到AB和3号树上的项连起来也肯定是频繁的。这个过程递归完成,建立不出条件子树递归就跳出去。

    算法包含两个部分:

    1. 是建立fp-tree:扫描一遍数据库,得到每个项的支持度,排序并过滤非频繁项;再扫描一次数据库,每条记录按顺序排序,添加到fp-tree上。
    
    2. 调用算法FP_growth(FP-tree, null)。
    
       Function Fp_growth(FP-tree, a){
    
     if(fp-tree 是单条路径){
    
       对路径上的组合b, 都连接a,输出b∪ a 
    
     }else{
    
       For each 项ai in 头表{
    
         输出一个模式b= ai∪ a,其支持度 support =ai.support 
    
         构造b的条件模式库,然后构造b的条件模式树 Treeb; 
    
         If (Treeb 不为空){
    
            调用算法FP_growth(Treeb,b )
      }
     }
     }
    

    FP_growth是个递归算法,期间需要反复遍历树和构建fp-tree。fp-growth中判断单路径部分可以不要,最后实际结果其实是和下面部分是一样的,但是直接计算单路径产生所有组合会便捷很多。另外一点,fp-tree要按支持度降序的顺序的好处有几点?前面说了可以提高共享前缀的可能,提高压缩率,树小了,遍历的步数还能减小,寻找最优压缩的顺序是个NP难问题,因此选这个办法能有个比较好的压缩率足够了。

    fp-growth虽然号称不产生候选集,但是实际上候选集产生已经在寻找条件子库的时候隐隐产生了,剪掉非频繁候选项的时候是通过建树步骤中的第一小步完成的。

    fp-growth在实现上也可以有很多技巧,比如寻找条件子树的时候,同一条路径会被遍历很多次,如何有效避免(后来han自己提出,遇到扫把型的fp-tree,即上面是单路径、下面分叉的,可以把单路径所有的组合分别连接到下面的部分挖掘结果上输出,那就不用遍历上面的单路径了) 另外树上节点用什么数据结构保存指向子孙节点的指针,能同时兼顾查询时间和空间?

    apriori和fp-growth之间的联系和差异

    初读fp-growth算法,估计都感觉不到它和apriori有什么关系,据猜测fp-growth是从apriori的统计候选集太耗时的那里 改良开始的,希望实现候选项集的更快速的计算支持度,最后就彻底的改变的搜索频繁项集的方式。据说,两个算法的最根本的差异在于apriori是以搜索项集组合的空间作为基础,通过数据库来对照。而fp-growth是以数据库为基础,在里面寻找项集是否频繁,表现为搜索方式一个是广度优先一个是深度优先。

    apriori的那剪枝步和统计支持度在fp-growth上就是不断的建fp-tree和遍历。而前者的统计需要经过的IO,后者已经压缩到内存了;但fp-growth不是在所有数据集上都比apriori强,比如在稀疏的数据集上,fp-tree每个节点可能包含非常多子孙,因此保存子孙节点的指针也是很大开销,fp-tree本来就是通过压缩使得数据集能被内存容纳,结果导致最后fp-tree起不到压缩效果适得其反。优化实现的apriori在稀疏数据集上也往往比fp-growth要快。

    这里fp-growth在大部分地方是完胜了apriori,后面很多改进都是基于深度优先的思想,并且更注重实现上的技巧。现在我们也没必要去费太多精力去改进这两个算法了,因为频繁项集挖掘是个组合爆炸的时间复杂度。在2003 2004年ICDM举办过两个workshop就是专门比谁实现的频繁项集挖掘最好(搜"FIMI 03",网站里有很多的源码)。在这里想多提一点,数据挖掘中,没有算法能在所有数据集上PK掉其他算法。因此我们应该了解一种任务的多种算法,看看它们为什么和如何在不同的数据集上体现出自己的优势,这样,通过比较我们不仅能更好的理解和掌握它们的精华,更能在当我们遇到新的数据集的时候,选取合适算法甚至做出针对性的优化措施。

    ————————————————
    版权声明:本文为CSDN博主「相国」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
    原文链接:https://blog.csdn.net/lgnlgn/article/details/7614892

    
    
    展开全文
  • 针对现有的最大频繁项集挖掘算法挖掘时间过长、内存消耗较大的问题,提出了一种基于构造链表B-list的最大频繁项集挖掘算法BMFI。该算法利用B-list数据结构来挖掘频繁项集,并采用全序搜索树作为搜索空间,然后采用...
  • 在硬件结构中建立深度学习挖掘模型,通过传感器、隐层、输入层、输出层、中心处理器、存储器和显示器构成硬件架构,软件流程由发送采集命令、预训练、微调训练、数据检测、判断候选项集是否为频繁项集等步骤组成。...
  • 提出了基于频繁项集的最大频繁项集(BFI-DMFI)和频繁闭项集挖掘算法(BFI-DCFI)。BFI-DMFI算法通过逐个检测频繁项集在其集合中是否存在超集确定该项集是不是最大频繁项集;BFI-DCFI算法则是通过挖掘所有支持度相等...
  • 1993年AGRAWAL R等人提出了一个重要的反映...最大频繁项集中已经隐含了所有的频繁项集,并且在许多数据挖掘应用中也只需要挖掘最大频繁项集,而不是获取所有的频繁项集,因此对最大频繁项集挖掘具有重大的现实意义。
  • 针对基于WN-list 加权频繁项集挖掘算法(NFWI)中挖掘加权频繁项集(FWI)效率低的问题,提出了一种基于WNegNodeset结构的加权频繁项集挖掘算法(NegNFWI)。该算法首先采用了新的数据结构WNegNodeset,它是...
  • 关联规则的研究是数据挖掘中的重要问题,如何高效地发现频繁项集是关联规则研究中的关键问题。根据数据库事务的统计性规律,在最大频繁项集发现算法Apriori及其变种算法的基础上,提出一种新的基于层次的最大频繁项...
  • Apriori算法是解决频繁项集挖掘最常用的算法之一,但多轮迭代扫描完整数据集的计算方式,严重影响算法效率且难以并行化处理。随着数据规模的持续增大,这一问题日益严重。针对这一问题,提出了一种基于项编码和Spark...
  • 提出一个数据流环境下的基于概念格和滑动窗口的频繁项集挖掘算法DSFMCL。算法在滑动窗口内分批挖掘新流入的基本窗口频繁概念后,生成概念格的Hasse图。引入最小支持度ζ和误差因子ε对非频繁概念节点进行剪枝操作。...
  • 为解决在挖掘频繁项集时由忽略项目间重要性差异以及最小支持度频繁变动而导致的挖掘...实验结果表明,WMDT算法较以往算法,精准度和挖掘效率有显著提高同时受最小支持度变动影响较小,是一个高效的频繁项集挖掘算法。
  • 频繁项集和关联规则的挖掘首先需要了解一些概念, 如支持度, 置信度, 事务,事务集,项,项集, 频繁项集等, 首先介绍下基本的概念定义(以下为笔者的简单化理解, 更严谨的定义请参考书中内容): 首先假设我们有一个由多行...

    本文的代码文件原件可以在我们的 "数据臭皮匠" 中输入"第六章1" 拿到

    1.基本概念介绍

    频繁项集和关联规则的挖掘首先需要了解一些概念, 如支持度, 置信度, 事务,事务集,项,项集, 频繁项集等, 首先介绍下基本的概念定义(以下为笔者的简单化理解, 更严谨的定义请参考书中内容):

    首先假设我们有一个由多行多列组成的表格

    事务: 可以将事务简单理解为表格的其中一行

    事务集:一个表格会有多行, 这个包括多个事务的集合就叫事务集

    项:表格中每一行会包括多个值, 每一个值就是一个项

    项集:多个项组成一个集合, 这个由多个项组成的集合就叫项集

    k项集: 包含k个项的项集为k项集 , 如{I1,I2} 为一个2项集

    支持度:假设有A项集, 表格共有N行, 其中包括A项集的有m行, 则绝对支持度为m, 相对支持度为m/N

    置信度:表格中, 包括项集A的行有n1行, 同时包括项集A和B的有n2行, 置信度c = n2/n1

    频度: 表格中有n1行包括项集A, n1即为A的频度

    频繁项集: 如果项集的A的相对支持度满足预设的最小支持度阈值, 则项集A为频繁项集

    规则: 假设有A,B两个项集, 由A出现可以推出B也出现(即A=>B) 这就是一条规则

    强规则: 同时满足最小支持度阈值和最小置信度阈值的规则为强规则

     

    2.闭频繁项集和极大频繁项集定义

    从大型数据集中挖掘频繁项集的主要挑战是: 这种挖掘常常产生大量满足最小支持度阈值的项集, 这是因为如果一个项集是频繁的, 则它的每个子集也是频繁的(回忆下支持度的定义,N行的表格中有m行包括项集A, 则A的相对支持度为m/N)。如果一个包括100个项的项集为频繁项集{a1,a2,...a100} , 则它有100个频繁1项集, C_{100}^{2} =4950个频繁2项集{a1,a2}, {a1,a3}, ...{a99,a100} , 因此, 该100项的频繁项集共可以产生1.23*10^{30}  个频繁项集, 对于任何计算机, 这个项集都太大了, 大到无法计算和存储。

    真超项集:假设X,Y为项集, 如果X是Y的真子项集, 则Y是X的真超项集。(X中每个项都包含在Y中, Y中至少有一个项不包含在X中)

    闭的项集: 对于X项集, 如果表格中不存在与其拥有相同支持度的它的真超项集,则项集X为闭的。

    闭频繁项集:如果项集X是闭的且频繁的, 则项集X为闭频繁项集。

    极大频繁项集:对于频繁项集X,如果表格中不存在它的频繁的超项集, 则X为极大频繁项集

     

    3.Apriori(先验)算法

    Apriori算法使用一种称为逐层搜索的迭代方法, 首先通过扫描数据库,累计每个项的计数,并收集频繁1项集的集合。该集合记为L1,然后使用L1找出频繁2项集的集合L2, 使用L2找出L3, 如此下去,直到不能再找到频繁k项集。

    为了提高频繁项集逐层产生的效率, 一种称为先验性质的重要性质用于压缩搜索空间。

    先验性质:频繁项集的所有非空子集也一定是频繁的,从 L_{k-1}L_{k} 需要两步:连接步剪枝步

    3.1 连接步

    为找出L_{k} ,通过将L_{k-1} 与自身连接产生候选k项集的集合, 该候选k项集的集合记为C_{k} ,假设l_{1}l_{2}L_{k-1} 中的项集,l_{i}\left [ j \right ] 表示项集 l_{i} 的第j 项。首先将L_{k} 中的所有项集l_{i} 排序,使得l_{i}\left [ 1 \right ] < l_{i}\left [ 2 \right ] <...< l_{i}\left [ k-1 \right ] , 然后执行连接L_{k-1} \timesL_{k-1}L_{k-1} 中的项集互相连接, 如果l_{i} 和 l_{j} 的前k-2项都是相同的, 则两者是可以连接的,连接的结果为 \left \{ l_{i}\left [ 1 \right ],l_{i}\left [ 2 \right ],...,l_{i}\left [ k-1 \right ],l_{j}\left [ k-1 \right ] \right \}

    该连接过程需要将L_{k-1} 中的元素两两连接, 执行完一遍

     

    3.2 剪枝步

    由连接步得到C_{k} 后, 可以扫描数据库, 计算其中每个候选k项集的计数, 从而确定L_{k} ,但 C_{k} 可能很大, 在遍历它之前可以使用先验性质减少其中候选k项集的数量,即剪枝。剪枝原理为:如果k项集的任意一个k-1项集子集不在L_{k-1} 中,则该k项集一定不是频繁项集,从而可以从 C_{k} 中删除。

     

    在书中的P162-P163 有一个比较详细的例子, 读者可以认真看下, 应该可以很好的理解该过程

     

    4.Apriori算法的代码实现

    本代码使用书中数据集, 根据Apriori算法逐步实现, 可以和上文中文字介绍做一一比较, 可以看到代码结果和书中一致

    def aprioriGen(Lk_1, k): #creates Ck 
        """ 根据k-1项集产生候选k项集 
        Lk_1: k-1项集的列表 
           k: k项集的k         
        """     
        retList = [] 
        lenLk_1 = len(Lk_1)  # k-1项集的长度  
        for i in range(lenLk_1): 
            for j in range(i+1, lenLk_1):  
                L1 = sorted(list(Lk_1[i]))   # k等于2时, 1项集取空, k等于3时,2项集取第一个元素, k等于4时,3项集取前两个元素 
                L2 = sorted(list(Lk_1[j]))   # k等于2时, 1项集取空, k等于3时,2项集取第一个元素, k等于4时,3项集取前两个元素 
     
                if L1[:k-2]==L2[:k-2]: # 如果前k减2个元素相等 , 就将两几何求并  
                    retList.append(Lk_1[i] | Lk_1[j]) #set union 
        return retList 
     
     
     
    def get_subset(ss): 
        """求一个k项集的所有k-1项集子集""" 
        ls = list(ss) 
        res = []  
        for i in range(len(ls)): 
            res.append(set(ls[:i] + ls[(i+1):])) 
        return res  
                        
     
         
    def check_in(Lk_1,ck): 
        """ 返回布尔值,  
            检验候选k项集的所有k-1项集子集 是否都在L_(k-1)中 
        """ 
        i = 0  
        # 取出候选k项集的一个k-1项集子集 
        for ss_sub in get_subset(ck): 
            # 如果该k-1项集子集在在L_(k-1)中, 加1  
            if ss_sub in Lk_1: 
                i+= 1  
        # 返回候选k项集的所有k-1项集子集 是否都在L_(k-1)中 
        return i == len(ck) 
     
     
    def cut_branch(Ck,Lk_1): 
        """剪枝,  
        只保留候选K项集集合中, 所有k-1项集都在L_(k-1) 的候选k项集 
        """ 
        Ck_res = []  
        # 取出一个候选k项集 
        for ck in Ck:  
            # 判断候选k项集的所有k-1项集子集 是否都在L_(k-1)中 
            flag = check_in(Lk_1,ck) 
            # 如果是, 保留该候选k项集 
            if flag :  
                Ck_res.append(ck)  
        return Ck_res  
                 
             
    def createC1(dataSet): 
        """从数据集中构建一项集候选集,  
        将每个一项集都以frozenset的数据类型保存 
        因为frozenset可以作为字典的key, 常规的set不可以, 方便后续对候选项集计数 
        """ 
        C1 = [] 
        for transaction in dataSet: 
            for item in transaction: 
                if not [item] in C1: 
                    C1.append([item]) 
        # frozenset 可以作为字典的key, set 不可以  
        return [frozenset(i) for i in C1] 
         
         
         
    def scanD(D, Ck, minSupport):         
        """ 
        D:数据集 
        Ck:候选k项集 
        minSupport:最小支持度阈值 
        """ 
        # 扫描数据集,确定Ck中每个候选的计数 
        ssCnt = {} 
        for tid in D: 
            for can in Ck: 
                if can.issubset(tid): 
                    ssCnt[can] = ssCnt.get(can,0)+1 
         
        # 根据最小支持度阈值筛选出频繁k项集  
        retList = [] 
        supportData = {} 
        for key in ssCnt: 
            # 计算备选k项集的支持度 
            support = ssCnt[key] 
             
            # 如果支持度大于阈值, insert进k项集的结果列表 
            if support >= minSupport: 
                retList.insert(0,key) 
            # 不管支持度是否大于阈值, 都记录下该备选k项集的支持度  
            supportData[key] = support 
        return retList, supportData 
     
     
    def apriori(dataSet, minSupport): 
        C1 = createC1(dataSet) 
    #     print('C1:',C1) 
        D = [set(i) for i in dataSet] 
         
        # 检查C1中每个备选1项集的支持度, L1为筛选出的1项集, supportData为每个备选1项集的支持度 
        L1, supportData = scanD(D, C1, minSupport) 
        print(f'L1:{L1}','\n') 
        L = [L1] # 将1项集列表插入频繁k项集的结果列表 
     
        k = 2  # 2项集     
        # k项集为空的时候停止 
        while (len(L[k-2]) > 0):     
            Ck = aprioriGen(L[k-2], k)  # 连接步,产生备选k项集  
            print('过滤前:',len(Ck),Ck,'\n') 
            Ck = cut_branch(Ck,L[k-2])  # 剪枝   
            print('过滤后:',len(Ck),Ck,'\n') 
            Lk, supK = scanD(D, Ck, minSupport)#scan DB to get Lk  扫描数据集,确认C_k中的每个候选k项集是否为频繁项集  
            print('筛选后:',len(Lk),Lk,'\n') 
            supportData.update(supK) 
            L.append(Lk)  
            k += 1 
     
        return L, supportData 
     
     
     
     
    data_ls =[['I1','I2','I5'], 
        ['I2','I4'], 
        ['I2','I3'], 
        ['I1','I2','I4'], 
        ['I1','I3'], 
        ['I2','I3'], 
        ['I1','I3'], 
        ['I1','I2','I3','I5'], 
        ['I1','I2','I3']] 
     
    L, supportData =apriori(data_ls,minSupport = 2) 
    print('L:',L,'\n') 
    print("supportData:",supportData) 
     

    结果为

    参考文档:

    1. 数据挖掘概念与技术(原书第三版)

    2. 机器学习实战(人民邮电出版社) 第11章

    关注公众号:数据臭皮匠;获得更多精彩内容

    作者:范小匠

    审核:灰灰匠

    编辑:森匠

    展开全文
  • 对现有的基于MapReduce的并行频繁项集挖掘算法进行了研究,提出一种基于后缀项表的并行闭频繁项集挖掘算法,通过后缀项表的引入及以闭频繁项集挖掘的形式,减少组分间的数据传送量,提高挖掘效率。实验表明,该算法...
  • 频繁项集挖掘是关联规则挖掘的重要内容,而现有的频繁项集挖掘算法在数据库扫描和复杂数据结构构建方面消耗过多的时间,效率较低。为克服现有频繁项集挖掘算法的不足,提出了基于随机相遇的频繁项集挖掘算法。在随机...
  • 频繁项集挖掘算法——Relim算法

    千次阅读 2018-03-29 10:22:56
    前面我们已经介绍了3中频繁项集挖掘算法,今天我们来介绍一种新的不需要候选项集的频繁项集挖掘算法——Relim算法。 FP-growth算法是当前挖掘频繁项集算法中速度最快,应用最广,并且不需要候选项集的一种频繁项集...

            前面我们已经介绍了3中频繁项集挖掘算法,今天我们来介绍一种新的不需要候选项集的频繁项集挖掘算法——Relim算法。

            FP-growth算法是当前挖掘频繁项集算法中速度最快,应用最广,并且不需要候选项集的一种频繁项集挖掘算法,但是FP-growth也存在着算法结构复杂和空间利用率低等缺点。Relim算法是在FP-growth算法的基础上提出的一种新的不需要候选项集的频繁项集挖掘算法。它具有算法结构简单,空间利用率高,易于实现等显著优点。

            主要思想

            Relim算法的主要思想和FP-growth相似,也是基于递归搜索(Recursive Exploration),但是和FP-growth不同的是:Relim算法在运行时不必创建频繁模式树,而是通过建立一个事务链表组(transaction lists)来找出所有频繁项集。

            方法描述

            为了更好地描述该算法,我们通过一个实例来说明Relim算法的挖掘过程。该例基于表一所示的事务数据集。数据集中有l0个事务。设最小支持度为3(即min sup=3/10=30% )。

                                          

            Relim算法的挖掘过程如下:
            1)与Apriori算法相同,首先对数据集(表一), 进行第一次扫描,找出候选1 项集的集合,并得到它们的支持度计数(频繁性)。然后,按照支持度计数递增排列各项集,如表二所示。

            2)扫描表一,将支持度小于最小支持度3的元素(表二中的元素g和f)从各事务中消除,然后根据元素的支持度计数递增地将表一中的事务重新进行排列,如表三所示。注意:事务元素的排列顺序不会影响挖掘结果,但对运行速度有影响。递增排列,运行速度最快;反之则最慢。

            3)为表三所示的事务数据集中的所有元素都创建一项单向数据链表,并且使每个元素的数据链表都包含一个计数器和一个指针。计数器的值表示在表三中以此元素为头元素的事务总数,在本文中称之为头元素数值。指针则用于保存表三中相关事务的关联信息,因此元素的数据链表也被称为事务链表(transaction list)。把所有事务链表按照表二中元素支持度的计数递增排列,由此就创建了一组事务链表,在本文中称之为事务链表组(transaction lists),如图1所示。

                            

            4)按照元素支持度计数由小到大的顺序,首先扫描以e元素为头元素的事务链表(简称为e事务链表),如发现该链表中有项集的支持度大于或等于最小支持度3,就将此项集输出。在e事务链表中,只有项集{e}的支持度等于3,所以,将{e}输出。扫描完后,将e事务链表的头元素数值设为零,并将e事务链表从链表组中删除。

            5)创建一个和第3)步描述的结构相似的单向数据链表组,链表组保存着将e事务链表的头元素除掉后,其后继元素作为头元素的事务关联信息。这个数据链表组在本文中称之为前缀e事务链表组。如图2所示。

                              

            6)将前缀‘e事务链表组和e事务链表为空的事务链表组进行合并,得到一个新的事务链表组。如图3所示。

                                

            7)根据4),5),6)步所述,递归地对新事务链表组中的第二个事务链表(即a事务链表),进行挖掘。其挖掘结果是:{a},{a,b},{a,b,d},{a,d}的支持度都大于最小支持度3,将其结果输出。                                                                                           8)当挖到最后一个事务链表的时候,事务链表组如图4所示。该事务链表的计数器的值为8而链表指针指向空。输出频繁项集{d}后,结束频繁项集的挖掘。

                            

            Relim算法的挖掘过程

    算法:Relim通过建立一个事务链表组,用递归消除的方式来挖掘频繁项集。
    输入:事物数据集D;最小支持度阙值min_sup。
    输出:D 中的频繁项集。
    方法:
    	1)扫描事务数据集D,找出频繁1项集和它们的支持度,并按支持度大小递增排列。然后,对于D 中每个事务,执行如下操作后得到新的事物数据集D’ :
    	删除频繁1项集以外的元素.并按支持度大小递增排列元素。
    	2)将D’ 转换成一个事务链表组TLs。该事务链表组中的各项事务链表TL保存着头元素相同的各事务的相关信息,并且接头元素支持度大小递增排列。
    	3)按头元素支持度大小递增排列顺序,依次对TLs中的每个TL进行如下操作:
    	a)递归地扫描该事务链表,找出频繁项集并输出。
    	b)将该事务链表从TLs中删除,并创建以该事务链表头元素为前缀的事务链表组TLs’
    	c)合并TLs和TLs’,得到新的事务链表组TLs。(TLs+TLs’ —>TLs)
    	4)挖掘完最后一个事务链表后,结束频繁项集的挖掘。
    

            扩展:Relim算法和FPP-growth算法的性能比较

            1)算法结构:由以上所述,显而易见Relim算法的结构比FP-growth算法简单。该算法没有复杂的数据结构,因而易于实现。

            2)空间利用率:FP-growth算法主要是通过建立频繁模式树来实现关联规则挖掘。频繁模式树从挖掘开始时建立,一直到挖掘结束时都完整地保存在内存里。而Relim算法主要是通过建立事务链表组来实现挖掘的,事务链表组中的事务链表依次地被挖掘。当一个事务链表中的关联项集被挖掘完后,此事务链表就被删除,所占的内存空间也就被释放。由此可见,Relim算法的空间利用率比FP-growth算法的要高很多。

            3)运行速度:Relim算法的运行速度与FP-growth算法相比并不慢,而且当对最小支持度高或者频繁规则比较少的数据集进行挖掘时,Relim算法的运行速度往往比FP-growth算法要快。由此,对最小支持度高或者频繁规则比较少的数据集进行数据挖掘时,用Relim 算法可以节约大量的运算时间。

            4)计算复杂度:Relim算法在挖掘长模式的数据库时计算复杂,因此,只适合于挖掘短模式的数据库。如果,要将其用于长模式的数据库挖掘,则通过数据库分解方法将长模式变成短模式可能是一个可行的方法。


    参考文献:

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

    《一个新的不需要候选集的挖掘关联规则算法—Relim算法的研究》

    展开全文
  • 频繁项集挖掘算法——Apriori算法

    万次阅读 多人点赞 2018-03-28 13:42:38
    前言 关联规则就是在给定训练项集上...这两种度量标准是频繁项集挖掘中两个至关重 要的因素,也是挖掘算法的关键所在。对项集支持度和规则置信度的计算是影响挖掘算法效率的决定性因素,也是对频繁项集挖掘进行改...

    前言

            关联规则就是在给定训练项集上频繁出现的项集与项集之间的一种紧密的联系。其中“频繁”是由人为设定的一个阈值即支持度 (support)来衡量,“紧密”也是由人为设定的一个关联阈值即置信度(confidence)来衡量的。这两种度量标准是频繁项集挖掘中两个至关重 要的因素,也是挖掘算法的关键所在。对项集支持度和规则置信度的计算是影响挖掘算法效率的决定性因素,也是对频繁项集挖掘进行改进的入口点和研究热点。
    基于关联规则的分类主要分为以下以个步骤:
    1.  对训练数据进行预处理(包括离散化、缺失值处理等) 
    2.  关联规则挖掘 
         2.1  频繁项集挖掘 
         2.2  关联规则生成 
    3.  规则处理

    4.  对测试集进行测试

            在关联规则挖掘中,最耗费时间和空间资源的就是频繁项集挖掘,目前针对频繁项集挖掘已经有很多比较成熟的算法,在时间效率或空间效率对频繁项集的挖掘进行不断的优化和改进。

            接下来的几篇博客都是笔者在阅读论文或者相关文献资料中学习的几个频繁项集挖掘算法的介绍,在这里分享一下,与大家一起学习~

    Apriori算法

            算法中最经典的莫过于Apriori算法,它可以算得上是频繁项集挖掘算法的鼻祖,后续很多的改进算法也是基于Apriori算法的。但是遗憾的是Apriori算法的性能一般,但是即使如此,该算法却是频繁项集挖掘必须要掌握的入门算法。

            相关定义:

            定义1.  设I={i1,i2,…,im}是一个全局项的集合,其中ij(1≤j≤m)是项(item)的唯一标识,j表示项的序号。

      事务数据库(transactional databases)D={t1,t2,…,tn}是一个事务(transaction)的集合,每个事务ti(1≤i≤n)都对应I上的一个子集,其中ti是事务的唯一标识,i表示事务的序号。

            定义2.  由I中部分或全部项构成的一个集合称为项集(itemset),任何非空项集中均不含有重复项。如I1={i1,i3,i4}就是一个项集。

            定义3.  给定一个全局项集I和事务数据库D,一个项集在D上的支持度是包含I1的事务在D中所占的百分比,即


            支持度是一种重要性度量,因为低支持度的规则可能只是偶然出现。从实际情况看,低支持度的规则多半是没有意义的。例如,顾客很少同时购买a、b商品,想通过对a或b商品促销(降价)来提高另一种商品的销售量是不可能的。

            定义4.  给定D上的最小支持度(记为min_sup),称为最小支持度阈值。

            定义5.  给定全局项集I和事务数据库D,对于I的非空子集I1,若其支持度大于或等于min_sup,则称I1为频繁项集(Frequent Itemsets)。

            定义6.  对于I的非空子集I1,若某项集I1中包含有I中的k个项,称I1为k-项集。

      若k-项集I1是频繁项集,称为频繁k-项集。显然,一个项集是否频繁,需要通过事务数据库D来判断。


            Apriori性质    

            (1)若A是一个频繁项集,则A的每一个子集都是一个频繁项集。

            (2)若A是一个频繁项集,则A的每一个子集都是一个频繁项集。

            

            基本的Apriori算法
            Apriori算法的基本思路是采用层次搜索的迭代方法,由候选(k-1)-项集来寻找候选k-项集,并逐一判断产生的候选k-项集是否是频繁的。
      设C
    k 是长度为k的候选项集的集合,L k 是长度为k的频繁项集的集合。为了简单,设最小支持度阈值min_sup为最小元组数,即采用最小支持度计数。
            
    输入:事务数据库D,最小支持度阈值min_sup。
    输出:所有的频繁项集集合L。
    方法:其过程描述如下:
    通过扫描D得到1-频繁项集L1;
    for (k=2;Lk-1!=Ф;k++)
    {      Ck=由Lk-1通过连接运算产生的候选k-项集;
            for (事务数据库D中的事务t)
            {	求Ck中包含在t中的所有候选k-项集的计数;
    	Lk={c | c∈Ck and c.sup_count≥min_sup};
    		//求Ck中满足min_sup的候选k-项集
            }
    }
    return L=∪kLk;
    
            举例

            对于下表1.1所示的事务数据库,设min_sup=2,产生所有频繁项集的过程如右图所示,最后L4=Ф,算法结束,产生的所有频繁项集为L1∪L2∪L3。



    展开全文
  • 挖掘加权频繁项集是多种数据挖掘应用中的关键问题,为提高传统加权频繁项集挖掘算法的性能,在研究概念格模型和差集Diffsets理论的基础上,构建一种利用差集的加权频繁项集格结构,该格结构通过差集性质快速计算加权支持...
  • 导入哈希树包参看上一篇博客:... # coding=utf-8 """ A simple frequent itemset mining algorithm implementation 一种简单的频繁项集挖掘算法实现 """ import itertools fro...
  • 挖掘频繁项目,项目,子序列或其他子结构通常是分析大规模数据的第一步,这是数据挖掘多年来一直活跃的研究课题。 可以参考一下维基百科中关于关联规则学习的基础知识。 文章目录1. FP-Growth 1. FP-Growth FP-...
  • 针对大数据中的频繁项集挖掘问题,提出一种基于Spark框架的FP-Growth频繁项集并行挖掘算法。首先,根据垂直布局思想将数据按照事务标志符垂直排列,以此解决扫描整个数据集的缺陷;然后,通过FP-Growth算法构建频繁...
  • 结合数据流的特点,提出了一种新的基于滑动窗口的最大频繁项集挖掘算法。该算法用位图来存储数据流中流动的数据;采用直接覆盖的方法存储和更新数据流上的数据;在深度优先搜索挖掘最大频繁项集时,除采用经典的剪枝...
  • 基于现有的关联规则挖掘算法,提出了一种通过循环迭代增加...并提出了一种基于索引数组的频繁项集挖掘新算法。该算法只需扫描数据库两次就能发现所有频繁项集。实验结果表明,该算法可以有效提高频繁项集的挖掘效率。
  • 近年来微博炒作账户异军突起,采用违规手段开展网络公关活动,严重扰乱了正常...针对以上问题,充分考虑到炒作账户共同参与微博炒作的群体特性,将炒作群体发现问题转化为挖掘 <span xss=removed>最大频繁项集问题,
  • 频繁项集挖掘Apriori算法及其Python实现 Apriori算法是通过限制候选产生发现频繁项集。 Apriori算法使用一种称为逐层搜索的迭代方法,其中k项集用于探索(k+1)项集。首先,通过扫描数据库,累计每个项的计数,...
  • 对关联挖掘中的最大频繁项集挖掘问题进行了研究,提出了一种基于项集格修剪机制的最大频繁项集挖掘算法。采用项集格生成树的数据结构,将最大频繁项集挖掘过程转化为对项集格生成树进行深度优先搜索获取所有最大频繁...
  • 本文档重点说明了关于时间敏感数据流上的频繁项集挖掘算法,为数据挖掘专业开发人员提供相关帮助
  • 为解决P2P网络频繁项集挖掘中存在的全体频繁项集数量过多和网络通信开销较大这两个问题,提出了一种在P2P网络中挖掘最大频繁项集的算法P2PMaxSet。首先,该算法只挖掘最大频繁项集,减少了结果的数量;其次,每个节点...
  • 基于不确定数据的频繁项集挖掘算法已经得到了广泛的研究。对于记录用户敏感信息的不确定数据,攻击者可以利用自己掌握的背景信息,通过分析基于不确定数据的频繁项集从而获得用户的敏感信息。为了从不确定的数据集中...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,022
精华内容 4,808
关键字:

频繁项集挖掘