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.

Aggregatsfunktion zur Berechnung der Entropie

Heute geht's um die Berechnung der Entropie mithilfe einer benutzerdefinierten Aggregatsfunktion. Die Entropie ist ein Maß aus der Informationstheorie und findet unter anderem Anwendung in Data Mining Algorithmen wie ID3 und dessen Nachfolger C4.5.

Die Formel zur Berechnung lautet wie folgt:

Dabei bezeichnet c die Anzahl der Ausprägungen, ni die Anzahl der Elemente der i-ten Ausprägung und n die Anzahl aller Elemente.

Anhand folgender Daten soll die Entropie für das Attribut credit_rating berechnet werden.

NAME     CREDIT_RATING
-------- -------------
SMITH    A
BLAKE    B
ALLEN    A
KING     B
JONES    B
CLARK    B
JAMES    B

Man erhält die Entropie zu:

Es sollte aufgefallen sein, dass die Formel nicht der Arbeitsweise von SQL und der von Aggregatsfunktionen entspricht, da die Gesamtanzahl in der Regel erst am Ende zur Verfügung steht.

Durch einige Umformungen erhält man jedoch die gewünschte Form:

Nun lassen sich die Bestandteile der Formel den Phasen von Aggregatsfunktionen zuordnen:

create or replace type entropy_t as object
(
  v_sum integer,
  v_entropy number,
  
  static function odciaggregateinitialize(
   sctx in out entropy_t) return number,
  
  member function odciaggregateiterate(
   self in out entropy_t, 
   value in integer) return number,
  
  member function odciaggregateterminate(
   self in entropy_t, 
   returnvalue out number,
   flags in number) return number,
  
  member function odciaggregatemerge(
   self in out entropy_t, 
   ctx2 in entropy_t) return number
);
/

create or replace type body entropy_t is

  static function odciaggregateinitialize(
   sctx in out entropy_t) return number is
  begin
   sctx := entropy_t(0,0.00);
   return odciconst.success;
  end;
  
  member function odciaggregateiterate(
   self in out entropy_t, 
   value in integer) return number is
  begin
   self.v_entropy := self.v_entropy - value * log( 2, value );
   self.v_sum := self.v_sum + value;
   return odciconst.success;
  end;
  
  member function odciaggregateterminate(
   self in entropy_t, 
   returnvalue out number, 
   flags in number) return number is
  begin
   returnvalue := ( self.v_entropy / self.v_sum ) +  log( 2, self.v_sum );
   return odciconst.success;
  end;
  
  member function odciaggregatemerge(
   self in out entropy_t, 
   ctx2 in entropy_t) return number is
  begin
   return odciconst.success;
  end;

end;
/

Nun fehlt nur noch die entsprechende Funktion.

create or replace function entropy (input integer) return number
parallel_enable aggregate using entropy_t;

Ein Aufruf der Funktion kann dann wie folgt erfolgen:

select
 entropy(count(*)) entropy
from
 customer
group by
 credit_rating;

ENTROPY
---------
0.8631206