2012年5月17日 星期四

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


無論是要進行全文檢索,還是對文章進行自動聚類分析,都需要將文章表示為術語向量(Term Vector),在Lucene內部就是通過術語向量來對文章進行索引和搜索的,但是Lucene沒有向外提供合適的術語向量計算介面,所以對術語向量計算還必須我們自己來做。
術語向量解述
眾所周知,一篇文章由一個個的單詞組成,我們在進行文本處理時,首先進行中文分詞,包括去除的、地、得等常用停止詞,對關鍵字加上同義詞,如縮寫和全稱,如果是英文可能還需要變為小寫,去除複數和過去分詞等,可能還需要提取詞根,總之經過上述步聚的預處理,文章將變成由一系列單詞組成的字串陣列。
對一系統中的每一篇文章,我們首先計算每個單詞的出現頻率(TFTermFrequency),即該單詞出現的次數除以文章總單詞數,然後統計這個單詞的反比文檔頻率(IDFInverse 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
因此通過計算結果系統會認為第一篇和第二篇更接近,實際情況也是如此,因為第一篇和第二篇間有兩個單詞是相同的,而第一篇和第三篇間則沒有任何相同的地方。


沒有留言: