(Java) Génère tous les antécédents d'une règle d'association

Question

Par exemple, je peux avoir un ensemble d'éléments fréquents de caractères {A, B, C, G}. J'ai besoin de générer tous les antécédents possibles des règles d'association. Dans ce cas: ABC, ABG, ACG, AB, AC, AG, BC, BG, CG, A, B, C, G. Je ne sais pas par où commencer. Des heures de recherche m'ont appris la terminologie et le concept, mais rien n'a expliqué comment faire cette étape particulière. C'est ce que j'ai jusqu'à présent pour la méthode. Les jeux d'éléments sont tous conservés sous la forme de chaînes et stockés ensemble en tant que ArrayList. J'ai déjà créé un algorithme Apriori fonctionnel pour la génération d'ensembles d'éléments fréquents.

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
    }

Bien que le code, les commentaires et les conseils sur cette étape et les étapes ultérieures soient bien sûr d'une grande aide, tout ce dont j'ai vraiment besoin est une explication en anglais de la façon de faire cette étape (par opposition au pseudocode ou à une autre méthode de travail utilisant différents types de données). Tout le reste semble gérable.

Answer 1

En supposant que vous ayez défini la définition de ce dont vous avez réellement besoin (tous les sous-ensembles triés comme la liste d'origine), vous pouvez le faire en pensant à cela et en utilisant ces propriétés:

• trié comme dans votre liste
• fini
• divisible

Tout ce que vous avez à faire est de parcourir votre liste de personnages plusieurs fois et à chaque fois de décider par caractère, de l'inclure cette fois ou de la supprimer. Si vous parcourez et capturez toutes les possibilités, vous avez terminé. Pour ce faire, vous devez trouver un moyen solide de compter les chaînes de résultats possibles.

une solution itérative

Pensez aux états binaires possibles. Vous avez n caractères et attribuez un peu chaque caractère (dans votre cas 4). Ensuite, chaque état binaire possible définit une permutation légale d'un sous-ensemble, par exemple pour {A, B, C, G}:

1001 serait AG

Comme nous le savons, tous les états possibles d'un ensemble de bits sont `` dénombrables '', ou en d'autres termes, vous pouvez simplement les compter en comptant du plus petit état au plus élevé en ajoutant 1.

Faites une boucle comptant de 1 à 2 ^ n - 1 (où n est le nombre de caractères que vous avez) puis construisez votre Stringen ajoutant (dans l'ordre correct) tous les caractères pour lesquels vous avez un 1 comme bit de représentation et omettez le caractères avec un 0. Ensuite, vous «comptez» à travers toutes les permutations légales possibles.

Une telle implémentation dépend fortement du programmeur et de son style, mais pour moi, cela ressemblerait à ceci:

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

et le résultat ressemble à ceci: [A, B, AB, C, AC, BC, ABC, G, AG, BG, ABG, CG, ACG, BCG, ABCG]

Il s'agit d'une solution itérative (non récursive), mais il existe également une solution récursive qui peut (ou non) être encore plus facile à implémenter.

une solution récursive

Une solution récursive pourrait simplement fonctionner en créant une méthode qui prend comme arguments un ensemble de caractères triés et un état booléen (inclus ou non inclus) et renvoie une liste de toutes les sous-permutations triées possibles. Vous appelleriez alors cela avec une méthode publique qui passe les caractères et 0comme position et soit trueou falsecomme état initial (l'autre vient plus tard).

La méthode fonctionne alors avec diviser pour conquérir. Vous incluez le caractère à la position définie (selon que l'indicateur d'inclusion est défini ou non) et appelez à nouveau la propre méthode avec un (sous) jeu de caractères cloné qui n'inclut pas le premier caractère.

Supposons pour le moment que vous commenciez par ne pas inclure le premier caractère de chaque séquence (mais par la suite l'inclure). Si vous passez à une telle méthode le jeu de caractères, {A, B, C, G}la méthode (commencerait) fonctionnerait comme ceci:

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", ""}
    ...

De cette façon, vous collecterez toutes les permutations de sous-ensembles triés de manière récursive. Selon que la chaîne vide est autorisée, vous pouvez la supprimer à la fin ou ne pas l'ajouter du tout.

Je l'ai implémenté comme ça, mais il existe d'autres moyens corrects:

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

Résultat: [G, CG, C, BG, BCG, BC, B, AG, ACG, AC, ABG, ABCG, ABC, AB, A]