Business & Competitive Intelligence Systems - Data Mining

Data Mining

Einführung

Data Mining bezeichnet das Entdecken interessanter Zusammenhänge und Trends in Daten mittels Mustererkennung sowie statistischer und mathematischer Verfahren.

Knowledge Discovery in Databases (KDD)
’Knowledge Discovery in Databases is the non-trivial process of identifying valid, novel, potentially useful, and ultimately understandable patterns in data’
’Data Mining is a step in the KDD process consisting of applying data analysis and discovery algorithms that, under acceptable computational efficiency limitations, produce a particular enumeration of patterns over the data’

Phasen des KDD-Prozesses

Phasen des KDD-Prozesses:

• Selektion: Hierbei erfolgt die Auswahl relevanter Daten einer Datenbasis.
• Preprocessing (Vorverarbeitung): Während dieses Schrittes werden Störungen wie Datenfehler oder Unvollständigkeit entfernt (Data Cleaning). Dieser Schritt entfällt unter Umständen bei Verwendung eines DWH als Datenquelle.
• Transformation: In dieser Phase wird die Quantität der Daten durch Entfernung von Attributen ohne oder mit geringem Vorkommen in der Datenbasis verringert. Zusätzlich werden die Daten in eine geeignete Analyseform transformiert.
• Data Mining (Kern des KDD-Prozesses): Hierbei kommen die eigentlichen Data-Mining-Techniken (Verfahren aus der Statistik und aus dem maschinellen Lernen) zum Einsatz.
• Interpretation/Evaluation: Das Problem bei der Interpretation/Evaluation besteht darin, dass viele der erkannten Muster uninteressant und unpräzise sind.

Cross-Industry Standard Process for Data Mining (CRISP-DM)
Der Cross-Industry Standard Process for Data Mining (CRISP-DM) stellt ein im Rahmen eines EU-Projektes entwickeltes Data-Mining-Prozessmodell dar. Initiatoren hierbei waren unter anderem DaimlerCrysler, Integral Solutions Ltd. und NCR/Teradata.
CRISP-DM teilt den Data-Mining-Prozess in sechs Phasen ein, nach denen man sich bei der Planung und Durchführung des Data-Mining-Projekts richten kann. CRISP-DM ist dabei breiter als das sich auf Technik fokussierende KDD-Prozessmodell.

Phasen des KDD-Prozesses

Die einzelen Phasen des CRISP-DM stellen sich wie folgt dar:

1. Business Understanding: In dieser Phase wird die Projektzielsetzung aus fachlicher Sicht festgelegt und die für die ausgemachte Problemstellung geeigneten Data-Mining-Techniken identifiziert.
2. Data Understanding: Hier werden Daten gesammelt, beschrieben und gesichtet. Darüber hinaus wird in dieser Phase zusätzlich die Datenqualität analysiert.
3. Data Preparation: Hierbei werden die Rohdaten so aufbereitet, wie sie für die Datenanalyse und für die Data Mining Tools benötigt werden
4. Modeling: In dieser Phase werden die ausgemachten Data-Mining-Techniken auf die Daten angewendet und die Parameter neu kalibiert. Bei Abweichungen erfolgt unter Umständen eine Rückkehr zu Phase 3.
5. Evaluation: Während der Evaluation wird das entwickelte Modell getestet und Entscheidungen bezüglich der Verwendung des Data-Mining-Ergebnisses getroffen.
6. Deployment: Hier wird der Plan für die Verwendung des entwickelten Modells, z.B. in einem operativen Softwaresystem, erstellt.

Aufgaben und Output im CRISP-DM-Referenzmodell

Data Mining/KDD kann als interdisziplinäre Wissenschaft bezeichnet werden. Im Data Mining/KDD treffen unter Anderem Methoden aus dem Bereich der Statistik, dem Bereich der Datenbanken oder dem Gebiet der künstlichen Intelligenz aufeinander.

Data Mining/KDD als interdisziplinäre Wissenschaft

Ziele des Data Mining
Allgemein besteht das Ziel des Data Mining in der Erkennung von Strukturen und Mustern anhand von Beispielen, um zukünftige Ergebnisse vorherzusagen oder Muster beschreiben bzw. erklären zu können, woraus sich eine Prognose ableitet. Die Trennung ist jedoch zum Teil unscharf, da z.B. eine Abhängigkeitsanalyse auch der Vorhersage dienen kann oder eine Klassifikation der Konzeptbeschreibung.

Ziele des Data Mining

Die Data-Mining-Ziele/-Methoden lassen sich wie folgt beschreiben:

• Segmentierung/Clustering: Einteilung der Datenmenge in Gruppen (sog. Cluster) mit für diese Gruppe charakteristischen Attributwerten. Oft Kombination mit anderen Verfahren.
• Klassifikation: Dient der Modellierung eines Klassifikators (a priori durch Trainingsdaten gegeben oder durch Clustering ermittelt). Beispiele sind Entscheidungsbäume und –regeln. Kann auch ein Beschreibungsziel verfolgen, z.B. Beschreibung der Konzepte ’treuer Kunde’ und ’untreuer Kunde’
• Numerische Prognose: Vorhersage von numerischen Attributwerten. Ähnelt einer Klassifikation (mit numerischen ’Klassen’).
• Abhängigkeitsanalyse: Auffinden signifikanter Abhängigkeiten zwischen Attributen. Klassisches Beispiel: Warenkorbanalyse
• Sequenzanalyse: Erweiterung der Abhängigkeitsanalyse durch Beachtung von zeitlichen Beziehungen. z.B. Produktsequenzen bei der Warenkorbanalyse.
• Abweichungsanalyse: Auffinden von ’abweichenden Instanzen’ (Ausreißern). z.B. zur Erkennung von fehlerhaften Daten.

Data Mining wird in vielfältigen Bereichen eingesetzt. Darunter gehören z.B. die Bearbeitung von Kreditanträgen, Risikoabschätzungen, die Erkennung von Versicherungsbetrug, die Lastvorhersage bei Stromversorgern oder im Telekommunikationsbereich oder auch diverse Bereiche im Marketing oder Customer Relationship Management. Weiterhin zählt auch die Anreicherung neu hinzuzufügender Daten oder die Unterstützung bei der Datenbereinigung im Zuge des ETL-Prozesses beim Data-Warehousing dazu.
Ein Beispiel ist die Bearbeitung von Kreditanträgen. Wenn man einen Kredit beantragen möchte, muss man zuerst einen Fragebogen mit relevanten finanziellen und persönlichen Informationen ausfüllen.
Dieser Fragebogen stellt die Grundlage für die Bewilligung oder die Ablehnung des Kredites dar. In 90% der Fälle kann durch eine einfache statistische Methode eine klare Entscheidung getroffen werden.
Die verbleibenden Grenzfälle werden von Sachbearbeiter*innen entschieden. Hierbei zeigen Untersuchungen, dass 50% der akzeptierten Grenzfälle jedoch in Zahlungsverzug geraten.
Eine komplette Ablehnung aller Grenzfälle stellt jedoch keine hinreichende Lösung dar, da Grenzfälle die aktivste Kund*innenguppe darstellen. Die Lösung des Problems wird durch maschinelles Lernen erreicht. Als Eingabe dienen 1000 Trainingsbeispiele von Grenzfällen mit 20 Attributen, wie unter anderem Alter, Jahre bei der/m momentanen Arbeitgeber*in, Jahre bei der aktuellen Adresse, Jahre bei der Bank oder Besitz anderer Kreditkarten.
Das Ergebnis dieses Lernprozesses stellt ein kleines Regelset dar, mit Hilfe dessen sich 2/3 der Grenzfälle korrekt prognostizieren lassen. Ein zusätzlicher Nebeneffekt besteht darin, dass die Regeln dazu genutzt werden können um den Kund*innen eine ablehnende Entscheidung zu erklären.
Ein weiteres Beispiel ist die Lastabschätzung bei Stromversorgern. Stromversorger benötigen eine Vorhersage für den zukünftigen Strombedarf, da korrekte Vorhersagen von minimaler und maximaler Last für jede Stunde immense Einsparungen ermöglichen.
Grundlage dieser Vorhersage war zunächst ein statisches Lastmodell, welches sich auf die letzten 15 Jahre bezieht, von normalen klimatischen Bedingungen ausgeht und sowohl aus Basislast des Jahres, Lastperiodizität über das Jahr als auch aus den Auswirkungen an Feiertagen besteht.
Eine Verfeinerung des Modells bestand darin, dass man klimatische Bedingungen mit in Betracht zog und die Prognose durch die Verwendung der ’ähnlichsten Tage’ der Vergangenheit korrigierte. Das statische Modell wurde hierbei um die durchschnittliche Abweichung der acht ähnlichsten Tage angepasst.
Weiterhin wurde eine Datenbank mit den Attributen Temperatur, Luftfeuchtigkeit, Windgeschwindigkeit und Messungen der Wolkendecke der letzten 15 Jahre, zusammen mit der Differenz zwischen tatsächlicher und prognostizierter Last angelegt.
Die Koeffizienten einer durchgeführten linearen Regressionsanalyse ergeben die Gewichte in der Ähnlichkeitsfunktion.
Das Resultat war, dass das neue System bei gleicher Performanz wesentlich weniger Zeit als ausgebildete menschliche Wetterexpert*innen zum Berechnen der Vorhersage benötigte.

Anwendungen im Marketing:

• Kund*innentreue: Durch die Erkennung von Veränderungen in ihrem Verhalten (z.B. bei Banken, Telefongesellschaften) lassen sich potenziell abspringende Kund*innen identifizieren.
• Spezielle Angebote: Identifizierung von profitträchtigen Kund*innen (z.B. zuverlässige Besitzer*innen von Kreditkarten, die zusätzliches Geld in der Weihnachtszeit benötigen)
• Warenkorbanalyse: Abhängigkeitsanalyse, um Gruppen von Produkten zu finden, die oft zusammen in einer Transaktion vorkommen (meist Analyse von Kassenbondaten).

Weitere Anwendungen:

• Sport: IBM Advanced Scout analysierte NBA-Spielestatistiken (Blocks, Fouls, etc.), um Vorteile für die New York Knicks und Miami Heat zu erreichen.
• Astronomie: JPL und das Palomar Observatory entdeckten mit der Hilfe von Data Mining 22 neue ’Quasare’.
• Web-Log Mining: Anwendung von Data-Mining-Algorithmen auf Web-Zugriffslogs zur Analyse des Navigationsverhaltens für die Verbesserung der Sitestruktur.

Die Verwendung von Daten, insbesondere von personenbezogenen Daten, für Data Mining bringt ernsthafte ethische Folgeerscheinungen mit sich. Während beispielsweise Informationen wie Geschlecht, Religion oder Abstammung bei den Entscheidungen über Kreditanträge zu Diskriminierungen führen können, sind die gleichen Informationen in medizinischen Anwendungen unproblematisch.
Ein weiterer Aspekt ist, dass Attribute indirekt problematische Informationen enthalten können. Zum Beispiel können durch Postleitzahlen eventuelle Rückschlüsse auf die Abstammung gezogen werden (z.B. Wohngebiete mit hohem Ausländer*innenanteil).
In Bezug auf die ethischen Aspekte müssen in der Praxis wichtige Fragen gestellt werden und die Ergebnisse von Analysen mit entsprechenden Warnungen versehen werden:

• Zu welchem Zweck wurden die Daten gesammelt?
• Wer hat Zugriff auf die Ergebnisse?
• Welche Schlussfolgerungen können letztendlich aus den Ergebnissen gezogen werden?

Hierbei ist anzumerken, dass statistische Argumente niemals ausreichend sein können. Ein verwandtes Problem findet sich im Bereich des Datenschutzes wieder.
Der Fokus liegt im Folgenden auf ausgewählten Data-Mining-Zielen und -Methoden wie der Klassifikation, der Abhängigkeitsanalye, der Methode des Clusterings und der nummerischen Prognose. Die Beispieldaten zu den aufgeführten Zielen und Methoden entstammen größtenteils dem UCI Machine Learning Repository .

Daten

Ziele/Methoden des Data Mining

Vorbereitung

Unter Datenvorbereitung versteht man die Bereitstellung des Inputs für die Ausführung von Data-Mining-Algorithmen. Die Datenvorbereitung stellt den aufwendigsten Teil im Data Mining Prozess dar.
Es existieren verschiedene Typen an Output für verschiedene Lernprobleme (z.B. Klassifikation). Daher werden die Darstellungsformen zusammen mit den Methoden und Algorithmen behandelt.

Datenvorbereitung im Data-Mining-Prozess

Unter einer Instanz versteht man einen spezifischen Typ eines Beispiels, einen individuellen, unabhängigen Beispieldatensatz, der von einer bestimmten Menge an Attributen charakterisiert wird.
Eine Menge von Instanzen bzw. Datensätzen stellen den Input eines Data Mining Algorithmus (Learning Scheme) dar. Die Datensätze bzw. Instanzen werden zuvor denormalisiert (d.h. mehrere Relationen werden per Join verbunden) und danach als eine einzige Relation bzw. als Flatfile repräsentiert.
Problematisch hierbei ist, dass diese Denormalisierung zu Scheinunregelmäßigkeiten führen kann, die nur die Datenbankstruktur widerspiegeln (Beispiel: ’Lieferant’ prognostiziert ’Lieferantenadresse’).
Jede Instanz wird durch eine feste, vordefinierte Menge von Merkmalen, den sogenannten ’Attributen’, beschrieben. Die Anzahl dieser Attribute kann in der Praxis variieren. Eine mögliche Lösung bietet hier ein ’irrelevant’ Flag (siehe unten ’missing’ für fehlende Werte). Ein verwandtes Problem hierzu ist, dass die Existenz eines Attributes von dem Wert eines anderen abhängen kann.
Mögliche Attributtypen (’Skalentypen’) sind Nominal-, Ordinal-, Intervall- und Verhältnismaßzahlen.

Nominalwerte (lateinisch ’nomen’ = Name) sind unterschiedliche Symbole wobei die Werte selbst nur als Namen dienen. Zwischen den Nominalwerten bestehen keinerlei Beziehungen, weder Reihenfolge noch Distanzgröße und sie können nur auf Gleichheit getestet werden. Beispiel: Attribut ’outlook’ der Wetterdaten mit den Werten ’sunny’, ’overcast’ und ’rainy’.
Bei Ordinalwerten gibt es eine definierte Reihenfolge, aber keine Definition einer Distanz zwischen den Werten. Zusätzlich sei noch angemerkt, dass weder Addition noch Subtraktion sinnvoll ist.

Beispiel: Attribut ’temperature’ in den Wetterdaten oder die definierte Reihefolge der Werte: hot > mild > cool.
Beispielregel:

Weiterhin ist eine Unterscheidung zwischen nominal und ordinal nicht immer klar nachvollziehbar. So kann z.B. argumentiert werden, dass die Nominalwerte des verwendeten Beispiels ’outlook’ eine Ordnung aufweisen und somit als Ordinalwerte angesehen werden können. Overcast kann hierbei als Übergang zwischen ’sunny’ und ’rainy’ gesehen werden, d.h.: sunny > overcast > rainy.

Intervallmaßzahlen sind nicht nur geordnet, sondern werden in festen, gleichen Einheiten gemessen. Ein Beispiel für Intervallmaßzahlen stellen Jahreszahlen dar. Dabei macht es Sinn, sich über die Differenz zwischen zwei Jahreszahlen Gedanken zu machen (z.B. Differenz zwischen 1960 und 1976 -> 16 Jahre). Eine Summe oder ein Produkt macht hingegen keinen Sinn (z.B. 1960 + 1976 = 3936). Zudem gibt es bei Intervallmaßzahlen keinen Nullpunkt.
Verhältnismaßzahlen werden als reelle Zahlen gehandhabt, auf denen alle mathematischen Operationen erlaubt sind. Zudem definiert diese Maßmethode einen Nullpunkt. Die Frage nach einem von Natur aus gegebenen Nullpunkt erfordert jedoch (wissenschaftliches) Domänenwissen (z.B. kannte Fahrenheit keine untere Temperaturgrenze). Beispiel: Attribut ’distance’. Die Distanz zwischen einem Objekt und sich selbst ist Null.
Die meisten Data Mining Algorithmen (Learning Schemes) unterscheiden nur zwei Typen von Attributen: nominal und ordinal. Nominale Attribute werden auch kategorisch aufgezählt (’enumerated’) oder diskret genannt. Anzumerken ist, dass aufgezählt und diskret eine hier nicht geforderte Reihenfolge implizieren.
Einen Spezialfall stellt die Dichotomie (Boolsche Attribute) dar, die nur zwei Werte enthält (’true’ und ’false’ oder ’yes’ und ’no’).
Weiterhin erlaubt eine einfache Transformation die Kodierung ordinaler Attribute mit n Werten mit Hilfe von n-1 booleschen Attributen. Das Attribut ’temperature’ dient in folgender Abbildung als Beispiel.

Transformation ordinal nach boolesch

Die bereits angesprochene Denormalisierung stellt nicht das einzige Problem in der Vorbereitung der Quelldaten dar. Hinzu kommt, dass die Daten oft aus unterschiedlichen Datenquellen stammen (z.B. Verkaufsabteilung, Rechnungswesen, …). Ein weiteres Problem stellen unterschiedliche Datenerhebungsverfahren, bestimmte Namenskonventionen, andere semantische Unterschiede oder fehlerhafte Daten dar. Die Quelldaten müssen deshalb integriert, bereinigt und gegebenfalls ergänzt werden, wobei u.U. zusätzliche externe Daten („Overlay Daten“) benötigt werden.
Im Data Warehousing findet dieses sogenannte „Data Cleansing“ im ETL-Prozess statt und stellt sicher, dass das Data Warehouse als konsistente Datenquelle angesehen werden kann.
Kritisch ist jedoch die Form und der Grad der Datenaggregierung (vgl. Dimensionalität in OLAP).

Fehlende Werte und ungenaue/fehlerhafte Werte
Fehlende Werte werden oft als Einträge ausserhalb des Wertebereichs angezeigt (z.B. ’-1’) oder als Grund des fehlenden Eintrags (’unbekannt’, ’nicht erfasst’ oder ’irrelevant’). Die Gründe hierfür können in fehlerhaften Messgeräten, in Änderungen im Versuchsplan, in der Zusammenführung verschiedener Datenbestände oder in einer nicht möglichen Messung liegen. Jedoch können fehlende Werte eine eigene Aussagekraft haben (z.B. eine fehlende Messung in einer medizinischen Untersuchung).
Die meisten Data Mining Algorithmen gehen davon aber nicht aus und somit muss der Eintrag ’missing’ möglicherweise als gesonderter Wert kodiert werden.
Eine wichtige Aufgabe ist es, die Quelldaten auf fehlerhafte oder ungenaue Werte hin zu überprüfen. Der Grund für die Fehlerhaftigkeit oder die Ungenauigkeit liegt darin, dass die zugrunde liegenden Daten meist nicht zum Zwecke des Data Mining erfasst wurden. So kann es beispielsweise möglich sein, dass in der ursprünglichen Anwendung leer gelassene oder ungeprüfte Felder sich nicht auswirkten (z.B. Kund*innenalter).
Weiterhin können auf Tippfehler bei der Eingabe von Daten fehlerhafte Mess- und Erfassungfehler bei numerischen Attributen oder absichtlich entstandene Fehler (z.B. fehlerhafte Straßennamen/Hausnummern) als Fehlerquelle identifiziert werden. In Folge dessen ist es erforderlich, diese Daten einer Konsistenzprüfung zu unterziehen.
Ein weiteres Problem stellen Duplikate und veraltete Daten dar. So kann beispielsweise die Gewichtung eines Attributes bei maschineller Auswertung durch Duplikate beeinflusst werden.
Ein weiterer wichtiger Punkt ist, seine Daten kennenzulernen. Einfache Hilfsmittel sind beispielsweise Histogramme, die die Verteilung der Werte von nominalen Attributen anzeigen oder Graphen, die die Verteilung der Werte von ordinalen Attributen darstellen. Diese simplen grafischen Visualisierungen machen es einfach, Probleme zu identifizieren. 2D- und 3D-Visualisierungen zeigen zudem Abhängigkeiten zwischen Attributen auf. Um Abweichungen oder die Bedeutung von fehlenden Werten zu beurteilen, müssen Domänenexpert*innen konsultiert werden. Bei zu großen Datenmengen müssen zudem Stichproben genommen werden, um die Daten kennenzulernen.

Methoden und Algorithmen

In diesem Kapitel werden Methoden und Algorithmen mit ihren Ergebnistypen betrachtet.

Methoden und Algorithmen mit ihren Ergebnistypen

Grundsätzlich lassen sich folgende Anforderungen an praxistaugliche Algorithmen definieren:

• Die Möglichkeit, numerische Attribute zu verarbeiten
• Die Möglichkeit, fehlende Werte zu handhaben
• Robustheit gegen verrauschte Daten (’Noise’)
• Die Möglichkeit, (zumindest prinzipiell) jeden beliebigen Output zu erreichen

Zudem ist anzumerken, dass einfache Algorithmen oft überraschend gut arbeiten, beispielsweise die Verwendung eines einzelnen Attributes für eine Klassifikation (siehe 1R-Verfahren), Lineare Regression zur Prognose numerischer Werte, instanzbasiertes Lernen.

Klassifikation

Die Klassifikation hat das Ziel der Vorhersage einer diskreten Klasse. Sie gehört zum Bereich des Supervised Learning (beaufsichtigtes Lernen). Das Ergebnis (die Klasse) wird für eine Menge von Beispielen (Trainingsdaten) vorgegeben, wobei der Erfolg anhand von weiteren Daten mit bekannten Klassen (Testdaten) gemessen werden kann. Im Folgenden werden Beispielprobleme in Form von Wetterdaten, Kontaktlinsendaten, Irisblumen oder Tarifverhandlungen vorgestellt.

In der nachfolgenden Tabelle sind Bedingungen zum Spielen eines (nicht genauer spezifizierten) Spiels aufgelistet.

Wetterdaten und zugehörige Klassifikationsregeln

Ein Klassifikationsverfahren kann dabei die folgenden Klassifikationsregeln liefern:

Es können auch Attribute mit nummerischen Werten vorkommen. Nachfolgend Wetterdaten mit gemischten Attributen.

Wetterdaten mit gemischten Attributen

Diese Daten führen beispielsweise zu folgenden Klassifikationsregeln:

Das folgende Beispiel zur Klassifikation von Irisblumen bezieht sich auf Daten des Statistikers R.A. Fischer aus den 30er Jahren, einer beliebten Beispieldatenmenge für Data Mining.

Klassifikation von Irisblumen

Die Daten führen zu Klassifikationsregeln der folgenden Form:

Die Klassifikation hat zum Ziel, eine diskrete Klasse vorherzusagen (Vorhersageziel) bzw. zu beschreiben, wie sich diese woraus ableitet (Beschreibungsziel). Wie bereits angeführt, gehört die Klassifikation zum Supervised Learning (beaufsichtigtes Lernen). Das Ergebnis (die Klasse) wird für eine Menge von Beispielen (Trainingsdaten) vorgegeben.

Mögliche Repräsentationen der Modelle:

• Entscheidungstabellen, -bäume, -regeln
• Instanzbasiert

Formal lässt sich eine Klassifikation wie folgt darstellen. Gegeben seien:

• Ein n-dimensionaler Raum S mit n Attributen
• eine Menge C von k unterschiedlichen Klassen
• eine Menge von Trainingsinstanzen mit bekannter Klasse aus C

Gesucht: Eine Funktion, die jedem Element aus S eine Klasse aus C zuordnet, d.h. K : S ${\textstyle \rightarrow }$ C (eine solche Funktion heißt Klassifikator).

Das Klassifikationsproblem

Entscheidungstabellen
Entscheidungstabellen stellen die rudimentärste Form des Outputs dar und verwenden das gleiche Format wie beim Input. Das Hauptproblem ist hierbei die Auswahl der richtigen Attribute, d.h. welche Attribute können weggelasssen werden, ohne die finale Entscheidung zu beeinflussen.

Entscheidungstabelle für das Wetterproblem

Entscheidungsbäume
Der ’Divide-and-Conquer’-Ansatz bezüglich des Problems des Lernens aus einem Set unabhängiger Instanzen führt zu einem sogenannten Entscheidungsbaum als Repräsentationsstil. Die Knoten repräsentieren den Test eines Attributs, meist den Vergleich mit einer Konstante. Weitere Möglichkeiten sind, dass die Knoten die Werte zweier Attribute miteinander vergleichen oder eine Funktion aus einem oder mehreren Attributen verwenden.
Die Blätter verweisen auf eine Klasse, eine Menge von Klassen oder eine Wahrscheinlichkeitsverteilung.

Kontaktlinsendaten

Nachfolgend die Darstellung eines Entscheidungsbaums für die Kontaktlinsendaten mit den Attributen ’tear production rate’, ’astigmatism’ und ’spectacle prescription’.

Entscheidungsbaum für die Kontaktlinsendaten

Enthalten die getesteten Knoten nominale Attribute, so entspricht die Anzahl der Kinder normalerweise der Anzahl der möglichen Werte. Jedes Attribut wird nur einmal getestet. Eine weitere Möglichkeit stellt die Aufteilung in zwei oder mehr Teilmengen dar.
Enthalten die Knoten numerische Attribute, so wird getestet ob der Wert größer oder kleiner als eine Konstante ist und es erfolgt ein Zwei-Wege-Split. Hierbei kann ein Attribut auch mehrmals getestet werden. Drei-Wege-Splits finden Verwendung, falls es mehrere Vergleichsmöglichkeiten gibt. So kann z.B. ein Integer auf ’kleiner als’, ’gleich’ oder ’größer als’ oder auf ’unterhalb’, ’innerhalb’ oder ’oberhalb’ eines Intervalls getestet werden.
Wenn das Fehlen eines Wertes eine eigene Aussagekraft hat, wird ’missing’ als eigener Wert kodiert. Ist das nicht der Fall so muss der fehlende Wert besonders behandelt werden. Eine mögliche Lösung stellt die Zuweisung zu dem ’beliebtesten’ Zweig dar.

Klassifikationsregeln
Eine beliebte Alternative zu Entscheidungsbäumen stellen Klassifikationsregeln dar. Sie setzen sich aus den Teilen Antecedent und Consequent zusammen, die meist mit einem logischen OR verbunden werden.
Der Antecedent-Teil (Prämisse, Bedingung) stellt eine Menge von Tests (wie die Tests an den Knoten eines Entscheidungsbaumes) dar, die üblicherweise mit einem logischen UND verbunden (auch andere logische Ausdrücke möglich) werden.
Als Consequent (Konklusion, Schlussfolgerung) bezeichnet man eine Klasse, eine Menge von Klassen oder eine Wahrscheinlichkeitsverteilung. Das Kontaktlinsenproblem lässt sich wie folgt mit Hilfe von Klassifikationsregeln abbilden:

Die Konvertierung eines Baumes in eine Menge von Regeln (eine Regel für jedes Blatt) gestaltet sich relativ einfach. Der Antecedentteil beinhaltet die Bedingung für jeden Knoten auf dem Pfad von der Wurzel zum Blatt während der Consequentteil die durch das Blatt zugewiesene Klasse repräsentiert.
Durch diese Transformation werden eindeutige Regeln erzeugt, deren Ausführungsreihenfolge keine Rolle spielt. Jedoch sind die resultierenden Regeln unnötig komplex und es ist erforderlich, redundante Regeln durch das sogenannte ’Pruning’ zu entfernen.
Die Transformation einer Regelmenge in einen Baum ist komplizierter als die Transformation von Bäumen in Regelmengen. So kann z.B. eine Disjunktion zwischen Regeln durch einen Baum nicht so einfach abgebildet werden. Im diesem Falle enthält der konstruierte Baum identische Teilbäume (’Replicated Subtree Problem’).
Beispiel – Regeln, die unterschiedliche Attribute testen:

Der zugehörige Baum für diese einfache Disjunktion:

Entscheidungsbaum für eine Disjunktion

R – ein Klassifikationsalgorithmus zum Ableiten elementarer Regeln

Eine einfache Methode um einfache Klassifikationsregeln aus einem Set von Instanzen zu finden, stellt der 1R-Klassifikationsalgorithmus dar.
Der Algorithums lernt einen 1-Ebenen-Entscheidungsbaum. Anders ausgedrückt generiert er eine Menge von Regeln, die alle nur ein einzelnes Attribut testen.
In der Basisversion (ausgehend von nominalen Attributen) repräsentiert jeder Zweig einen anderen Attributwert. Jedem Zweig wird dabei die in den Trainingsdaten am häufigsten auftauchende Klasse zugewiesen. Die Fehlerrate ist das Verhältnis zwischen den Instanzen, die nicht in die Mehrheitsklasse des zugehörigen Zweiges und allen dem Zweig zugeordneten Instanzen gehören. Das Attribut mit der niedrigsten Fehlerrate wird ausgewählt. Zusätzlich ist darauf hinzuweisen, dass ’missing’ immer als separater Attributwert behandelt wird.
Pseudo-Code für 1R:

Beispiel:

Bewertung der Wetterattribute

Das erste und das dritte Regelset werden ausgewählt. Es fällt auf, dass das Spiel nur gespielt wird, wenn es bewölkt ist oder regnet, hingegen nicht, wenn die Sonne scheint.

Verarbeiten numerischer Attribute in 1R
Bei der Verarbeitung von numerischen Attributen werden die numerischen Attribute durch eine Diskretisierungmethode in nominale Attribute umgewandelt. Der Wertebereich der Attribute wird dabei in Intervalle aufgeteilt. Im Anschluss werden die Instanzen nach den Werten des Attributs sortiert und die Intervallwechsel dort gesetzt, wo sich die (Mehrheits-) Klasse ändert so dass der Gesamtfehler minimiert wird.
Beispiel:

Wetterdaten mit numerischer Temperatur

Das Problem des ’Overfitting’
Die beim Verarbeiten von numerischen Attributen angewandte Diskretisierung ist sehr anfällig gegen verrauschte Daten. Eine einzige Instanz mit einem inkorrekten Klassenlabel wird vermutlich zu einem eigenen Intervall führen. Zudem wird z.B. ein Zeitstempelattribut immer einen Fehlerwert von 0 haben. Eine einfache Lösung ist das Erzwingen einer Mindestanzahl an Instanzen in der Mehrheitsklasse pro Intervall.
Beispiel:

Wetterdaten (mit einem Minimum von 3)

Ergebnis der Overfitting-Vermeidung für das Temperatur-Attribut

Die entsprechende Ergebnisregelmenge

Der 1R-Algorithmus wurde in einem Aufsatz von Holte (1993) beschrieben. Das Paper beinhaltet eine experimentelle Evaluation anhand von 16 Datenmengen (unter Verwendung von ’Cross-Validation’). Die Minimalanzahl an Instanzen wurde nach einigen Experimenten auf 6 gesetzt. Die einfachen 1R-Regeln lieferten kaum schlechtere Ergebnisse als deutlich komplexere Entscheidungsbäume. Die Schlussfolgerung daraus: Einfachheit lohnt sich!

ID3 – ein Klassifikationsalgorithmus zur Konstruktion von Entscheidungsbäumen

Das übliche Verfahren beim ID3-Algorithmus verläuft Top-down und rekursiv nach dem ’Divide-and-Conquer’ Prinzip. Zunächst wird das Attribut für die Wurzel selektiert und ein Zweig für jeden möglichen Wert wird erzeugt.
Dann werden für jeden von dem Knoten ausgehenden Zweig die Instanzen in Teilmengen aufgeteilt. Schließlich wird das Verfahren für jeden Zweig rekursiv mit den jeweiligen Instanzen wiederholt. Der Prozess terminiert, wenn alle Instanzen einer Teilmenge die gleiche Klasse haben, zum Split kein Attribut mehr übrig ist oder wenn es keine Instanzen für die vorzunehmende Aufteilung gibt.

Attributauswahl

Das beste Attribut ist das, welches zum kleinsten Baum führt. Die Heuristik hierzu: Wähle das Attribut, das die ’reinsten’ Knoten produziert.
Ein beliebtes Kriterium für ’Reinheit’ stellt der Information Gain (Informationsgewinn) dar. Der Information Gain wächst mit der durchschnittlichen Reinheit der Teilmengen, die ein Attribut erzeugt. Die Strategie hierfür ist, das Attribut zu wählen, das zum größten Information Gain führt.
Das Informationsmaß wird in Bits gemessen. Bei einer gegebenen Wahrscheinlichkeitsverteilung entspricht die Information, die zur Vorhersage eines Ereignisses benötigt wird, der Entropie der Verteilung. Die Entropie liefert die benötigten Informationen in Bits (Kann auch Teile eines Bits beinhalten!)
Die Formel zur Berechnung der Entropie lautet:

Sie geht zurück auf Shannon und findet sich auch in anderen Anwendungen wie z.B. der Kryptographie.
Beispiel – Attribut ’Outlook’:

• ’Outlook’ = ’Sunny’:

• ’Outlook’ = ’Overcast’:

• ’Outlook’ = ’Rainy’:

Das erwartete Informationsmaß für das Attribut: 

Die Berechnung des Information Gains wird wie folgt vorgenommen. Information Gain = Informationsgehalt vor dem Split – Informationsgehalt nach dem Split:

Beispiel – Information Gain für die Attribute der Wetterdaten:

Weitere Teilung:

Weitere Teilung

Ergebnis:

Der fertige Entscheidungsbaum:

Fertiger Entscheidungsbaum

Hinzuzufügen ist, dass nicht alle Blätter vollständig rein sein müssen. Manchmal haben identische Instanzen unterschiedliche Klassen. Die Teilung terminiert, wenn keine weitere Teilung möglich ist.

Die Gain Ratio ist eine Veränderung des Information Gains, die das Overfitting reduziert. Sie berücksichtigt die Anzahl und Größe der Zweige bei der Auswahl eines Attributes und berichtigt den Information Gain durch Berücksichtigung ’intrinsischer’ Informationen.
Eine ’Intrinsic Information’ stellt die Entropie der Verteilung der Instanzen auf die Zweige (d.h. wie viel Information wird benötigt, um zu entscheiden, zu welchem Zweig eine Instanz gehört) dar.
Der ID3-Algorithmus wurde zur Top-down Induktion von Entscheidungsbäumen von Ross Quinlan entwickelt. Die Verwendung der Gain Ratio ist nur eine Erweiterung dieses Basisalgorithmus. Er führte zu der Entwicklung von C4.5, der numerische Attribute, fehlende Werte und verrauschte Daten verarbeiten kann und ist zudem der bekannteste und (wahrscheinlich) der meistbenutzte Lernalgorithmus. Der kommerzielle Nachfolger ist C5.0. Einen ähnlichen Ansatz verfolgt auch CART (Classification And Regression Tree).

Erzeugung von Klassifikationsregeln
Ein Entscheidungsbaum kann in eine Regelmenge übersetzt werden. Bei einer einfachen Konvertierung wird die Regelmenge übermäßig komplex. Effektivere Konvertierungen sind jedoch nicht trivial.
Eine mögliche Strategie zur direkten Regelerzeugung ist für jede Klasse eine Regelmenge zu finden, die alle zugehörigen Instanzen einschließt (und keine Instanzen außerhalb der Klasse). Dieser Ansatz heißt ’Covering’, da in jedem Schritt eine Regel gefunden wird, die einen Teil der Instanzen ’abdeckt’.
Beispiel – Erzeugen einer Regel:

Erzeugung einer Klassifikationsregel

Eine mögliche Regelmenge für Klasse ’b’:

Weitere Regeln können hinzugefügt werden, um zu einer ’perfekten’ Regelmenge zu gelangen.
Der zugehörige Entscheidungsbaum liefert exakt die gleichen Vorhersagen. Regelmengen können jedoch verständlicher sein. Bei mehreren Klassen behandelt ein Covering-Ansatz eine Klasse nach der anderen, während ein Algorithmus für Entscheidungsbäume alle Klassen auf einmal berücksichtigt.

Zugehöriger Entscheidungsbaum

PRISM – ein Klassifikationsalgorithmus zum Erzeugen von Klassifikationsregeln (Covering-Ansatz)

Der PRISM-Klassifikationsalgorithmus erzeugt eine Regel durch das Hinzufügen von Tests, die die Genauigkeit der Regel maximieren. Jeder neue Test reduziert die Abdeckung der Regel. Das Problem der Auswahl eines Attributes für den Split ist ähnlich der Situation bei Entscheidungsbäumen, wobei der Entscheidungsbaum-Algorithmus hingegen die Gesamtreinheit maximiert.
Das Ziel ist die maximale Genauigkeit der Regel. t steht dabei für die Gesamtzahl der durch die Regel abgedeckten Instanzen. p repräsentiert die Anzahl der positiven (richtig klassifizierten) Beispiele. t-p stellt Anzahl der Fehler (d.h. der Falsch-klassifizierungen) dar. Anschliessend wird der Test ausgewählt, der das Verhältnis p/t maximiert. Die Regel ist fertig, wenn p/t = 1 oder wenn die Instanzmenge nicht mehr weiter aufgeteilt werden kann.

Zur Erinnerung: Kontaktlinsendaten

Die gesuchte Regel:

Die möglichen Tests:

Die Regel nach Hinzufügen des besten Tests:

Die durch die Regel abgedeckte Instanzen:

Eine weitere Verfeinerung des aktuellen Stands:

Die möglichen Tests:

Die veränderte Regel nach Hinzufügen des besten Tests und den zugehörigen Daten:

Die nachfolgende Tabelle zeigt die durch die neue Regel abgedeckte Instanzen:

Eine weitere Verfeinerung des aktuellen Stands:

Mögliche Tests:

Es stellt sich raus, dass Gleichstand zwischen erstem und viertem Test herrscht. Deshalb wird derjenige mit der größeren Abdeckung ausgewählt.
Das Endergebnis und die fertige Regel lauten:

Die zweite Regel zur Empfehlung von ’hard lenses’ (mit den durch die erste Regel nicht abgedeckten Instanzen erzeugt):

Diese beiden Regeln decken alle ’hard lenses’ ab. Der gesamte Vorgang wird nun für die anderen beiden Klassen wiederholt.
Pseudo-Code für PRISM:

Methoden wie PRISM sind sog. ’Separate-and-Conquer’ Algorithmen mit folgendem Vorgehen:

Erst wird eine Regel identifiziert, dann werden alle Instanzen, die von der Regel abgedeckt werden, aussortiert. Schließlich werden die übrigen Instanzen ’erobert’. Der Unterschied zu ’Divide-and-Conquer’ Methoden ist, dass die von der Regel abgedeckte Teilmenge nicht mehr weiter untersucht werden müssen. Ein praxisüblicher Algorithmus ist CN2 .

k-NN – ein Klassifikationsalgorithmus für instanzbasiertes Lernen

Die einfachste Form des Lernens ist das sogenannte „Routinelernen“. Dabei werden die Trainingsdaten nach Instanzen durchsucht, die der neuen Instanz am ähnlichsten sind. Diese Instanzen selbst repräsentieren das Wissen.
Das ’Routinelernen’ wird auch instanzbasiertes Lernen (IBL), oder auch fallbasiertes Lernen/Schließen (’Case-based Reasoning’, CBR) genannt und fällt in den Bereich des ’Lazy Learning’.
Hierbei bestimmt die Ähnlichkeitsfunktion (Distanzfunktion) was ’gelernt’ wird. Die eingesetzten Methoden: Nächste-Nachbarn, k-Nächste-Nachbarn, …
Die einfachste Form der Distanzfunktion ist ein numerisches Attribut. Die Distanz ist die Differenz zwischen zwei Attributwerten oder eine Funktion davon. Bei mehreren numerischen Attributen wird normalerweise die „Euklidische Distanz“ verwendet und die Attribute werden normalisiert.
Bei nominalen Attributen ist die Distanz bei verschiedenen Werten 1 und bei gleichen Werten 0. Falls zudem nicht alle Attribute gleich wichtig sind, kann eine Gewichtung der Attribute notwendig sein.
Minkowski-Distanz – Gegeben seien zwei Instanzen a(1) und a(2) mit k Attributen:

q=1: City-Block Metric (auch: Manhattan-Distanz)
q=2: Euklidische Distanz (am häufigsten verwendet)
Das Ziehen der Wurzel ist nicht notwendig, wenn Distanzen nur verglichen werden sollen.
Bei numerischen Attributen werden verschiedene Attribute auf unterschiedlichen Skalen gemessen und müssen normalisiert werden:

vi: Wert des Attributes i
Bei nominalen Attributen ist die Distanz entweder 0 oder 1. Die übliche Vorgehensweise bei fehlenden Werten ist die Annahme der maximalen Distanz (bei normalisierten Attributen).
Zur Auswahl des Parameters k ist folgendes anzumerken. Falls k zu klein ist, ist die Empfindlichkeit gegenüber Ausreißern in den Daten zu hoch. Falls k zu groß ist, werden viele Instanzen aus anderen Klassen in die Entscheidung miteinbezogen. In vielen Fällen ist ein Wert zwischen 1 und 10 angemessen und erzielt gute Ergebnisse.
1-NN ist oft korrekt, aber langsam. Eine einfache Version durchsucht die gesamten Trainingsdaten, um eine Prognose abzuleiten.
Unter der Annahme, dass alle Attribute gleich wichtig sind, kann eine Lösung sein, eine Auswahl von Attributen oder der Gewichtung vorzunehmen. Eine mögliche Lösung bei verrauschten Daten stellt ein ’Mehrheitsentscheid’ der k nächsten Nachbarn dar. Zudem können Ausreißer aus den Daten entfernt werden, was sich jedoch meist nur schwer bewerkstelligen lässt.
In der Statistik wird k-NN seit den frühen 50er Jahren verwendet. Wenn n ${\textstyle \rightarrow }$ ${\textstyle \infty }$ und k/n ${\textstyle \rightarrow }$ 0, wird der Fehler minimal.

Evaluation von Klassifikationsverfahren

Evaluation ist der Schlüssel zum Erfolg im Data Mining. Die Fragestellung hierbei lautet, wie gut das erlernte Modell ist.
Die Fehlerrate in den Trainingsdaten ist kein guter Indikator für die Prognosegüte bei neuen Daten, sonst wäre 1-NN der beste Klassifikator.
Eine einfache Lösung, die verwendet werden kann, wenn viele Daten (mit zugehöriger Klasse) zur Verfügung stehen, ist das Aufteilen der Daten in eine Trainings- und eine Testmenge. Der Nachteil hierbei ist, dass klassifizierte Daten normalerweise rar sind.
Aspekte bei der Evaluation:

• Statistische Verlässlichkeit der abgeschätzten Modellgüte (Signifikanztests)
• Auswahl des Gütemaßes
• Anzahl korrekter Klassifizierungen
• Genauigkeit der geschätzten Wahrscheinlichkeiten
• Fehler bei numerischen Prognosen
• Unterschiedliche ’Kosten’ können verschiedenen Fehlertypen zugewiesen werden.

Die Fehlerrate ist ein natürliches Gütemaß für Klassifikationsprobleme. Der Klassifikator sagt die Klasse jeder Instanz voraus.
Wird die Klasse einer Instanz richtig prognostiziert, so zählt das als Erfolg. Wird hingegen die Klasse einer Instanz falsch prognostiziert, so zählt das als Fehler.
Das Verhältnis der Fehler zu der Gesamtzahl an getesteten Instanzen wird als Fehlerrate bezeichnet und misst die Performanz des Klassifikators. Der ’Resubstitution Error’ ist die Fehlerrate, die sich aus den Trainingsdaten ergibt (durch ’Ersetzen’ der zum Training verwendeten Klassen).
Anzumerken ist hierbei, dass der ’Resubstitution Error’ extrem optimistisch ist.
Die Testmenge stellt eine Menge unabhängiger Instanzen dar, die bei der Erzeugung des Klassifikators keine Rolle gespielt haben. Es wird angenommen, dass Trainings- und Testdaten repräsentative Stichproben des zugrunde liegenden Problems sind. Generell gilt, dass je größer die Trainingsdatenmenge, desto besser ist der Klassifikator. Ebenfalls gilt, dass je größer die Testdatenmenge, desto genauer ist die Fehlerabschätzung. Ideal wäre also beides, eine große Trainings- und eine große Testmenge.
Es ist wichtig, dass die Testdaten in keinster Weise bei der Erzeugung des Klassifikators verwendet werden. Einige Lernschemata beinhalten zwei Phasen: In Phase 1 wird die Basisstruktur erzeugt. In Phase 2 findet die Optimierung der Parameterwerte statt. Anzumerken ist, dass die Testdaten auch nicht zur Parameteroptimierung verwendet werden dürfen. Richtig ist hingegen die Verwendung von drei Datenmengen: Trainingsdaten, Validierungsdaten und Testdaten.
Die Trainingsdaten werden von einer oder mehreren Lernmethoden zusammen mit Klassifikatoren benutzt. Die Validierungsdaten werden zur Optimierung der Parameter verwendet und die Testdaten werden verwendet, um die Fehlerrate der finalen und optimierten Methode zu bestimmen.
Wenn die Datenmenge begrenzt ist, kommt die Holdout-Methode zum Einsatz. Sie reserviert einen Teil für das Testen und verwendet den Rest zum Training. Üblicherweise wird ein Drittel zum Testen und der Rest zum Training verwendet. Das Problem hierbei ist, dass die Stichproben möglicherweise nicht repräsentativ sind. So kann zum Beispiel eine Klasse in den Trainingsdaten fehlen.
Die erweiterte Version des Holdout-Verfahrens verwendet Stratifizierung. Sie stellt sicher, dass jede Klasse mit ungefähr gleichen Anteilen in beiden Teilmengen enthalten ist.
Die Zuverlässigkeit der Holdout-Abschätzung kann durch Wiederholung des Vorgangs mit unterschiedlichen Stichproben gesteigert werden. In jeder Iteration wird eine zufällige Stichprobe (ggf. mit Stratifizierung) gezogen. Die Gesamtfehlerrate wird dann als Durchschnitt der Fehlerraten der einzelnen Iterationen gebildet.
Diese Methode nennt man ’Repeated Holdout’. Sie ist aber immer noch nicht optimal, denn die einzelnen Testmengen überlappen.
Die Cross-Validation verhindert die überlappende Testmengen beim Holdout-Verfahren. Als erster Schritt werden die Daten in k Teilmengen gleicher Größe aufgeteilt. Im zweiten Schritt wird jede Teilmenge jeweils zum Testen verwendet und der Rest der Daten zum Training. Dieses Verfahren nennt man k-fache Cross-Validation.
Hierbei werden die Teilmengen oft vorher stratifiziert. Die Gesamtfehlerabschätzung ergibt sich wieder aus dem Durchschnitt der einzelnen Fehlerabschätzungen.
Das Standardverfahren zur Evaluation ist die stratifizierte zehnfache Cross-Validation. Zehnfach deshalb, da sich bei vielen Experimenten dieser Wert als die beste Wahl herausgestellt hat. Außerdem gibt es eine gewisse theoretische Grundlage dafür.
Die Leave-One-Out Cross-Validation ist eine besondere Form der Cross-Validation. Die Anzahl der Wiederholungen ist gleich der Anzahl aller Trainingsinstanzen, d.h. es muss n-mal ein Klassifikator erzeugt werden, wobei n die Anzahl der Trainingsinstanzen ist.
Die Leave-One-Out Cross-Validation macht maximalen Gebrauch von den Daten. Zudem gibt es keine zufälligen Stichproben. Ein Nachteil ist, dass ein sehr hoher Rechenaufwand (Ausnahme: NN) notwendig ist. Ein weiterer Nachteil von LOO-CV ist, dass eine Stratifizierung nicht möglich ist. Im Gegenteil, das Verfahren garantiert nicht-stratifizierte Stichproben, da die Testdaten aus jeweils nur einer Instanz bestehen.
Als Extrembeispiel dient eine vollständig zufällige Datenmenge mit zwei Klassen und gleichmäßiger Verteilung. Der beste Klassifikator prognostiziert die Mehrheitsklasse der Trainingsdaten (entspricht einer Fehlerrate von 50% bei frischen Daten mit gleichen Eigenschaften). Die durch LOO-CV abgeschätzte Fehlerrate dieses Klassifikators liegt aber bei 100%, da die verbleibende Testinstanz nie zur Mehrheitsklasse gehört.
Im Vergleich von Data-Mining-Verfahren steht die Frage im Mittelpunkt, welches von zwei Lernschemata besser arbeitet. Ein offensichtlicher Ansatz bietet ein Vergleich der 10-fachen Cross-Validation Abschätzungen. Das Problem ist die Varianz der Abschätzungen. Die Varianz kann aber durch wiederholte Cross-Validations reduziert werden. Jedoch ist die Zuverlässigkeit der Ergebnisse dann immer noch unbekannt. Die Durchführung von Signifikanztests ergibt, wie sicher man sein kann, dass tatsächlich Unterschiede existieren.

Abhängigkeitsanalyse

Das Erkennen von Abhängigkeiten zwischen Merkmalen realisiert man durch die sogenannte Abhängigkeitsanalyse. Sie kann angewendet werden, wenn keine Klasse verwendet werden kann und alle Strukturen als ’interessant’ angesehen werden.
Der Unterschied zur Klassifikationsanalyse besteht darin, dass mit Hilfe der Abhängigkeitsanalyse auch der Wert beliebiger Attribute (auch mehrerer) vorhergesagt werden kann, anstatt nur eine Klasse. Mit Hilfe von Klassifikationsregeln lässt sich somit der Wert eines vordefinierten Attributes (der Klasse eines Beispiels) vorhersagen bzw. erklären.
Mit Abhängigkeitsregeln (’Association Rules’) lässt sich hingegen der Wert eines beliebigen Attributes oder der Kombination eines Attributes vorhersagen bzw. erklären:

Da aus Datensätzen wesentlich mehr Abhängigkeitsregeln als Klassifikationsregeln abgeleitet werden können, sind die Einschränkungen minimaler Support (Abdeckung) und minimale Konfidenz (Genauigkeit) notwendig.
Die Abhängigkeitsanalyse kann verwendet werden, wenn keine Klasse angegeben werden kann und alle Strukturen als ’interessant’ angesehen werden. Sie zählt zum unbeaufsichtigten Lernen (’Unsupervised Learning’) und verfolgt ein Beschreibungsziel. Ein klassisches Beispiel ist die Warenkorbanalyse (die Attribute sind Produkte in einem Warenkorb). Der Output einer Anhängigkeitsanalyse sind Abhängigkeitsregeln bzw. Interdependenzgraphen.
Mit Hilfe von Abhängigkeitsregeln (’Association Rules’) kann ein Attribut oder eine Kombination von Attributen vorhergesagt werden.
Abhängigkeitsregeln sollen nicht als Regelmenge zusammen verwendet werden, sondern einzelne Regeln sind von Interesse. Ein Problem stellt hierbei die extrem große Anzahl an möglichen Abhängigkeiten dar. Der Output muss so eingeschränkt werden, dass nur die ’besten’ Abhängigkeiten ermittelt bzw. ausgegeben werden. Daraus folgen nur Regeln mit einem hohen Support und einer hohen Konfidenz.

Ein Item ist ein Paar aus Test und Attributwert. Eine Menge von Items wird als Item Set bezeichnet.
Der Support eines Item Set ist die Anzahl der Instanzen in der Trainingsmenge, die das Item Set enthalten (im Verhältnis zur Anzahl aller Instanzen in der Trainingsmenge). Die Konfidenz einer Regel ist die Anzahl der Instanzen, die die Regel (Bedingungs- und Schlussfolgerungsteil) erfüllen im Verhältnis zur Anzahl der Instanzen, die den Bedingungsteil erfüllen.

Ein Probem ist, dass bei vielen Elementen Zusammenhänge und Beziehungen aufgrund von mangelndem Support verloren gehen. Eine mögliche Lösung ist die Definition und das Speichern von Taxonomien.

Beispiel: ’Die Kund*innen, die Straßenschuhe kaufen, erwerben auch Jacken’. Wegen zu hoher Supportschranke gilt aber nicht: ’Die Kund*innen, die Stiefel kaufen, erwerben auch Jacken’. Die Aussagen werden wegen höherem Aggregationsniveau genereller.

Generalisierte Assoziationsregeln

APRIORI – ein Algorithmus zum Erlernen von Abhängigkeitsregeln

Der APRIORI-Algorithmus ist eine naive Methode zum Finden von Abhängigkeitsregeln. Er verwendet die Standard ’Separate-and-Conquer’ Methode, nur dass jede mögliche Kombination von Attributwerten als separate Klasse behandelt wird. Hierbei gibt es jedoch zwei Probleme. Zum einen ist der APRIORI-Algorithmus sehr aufwendig und komplex. Zum anderen gibt es eine große Anzahl an resultierenden Regeln, die anhand von Support und Konfidenz noch einem ’Pruning’ unterworfen werden müssen.
Vorteilhaft ist dabei, dass Regeln mit hohem Support direkt gefunden werden können. Man findet zunächst alle Item Sets mit dem gegebenen minimalen Support und generiert daraus dann Regeln.
Beispiel – Wetterdaten:

Zur Erinnerung: Wetterdaten

Item Sets für die Wetterdaten:

Item Sets für die Wetterdaten

Insgesamt entstehen 12 1-Item-Sets, 47 2-Item-Sets, 39 3-Item-Sets, 6 4-Item-Sets und keine 5-Item-Sets (mit einem minimalen Support von 2). Wenn alle Item Sets mit dem minimalen Support gefunden sind, können diese in Regeln umgewandelt werden.

Beispiel:

Es existieren sieben (2N-1) potenzielle Regeln:

Die resultierenden Regeln mit Support 2 und Konfidenz = 100%:

Resultierende Abhängigkeitsregeln

Es gibt 3 Regeln mit Support = 4, 5 mit Support = 3 und 50 mit Support = 2.

Effiziente Generierung der Item Sets

Es stellt sich die Frage, wie alle häufigen Item Sets gefunden werden können. Das Finden von 1-Item-Sets ist trivial. Zum Finden von k-Item-Sets gibt es folgende Idee
Man verwendet 1-Item-Sets, um 2-Item-Sets zu generieren, 2-Item-Sets, um 3-Item-Sets zu generieren, usw. Die Idee ist dass wenn (A B) ein häufiges Item Set ist, dass dann (A) und (B) ebenfalls häufige Item Sets sein müssen. Allgemein gilt dann:
Wenn X ein häufiges k-Item-Set ist, dann müssen alle darin enthaltenen (k-1)-Item-Sets ebenfalls häufig sein (sog. A-Priori-Eigenschaft). Die k-Item-Sets werden durch Zusammenfassen von (k-1)-Item-Sets berechnet.

Beispiel – Gegeben sind fünf 3-Item-Sets (Lexikographisch geordnet):

Kandidaten für 4-Item-Sets:

Abschließend findet eine Überprüfung durch Zählen der Instanzen statt und die (k-1)-Item-Sets werden in einer Hashtabelle gespeichert.
Zur effizienten Regelgenerierung werden alle Regeln mit hoher Konfidenz gesucht. Der Support des Antecedent kann aus der Hash Table ausgelesen werden, um Konfidenz zu berechnen. Der Nachteil hierbei ist, dass die Anwendung der Brute-Force-Methode (2^N-1) Versuche bedeutet.
Besser ist es, (c+1)-Consequent-Regeln aus c-Consequent-Regeln zu erzeugen. Die Beobachtung zeigt, dass eine (c+1)-Consequent-Regel nur gültig sein kann, wenn alle zugehörigen c-Consequent-Regeln ebenfalls gültig sind. Der resultierende Algorithmus ist ähnlich zu dem zum Finden der Item Sets.

Beispiel – 1-Consequent-Regeln:

Zugehörige 2-Consequent-Regel:

Abschließend erfolgt eine Prüfung des Antecedent in der Hash Table.
Die genannte Methode benötigt einen Durchlauf durch die Datenmenge für jede Item-Set-Größe. Eine andere Möglichkeit ist die Generierung von (k+2)-Item-Sets sofort nach der Generierung der (k+1)-Item-Sets ohne Überprüfung der (k+1)-Sets nach ihrer Erzeugung. Das Ergebnis ist, dass mehr (k+2)-Item-Sets als nötig berücksichtigt werden, aber weniger Durchläufe durch die Daten erfolgen. Diese Methode kann sinnvoll sein, wenn die Datenmenge zu groß ist, um in den Hauptspeicher zu passen.
Eine praktische Möglichkeit ist die Generierung einer bestimmten Anzahl von Regeln z.B. durch sukzessive Reduzierung des minimalen Supports.
Der Standardinput (flache Relation mit einer Zeile pro Instanz und einer Spalte pro Attribut) ist sehr ineffizient für typische Warenkorbdaten. Die Attribute repräsentieren Produkte in einem Warenkorb wobei üblicherweise die meisten Produkte fehlen. Die Instanzen werden in dem Zusammenhang auch Transaktionen genannt.
Zur graphischen Darstellung einfacher Abhängigkeitsregeln können sogenannte Interdependenzgraphen verwendet werden. Nachfolgende Grafik zeigt den Interdependenzgraphen einer Warenkorbanalyse.

Interdependenzgraph

Clustering

Unter Clustering, das zum Unsupervised Learning (unbeaufsichtigtes Lernen) gehört, versteht man die Gruppierung ähnlicher Instanzen in einer Menge (Cluster). Der Erfolg des Clusterings kann meist nur subjektiv gemessen werden.

Beispielproblem: Irisdaten ohne Klasse

Die Methode des Clusterings zählt zum Unsupervised Learning, d.h. es wird kein Zielwert vorgegeben.
Die Vorgaben sind:

• Intra-Cluster-Ähnlichkeit der Instanzen soll möglichst hoch sein
• Inter-Cluster-Ähnlichkeit der Instanzen soll möglichst gering sein

Die Unterschiede zwischen Modellen/Algorithmen:

• Eindeutig vs. überlappend
• Deterministisch vs. probabilistisch
• Hierarchisch vs. Flach

Weiterhin gibt es eine Evaluationsproblematik. Eine Evaluierung ist üblicherweise nur durch manuelle Prüfung möglich, außer das Clustering wird als Dichteabschätzung verstanden. Dann kann es auf Testdaten evaluiert werden.

k-Means – ein Clustering-Algorithmus

Beim k-Means-Algorithmus werden die Daten in k Gruppen (mit vordefiniertem k) aufgeteilt. Die Vorgehensweise ist wie folgt:

1. Clustermitten werden gewählt (z.B. zufällig)
2. Instanzen werden den Clustern aufgrund ihrer Distanz zu den Clustermitten zugewiesen
3. die Schwerpunkte der Cluster werden berechnet und als neue Mitten verwendet
4. zurück zum ersten Schritt bis zur Konvergenz

Die Eigenschaften dabei sind, dass kein Cluster leer ist und jede Instanz genau einem Cluster angehört.
Die Ergebnisse des k-Means-Algorithmus können stark von der Auswahl der Anfangswerte abhängen. So kann der Algorithmus z.B. auf ein lokales Minimum ’hereinfallen’. Beispiel: Es gibt vier Instanzen an den Eckpunkten eines zweidimensionalen Rechtecks. Das lokale Minimum stellen zwei Clustermitten an den Mittelpunkten der langen Seiten des Rechtecks dar.
Eine einfache Möglichkeit, die Chance zum Auffinden des globalen Optimums zu erhöhen ist das wiederholte Ausführen mit unterschiedlichen Zufallsstartwerten.
Repräsentation von Clustern
Einfache 2D-Repräsentation:

Einfache 2D-Repräsentation

Probabilistische Zuweisung:

Probabilistische Zuweisung

Venn-Diagramm:

Überlappende Cluster

Dendrogramm (hierarchisch):

Hierarchische Cluster

Zum hierarchischen Clustering werden beim Bottom-up (agglomerativen) Vorgehen in jedem Schritt die beiden ähnlichsten Cluster zusammengefasst (Beginn mit Einzelinstanz-Clustern), bis nur noch ein Cluster übrigbleibt.
Beim Top-down (divisiven) Vorgehen werden zwei Cluster gefunden und die Prozedur für die Teilmengen rekursiv fortgesetzt, bis Einzelinstanz-Cluster erreicht sind. Beide Methoden erzeugen ein Dendrogramm.
Gütemaße für Cluster – Gegeben seien zwei Cluster A und B.

• Single-Link: Verwendet die minimale Distanz zwischen zwei Instanzen aus A und B und neigt zur Bildung von Ketten durch ’ungünstige’ Instanzen in den Clustern
• Complete-Link: Verwendet die maximale Distanz zwischen zwei Instanzen aus A und B und ist empfindlich gegen Ausreißer.
• Average-Link: Ist ein Kompromiss zwischen Single- und Complete-Link und verwendet den mittleren Abstand zwischen allen Instanzpaaren aus A und B.

Cluster können nachträglich mit Hilfe von Supervised Learning (Klassifikation) erklärt/ interpretiert werden. Ein Vorteil des probabilistischen Clustering-Verfahrens ist, dass Instanzen nur mit einer gewissen Wahrscheinlichkeit in einen bestimmten Cluster gehören. Zusätzlich kann das ’Likelihood’ der Daten abgeschätzt und zum Vergleich unterschiedlicher Clustering-Ergebnisse verwendet werden. Beispielalgorithmen sind: EM, Bayes’sches Clustering.

Numerische Prognose

Mit Hilfe der numerischen Prognose, die zum Supervised Learning zählt, lassen sich numerische Größen vorhersagen. Die numerische Prognose ist vergleichbar mit der Klassifikation, nur dass hier eine numerische ’Klasse’ gebildet wird. Der Erfolg wird, wie bei der Klassifikation, anhand von Testdaten (oder subjektiv) gemessen.

Beispiel: Angepasste Version der Wetterdaten

Ein weiteres Beispiel ist die Vorhersage der CPU-Performance bei 209 unterschiedlichen Computer-Konfigurationen.

Beispiel: Angepasste Version der CPU-Performancedaten

Die lineare Regressionsfunktion hierzu:

Die Standardmethode für die numerische Prognose ist die lineare Regression. Alle Klassifikationsverfahren können auch auf Regressionsprobleme angewandt werden (z.B. Regressionsbäume), was aber eine Diskretisierung der Daten erfordert. Umgekehrt kann die lineare Regression auch zur Prognose nominaler Attribute (also zur Klassifizierung) verwendet werden.

Regression zur numerischen Prognose

Regression nennt man die Ermittlung eines mathematischen Ausdrucks zur Vorhersage einer numerischen Größe. Die lineare Regression verwendet lineare Funktionen als Annäherung. Das Ergebnis der linearen Regression ist eine Linearkombination von Attributen:

Die Gewichte werden anhand der Trainingsdaten ermittelt. Der Prognosewert für die erste Trainingsinstanz a(1):

Die lineare Regression basiert auf der Methode der kleinsten Quadrate. Die k+1 Koeffizienten werden so gewählt, dass der quadrierte Fehler der n Trainingsinstanzen minimal wird.

Der quadrierte Fehler über alle n Instanzen:

Die Koeffizienten können durch Standard-Matrixoperationen ermittelt werden, wenn mehr Instanzen als Attribute existieren (vereinfacht ausgedrückt). Die Minimierung des absoluten Fehlers ist schwieriger.

Regression zur Klassifikation
Eine lineare Regression kann auch zur Klassifikation verwendet werden.
Training: Für jede Klasse wird eine Regression ausgeführt, das Ergebnis wird für Instanzen in der Klasse auf 1 gesetzt, für die anderen auf 0.

Prognose:
Wahl der Klasse des Modells mit dem größten Ergebniswert (’Membership Value’).
Bei der linearen Regression nennt man dieses Verfahren ’Multi-Response Linear Regression’. Erweiterungen hierzu sind die Pairwise Regression oder die Logistic Regression.
Ferner haben Minsky and Papert (1969) gezeigt, dass es bei linearen Klassifikatoren Einschränkungen gibt, sie können z.B. kein XOR lernen.

Bäume zur numerischen Prognose

Ein Regressionsbaum ist ein ’Entscheidungsbaum’, bei dem die Blätter numerische Größen darstellen. Ein Regressionsbaum dient der numerischen ’Klassifikation’. Der prognostizierte Wert ist der Durchschnittswert der Trainingsinstanzen, die das Blatt erreichen.
Ein Modellbaum ist ein ’Regressionsbaum’ mit linearen Regressionsmodellen als Blattknoten. Unter Umständen sind Bäume zur numerischen Prognose die bessere Wahl als eine einfache lineare Regression.
Regressionsbäume unterscheiden sich von Entscheidungsbäumen dadurch, dass der Teilungsprozess endet, wenn die Streuung in der Teilmenge ein Minimum erreicht hat (z.B. 5%). Das Pruning-Kriterium basiert auf einem numerischen Fehlermaß. Ein Blattknoten prognostiziert den durchschnittlichen ’Klassen’-Wert der Trainingsinstanzen, die den Knoten erreichen.
Der Vorteil von Regressionsbäumen liegen darin, dass sie konstante Funktionen stückweise annähern können und leicht zu interpretieren sind.

Beispiel – Regressionsbaum für die CPU-Daten:

Regressionsbaum für die CPU-Daten

Die erweitere Version von Regressionsbäumen stellen Modellbäume dar. Modellbäume sind Regressionsbäume mit einer linearen Regressionsfunktion an jedem Knoten. Die lineare Regression wird auf die Instanzen eines Knotens angewendet, wenn der gesamte Baum erzeugt ist. Für die lineare Regression wird nur eine Teilmenge der Attribute verwendet. Verwendung finden nur die Attribute, die in dem Teilbaum vorkommen und unter Umständen solche, die auf dem Pfad zur Wurzel liegen. Der Overhead für die lineare Regression ist gering, da üblicherweise nur ein kleiner Teil der Attribute im Baum verwendet wird. Deshalb ist dieses Verfahren sehr schnell.
Beispiel – Modellbaum für die CPU-Daten:

Modellbaum für die CPU-Daten

Einfache lineare Modelle sind unangebracht, wenn die Daten nicht-lineare Abhängigkeiten aufweisen. Sie können aber als Bausteine für komplexere Lernschemata (Modellbäume) verwendet werden.
Regressionsbäume wurden in CART (Classification And Regression Tree) eingeführt. Quinlan entwickelte das M5 Modellbaum-Verfahren . M5 ist eine leicht verbesserte veröffentlichte Version.

Evaluation von numerischer Prognose

Bei der Evaluation numerischer Prognosen kommen die gleichen Strategien zum Einsatz wie zum Beispiel unabhängige Testmenge, Cross-Validation, oder Signifikanztests. Der Unterschied liegt im Fehlermaß.
Ein beliebtestes Maß ist der Mittelwert des quadrierten Fehlers:

Die tatsächlichen Zielwerte sind a1, a2, …, an, die prognostizierten sind Zielwerte p1, p2, …, pn.
Die Wurzel des Mittelwertes der quadrierten Fehler:

Der Mittelwert des absoluten Fehlers ist weniger anfällig gegen Ausreißer:

Manchmal sind relative Fehlerwerte angebrachter (z.B. 10% für einen Fehler von 50, wenn 500 prognostiziert wird).

Oft ist es wissenswert, wie gut ein Schema den Mittelwert prognostiziert. Der relative quadrierte Fehler lautet (ā ist der Mittelwert):

Der relative absolute Fehler lautet:

Der Korrelationskoeffizient misst die statistische Korrelation zwischen den prognostizierten und den tatsächlichen Werten:

Er ist skalenunabhängig und zwischen -1 und +1. Eine gute Prognose führt im Gegensatz zu anderen Fehlermaßen zu großen Werten.
Es stellt sich die Frage, welche Bewertungsmaßzahl verwendet werden soll. Man betrachtet am besten alle, da es oft keine Rolle spielt.

Beispiel: