Montag, 13. Februar 2012

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 

Keine Kommentare:

Kommentar veröffentlichen

Kommentar veröffentlichen