全文檢索、資料採擷、推薦引擎系列7---條目相似度演算法

在實際的專案中，有許多場合需要進行條目相似度計算，比如在電商系統中，經常有喜歡這個商品的用戶還喜歡，通常計算商品的相似度是實現這種功能的方法之一，這可以視為一種基於內容的推薦系統的應用。同時，計算相似度不僅可以用於推薦商品，利用同樣的演算法，我們還可以計算出用戶的相似度，可以向用戶推薦其感興趣的其他用戶。與文本分析不同，對相似度的計算一般基於與使用者的交互資料，如使用者對商品進行投票、打分、流覽、購買等行為，經過適當的流程，將這些交互資料進行數位化，如流覽、購買、投票與否用0/1表示，對打分用實際的分數計算。

這類演算法與文本分析演算法相比具有兩個明顯的優勢：第一是文本分析演算法需要處理英文和中文問題，並且不同語言的處理方法會相當不同，如中文分詞就比英文分詞複雜很多，但是採用相似度計算方法，就不存在不同語言處理問題；第二是相似度計算以使用者與系統間交互資料為依據，這樣可以更好的反映某些熱點條目，從而使推薦結果更具有時效性。

當然，利用計算相似度來進行推薦，由於是基於資料採擷技術，難免會受原始資料中噪音的影響，而且由於當前網路環境，水軍、門戶網站位置行銷或SEO等技術的採用，可能使某些品質低劣的項目成為熱點，因此而降低了推薦品質。因此在使用相似度推薦時，需要綜合考慮各種因素，找到最適合的推薦演算法。

下面我們以用戶對商品進行打分為例，描述相似度的計算方法：

	product1	product2	product3
user1	3	4	2
user2	2	2	4
user3	1	3	5

表1

為了簡單起見，我們假設三個用戶對三個商品進行了打分，分數如表1所示。我們首先想通過該資料計算產品的相似度，因此我們需要將資料進行重新整理：

	user1	user2	user3
product1	3	2	1
product2	4	2	3
product3	2	4	5

表2

到此原始資料準備完畢，下面就是計算相似度演算法了。

通常相似度需要按相似度大小進行排序，我們定義了ItemInfo類來保存相似度排序清單中所需要的資訊。

public class ItemInfo implements Comparable<ItemInfo> {
 public String getKey() {
  return key;
 }
 public void setKey(String key) {
  this.key = key;
 }
 public double getVal() {
  return val;
 }
 public void setVal(double val) {
  this.val = val;
 }
 private String key = null;
 private double val = 0.0;
 @Override
 public int compareTo(ItemInfo o) {
  // TODO Auto-generated method stub
  ItemInfo info = (ItemInfo)o;
  if (val > info.getVal()) {
   return -1;
  } else {
   return 1;
  }
 }
}

我們實現了比較介面，這樣便於對本類組成的List列表進行排序操作。

我們需要定義一個某個產品與其它相品相似度存儲清單類：

public class SmlrList {
 public SmlrList() {
  rates = new Hashtable<String, Double>();
  sortedKeys = new Vector<String>();
  sortedVals = new Vector<ItemInfo>();
 }
 public List<ItemInfo> getSortedVals() {
  return sortedVals;
 }
 public void setSortedVals(List<ItemInfo> sortedVals) {
  this.sortedVals = sortedVals;
 }
 public List<String> getSortedKeys() {
  return sortedKeys;
 }
 public void setSortedKeys(List<String> sortedKeys) {
  this.sortedKeys = sortedKeys;
 }
 public Hashtable<String, Double> getRates() {
  return rates;
 }
 public void setRates(Hashtable<String, Double> rates) {
  this.rates = rates;
 }

 private List<ItemInfo> sortedVals = null;
 private List<String> sortedKeys = null; // 存儲按照相似度排序的key值
 private Hashtable<String, Double> rates = null; // 與其他元素的相似度清單
}
由上面的代碼可以看出，該產品與其他產品相似度存儲在rates清單中，為調試方便，我們加入了sortedKeys，可以按產品序號順序顯示相似度，按相似度由大到小排序的列表是sortedVals。注意：在實際系統中，可以只取sortedVals即可，其它屬性需是用於調試目的。

具體調用代碼如下所示：

/**
  * 計算條目的相似度清單，可以是如產品、地點的相似度，也可以是用戶的相似度
  * 原始資料如下所示：
  * 
  */
 public void test() {
  Hashtable<String, SmlrList> itemsSmlrList = null;
  Vector<String> sortedItemId = null; // 經過排序的條目編號
  Hashtable<String, Hashtable<String, Double>> rateData = null; // 條目被每個使用者評分的資訊
  Hashtable<String, Double> itemRateData = null;
 
  // 初始化原始資料
  rateData = new Hashtable<String, Hashtable<String, Double>>();
  int rowId = 1;
  int colId = 1;
  // 加入第三行
  rowId = 3;
  itemRateData = new Hashtable<String, Double>();
  colId = 1;
  itemRateData.put("" + colId, 2.0);
  colId = 2;
  itemRateData.put("" + colId, 4.0);
  colId = 3;
  itemRateData.put("" + colId, 5.0);
  rateData.put("" + rowId, itemRateData);
  // 加入第一行
  rowId = 1;
  itemRateData = new Hashtable<String, Double>();
  colId = 1;
  itemRateData.put("" + colId, 3.0);
  colId = 2;
  itemRateData.put("" + colId, 2.0);
  colId = 3;
  itemRateData.put("" + colId, 1.0);
  rateData.put("" + rowId, itemRateData);
  // 加入第二行
  rowId = 2;
  itemRateData = new Hashtable<String, Double>();
  colId = 1;
  itemRateData.put("" + colId, 4.0);
  colId = 2;
  itemRateData.put("" + colId, 2.0);
  colId = 3;
  itemRateData.put("" + colId, 3.0);
  rateData.put("" + rowId, itemRateData);
 
  sortedItemId = new Vector<String>(rateData.keySet());
  Collections.sort(sortedItemId);
  // 對原始資料進行歸一化並顯示
  Hashtable<String, Double> normUserRateData = null;
  Vector<String> sortedUk = null;
  for (String rowKey : sortedItemId) {
   double sum = 0.0;
   for (Double dbl : rateData.get(rowKey).values()) {
    sum += dbl.doubleValue() * dbl.doubleValue();
   }
   sum = Math.sqrt(sum);
   normUserRateData = new Hashtable<String, Double>();
   itemRateData = rateData.get(rowKey);
   for (String colKey : itemRateData.keySet()) {
    normUserRateData.put(colKey, itemRateData.get(colKey).doubleValue() / sum);
   }
   rateData.remove(rowKey);
   rateData.put(rowKey, normUserRateData);
   // 列印
   sortedUk = new Vector<String>(rateData.get(rowKey).keySet());
   Collections.sort(sortedUk);
   for (String suk : sortedUk) {
    System.out.print(" " + suk + ":" + rateData.get(rowKey).get(suk).doubleValue());
   }
   System.out.print("\r\n");
  }
 
 
  // 計算條目之間的相似度
  itemsSmlrList = new Hashtable<String, SmlrList>();
  SmlrList smlrList = null;
  ItemInfo itemInfo = null;
  int i = 0;
  int j = 0;
  double smlrVal = 0.0;
  for (i=0; i<sortedItemId.size(); i++) {
   smlrList = new SmlrList();
   for (j=0; j<sortedItemId.size(); j++) {
    smlrVal = calDotProd(new Vector<Double>(rateData.get(sortedItemId.get(i)).values()), 
      new Vector<Double>(rateData.get(sortedItemId.get(j)).values()));
    smlrList.getSmlrs().put(sortedItemId.get(j), smlrVal);
    smlrList.getSortedKeys().add(sortedItemId.get(j));
    itemInfo = new ItemInfo();
    itemInfo.setKey(sortedItemId.get(j));
    itemInfo.setVal(smlrVal);
    smlrList.getSortedVals().add(itemInfo);
   }
   Collections.sort(smlrList.getSortedKeys());
   Collections.sort(smlrList.getSortedVals());
   itemsSmlrList.put(sortedItemId.get(i), smlrList);
  }
 
  // 顯示相似度結果
  SmlrList sl02 = null;
  for (String uk2 : sortedItemId) {
   sl02 = itemsSmlrList.get(uk2);
   System.out.print(uk2 + ":");
   for (String uk3 : sl02.getSortedKeys()) {
    System.out.print(" " + sl02.getSmlrs().get(uk3) + "[" + uk3 + "] ");
   }
   System.out.print("\r\n");
  }
  System.out.println("**************************************");
  for (String rowKey : sortedItemId) {
   smlrList = itemsSmlrList.get(rowKey);
   System.out.print(rowKey + ":");
   for (ItemInfo itemInfo1 : smlrList.getSortedVals()) {
    if (!itemInfo1.getKey().equals(rowKey)) {
     System.out.print(" " + itemInfo1.getVal() + "[" + itemInfo1.getKey() + "] ");
    }
   }
   System.out.print("\r\n");
  }
 }

程式運行結果為：

 1:0.8017837257372732 2:0.5345224838248488 3:0.2672612419124244
 1:0.7427813527082074 2:0.3713906763541037 3:0.5570860145311556
 1:0.29814239699997197 2:0.5962847939999439 3:0.7453559924999299
1: 1.0[1]  0.9429541672723838[2]  0.756978119245116[3] 
2: 0.9429541672723838[1]  1.0[2]  0.8581366251553131[3] 
3: 0.756978119245116[1]  0.8581366251553131[2]  1.0[3] 
**************************************
1: 0.9429541672723838[2]  0.756978119245116[3] 
2: 0.9429541672723838[1]  0.8581366251553131[3] 
3: 0.8581366251553131[2]  0.756978119245116[1]

同理，如果我們需要計算使用者的相似度，只需要將原始資料變為表1格式讀入程式即可。

如上所述，有了上述類和方法，我們可以很容易求出任意兩個條目的相似度，同時可以對某個條目按相似度從大到小的方式，顯示該條目與其他條目相似度。

相似度度量這裡採用向量的點積，點積值越大，表明對應條目的相似度越大，具體計算方法如下所示：

 public double calDotProd(List<Double> vec1, List<Double> vec2) {
  double dotProd = 0.0;
  for (int i=0; i<vec1.size(); i++) {
   dotProd += vec1.get(i).doubleValue() * vec2.get(i).doubleValue();
  }
  return dotProd;
 }

全文檢索、資料採擷、推薦引擎系列6---基於KMean的文本自動演算法

對一系列文章進行自動聚類可以做為基於內容的推薦引擎的基礎，如果要實現文本的自動聚類，首先按照本系列5中所介紹的，對文章進行分詞，然後計算得出文章的術語向量表示，即求文章中每個不同的單詞以其所對應的TF*IDF，具體計算方法如5中所示。目前文本自動聚類演算法中，用得最多是KMean演算法，本文中就介紹KMean演算法的應用。當然，KMean演算法可以通過調用Mahout或WEKA這兩個開源的機器學習演算法庫來實現，但是在這類演算法中需要準備比較複雜的輸入檔，預處理過程比較複雜，還有一點，我們可能在實際應用中要對KMean演算法進行調整，這樣自己編寫KMean演算法重加有助於我們對文本聚類演算法的理解。

我們首先定義術語向量類，用來表示每篇文章的術語向量，還包括文檔編號和類別編號，具體代碼如下所示：

public class SepaTermVector {
 public SepaTermVector() {
  termVector = new Vector<TermInfo>();
 }
 public Vector<TermInfo> getTermVector() {
  return termVector;
 }
 public void setTermVector(Vector<TermInfo> termVector) {
  this.termVector = termVector;
 }
 public int getDocId() {
  return docId;
 }
 public void setDocId(int docId) {
  this.docId = docId;
 }
 public int getClusterId() {
  return clusterId;
 }
 public void setClusterId(int clusterId) {
  this.clusterId = clusterId;
 }

 /**
  * 在使用文章的術語向量時，我們不希望在自動聚類過程中破壞文章的術語向量，所以需要完體複
  * 制一份術語向量給自動聚類演算法
  */
 @Override
 public SepaTermVector clone() {
  SepaTermVector obj = new SepaTermVector();
  obj.setDocId(docId);
  obj.setClusterId(clusterId);
  Vector<TermInfo> vt = new Vector<TermInfo>();
  for (TermInfo item : termVector) {
   vt.add(item);
  }
  obj.setTermVector(vt);
  return obj;
 }
 private Vector<TermInfo> termVector = null; 
 private int docId = -1; // 所屬的文章編號
 private int clusterId = -1; // 所屬的聚類編號
}

然後我們定義文本聚類的類，在該類中保存聚類編號，聚類的中心（本身是該聚類中所有文章術語向量的一個並集）和聚類中所包含的術語向量（每個術語向量代表一篇文章）。代碼如下所示：

public class TextClusterInfo {
 public TextClusterInfo(int clusterId) {
  this.clusterId = clusterId;
  items = new Vector<SepaTermVector>(); // 考慮執行緒安全性而犧牲部分性能
 }

 public void addItem(SepaTermVector item) {
  items.add(item);
 }

 public void clearItems() {
  items.clear();
 }

 /**
  * 計算本類型的中心點
  */
 public void computeCenter() {
  if (items.size() <= 0) {
   return ;
  }
  for (SepaTermVector item : items) {
   if (null == center) {
    center = item;
   } else {
    center = DocTermVector.calCenterTermVector(item, center);
   }
  }
 }

 public int getClusterId() {
  return clusterId;
 }
 public void setClusterId(int clusterId) {
  this.clusterId = clusterId;
 }
 public SepaTermVector getCenter() {
  return center;
 }
 public void setCenter(SepaTermVector center) {
  this.center = center;
 }
 public List<SepaTermVector> getItems() {
  return items;
 }
 public void setItems(List<SepaTermVector> items) {
  this.items = items;
 }
 private int clusterId = 0;
 private SepaTermVector center = null;
 private List<SepaTermVector> items = null;
}

接下來就是KMean自動聚類演算法的工具類了，這裡需要注意的是標準KMean自動聚類演算法中，只需要指定初始的聚類數，然後由演算法自動隨機選擇聚類中心，然後進行反覆運算，最終找出自動聚類結果。為了降低演算法計算強度，我們在實際中不但給出了聚類數量，還給出了每個聚類的中心術語向量，即在大量文本中，找出每個聚類中的一篇代表性文章，作為參數傳給自動聚類演算法，在我們的實驗資料中，可以很快達到收斂的效果，並且準確性很高。

KMean算分為下列幾步：

1. 根據所給出的聚類中心初始化聚類
2. 清空每個聚類中屬於該聚類的術語向量列表
3. 針對每篇文章的術語向量，求出與其最近的聚類，將該術語向量加入到該聚類，如果上次迴圈中求出的聚類和本次不同，則表明還需繼續運行聚類演算法
4. 計算加入新術語向量後的聚類新的中心
5. 判斷是否還需要運行自動聚類演算法，若需要則回到2

衡量術語向量與聚類的相似度採用點積形式，就是術語向量與聚類中心所代表的術語向量相同單詞權值之和，值越大代表二者越相像，具體代碼如下所示：

 public static double getDotProdTvs(SepaTermVector stv1, SepaTermVector stv2) {
  double dotProd = 0.0;
  Hashtable<String, Double> dict = new Hashtable<String, Double>();
  for (TermInfo info : stv2.getTermVector()) {
   dict.put(info.getTermStr(), info.getWeight());
  }
  for (TermInfo item : stv1.getTermVector()) {
   if (dict.get(item.getTermStr())!= null) {
    dotProd += item.getWeight() * dict.get(item.getTermStr()).doubleValue();
   }
  }
  return dotProd;
 }

下面KMean演算法實現類的代碼：

public class TextKMeanCluster {
 /**
  * 在通常情況下，我們需要將待分類文本分出大致的類別來，即確定numClusters。在有些情況下，還可以指定某個類別中
  * 的一篇文章。這樣可以避免演算法不收斂時聚類的品質問題。
  * @param docTermVectors 需要進行聚類的術語向量
  * @param numClusters 聚類數量
  */
 public TextKMeanCluster(List<SepaTermVector> docTermVectors, int numClusters) {
  this.docTermVectors = docTermVectors;
  this.numClusters = numClusters;
 }

 /**
  * 對文章進行聚類
  * @param initCenters 聚類的中心點
  * @return 聚類結果
  */
 public List<TextClusterInfo> cluster(List<SepaTermVector> initCenters) {
  if (docTermVectors.size() <= 0) {
   return null;
  }
  initClusters(initCenters);
  boolean hadReassign = true;
  int runTimes = 0;
  while ((runTimes<=MAX_KMEAN_RUNTIMES) && (hadReassign)) {
   System.out.println("runTimes=" + runTimes + "!");
   clearClusterItems();
   hadReassign = reassignClusters();
   computeClusterCenters();
   runTimes++;
  }
  return clusters;
 }

 /**
  * 本演算法中採用給定聚類中心的方式，但是在標準KMean演算法中是隨機選擇聚類中心的，隨機選擇收斂較慢。
  */
 public void initClusters(List<SepaTermVector> initCenters) {
  clusters = new Vector<TextClusterInfo>();
  TextClusterInfo cluster = null;
  int i = 0;
  for (SepaTermVector stv : initCenters) {
   cluster = new TextClusterInfo(i++);
   cluster.setCenter(stv);
   clusters.add(cluster);
  }
 }

 /**
  * 求出所有文章術語向量的新聚類，如果與上次求出的聚類不同，則表明需要繼續運行
  * @return 真時代表需要繼續運行自動聚類演算法
  */
 public boolean reassignClusters() {
  int numChanges = 0;
  TextClusterInfo newCluster = null;
  for (SepaTermVector termVector : docTermVectors) {
   newCluster = getClosetCluster(termVector);
   if ((termVector.getClusterId()<0) || termVector.getClusterId() != newCluster.getClusterId()) {
    numChanges++;
    termVector.setClusterId(newCluster.getClusterId());
   }
   newCluster.addItem(termVector);
   //System.out.println("reassignCluster:cid=" + newCluster.getClusterId() + ":size=" + 
     //newCluster.getItems().size());
  }
  return (numChanges>0);
 }

 /**
  * 求出加入新述語向量後聚類的新中心
  */
 public void computeClusterCenters() {
  for (TextClusterInfo cluster : clusters) {
   cluster.computeCenter();
  }
 }

 /**
  * 清除該聚類的術語向量列表
  */
 public void clearClusterItems() {
  for (TextClusterInfo cluster : clusters) {
   cluster.clearItems();
  }
 }

 /**
  * 在標準KMean演算法中隨機抽取聚類中心的演算法，在本類中該方法暫時未使用
  * @param usedIndex
  * @return
  */
 private SepaTermVector getTermVectorAtRandom(Hashtable<Integer, Integer> usedIndex) {
  boolean found = false;
  int index = -1;
  while (!found) {
   index = (int)Math.floor(Math.random() * docTermVectors.size());
   while (usedIndex.get(index) != null) {
    index = (int)Math.floor(Math.random() * docTermVectors.size());
   }
   usedIndex.put(index, index);
   return docTermVectors.get(index).clone(); // 重新複製一份，不破壞原來的拷貝
  }
  return null;
 }

 /**
  * 對術語向量和所有聚類中心所代表的術語向量做點積，取值最大的聚類為該文檔的聚類
  * @param termVector 術語向量
  * @return 與該術語向量最接近的聚類
  */
 private TextClusterInfo getClosetCluster(SepaTermVector termVector) {
  TextClusterInfo closetCluster = null;
  double dotProd = -1.0;
  double maxDotProd = -2.0;
  double dist = -1.0;
  double smallestDist = Double.MAX_VALUE;
  for (TextClusterInfo cluster : clusters) {
   //dist = DocTermVector.calTermVectorDist(cluster.getCenter(), termVector);
   dotProd = DocTermVector.getDotProdTvs(cluster.getCenter(), termVector);
   //System.out.println("getClosetCluster:dotProd=" + dotProd + "[" + maxDotProd + "] docId="
     //+ termVector.getDocId() + "!");
   //if (dist < smallestDist) {
   if (dotProd > maxDotProd) {
    //smallestDist = dist;
    maxDotProd = dotProd;
    closetCluster = cluster;
   }
  }
  return closetCluster;
 }

 public final static int MAX_KMEAN_RUNTIMES = 1000;

 private List<SepaTermVector> docTermVectors = null; // 所有文章的術語向量
 private List<SepaTermVector> centers = null;
 private List<TextClusterInfo> clusters = null; // 所有聚類
 private int numClusters = 0;
}

具體的調用方法如下所示：

DocTermVector.init();
  // 技術類
  int doc1Id = FteEngine.genTermVector(-1, "Java語言程式設計技術詳解", "", "", "", "");
  int doc2Id = FteEngine.genTermVector(-1, "C++語言程式設計指南", "", "", "", "");
  int doc4Id = FteEngine.genTermVector(-1, "Python程式設計教程", "", "", "", "");
  // 同性戀
  int doc3Id = FteEngine.genTermVector(-1, "同性戀網站變身電子商務網站", "", "", "", "");
  int doc5Id = FteEngine.genTermVector(-1, "同性戀網站大全", "", "", "", "");
  int doc6Id = FteEngine.genTermVector(-1, "男同性戀特點", "同性戀", "", "", "");
  // 天使投資
  int doc7Id = FteEngine.genTermVector(-1, "天使投資社交網路", "", "", "", "");
  int doc8Id = FteEngine.genTermVector(-1, "天使投資發展概況", "", "", "", "");
  int doc9Id = FteEngine.genTermVector(-1, "著名天使投資人和天使投資機構", "", "", "", "");
  // 環境保護
  int doc10Id = FteEngine.genTermVector(-1, "環境保護技術分析", "", "", "", "");
  int doc11Id = FteEngine.genTermVector(-1, "環境保護與碳關稅分析", "", "", "", "");
  int doc12Id = FteEngine.genTermVector(-1, "環境保護與我國經濟發展趨勢", "", "", "", "");
 
  FteEngine.genTermVector(-1, "VB程式設計指南", "", "", "", "");
  FteEngine.genTermVector(-1, "天使投資社區天使街正式上線運行", "", "", "", "");
  FteEngine.genTermVector(-1, "年度程式設計語言評選活動", "", "", "", "");

List<SepaTermVector> centers = new Vector<SepaTermVector>();
  centers.add(DocTermVector.getDocTermVector(0));
  centers.add(DocTermVector.getDocTermVector(3));
  centers.add(DocTermVector.getDocTermVector(6));
  centers.add(DocTermVector.getDocTermVector(9));
  TextKMeanCluster tkmc = new TextKMeanCluster(DocTermVector.getDocTermVectors(), 4);
  List<TextClusterInfo> rst = tkmc.cluster(centers);
  String lineStr = null;
  for (TextClusterInfo info : rst) {
   lineStr = "" + info.getClusterId() + "(" + info.getItems().size() + "):";
   for (SepaTermVector tvItem : info.getItems()) {
    lineStr += " " + tvItem.getDocId();
   }
   lineStr += "^_^";
   System.out.println(lineStr);
  }

運行的結果為：

0(5): 0 1 2 12 14^_^
1(3): 3 4 5^_^
2(4): 6 7 8 13^_^
3(3): 9 10 11^_^

由上面的結果來看，實現了基本正確的聚類。

全文檢索、資料採擷、推薦引擎系列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

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