solr - オンライン エントロピー評価アルゴリズム

Question

平均と偏差のSumamryStatisticsに似た離散値のストリームでエントロピーを評価する方法はありますか? リアルタイムの solr コンポーネントにこのアルゴリズムが必要です。おそらく、大規模なドキュメント コレクション (100,000) を反復処理します。

関連する質問、Map Reduce のような環境でエントロピーを計算する最良の方法は何ですか。

Answer 1

方法があるかもしれません - それは、ストリームの特性と、結果に対して何をしたいかによって多少異なります。

サンプル エントロピーは、サンプル確率分布の関数です。各値の現在のカウントを現在の合計カウントと一緒に保存できます。これは、分布をオンデマンドで計算できることを意味します。ずさんな Java ですみません。書いてから約 1 年が経ちました。

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メソッドがストリーム値を保存しないという事実からわかるように、ストリーム内の値の数とは無関係です。