webentwicklung-frage-antwort-db.com.de

Der schnellste Weg, um Entropie in Python zu berechnen

In meinem Projekt muss ich die Entropie von 0-1 Vektoren viele Male berechnen. Hier ist mein Code:

def entropy(labels):
    """ Computes entropy of 0-1 vector. """
    n_labels = len(labels)

    if n_labels <= 1:
        return 0

    counts = np.bincount(labels)
    probs = counts[np.nonzero(counts)] / n_labels
    n_classes = len(probs)

    if n_classes <= 1:
        return 0
    return - np.sum(probs * np.log(probs)) / np.log(n_classes)

Gibt es einen schnelleren Weg?

pythonnumpyentropy
31
blueSurfer

@Sanjeet Guptas Antwort ist gut, könnte aber verdichtet werden. Diese Frage fragt speziell nach dem "schnellsten" Weg, aber ich sehe nur eine Antwort auf eine Antwort. Daher werde ich einen Vergleich zwischen Scipy und Numpy mit der Entropy2-Antwort des ursprünglichen Posters mit geringfügigen Änderungen posten.

Vier verschiedene Ansätze: scipy/numpy , numpy/math , pandas/numpy , numpy 

import numpy as np
from scipy.stats import entropy
from math import log, e
import pandas as pd

import timeit

def entropy1(labels, base=None):
  value,counts = np.unique(labels, return_counts=True)
  return entropy(counts, base=base)

def entropy2(labels, base=None):
  """ Computes entropy of label distribution. """

  n_labels = len(labels)

  if n_labels <= 1:
    return 0

  value,counts = np.unique(labels, return_counts=True)
  probs = counts / n_labels
  n_classes = np.count_nonzero(probs)

  if n_classes <= 1:
    return 0

  ent = 0.

  # Compute entropy
  base = e if base is None else base
  for i in probs:
    ent -= i * log(i, base)

  return ent

def entropy3(labels, base=None):
  vc = pd.Series(labels).value_counts(normalize=True, sort=False)
  base = e if base is None else base
  return -(vc * np.log(vc)/np.log(base)).sum()

def entropy4(labels, base=None):
  value,counts = np.unique(labels, return_counts=True)
  norm_counts = counts / counts.sum()
  base = e if base is None else base
  return -(norm_counts * np.log(norm_counts)/np.log(base)).sum()

Timeit-Operationen:

repeat_number = 1000000

a = timeit.repeat(stmt='''entropy1(labels)''',
                  setup='''labels=[1,3,5,2,3,5,3,2,1,3,4,5];from __main__ import entropy1''',
                  repeat=3, number=repeat_number)

b = timeit.repeat(stmt='''entropy2(labels)''',
                  setup='''labels=[1,3,5,2,3,5,3,2,1,3,4,5];from __main__ import entropy2''',
                  repeat=3, number=repeat_number)

c = timeit.repeat(stmt='''entropy3(labels)''',
                  setup='''labels=[1,3,5,2,3,5,3,2,1,3,4,5];from __main__ import entropy3''',
                  repeat=3, number=repeat_number)

d = timeit.repeat(stmt='''entropy4(labels)''',
                  setup='''labels=[1,3,5,2,3,5,3,2,1,3,4,5];from __main__ import entropy4''',
                  repeat=3, number=repeat_number)

Timeit Ergebnisse:

# for loop to print out results of timeit
for approach,timeit_results in Zip(['scipy/numpy', 'numpy/math', 'pandas/numpy', 'numpy'], [a,b,c,d]):
  print('Method: {}, Avg.: {:.6f}'.format(approach, np.array(timeit_results).mean()))

Method: scipy/numpy, Avg.: 63.315312
Method: numpy/math, Avg.: 49.256894
Method: pandas/numpy, Avg.: 884.644023
Method: numpy, Avg.: 60.026938

Gewinner: numpy/math (entropy2)

Es ist auch erwähnenswert, dass die entropy2-Funktion oben numerische UND-Textdaten verarbeiten kann. zB: entropy2(list('abcdefabacdebcab')). Die Antwort des ursprünglichen Posters stammt aus dem Jahr 2013 und hatte einen speziellen Anwendungsfall für Binning-Ints, aber es funktioniert nicht für Text.

21
Jarad
import pandas as pd
import scipy as sc

# Input a pandas series 
def ent(data):
    p_data= data.value_counts()/len(data) # calculates the probabilities
    entropy=sc.stats.entropy(p_data)  # input probabilities to get the entropy 
    return entropy
18
Sanjeet Gupta

Dem Vorschlag von unutbu folgend, erstelle ich eine reine Python-Implementierung.

def entropy2(labels):
 """ Computes entropy of label distribution. """
    n_labels = len(labels)

    if n_labels <= 1:
        return 0

    counts = np.bincount(labels)
    probs = counts / n_labels
    n_classes = np.count_nonzero(probs)

    if n_classes <= 1:
        return 0

    ent = 0.

    # Compute standard entropy.
    for i in probs:
        ent -= i * log(i, base=n_classes)

    return ent

Der Punkt, den ich vermisst habe, war, dass Labels ein großes Array sind, aber Probs sind 3 oder 4 Elemente lang. Mit reinem Python ist meine Anwendung jetzt doppelt so schnell. 

11
blueSurfer

Eine Antwort, die auch nicht auf numpy angewiesen ist:

import math
from collections import Counter

def eta(data, unit='natural'):
    base = {
        'shannon' : 2.,
        'natural' : math.exp(1),
        'hartley' : 10.
    }

    if len(data) <= 1:
        return 0

    counts = Counter()

    for d in data:
        counts[d] += 1

    ent = 0

    probs = [float(c) / len(data) for c in counts.values()]
    for p in probs:
        if p > 0.:
            ent -= p * math.log(p, base[unit])

    return ent

Dies akzeptiert jeden Datentyp, den Sie darauf werfen könnten:

>>> eta(['mary', 'had', 'a', 'little', 'lamb'])
1.6094379124341005

>>> eta([c for c in "mary had a little lamb"])
2.311097886212714

Die Antwort von @Jarad schlug auch Timings vor. Zu diesem Zweck:

repeat_number = 1000000
e = timeit.repeat(
    stmt='''eta(labels)''', 
    setup='''labels=[1,3,5,2,3,5,3,2,1,3,4,5];from __main__ import eta''', 
    repeat=3, 
    number=repeat_number)

Timeit-Ergebnisse: (Ich glaube, das ist ~ 4x schneller als der beste numpy Ansatz)

print('Method: {}, Avg.: {:.6f}'.format("eta", np.array(e).mean()))

Method: eta, Avg.: 10.461799
8
joemadeus

Meine Lieblingsfunktion für Entropie ist folgende:

def entropy(labels):
    prob_dict = {x:labels.count(x)/len(labels) for x in labels}
    probs = np.array(list(prob_dict.values()))

    return - probs.dot(np.log2(probs))

Ich bin immer noch auf der Suche nach einer besseren Möglichkeit, die Konvertierung von Diktieren -> Werten -> Liste -> np.array zu vermeiden. Werde es noch einmal kommentieren, wenn ich es gefunden habe.

7
Ottotos

Hier ist mein Ansatz:

labels = [0, 0, 1, 1]

from collections import Counter
from scipy import stats

stats.entropy(list(Counter(labels).values()), base=2)
3
Tan Duong

Gleichmäßig verteilte Daten (hohe Entropie):

s=range(0,256)

Shannon Entropie-Berechnung Schritt für Schritt:

import collections

# calculate probability for each byte as number of occurrences / array length
probabilities = [n_x/len(s) for x,n_x in collections.Counter(s).items()]
# [0.00390625, 0.00390625, 0.00390625, ...]

# calculate per-character entropy fractions
e_x = [-p_x*math.log(p_x,2) for p_x in probabilities]
# [0.03125, 0.03125, 0.03125, ...]

# sum fractions to obtain Shannon entropy
entropy = sum(e_x)
>>> entropy 
8.0

Einzeiler (vorausgesetzt import collections):

def H(s): return sum([-p_x*math.log(p_x,2) for p_x in [n_x/len(s) for x,n_x in collections.Counter(s).items()]])

Eine richtige Funktion:

import collections

def H(s):
    probabilities = [n_x/len(s) for x,n_x in collections.Counter(s).items()]
    e_x = [-p_x*math.log(p_x,2) for p_x in probabilities]    
    return sum(e_x)

Testfälle - Englischer Text aus CyberChef Entropy Estimator :

>>> H(range(0,256))
8.0
>>> H(range(0,64))
6.0
>>> H(range(0,128))
7.0
>>> H([0,1])
1.0
>>> H('Standard English text usually falls somewhere between 3.5 and 5')
4.228788210509104
3
kravietz

schauen Sie sich auch hier um, es gibt eine klassische Shannon-Entropie, die etwas schneller sein sollte als die von JohnEntropy http://pythonfiddle.com/shannon-entropy-calculation/

3
chupvl
from collections import Counter
from scipy import stats

labels = [0.9, 0.09, 0.1]
stats.entropy(list(Counter(labels).keys()), base=2)
1
Krishna Chaitanya Gopaluni

Die obige Antwort ist gut, aber wenn Sie eine Version benötigen, die auf verschiedenen Achsen arbeiten kann, finden Sie hier eine funktionierende Implementierung.

def entropy(A, axis=None):
    """Computes the Shannon entropy of the elements of A. Assumes A is 
    an array-like of nonnegative ints whose max value is approximately 
    the number of unique values present.

    >>> a = [0, 1]
    >>> entropy(a)
    1.0
    >>> A = np.c_[a, a]
    >>> entropy(A)
    1.0
    >>> A                   # doctest: +NORMALIZE_WHITESPACE
    array([[0, 0], [1, 1]])
    >>> entropy(A, axis=0)  # doctest: +NORMALIZE_WHITESPACE
    array([ 1., 1.])
    >>> entropy(A, axis=1)  # doctest: +NORMALIZE_WHITESPACE
    array([[ 0.], [ 0.]])
    >>> entropy([0, 0, 0])
    0.0
    >>> entropy([])
    0.0
    >>> entropy([5])
    0.0
    """
    if A is None or len(A) < 2:
        return 0.

    A = np.asarray(A)

    if axis is None:
        A = A.flatten()
        counts = np.bincount(A) # needs small, non-negative ints
        counts = counts[counts > 0]
        if len(counts) == 1:
            return 0. # avoid returning -0.0 to prevent weird doctests
        probs = counts / float(A.size)
        return -np.sum(probs * np.log2(probs))
    Elif axis == 0:
        entropies = map(lambda col: entropy(col), A.T)
        return np.array(entropies)
    Elif axis == 1:
        entropies = map(lambda row: entropy(row), A)
        return np.array(entropies).reshape((-1, 1))
    else:
        raise ValueError("unsupported axis: {}".format(axis))
0
d.b