在關聯(lián)規(guī)則挖掘領域最經(jīng)典的算法法是Apriori，其致命的缺點是需要多次掃描事務數(shù)據(jù)庫。于是人們提出了各種裁剪（prune）數(shù)據(jù)集的方法以減少I/O開支，韓嘉煒老師的FP-Tree算法就是其中非常高效的一種。
支持度和置信度
嚴格地說Apriori和FP-Tree都是尋找頻繁項集的算法，頻繁項集就是所謂的“支持度”比較高的項集，下面解釋一下支持度和置信度的概念。
設事務數(shù)據(jù)庫為：
A E F GA F GA B E F GE F G則{A,F,G}的支持度數(shù)為3，支持度為3/4。
{F,G}的支持度數(shù)為4，支持度為4/4。
{A}的支持度數(shù)為3，支持度為3/4。
{F,G}=>{A}的置信度為：{A,F,G}的支持度數(shù) 除以 {F,G}的支持度數(shù)，即3/4
{A}=>{F,G}的置信度為：{A,F,G}的支持度數(shù) 除以 {A}的支持度數(shù)，即3/3
強關聯(lián)規(guī)則挖掘是在滿足一定支持度的情況下尋找置信度達到閾值的所有模式。
FP-Tree算法
我們舉個例子來詳細講解FP-Tree算法的完整實現(xiàn)。
事務數(shù)據(jù)庫如下，一行表示一條購物記錄：
我們的目的是要找出哪些商品總是相伴出現(xiàn)的，比如人們買薯片的時候通常也會買雞蛋，則[薯片，雞蛋]就是一條頻繁模式（frequent pattern）。
FP-Tree算法第一步：掃描事務數(shù)據(jù)庫，每項商品按頻數(shù)遞減排序，并刪除頻數(shù)小于最小支持度MinSup的商品。（第一次掃描數(shù)據(jù)庫）
薯片:7雞蛋:7面包:7牛奶:6啤酒:4 （這里我們令MinSup=3）
以上結果就是頻繁1項集，記為F1。
第二步：對于每一條購買記錄，按照F1中的順序重新排序。（第二次也是最后一次掃描數(shù)據(jù)庫）
第三步：把第二步得到的各條記錄插入到FP-Tree中。剛開始時后綴模式為空。
插入第一條（薯片,雞蛋,面包,牛奶）之后
插入第二條記錄（薯片,雞蛋,啤酒）
插入第三條記錄（面包,牛奶,啤酒）
估計你也知道怎么插了，最終生成的FP-Tree是：
上圖中左邊的那一叫做表頭項，樹中相同名稱的節(jié)點要鏈接起來，鏈表的第一個元素就是表頭項里的元素。
如果FP-Tree為空（只含一個虛的root節(jié)點），則FP-Growth函數(shù)返回。
此時輸出表頭項的每一項+postModel，支持度為表頭項中對應項的計數(shù)。
第四步：從FP-Tree中找出頻繁項。
遍歷表頭項中的每一項（我們拿“牛奶：6”為例），對于各項都執(zhí)行以下（1）到（5）的操作：
（1）從FP-Tree中找到所有的“牛奶”節(jié)點，向上遍歷它的祖先節(jié)點，得到4條路徑：
薯片：7，雞蛋：6，牛奶：1薯片：7，雞蛋：6，面包：4，牛奶：3薯片：7，面包：1，牛奶：1面包：1，牛奶：1
對于每一條路徑上的節(jié)點，其count都設置為牛奶的count
薯片：1，雞蛋：1，牛奶：1薯片：3，雞蛋：3，面包：3，牛奶：3薯片：1，面包：1，牛奶：1面包：1，牛奶：1
因為每一項末尾都是牛奶，可以把牛奶去掉，得到條件模式基（Conditional Pattern Base,CPB），此時的后綴模式是：（牛奶）。
（2）我們把上面的結果當作原始的事務數(shù)據(jù)庫，返回到第3步，遞歸迭代運行。
沒講清楚，你可以參考這篇博客，直接看核心代碼吧：
對于FP-Tree已經(jīng)是單枝的情況，就沒有必要再遞歸調用FPGrowth了，直接輸出整條路徑上所有節(jié)點的各種組合+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實現(xiàn)
FP樹節(jié)點定義
挖掘頻繁模式
輸入文件
牛奶，雞蛋，面包，薯片雞蛋，爆米花，薯片，啤酒雞蛋，面包，薯片牛奶，雞蛋，面包，爆米花，薯片，啤酒牛奶，面包，啤酒雞蛋，面包，啤酒牛奶，面包，薯片牛奶，雞蛋，面包，黃油，薯片牛奶，雞蛋，黃油，薯片輸出
6 薯片 雞蛋5 薯片 面包5 雞蛋 面包4 薯片 雞蛋 面包5 薯片 牛奶5 面包 牛奶4 雞蛋 牛奶4 薯片 面包 牛奶4 薯片 雞蛋 牛奶3 面包 雞蛋 牛奶3 薯片 面包 雞蛋 牛奶3 雞蛋 啤酒3 面包 啤酒
用Hadoop來實現(xiàn)
在上面的代碼我們把整個事務數(shù)據(jù)庫放在一個List<List<String>>里面?zhèn)鹘oFPGrowth，在實際中這是不可取的，因為內存不可能容下整個事務數(shù)據(jù)庫，我們可能需要從關系關系數(shù)據(jù)庫中一條一條地讀入來建立FP-Tree。但無論如何 FP-Tree是肯定需要放在內存中的，但內存如果容不下怎么辦？另外FPGrowth仍然是非常耗時的，你想提高速度怎么辦？解決辦法：分而治之，并行計算。
按照論文《FP-Growth 算法MapReduce 化研究》中介紹的方法，我們來看看語料中哪些詞總是經(jīng)常出現(xiàn)，一句話作為一個事務，這句話中的詞作為項。
MR_FPTree.java
import imdm.bean.TreeNode;import ioformat.EncryptFieInputFormat;import java.io.IOException;import java.text.SimpleDateFormat;import java.util.ArrayList;import java.util.Calendar;import java.util.Collections;import java.util.Comparator;import java.util.LinkedHashMap;import java.util.LinkedList;import java.util.List;import org.apache.hadoop.conf.Configuration;import org.apache.hadoop.fs.FSDataInputStream;import org.apache.hadoop.fs.FileSystem;import org.apache.hadoop.fs.Path;import org.apache.hadoop.io.IntWritable;import org.apache.hadoop.io.LongWritable;import org.apache.hadoop.io.Text;import org.apache.hadoop.mapreduce.Job;import org.apache.hadoop.mapreduce.Mapper;import org.apache.hadoop.mapreduce.Reducer;import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;import org.apache.hadoop.util.GenericOptionsParser;import org.apache.hadoop.util.LineReader;import org.wltea.analyzer.dic.Dictionary;import text.outservice.WordSegService;public class MR_FPTree { private static final int minSuport = 30; // 最小支持度 public static class GroupMapper extends Mapper<LongWritable, Text, Text, Text> { LinkedHashMap<String, Integer> freq = new LinkedHashMap<String, Integer>(); // 頻繁1項集 org.wltea.analyzer.cfg.Configuration cfg = null; Dictionary ikdict = null; /** * 讀取頻繁1項集 */ @Override public void setup(Context context) throws IOException { // 初始化IK分詞器 cfg = org.wltea.analyzer.cfg.DefaultConfig.getInstance(); ikdict = Dictionary.initial(cfg); // 從HDFS文件讀入頻繁1項集，即讀取IMWordCount的輸出文件，要求已經(jīng)按詞頻降序排好 Configuration conf = context.getConfiguration(); FileSystem fs = FileSystem.get(conf); Calendar cad = Calendar.getInstance(); cad.add(Calendar.DAY_OF_MONTH, -1); // 昨天 SimpleDateFormat sdf = new SimpleDateFormat("yyyyMMdd"); String yes_day = sdf.format(cad.getTime()); Path freqFile = new Path("/dsap/resultdata/content/WordCount/" + yes_day + "/part-r-00000"); FSDataInputStream fileIn = fs.open(freqFile); LineReader in = new LineReader(fileIn, conf); Text line = new Text(); while (in.readLine(line) > 0) { String[] arr = line.toString().split("\\s+"); if (arr.length == 2) { int count = Integer.parseInt(arr[1]); // 只讀取詞頻大于最小支持度的 if (count > minSuport) { String word = arr[0]; freq.put(word, count); } } } in.close(); } @Override public void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException { String[] arr = value.toString().split("\\s+"); if (arr.length == 4) { String content = arr[3]; List<String> result = WordSegService.wordSeg(content); List<String> list = new LinkedList<String>(); for (String ele : result) { // 如果在頻繁1項集中 if (freq.containsKey(ele)) { list.add(ele.toLowerCase()); // 如果包含英文字母，則統(tǒng)一轉換為小寫 } } // 對事務項中的每一項按頻繁1項集排序 Collections.sort(list, new Comparator<String>() { @Override public int compare(String s1, String s2) { return freq.get(s2) - freq.get(s1); } }); /** * 比如對于事務(中國，人民，人民，廣場)，輸出(中國，人民)、(中國，人民，廣場) */ List<String> newlist = new ArrayList<String>(); newlist.add(list.get(0)); for (int i = 1; i < list.size(); i++) { // 去除list中的重復項 if (!list.get(i).equals(list.get(i - 1))) { newlist.add(list.get(i)); } } for (int i = 1; i < newlist.size(); i++) { StringBuilder sb = new StringBuilder(); for (int j = 0; j <= i; j++) { sb.append(newlist.get(j) + "\t"); } context.write(new Text(newlist.get(i)), new Text(sb.toString())); } } } } public static class FPReducer extends Reducer<Text, Text, Text, IntWritable> { public void reduce(Text key, Iterable<Text> values, Context context) throws IOException, InterruptedException { List<List<String>> trans = new LinkedList<List<String>>(); // 事務數(shù)據(jù)庫 while (values.iterator().hasNext()) { String[] arr = values.iterator().next().toString() .split("\\s+"); LinkedList<String> list = new LinkedList<String>(); for (String ele : arr) list.add(ele); trans.add(list); } List<TreeNode> leafNodes = new LinkedList<TreeNode>(); // 收集FPTree中的葉節(jié)點 buildFPTree(trans, leafNodes); for (TreeNode leaf : leafNodes) { TreeNode tmpNode = leaf; List<String> associateRrule = new ArrayList<String>(); int frequency = 0; while (tmpNode.getParent() != null) { associateRrule.add(tmpNode.getName()); frequency = tmpNode.getCount(); tmpNode = tmpNode.getParent(); } // Collections.sort(associateRrule); //從根節(jié)點到葉節(jié)點已經(jīng)按F1排好序了，不需要再排序了 StringBuilder sb = new StringBuilder(); for (String ele : associateRrule) { sb.append(ele + "|"); } // 因為一句話可能包含重復的詞，所以即使這些詞都是從F1中取出來的，到最后其支持度也可能小于最小支持度 if (frequency > minSuport) { context.write(new Text(sb.substring(0, sb.length() - 1) .toString()), new IntWritable(frequency)); } } } // 構建FP-Tree public TreeNode buildFPTree(List<List<String>> records, List<TreeNode> leafNodes) { TreeNode root = new TreeNode(); // 創(chuàng)建樹的根節(jié)點 for (List<String> record : records) { // 遍歷每一項事務 // root.printChildrenName(); insertTransToTree(root, record, leafNodes); } return root; } // 把record作為ancestor的后代插入樹中 public void insertTransToTree(TreeNode root, List<String> record, List<TreeNode> leafNodes) { if (record.size() > 0) { String ele = record.get(0); record.remove(0); if (root.findChild(ele) != null) { root.countIncrement(1); root = root.findChild(ele); insertTransToTree(root, record, leafNodes); } else { TreeNode node = new TreeNode(ele); root.addChild(node); node.setCount(1); node.setParent(root); if (record.size() == 0) { leafNodes.add(node); // 把葉節(jié)點都放在一個鏈表中 } insertTransToTree(node, record, leafNodes); } } } } public static void main(String[] args) throws IOException, InterruptedException, ClassNotFoundException { Configuration conf = new Configuration(); String[] argv = new GenericOptionsParser(conf, args).getRemainingArgs(); if (argv.length < 2) { System.err .println("Usage: MR_FPTree EcryptedChartContent AssociateRules"); System.exit(1); } FileSystem fs = FileSystem.get(conf); Path inpath = new Path(argv[0]); Path outpath = new Path(argv[1]); fs.delete(outpath, true); Job FPTreejob = new Job(conf, "MR_FPTree"); FPTreejob.setJarByClass(MR_FPTree.class); FPTreejob.setInputFormatClass(EncryptFieInputFormat.class); EncryptFieInputFormat.addInputPath(FPTreejob, inpath); FileOutputFormat.setOutputPath(FPTreejob, outpath); FPTreejob.setMapperClass(GroupMapper.class); FPTreejob.setMapOutputKeyClass(Text.class); FPTreejob.setMapOutputValueClass(Text.class); FPTreejob.setReducerClass(FPReducer.class); FPTreejob.setOutputKeyClass(Text.class); FPTreejob.setOutputKeyClass(IntWritable.class); FPTreejob.waitForCompletion(true); }}結束語
在實踐中，關聯(lián)規(guī)則挖掘可能并不像人們期望的那么有用。一方面是因為支持度置信度框架會產(chǎn)生過多的規(guī)則，并不是每一個規(guī)則都是有用的。另一方面大部分的關聯(lián)規(guī)則并不像“啤酒與尿布”這種經(jīng)典故事這么普遍。關聯(lián)規(guī)則分析是需要技巧的，有時需要用更嚴格的統(tǒng)計學知識來控制規(guī)則的增殖。
