(Java) Generieren Sie alle Antezedenzien einer Zuordnungsregel

Sep 29 2020

Zum Beispiel kann ich eine häufige Menge von Zeichen {A, B, C, G} haben. Ich muss alle möglichen Vorläufer von Assoziationsregeln generieren. In diesem Fall: ABC, ABG, ACG, AB, AC, AG, BC, BG, CG, A, B, C, G. Ich habe keine Ahnung, wo ich damit anfangen soll. Stundenlange Forschung hat mich über die Terminologie und das Konzept unterrichtet, aber nichts hat erklärt, wie man diesen bestimmten Schritt macht. Das habe ich bisher für die Methode. Die Itemsets werden alle in Form von Strings gespeichert und zusammen als ArrayList gespeichert. Ich habe bereits einen funktionierenden Apriori-Algorithmus für die Erzeugung häufiger Itemsets erstellt.

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
    }

Während Code, Feedback und Ratschläge zu diesem und späteren Schritten natürlich eine große Hilfe wären, brauche ich nur eine englische Erklärung, wie dieser eine Schritt ausgeführt wird (im Gegensatz zu Pseudocode oder einer anderen Arbeitsmethode mit unterschiedlichen Datentypen). Alles andere scheint überschaubar.

Antworten

3 TreffnonX Sep 29 2020 at 11:52

Angenommen, Sie haben die Definition dessen festgelegt, was Sie tatsächlich benötigen (alle Teilmengen, die als ursprüngliche Liste sortiert sind), können Sie dies tun, indem Sie sich das so vorstellen und die folgenden Eigenschaften verwenden:

  • sortiert wie in Ihrer Liste
  • endlich
  • teilbar

Alles, was Sie tun müssen, ist, Ihre Charakterliste mehrmals durchzugehen und jedes Mal pro Chrarakter zu entscheiden, ob Sie sie dieses Mal einfügen oder löschen möchten. Wenn Sie alle Möglichkeiten durchgehen und erfassen, sind Sie fertig. Um dies zu tun, sollten Sie einen soliden Weg finden, um durch die möglichen Ergebniszeichenfolgen zu zählen.

eine iterative Lösung

Denken Sie über mögliche Bitzustände nach. Sie haben n Zeichen und weisen jedem Zeichen ein Bit zu (in Ihrem Fall 4). Dann wird jeder möglicher Bit-Zustand definiert eine rechtliche Permutation einer Untergruppe, zB für {A, B, C, G}:

1001 wäre AG

Wie wir wissen, sind alle möglichen Zustände eines gesetzten Bits 'zählbar', oder mit anderen Worten, Sie können sie einfach durchzählen, indem Sie vom kleinsten zum höchsten Zustand zählen, indem Sie 1 addieren.

Machen Sie eine Schleife, die von 1 bis 2 ^ n - 1 zählt (wobei n die Anzahl der Zeichen ist, die Sie haben) und bauen Sie dann Ihre Stringauf, indem Sie (in der richtigen Reihenfolge) alle Zeichen hinzufügen, für die Sie eine 1 als Repräsentationsbit haben, und lassen Sie das Zeichen weg Zeichen mit einer 0. Dann 'zählen' Sie alle möglichen rechtlichen Permutationen durch.

Eine solche Implementierung hängt stark vom Programmierer und seinem Stil ab, aber für mich würde es ungefähr so ​​aussehen:

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

und das Ergebnis sieht so aus: [A, B, AB, C, AC, BC, ABC, G, AG, BG, ABG, CG, ACG, BCG, ABCG]

Dies ist eine iterative (nicht rekursive) Lösung, aber es gibt auch eine rekursive Lösung, die möglicherweise noch einfacher zu implementieren ist (oder auch nicht).

eine rekursive Lösung

Eine rekursive Lösung könnte einfach funktionieren, indem eine Methode erstellt wird, die eine Reihe sortierter Zeichen und einen booleschen Status (enthalten oder nicht enthalten) als Argumente verwendet und eine Liste aller möglichen sortierten Subpermutationen zurückgibt. Sie würden dies dann mit einer öffentlichen Methode aufrufen, die die Zeichen und 0als Position und entweder trueoder falseals Anfangszustand übergibt (der andere kommt später).

Die Methode arbeitet dann mit Teilen und Erobern. Sie fügen das Zeichen an der definierten Position ein (basierend darauf, ob das Include-Flag gesetzt ist oder nicht) und rufen die eigene Methode erneut mit einem geklonten Zeichensatz (Untersatz) auf, der das erste Zeichen nicht enthält.

Nehmen wir für den Moment an, dass Sie zunächst das erste Zeichen jeder Sequenz nicht einschließen (aber später einschließen). Wenn Sie den Zeichensatz an eine solche Methode übergeben {A, B, C, G}, funktioniert die Methode wie folgt:

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

Auf diese Weise erfassen Sie alle sortierten Teilmengenpermutationen rekursiv. Je nachdem, ob die leere Zeichenfolge zulässig ist, können Sie diese am Ende entfernen oder gar nicht hinzufügen.

Ich habe es so implementiert, aber es gibt andere richtige Wege:

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

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