全文檢索、資料採擷、推薦引擎系列5---文章術語向量標記法

無論是要進行全文檢索，還是對文章進行自動聚類分析，都需要將文章表示為術語向量（Term Vector），在Lucene內部就是通過術語向量來對文章進行索引和搜索的，但是Lucene沒有向外提供合適的術語向量計算介面，所以對術語向量計算還必須我們自己來做。

術語向量解述

眾所周知，一篇文章由一個個的單詞組成，我們在進行文本處理時，首先進行中文分詞，包括去除“的、地、得”等常用停止詞，對關鍵字加上同義詞，如縮寫和全稱，如果是英文可能還需要變為小寫，去除複數和過去分詞等，可能還需要提取詞根，總之經過上述步聚的預處理，文章將變成由一系列單詞組成的字串陣列。

對一系統中的每一篇文章，我們首先計算每個單詞的出現頻率（TF：TermFrequency），即該單詞出現的次數除以文章總單詞數，然後統計這個單詞的反比文檔頻率（IDF：Inverse Document Frequency），在所有文章中出現的次數，並用該數除文章總數，即總文章數除以出現該單詞文章的數目。由上面的定義可以看出，單詞越重要，他的單詞出現頻率TF就越高，單詞越是只在這篇文章中出現，很少在其它文章中出現，那該單詞越對本篇文章具有重要意義。通過一定的公式，可以計算出每個單詞的對每篇文章的權重，這樣所有單詞加上其對應的權重，就形成了一個多維術語向量。

計算TF*IDF

對於術語向量的計算方法，目前還沒有特別成熟的演算法，現在常用的只是一些經驗演算法，一些文章中提出的號稱更加準確的演算法，還沒有經過實際驗證。我們在這裡採用的是當前最常用的演算法，根據實際需要對這些演算法進行修正也是相當簡單的。

首先系統需要維護幾個全域變數：總文章數、系統中所有單詞以及其在文章中出現的次數

 // 因為單詞出現在文章的不同位置重要性不同，可以設置不同的權重
 public final static int TITLE_WEIGHT = 1;
 public final static int KEYWORD_WEIGHT = 1;
 public final static int TAG_WEIGHT = 1;
 public final static int ABCT_WEIGHT = 1;
 public final static int BODY_WEIGHT = 1;

 private static int docsNum = 0; // 目前系統中的總文檔數，將來需要存在資料庫中
 private static Map<String, Integer> wordDocs = null; // 每個單詞在所有的每篇文章中出現的文章個數（文章數）
 private static Vector<Integer> termNumDoc = null; // 每篇文章的總單詞數
 private static Vector<Vector<TermInfo>> termVectors = null; // 每篇文章的術語向量表示

然後是對一段文本產生術語原始術語向量的程式，如下所示：
 /**
  * 一篇文章分為標題、關鍵字、摘要、標誌、正文幾個部分組成，每個部分的單詞具有不同的權重，通過
  * 本函數進行中文分詞，同時生成該部分的術語向量
  * @param text 需要處理的文本
  * @param termArray 術語向量
  * @param weight 單詞在本部分的權重
  * @return 本部分的單總數（用於計算單詞出現頻率TF）
  */
 private static int procDocPart(String text, Vector<TermInfo> termArray, int weight) {
  Collection<String> words = FteEngine.tokenize(text);
  Iterator<String> itr = words.iterator();
  String word = null;
  TermInfo termInfo = null;
  int termMount = 0;
  while (itr.hasNext()) {
   word = itr.next();
   if (termArray.contains(word)) {
    termInfo = termArray.get(termArray.indexOf(word));
    termInfo.setMountPerDoc(termInfo.getMountPerDoc() + weight);
   } else {
    termInfo = new TermInfo();
    termInfo.setMountPerDoc(weight);
    termInfo.setTermStr(word);
    termInfo.setRawWeight(0.0);
    termInfo.setWeight(0.0);
    termArray.add(termInfo);
   }
   termMount += weight;
  }
  return termMount;
 }

下面是求出TF*IDF然後進行歸一化生成最終術語向量的程式：

/**
  * 對標題、關鍵字、標記、摘要、正文採用迭加方式生成術語向量
  * @param docIdx 文檔編號，為-1時表示新加入的文檔
  * @param text 需要處理的文本
  * @param weight 本段文本單詞出現的權重
  * @return 文檔編號
  */
 public static int genTermVector(int docIdx, String text, int weight) {
  Vector<TermInfo> termVector = null;
  if (docIdx < 0) {
   docIdx = docsNum;
   termNumDoc.add(0);
   termVector = new Vector<TermInfo>();
   termVectors.add(termVector);
   docsNum++;
  }
  termVector = termVectors.elementAt(docIdx);
  int termMount = procDocPart(text, termVector, weight);
  termNumDoc.set(docIdx, termNumDoc.elementAt(docIdx).intValue() + termMount);
  // 計算所有術語的IDF
  TermInfo termInfo = null;
  String termStr = null;
  Iterator<TermInfo> termInfoItr = termVector.iterator();
  // 計算每個單詞在文章中出現的篇數
  while (termInfoItr.hasNext()) {
   termInfo = termInfoItr.next();
   termStr = termInfo.getTermStr();
   if (wordDocs.get(termStr) != null) {
    wordDocs.put(termStr, wordDocs.get(termStr).intValue() + 1);
   } else {
    wordDocs.put(termStr, 1);
   }
   termInfo.setTf(termInfo.getMountPerDoc() / ((double)termNumDoc.elementAt(docIdx).intValue()));
  }
  Iterator<Vector<TermInfo>> docItr = termVectors.iterator();
  // 計算TF*IDF
  double rwPSum = 0.0;
  while (docItr.hasNext()) {
   termVector = docItr.next();
   termInfoItr = termVector.iterator();
   rwPSum = 0.0;
   while (termInfoItr.hasNext()) {
    termInfo = termInfoItr.next();
    termInfo.setRawWeight(termInfo.getTf() * Math.log(((double)docsNum) / 
      wordDocs.get(termInfo.getTermStr()).intValue()));
    rwPSum += termInfo.getRawWeight() * termInfo.getRawWeight();
   }
   // 對TF*IDF進行歸一化
   termInfoItr = termVector.iterator();
   while (termInfoItr.hasNext()) {
    termInfo = termInfoItr.next();
    termInfo.setWeight(termInfo.getRawWeight() / Math.sqrt(rwPSum));
   }
  }
  return docIdx;
 }

文章相似度計算

文章的相似度就是要計處兩篇文章對應的術語向量的距離，也就是對應各個術語歸一化後的TF*IDF的權重差的平方合再開發，類似於二維向量距離的計算，具體實現代碼如下所示：

/**
  * 計算術語向量的距離，該值小則表明兩篇文章相似度高
  * @param termVector1
  * @param termVector2
  * @return 距離
  */
 public static double calTermVectorDist(Collection<TermInfo> termVector1, Collection<TermInfo> termVector2) {
  double dist = 0.0;
  Vector<TermInfo> tv1 = (Vector<TermInfo>)termVector1;
  Vector<TermInfo> tv2 = (Vector<TermInfo>)termVector2;
  Hashtable<String, TermInfo> tv2Tbl = new Hashtable<String, TermInfo>();
  Iterator<TermInfo> tvItr = null;
  TermInfo termInfo = null;
  TermInfo ti2 = null;
  double[] weights = new double [tv2.size()];
  int idx = 0;
  // 初始化數據
  tvItr = tv2.iterator();
  while (tvItr.hasNext()) {
   termInfo = tvItr.next();
   //weights[idx++] = termInfo.getWeight();
   tv2Tbl.put(termInfo.getTermStr(), termInfo);
  }
  // 
  tvItr = tv1.iterator();
  while (tvItr.hasNext()) {
   termInfo = tvItr.next();
   ti2 = tv2Tbl.get(termInfo.getTermStr());
   if (ti2 != null) {
    dist += (termInfo.getWeight() - ti2.getWeight()) * (termInfo.getWeight() - ti2.getWeight());
    ti2.setWeight(0.0);
   } else {
    dist += termInfo.getWeight() * termInfo.getWeight();
   }
  }
  tvItr = tv2Tbl.values().iterator();
  while (tvItr.hasNext()) {
   termInfo = tvItr.next();
   System.out.println("######: " + termInfo.getTermStr() + "=" + termInfo.getWeight() + "!");
   dist += termInfo.getWeight() * termInfo.getWeight();
  }
  System.out.println();
 
  return Math.sqrt(dist);
 }

下面對以下三句話進行計算：

Java語言程式設計技術詳解

C++語言程式設計指南

同性戀網站變身電子商務網站

計算的術語向量值為：

java:0.5527962688403749
語言:0.20402065516569604
程式設計:0.20402065516569604
技術:0.5527962688403749
詳解:0.5527962688403749
############## doc2 ############
c:0.6633689723434504           （注：我們的詞典中沒有C++）
語言:0.24482975009584626
程式設計:0.24482975009584626
指南:0.6633689723434504
############## doc3 ############
同性戀:0.531130184813292
網:0.196024348194679
站:0.196024348194679
變身:0.531130184813292
電子商務:0.531130184813292
網:0.196024348194679
站:0.196024348194679

然後計算距離為：

第一篇與第二篇：1.3417148340558687

第一篇與第三篇：1.3867764455130116

因此通過計算結果系統會認為第一篇和第二篇更接近，實際情況也是如此，因為第一篇和第二篇間有兩個單詞是相同的，而第一篇和第三篇間則沒有任何相同的地方。