互信息的实现

Question

我在Lucene索引中有一个文本文档集合。索引中有超过4.000.000个文档。该程序基于用户查询运行搜索，并返回与该查询相关的N个文档。然后，我们的想法是对N个文档中的术语执行互信息计算，并找到与整个集合强烈相关的术语。

代码如下：

public class CoOccurrence {
    private Map<String, Double> cooccurrenceMatrix = new HashMap<String, Double>();
    private int n;
    private List<String> terms = new ArrayList<String>();

    public CoOccurrence(List<String> abstracts){
        n = abstracts.size();

        for(int i = 0; i < abstracts.size(); i++){
            String[] line = abstracts.get(i).split(" ");
            for(String word: line){
                if(!Utils.containsDigits(word)){
                    if(!terms.contains(word)){
                        terms.add(word);
                    }
                }
            }
        }
        getMutualInformation(abstracts);
    }

    private void getMutualInformation(List<String> abstracts){
        double n = this.n;
        double sum;

        for(int f1 = 0; f1 < terms.size()-1; f1++){
            sum = 0;
            for(int f2 = f1 + 1; f2 < terms.size(); f2++){
                Bigram bigram = new Bigram(terms.get(f1), terms.get(f2));

                //Fetch number of documents that contains both term.f1 and term.f2
                double p_xy = docsContainingXandY(bigram, abstracts) / n;

                //Fetch number of documents containing term.f1
                double p_x = docsContainingX(bigram, abstracts) / n;

                //Fetch number of documents containing term.f2
                double p_y = docsContainingY(bigram, abstracts) / n;

                sum += (p_xy) * Utils.logWithoutNaN( p_xy / (p_x * p_y) );
            }
            cooccurrenceMatrix.put(terms.get(f1), sum);
        }
    }
}

有没有人看到我在以某种错误的方式执行计算，或者有任何其他的错误或误解阻碍了预期的结果？

编辑: Bigram类是一个简单的包装器，包含两个String : String x，String y。

Util类包含许多不同的任务，但是logWithoutNaN看起来像这样：

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

其中，EPSILON = 0.000001

至于输出:搜索“计算机”会给出20个应该相关的术语，但(大多数)不是：“处理称为东南亚区域联盟边缘海洋协会非营利性输入国家一般意义上的专业提供协会科学给出”

Answer 1

有几件事会立即浮现在脑海中。但是，这很难说话，因为我不知道你的数据(有多少文档，有多大，等等)

但是在bat的右边，terms应该是一个集合，而不是一个列表，那么"contains“(不断扫描列表)应该更有效。

接下来，虽然分离是一个值得称赞的目标，但我会将docContaining...例程组合到单个例程中。你遍历文档列表，我假设它们的全部内容，3次。您(可能)只需扫描它们一次，然后同时导出所有3个值(p_xy、p_x、p_y)。

所以，简单地说，我只是看到了许多重复的扫描，也许一些更好的算法和数据结构的选择可能会产生很大的影响。

附录:令人惊讶的是阵雨能带来什么。

这里的基本问题是位于中心的主double for循环，您将在该循环中遍历单词对。这就是要你命的原因。它是n^2。字数越多，性能就越差。

因此，真正的目标是尽早消除单词。

首先，您应该对单词运行词干分析器。词干消除了像复数和缩写之类的东西。您还应该删除常见的停用词("the“、"a”、"then“等)。这两个过程都将减少字数。你可以搜索词干算法，Lucene当然已经有了这些算法。

接下来，我将为每个文档创建唯一的单词列表。从这些列表中，我将开始删除文档中独有的单词。显然，如果一个单词只存在于单个文档中，那么整个文档集中就没有任何相关性。

最后，我会开始扔掉那些很少用过的分享词汇。如果您对每个相关性都感兴趣，那么您不想这样做。但大多数人对“前几名”感兴趣。因此，应该直接删除那些明显不会上升到列表顶部的单词。例如，在两个文档中只使用一次的单词。您可以尝试一些启发式方法，例如平均所有文档中的单词出现次数，并将这些单词降低到特定阈值以下。

所有这些的目标都是减少整体单词列表，因为每个新单词都会对整体性能产生如此巨大的影响。