(Java)生成关联规则的所有先行项

Question

例如，我可能有一个字符{a，B，C，G}的频繁项集。我需要生成关联规则的所有可能的前导。在这种情况下：ABC、ABG、ACG、AB、AC、AG、BC、BG、CG、A、B、C、G。我不知道从哪里开始做这件事。数小时的研究教会了我有关术语和概念的知识，但没有任何东西解释如何完成这一特定步骤。这就是我迄今为止对该方法的了解。项目集都以字符串的形式保存，并作为ArrayList存储在一起。我已经制作了一个用于生成频繁项集的Apriori算法。

public static ArrayList<String> associationRules(ArrayList<String> data, ArrayList<String> freqItemsets, int minConf){
ArrayList<String> generatedRules = new ArrayList<String>();
for(int i = 0; i < freqItemsets.size(); i++) {
String currentItemset = freqItemsets.get(i);
if(currentItemset.length() < 2) {
continue;
}

}


return null; // temporary return statement to avoid compile error
}

虽然关于这一步和以后的步骤的代码、反馈和建议当然会有很大帮助，但我真正需要的只是一个关于如何完成这一步的英文解释(而不是使用不同数据类型的伪代码或其他工作方法(。其他一切似乎都是可控的。

Answer 1

假设您确定了实际需要的定义(所有排序为原始列表的子集(，您可以通过将其视为那样并使用这些属性来实现这一点：

• 在您的列表中排序
• 有限的
• 可分割的

你所需要做的就是多次浏览你的角色列表，每次都根据每个角色来决定这次是包括它还是删除它。如果你浏览并捕捉到所有的可能性，那么你就完成了。要做到这一点，您应该找到一种可靠的方法来计算可能的结果字符串。

迭代解法

考虑可能的位状态。您有n个字符，并为每个字符分配一位(在您的情况下为4(。然后，每个可能的比特状态定义子集的合法排列，例如对于{A, B, C, G}:

1001将是AG

正如我们所知，比特集的所有可能状态都是"可计数的"，或者换句话说，你可以通过从最小状态到最高状态加1来计数。

进行一个从1到2^n-1的循环计数(其中n是您拥有的字符数(，然后通过添加(按正确顺序(所有以1为代表位的字符来构建String，并去掉带有0的字符。然后你"数"完所有可能的法律排列。

这样的实现在很大程度上取决于程序员和他们的风格，但对我来说，它看起来是这样的：

public static List<String> associationRules(List<String> elements) {
List<String> result = new ArrayList<>();
long limit = 1 << elements.size(); // thanks to saka1029 for this correction. My code was n^2 not 2^n.
// count from 1 to n^2 - 1
for (long i = 1; i < limit; ++i) {
StringBuilder seq = new StringBuilder();
// for each position (character) decide, whether to include it based on the state of the bit.
for (int pos = 0; pos < elements.size(); ++pos) {
boolean include = ((i >> pos) % 2) == 1; // this line will give you true, if the in 'i' the bit at 'pos' (from behind) is 1, and false otherwise.
if (include) {
seq.append(elements.get(pos));
}
}
// add to the final result the newly generated String.
result.add(seq.toString());
}
return result;
}

结果如下：[A, B, AB, C, AC, BC, ABC, G, AG, BG, ABG, CG, ACG, BCG, ABCG]

这是一个迭代(非递归(解决方案，但也有一个递归解决方案可能更容易实现(也可能不容易实现(。

递归解法

递归解决方案可以简单地通过创建一个方法来工作，该方法将一组排序字符和布尔状态(包括或不包括(作为参数，并返回所有可能的排序子项的列表。然后，您可以使用一个公共方法来调用它，该方法传递字符和0作为位置，true或false作为初始状态(另一个稍后出现(。

然后，这种方法适用于分而治之。在定义的位置包含字符(取决于是否设置了包含标志(，然后使用不包含第一个字符的克隆字符(子(集再次调用自己的方法。

让我们暂时假设，您从开始，而不是，包括每个序列的第一个字符(但后来包括它(。如果您将字符集{A, B, C, G}传递给这样一个方法，则该方法将(开始(如下操作：

A: recurse on {B, C, G}
B: recurse on {C, G}
C: recurse on {G}
G: set is empty,
G: Add to the result all Strings with 'G' prefixed and without.
G: return {"G", ""}
C: Add to the result all Strings with 'C' prefixed and without.
C: {"CG", "C", "G", ""}
...

通过这种方式，您将递归地收集所有排序的子集排列。根据是否允许空字符串，您可以在末尾删除它，也可以根本不添加它。

我是这样实现的，但还有其他正确的方法：

public static List<String> associationRules2(List<String> elements) {
List<String> result = new ArrayList<>();
String thisElement = elements.get(0);

// build the subset list (leaving out the first element
List<String> remaining = new ArrayList<>();
boolean first = true;
for (String s : elements) {
if (first) {
first = false;
} else {
remaining.add(s);
}
}

// if the subset is not empty, we recurse.
if (! remaining.isEmpty()) {
List<String> subPermutations = associationRules2(remaining);

// add all permutations without thisElement.
result.addAll(subPermutations);

// add all permutations *with* thisElement.
for (String s : subPermutations) {
result.add(thisElement + s);
}
}

// finally add thisElement on it's own.
result.add(thisElement);

return result;
}

结果：[G, CG, C, BG, BCG, BC, B, AG, ACG, AC, ABG, ABCG, ABC, AB, A]