相互信息的實現

我有一個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類是一個簡單的包裝，包含兩個字符串：字符串x，字符串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項（大多數情況下）：「處理稱爲東南亞地區聯邦邊緣searcc協會非營利性輸入國家一般意義專業提供協會科學給予」

來源

2014-02-06 Geir K.H.

需要了解更多，特別是因爲我們沒有'BigGram'和'Utils'類。什麼是錯誤或錯誤的輸出？請提供更多信息，例如堆棧跟蹤。 – aliteralmind

@aliteralmind我已添加所需的信息。 –

一對夫婦o事情馬上就會浮現在腦海中。但是，很難說話，因爲我不知道你的數據（有多少文檔，有多大，等等）

但是，蝙蝠的權利，terms應該是一個集，而不是一個列表，然後「包含「（它不斷地掃描該列表）應該更有效率。

接下來，雖然分離是一個值得讚賞的目標，但我會將docContaining...例程合併到一個例程中。您遍歷文檔列表，並假設其全部內容3次。您（可能）可能會同時掃描一次，並同時得出所有3個值（p_xy,p_x，p_y）。

所以，我只是看到很多重複掃描，其中一些更好的算法和數據結構選擇可能會產生很大的影響。

附錄：驚人的淋浴可以帶來什麼。

這裏的根本問題是在您正在迭代單詞對的中心的主要雙重for循環。這是什麼殺了你。這是n^2。更多的話，更差的表現。

所以真正的目標是儘早消除單詞。

首先，你應該在單詞上運行詞幹。干擾消除諸如複數和收縮之類的東西，而不是。您還應該排除常見停用詞（「the」，「a」，「then」等）。這兩個過程都會減少字數。你可以搜索周圍的干擾算法，Lucene肯定有這些。

接下來，我會爲每個文檔創建獨特的單詞列表。從這些清單中，我將開始刪除文件特有的文字。很明顯，如果一個詞只存在於單個文檔中，那麼在整個文檔集中沒有任何關聯。

最後，我會開始丟棄一些共享的舊詞。如果你對每一次關聯感興趣，那麼你不想這樣做。但大多數人都對「前幾名」感興趣。因此，清楚地排除那些顯然不會超出列表頂部的詞語應該很簡單。例如，在2個文檔中僅使用一次的詞。您可以嘗試一些啓發式方法，比如平均所有文檔中的單詞出現次數，並將這些單詞放在特定閾值以下。

所有這些的目標是減少整個單詞列表，因爲每個新單詞都會對整體性能產生如此巨大的影響。

來源

2014-02-06 16:07:52

是的，你是正確的，因爲它不是你可能稱之爲時間有效的現在。然而，這些事情都沒有改變該計劃的結果，這正是我現在所堅持的。我將用更多信息編輯我的輸入。 –

您提出了一些優秀的想法，以獲得更好的表現，但首先：雖然干擾可能會減少總字數，但對於搜索精度來說這是破壞性的，這正是我在這裏所瞄準的。（Stemming有利於召回，對精度不利）。其次：這根本不能真正回答我的問題。我的問題不是性能。是的，這是一個緩慢的非最佳方案，但我現在對於表演並沒有感到困擾。首先我需要這個來給出預期的輸出。 –

相互信息的實現

回答

相關問題