2012年5月17日 星期四

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


沒有留言: