algorithm description

网上下载的用java写的fpgrowth算法的源代码

FP_growth算法描述：
    FP_growth算法有两个特点；一是将事务中的项集压缩存储到一棵树上。二是在这棵树上用递归的方法挖掘频繁项集。
一、构造FPTree：
  FPTree由ItemTb表和一棵Tree组成。ItemTb表中按项的支持度计数从大到小的顺序将数据库中所有的项进行排列。ItemTb
表包含三个数组一个是项的名称item，一个是项的支持度计数count，一个是指向该项在树中第一个结点的头结点数组link。
  Tree的结点结构较复杂
  
              ^
              |
            pa|rent   child   item    count   bnode    
            __|_____________________________________
           |_______|____|___|_______|_______|______-|--> 兄弟结点
                        |
                        v
                       link   next
                       ____________  描述孩子结点的下一个结点   __________
                      |__|___|____-|--------------------->|__|__|____|
                         |                                   |
                         V                                   V
                    孩子结点                                        孩子结点
                      
                      
    parent指向父结点，child的link指向孩子结点，next指向描述下一个孩子的结点                  
bnode的作用是将树中所有相同项的结点串起。
构造FPTree的过程是:
    1、首先读取数据库中所有种类的项和这些项的支持度计数。存入到itTotal链表中。
    2、将itTotal链表按照支持度计数从大到小排序     
    3、将itTotal链表插入到ItemTb表中
    4、第二便读取数据库中的事务，将事务中的项按照支持度计数由大到小的顺序插入到树中。  
    5、遍历树，将属于同一项的结点通过bnode指针连接起来。
    本程序中，FP-tree中存储了所有的项集，没有考虑最小支持度。只是在FP-growth中挖掘频繁项集时考虑最小支持度
    
二、FP_growth算法：
   从一棵FPTree的ItemTb表中取得第一个项I1。如果该项的支持度计数满足最小支持度计数{
     1、把该项I1加入到存储挖掘到的频繁项集的数据结构ItemSet中
     2、得到该项I1在目前FPTree中的条件模式基，即该项在树中的结点的前缀路径（路径中不再包括该项）。
         注意该项I1的条件模式基中各个项的支持度计数相等，等于该项I1的支持度计数
     3、每条路径看作一个事务，用这些路径建造该项的条件FPTree，然后递归调用FP_growth算法。
         在递归调用FP_growth算法时，那些大于支持度计数的项作为项I1的孩子结点存储在ItemSet中。
   }      
   继续ItemTb表中满足支持度计数的其他项 。                 
   ItemSet中的存储结果举例：     
                 
     I1              child
     ______  child  _______
    |__|__-|------>|___|___|
       |               |
  next |       next    |
    I2 V            I3 V
     _____          ________  child  _______
    |_____|        |___|___-|------>|___|___|
                       |                |
                  next |                |
                       V             I4 V
                       
     它表示I1是从最初的FPTree中得到的频繁项，然后产生I1的条件FPTree fpt1后得到I3是该fpt1的频繁项。
在fpt1上产生I3的条件FPTree fpt2得到I4是fpt2 的频繁项。
    I2是从最初FPTree中得到的第二个频繁项。
    因此得到的最大频繁项集是{I1 I3 I4}和{I2}