Samstag, 21. Juli 2012

Data Mining mit Bordmitteln - Teil 1

Mit diesem Post möchte ich eine Reihe starten, welche sich mit dem Thema Data Mining beschäftigt; konkret die Implementierung von Algorithmen mit Bordmitteln samt den Besonderheiten, die im Datenbankumfeld zu beachten sind.

Als Beispiel dient ein Algorithmus zur Klassifikation auf der Basis von Entscheidungsbäumen - der ID3-Algorithmus. Doch bevor wir uns mit der Implementierung des Algorithmus beschäftigen, schauen wir uns zunächst das Ergebnis an. Zunächst wird der Algorithmus mit der Prozedur init initialisiert:
exec dm_id3.init(1,10);
Das erste Argument bestimmt das Projekt, während das zweite Argument die minimale Anzahl von Beobachtungen in einem Knoten festlegt; in diesem Fall muss jeder Knoten mindestens 10 Beobachtungen enthalten.

Das Projekt nimmt Bezug auf eine Tabelle, welche die Daten des Data Sets "Chess (King-Rook vs. King)" enthält.

Nach der erfolgreichen Initialisierung erfolgt ein Aufruf der Table-Funtion gain. Man erhält den Gain bzw. den Gain Ratio, also wie sehr sich ein Attribut zur weiteren Zerlegung eignet:
select * from table(dm_id3.gain(0)) order by gain desc;
NODE   ATTRIBUTE          INFO      SPLIT_INFO GAIN     
------ ------------------ --------- ---------- ---------- 
0      BLACK_KING_RANK    3.5041597 3.1896893  0.31446969 
0      WHITE_KING_RANK    3.5041597 3.2139022  0.29025673 
0      BLACK_KING_FILE    3.5041597 3.3190435  0.18511551 
0      WHITE_KING_FILE    3.5041597 3.3388416  0.16531733 
0      WHITE_ROOK_FILE    3.5041597 3.4540855  0.05007348 
0      WHITE_ROOK_RANK    3.5041597 3.4579962  0.04616276 
Man sieht, dass das Attribut "BLACK_KING_RANK" am besten geeignet ist, um eine Zerlegung des Root-Knoten vorzunehmen.

Um den Entscheidungsbaum zu erzeugen, wird die Prozedur make_tree aufgerufen:
exec dm_id3.make_tree(0);
Nun werfen wir einen Blick auf den erzeugten Entscheidungsbaum:
select * from table(dm_id3.show_tree(1));
NODE                              SUPPORT  PREDICTION   CONFIDENCE DEPTH
--------------------------------- -------- ------------ ---------- ------
0: 1 = 1                          28056    fourteen     4553       1
   1: BLACK_KING_RANK = 1         3664     eight        591        2
      9: WHITE_KING_FILE = a      372      eleven       89         3
         49: WHITE_ROOK_RANK = 1  36       draw         10         4
         50: WHITE_ROOK_RANK = 2  48       eight        19         4
         51: WHITE_ROOK_RANK = 3  48       ten          25         4
         52: WHITE_ROOK_RANK = 4  48       twelve       22         4
         53: WHITE_ROOK_RANK = 5  48       eleven       13         4
         54: WHITE_ROOK_RANK = 6  48       fourteen     13         4
         55: WHITE_ROOK_RANK = 7  48       fourteen     13         4
         56: WHITE_ROOK_RANK = 8  48       eleven       12         4
      10: WHITE_KING_FILE = b     620      ten          163        3
...
Man sieht unter anderem, dass das Attribut "BLACK_KING_RANK" tatsächlich für die Zerlegung des Root-Knoten verwendet wurde.

So viel für heute... in den kommenden Postings erfolgt dann die eigentliche Implementierung der eben gezeigten Funktionen.

1 Kommentar:

  1. Hallo,
    einen tollen und interessanten Blog führen Sie –
    man trifft im Internet selten auf so fundiertes Wissen. Danke dafür.
    Ich bin selber Student und baue auch eine Seite zum Thema Datenbanken(Datenbanken-verstehen.de)auf,
    welche allerdings nicht so tiefgehende Inhalte wie ihre Seite vermittelt,
    sondern ehre die Grundlagen. Würde mich gegebenenfalls über eine Verlinkung oder einen Linktausch freuen.
    Gruß, Markus

    AntwortenLöschen