有没有办法评估类似于 SumamryStatistics 的离散值流上的熵的平均值和偏差?我需要这种算法用于实时 solr 组件,它可能会迭代大型文档集合(100,000)。
相关问题,在Map Reduce类似环境中计算熵的最佳方法是什么。
可能有一种方法 - 这在某种程度上取决于流的特征,以及你想对结果做什么。
样本熵是样本概率分布的函数。您可以将每个值的运行计数与运行总计数一起存储,这意味着可以按需计算分布。请原谅我草率的Java,我写它已经有一年了。
Map<K,Integer> runningCount = new Map<K,Integer>();
int totalCount = 0;
public void addValue(K k) {
runningCount.insert(k, runningCount.get(k) + 1);
totalCount += 1;
}
public Map<K,Double> getDistribution() {
Map<K,Double> dist = new Map<K,Double>();
for (K k : runningCount.keys()) {
dist.insert(k, runningCount.get(k) / totalCount);
}
return dist;
}
这意味着您还可以按需计算熵:
public double getEntropy() {
Map<K,Double> dist = getDistribution();
double entropy = 0;
for (K k : dist.keys()) {
double p = dist.get(k);
entropy -= p * Math.log(p);
}
return entropy;
}
此算法为 O(n),用于计算分布和熵,其中 n 是流可能采用的值数。它与流中的值数无关,从 addValue
方法不存储流值的事实可以看出。