Besseres Entropiemaß

[BAGZZlash]

Ich habe zwei Mengen von Informationen (sagen wir mal, Vektoren gleicher Dimension), deren Entropie ich vergleichen möchte. Momentan mache ich das, indem ich einfach die Standardabweichungen vergleiche. Gibt's da auch coolere Herangehensweisen?

[Spasstiger]

http://www.forum-3dcenter.org/vbulletin/showthread.php?t=452841

Ist aber nur für die Entropie, wenn man einzelne Zeichen betrachtet. Um das Einsparpotential für einen Komprimierer und somit die "vollständige" Entropie zu berechnen, müsste man alle möglichen Zeichenkombinationen aller Längen zählen.

Die eigentliche Entropieberechnung in meinem Skript liegt in diesen drei Zeilen:
n=hist(content,values); % absolute Häufigkeiten ermitteln
p = n ./ sum(n); % Häufigkeiten prozentual
E = -nansum(p.*log2(p)) % Entropie in Bits pro Zeichen (Byte)
content ist dabei der Vektor mit der Zeichenfolge, values der Vektor mit den möglichen Zeichen und p der Vektor, der jedem Zeichen die prozentuale Häufigkeit zuweist. nansum ist einfach eine Summenfunktion, die NaN-Werte ignoriert.

Die Standardabweichung sagt eigentlich recht wenig über die Entropie aus. Wenn du eine Ziffenfolge 090909090909 aus einem Alphabet von 10 Ziffern hast, ist die Entropie genauso groß wie für die Ziffernfolge 454545454545, obwohl natürlich die Standardabweichung im ersten Fall viel größer ist.

[BAGZZlash]

Super, vielen Dank für die Antwort. Okay, also relative Häufigkeiten und dann die Summe der Logarithmen der Kehrwerte der relativen Häufigkeiten, ja? Zwei Beispiele:

http://www.matheboard.de/latex2png/latex2png.php?X%20=%20\left(\begin{array}{c}A\\B\\C\\D\\E\\\end{array}\right) und http://www.matheboard.de/latex2png/latex2png.php?Y%20=%20\left(\begin{array}{c}A\\B\\A\\A\\C\\\end{array}\right).

Entropie von X: log(5) + log(5) + log(5) + log(5) + log(5) = 8,0472.

Entropie von Y: log(5/3) + log(5) + log(5/3) + log(5/3) + log(5) = 4,7514.

Richtig?

Das Ganze ist nur ein kleiner Teil eines Bildanalysetools, die Daten sind Pixelfarben von Fotos. Da dort ja schon kleinste farbliche Abweichungen einen anderen Farbcode erzeugen, dürfte die relative Häufigkeit jeder Farbe stets 1/n sein. Hm, ich implementier' das erst mal und schaue, ob da was Vernünftiges bei rauskommt.

[BAGZZlash]

Rückmeldung: Okay, das Ergebnis ist erheblich besser als das mit der Standardabweichung! Vielen Dank nochmal für die Hinweise! :-)

[Spasstiger]

Entropie von X: log(5) + log(5) + log(5) + log(5) + log(5) = 8,0472.

Entropie von Y: log(5/3) + log(5) + log(5/3) + log(5/3) + log(5) = 4,7514.

Richtig?
Nein, das ist so nicht korrekt berechnet. Zum Einen hast du die Multiplikation mit der relativen Häufigkeit übersehen, zum anderen summierst du falsch auf. Und wenn du als Einheit bit/Zeichen haben willst, musst du den Logarithmus Dualis nehmen oder durch log(2) teilen.

So gehts richtig:
X=(A, B, C, D, E)
=> n = (n(A), n(B), n(C), n(D), n(E)) = (1, 1, 1, 1, 1)
=> p = (p(A), p(B), p(C), p(D), p(E)) = n/5 = (1/5, 1/5, 1/5, 1/5, 1/5)
=> E = (1/5*log(5) + 1/5*log(5) + 1/5*log(5) + 1/5*log(5) + 1/5*log(5))/log(2) = log(5)/log(2) = 2,32 Bit/Zeichen

Y=(A, B, A, A, C)
=> n = (n(A), n(B), n(C), n(D), n(E)) = (3, 1, 1, 0, 0)
=> p = (p(A), p(B), p(C), p(D), p(E)) = n/5 = (3/5, 1/5, 1/5, 0, 0)
=> E = (3/5*log(5/3) + 1/5*log(5) + 1/5*log(5))/log(2) = (log(5) - 3/5*log(3))/log(2) = 1,37 Bit/Zeichen

/EDIT: Dein Ergebniss stimmt allerdings bis auf einen Skalierungsfaktor mit meinem Ergebnis überein. Dieser Skalierungsfaktor hängt bei dir von der Vektorlänge ab. Dein Ansatz ist also nicht grundsätzlich falsch, er muss nur erweitert werden, um auf eine einheitliche Größe unabhängig von der Vektorlänge zu kommen. Zum Vergleichen von Vektoren gleicher Länge taugt dein Maß wohl.