0

我正在尝试在 Java 中实现 Apriori 算法，并且在生成候选项集时遇到问题。为了创建 k-itemset 的候选者，我使用了 k-1 和 1-itemset 的所有组合。例如，对于频繁的 1 项集：面包：9，牛奶：9，咖啡：9，糖：10。

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

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

我的代码：

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;
}

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

4

1 回答 1

1

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

至于您的代码中有重复的项目，您可以只在 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
    }
}

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

于 2020-01-03T12:08:53.780 回答