java - (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 是您拥有的字符数)，然后构建您的 String通过添加(以正确的顺序)所有您将 1 作为其代表位的字符并省略带有 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]这是一种迭代(非递归)解决方案，但也有一个可能(或可能不会)更容易实现的递归解决方案。
递归解决方案
递归解决方案可以简单地通过创建一个方法来工作，该方法将一组排序字符和一个 boolean 状态(包括或不包括)作为参数并返回所有可能的排序子排列的列表。
然后，您将使用传递字符和 0 的公共(public)方法调用它。作为位置和 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]