1 /** 2 * 3 * groups all Frequent Patterns containing an item and outputs the top K patterns 4 * containing that particular item 5 * 6 */ 7 public class AggregatorReducer extends Reducer<Text,TopKStringPatterns,Text,TopKStringPatterns> { 8 9 private int maxHeapSize = 50; 10 11 @Override 12 protected void reduce(Text key, Iterable<TopKStringPatterns> values, Context context) throws IOException, 13 InterruptedException { 14 TopKStringPatterns patterns = new TopKStringPatterns(); 15 for (TopKStringPatterns value : values) { 16 context.setStatus("Aggregator Reducer: Selecting TopK patterns for: " + key); 17 patterns = patterns.merge(value, maxHeapSize); 18 } 19 context.write(key, patterns); 20 21 } 22 23 @Override 24 protected void setup(Context context) throws IOException, InterruptedException { 25 super.setup(context); 26 Parameters params = new Parameters(context.getConfiguration().get("pfp.parameters", "")); 27 maxHeapSize = Integer.valueOf(params.get("maxHeapSize", "50")); 28 29 } 30 }
3. 讨论
并行化FP-Growth算法解决了大数据量时传统FP-Growth的性能瓶颈。除了并行化FP-Growth算法外，还有许多方法可以优化FP-Growth算法，比如并行化FP-Growth算法时考虑负载均衡，采用极大频繁项集和闭频繁项集表示频繁模式。
极大频繁项集
极大频繁项集是这样的频繁项集，它的直接超集都不是频繁的。极大频繁项集形成了可以导出所有频繁项集的最小项集集合，但是极大频繁项集却不包含它们子集的支持度信息。
闭频繁项集
如果项集的直接超集都不具有和它相同的支持度并且该项集的支持度大于或等于最小支持度阈值，则该项集是闭频繁项集。闭频繁项集提供了频繁项集的一种最小表示，该表示不丢失支持度信息。
4. 参考资料
[1] 关联分析：FP-Growth算法. Mark Lin. datahunter. 2014. [Link]
[2] PFP: Parallel FP-Growth for Query Recommendation. Haoyuan Li etc. RecSys '08 Proceedings of the 2008 ACM conference on Recommender systems. 2008. [PDF]