Association Rules
• Ziel: finde interessante Verbindungen zwischen Variablen (Items oder Events)
• Nutzt ‚Unsupervised Learning‘
• Keine Output Variable
• Auch als Warenkorb-Analyse bekannt ( Bier und Windeln)
Input: Einfache Verkaufsstellen Transaktions Daten

Output: Meistens Verbindungen zwischen Gegenständen Repräsentative Anwendung von ARM beinhalten:
• In Unternehmen: cross-marketing, cross-selling, store design, catalog design, Webshop Design, Optimierung des Marketing, Pricing, Konfiguration…
• In Medizin: Zusammenhang zwischen Symptomen und Krankheit; Diagnose und Patientencharakteristika…
Example: {Laptop Computer, Antivirus Software}
=> {Extended Service Plan} [30%, 70%]
Kunden, die einen Laptop und Virenschutz zsm gekauft haben, haben in 70% der Fälle auch einen erweiterten Service Vertrag gekauft.
T=[{t1,t2,…,tn} Set aller Transaktionen
Jede Transaktion ti beinhaltet einen Datensatz mit Gegenständen aus I
Itemset I={i1,i2,,…,in}: Sammlung von einem oder mehrerer Gegenstände ‘Support Count’ Supp(….) eines Itemsets: Anzahl an enthaltenen Transaktionen. AR: z.B.: {Milk, Diaper} -> {Beer} X->Y
Support (s):
• Anteil der Transaktionen, die das Itemset beinhalten
• Regel mit wenig support wird wahrscheinlich durch puren Zufall bestimmt sein -> eliminieren
• Z.B.: s({Milk, Bread, Diaper}) = 2/5 = Supp/n
Confidence (c):
• Misst wie oft Y in Transaktionen vorkommt, die X enthalten => Abh. Wahrscheinlichkeit Y|X
• Misst die Zuverlässigkeit der Folgerung, die durch die Regel bestimmt wurde.

Ziel von ARM ist es für ein Set an Transaktionen T Regeln zu finden mit: support >= minsup Schwelle und confidence >= minconf Schwelle Brute-force Ansatz:
• Listet alle möglichen AR’s auf
• Berechnen s und c für jede Regel
• Streiche Regeln, die die minsup und minconf Schwelle nicht erreichen
Rechnerisch unerschwinglich ->Nützlich Regeln früh auszuschließen.
Ein erster Schritt die Leistung zu verbessern: Abkoppeln von s und c Anforderungen
Regeln, die aus dem gleichen Itemset kommen, haben alle den gleichen s aber andere c.
 Wenn das Itemset selten ist, können alle Regeln sofort ausgeschlossen werden ohne ihre C Werte zu berechnen
2- Schritte Ansatz:

1. Generierung häufiger Itemsets (erfüllen support >= minsup)
2. Regel Generierung (Regeln mit hoher c für jedes häufige Itemset, wobei jede Regel ein binärer Teil der häufigen Itemsets ist =>strong rules)
   Die Rechnungsanforderungen für die Generierung häufiger Itemsets sind teurer als für die Regel Generierung  Wir fokussieren uns zuerst auf die Generierung häufiger Itemsets
   Apriori Algorithm: Hilft häufige Itemsets zu identifizieren
   • Find Teilsätze, die für eine Mindestanzahl an Itemsets üblich sind
   • Dann, ‘bottom-up’ Ansatz:

o Häufige Teilsätze mit einem Item pro Schritt erweitert (Anfang: 1 Item pro Teilsatz)
o Gruppen an Kandidaten auf jedem Level gegen die Daten auf minsup getestet
• Apriori Prinzip:
o Wenn ein Itemset häufig ist, dann müssen alle Teilsätze häufig sein.
• Monotonie Eigenschaft von s:

Wegen dem Apriori Prinzip müssen wir nur dieses Triplet behalten, da es das einzige ist, in dem alle Teilsätze enthalten sind.

Entscheidungsbäume
Decision Tree Representation
• Z.b. dargestellt als Eigenschafts-Vektoren (Knoten testen die Eigenschaften, Äste als Wert jeder Eigenschaft, ‘Blätter’spezifizieren die Kategorie)
• Können beliebige Verbindungen oder Verknüpfungen darstellen. Außerdem als Klassifizierungsfunktion über jeden diskreten Eigenschaftsvektoren.
• Können als Set an Regeln geschrieben werden, z.B. disjunctive normal form (DNF).
• Belegstellen beschreibbar durch Paare an Attributwerten: e.g Humidity: High, Normal
• Zielfunktion ist diskret: e.g Play tennis; Yes, No
• Eine trennende Hypothese muss evt. genutzt werden: e.g Outlook=Sunny oder Wind=Weak
• Probleme: gestörte Trainingsdaten oder fehlende Attributwerte Lsg wurden entwickelt.
Eigenschaften:
• Kontinuierliche Eigenschaften können durch Aufteilen der Knoten in 2 verschiedene Bereiche (Länge kleiner 3 und Länge größer 3) verarbeitet werden.

• Klassifizierungsbäum e haben diskrete Klassenbeschreibungen an ihren Blättern,
Regressionsbäume erlauben ‚real-valued‘ Outputs an ihren Blättern.
• Algorithmen um konsistente Bäume zu finden sind effizient um große Mengen an Trainingsdaten zu verarbeiten.
Probleme:
Wie tief soll der Baum wachsen?
Wie werden nicht-diskrete Attribute behandelt?
Wie werden Attribute für Verzweigungen ausgewählt?
Wie werden Observationen mit fehlenden Attributwerten behandelt?
Vorteile:
Leicht zu Verstehen und zu interpretieren. Braucht nur wenige Beobachtungen
Wörter, beste und erwartete Werte können für verschiedene Szenarien bestimmt werden
Nachteile:
IG Kriterium ist verzerrt bei Attributen mit mehreren Leveln
Berechnungen werden komplex wenn die Werte unsicher und/oder die Ergebnisse verknüpft sind

Top-Dow Decision Tree Induktion

1. A -> ‘bestes’ Entscheidungsattribut für den nächsten Knoten
2. Weise A ein Entscheidungsattribut für den Knoten zu
3. Für jeden Wert von A wird ein ‚Nachfahre‘ kreiert
4. Sortiere die Trainingsbeispiele zum Blätterknoten nach dem Attributwert des Astes
5. Wenn alle Trainingsbeispiele perfekt klassifiziert wurden stoppe, sonst wiederhole den Vorgang über neue Blätterknoten.
   Anschließend wird ein Baum rekursiv nachgebaut

Entropy and Information Gain
Wählen einer guten Aufspaltungs-Eigenschaft:
• Ziel ist, dass der Baum so klein wie möglich bleibt,
• Bevorzuge die simpelste Hypothese, die die Daten beschreibt.
bessere Fähigkeit zur Verallgemeinerung und Anzahl an kurzen Hypothesen klein, ein Zufallstreffer auf eine kurze Hypothese ist damit unwahrscheinlich.
• Die Top-down Methode gibt einen simplen Baum, es muss jedoch nicht der kleinste sein.
• Wähle Eigenschaften, die Teilsätze an Beispielen erstellen, die relativ klar in einer einzigen Klasse sind und daher ‚näher‘ an den Blätterknoten liegen.
• Eine bekannte Entscheidungsregel basiert auf IG, ursprünglich aus dem ID3 System

Entropy
Anzahl benötigter bits, um die Klassen eines Beispiels S zu verschlüsseln (unter Verwendung eines kürzeren Codes für wahrscheinlichere Fälle)

• log2 p wobei p die Wahrscheinlichkeit ist, mit der jeder Wert auftreten kann. (log2=log(p)/log(2))

“Hohe Entropie”
• Gleichmäßige Verteilung von X mit flachem Histogramm.
• Probierte Werte weniger vorhersehbar

“Geringe Entropie”
• Verteilung und Histogramm von X mit vielen Höhen und Tiefen
• Probierte Werte besser vorhersehbar
Entropie-Verschlüsselungs-Algorithmus wird für verlustfreie Daten Komprimierung genutzt

Huffman Coding
Algorithmus:

1. Zähle das Vorkommen der Buchstaben des zu komprimierenden Textes
2. Priorisiere die Buchstaben basierend auf der Anzahl der Vorkommnisse
3. Baue den Huffman code Baum, auf der Prioritätsliste basierend
4. Wende ein Traversal des Baumes an, um alle Wörter zu codieren.
5. Scanne den Text erneut und erstelle einen neuen File unter Verwendung des Huffman codes Example: Eerie eyes seen near lake
   Häufigkeit aller Buchstaben im Text:

Information Gain
Definition:
Information Gain ist die Anzahl an durchschnittlich gesparter Bits, wenn wir Y übermitteln während Sender und Empfänger X kennen.
IG(Y|X) = Ich muss Y übermitteln.
Wie viele bits würde es durchschnittlich sparen wenn beide X kennen?
• IG(Y|X) = Entropy(Y) – Entropy(Y|X)
IG(Y|X) = 1 – 0.5 = 0.5