Data Mining

13. Seminar: Grundlegende Algorithmen für Klassifikation I

Data Mining & PredictionData Mining & Prediction

Grundlegende Algorithmen für Grundlegende Algorithmen für Klassifikation IKlassifikation I

Martin Held & Martin LangwischMartin Held & Martin Langwisch


GliederungGliederung

1.1. EinführungEinführung

2.2. EntscheidungsbäumeEntscheidungsbäumeKonstruktion, InformationsmaßKonstruktion, Informationsmaß

3.3. Instanzbasiertes LernenInstanzbasiertes Lernen


Classification & PredictionClassification & Prediction

Beides wird benutzt, um aus gegebenen Daten Beides wird benutzt, um aus gegebenen Daten ein Model zu gewinnen, um wichtige ein Model zu gewinnen, um wichtige Datenklassen bzw. zukünftige Trends zu Datenklassen bzw. zukünftige Trends zu beschreiben.beschreiben.

Classification – Vorhersage der Klasse oder des Classification – Vorhersage der Klasse oder des AttributwertesAttributwertesPrediction – Vorhersage der Klasse, des Wertes oder Prediction – Vorhersage der Klasse, des Wertes oder WertebereichesWertebereiches

keine eindeutige Definition beider Begriffe!keine eindeutige Definition beider Begriffe!

Classification: Vorhersage diskreter Werte/Classification: Vorhersage diskreter Werte/ Bestimmung der Klassenwerte Bestimmung der Klassenwerte

Prediction: Vorhersage kontinuierlicher Werte/Prediction: Vorhersage kontinuierlicher Werte/ Vorhersage der Klassenwerte Vorhersage der Klassenwerte


BeispieleBeispiele

Kundendatenbank eines HardwarevertreibersKundendatenbank eines Hardwarevertreibers

Classification:Classification:Werbung für die neuesten Rechner soll verteilt werdenWerbung für die neuesten Rechner soll verteilt werdenrelativ teuer wenn alle Kunden beschickt werden, jedoch nur relativ teuer wenn alle Kunden beschickt werden, jedoch nur wenige kaufenwenige kaufen

Welche (Gruppe von) Kunden werden die neuen Rechner Welche (Gruppe von) Kunden werden die neuen Rechner kaufen?kaufen?

Prediction:Prediction:neues Geschäftsjahr wird geplantneues Geschäftsjahr wird geplant

Wieviel Geld werden die Kunden in welchen Bereichen ausgeben?Wieviel Geld werden die Kunden in welchen Bereichen ausgeben?


DatenaufbereitungDatenaufbereitung

Data cleaning:Data cleaning:

Reduzierung oder Löschen verrauschter WerteReduzierung oder Löschen verrauschter Werte

Wie behandelt man fehlende WerteWie behandelt man fehlende Werte

Relevance analysis:Relevance analysis:

Herausfiltern der irrelevanten AttributeHerausfiltern der irrelevanten Attribute(wann wurde ein Rechner gekauft)(wann wurde ein Rechner gekauft)

Komprimierung von redundanten AttributenKomprimierung von redundanten Attributen

Data transformationData transformation

Verallgemeinern von Daten mithilfe von Konzepthierarchien Verallgemeinern von Daten mithilfe von Konzepthierarchien (Gruppe Drucker statt spezieller Name, Peripheriegeräte statt (Gruppe Drucker statt spezieller Name, Peripheriegeräte statt Drucker, …)Drucker, …)

Normalisieren von Daten auf einen bestimmten WertebereichNormalisieren von Daten auf einen bestimmten Wertebereich

verhindert Übergewichtung von Werten mit großem verhindert Übergewichtung von Werten mit großem WertebereichWertebereich


Wie funktioniert Classification?Wie funktioniert Classification?

Lernen eines Models durch einen Lernen eines Models durch einen Classification-AlgorithmusClassification-Algorithmus

Evaluierung des gelerntes ModellsEvaluierung des gelerntes Modells

Klassifizierung neuer DatenKlassifizierung neuer Daten


Lernen eines ModellsLernen eines Modellssupervised Learning (überwachtes Lernen)supervised Learning (überwachtes Lernen)

Funktion aus Trainingsdaten gewinnenFunktion aus Trainingsdaten gewinnen

jedes sample besteht aus Werten fü die Input-Attribute und Wert des jedes sample besteht aus Werten fü die Input-Attribute und Wert des vorherzusagenden Attributesvorherzusagenden Attributes

Funktion soll für ein beliebiges neues Objekt den Attributwert Funktion soll für ein beliebiges neues Objekt den Attributwert ausgebenausgeben

Probleme: Overfitting (Erlernen von Eigenheiten der Trainingsdaten)Probleme: Overfitting (Erlernen von Eigenheiten der Trainingsdaten)Beispiele: Entscheidungsbäume, Klassifikationsregeln, …Beispiele: Entscheidungsbäume, Klassifikationsregeln, …

unsupervised Learning (nicht überwachtes Lernen)unsupervised Learning (nicht überwachtes Lernen) keine a priori-Ausgabewertekeine a priori-Ausgabewerte

Daten werden aufgrund ihrer Attributwerte in Gruppen eingeteiltDaten werden aufgrund ihrer Attributwerte in Gruppen eingeteilt

Probleme: Anzahl und Art der Gruppen ist unbekanntProbleme: Anzahl und Art der Gruppen ist unbekanntBeispiele: k-means, hierarchical clustering, …Beispiele: k-means, hierarchical clustering, …


Klassifikation mit Entscheidungsbäumen



Traingsdaten Traingsdaten ## AlterAlter EinkommenEinkommen StudentStudent BonitätBonität Kauft Kauft

ComputerComputer

11 <30<30 HochHoch NeinNein AusreichendAusreichend NeinNein

22 <30<30 HochHoch NeinNein AusgezeichnetAusgezeichnet NeinNein

33 30-4030-40 HochHoch NeinNein AusreichendAusreichend JaJa

44 >40>40 MittelMittel NeinNein AusreichendAusreichend JaJa

55 >40>40 NiedrigNiedrig JaJa AusreichendAusreichend JaJa

66 >40>40 NiedrigNiedrig JaJa AusgezeichnetAusgezeichnet NeinNein

77 30-4030-40 NiedrigNiedrig JaJa AusgezeichnetAusgezeichnet JaJa

88 <30<30 MittelMittel NeinNein AusreichendAusreichend NeinNein

99 <30<30 NiedrigNiedrig JaJa AusreichendAusreichend JaJa

1010 >40>40 MittelMittel JaJa AusreichendAusreichend JaJa

1111 <30<30 MittelMittel JaJa AusgezeichnetAusgezeichnet JaJa

1212 30-4030-40 MittelMittel NeinNein AusgezeichnetAusgezeichnet JaJa

1313 30-4030-40 HochHoch JaJa AusreichendAusreichend JaJa

1414 >40>40 MittelMittel NeinNein AusgezeichnetAusgezeichnet NeinNein

xx 30-4030-40 HochHoch JaJa AusgezeichnetAusgezeichnet ??????


Alter?

Student? Bonität?

< 30

30-40

> 40

Ja Nein

ausg

ezeic

hnet ausreichend

Ja

Ja Nein JaNein



xx 30-4030-40 HochHoch JaJa AusgezeichnetAusgezeichnet ??????




AlterAlter Ein-Ein-kommenkommen StudentStudent BonitätBonität

JaJaJaJa

NeinNeinNeinNeinNeinNein

JaJaJaJaJaJaJaJa

JaJaJaJaJaJa

NeinNeinNeinNein

<30<30 >40>4030 - 4030 - 40

JaJaJaJaJaJa

NeinNein

JaJaJaJaJaJaJaJa

NeinNeinNeinNein

JaJaJaJa

NeinNeinNeinNein

NNMM HH

JaJaJaJaJaJaJaJaJaJaJaJa

NeinNein

JaJaJaJaJaJa

NeinNeinNeinNeinNeinNeinNeinNein

JaJa NeinNein

JaJaJaJaJaJa


JaJaJaJaJaJaJaJaJaJaJaJa

NeinNeinNeinNein

++++++ ++


AlterAlter

JaJaJaJa


JaJaJaJaJaJaJaJa

JaJaJaJaJaJa

NeinNeinNeinNein

<30<30 >40>4030 - 4030 - 40

JaJa

JaJa JaJaNeinNein

NeinNeinNeinNein

NNMM HH

Ein-Ein-kommenkommen

JaJaJaJa


JaJa NeinNein

StudentStudent

JaJaNeinNein

JaJaNeinNeinNeinNein

++++++ ++

BonitätBonität


AlterAlter

JaJaJaJaJaJa

NeinNeinNeinNein

<30<30 >40>4030 - 4030 - 40

JaJa NeinNein

StudentStudent JaJa

JaJa NeinNein

JaJaNeinNein

JaJaJaJa

NeinNein

NNMM HH


NeinNeinNeinNein

JaJaJaJaJaJa

++++++ ++

BonitätBonität

JaJaJaJa

NeinNein

JaJaNeinNein

JaJa NeinNein

StudentStudent


AlterAlter

<30<30 >40>4030 - 4030 - 40

JaJa NeinNein

StudentStudent JaJa

JaJa NeinNein

JaJaNeinNein

JaJaJaJa

NeinNein

NNMM HH


NeinNeinNeinNein

JaJaJaJaJaJa

++++++ ++

BonitätBonität

JaJaJaJa

NeinNein

JaJaNeinNein

JaJa NeinNein

StudentStudent

++++++ ++

BonitätBonität

JaJaNeinNein


Algorithmus (ID3)Algorithmus (ID3)Generate_decision_tree(Generate_decision_tree(samplessamples, , attribute-listattribute-list))

01: create a Node 01: create a Node NN02: 02: ifif samplessamples are all of the same class are all of the same class CC thenthen03:03: return return NN as a leaf node labeled with class as a leaf node labeled with class CC04: 04: ifif attribute-listattribute-list is empty is empty thenthen05:05: return return NN as a leaf node with most common class in samples as a leaf node with most common class in samples06: select 06: select test-attributetest-attribute from from attribute-listattribute-list with highest information gain with highest information gain07: label node 07: label node NN with with test-attributetest-attribute08: 08: for eachfor each known value known value aaii of of test-attributetest-attribute

09:09: grow a branch from node grow a branch from node NN for for aiai10:10: let let ssii be the set of samples in be the set of samples in samplessamples where where test-attributetest-attribute==aaii

11:11: ifif ssii is empty is empty thenthen

12:12: attach a leaf labeled with most common class in samplesattach a leaf labeled with most common class in samples13:13: elseelse14:14: attach node returned byattach node returned by

Generate_decision_tree(Generate_decision_tree(ssi i , , attribute-list attribute-list –– test-attribute test-attribute))


Weitere AlgorithmenWeitere Algorithmen

CHAID CHAID (1975 J.A. Hartigan)(1975 J.A. Hartigan)

Ältester Algorithmus, PrepruningÄltester Algorithmus, Prepruning

CART CART (1984 L. Briemen)(1984 L. Briemen)

Nur Binär-Bäume, Pruning von Subtrees unter Nur Binär-Bäume, Pruning von Subtrees unter Berücksichtigung eines unabh. TestsetsBerücksichtigung eines unabh. Testsets

ID3 ID3 (1986 Ross Quinlan)(1986 Ross Quinlan)

Top-down induction of decision trees (TDIDT)Top-down induction of decision trees (TDIDT)

C4.5 C4.5 (1993)(1993) und J4.8 und J4.8 (?) (?) Ross QuinlanRoss Quinlan

Verbesserung von ID3Verbesserung von ID3

Nicht vorhandene Werte, kontinuierliche Variablen, Pruning, Nicht vorhandene Werte, kontinuierliche Variablen, Pruning, EntscheidungsregelnEntscheidungsregeln


Information Gain / EntropyInformation Gain / Entropy

Welches Attribut trennt die Daten am besten?Welches Attribut trennt die Daten am besten?

Welches Attribut produziert die ‚saubersten‘ Welches Attribut produziert die ‚saubersten‘ Kinderknoten?Kinderknoten?

Maß für Informationsgehalt / EntropieMaß für Informationsgehalt / Entropie

Wenn nur ein Klassenwert H = 0Wenn nur ein Klassenwert H = 0

Wenn alle Klassenwerte gleich wahrscheinlich größte Wenn alle Klassenwerte gleich wahrscheinlich größte EntropieEntropie

21

( ) logv

i ii

H I p p

21

( ) logv

i ii

H I p p

ip ip W‘keit für pW‘keit für pii


( ) 0.693H Alter ( ) 0.693H Alter

2 2 3 3log log 0.9715 5 5 5

2 2 3 3log log 0.9715 5 5 5

4 4log 04 4

4 4log 04 4

3 3 2 2log log 0.9715 5 5 5

3 3 2 2log log 0.9715 5 5 5

Entropie BeispielEntropie Beispiel

AlterAlter

Ja Ja Nein Nein NeinJa Ja Nein Nein Nein

Ja Ja Ja JaJa Ja Ja Ja

Ja Ja Ja Nein NeinJa Ja Ja Nein Nein

<30<30

>40>40

30 - 4030 - 40

Entropie von Alter?Entropie von Alter?

5 4 5( ) *0.971 *0 *0.971

14 14 14H Alter

5 4 5( ) *0.971 *0 *0.971

14 14 14H Alter


Information GainInformation Gain

( ) 0.693H Alter ( ) 0.693H Alter Entropie von Alter?Entropie von Alter?

Entropie vor Berücksichtigung von Alter:Entropie vor Berücksichtigung von Alter:

Ja Ja Ja Ja Ja Ja Ja Ja Ja Nein Nein Nein Nein NeinJa Ja Ja Ja Ja Ja Ja Ja Ja Nein Nein Nein Nein Nein

9 9 5 5( ) log log 0.94

14 14 14 14H C

Klassenaufteilung C =Klassenaufteilung C =

9 9 5 5( ) log log 0.94

14 14 14 14H C

Informationsgewinn duch Alter:Informationsgewinn duch Alter:

( ) ( ) ( ) 0.247gain Alter H C H Alter ( ) ( ) ( ) 0.247gain Alter H C H Alter


( ) ( ) ( ) 0.247Gain Alter H C H Alter ( ) ( ) ( ) 0.247Gain Alter H C H Alter

Information GainInformation Gain

( ) 0.029

( ) 0.151

( ) 0.048

Gain Einkommen

Gain Student

Gain Bonität

( ) 0.029

( ) 0.151

( ) 0.048

Gain Einkommen

Gain Student

Gain Bonität


Tree pruningTree pruning

Pruning – entfernen überflüssiger KnotenPruning – entfernen überflüssiger Knoten

wirkt Overfitting des Entscheidungsbaumes wirkt Overfitting des Entscheidungsbaumes entgegenentgegen

Ziele: Ziele:

Verbesserung der Klassifikationseigenschaft Verbesserung der Klassifikationseigenschaft auf unbekannten Datenauf unbekannten Daten

Schnellere KlassifikationSchnellere Klassifikation

PrepruningPrepruning PostpruningPostpruning


PrepruningPrepruning

Baumstruktur einfach haltenBaumstruktur einfach halten

Knoten nicht splitten, wenn ‚Güte‘ eines Splits an Knoten nicht splitten, wenn ‚Güte‘ eines Splits an

diesem Knoten unter einen bestimmten diesem Knoten unter einen bestimmten

Schwellenwert fälltSchwellenwert fällt

z.B. Information Gain zu klein istz.B. Information Gain zu klein ist

Problem: Wahl des richtiges SchwellenwertesProblem: Wahl des richtiges Schwellenwertes

Schwellenwert zu Groß Schwellenwert zu Groß zu stark vereinfacht zu stark vereinfacht

Schwellenwert zu Klein Schwellenwert zu Klein zu wenig vereinfacht zu wenig vereinfacht


PostpruningPostpruning

Entfernen von Knoten eines fertig gewachsenen BaumesEntfernen von Knoten eines fertig gewachsenen Baumes

z.B. Cost complexity algorithmz.B. Cost complexity algorithm

Für jeden inneren Knoten des Baumes vergleicheFür jeden inneren Knoten des Baumes vergleiche

Fehlerrate wenn Subtree unter dem Knoten weggeschnittenFehlerrate wenn Subtree unter dem Knoten weggeschnitten

vs.vs.

Fehlerrate wenn Subtree unter dem Knoten erhaltenFehlerrate wenn Subtree unter dem Knoten erhalten

Wenn das Pruning zu einer höheren Fehlerrate führt, bleibt Wenn das Pruning zu einer höheren Fehlerrate führt, bleibt der Subtree erhalten, sonst wegder Subtree erhalten, sonst weg

Postpruning ist rechenaufwendiger als Prepruning, erzeugt Postpruning ist rechenaufwendiger als Prepruning, erzeugt aber zuverlässigere Bäumeaber zuverlässigere Bäume


1-Rule (1R)1-Rule (1R)

„„Very simple classification rules perform Very simple classification rules perform well on most commonly used datasets“ well on most commonly used datasets“ (Holte 1993)(Holte 1993)

Einfache Regeln Einfache Regeln hohe Genauigkeit hohe Genauigkeit

1 stufiger Entscheidungsbaum1 stufiger Entscheidungsbaum

Benutzte das Attribut mit der geringsten Benutzte das Attribut mit der geringsten FehlerrateFehlerrate

Nur wenige Prozentpunkte schlechter als Nur wenige Prozentpunkte schlechter als als state-of-the-art Lernalgorithmenals state-of-the-art Lernalgorithmen


WEKA EXAMPLEWEKA EXAMPLE


Evaluierung des gelernten ModellsEvaluierung des gelernten Modells

prediction accuracy –prediction accuracy – Verhältnis der korrekten Vorhersagen zu allen Verhältnis der korrekten Vorhersagen zu allen VorhersagenVorhersagen

speed - Zeit für Bau und Benutzung des Modellsspeed - Zeit für Bau und Benutzung des Modells

robustness –robustness – Robustheit gegenüber fehlenden Werten, verrauschten Robustheit gegenüber fehlenden Werten, verrauschten DatenDaten

scalability – Anwendbarkeit des Modells auf große Datenmengenscalability – Anwendbarkeit des Modells auf große Datenmengen

interpretability –interpretability – erzeugt das Modell tieferes Verständnis oder neue erzeugt das Modell tieferes Verständnis oder neue Erkenntnisse?Erkenntnisse?

WIE?WIE?

Aufteilen der Trainingsdaten in trainings set und test setAufteilen der Trainingsdaten in trainings set und test set

Lernen mit Trainingsset, danach Vorhersage der Werte des TestsetsLernen mit Trainingsset, danach Vorhersage der Werte des Testsets nur möglich bei großer Traingsdatenmenge nur möglich bei großer Traingsdatenmenge

bei geringer Trainingsdatenmenge: k-fold cross validationbei geringer Trainingsdatenmenge: k-fold cross validation


Klassifikationsregeln aus Entscheidungsbäumen

Klassifikationsregeln aus Entscheidungsbäumen

Sinn: Klassifikationsregeln sind intuitiver als EntscheidungsbäumeSinn: Klassifikationsregeln sind intuitiver als Entscheidungsbäume

Aus jedem Weg, den es im Entscheidungsbaum gibt, wird eine Regel Aus jedem Weg, den es im Entscheidungsbaum gibt, wird eine Regel erstellt, wobei die Knoten durch ‚UND‘ ersetzt werden. Ein Blatt wird erstellt, wobei die Knoten durch ‚UND‘ ersetzt werden. Ein Blatt wird durch ‚THEN‘ + Label ersetzt.durch ‚THEN‘ + Label ersetzt.

++++++ ++

BonitätBonität

AlterAlter

<30<30 >40>4030 - 4030 - 40

JaJa NeinNein

StudentStudent JaJa

JaJa NeinNein JaJaNeinNein

IF (ALTER < 30) AND (STUDENT = JA) THEN JAIF (ALTER < 30) AND (STUDENT = JA) THEN JA

IF (ALTER < 30) AND (STUDENT = NEIN) THEN NEINIF (ALTER < 30) AND (STUDENT = NEIN) THEN NEIN

IF (30 IF (30 ≤ ≤ ALTER ≤ 40) THEN JAALTER ≤ 40) THEN JA

IF (ALTER > 40) AND (BONITÄT = +++) THEN NEINIF (ALTER > 40) AND (BONITÄT = +++) THEN NEIN

IF (ALTER > 40) AND (BONITÄT = +) THEN JAIF (ALTER > 40) AND (BONITÄT = +) THEN JA


Verbesserungen von EntscheidungsbäumenVerbesserungen von

Entscheidungsbäumen

Decision Tree Induction: für jeden Wert eines Attributes neueDecision Tree Induction: für jeden Wert eines Attributes neueKanteKante

Problem: viele Attributwerte Problem: viele Attributwerte Fragmentierung der Daten Fragmentierung der Daten statistisch nicht signifikante Teilmengen statistisch nicht signifikante TeilmengenLösung: Gruppierung von Attributwerten, BinärbäumeLösung: Gruppierung von Attributwerten, BinärbäumeBinärbäume: Auftrennung nur nach ‚besten‘ Attributwert Binärbäume: Auftrennung nur nach ‚besten‘ Attributwert andere Attributwerte können im Unterbaum wieder andere Attributwerte können im Unterbaum wieder auftreten (dort bessere Auftrennung)auftreten (dort bessere Auftrennung)

information gain bevorzugt Attribute mit vielen Werteninformation gain bevorzugt Attribute mit vielen Werten Einführung anderer MaßeEinführung anderer Maße

gain ratio: Einbeziehung der Fragmentierung der Attributegain ratio: Einbeziehung der Fragmentierung der AttributeChi square contigency table statistic, gini index, G-statisticChi square contigency table statistic, gini index, G-statistic

Incremental versions – restructure decision trees instead of Incremental versions – restructure decision trees instead of building new onesbuilding new ones


Skalierbarkeit von Entscheidungsbäumen

Skalierbarkeit von Entscheidungsbäumen

Viele Algorithmen gehen von Datenmengen aus, die im SpeicherViele Algorithmen gehen von Datenmengen aus, die im Speicherverbleiben können.verbleiben können.

trifft auf reale Daten nicht zu (Wal Mart)trifft auf reale Daten nicht zu (Wal Mart)Swapping macht Algorithmen unbrauchbarSwapping macht Algorithmen unbrauchbar

Lösungen:Lösungen:Diskretisierung der Werte, Erstellung der Untermengen bei jeder Diskretisierung der Werte, Erstellung der Untermengen bei jeder Aufteilung (weniger Daten im Speicher)Aufteilung (weniger Daten im Speicher)Teilen der Daten in Blöcke, die in den Speicher passen;Teilen der Daten in Blöcke, die in den Speicher passen;Bau vieler subset-decision trees;Bau vieler subset-decision trees;finaler decision tree enthält alle subset-decision treesfinaler decision tree enthält alle subset-decision trees

neuere Algorithmen sortieren die Daten auf der Platte und benutzenneuere Algorithmen sortieren die Daten auf der Platte und benutzenneue Datenstrukturen, um das Swapping zu vermindern (Teilung derneue Datenstrukturen, um das Swapping zu vermindern (Teilung derDaten nach Attributen, nicht nach Datentupeln)Daten nach Attributen, nicht nach Datentupeln)

SLIQ, SPRINTSLIQ, SPRINT


SLIQ (supervised Learning in Quest)SLIQ (supervised Learning in Quest)

nutzt attribute lists (auf Platte) undnutzt attribute lists (auf Platte) und

class list (im Speicher)class list (im Speicher)

alle Listen durch den rid (record identifier) alle Listen durch den rid (record identifier) verbundenverbunden

rid identifiziert Datentupelrid identifiziert Datentupel

bei jeder Bewertung wird nur eine attribute bei jeder Bewertung wird nur eine attribute list in den Speicher genommenlist in den Speicher genommen


|Class list| = # Datentupel|Class list| = # Datentupel wenn # Datentupel größer als Speicher wenn # Datentupel größer als Speicher SLIQ wird langsam SLIQ wird langsam


SPRINTSPRINTbenutzt attribute lists, die sowohl rid, als auch class benutzt attribute lists, die sowohl rid, als auch class identifier tragenidentifier tragenbei Aufteilung der Listen wird hash-table genutztbei Aufteilung der Listen wird hash-table genutzt kein neues Sortieren kein neues Sortieren

SPRINT hat keine Speicherbeschränkungen mehr, SPRINT hat keine Speicherbeschränkungen mehr, benötigt jedoch eine hash table beim Aufteilen der benötigt jedoch eine hash table beim Aufteilen der Listen, was bei großen Traingsmengen teuer Listen, was bei großen Traingsmengen teuer werden kannwerden kann


Integration von data warehousing Techniken

Integration von data warehousing Techniken

Attribute-oriented indution (AOI)Attribute-oriented indution (AOI)Konzepthierarchien werden benutzt, um low level-Konzepthierarchien werden benutzt, um low level-Daten durch higher level-Daten zu ersetzten:Daten durch higher level-Daten zu ersetzten:statt des Einkommens wird in Gruppen reich, statt des Einkommens wird in Gruppen reich, mittel, arm eingeteiltmittel, arm eingeteilt

solche Daten werden imsolche Daten werden immultidimensionalenmultidimensionalenDaten-Würfel zusammen-Daten-Würfel zusammen-gefaßtgefaßterlaubt data mining auferlaubt data mining aufverschiedenenverschiedenenAbstraktionsebenenAbstraktionsebenen


Instanzen-basiertes Lernen: K-nearest neighbours

Instanzen-basiertes Lernen: K-nearest neighbours

Daten werden durch Ähnlichkeit zu bekannten Daten klassifiziert:Daten werden durch Ähnlichkeit zu bekannten Daten klassifiziert:Jede Instanz wird als Punkt im n-dimensionalen Raum betrachtet.Jede Instanz wird als Punkt im n-dimensionalen Raum betrachtet.Klassifizierung einer Instanz durch die k nächsten Instanzen im Raum.Klassifizierung einer Instanz durch die k nächsten Instanzen im Raum.

Abstandsmaß: Abstandsmaß:

höhere Potenzen erhöhen den Einfluß großer höhere Potenzen erhöhen den Einfluß großer Unterschiede, meist ist der euklidischer Abstand das Unterschiede, meist ist der euklidischer Abstand das

günstigste Maßgünstigste Maß

Vorraussetzung: Abstand zwischen Attributwerten ist meßbarVorraussetzung: Abstand zwischen Attributwerten ist meßbar

bei nicht-geordneten Werten (nominal) ist der Abstand 0, wenn sie gleich bei nicht-geordneten Werten (nominal) ist der Abstand 0, wenn sie gleich sind, und 1 sonstsind, und 1 sonstWerte werden auf 1 normalisiert, Werte werden auf 1 normalisiert, umum ungewollte Gewichtung zu vermeiden ungewollte Gewichtung zu vermeiden

1

( , ) ( - )n

ppi i

i

d X Y x y

1

( , ) ( - )n

ppi i

i

d X Y x y


K-nearest neighbours: BeispielK-nearest neighbours: Beispiel


K-nearest neighboursK-nearest neighbours

Classification:Classification:

durch Mehrheitsentscheidungdurch Mehrheitsentscheidung

prozentuale Classificationprozentuale Classification

Probleme:Probleme:

sehr große Datenmenge, sehr große Datenmenge, sehr großer sehr großer BerechnungsaufwandBerechnungsaufwand

je mehr Dimensionen desto höher der Aufwandje mehr Dimensionen desto höher der Aufwand

sehr kleines k sehr kleines k Aussage statistisch nicht relevant Aussage statistisch nicht relevant

relativ großes k ebenfallsrelativ großes k ebenfalls(wenn k ~ |Daten|, bzw. k >> |Klassenmenge|)(wenn k ~ |Daten|, bzw. k >> |Klassenmenge|)


ZusammenfassungZusammenfassung

Classification/Prediction: Zuordnung/Vorhersage von Klassen unter Classification/Prediction: Zuordnung/Vorhersage von Klassen unter Berücksichtigung von TrainingsdatenBerücksichtigung von Trainingsdaten

Entscheidungsbäume:Entscheidungsbäume:Einfache KlassifikationsmethodeEinfache KlassifikationsmethodeEinfache Bäumen können gute Ergebnisse erzielen (1 Rule)Einfache Bäumen können gute Ergebnisse erzielen (1 Rule)Overfitting-Gefahr durch Pruning verringertOverfitting-Gefahr durch Pruning verringert

Instanzen-basiertes LernenInstanzen-basiertes LernenClassification/ Prediction durch Ähnlichkeit zu anderen InstanzenClassification/ Prediction durch Ähnlichkeit zu anderen InstanzenAbhängig von DistanzmaßAbhängig von Distanzmaßunpraktisch bei großen Datenmenge und/oder hochdimensionalen unpraktisch bei großen Datenmenge und/oder hochdimensionalen DatenDaten

Algorithmen sind datenabhängig Algorithmen sind datenabhängig Data cleaning, Relevance Data cleaning, Relevance analysis, Data transformation sollten durchgeführt werdenanalysis, Data transformation sollten durchgeführt werden


QuellenQuellen

Ian H. Witten, Elbe Frank: Data Mining. Morgan Kaufmann Publishers, Ian H. Witten, Elbe Frank: Data Mining. Morgan Kaufmann Publishers, San Francisco 1999 (4.1, 4.3, 4.7)San Francisco 1999 (4.1, 4.3, 4.7)

Jiawei Han, Micheline Kamber: Data Mining: Concepts and Jiawei Han, Micheline Kamber: Data Mining: Concepts and Techniques. Morgan Kaufmann, 2001 (7.1, 7.2, 7.3, 7.7.1)Techniques. Morgan Kaufmann, 2001 (7.1, 7.2, 7.3, 7.7.1)

Weka 3.4 Software, Weka 3.4 Software, http://http://www.cs.waikato.ac.nz/ml/wekawww.cs.waikato.ac.nz/ml/weka//

Wikipedia, http://www.wikipedia.orgWikipedia, http://www.wikipedia.org

Documents

Data Mining