SPMF源码学习与总结——Apriori算法.pdfVIP

SPMF源码学习与总结——Apriori算法 ⾸先介绍下SPMF，SPMF是⼀个采⽤Java开发的开源数据挖掘平台。它提供了51种数据挖掘算法实现，⽤于： ·序列模式挖掘, ·关联规则挖掘， ·frequent itemset 挖掘, ·顺序规则挖掘， ·聚类 这⼏天放假研究了下Apriori算法的源代码，把总结写下，好记性不如⼀个烂笔头，防⽌以后忘。 Apriori算法的主要步骤： 数据读取 ⽣成频繁1项集 如何由频繁K-1项集⽣成候选Ck项集（候选项集内部剪枝：确保k阶候选项集的每⼀个k-1阶⼦集都是频繁的） 计数、剪枝⽣成频繁k项集 现在将以上步骤的核⼼源代码的注释和分析贴在下⾯，Apriori算法的源代码在此处下载（eclipse编译过，可⽤eclipse直接打开使⽤）： （1）数据读取 根据输⼊⽂件IO路径，按⾏读取⽂件，每⼀⾏按照空格“ ”分割，分割后存⼊数组中，然后存⼊map中，key是每⼀个项，value是key出 现的次数，即使⽀持度计数。通过这个操作，便可获得每⼀个项及其⽀持度，并且把数据库存⼊database中。输⼊⽂件为本地txt⽂件，内 容为 ： 1 3 4 2 3 5 1 2 3 5 2 5 1 2 3 5 MapInteger, Integer mapItemCount = new HashMapInteger, Integer(); database = new ArrayListint[](); BufferedReader reader = new BufferedReader(new FileReader(input)); String line; while (((line = reader.readLine()) != null)) { if (line.isEmpty() == true || line.charAt(0) == # || line.charAt(0) == % || line.charAt(0) == @) { continue; } String[] lineSplited = line.split( ); int transaction[] = new int[lineSplited.length]; for (int i=0; i lineSplited.length; i++) { Integer item = Integer.parseInt(lineSplited[i]); transaction[i] = item; Integer count = mapItemCount.get(item); if (count == null) { mapItemCount.put(item, 1); } else { mapItemCount.put(item, ++count); } } database.add(transaction); } （2）如何由频繁K-1项集⽣成候选Ck项集 当k=2时，由频繁1项集⽣成候选2项集。这个情况时⽐较简单，直接依次⽐较组合即可，源代码也是这么实现的，在⽣成候选项集前，对 候选项集进⾏排列，使后选项集按照字典序列排列： Collections.sort(frequent1, new ComparatorInteger() { public int compare(Integer o1, Integer o2) {