Post on 05-Apr-2015
transcript
ID3 vs. AprioriChristian Schulz, Marc Thielbeer, Sebastian Boldt
Inhaltsverzeichnis
1. Klassifikation ( ID3 )2. Assoziationsanalyse ( Apriori )3. Klassifikation anhand von Assoziationsregeln4. Realisierung in KNIME5. Probleme 6. Auswertung der Ergebnisse7. Zusammenfassung & Ausblick
Klassifikation• Zuordnung von Objekten mit gemeinsamen Eigenschaften zu Gruppen/Klassen • Im Gegensatz zum Clustering Klassen bereits bekannt• Erstellen von Klassifikationsregeln (z.B “guter Kunde” wenn Alter > 20 und …)• Verwendung von Stichproben (Trainigsdaten)
NAME RANK SKILL AGE
Peter 1 HIGH 18
Gustav 2 LOW 35
Harald 3 LOW 49
Trainingsdaten
If object.rank <= 1 && object.age <= 20{
object.skill = “High”}
Klassifikator
ID3-Algorithmus• Algorithmus der zur Entscheidungsfindung dient• Generierung von Entscheidungsbäumen• Iterative Basisstruktur• Für jedes nicht benutztes Attribut werden Entropien bezüglich der Traningsmenge berechnet• Aus Attribut mit höchsten Informationsgehalt wird Baumknoten generiert• Das Verfahren terminiert wenn alle Traningsmengen klassifiziert worden sind
Assoziationsanalyse• Assoziationsregeln beschreiben Korrelationen zwischen gemeinsam auftretenden Dingen • Zweck : Auffinden von Elementen einer Menge die das Auffinden anderer Elemente
implizieren• Beispielregel (Warenkorbanalyse): Kunden die Brot kaufen, werden mit einer
Wahrscheinlichkeit von 60 % auch Milch kaufen • Support & Konfidenz spielen wichtie Rolle
Apriori-Algorithmus• Iteratives Verfahren zur Erzeugung von Assoziationsregeln• Funktionsweise:• Übergabe von: Datensätzen, min. Support, min. Konfidenz • Bestimmung von Frequent Itemsets deren relative Häufigkeit min. Support übersteigt• Bildung von Assoziationsregeln aus Itemsets die min. Konfidenz erfüllen
Klassifikation anhand von Assoziationsregeln• Assoziationsregeln für die Klassifikation nutzen• Aufstellen der Assoziationsregeln (Apriori Algorithmus)• Klassifikation des Datensatzes anhand dieser Regeln
NAME RANK SKILL AGE
Peter 1 HIGH 18
Gustav 2 LOW 35
Harald 3 LOW 49
Trainingsdaten
If object.rank <= 1 && object.age <= 20{
object.skill = “High”}
Assoziationsregeln
Realisierung in Knime• Nutzung bestehender Bausteine (ID3 , Apriori , Decision Tree )• Vergleich von unterscheidlichen Datensätzen• Datenvorverarbeitung mittels bestimmter Module• Aufteilung von Daten in Trainings und Test-Daten• Ausgabe der Ergebnisse
Apriori in Knime• Auslesen der Daten über File Reader• Aufteilung der kontinuierlichen Größen in diskrete Werte mit Numeric Binner• Partionierung der Daten in Test und Trainingsdaten
Apriori in Knime• Manuelles Filtern der Relevanten Regeln• Eintragen in die Rule Engine
Apriori in Knime• Wenn Zielattribut kein boolscher Wert -> One2Many Element notwendig • Aufteilung jedes möglichen Wertes in einzelne Spalten mit boolschem Wert
ID3 & Decision Tree Knime• Einlesen der Daten über File-Reader• Aufteilung in Intervalle mittels Numeric Binner• Partionierung der Datensätze und Training und Testdaten• Vorhersage mittels Predictor
Vergleich der Genauigkeiten• Vergleich von 4 Datensätzen• Bei Klassenanzahl = 1 keine
gravierenden Unterscheide• Bei höherer Klassenanzahl bessere
Klassifizierung mittels Apriori• Bei großen Datensätzen zu hoher
Aufwand
Probleme• KNIME-Module bieten nicht die nötigen Ein & Ausgänge• Abbildung von numerischen Daten auf Intervalle• Abbildung dieser Intervalle auf boolsche Werte• Mit Anzahl der Klassen steigt der Konfigurationsaufwand in KNIME• A-Priori im Gegensatz zum ID3 unter Knime deshalb sehr aufwändig
Zusammenfassung & Ausblick• Zielstellung : Apriori Regeln für die Klassififkation von Daten besser geeignet als ID3 ?• Knime Module erweitern• Für Große Datensätze aufgrund des manuellen Zwischenschrittes in Knime momentan noch ungeeignet• Vergleichbare Ergebnisse der unterscheidlichen Ansätze• Bei höherer Anzahl von Klassen bessere Klassifizierung