Najszybszy sposób obliczania entropii w Pythonie

Question

W moim projekcie muszę wielokrotnie obliczać entropię wektorów 0-1. Oto mój kod:

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) 

Czy jest szybszy sposób?

Answer 1

Idąc za sugestią z unutbu, tworzę czystą implementację pythona.

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 

Punktem, którego brakowało było to, że etykiety to duża tablica, jednak probs ma długość 3 lub 4 elementów. Używając czystego Pythona, moja aplikacja jest teraz dwa razy szybsza.

Answer 2

spojrzeć tutaj również znajduje się klasyczny Shannon Entropia, powinien być trochę szybciej niż jednego przez JohnEntropy http://pythonfiddle.com/shannon-entropy-calculation/

Answer 3

Powyższa odpowiedź jest dobra, ale jeśli potrzebujesz wersję, która może działać wzdłuż różnych osi , oto działająca implementacja.

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)) 

Answer 4

odpowiedź, która nie opiera się na numpy, albo:

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 

    probs = [float(c)/len(data) for c in counts.values()] 
    probs = [p for p in probs if p > 0.] 

    ent = 0 

    for p in probs: 
     if p > 0.: 
      ent -= p * math.log(p, base[unit]) 

    return ent 

to zaakceptuje żadnego typu danych można rzucić na niego:

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

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

Answer 5

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 

Answer 6

Moja ulubiona funkcja entropia jest następująca:

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)) 

Wciąż szukam lepszego sposobu na uniknięcie dict -> values ​​-> list -> np.array conversion. Powiem ponownie, jeśli ją znajdę.

Answer 7

@Sanjeet Gupta odpowiedź jest dobra, ale może być skondensowana. To pytanie jest szczególnie pytające o "Najszybszy" sposób, ale widzę tylko czasy na jedną odpowiedź, więc opublikuję porównanie użycia scipy i numpy do oryginalnej odpowiedzi entropii2 plakatu z niewielkimi zmianami.

Cztery różne podejścia: scipy/numpy, NumPy/math, pandy/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() 

operacje timeit:

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) 

wyniki timeit:

# 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 

Zwycięzca: numpy/math (entropy2)

Warto również zauważyć, że funkcja entropy2 powyżej może obsługiwać dane liczbowe i tekstowe. np. entropy2(list('abcdefabacdebcab')). Oryginalna odpowiedź na plakat pochodzi z 2013 roku i miała konkretny przypadek użycia dla binningów, ale nie będzie działać dla tekstu.

Answer 8

równomiernie rozłożone dane (wysoka entropia)

s=range(0,256) 

Shannon entropia etap obliczenia w etapie:

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 

jedną wykładzinę (zakładając 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()]]) 

Odpowiedni funkcja:

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) 

przypadki testowe - English tekstu zaczerpnięte z 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