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 

Korrekte Implementierung der Aggregatsfunktion SUM

Heute geht es um die bekannte Aggregatsfunktion SUM und deren nicht ganz optimales Verhalten. Damit meine ich im Wesentlichen die Rückgabe der Funktion, im Falle einer leeren Tabelle.

Betrachten wir dazu das folgende Beispiel:

create table empty_tab
(
 val number
);

select sum(val) sum_val from empty_tab;

Das Ergebnis ist eine Tabelle, die eine Spalte mit dem Namen SUM_VAL enthält deren "Wert" NULL ist; in der Session wurde zuvor set null ? ausgeführt.

SUM_VAL               
-----------------------
?

Und genau an dieser Stelle befindet sich der Fehler in der Implementierung, denn korrekt wäre die Rückgabe von 0. Eine Summe ohne Summanden (die leere Summe) ergibt in der Mathematik 0.

Natürlich kann man z.B. die Funktion COALESCE verwenden, um das gewünschte Ergebnis zu erhalten.

select coalesce(sum(val),0) sum_val from empty_tab;

SUM_VAL               
-----------------------
0

Aber glücklicherweise kann man mithilfe von User-Defined-Aggregates eine eigene Funktion, die ich RSUM nenne, implementieren, die ein korrektes Verhalten zeigt.

Dazu zunächst der Objekt-Typ:

create or replace type sum_t as object
(
  v_sum number,

  static function ODCIAggregateInitialize(
   sctx IN OUT sum_t) return number,

  member function ODCIAggregateIterate(
   self IN OUT sum_t, 
   value IN number) return number,

  member function ODCIAggregateTerminate(
   self IN sum_t, 
   returnValue OUT number, 
   flags IN number) return number,

  member function ODCIAggregateMerge(
   self IN OUT sum_t, 
   ctx2 IN sum_t) return number
);

Die Variable v_sum dient der Speicherung der Summe. Der nun folgende Rumpf des Objek-Typs enthält dann die korrekte Initialisierung mit 0 (siehe Zeile 6 des folgenden Listings).

create or replace type body sum_t is

  static function ODCIAggregateInitialize(
   sctx IN OUT sum_t) return number is
  begin
   sctx := sum_t(0);
   return ODCIConst.Success;
  end;
  
  member function ODCIAggregateIterate(
   self IN OUT sum_t, 
   value IN number) return number is
  begin
   self.v_sum := self.v_sum + value;
   return ODCIConst.Success;
  end;
  
  member function ODCIAggregateTerminate(
   self IN sum_t, 
   returnValue OUT number, 
   flags IN number) return number is
  begin
   returnValue := self.v_sum;
   return ODCIConst.Success;
  end;
  
  member function ODCIAggregateMerge(
   self IN OUT sum_t, 
   ctx2 IN sum_t) return number is
  begin
   self.v_sum := self.v_sum + ctx2.v_sum;
   return ODCIConst.Success;
  end;

end;

Jetzt fehlt nur noch die Funktion, welche den Objekt-Typ verwendet.

create or replace function rsum (input number) return number
deterministic parallel_enable aggregate using sum_t;

Eine Ausführung der Funktion RSUM auf einer leeren Tabelle liefert dann das korrekte Ergebnis 0 zurück. Anmerkung: Da die Methode ODCIAggregateIterate nur für Nicht-NULL's aufgerufen wird, gilt dies auch für eine Tabelle, die in der entsprechenden Spalte nur NULL's enthält.

select rsum(val) rsum_val from empty_tab;                 

RSUM_VAL               
-----------------------
0

Ähnlich verhält es sich übrigens bei der Aggregatsfunktion AVG zur Berechnung des arithmetischen Mittels. Wendet man die Funktion auf eine leere Tabelle an erhält man als Rückgabe NULL. Eine Fehlermeldung der Art "divisor is equal to zero" erschien mir in diesem Falle schlüssiger.