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