(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

假设您确定了实际需要的定义（按原始列表排序的所有子集），您可以通过考虑它并使用这些属性来做到这一点：

按照您的列表排序
有限
可分割

所有你需要做的就是多次浏览你的角色列表，每次决定每个角色，这次是包含它还是放弃它。如果您遍历并捕获所有可能性，那么您就完成了。为此，您应该找到一种可靠的方法来计算可能的结果字符串。

迭代解决方案

想想可能的 bit-states。您有 n 个字符并为每个字符分配一点（在您的情况下为 4）。然后每个可能的 bit-state 定义一个子集的合法排列，例如{A, B, C, G}:

1001 将是 AG

我们知道，一个bit set所有可能的状态都是'countable'，也就是说，从最低的状态到最高的状态加1就可以算完了。

创建一个从 1 到 2^n - 1 的循环（其中 n 是您拥有的字符数），然后通过添加（以正确的顺序）您拥有的所有字符来构建您的 String a 1 作为它们的代表位，并用 0 省略字符。然后你 'count' 通过所有可能的合法排列。

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

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]

这是一个迭代 (non-recursive) 解决方案，但还有一个递归解决方案可能（或可能不）更容易实现。

一个递归的解决方案

递归解决方案可以简单地通过创建一个方法来工作，该方法将一组排序的字符和一个布尔状态（包括或不包括）和 returns 所有可能的排序子排列的列表作为参数。然后，您将使用 public 方法调用它，该方法传递字符和 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]

(Java) 生成关联规则的所有前因

(Java) Generate all antecedents of an association rule

java

data-mining

apriori

迭代解决方案

一个递归的解决方案