精华内容
下载资源
问答
  • 为了克服 Apriori 算法在复杂度和效率方面的缺陷,本节还进一步的介绍了基于 FP-Tree 的频繁模式挖掘方法。 Apriori关联分析算法 Apriori 算法是挖掘产生关联规则所需频繁项集的基本算法,也是最著名的关联分析算法...
  • Apriori 算法和 FPTree 算法都是数据挖掘中的关联规则挖掘算法处理的都是最简单的单层单维布尔关联规则 Apriori 算法 Apriori 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法是基于这样的事实算法使用频繁项集...
  • fpTree算法演示程序GDI+画的详细的每一步算法示例
  • 数据挖掘fp_tree算法代码,希望对大家有帮助
  • FP Tree算法原理

    千次阅读 多人点赞 2019-06-17 09:59:57
    为了解决这个问题,FP Tree算法(也称FP Growth算法)采用了一些技巧,无论多少数据,只需要扫描两次数据集,因此提高了算法运行的效率。下面我们就对FP Tree算法做一个总结。 1. FP Tree数据结构 为了减少 I/O ...

    作为一个挖掘频繁项集的算法,Apriori算法需要多次扫描数据,I/O是很大的瓶颈。为了解决这个问题,FP Tree算法(也称FP Growth算法)采用了一些技巧,无论多少数据,只需要扫描两次数据集,因此提高了算法运行的效率。下面我们就对FP Tree算法做一个总结。


    1. FP Tree数据结构

    为了减少 I/O 次数,FP Tree算法引入了一些数据结构来临时存储数据。这个数据结构包括三部分,如下图:

    在这里插入图片描述

    第一部分是一个项头表。里面记录了所有的1项频繁集出现的次数,按照次数降序排列。比如上图中B在所有10组数据中出现了8次,因此排在第一位,这部分好理解。第二部分是FP Tree,它将我们的原始数据集映射到了内存中的一颗FP树,这个FP树比较难理解,它是怎么建立的呢?这个我们后面再讲。第三部分是节点链表。所有项头表里的1项频繁集都是一个节点链表的头,它依次指向FP树中该1项频繁集出现的位置。这样做主要是方便项头表和FP Tree之间的联系查找和更新,也好理解。

    下面我们讲项头表和FP树的建立过程。

    2. 项目表的建立

    FP树的建立需要首先依赖项头表的建立。首先我们看看怎么建立项头表。

    我们第一次扫描数据,得到所有频繁一项集的的计数。然后删除支持度低于阈值的项,将1项频繁集放入项头表,并按照支持度降序排列。接着第二次也是最后一次扫描数据,将读到的原始数据剔除非频繁1项集,并按照支持度降序排列。

    上面这段话很抽象,我们用下面这个例子来具体讲解。我们有10条数据,首先第一次扫描数据并对1项集计数,我们发现O,I,L,J,P,M, N都只出现一次,支持度低于20%的阈值,因此他们不会出现在下面的项头表中。剩下的A,C,E,G,B,D,F按照支持度的大小降序排列,组成了我们的项头表。

    接着我们第二次扫描数据,对于每条数据剔除非频繁1项集,并按照支持度降序排列。比如数据项ABCEFO,里面O是非频繁1项集,因此被剔除,只剩下了ABCEF。按照支持度的顺序排序,它变成了ACEBF。其他的数据项以此类推。为什么要将原始数据集里的频繁1项数据项进行排序呢?这是为了我们后面的FP树的建立时,可以尽可能的共用祖先节点。

    通过两次扫描,项头表已经建立,排序后的数据集也已经得到了,下面我们再看看怎么建立FP树。

    在这里插入图片描述

    3. FP Tree的建立

    有了项头表和排序后的数据集,我们就可以开始FP树的建立了。开始时FP树没有数据,建立FP树时我们一条条的读入排序后的数据集,插入FP树,插入时按照排序后的顺序,插入FP树中,排序靠前的节点是祖先节点,而靠后的是子孙节点。如果有共用的祖先,则对应的公用祖先节点计数加1。插入后,如果有新节点出现,则项头表对应的节点会通过节点链表链接上新节点。直到所有的数据都插入到FP树后,FP树的建立完成。

    似乎也很抽象,我们还是用第二节的例子来描述。

    首先,我们插入第一条数据ACEBF,如下图所示。此时FP树没有节点,因此ACEBF是一个独立的路径,所有节点计数为1, 项头表通过节点链表链接上对应的新增节点。

    在这里插入图片描述

    接着我们插入数据ACG,如下图所示。由于ACG和现有的FP树可以有共有的祖先节点序列AC,因此只需要增加一个新节点G,将新节点G的计数记为1。同时A和C的计数加1成为2。当然,对应的G节点的节点链表要更新。
    在这里插入图片描述

    同样的办法可以更新后面8条数据,如下8张图。由于原理类似,这里就不多文字讲解了,大家可以自己去尝试插入并进行理解对比。相信如果大家自己可以独立的插入这10条数据,那么FP树建立的过程就没有什么难度了。

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    4. FP Tree的挖掘

    我们辛辛苦苦,终于把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的频繁2项集为{A:2,F:2}, {C:2,F:2}, {E:2,F:2}, {B:2,F:2}。递归合并二项集,得到频繁三项集为{A:2,C:2,F:2},{A:2,E:2,F:2},…还有一些频繁三项集,就不写了。当然一直递归下去,最大的频繁项集为频繁5项集,为{A:2,C:2,E:2,B:2,F:2}

    F挖掘完了,我们开始挖掘D节点。D节点比F节点复杂一些,因为它有两个叶子节点,因此首先得到的FP子树如下图左。我们接着将所有的祖先节点计数设置为叶子节点的计数,即变成{A:2, C:2,E:1 G:1,D:1, D:1}此时E节点和G节点由于在条件模式基里面的支持度低于阈值,被我们删除,最终在去除低支持度节点并不包括叶子节点后D的条件模式基为{A:2, C:2}。通过它,我们很容易得到D的频繁2项集为{A:2,D:2}, {C:2,D:2}。递归合并二项集,得到频繁三项集为{A:2,C:2,D:2}。D对应的最大的频繁项集为频繁3项集。

    在这里插入图片描述

    同样的方法可以得到B的条件模式基如下图右边,递归挖掘到B的最大频繁项集为频繁4项集{A:2, C:2, E:2,B:2}。
    在这里插入图片描述
    继续挖掘G的频繁项集,挖掘到的G的条件模式基如下图右边,递归挖掘到G的最大频繁项集为频繁4项集{A:5, C:5, E:4,G:4}。
    在这里插入图片描述
    E的条件模式基如下图右边,递归挖掘到E的最大频繁项集为频繁3项集{A:6, C:6, E:6}。
    在这里插入图片描述
    C的条件模式基如下图右边,递归挖掘到C的最大频繁项集为频繁2项集{A:8, C:8}。
    在这里插入图片描述
    至于A,由于它的条件模式基为空,因此可以不用去挖掘了。

    至此我们得到了所有的频繁项集,如果我们只是要最大的频繁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派系的。

    转载

    展开全文
  • 基于kdtree 的点云邻近点的匹配与搜索。点的深度搜索。
  • Apriori算法与FPtree算法的探讨
  • 5类手势,每类10张20*20的图片。用OpenCV自带的random tree算法进行学习,得到学习结果再对原来的50张图进行检测。
  • FP-tree算法介绍及python实现 FP-tree算法原理可参考刘建平老师的的FP-tree原理介绍,非常详细 https://www.cnblogs.com/pinard/p/6307064.html 总结起来,FP-tree算法实现需要完成三个步骤: (1)两次扫描...

    FP-tree算法介绍及python实现

    FP-tree算法原理可参考刘建平老师的的FP-tree原理介绍,非常详细

    https://www.cnblogs.com/pinard/p/6307064.html

    总结起来,FP-tree算法实现需要完成三个步骤:

    (1)两次扫描数据库,建立项头表

    (2)建立FP-tree树形结构

    (3)频繁项集的挖掘

    FP-tree实例及python实现:

    python代码实现

    import fp_growth as fpg
    
    # 数据集
    dataset = [[11,12,15], [11,12], [12,14], [11,12,14], [11,13], [11,12,13,15], [11,12,13], [12,15], [12,13,14], [13,14]]
    if __name__ == '__main__':
     '''
        调用find_frequent_itemsets()生成频繁项
        minimum_support表示设置的最小支持度,即若支持度大于等于inimum_support,保存此频繁项,否则删除
        include_support表示返回结果是否包含支持度,若include_support=True,返回结果中包含itemset和support,否则只返回itemset
    frequent_itemsets=fpg.find_frequent_itemsets(dataset,minimum_support=2,include_support=True)
        print(type(frequent_itemsets))   # print type 类型为<type 'generator'>
        result = []
        for itemset, support in frequent_itemsets:    # 将generator结果存入list
            result.append((itemset, support))
        result = sorted(result, key=lambda i: i[0])   # 排序后输出
        for itemset, support in result:
        print(str(itemset) + ' ' + str(support))       # 打印最后的结果
    
    

    实验结果:

    [11] 6

    [11, 13] 3

    [11, 15] 2

    [12] 8

    [12, 11] 5

    [12, 11, 13] 2

    [12, 11, 15] 2

    [12, 13] 3

    [12, 14] 3

    [12, 15] 3

    [13] 5

    [13, 14] 2

    [14] 4

    [15] 3

    算法总结:

    FP-Growth算法与Apriori算法(见上一篇博客)比较

    FP-Growth算法比Apriori算法快一个数量级, 也比树-投影算法快

    原因:

    (1)没有候选集的产生,没有候选测试

    (2)使用简洁的数据结构

    (3)除去了重复的数据库扫描

     
    展开全文
  • B-tree算法需求分析及实现

    千次阅读 2018-06-28 14:07:45
    下面来简要介绍一下B-tree算法,B-tree其实就是一颗多叉树,即一个父结点会下挂很多个子结点,每个结点由关键字和子结点的指针组成,关键字里存储了所需的记录数据,每个结点里的关键字都是从小到大的顺序排列,而且...


    1. 基本需求

    考虑在磁盘文件上存储一张数据表,每张表有很多记录,暂时假定每个记录所存储的空间长度是相同的,每个记录有一个唯一的索引。操作系统对文件的读写是以页为单位的,每页长度为4096字节,现在需要对这张表中的记录进行插入、查找、删除操作。

    不考虑时间和内存的性能,最简单的思路就是遍历每一页,在页中遍历每一个记录,查找给定的记录,如果记录不在这一页中再查找下一页,删除时只要找到对应的记录将其清空即可,而插入操作更简单,遍历每一页找到空闲的记录地址,将数据写入到该地址即可。

    应该说在数据量不大的时候,上述做法还是挺好的,思路清晰自然,实现起来也很简单,在性能上也并不会受到什么大的影响。

    但是在数据量比较大的时候,相对来说顺序查找的速度会慢一些,一两次查找也不会感受到慢太多,但如果是成千上万次频繁查找,积累下来的时间就非常可观了,人会明显感觉到慢很多,这时我们就要考虑做一些优化了。

    我们知道顺序查找的平均时间是O(N),二叉树查找的平均时间是O(log2N),那么能不能采用二叉树查找来缩短查找的时间呢?答案是否定的,因为二叉树只有2个子结点,每读取一个记录时都需要一次磁盘I/O 操作,树的深度较深,需要更多的磁盘I/O操作,但是磁盘的读写时间比内存要多的多,对于查找时间的最主要制约因素是磁盘文件的读写次数,所以即使总的搜索次数较少,如果磁盘I/O操作太频繁也是不行的。

    这时我们发现B-tree结构正好能弥补二叉树的缺陷,B-tree是一种多叉树,一个父结点有很多个子结点,同一个父结点下的子结点组成一个磁盘块,每读取一页时就能一次性读取到多个记录,假设子结点的个数是m,则树的深度是O(logmN),这大大减少了对磁盘文件的读写。

    2. 测试分析

    为了能感受B-tree带来的好处,有必要对顺序查找做一个简单的测试来直观感受一下。先随机插入10条记录,每条记录占16字节,再做100次随机查找,然后随机删掉2条记录,重复上述操作,记录所需要的时间。

    插入时隐含着一次查询,因为需要先查询来判读这条记录是否已经在表中了,如果在表中则表示记录存在冲突,不执行此次插入。删除时也隐含着一次查找,为了确定要删除记录在文件中的位置。

    如下图所示,遍历整张表后发现key值不在表内,同时确定了第3个slot为空闲slot,然后把key插入到该位置。

    测试平台为msys2和linux虚拟机:

                                                                 顺序查找表测试时间

    重复次数

    msys2下时间

    linux下时间

    1000

    13s

    6s

    2000

    54s

    20s

    4000

    213s

    59s

    10000

    409

    很显然根据上面的测试,顺序查询的效率非常低,而且文件数据量的增大,花费的时间基本呈指数增长。我们先看看不用btree算法有没有什么优化的方法。

    在优化前要把握住2个最关键的因素,其中一个是减少硬盘的读写次数,因为内存的读写速度要远远快于磁盘的读写速度,另外在磁盘中读写数据,磁头的移动非常耗时间,所以顺序读写的时间远远快于随机读写,甚至在固态硬盘中顺序读写比内存的随机读写都要快很多。

    根据以上2个问题,并针对上面的测试场景,我们来对插入、查找、删除分别做优化,现在先不考虑B-tree算法:

    • 插入

    每一次插入都要查询导致了磁盘的写数据不连续,所以可以先把要插入的10条记录保存到内存,进行统一查找确定没有冲突的记录,然后一次性写入到文件末尾,等到空闲的slot超过1000条时,再统一把后面的记录移到前面。在实际应用中,我们不知道什么时候会开始下一次插入操作,所以要做一个批量插入的接口。

    • 查找

    为了加快查找的速度,通常都是把数据按照一定的结构排序,但是我们上面的优化是按顺序写入数据,所以这种方法不行。那么有没有方法能使我们在查找之前就知道这个记录在不在表中呢?答案是有的,就是用bitmap算法把关键字映射到一个bit里,但是如果关键字太大的话用普通的bitmap算法将会非常耗内存,我在之前的文章里介绍过SQLite的bitmap算法可以解决这个问题,即需要多少记录使用多少内存。

    现在先假定最大记录数量为100万,此时最多需要消耗125K内存。我们把磁盘文件按块划分每10页即2560个记录组成一块,用bitmap先确定记录在哪一块,然后到对应的那一块里搜索,块的划分可以根据数据量和内存自行调整。

    使用bitmap在提高搜索速度的同时更多是为了节省内存的考虑,如果不考虑内存,甚至可以建立一个超大数组,把关键字和记录在文件中的偏移位置做一个映射。

    如下图所示,先遍历每一块,确定要查找的记录在第2块里,然后再遍历这一块的所有页中的所有slot


    •  删除

    删除操作没有什么好优化的,这就是一个建立在查找上的附加操作。

    •   移动

    每次插入时都是插入到文件的末尾,中间可能会有很多slot被删除,所以为了避免文件变得很大,当空闲slot到达1000时个时,就把后面的记录移到前面。


    下表是经过优化后的测试数据                                       

                                                          优化后的顺序查找表测试时间

    重复次数

    msys2下时间

    linux下时间

    1000

    2s

    1s

    2000

    4s

    4s

    4000

    8s

    8s

    10000

    22s

    18s

    算法的思路基本差不多,但是经过优化后发现速度提高了数10倍,所以写代码不能太随意,否则写出来的代码性能会非常差。

    3. B-tree算法

    上面已经对插入和查找做了一些优化,在查找虽然增加了bitmap分块定位来缩小查找范围,但是在每一块里基本还是顺序查找,而B-tree并不是顺序查找,而是一种特殊的二叉树查找,能够有效减少读取磁盘的次数,这是非常重要的,所以尽管B-tree写数据时是随机写入到磁盘,相比顺序写入性能会下降,但是大量应用都需要很多读操作,而写操作相对较少,所以写入性能变差也不那么关键了。

    下面来简要介绍一下B-tree算法,B-tree其实就是一颗多叉树,即一个父结点会下挂很多个子结点,每个结点由关键字和子结点的指针组成,关键字里存储了所需的记录数据,每个结点里的关键字都是从小到大的顺序排列,而且如果我们把子结点中的关键字全部展开,这时候父结点和子结点的所有关键字也都是按顺序排列的,下图就是一个典型的B-tree


    每一个磁盘块相当于一个B-tree的结点,蓝色区域是结点的关键字,黄色是子结点的指针,磁盘块里可能会有很多个关键字记录和子结点指针,我们先来看磁盘块2,关键字是8、12,子结点有P1,P2,P3,现在用子结点的关键字替代子结点的指针,得到全部关键字为3、5、8、9、10、12、13、15也是按照顺序排列的。

    如果只是随便插入的话,经过多次插入和删除后这棵树就会退化成一张线性表,那么B-tree查找的优势也就不存在了,所以每一次插入都要使B-tree保持平衡,为了保持平衡B-tree会有以下一些特性,以一颗m阶B-tree(m叉树)为例:

    • 树中每个结点至多有m个子结点
    • 除根结点和叶子结点外,其他每个结点至少有[m/2]个子结点
    • 若根结点不是叶子结点,则至少有2个子结点
    • 所有叶子结点都出现在同一层
    • 假设在某个非叶子结点里,子结点的个数为n,那么关键字的个数为n-1
    • 所有结点的关键字个数范围为[m/2]-1~m-1

    B-tree的查找比较简单,从根结点开始,按照关键字的大小定位目标结点在哪一个子结点里,层层往下搜索直到到达叶子结点,最后必定能找到目标。

    插入和删除操作就有些繁琐,因为这会变更B-tree的结构,每次操作都要维持B-tree满足上面的特性。

    下面来介绍B-tree的实现,这里以磁盘的每一页为一个结点,一页仍然是4096个字节,一页里有16字节的头部,接下来每一个记录为20个字节,其中16个字节为关键字和数据,另外4字节为子结点地址,一页里总共有(4096-16)/20=204个记录,即子结点个数最多为204个,关键字个数最多为203个,因为关键字个数要比子结点个数少1,所以最后一个记录只要子结点地址而没有关键字。

    每个结点的定义如下:

    struct Node
    {
    	NodeHdr nodeHdr;//16字节头部
    	BtreeRecord aRecord[MAX_SUB_NUM];//204个记录
    };

    头部包含了结点的属性,如是否是根结点或叶子结点,定义如下

    typedef struct NodeHdr
    {
    	u32 nPage;//页面数量,只用在第一次读取文件时从根结点获取
    	u32 reserve;
    	u8  aMagic[4];//校验值
    	u16 nRecord;//关键字个数
    	u8  isLeaf;//是否为叶子结点
    	u8  isRoot;//是否为根结点
    }NodeHdr;

    每个记录的结构体定义如下

    typedef struct BtreeRecord
    {
    	int key;//关键字
    	u8 aMagic[4];
    	u8 aData[8];
    	u32 iSub;//关键字左边的子结点地址
    }BtreeRecord;

    插入的时候数据的时候找到要插入关键字所在的叶子结点插入,在查找过程中如果有发现要查找的非叶子结点关键字数量已经到达m-1,则对其进行分裂,而叶子结点在超过m-1时才分裂,这样接保证了在分裂后父节点的关键字数量不会超过m-1,下面假设m的值为6,插入过程如下图,插入B时的时候关键字个数还没有超过最大值,直接插入,插入Q的时候关键字个数超过最大值,则进行分裂,把中间关键字T提到父结点:


    接下来要插入L时,内部结点(GMPTX)的关键字数量达到最大值,则先进行分裂,否则子树会在分裂后上提一个关键字到父结点,造成关键字数量超过限制。


    删除的操作就更加复杂了,情况分为很多种,基本思路就是先把结点删除了,如果关键字数量小于最小值2,再进行调整,整个删除过程如下图所示

    (1)如图b,删除的记录在叶子结点,且不用调整,实现函数为

    BtreeDeleteLeaf()

    (2)如图c,删除的记录M在内部结点,向下从叶子结点中找到与M相邻的记录,如果关键字的数量有多余则将其上移到被删除的M位置,此处L上移到M,注意如果L不是叶子结点,L就不与M相邻,要继续向下搜索,实现函数为

    BtreeDeleteInside()

    (3)如图c、d所示,要删除内部G,此时与M相邻的叶子结点已经没有多余的记录了,但是此时仍然把记录E或J上移到G的位置,这里假定是E,这时E所在结点已经小于最小关键字数量了,而且邻居结点的关键字数量也都到了最小值,那么找一个邻居结点合并,这里是J和K,实现函数为

    BtreeDeleteInside()

    BtreeAdjust()

    mergeBtree()

     

    (4)如图d所示,P的左右子结点的最大关键字数量都已经为最小值则将其合并,如图e所示。为了让工程实现更简单,这里只有等到(C、L)和(T、X)结点中被删关键字后从叶子结点补上来了一个关键字,但是又由于叶子结点向上层层合并触发了结点的记录数减小才合并。所以实际上,我写的代码在记录D被删除后并不触发合并,图e是《算法导论》的方案,仅作参考。

    (5)在图e和图f中,B被删除,但是邻居结点(E、J、K)的记录数有多余,则把父结点C移到被删除的B位置,把E移到父结点,实现函数为

    getNeighborKey()

    (6) 在实现时无论是删除内部结点还是叶子结点,最后都会产生一个由根结点到叶子结点的搜素记录

    pBt->aFind[pBt->iFind++]= pBt->iPage;

    最后接可以由pBt->aFind和pBt->iFind从叶子结点开始回退到根结点,回退过程中遇到关键字数量小于最小值则或是情况(5)从邻居结点拿关键字或是情况(3)与邻居结点合并。

    通过上面的分析就完成了Btree的查找和删除过程,接下来按照上一节讲到的测试方法来测试,测试结果如下,并与顺序表的处理时间做对比:

    Btree数据处理测试时间

    重复次数

    msys2下时间

    linux下时间

    1000

    0s

    0s

    2000

    1s

    1s

    4000

    3s

    2s

    10000

    8s

    6s

    顺序表处理测试时间


           重复次数

                                msys2下时间

                                       linux下时间

    优化后

    未优化

    优化后

    未优化

    1000

    2s

    13s

    1s

    6s

    2000

    4s

    54s

    4s

    20s

    4000

    8s

    213s

    8s

    59s

    10000

    22s

    18s

    409

    最后结果可以看到Btree算法比优化后的顺序查找的性能都要提高了好几倍,这里最关键的因素就是Btree减少了大量磁盘的读取次数,因为磁盘读取是一个非常耗时间的操作。

    4. 测试代码

    测试代码的 github地址如下:

    https://github.com/pfysw/btree

    btree_test()测试Btree的插入、删除和查找操作;SequenceTest()测试顺序表的插入、删除和查找操作,其中SeqTest1()是未经优化的,SeqTest2()是优化后的。

    代码是自己写的,应该还有许多不足,后续会借鉴其他开源代码中B-tree、B+-tree、LSM tree的处理来进一步优化



    展开全文
  • kd-tree算法 matlab

    2010-04-20 14:34:20
    matlab可用的kd-tree算法,运行时请将mex下对应系统的文件加入到matlab路径中
  • 数据挖掘之FP-Tree算法速学详解

    千次阅读 2021-01-07 19:58:37
    FP-TreeFP-tree算法的基本原理FP-tree算法实例1统计频率重新排序建立FP树挖掘频繁项集FP-tree算法实例2排序生成频繁模式树FP-Tree生成条件模式库构造C-FP-tree递归构造C-FP-tree FP-tree算法的基本原理 Frequent ...

    FP-tree算法的基本原理

    Frequent Pattern Tree:进行2次数据库扫描:一次对所有1-项目的频度排序;一次将数据库信息转变成紧缩内存结构。

    不使用侯选集,直接压缩数据库成一个频繁模式树,通过频繁模式树可以直接得到频集。

    基本步骤是:
    ·两次扫描数据库,生成频繁模式树FP-Tree:

        ·扫描数据库一次,得到所有1-项目的频度排序表T;
        ·依照T,再扫描数据库,得到FP-Tree。
    

    ·使用FP-Tree,生成频集:

       ·为FP-tree中的每个节点生成条件模式库;
       ·用条件模式库构造对应的条件FP-tree;
       ·递归挖掘条件FP-trees同时增长其包含的频繁集:
            -如果条件FP-tree只包含一个路径,则直接生成所包含的频繁集。
    

    FP-tree算法实例1

    统计频率

    在这里插入图片描述

    重新排序

    在这里插入图片描述

    建立FP树

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    挖掘频繁项集

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    FP-tree算法实例2

    排序

    在这里插入图片描述在这里插入图片描述

    生成频繁模式树FP-Tree

    在这里插入图片描述

    生成条件模式库

    为每个节点, 寻找它的所有前缀路径并记录其频度,形成CPB
    在这里插入图片描述

    构造C-FP-tree

    为每一个节点,通过FP-tree构造一个C-FP-tree
    例如,m节点的C-FP-tree为:
    在这里插入图片描述

    递归构造C-FP-tree

    在这里插入图片描述

    展开全文
  • FP-tree两个主要步骤: 1. 利用事务数据库中的数据构造FP-tree; 2. 从FP-tree中挖掘频繁模式。 具体过程: 1.扫描数据库一次,得到频繁1-项集。 2.把项按支持度递减排序。 3.再一次扫描数据库,建立FP-tree。 ...
  • 当前是信息爆炸的时代,推荐系统已成为解决当前网络...文章针对网上书店的电子商务网站的销售特点,详细地设计了推荐系统,并利用挖掘技术中的FP-tree关联规则算法实现数据挖掘运算,很好的实现了在线推荐的系统功能。
  • 关联规则可以说得上是数据挖掘领域最广为人知的一类算法了,起码对于我来说是这样的,在大三时候第一次接触数据挖掘领域就是Apriori算法了,后来又断断续续地接触到了FP Tree算法。现在因为工作的原因,需要进一步...
  • FP Tree算法原理总结

    千次阅读 多人点赞 2017-01-19 21:19:00
    为了解决这个问题,FP Tree算法(也称FP Growth算法)采用了一些技巧,无论多少数据,只需要扫描两次数据集,因此提高了算法运行的效率。下面我们就对FP Tree算法做一个总结。 1. FP Tree数据结构  为了减少I...
  • 数据挖掘之FP_Tree算法实现

    千次阅读 2018-09-20 11:39:06
    转自... (格式复制之后有变化,建议直接点链接去博客园看原文) ... FP-Tree算法的实现 在关联规则挖掘领域最经典的算法法是Apriori,其致命的缺点是需要多次扫描事务数据...
  • 改进算法采用二进制位标记来代替实际节点元素,并采用了有效的剪枝策略及节点扩展方式,避免了HSSE-tree算法中存在的节点个数及超集个数随着问题规模增大而产生的爆炸式增长的问题;此外,改进算法采用二进制位运算...
  • KDtree算法 python

    2021-05-18 15:18:20
    KDtree算法 python
  • Apriori算法和FP-Tree算法简介 本节主要描述了基于 Apriori 算法的关联分析方法为了克服 Apriori 算法在复杂度和效率方面的缺陷本节还进一步的介绍了基于 FP-Tree 的频繁模式挖掘方法 Apriori关联分析算法 Apriori ...
  • KD-Tree算法

    万次阅读 多人点赞 2018-05-06 21:49:08
    kd树(k-dimensional树的简称),是一种分割k维数据空间的数据结构,主要... 一、Kd-tree其实KDTree就是二叉查找树(Binary Search Tree,BST)的变种。二叉查找树的性质如下:1)若它的左子树不为空,则左子树上所...
  • Apriori算法是常用的用于挖掘出数据关联规则的算法,它用来找出数据值中频繁出现的数据集合,找出这些集合的模式有助于我们做一些决策。比如在常见的超市购物数据集,或者电商的网购数据集中,如果我们找到了频繁...
  • kdtree 算法

    2009-10-19 21:44:50
    一个算法来的 ...【实验内容】:K-D tree数据结构算法 【实验准备】:VC++编程环境软件;测试数据 【实验步骤】: 1. 先阅读教材上关于k-d tree的说明与描述 2. 设计算法实现基本数据结构 点的数据结构
  • 数据挖掘 FP-tree 算法

    万次阅读 2018-05-15 19:31:05
    学习笔记之数据挖掘 FP-tree 算法 FP-tree 算法和 Apriori 算法都被用作关联规则挖掘。 FP-tree 算法只进行 2 次数据库扫描。相比于 Apriori 算法,她没有候选集,直接压缩数据库成一个频繁模式树,通过这棵树...
  • Kd-Tree算法原理 最近邻查找

    千次阅读 2018-08-22 09:12:38
    本文介绍一种用于高维空间中的快速最近邻和近似最近邻...Kd-Tree,即K-dimensional tree,是一种高维索引树形数据结构,常用于在大规模的高维数据空间进行最近邻查找(Nearest Neighbor)和近似最近邻查找(Approxi...
  • 基于pcl库的KD-tree算法

    2020-10-17 17:06:23
    kdtree的源码,用于压缩点云数据,能够让ICP算法更加快速.k-d树 [1] (k-dimensional树的简称),是一种分割k维数据空间的数据结构。主要应用于多维空间关键数据的搜索(如:范围搜索和最近邻搜索)。K-D树是二进制...
  • KD tree算法(1)-简介&构建KD tree

    千次阅读 2017-07-06 18:15:40
    KD tree算法是KNN(K-nearest neighbor)实现的重要算法之一,下面我们先简单介绍一些KNN的知识,然后开始我们KD tree的讲解。KNN分类算法KNN是一种简单的分类方法: 分类时,对新的实例,根据k个最近邻的训练实例...
  • 基于FP-tree算法的推荐系统设计与实现.pdf
  • 数据挖掘\fp-tree算法

    2012-07-03 15:11:38
    fp-tree算法
  • 于是人们提出了各种裁剪(prune)数据集的方法以减少I/O开支,韩嘉炜老师的FP-Tree算法就是其中非常高效的一种。 支持度和置信度 严格地说Apriori和FP-Tree都是寻找频繁项集的算法,频繁项集就是所谓的“支持...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 247,345
精华内容 98,938
关键字:

tree算法