Инкрементальное вычисление энтропии

Question

Инкрементальное вычисление энтропии

Позволять std::vector<int> counts быть вектором натуральных чисел и пусть N:=counts[0]+...+counts[counts.length()-1] быть суммой компонент вектора. настройка pi:=counts[i]/NЯ вычисляю энтропию по классической формуле H=p0*log2(p0)+...+pn*log2(pn),

counts вектор меняется — счетчики увеличиваются — и каждые 200 изменений я пересчитываю энтропию. После быстрого поиска в google и stackoverflow я не смог найти никакого метода для вычисления возрастающей энтропии. Итак, вопрос: есть ли инкрементный метод, как те, для дисперсии, для вычисления энтропии?

РЕДАКТИРОВАТЬ: Мотивация для этого вопроса было использование таких формул для оценки прироста прироста информации в VFDT-как ученики.

Постановили: Увидеть этот mathoverflow сообщение.

2

algorithm c++decision-tree entropy

Решение

Другие решения

Вы можете пересчитать энтропию, пересчитав число и используя простую математическую идентификацию, чтобы упростить формулу энтропии.

K = count.size();
N = count[0] + ... + count[K - 1];
H = count[0]/N * log2(count[0]/N) + ... + count[K - 1]/N * log2(count[K - 1]/N)
= F * h
h = (count[0] * log2(count[0]) + ... + count[K - 1] * log2(count[K - 1]))
F = -1/(N * log2(N))

который держит из-за log2(a / b) == log2(a) - log2(b)

Сейчас дан старый вектор count наблюдений до сих пор и еще один вектор новых 200 наблюдений называется batchВы можете сделать в C ++ 11

void update_H(double& H, std::vector<int>& count, int& N, std::vector<int> const& batch)
{
N += batch.size();
auto F = -1/(N * log2(N));
for (auto b: batch)
++count[b];
H = F * std::accumulate(count.begin(), count.end(), 0.0, [](int elem) {
return elem * log2(elem);
});
}

Здесь я предполагаю, что вы закодировали свои наблюдения как int, Если у вас есть какой-то символ, вам понадобится таблица символов std::map<Symbol, int>и выполните поиск для каждого символа в batch прежде чем обновлять count,

Это кажется самым быстрым способом написания кода для общего обновления. Если вы знаете, что в каждом пакете фактически изменяется только небольшое количество, вы можете делать то же, что и @migdal, и отслеживать изменения количества, вычитать их старый вклад в энтропию и добавлять новый вклад.

0

Источник

Accepted Answer

Я вывел формулы обновления и алгоритмы для энтропии и индекса Джини и сделал заметку доступно на arXiv. (Рабочая версия заметки доступна Вот.) Также см этот mathoverflow ответ.

Для удобства я включаю простой код Python, демонстрируя производные формулы:

from math import log
from random import randint

# maps x to -x*log2(x) for x>0, and to 0 otherwise
h = lambda p: -p*log(p, 2) if p > 0 else 0

# update entropy if new example x comes in
def update(H, S, x):
new_S = S+x
return 1.0*H*S/new_S+h(1.0*x/new_S)+h(1.0*S/new_S)

# entropy of union of two samples with entropies H1 and H2
def update(H1, S1, H2, S2):
S = S1+S2
return 1.0*H1*S1/S+h(1.0*S1/S)+1.0*H2*S2/S+h(1.0*S2/S)

# compute entropy(L) using only `update' function
def test(L):
S = 0.0 # sum of the sample elements
H = 0.0 # sample entropy
for x in L:
H = update(H, S, x)
S = S+x
return H

# compute entropy using the classic equation
def entropy(L):
n = 1.0*sum(L)
return sum([h(x/n) for x in L])

# entry point
if __name__ == "__main__":
L = [randint(1,100) for k in range(100)]
M = [randint(100,1000) for k in range(100)]

L_ent = entropy(L)
L_sum = sum(L)

M_ent = entropy(M)
M_sum = sum(M)

T = L+M

print "Full = ", entropy(T)
print "Update = ", update(L_ent, L_sum, M_ent, M_sum)

2