FP-Tree算法的实现

╰半橙微兮° 2022-08-02 02:22 139阅读 0赞

## FP-Tree算法的实现 ##

在关联规则挖掘领域最经典的算法法是Apriori，其致命的缺点是需要多次扫描事务数据库。于是人们提出了各种裁剪（prune）数据集的方法以减少I/O开支，韩嘉炜老师的FP-Tree算法就是其中非常高效的一种。

### 支持度和置信度 ###

严格地说Apriori和FP-Tree都是寻找频繁项集的算法，频繁项集就是所谓的“支持度”比较高的项集，下面解释一下支持度和置信度的概念。

设事务数据库为：

![复制代码][copycode.gif]

A　　E　　F　　G
    
    A　　F　　G
    
    A　　B　　E　　F　　G
    
    E　　F　　G

![复制代码][copycode.gif]

则\{A,F,G\}的支持度数为3，支持度为3/4。

\{F,G\}的支持度数为4，支持度为4/4。

\{A\}的支持度数为3，支持度为3/4。

\{F,G\}=>\{A\}的置信度为：\{A,F,G\}的支持度数 除以 \{F,G\}的支持度数，即3/4

\{A\}=>\{F,G\}的置信度为：\{A,F,G\}的支持度数 除以 \{A\}的支持度数，即3/3

强关联规则挖掘是在满足一定支持度的情况下寻找置信度达到阈值的所有模式。

### FP-Tree算法 ###

我们举个例子来详细讲解FP-Tree算法的完整实现。

事务数据库如下，一行表示一条购物记录：

![复制代码][copycode.gif]

牛奶，鸡蛋，面包，薯片
    
    鸡蛋，爆米花，薯片，啤酒
    
    鸡蛋，面包，薯片
    
    牛奶，鸡蛋，面包，爆米花，薯片，啤酒
    
    牛奶，面包，啤酒
    
    鸡蛋，面包，啤酒
    
    牛奶，面包，薯片
    
    牛奶，鸡蛋，面包，黄油，薯片
    
    牛奶，鸡蛋，黄油，薯片

![复制代码][copycode.gif]

我们的目的是要找出哪些商品总是相伴出现的，比如人们买薯片的时候通常也会买鸡蛋，则\[薯片，鸡蛋\]就是一条频繁模式（frequent pattern）。

FP-Tree算法第一步：扫描事务数据库，每项商品按频数递减排序，并删除频数小于最小支持度MinSup的商品。（第一次扫描数据库）

薯片:7鸡蛋:7面包:7牛奶:6啤酒:4                       （这里我们令MinSup=3）

以上结果就是频繁1项集，记为F1。

第二步：对于每一条购买记录，按照F1中的顺序重新排序。（第二次也是最后一次扫描数据库）

![复制代码][copycode.gif]

薯片,鸡蛋,面包,牛奶
    
    薯片,鸡蛋,啤酒
    
    薯片,鸡蛋,面包
    
    薯片,鸡蛋,面包,牛奶,啤酒
    
    面包,牛奶,啤酒
    
    鸡蛋,面包,啤酒
    
    薯片,面包,牛奶
    
    薯片,鸡蛋,面包,牛奶
    
    薯片,鸡蛋,牛奶

![复制代码][copycode.gif]

第三步：把第二步得到的各条记录插入到FP-Tree中。刚开始时后缀模式为空。

插入第一条（薯片,鸡蛋,面包,牛奶）之后

![2011100415080029.png][]

插入第二条记录（薯片,鸡蛋,啤酒）

![2011100415073229.png][]

插入第三条记录（面包,牛奶,啤酒）

![2011100415081681.png][]

估计你也知道怎么插了，最终生成的FP-Tree是：

![2011100415083056.png][]

上图中左边的那一叫做表头项，树中相同名称的节点要链接起来，链表的第一个元素就是表头项里的元素。

如果FP-Tree为空（只含一个虚的root节点），则FP-Growth函数返回。

此时输出表头项的每一项+postModel，支持度为表头项中对应项的计数。

第四步：从FP-Tree中找出频繁项。

遍历表头项中的每一项（我们拿“牛奶：6”为例），对于各项都执行以下（1）到（5）的操作：

（1）从FP-Tree中找到所有的“牛奶”节点，向上遍历它的祖先节点，得到4条路径：

![复制代码][copycode.gif]

薯片：7，鸡蛋：6，牛奶：1
    
    薯片：7，鸡蛋：6，面包：4，牛奶：3
    
    薯片：7，面包：1，牛奶：1
    
    面包：1，牛奶：1

![复制代码][copycode.gif]

对于每一条路径上的节点，其count都设置为牛奶的count

![复制代码][copycode.gif]

薯片：1，鸡蛋：1，牛奶：1
    
    薯片：3，鸡蛋：3，面包：3，牛奶：3
    
    薯片：1，面包：1，牛奶：1
    
    面包：1，牛奶：1

![复制代码][copycode.gif]

因为每一项末尾都是牛奶，可以把牛奶去掉，得到条件模式基（Conditional Pattern Base,CPB），此时的后缀模式是：（牛奶）。

![复制代码][copycode.gif]

薯片：1，鸡蛋：1
    
    薯片：3，鸡蛋：3，面包：3
    
    薯片：1，面包：1
    
    面包：1

![复制代码][copycode.gif]

（2）我们把上面的结果当作原始的事务数据库，返回到第3步，递归迭代运行。

没讲清楚，你可以参考[这篇博客][Link 1]，直接看核心代码吧：

![复制代码][copycode.gif]

public void FPGrowth(List<List<String>> transRecords,
            List<String> postPattern,Context context) throws IOException, InterruptedException {
        // 构建项头表，同时也是频繁1项集
        ArrayList<TreeNode> HeaderTable = buildHeaderTable(transRecords);
        // 构建FP-Tree
        TreeNode treeRoot = buildFPTree(transRecords, HeaderTable);
        // 如果FP-Tree为空则返回
        if (treeRoot.getChildren()==null || treeRoot.getChildren().size() == 0)
            return;
        //输出项头表的每一项+postPattern
        if(postPattern!=null){
            for (TreeNode header : HeaderTable) {
                String outStr=header.getName();
                int count=header.getCount();
                for (String ele : postPattern)
                    outStr+="\t" + ele;
                context.write(new IntWritable(count), new Text(outStr));
            }
        }
        // 找到项头表的每一项的条件模式基，进入递归迭代
        for (TreeNode header : HeaderTable) {
            // 后缀模式增加一项
            List<String> newPostPattern = new LinkedList<String>();
            newPostPattern.add(header.getName());
            if (postPattern != null)
                newPostPattern.addAll(postPattern);
            // 寻找header的条件模式基CPB，放入newTransRecords中
            List<List<String>> newTransRecords = new LinkedList<List<String>>();
            TreeNode backnode = header.getNextHomonym();
            while (backnode != null) {
                int counter = backnode.getCount();
                List<String> prenodes = new ArrayList<String>();
                TreeNode parent = backnode;
                // 遍历backnode的祖先节点，放到prenodes中
                while ((parent = parent.getParent()).getName() != null) {
                    prenodes.add(parent.getName());
                }
                while (counter-- > 0) {
                    newTransRecords.add(prenodes);
                }
                backnode = backnode.getNextHomonym();
            }
            // 递归迭代
            FPGrowth(newTransRecords, newPostPattern,context);
        }
    }

![复制代码][copycode.gif]

对于FP-Tree已经是单枝的情况，就没有必要再递归调用FPGrowth了，直接输出整条路径上所有节点的各种组合+postModel就可了。例如当FP-Tree为：

![2012081411593897.png][]

我们直接输出：

3　　A+postModel

3　　B+postModel

3　　A+B+postModel

就可以了。

如何按照上面代码里的做法，是先输出：

3　　A+postModel

3　　B+postModel

然后把B插入到postModel的头部，重新建立一个FP-Tree，这时Tree中只含A，于是输出

3　　A+(B+postModel)

两种方法结果是一样的，但毕竟重新建立FP-Tree计算量大些。

### Java实现 ###

FP树节点定义

[\+  ][ ] [?][ ]

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div> 
     <div> 
      <code>package</code> 
      <code> fptree; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>import</code> 
      <code> java.util.ArrayList; </code> 
     </div> 
     <div> 
      <code>import</code> 
      <code> java.util.List; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>public</code> 
      <code> class</code> 
      <code>TreeNode </code> 
      <code>implements</code> 
      <code>Comparable&lt;TreeNode&gt; { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>private</code> 
      <code>String name; </code> 
      <code>// 节点名称 </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>private</code> 
      <code>int</code> 
      <code>count; </code> 
      <code>// 计数 </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>private</code> 
      <code>TreeNode parent; </code> 
      <code>// 父节点 </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>private</code> 
      <code>List&lt;TreeNode&gt; children; </code> 
      <code>// 子节点 </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>private</code> 
      <code>TreeNode nextHomonym; </code> 
      <code>// 下一个同名节点 </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>TreeNode() { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>TreeNode(String name) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>this</code> 
      <code>.name = name; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>String getName() { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>name; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>void</code> 
      <code>setName(String name) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>this</code> 
      <code>.name = name; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>int</code> 
      <code>getCount() { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>count; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>void</code> 
      <code>setCount(</code> 
      <code>int</code> 
      <code>count) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>this</code> 
      <code>.count = count; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>TreeNode getParent() { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>parent; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>void</code> 
      <code>setParent(TreeNode parent) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>this</code> 
      <code>.parent = parent; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>List&lt;TreeNode&gt; getChildren() { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>children; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>void</code> 
      <code>addChild(TreeNode child) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(</code> 
      <code>this</code> 
      <code>.getChildren() == </code> 
      <code>null</code> 
      <code>) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>List&lt;TreeNode&gt; list = </code> 
      <code>new</code> 
      <code>ArrayList&lt;TreeNode&gt;(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>list.add(child); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>this</code> 
      <code>.setChildren(list); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
      <code>else</code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>this</code> 
      <code>.getChildren().add(child); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>TreeNode findChild(String name) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>List&lt;TreeNode&gt; children = </code> 
      <code>this</code> 
      <code>.getChildren(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(children != </code> 
      <code>null</code> 
      <code>) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(TreeNode child : children) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(child.getName().equals(name)) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>child; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>null</code> 
      <code>; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>void</code> 
      <code>setChildren(List&lt;TreeNode&gt; children) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>this</code> 
      <code>.children = children; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>void</code> 
      <code>printChildrenName() { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>List&lt;TreeNode&gt; children = </code> 
      <code>this</code> 
      <code>.getChildren(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(children != </code> 
      <code>null</code> 
      <code>) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(TreeNode child : children) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>System.out.print(child.getName() + </code> 
      <code>" "</code> 
      <code>); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
      <code>else</code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>System.out.print(</code> 
      <code>"null"</code> 
      <code>); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>TreeNode getNextHomonym() { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>nextHomonym; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>void</code> 
      <code>setNextHomonym(TreeNode nextHomonym) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>this</code> 
      <code>.nextHomonym = nextHomonym; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>void</code> 
      <code>countIncrement(</code> 
      <code>int</code> 
      <code>n) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>this</code> 
      <code>.count += n; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>@Override</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>int</code> 
      <code>compareTo(TreeNode arg0) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>// TODO Auto-generated method stub </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>count0 = arg0.getCount(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>// 跟默认的比较大小相反，导致调用Arrays.sort()时是按降序排列 </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>count0 - </code> 
      <code>this</code> 
      <code>.count; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

挖掘频繁模式

[\+  ][ ] [?][ ]

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div> 
     <div> 
      <code>package</code> 
      <code> fptree; </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>import</code> 
      <code> java.io.BufferedReader; </code> 
     </div> 
     <div> 
      <code>import</code> 
      <code> java.io.FileReader; </code> 
     </div> 
     <div> 
      <code>import</code> 
      <code> java.io.IOException; </code> 
     </div> 
     <div> 
      <code>import</code> 
      <code> java.util.ArrayList; </code> 
     </div> 
     <div> 
      <code>import</code> 
      <code> java.util.Collections; </code> 
     </div> 
     <div> 
      <code>import</code> 
      <code> java.util.Comparator; </code> 
     </div> 
     <div> 
      <code>import</code> 
      <code> java.util.HashMap; </code> 
     </div> 
     <div> 
      <code>import</code> 
      <code> java.util.LinkedList; </code> 
     </div> 
     <div> 
      <code>import</code> 
      <code> java.util.List; </code> 
     </div> 
     <div> 
      <code>import</code> 
      <code> java.util.Map; </code> 
     </div> 
     <div> 
      <code>import</code> 
      <code> java.util.Map.Entry; </code> 
     </div> 
     <div> 
      <code>import</code> 
      <code> java.util.Set; </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>public</code> 
      <code> class</code> 
      <code>FPTree { </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>private</code> 
      <code>int</code> 
      <code>minSuport; </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>int</code> 
      <code>getMinSuport() { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>minSuport; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>void</code> 
      <code>setMinSuport(</code> 
      <code>int</code> 
      <code>minSuport) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>this</code> 
      <code>.minSuport = minSuport; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>// 从若干个文件中读入Transaction Record </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>List&lt;List&lt;String&gt;&gt; readTransRocords(String... filenames) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>List&lt;List&lt;String&gt;&gt; transaction = </code> 
      <code>null</code> 
      <code>; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(filenames.length &gt; </code> 
      <code>0</code> 
      <code>) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>transaction = </code> 
      <code>new</code> 
      <code>LinkedList&lt;List&lt;String&gt;&gt;(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(String filename : filenames) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>try</code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>FileReader fr = </code> 
      <code>new</code> 
      <code>FileReader(filename); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>BufferedReader br = </code> 
      <code>new</code> 
      <code>BufferedReader(fr); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>try</code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>String line; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>List&lt;String&gt; record; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>while</code> 
      <code>((line = br.readLine()) != </code> 
      <code>null</code> 
      <code>) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(line.trim().length()&gt;</code> 
      <code>0</code> 
      <code>){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>String str[] = line.split(</code> 
      <code>"，"</code> 
      <code>); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>record = </code> 
      <code>new</code> 
      <code>LinkedList&lt;String&gt;(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(String w : str) </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>record.add(w); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>transaction.add(record); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
      <code>finally</code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>br.close(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
      <code>catch</code> 
      <code>(IOException ex) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>System.out.println(</code> 
      <code>"Read transaction records failed."</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>+ ex.getMessage()); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>System.exit(</code> 
      <code>1</code> 
      <code>); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>transaction; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>// FP-Growth算法 </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>void</code> 
      <code>FPGrowth(List&lt;List&lt;String&gt;&gt; transRecords, </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>List&lt;String&gt; postPattern) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>// 构建项头表，同时也是频繁1项集 </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>ArrayList&lt;TreeNode&gt; HeaderTable = buildHeaderTable(transRecords); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>// 构建FP-Tree </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>TreeNode treeRoot = buildFPTree(transRecords, HeaderTable); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>// 如果FP-Tree为空则返回 </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(treeRoot.getChildren()==</code> 
      <code>null</code> 
      <code>|| treeRoot.getChildren().size() == </code> 
      <code>0</code> 
      <code>) </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>//输出项头表的每一项+postPattern </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(postPattern!=</code> 
      <code>null</code> 
      <code>){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(TreeNode header : HeaderTable) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>System.out.print(header.getCount() + </code> 
      <code>"\t"</code> 
      <code>+ header.getName()); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(String ele : postPattern) </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>System.out.print(</code> 
      <code>"\t"</code> 
      <code>+ ele); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>System.out.println(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>// 找到项头表的每一项的条件模式基，进入递归迭代 </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(TreeNode header : HeaderTable) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>// 后缀模式增加一项 </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>List&lt;String&gt; newPostPattern = </code> 
      <code>new</code> 
      <code>LinkedList&lt;String&gt;(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>newPostPattern.add(header.getName()); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(postPattern != </code> 
      <code>null</code> 
      <code>) </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>newPostPattern.addAll(postPattern); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>// 寻找header的条件模式基CPB，放入newTransRecords中 </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>List&lt;List&lt;String&gt;&gt; newTransRecords = </code> 
      <code>new</code> 
      <code>LinkedList&lt;List&lt;String&gt;&gt;(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>TreeNode backnode = header.getNextHomonym(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>while</code> 
      <code>(backnode != </code> 
      <code>null</code> 
      <code>) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>counter = backnode.getCount(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>List&lt;String&gt; prenodes = </code> 
      <code>new</code> 
      <code>ArrayList&lt;String&gt;(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>TreeNode parent = backnode; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>// 遍历backnode的祖先节点，放到prenodes中 </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>while</code> 
      <code>((parent = parent.getParent()).getName() != </code> 
      <code>null</code> 
      <code>) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>prenodes.add(parent.getName()); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>while</code> 
      <code>(counter-- &gt; </code> 
      <code>0</code> 
      <code>) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>newTransRecords.add(prenodes); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>backnode = backnode.getNextHomonym(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>// 递归迭代 </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>FPGrowth(newTransRecords, newPostPattern); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>// 构建项头表，同时也是频繁1项集 </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>ArrayList&lt;TreeNode&gt; buildHeaderTable(List&lt;List&lt;String&gt;&gt; transRecords) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>ArrayList&lt;TreeNode&gt; F1 = </code> 
      <code>null</code> 
      <code>; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(transRecords.size() &gt; </code> 
      <code>0</code> 
      <code>) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>F1 = </code> 
      <code>new</code> 
      <code>ArrayList&lt;TreeNode&gt;(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>Map&lt;String, TreeNode&gt; map = </code> 
      <code>new</code> 
      <code>HashMap&lt;String, TreeNode&gt;(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>// 计算事务数据库中各项的支持度 </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(List&lt;String&gt; record : transRecords) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(String item : record) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(!map.keySet().contains(item)) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>TreeNode node = </code> 
      <code>new</code> 
      <code>TreeNode(item); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>node.setCount(</code> 
      <code>1</code> 
      <code>); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>map.put(item, node); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
      <code>else</code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>map.get(item).countIncrement(</code> 
      <code>1</code> 
      <code>); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>// 把支持度大于（或等于）minSup的项加入到F1中 </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>Set&lt;String&gt; names = map.keySet(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(String name : names) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>TreeNode tnode = map.get(name); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(tnode.getCount() &gt;= minSuport) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>F1.add(tnode); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>Collections.sort(F1); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>F1; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
      <code>else</code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>null</code> 
      <code>; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>// 构建FP-Tree </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>TreeNode buildFPTree(List&lt;List&lt;String&gt;&gt; transRecords, </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>ArrayList&lt;TreeNode&gt; F1) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>TreeNode root = </code> 
      <code>new</code> 
      <code>TreeNode(); </code> 
      <code>// 创建树的根节点 </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(List&lt;String&gt; transRecord : transRecords) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>LinkedList&lt;String&gt; record = sortByF1(transRecord, F1); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>TreeNode subTreeRoot = root; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>TreeNode tmpRoot = </code> 
      <code>null</code> 
      <code>; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(root.getChildren() != </code> 
      <code>null</code> 
      <code>) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>while</code> 
      <code>(!record.isEmpty() </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>&amp;&amp; (tmpRoot = subTreeRoot.findChild(record.peek())) != </code> 
      <code>null</code> 
      <code>) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>tmpRoot.countIncrement(</code> 
      <code>1</code> 
      <code>); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>subTreeRoot = tmpRoot; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>record.poll(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>addNodes(subTreeRoot, record, F1); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>root; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>// 把交易记录按项的频繁程序降序排列 </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>LinkedList&lt;String&gt; sortByF1(List&lt;String&gt; transRecord, </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>ArrayList&lt;TreeNode&gt; F1) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>Map&lt;String, Integer&gt; map = </code> 
      <code>new</code> 
      <code>HashMap&lt;String, Integer&gt;(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(String item : transRecord) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>// 由于F1已经是按降序排列的， </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(</code> 
      <code>int</code> 
      <code> i = </code> 
      <code>0</code> 
      <code>; i &lt; F1.size(); i++) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>TreeNode tnode = F1.get(i); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(tnode.getName().equals(item)) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>map.put(item, i); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>ArrayList&lt;Entry&lt;String, Integer&gt;&gt; al = </code> 
      <code>new</code> 
      <code>ArrayList&lt;Entry&lt;String, Integer&gt;&gt;( </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>map.entrySet()); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>Collections.sort(al, </code> 
      <code>new</code> 
      <code>Comparator&lt;Map.Entry&lt;String, Integer&gt;&gt;() { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>@Override</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>int</code> 
      <code>compare(Entry&lt;String, Integer&gt; arg0, </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>Entry&lt;String, Integer&gt; arg1) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>// 降序排列 </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>arg0.getValue() - arg1.getValue(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>LinkedList&lt;String&gt; rest = </code> 
      <code>new</code> 
      <code>LinkedList&lt;String&gt;(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(Entry&lt;String, Integer&gt; entry : al) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>rest.add(entry.getKey()); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>rest; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>// 把record作为ancestor的后代插入树中 </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>void</code> 
      <code>addNodes(TreeNode ancestor, LinkedList&lt;String&gt; record, </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>ArrayList&lt;TreeNode&gt; F1) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(record.size() &gt; </code> 
      <code>0</code> 
      <code>) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>while</code> 
      <code>(record.size() &gt; </code> 
      <code>0</code> 
      <code>) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>String item = record.poll(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>TreeNode leafnode = </code> 
      <code>new</code> 
      <code>TreeNode(item); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>leafnode.setCount(</code> 
      <code>1</code> 
      <code>); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>leafnode.setParent(ancestor); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>ancestor.addChild(leafnode); </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(TreeNode f1 : F1) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(f1.getName().equals(item)) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>while</code> 
      <code>(f1.getNextHomonym() != </code> 
      <code>null</code> 
      <code>) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>f1 = f1.getNextHomonym(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>f1.setNextHomonym(leafnode); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>break</code> 
      <code>; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>addNodes(leafnode, record, F1); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>static</code> 
      <code>void</code> 
      <code> main(String[] args) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>FPTree fptree = </code> 
      <code>new</code> 
      <code>FPTree(); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>fptree.setMinSuport(</code> 
      <code>3</code> 
      <code>); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>List&lt;List&lt;String&gt;&gt; transRecords = fptree </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>.readTransRocords(</code> 
      <code>"/home/orisun/test/market"</code> 
      <code>); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>fptree.FPGrowth(transRecords, </code> 
      <code>null</code> 
      <code>); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

输入文件

![复制代码][copycode.gif]

牛奶，鸡蛋，面包，薯片
    鸡蛋，爆米花，薯片，啤酒
    鸡蛋，面包，薯片
    牛奶，鸡蛋，面包，爆米花，薯片，啤酒
    牛奶，面包，啤酒
    鸡蛋，面包，啤酒
    牛奶，面包，薯片
    牛奶，鸡蛋，面包，黄油，薯片
    牛奶，鸡蛋，黄油，薯片

![复制代码][copycode.gif]

输出

![复制代码][copycode.gif]

6    薯片    鸡蛋
    5    薯片    面包
    5    鸡蛋    面包
    4    薯片    鸡蛋    面包
    5    薯片    牛奶
    5    面包    牛奶
    4    鸡蛋    牛奶
    4    薯片    面包    牛奶
    4    薯片    鸡蛋    牛奶
    3    面包    鸡蛋    牛奶
    3    薯片    面包    鸡蛋    牛奶
    3    鸡蛋    啤酒
    3    面包    啤酒

![复制代码][copycode.gif]

### 用Hadoop来实现 ###

在上面的代码我们把整个事务数据库放在一个List<List<String>>里面传给FPGrowth，在实际中这是不可取的，因为内存不可能容下整个事务数据库，我们可能需要从关系关系数据库中一条一条地读入来建立FP-Tree。但无论如何 FP-Tree是肯定需要放在内存中的，但内存如果容不下怎么办？另外FPGrowth仍然是非常耗时的，你想提高速度怎么办？解决办法：分而治之，并行计算。

按照论文《[FP-Growth 算法MapReduce 化研究][FP-Growth _MapReduce]》中介绍的方法，我们来看看语料中哪些词总是经常出现，一句话作为一个事务，这句话中的词作为项。

MR\_FPTree.java

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 import imdm.bean.TreeNode;
      2 import ioformat.EncryptFieInputFormat;
      3 
      4 import java.io.IOException;
      5 import java.text.SimpleDateFormat;
      6 import java.util.ArrayList;
      7 import java.util.Calendar;
      8 import java.util.Collections;
      9 import java.util.Comparator;
     10 import java.util.LinkedHashMap;
     11 import java.util.LinkedList;
     12 import java.util.List;
     13 
     14 import org.apache.hadoop.conf.Configuration;
     15 import org.apache.hadoop.fs.FSDataInputStream;
     16 import org.apache.hadoop.fs.FileSystem;
     17 import org.apache.hadoop.fs.Path;
     18 import org.apache.hadoop.io.IntWritable;
     19 import org.apache.hadoop.io.LongWritable;
     20 import org.apache.hadoop.io.Text;
     21 import org.apache.hadoop.mapreduce.Job;
     22 import org.apache.hadoop.mapreduce.Mapper;
     23 import org.apache.hadoop.mapreduce.Reducer;
     24 import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
     25 import org.apache.hadoop.util.GenericOptionsParser;
     26 import org.apache.hadoop.util.LineReader;
     27 import org.wltea.analyzer.dic.Dictionary;
     28 
     29 import text.outservice.WordSegService;
     30 
     31 public class MR_FPTree {
     32 
     33     private static final int minSuport = 30; // 最小支持度
     34 
     35     public static class GroupMapper extends
     36             Mapper<LongWritable, Text, Text, Text> {
     37 
     38         LinkedHashMap<String, Integer> freq = new LinkedHashMap<String, Integer>(); // 频繁1项集
     39 
     40         org.wltea.analyzer.cfg.Configuration cfg = null;
     41         Dictionary ikdict = null;
     42 
     43         /**
     44          * 读取频繁1项集
     45          */
     46         @Override
     47         public void setup(Context context) throws IOException {
     48             // 初始化IK分词器
     49             cfg = org.wltea.analyzer.cfg.DefaultConfig.getInstance();
     50             ikdict = Dictionary.initial(cfg);
     51             // 从HDFS文件读入频繁1项集，即读取IMWordCount的输出文件，要求已经按词频降序排好
     52             Configuration conf = context.getConfiguration();
     53             FileSystem fs = FileSystem.get(conf);
     54             Calendar cad = Calendar.getInstance();
     55             cad.add(Calendar.DAY_OF_MONTH, -1); // 昨天
     56             SimpleDateFormat sdf = new SimpleDateFormat("yyyyMMdd");
     57             String yes_day = sdf.format(cad.getTime());
     58             Path freqFile = new Path("/dsap/resultdata/content/WordCount/"
     59                     + yes_day + "/part-r-00000");
     60 
     61             FSDataInputStream fileIn = fs.open(freqFile);
     62             LineReader in = new LineReader(fileIn, conf);
     63             Text line = new Text();
     64             while (in.readLine(line) > 0) {
     65                 String[] arr = line.toString().split("\\s+");
     66                 if (arr.length == 2) {
     67                     int count = Integer.parseInt(arr[1]);
     68                     // 只读取词频大于最小支持度的
     69                     if (count > minSuport) {
     70                         String word = arr[0];
     71                         freq.put(word, count);
     72                     }
     73                 }
     74             }
     75             in.close();
     76 
     77         }
     78 
     79         @Override
     80         public void map(LongWritable key, Text value, Context context)
     81                 throws IOException, InterruptedException {
     82             String[] arr = value.toString().split("\\s+");
     83             if (arr.length == 4) {
     84                 String content = arr[3];
     85                 List<String> result = WordSegService.wordSeg(content);
     86                 List<String> list = new LinkedList<String>();
     87                 for (String ele : result) {
     88                     // 如果在频繁1项集中
     89                     if (freq.containsKey(ele)) {
     90                         list.add(ele.toLowerCase()); // 如果包含英文字母，则统一转换为小写
     91                     }
     92                 }
     93 
     94                 // 对事务项中的每一项按频繁1项集排序
     95                 Collections.sort(list, new Comparator<String>() {
     96                     @Override
     97                     public int compare(String s1, String s2) {
     98                         return freq.get(s2) - freq.get(s1);
     99                     }
    100                 });
    101 
    102                 /**
    103                  * 比如对于事务(中国，人民，人民，广场)，输出(中国，人民)、(中国，人民，广场)
    104                  */
    105                 List<String> newlist = new ArrayList<String>();
    106                 newlist.add(list.get(0));
    107                 for (int i = 1; i < list.size(); i++) {
    108                     // 去除list中的重复项
    109                     if (!list.get(i).equals(list.get(i - 1))) {
    110                         newlist.add(list.get(i));
    111                     }
    112                 }
    113                 for (int i = 1; i < newlist.size(); i++) {
    114                     StringBuilder sb = new StringBuilder();
    115                     for (int j = 0; j <= i; j++) {
    116                         sb.append(newlist.get(j) + "\t");
    117                     }
    118                     context.write(new Text(newlist.get(i)),
    119                             new Text(sb.toString()));
    120                 }
    121             }
    122         }
    123     }
    124 
    125     public static class FPReducer extends
    126             Reducer<Text, Text, Text, IntWritable> {
    127         public void reduce(Text key, Iterable<Text> values, Context context)
    128                 throws IOException, InterruptedException {
    129             List<List<String>> trans = new LinkedList<List<String>>(); // 事务数据库
    130             while (values.iterator().hasNext()) {
    131                 String[] arr = values.iterator().next().toString()
    132                         .split("\\s+");
    133                 LinkedList<String> list = new LinkedList<String>();
    134                 for (String ele : arr)
    135                     list.add(ele);
    136                 trans.add(list);
    137             }
    138             List<TreeNode> leafNodes = new LinkedList<TreeNode>(); // 收集FPTree中的叶节点
    139             buildFPTree(trans, leafNodes);
    140             for (TreeNode leaf : leafNodes) {
    141                 TreeNode tmpNode = leaf;
    142                 List<String> associateRrule = new ArrayList<String>();
    143                 int frequency = 0;
    144                 while (tmpNode.getParent() != null) {
    145                     associateRrule.add(tmpNode.getName());
    146                     frequency = tmpNode.getCount();
    147                     tmpNode = tmpNode.getParent();
    148                 }
    149                 // Collections.sort(associateRrule); //从根节点到叶节点已经按F1排好序了，不需要再排序了
    150                 StringBuilder sb = new StringBuilder();
    151                 for (String ele : associateRrule) {
    152                     sb.append(ele + "|");
    153                 }
    154                 // 因为一句话可能包含重复的词，所以即使这些词都是从F1中取出来的，到最后其支持度也可能小于最小支持度
    155                 if (frequency > minSuport) {
    156                     context.write(new Text(sb.substring(0, sb.length() - 1)
    157                             .toString()), new IntWritable(frequency));
    158                 }
    159             }
    160         }
    161 
    162         // 构建FP-Tree
    163         public TreeNode buildFPTree(List<List<String>> records,
    164                 List<TreeNode> leafNodes) {
    165             TreeNode root = new TreeNode(); // 创建树的根节点
    166             for (List<String> record : records) { // 遍历每一项事务
    167                 // root.printChildrenName();
    168                 insertTransToTree(root, record, leafNodes);
    169             }
    170             return root;
    171         }
    172 
    173         // 把record作为ancestor的后代插入树中
    174         public void insertTransToTree(TreeNode root, List<String> record,
    175                 List<TreeNode> leafNodes) {
    176             if (record.size() > 0) {
    177                 String ele = record.get(0);
    178                 record.remove(0);
    179                 if (root.findChild(ele) != null) {
    180                     root.countIncrement(1);
    181                     root = root.findChild(ele);
    182                     insertTransToTree(root, record, leafNodes);
    183                 } else {
    184                     TreeNode node = new TreeNode(ele);
    185                     root.addChild(node);
    186                     node.setCount(1);
    187                     node.setParent(root);
    188                     if (record.size() == 0) {
    189                         leafNodes.add(node); // 把叶节点都放在一个链表中
    190                     }
    191                     insertTransToTree(node, record, leafNodes);
    192                 }
    193             }
    194         }
    195     }
    196 
    197     public static void main(String[] args) throws IOException,
    198             InterruptedException, ClassNotFoundException {
    199         Configuration conf = new Configuration();
    200         String[] argv = new GenericOptionsParser(conf, args).getRemainingArgs();
    201         if (argv.length < 2) {
    202             System.err
    203                     .println("Usage: MR_FPTree EcryptedChartContent AssociateRules");
    204             System.exit(1);
    205         }
    206 
    207         FileSystem fs = FileSystem.get(conf);
    208         Path inpath = new Path(argv[0]);
    209         Path outpath = new Path(argv[1]);
    210         fs.delete(outpath, true);
    211 
    212         Job FPTreejob = new Job(conf, "MR_FPTree");
    213         FPTreejob.setJarByClass(MR_FPTree.class);
    214 
    215         FPTreejob.setInputFormatClass(EncryptFieInputFormat.class);
    216         EncryptFieInputFormat.addInputPath(FPTreejob, inpath);
    217         FileOutputFormat.setOutputPath(FPTreejob, outpath);
    218 
    219         FPTreejob.setMapperClass(GroupMapper.class);
    220         FPTreejob.setMapOutputKeyClass(Text.class);
    221         FPTreejob.setMapOutputValueClass(Text.class);
    222 
    223         FPTreejob.setReducerClass(FPReducer.class);
    224         FPTreejob.setOutputKeyClass(Text.class);
    225         FPTreejob.setOutputKeyClass(IntWritable.class);
    226 
    227         FPTreejob.waitForCompletion(true);
    228     }
    229 }

### 结束语 ###

在实践中，关联规则挖掘可能并不像人们期望的那么有用。一方面是因为支持度置信度框架会产生过多的规则，并不是每一个规则都是有用的。另一方面大部分的关联规则并不像“啤酒与尿布”这种经典故事这么普遍。关联规则分析是需要技巧的，有时需要用更严格的统计学知识来控制规则的增殖。

原文来自:博客园（华夏35度）http://www.cnblogs.com/zhangchaoyang 作者:Orisun

[copycode.gif]: /images/20220731/87a5afdfa3174436a6ee3685e553d93e.png
[2011100415080029.png]: /images/20220731/53d43e9630014f50a9b599b0efcf1d86.png
[2011100415073229.png]: /images/20220731/48b53a2cdf7c48048f5d482eeec71f01.png
[2011100415081681.png]: /images/20220731/0a5b1a675f054f6996b948d2f7eb7353.png
[2011100415083056.png]: /images/20220731/1fd8308ea2914dd9ad4bc303fab3784b.png
[Link 1]: http://hi.baidu.com/yfx416/blog/item/3daf552cea14cff68b139907.html
[2012081411593897.png]: /images/20220731/39921ea6f5cb4e7f92806252a6db7152.png
[ ]: http://www.cnblogs.com/zhangchaoyang/articles/2198946.html#
[FP-Growth _MapReduce]: http://www.chinacloud.cn/upload/2012-12/12122309272711.pdf
[ContractedBlock.gif]: http://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220731/32744532ba9c459dabb6b1ae5dbf240c.png