Apriori算法中的候选集生成

Question

我正在尝试在 Java 中实现 Apriori 算法，但在生成候选项集时遇到了问题。为了创建 k-itemset 的候选项，我使用了 k-1 和 1-itemsets 的所有组合。例如，对于频繁 1 项集： bread:9、milk:9、coffee:9、sugar:10。

生成的候选2项集应该是：面包牛奶、面包咖啡、面包糖、牛奶咖啡、牛奶糖、咖啡糖。

但是我的代码returns：面包咖啡，面包牛奶，面包糖，咖啡面包，咖啡牛奶，咖啡糖，牛奶面包，牛奶咖啡，牛奶糖，糖面包，糖咖啡，糖牛奶（所有排列；returns面包牛奶和牛奶面包，但是，这两者是一回事。

我的代码：

public static ArrayList<ArrayList<String>> getCandidates(Map<String, Long> one_itemset_1, Map<String, Long> n_itemset_1){
    ArrayList<ArrayList<String>> tuples = new ArrayList<ArrayList<String>>();


    Map<String, Long> one_itemset = sortbykey(one_itemset_1);
    Map<String, Long> n_itemset = sortbykey(n_itemset_1);

    for(String item : one_itemset.keySet()) {

        for(String item2 : n_itemset.keySet()) {
            if(!item.equals(item2) && !item2.contains(item)) {
                ArrayList<String> singleList = new ArrayList<String>();
                singleList.add(item);
                String item2_sep[] = item2.split(" ");
                for(int i = 0; i < item2_sep.length; i++)
                    singleList.add(item2_sep[i]);
                //singleList.add(item2);
                tuples.add(singleList);
            }
            //index2++;
        }
        //index2 = 0;
        //index1++;
    }

    return tuples;
}

有没有办法修改此方法以摆脱重复的项目集？请指教。谢谢。

Answer 1

Apriori 算法不要求您在 Lk 和所有 1-项集之间进行连接以获得 Ck+1。这种方法将具有更高的运行时间。相反，我们在前 (k-1) 个元素在两个 k 项集中相同的条件下将 Lk 与其自身连接：see here

至于代码中有重复项，您可以只在 1 项中定义一个顺序 (I1 < I2 < I3 ... In) 然后只考虑升序（或降序）的项目。这将使项目集保持排序 -> (I1, I3, I5) 是一个有效的项目集但是 (I1, I5, I3 ) 不是。

对于您的示例，使用两个 for 循环可以轻松完成此操作：

for (int i=0; i<k-itemsets.size()-1; i++){
    for(int j=i+1; j<k-itemsets.size(); j++){
        // compare k-itemsets here and join in ascending order to produce k+1-itemset
    }
}

如果您一开始不了解该算法，我还建议您查看其他资源。例如，the SPMF library 实现了与模式挖掘相关的最流行算法。

Apriori算法中的候选集生成

Candidate set generation in Apriori algorithm

apriori

pattern-mining