java - Java高效实现互信息

Question

我希望使用 Java 计算两个特征之间的互信息。

我读过 Calculating Mutual Information For Selecting a Training Set in Java已经，但那是关于相互信息是否适合张贴者的讨论，只有一些关于实现的简单伪代码。

我当前的代码如下，但我希望有一种方法可以优化它，因为我有大量的信息要处理。我知道调用另一种语言/框架可能会提高速度，但现在我想专注于用 Java 解决这个问题。

非常感谢任何帮助。

public static double calculateNewMutualInformation(double frequencyOfBoth, double frequencyOfLeft,
                                                   double frequencyOfRight, int noOfTransactions) {
    if (frequencyOfBoth == 0 || frequencyOfLeft == 0 || frequencyOfRight == 0)
        return 0;
    // supp = f11
    double supp = frequencyOfBoth / noOfTransactions; // P(x,y)
    double suppLeft = frequencyOfLeft / noOfTransactions; // P(x)
    double suppRight = frequencyOfRight / noOfTransactions; // P(y)
    double f10 = (suppLeft - supp); // P(x) - P(x,y)
    double f00 = (1 - suppRight) - f10; // (1-P(y)) - P(x,y)
    double f01 = (suppRight - supp); // P(y) - P(x,y)

    // -1 * ((P(x) * log(Px)) + ((1 - P(x)) * log(1-p(x)))
    double HX = -1 * ((suppLeft * MathUtils.logWithoutNaN(suppLeft)) + ((1 - suppLeft) * MathUtils.logWithoutNaN(1 - suppLeft)));
    // -1 * ((P(y) * log(Py)) + ((1 - P(y)) * log(1-p(y)))
    double HY = -1 * ((suppRight * MathUtils.logWithoutNaN(suppRight)) + ((1 - suppRight) * MathUtils.logWithoutNaN(1 - suppRight)));

    double one = (supp * MathUtils.logWithoutNaN(supp)); // P(x,y) * log(P(x,y))
    double two = (f10 * MathUtils.logWithoutNaN(f10)); 
    double three = (f01 * MathUtils.logWithoutNaN(f01));
    double four = (f00 * MathUtils.logWithoutNaN(f00));
    double HXY = -1 * (one + two + three + four);
    return (HX + HY - HXY) / (HX == 0 ? MathUtils.EPSILON : HX);
}        

public class MathUtils {
public static final double EPSILON = 0.000001;

public static double logWithoutNaN(double value) {
    if (value == 0) {
        return Math.log(EPSILON);
    } else if (value < 0) {
        return 0;
    }
    return Math.log(value);
}  

Answer 1

我发现以下方法速度很快，但我没有将其与您的方法进行比较 - 仅在 weka 中提供.

它的工作前提是重新排列 MI 方程，以便可以最大限度地减少浮点运算次数:

我们首先定义 作为样本/交易数量的计数/频率。所以，我们定义item的个数为n，x出现的次数为|x|，y出现的次数为|y|以及它们作为 |x,y| 同时出现的次数。然后我们得到，

.

现在，我们可以通过翻转内分界线的底部来重新排列，得到 (n|x,y|)/(|x||y|)。此外，计算使用 N = 1/n，这样我们就少了一个除法运算。这给了我们:

这为我们提供了以下代码:

/***
 * Computes MI between variables t and a. Assumes that a.length == t.length.
 * @param a candidate variable a
 * @param avals number of values a can take (max(a) == avals)
 * @param t target variable
 * @param tvals number of values a can take (max(t) == tvals)
 * @return 
 */
static double computeMI(int[] a, int avals, int[] t, int tvals) {
    double numinst = a.length;
    double oneovernuminst = 1/numinst;
    double sum = 0;

    // longs are required here because of big multiples in calculation
    long[][] crosscounts = new long[avals][tvals];
    long[] tcounts = new long[tvals];
    long[] acounts = new long[avals];
    // Compute counts for the two variables
    for (int i=0;i<a.length;i++) {
        int av = a[i];
        int tv = t[i];
        acounts[av]++;
        tcounts[tv]++;
        crosscounts[av][tv]++;
    }

    for (int tv=0;tv<tvals;tv++) {
        for (int av=0;av<avals;av++) {
            if (crosscounts[av][tv] != 0) {
                // Main fraction: (n|x,y|)/(|x||y|)
                double sumtmp = (numinst*crosscounts[av][tv])/(acounts[av]*tcounts[tv]);
                // Log bit (|x,y|/n) and update product
                sum += oneovernuminst*crosscounts[av][tv]*Math.log(sumtmp)*log2;
            }
        }

    }

    return sum;
}

此代码假定 a 和 t 的值不是稀疏的(即 min(t)=0 和 tvals=max(t))，以使其高效。否则(如评论的那样)会创建大型且不必要的数组。

我相信这种方法在一次计算多个变量之间的 MI 时会进一步改进(可以压缩计数操作 - 特别是目标的计数操作)。我使用的实现是与 WEKA 接口(interface)的实现。

最后，甚至从求和中去掉对数可能会更有效。但我不确定 log 或 power 是否会在循环中进行更多计算。这是通过以下方式完成的:

1. 应用 a*log(b) = log(a^b)
2. 使用 log(a)+log(b) = log(ab) 将日志移到求和之外

并给出: