Java中互信息的高效实现

我在计算使用Java的两个特性之间的互信息。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); 
}

来源

2011-09-29 Ina

你有没有衡量性能，决定了它是慢？ –

不错的问题，但是你可以将每个符号映射到互信息环境中的变量吗？因为我有点困惑。 – lonesome

我发现下面的要快，但我没有比这对你的方法 - 仅在weka提供。

它的工作原理上的前提下，重新安排MI公式，这样就可以最大限度地减少浮点运算的次数：通过定义 $p(\cdot)$ 为计数/频率超过数

$mutual information equation$

我们开始的样本/交易。因此，我们定义项目的数量为n，x出现的次数为| x |，y出现的次数为| y |以及它们共同出现的次数为| x，y |。然后我们得到，

$MI(X;Y) = \sum \limits_{y \in Y} \sum \limits_{x \in X} \frac{|x,y|}{n} \log \frac{\frac{|x,y|}{n}}{\frac{|x|}{n}\frac{|y|}{n}}$ 。现在

，我们可以重新安排，通过翻转内鸿沟的底部，这给了我们（N | X，Y |）/（| X || Y |）。另外，计算使用N = 1/n，所以我们有一个较少的分割操作。这给我们：

$MI(X;Y) = \sum \limits_{y \in Y} \sum \limits_{x \in X} N|x,y| log \bigg(\frac{n|x,y|}{|x||y|} \bigg)$

这使我们有以下代码：

/*** 
* 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的值不稀疏（即分钟（T）= 0和tvals = max（t）），因为它是有效的。否则（如评论）创建大型和不必要的数组。

我相信当多个变量同时计算MI（计数操作可以被压缩 - 尤其是目标的压缩操作）时，这种方法会进一步改进。我使用的是与WEKA接口的实现。

最后，即使是将日志从总和中取出也可能更有效。但我不确定日志或者权力是否会在循环中进行更多的计算。这是通过：

套用*日志（B）=日志（一个^ B）
日志移动到求和外，使用对数（一）+日志（B）=日志（AB ）

，并给出：

$MI(X;Y) = \log \bigg[ \prod \limits_{y \in Y} \prod \limits_{x \in X} \bigg(\frac{n|x,y|}{|x||y|}\bigg)^{\frac{|x,y|}{n}} \bigg]$

来源

2014-07-25 12:16:24 blitzen

考虑到OP是要求高效实现你所提供的代码有一个小的和一个潜在的巨大的低效率。 – neilireson

......我是说...... 首先，你可以移动不变“的log 2”跳出循环。其次还有一种可能性，即crosscounts矩阵将是非常稀疏，所以你进行毫无意义的重复的大量的，crosscounts仅需要则为a.length * t.length，例如，如果A和T都是{10，100 ，1000}，那么你有一个百万个单元矩阵，只有9个非零值。 – neilireson

我认为答案提到将日志移出循环（尽管不在代码段中）。我同意关于稀疏性的问题，但我会假设价值观没有差距。如果没有，或者如果有其他原因数据可能会导致稀疏，稀疏矩阵库将有所帮助。 – blitzen

我不是数学家，但..

只是有一堆浮点运算这里的。一些mathemagician可能会减少这种计算，请尝试Math SE。

同时，你应该能够使用static final double为Math.log(EPSILON)

您的问题可能不是一个单一的呼叫，但数据量的此计算有许多工作要做。抛出更多硬件可以更好地解决这个问题。

来源

2011-09-29 18:20:35

看起来像有没有神奇的解决方案，但是，这是一个良好的开端，感谢 – Ina

@Ina两年半接受我的答案后，您返回到它拿走:(高兴你发现虽然正确的解决方案。 –

你还有我给予好评和我谢谢！ – Ina

Java中互信息的高效实现

回答

相关问题