原文來自:博客園（華夏35度）http://www.cnblogs.com/zhangchaoyang 作者:Orisun

個人覺得這篇文章寫的挺好的，前面大半部分都很好理解，到了最后根據FP-tree獲取頻繁項集那里有點費勁。不過多看兩遍就好了，第一遍看不懂的同學不要輕易放棄。

======================＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

在關聯規則挖掘領域最經典的算法法是Apriori，其致命的缺點是需要多次掃描事務數據庫。于是人們提出了各種裁剪（prune）數據集的方法以減少I/O開支，韓嘉煒老師的FP-Tree算法就是其中非常高效的一種。

支持度和置信度

嚴格地說Apriori和FP-Tree都是尋找頻繁項集的算法，頻繁項集就是所謂的“支持度”比較高的項集，下面解釋一下支持度和置信度的概念。

設事務數據庫為：

A　　E　　F　　GA　　F　　GA　　B　　E　　F　　GE　　F　　G

則{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算法的完整實現。

事務數據庫如下，一行表示一條購物記錄：

牛奶，雞蛋，面包，薯片雞蛋，爆米花，薯片，啤酒雞蛋，面包，薯片牛奶，雞蛋，面包，爆米花，薯片，啤酒牛奶，面包，啤酒雞蛋，面包，啤酒牛奶，面包，薯片牛奶，雞蛋，面包，黃油，薯片牛奶，雞蛋，黃油，薯片

我們的目的是要找出哪些商品總是相伴出現的，比如人們買薯片的時候通常也會買雞蛋，則[薯片，雞蛋]就是一條頻繁模式（frequent pattern）。

FP-Tree算法第一步：掃描事務數據庫，每項商品按頻數遞減排序，并刪除頻數小于最小支持度MinSup的商品。（第一次掃描數據庫）

薯片:7雞蛋:7面包:7牛奶:6啤酒:4? ? ? ? ? ? ? ? ? ? ? ?（這里我們令MinSup=3）

以上結果就是頻繁1項集，記為F1。

第二步：對于每一條購買記錄，按照F1中的順序重新排序。（第二次也是最后一次掃描數據庫）

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

第三步：把第二步得到的各條記錄插入到FP-Tree中。剛開始時后綴模式為空。

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

插入第二條記錄（薯片,雞蛋,啤酒）

插入第三條記錄（面包,牛奶,啤酒）

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

上圖中左邊的那一叫做表頭項，樹中相同名稱的節點要鏈接起來，鏈表的第一個元素就是表頭項里的元素。

如果FP-Tree為空（只含一個虛的root節點），則FP-Growth函數返回。

此時輸出表頭項的每一項+postModel，支持度為表頭項中對應項的計數。

第四步：從FP-Tree中找出頻繁項。

遍歷表頭項中的每一項（我們拿“牛奶：6”為例），對于各項都執行以下（1）到（5）的操作：

（1）從FP-Tree中找到所有的“牛奶”節點，向上遍歷它的祖先節點，得到4條路徑：

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

對于每一條路徑上的節點，其count都設置為牛奶的count

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

因為每一項末尾都是牛奶，可以把牛奶去掉，得到條件模式基（Conditional Pattern Base,CPB），此時的后綴模式是：（牛奶）。

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

（2）我們把上面的結果當作原始的事務數據庫，返回到第3步，遞歸迭代運行。

沒講清楚，你可以參考這篇博客，直接看核心代碼吧：

public void FPGrowth(List<List<String>> transRecords,List<String> postPattern,Context context) throws IOException, InterruptedException {// 構建項頭表，同時也是頻繁1項集ArrayList<TreeNode> HeaderTable = buildHeaderTable(transRecords);// 構建FP-TreeTreeNode treeRoot = buildFPTree(transRecords, HeaderTable);// 如果FP-Tree為空則返回if (treeRoot.getChildren()==null || treeRoot.getChildren().size() == 0)return;//輸出項頭表的每一項+postPatternif(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);} }

對于FP-Tree已經是單枝的情況，就沒有必要再遞歸調用FPGrowth了，直接輸出整條路徑上所有節點的各種組合+postModel就可了。例如當FP-Tree為：

我們直接輸出：

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樹節點定義

+ View Code

挖掘頻繁模式

+ View Code

輸入文件

牛奶，雞蛋，面包，薯片 雞蛋，爆米花，薯片，啤酒 雞蛋，面包，薯片 牛奶，雞蛋，面包，爆米花，薯片，啤酒 牛奶，面包，啤酒 雞蛋，面包，啤酒 牛奶，面包，薯片 牛奶，雞蛋，面包，黃油，薯片 牛奶，雞蛋，黃油，薯片

輸出

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

用Hadoop來實現

在上面的代碼我們把整個事務數據庫放在一個List<List<String>>里面傳給FPGrowth，在實際中這是不可取的，因為內存不可能容下整個事務數據庫，我們可能需要從關系關系數據庫中一條一條地讀入來建立FP-Tree。但無論如何?FP-Tree是肯定需要放在內存中的，但內存如果容不下怎么辦？另外FPGrowth仍然是非常耗時的，你想提高速度怎么辦？解決辦法：分而治之，并行計算。

按照論文《FP-Growth 算法MapReduce?化研究》中介紹的方法，我們來看看語料中哪些詞總是經常出現，一句話作為一個事務，這句話中的詞作為項。

MR_FPTree.java

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 }

結束語

在實踐中，關聯規則挖掘可能并不像人們期望的那么有用。一方面是因為支持度置信度框架會產生過多的規則，并不是每一個規則都是有用的。另一方面大部分的關聯規則并不像“啤酒與尿布”這種經典故事這么普遍。關聯規則分析是需要技巧的，有時需要用更嚴格的統計學知識來控制規則的增殖。　

總結

以上是生活随笔為你收集整理的机器学习（十一）：FP-Tree算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。