1/1, 7«1»

阅读摘要:推荐算法介绍(隐性打分)

2010-3-1 19:40:59 开发者 抢沙发(0)

 来源:http://blog.csdn.net/liuzhenwen/archive/2009/04/22/4101003.aspx

推荐系统最早在亚马逊的网站上应用,根据以往用户的购买行为,推荐出购买某种产品同时可能购买的其他产品。

直接打分需要用户的参与程度比较高,很多网站都在内容页中留一个打分的按钮,从1~5选一 个,我可能喜欢这篇文章,可我哪里知道我喜欢的程度是几分啊,还要我去思考,而网站设计中一条很重要的原则是:Do not let me think!,于是我就胡打一个分数或者不打,而隐性的打分则不同,只有你喜欢的图书你才会购买,只有你喜欢的歌曲才会听多次。

最近邻搜索算法一般是皮尔森相关系数(Person Correlation Coefficient)、余弦相似性(Cosine-based Similarity)以及调整余弦相似性(Adjusted Cosine Similarity)。关于余弦定理在数据挖掘中的应用,google黑白报有过介绍,可以参考数学之美 系列 12 - 余弦定理和新闻的分类

 

基本原理

用户          对事物A打分 对事物B打分
X 3 4
Y 2 4
Z 4 ?

用户Z对事物B的打分可能是多少呢?股票上有个说法是平均值可以掩盖一切异常波动,所以股票上的各个技术指标收拾不同时间段的平均值的曲线图或者柱 状图等。同样的,Slope one算法也认为:平均值也可以代替某两个未知个体之间的打分差异,事物A对事物B的平均很差是:((3 - 4) + (2 - 4)) / 2 = -1.5,也就是说人们对事物B的打分一般比事物A的打分要高1.5,于是Slope one算法就猜测Z对事物B的打分是4 + 1.5 = 5.5

 

 

加权算法

有n个人对事物A和事物B打分了,R(A->B)表示这n个人对A和对B打分的平均差(A-B),有m个人对事物B和事物C打分 了,R(C->B)表示这m个人对C和对B打分的平均差(C-B),注意都是平均差而不是平方差,现在某个用户对A的打分是ra,对C的打分是 rc,那么A对B的打分可能是:

rb = (n * (ra - R(A->B)) + m * (rc - R(C->B)))/(m+n)

 

 

 

 

  1.  
  2. # This is the code in plain text out of the technical report. 
  3. # Daniel Lemire, Sean McGrath, Implementing a Rating-Based Item-to-Item 
  4. # Recommender System in PHP/SQL, Technical Report D-01, January 2005. 
  5. # http://www.ondelette.com/lemire/abstracts/TRD01.html 
  6. # This code is in the public domain, use at your own risks. 
  7. # It is assumed that you looked at the report and know some SQL and PHP. 
  8. # Daniel Lemire, February 3rd 2005 
  9. # First part is sample SQL code. 
  10. #########CUT HERE#################### 
  11.  
  12. CREATE TABLE rating ( 
  13.     userID INT PRIMARY KEY, 
  14.     itemID INT NOT NULL, 
  15.     ratingValue INT NOT NULL, 
  16.     datetimestamp TIMESTAMP NOT NULL 
  17. ); 
  18.  
  19.  
  20. CREATE TABLE dev ( 
  21.   itemID1 int(11) NOT NULL default '0'
  22.   itemID2 int(11) NOT NULL default '0'
  23.   count int(11) NOT NULL default '0'
  24.   sum int(11) NOT NULL default '0'
  25.   PRIMARY KEY  (itemID1,itemID2) 
  26. ); 
  27.  
  28.  
  29. # simple query to output 10 most liked items 
  30. # by people who rated item 1 
  31. SELECT itemID2, ( sum / count ) AS average 
  32. FROM dev 
  33. WHERE count > 2 AND itemID1 = 1 
  34. ORDER  BY ( sum / count ) DESC 
  35. LIMIT 10; 
  36.  
  37. # Next part is sample PHP code. 
  38. #########CUT HERE#################### 
  39.  
  40. // This code assumes $itemID is set to that of  
  41. // the item that was just rated.  
  42. // Get all of the user's rating pairs 
  43. $sql = "SELECT DISTINCT r.itemID, r2.ratingValue - r.ratingValue  
  44.             as rating_difference 
  45.             FROM rating r, rating r2 
  46.             WHERE r.userID=$userID AND  
  47.                     r2.itemID=$itemID AND  
  48.                     r2.userID=$userID;"; 
  49. $db_result = mysql_query($sql$connection); 
  50. $num_rows = mysql_num_rows($db_result); 
  51. //For every one of the user's rating pairs,  
  52. //update the dev table 
  53. while ($row = mysql_fetch_assoc($db_result)) { 
  54.     $other_itemID = $row["itemID"]; 
  55.     $rating_difference = $row["rating_difference"]; 
  56.     //if the pair ($itemID, $other_itemID) is already in the dev table 
  57.     //then we want to update 2 rows. 
  58.     if (mysql_num_rows(mysql_query("SELECT itemID1  
  59.     FROM dev WHERE itemID1=$itemID AND itemID2=$other_itemID", 
  60.     $connection)) > 0)  { 
  61.         $sql = "UPDATE dev SET count=count+1,  
  62.     sum=sum+$rating_difference WHERE itemID1=$itemID  
  63.     AND itemID2=$other_itemID"; 
  64.         mysql_query($sql$connection); 
  65.     //We only want to update if the items are different                 
  66.         if ($itemID != $other_itemID) { 
  67.             $sql = "UPDATE dev SET count=count+1,  
  68.         sum=sum-$rating_difference  
  69.         WHERE (itemID1=$other_itemID AND itemID2=$itemID)"; 
  70.             mysql_query($sql$connection); 
  71.         } 
  72.     } 
  73.     else { //we want to insert 2 rows into the dev table 
  74.         $sql = "INSERT INTO dev VALUES ($itemID$other_itemID
  75.         1, $rating_difference)"; 
  76.         mysql_query($sql$connection);  
  77.     //We only want to insert if the items are different        
  78.         if ($itemID != $other_itemID) {          
  79.             $sql = "INSERT INTO dev VALUES ($other_itemID,  
  80.         $itemID, 1, -$rating_difference)"; 
  81.             mysql_query($sql$connection); 
  82.         } 
  83.     }     
  84.  
  85.  
  86. function predict($userID$itemID) { 
  87.     global $connection;     
  88.     $denom = 0.0; //denominator 
  89.     $numer = 0.0; //numerator     
  90.     $k = $itemID;     
  91.     $sql = "SELECT r.itemID, r.ratingValue  
  92.     FROM rating r WHERE r.userID=$userID AND r.itemID <> $itemID"; 
  93.     $db_result = mysql_query($sql$connection);         
  94.     //for all items the user has rated 
  95.     while ($row = mysql_fetch_assoc($db_result))  { 
  96.         $j = $row["itemID"]; 
  97.         $ratingValue = $row["ratingValue"];         
  98.         //get the number of times k and j have both been rated by the same user 
  99.         $sql2 = "SELECT d.count, d.sum FROM dev d WHERE itemID1=$k AND itemID2=$j"
  100.         $count_result = mysql_query($sql2$connection);         
  101.         //skip the calculation if it isn't found 
  102.         if(mysql_num_rows($count_result) > 0)  { 
  103.             $count = mysql_result($count_result, 0, "count"); 
  104.             $sum = mysql_result($count_result, 0, "sum");             
  105.             //calculate the average 
  106.             $average = $sum / $count;             
  107.             //increment denominator by count 
  108.             $denom += $count;             
  109.             //increment the numerator 
  110.             $numer += $count * ($average + $ratingValue); 
  111.         }         
  112.     }     
  113.     if ($denom == 0) 
  114.         return 0; 
  115.     else 
  116.         return ($numer / $denom); 
  117.  
  118.  
  119. function predict_all($userID ) { 
  120.     $sql2 = "SELECT d.itemID1 as 'item', sum(d.countas 'denom',  
  121.     sum(d.sum + d.count*r.ratingValue) as 'numer' FROM item i, rating r, 
  122.     dev d WHERE r.userID=$userID  
  123.     AND d.itemID1<>r.itemID  
  124.     AND d.itemID2=r.itemID GROUP BY d.itemID1"; 
  125.     return mysql_query($sql2$connection); 

 

Java:

  1. import java.util.*; 
  2. /** 
  3. * Daniel Lemire 
  4. * A simple implementation of the weighted slope one 
  5. * algorithm in Java for item-based collaborative  
  6. * filtering.  
  7. * Assumes Java 1.5. 
  8. * 
  9. * See main function for example. 
  10. * 
  11. * June 1st 2006. 
  12. * Revised by Marco Ponzi on March 29th 2007 
  13. */ 
  14.  
  15. public class SlopeOne { 
  16.    
  17.   public static void main(String args[]){ 
  18.     // this is my data base 
  19.     Map<UserId,Map<ItemId,Float>> data = new HashMap<UserId,Map<ItemId,Float>>(); 
  20.     // items 
  21.     ItemId item1 = new ItemId("       candy"); 
  22.     ItemId item2 = new ItemId("         dog"); 
  23.     ItemId item3 = new ItemId("         cat"); 
  24.     ItemId item4 = new ItemId("         war"); 
  25.     ItemId item5 = new ItemId("strange food"); 
  26.      
  27.     mAllItems = new ItemId[]{item1, item2, item3, item4, item5}; 
  28.      
  29.     //I'm going to fill it in 
  30.     HashMap<ItemId,Float> user1 = new HashMap<ItemId,Float>(); 
  31.     HashMap<ItemId,Float> user2 = new HashMap<ItemId,Float>(); 
  32.     HashMap<ItemId,Float> user3 = new HashMap<ItemId,Float>(); 
  33.     HashMap<ItemId,Float> user4 = new HashMap<ItemId,Float>(); 
  34.     user1.put(item1,1.0f); 
  35.     user1.put(item2,0.5f); 
  36.     user1.put(item4,0.1f); 
  37.     data.put(new UserId("Bob"),user1); 
  38.     user2.put(item1,1.0f); 
  39.     user2.put(item3,0.5f); 
  40.     user2.put(item4,0.2f); 
  41.     data.put(new UserId("Jane"),user2); 
  42.     user3.put(item1,0.9f); 
  43.     user3.put(item2,0.4f); 
  44.     user3.put(item3,0.5f); 
  45.     user3.put(item4,0.1f); 
  46.     data.put(new UserId("Jo"),user3);     
  47.     user4.put(item1,0.1f); 
  48.     //user4.put(item2,0.4f); 
  49.     //user4.put(item3,0.5f); 
  50.     user4.put(item4,1.0f); 
  51.     user4.put(item5,0.4f); 
  52.     data.put(new UserId("StrangeJo"),user4);     
  53.     // next, I create my predictor engine 
  54.     SlopeOne so = new SlopeOne(data); 
  55.     System.out.println("Here's the data I have accumulated..."); 
  56.     so.printData(); 
  57.     // then, I'm going to test it out... 
  58.     HashMap<ItemId,Float> user = new HashMap<ItemId,Float>(); 
  59.     System.out.println("Ok, now we predict..."); 
  60.     user.put(item5,0.4f); 
  61.     System.out.println("Inputting..."); 
  62.     SlopeOne.print(user); 
  63.     System.out.println("Getting..."); 
  64.     SlopeOne.print(so.predict(user)); 
  65.     // 
  66.     user.put(item4,0.2f); 
  67.     System.out.println("Inputting..."); 
  68.     SlopeOne.print(user); 
  69.     System.out.println("Getting..."); 
  70.     SlopeOne.print(so.predict(user)); 
  71.   } 
  72.    
  73.   Map<UserId,Map<ItemId,Float>> mData; 
  74.   Map<ItemId,Map<ItemId,Float>> mDiffMatrix; 
  75.   Map<ItemId,Map<ItemId,Integer>> mFreqMatrix; 
  76.    
  77.   static ItemId[] mAllItems; 
  78.    
  79.   public SlopeOne(Map<UserId,Map<ItemId,Float>> data) { 
  80.     mData = data; 
  81.     buildDiffMatrix();     
  82.   } 
  83.    
  84.   /** 
  85.   * Based on existing data, and using weights, 
  86.   * try to predict all missing ratings. 
  87.   * The trick to make this more scalable is to consider 
  88.   * only mDiffMatrix entries having a large  (>1) mFreqMatrix 
  89.   * entry. 
  90.   * 
  91.   * It will output the prediction 0 when no prediction is possible. 
  92.   */ 
  93.   public Map<ItemId,Float> predict(Map<ItemId,Float> user) { 
  94.     HashMap<ItemId,Float> predictions = new HashMap<ItemId,Float>(); 
  95.     HashMap<ItemId,Integer> frequencies = new HashMap<ItemId,Integer>(); 
  96.     for (ItemId j : mDiffMatrix.keySet()) { 
  97.       frequencies.put(j,0); 
  98.       predictions.put(j,0.0f); 
  99.     } 
  100.     for (ItemId j : user.keySet()) { 
  101.       for (ItemId k : mDiffMatrix.keySet()) { 
  102.         try { 
  103.         float newval = ( mDiffMatrix.get(k).get(j).floatValue() + user.get(j).floatValue() ) * mFreqMatrix.get(k).get(j).intValue(); 
  104.         predictions.put(k, predictions.get(k)+newval); 
  105.         frequencies.put(k, frequencies.get(k)+mFreqMatrix.get(k).get(j).intValue()); 
  106.         } catch(NullPointerException e) {} 
  107.       } 
  108.     } 
  109.     HashMap<ItemId,Float> cleanpredictions = new HashMap<ItemId,Float>(); 
  110.     for (ItemId j : predictions.keySet()) { 
  111.         if (frequencies.get(j)>0) { 
  112.           cleanpredictions.put(j, predictions.get(j).floatValue()/frequencies.get(j).intValue()); 
  113.         } 
  114.     } 
  115.     for (ItemId j : user.keySet()) { 
  116.          cleanpredictions.put(j,user.get(j)); 
  117.     } 
  118.     return cleanpredictions; 
  119.   } 
  120.    
  121.   /** 
  122.   * Based on existing data, and not using weights, 
  123.   * try to predict all missing ratings. 
  124.   * The trick to make this more scalable is to consider 
  125.   * only mDiffMatrix entries having a large  (>1) mFreqMatrix 
  126.   * entry. 
  127.   */ 
  128.   public Map<ItemId,Float> weightlesspredict(Map<ItemId,Float> user) { 
  129.     HashMap<ItemId,Float> predictions = new HashMap<ItemId,Float>(); 
  130.     HashMap<ItemId,Integer> frequencies = new HashMap<ItemId,Integer>(); 
  131.     for (ItemId j : mDiffMatrix.keySet()) { 
  132.       predictions.put(j,0.0f); 
  133.       frequencies.put(j,0); 
  134.     } 
  135.     for (ItemId j : user.keySet()) { 
  136.       for (ItemId k : mDiffMatrix.keySet()) { 
  137.         //System.out.println("Average diff between "+j+" and "+ k + " is "+mDiffMatrix.get(k).get(j).floatValue()+" with n = "+mFreqMatrix.get(k).get(j).floatValue()); 
  138.         float newval = ( mDiffMatrix.get(k).get(j).floatValue() + user.get(j).floatValue() ) ; 
  139.         predictions.put(k, predictions.get(k)+newval); 
  140.       } 
  141.     } 
  142.     for (ItemId j : predictions.keySet()) { 
  143.         predictions.put(j, predictions.get(j).floatValue()/user.size()); 
  144.     } 
  145.     for (ItemId j : user.keySet()) { 
  146.       predictions.put(j,user.get(j)); 
  147.     } 
  148.     return predictions; 
  149.   } 
  150.  
  151.  
  152.   public void printData() { 
  153.         for(UserId user : mData.keySet()) { 
  154.           System.out.println(user); 
  155.           print(mData.get(user)); 
  156.         } 
  157.         for (int i=0; i<mAllItems.length; i++) { 
  158.             System.out.print("\n" + mAllItems[i] + ":"); 
  159.             printMatrixes(mDiffMatrix.get(mAllItems[i]), mFreqMatrix.get(mAllItems[i])); 
  160.         } 
  161.       } 
  162.  
  163.     private void printMatrixes(Map<ItemId,Float> ratings, 
  164.                 Map<ItemId,Integer> frequencies) {   
  165.             for (int j=0; j<mAllItems.length; j++) { 
  166.                 System.out.format("%10.3f", ratings.get(mAllItems[j])); 
  167.                 System.out.print(" "); 
  168.                 System.out.format("%10d", frequencies.get(mAllItems[j])); 
  169.             } 
  170.         System.out.println(); 
  171.     } 
  172.    
  173.   public static void print(Map<ItemId,Float> user) { 
  174.     for (ItemId j : user.keySet()) { 
  175.       System.out.println(" "+ j+ " --> "+user.get(j).floatValue()); 
  176.     } 
  177.   } 
  178.    
  179.   public void buildDiffMatrix() { 
  180.     mDiffMatrix = new HashMap<ItemId,Map<ItemId,Float>>(); 
  181.     mFreqMatrix = new HashMap<ItemId,Map<ItemId,Integer>>(); 
  182.     // first iterate through users 
  183.     for(Map<ItemId,Float> user : mData.values()) { 
  184.       // then iterate through user data 
  185.       for(Map.Entry<ItemId,Float> entry: user.entrySet()) { 
  186.         if(!mDiffMatrix.containsKey(entry.getKey())) { 
  187.           mDiffMatrix.put(entry.getKey(), new HashMap<ItemId,Float>()); 
  188.           mFreqMatrix.put(entry.getKey(), new HashMap<ItemId,Integer>()); 
  189.         } 
  190.         for(Map.Entry<ItemId,Float> entry2: user.entrySet()) { 
  191.           int oldcount = 0
  192.           if(mFreqMatrix.get(entry.getKey()).containsKey(entry2.getKey())) 
  193.             oldcount = mFreqMatrix.get(entry.getKey()).get(entry2.getKey()).intValue(); 
  194.           float olddiff = 0.0f; 
  195.           if(mDiffMatrix.get(entry.getKey()).containsKey(entry2.getKey())) 
  196.             olddiff = mDiffMatrix.get(entry.getKey()).get(entry2.getKey()).floatValue(); 
  197.           float observeddiff = entry.getValue() - entry2.getValue(); 
  198.           mFreqMatrix.get(entry.getKey()).put(entry2.getKey(),oldcount + 1); 
  199.           mDiffMatrix.get(entry.getKey()).put(entry2.getKey(),olddiff+observeddiff);           
  200.         } 
  201.       } 
  202.     } 
  203.     for (ItemId j : mDiffMatrix.keySet()) { 
  204.       for (ItemId i : mDiffMatrix.get(j).keySet()) { 
  205.         float oldvalue = mDiffMatrix.get(j).get(i).floatValue(); 
  206.         int count = mFreqMatrix.get(j).get(i).intValue(); 
  207.         mDiffMatrix.get(j).put(i,oldvalue/count); 
  208.       } 
  209.     } 
  210.   } 
  211.  
  212. class UserId  { 
  213.   String content; 
  214.   public UserId(String s) { 
  215.     content = s; 
  216.   } 
  217.    
  218.   public int hashCode() { return content.hashCode();} 
  219.   public String toString() { return content; } 
  220. class ItemId  { 
  221.   String content; 
  222.   public ItemId(String s) { 
  223.     content = s; 
  224.   } 
  225.   public int hashCode() { return content.hashCode();} 
  226.   public String toString() { return content; } 

 

Python:

  1. # Copyright 2006 Bryan O'Sullivan <bos@serpentine.com>. 
  2. # 
  3. # This software may be used and distributed according to the terms 
  4. # of the GNU General Public License, version 2 or later, which is 
  5. # incorporated herein by reference. 
  6.  
  7. class SlopeOne(object): 
  8.     def __init__(self): 
  9.         self.diffs = {} 
  10.         self.freqs = {} 
  11.  
  12.     def predict(self, userprefs): 
  13.         preds, freqs = {}, {} 
  14.         for item, rating in userprefs.iteritems(): 
  15.             for diffitem, diffratings in self.diffs.iteritems(): 
  16.                 try
  17.                     freq = self.freqs[diffitem][item] 
  18.                 except KeyError: 
  19.                     continue 
  20.                 preds.setdefault(diffitem, 0.0
  21.                 freqs.setdefault(diffitem, 0
  22.                 preds[diffitem] += freq * (diffratings[item] + rating) 
  23.                 freqs[diffitem] += freq 
  24.         return dict([(item, value / freqs[item]) 
  25.                      for item, value in preds.iteritems() 
  26.                      if item not in userprefs and freqs[item] > 0]) 
  27.  
  28.     def update(self, userdata): 
  29.         for ratings in userdata.itervalues(): 
  30.             for item1, rating1 in ratings.iteritems(): 
  31.                 self.freqs.setdefault(item1, {}) 
  32.                 self.diffs.setdefault(item1, {}) 
  33.                 for item2, rating2 in ratings.iteritems(): 
  34.                     self.freqs[item1].setdefault(item2, 0
  35.                     self.diffs[item1].setdefault(item2, 0.0
  36.                     self.freqs[item1][item2] += 1 
  37.                     self.diffs[item1][item2] += rating1 - rating2 
  38.         for item1, ratings in self.diffs.iteritems(): 
  39.             for item2 in ratings: 
  40.                 ratings[item2] /= self.freqs[item1][item2] 
  41.  
  42. if __name__ == '__main__'
  43.     userdata = dict( 
  44.         alice=dict(squid=1.0
  45.                    cuttlefish=0.5
  46.                    octopus=0.2), 
  47.         bob=dict(squid=1.0
  48.                  octopus=0.5
  49.                  nautilus=0.2), 
  50.         carole=dict(squid=0.2
  51.                     octopus=1.0
  52.                     cuttlefish=0.4
  53.                     nautilus=0.4), 
  54.         dave=dict(cuttlefish=0.9
  55.                   octopus=0.4
  56.                   nautilus=0.5), 
  57.         ) 
  58.     s = SlopeOne() 
  59.     s.update(userdata) 
  60.     print s.predict(dict(squid=0.4)) 

 

 =-========================== 延伸文章===========================

来源 : http://my.donews.com/clickstone/2006/10/16/fktEQWUckzvGDyfjugcqcJjkaDpdjemooGTf/

 

本文是关于推荐系统的系列研究文章之一,其他内容将陆续发布。这些内容,大多数来自我在2004年底完成的一篇项目方案建议书。放在这里,抛砖引玉,供大家讨论之用。
-------------------------------------------------

在推荐系统简介中,我们给出了推荐系统的一般框架。很明显,推荐方法是整个推荐系统中最核心、最关键的部分,很大程度上决定了推荐系统性能的优劣。目前,主要的推荐方法包括:基于内容推荐、协同过滤推荐、基于关联规则推荐、基于效用推荐、基于知识推荐和组合推荐。

一、基于内容推荐

基于内容的推荐(Content-based Recommendation)是信息过滤技术的延续与发展,它是建立在项目的内容信息上作出推荐的,而不需要依据用户对项目的评价意见,更多地需要用机 器学习的方法从关于内容的特征描述的事例中得到用户的兴趣资料。在基于内容的推荐系统中,项目或对象是通过相关的特征的属性来定义,系统基于用户评价对象 的特征,学习用户的兴趣,考察用户资料与待预测项目的相匹配程度。用户的资料模型取决于所用学习方法,常用的有决策树、神经网络和基于向量的表示方法等。 基于内容的用户资料是需要有用户的历史数据,用户资料模型可能随着用户的偏好改变而发生变化。

基于内容推荐方法的优点是:
 1)不需要其它用户的数据,没有冷开始问题和稀疏问题。
 2)能为具有特殊兴趣爱好的用户进行推荐。
 3)能推荐新的或不是很流行的项目,没有新项目问题。
 4)通过列出推荐项目的内容特征,可以解释为什么推荐那些项目。
 5)已有比较好的技术,如关于分类学习方面的技术已相当成熟。

缺点是要求内容能容易抽取成有意义的特征,要求特征内容有良好的结构性,并且用户的口味必须能够用内容特征形式来表达,不能显式地得到其它用户的判断情况。

二、协同过滤推荐

协同过滤推荐(Collaborative Filtering Recommendation)技术是推荐系统中应用最早和最为成功的技术之一。它一般采用最近邻技术,利用用户的历史喜好信息计算用户之间的距离,然后 利用目标用户的最近邻居用户对商品评价的加权评价值来预测目标用户对特定商品的喜好程度,系统从而根据这一喜好程度来对目标用户进行推荐。协同过滤最大优 点是对推荐对象没有特殊的要求,能处理非结构化的复杂对象,如音乐、电影。

协同过滤是基于这样的假设:为一用户找到他真正感兴趣的内容的好方法是首先找到与此用户有相似兴趣的其他用户,然后将他们感兴趣的内容推荐给此用 户。其基本思想非常易于理解,在日常生活中,我们往往会利用好朋友的推荐来进行一些选择。协同过滤正是把这一思想运用到电子商务推荐系统中来,基于其他用 户对某一内容的评价来向目标用户进行推荐。

基于协同过滤的推荐系统可以说是从用户的角度来进行相应推荐的,而且是自动的,即用户获得的推荐是系统从购买模式或浏览行为等隐式获得的,不需要用户努力地找到适合自己兴趣的推荐信息,如填写一些调查表格等。

和基于内容的过滤方法相比,协同过滤具有如下的优点:
1) 能够过滤难以进行机器自动内容分析的信息,如艺术品,音乐等。
2) 共享其他人的经验,避免了内容分析的不完全和不精确,并且能够基于一些复杂的,难以表述的概念(如信息质量、个人品味)进行过滤。
3) 有推荐新信息的能力。可以发现内容上完全不相似的信息,用户对推荐信息的内容事先是预料不到的。这也是协同过滤和基于内容的过滤一个较大的差别,基于内容的过滤推荐很多都是用户本来就熟悉的内容,而协同过滤可以发现用户潜在的但自己尚未发现的兴趣偏好。
4) 能够有效的使用其他相似用户的反馈信息,较少用户的反馈量,加快个性化学习的速度。

虽然协同过滤作为一种典型的推荐技术有其相当的应用,但协同过滤仍有许多的问题需要解决。最典型的问题有稀疏问题(Sparsity)和可扩展问题(Scalability)。

三、基于关联规则推荐

基于关联规则的推荐(Association Rule-based Recommendation)是以关联规则为基础,把已购商品作为规则头,规则体为推荐对象。关联规则挖掘可以发现不同商品在销售过程中的相关性,在零 售业中已经得到了成功的应用。管理规则就是在一个交易数据库中统计购买了商品集X的交易中有多大比例的交易同时购买了商品集Y,其直观的意义就是用户在购 买某些商品的时候有多大倾向去购买另外一些商品。比如购买牛奶的同时很多人会同时购买面包。

算法的第一步关联规则的发现最为关键且最耗时,是算法的瓶颈,但可以离线进行。其次,商品名称的同义性问题也是关联规则的一个难点。

四、基于效用推荐

基于效用的推荐(Utility-based Recommendation)是建立在对用户使用项目的效用情况上计算的,其核心问题是怎么样为每一个用户去创建一个效用函数,因此,用户资料模型很大 程度上是由系统所采用的效用函数决定的。基于效用推荐的好处是它能把非产品的属性,如提供商的可靠性(Vendor Reliability)和产品的可得性(Product Availability)等考虑到效用计算中。

五、基于知识推荐

基于知识的推荐(Knowledge-based Recommendation)在某种程度是可以看成是一种推理(Inference)技术,它不是建立在用户需要和偏好基础上推荐的。基于知识的方法因 它们所用的功能知识不同而有明显区别。效用知识(Functional Knowledge)是一种关于一个项目如何满足某一特定用户的知识,因此能解释需要和推荐的关系,所以用户资料可以是任何能支持推理的知识结构,它可以 是用户已经规范化的查询,也可以是一个更详细的用户需要的表示。

六、组合推荐

由于各种推荐方法都有优缺点,所以在实际中,组合推荐(Hybrid Recommendation)经常被采用。研究和应用最多的是内容推荐和协同过滤推荐的组合。最简单的做法就是分别用基于内容的方法和协同过滤推荐方法 去产生一个推荐预测结果,然后用某方法组合其结果。尽管从理论上有很多种推荐组合方法,但在某一具体问题中并不见得都有效,组合推荐一个最重要原则就是通 过组合后要能避免或弥补各自推荐技术的弱点。

在组合方式上,有研究人员提出了七种组合思路:
1)加权(Weight):加权多种推荐技术结果。
2)变换(Switch):根据问题背景和实际情况或要求决定变换采用不同的推荐技术。
3)混合(Mixed):同时采用多种推荐技术给出多种推荐结果为用户提供参考。
4)特征组合(Feature combination):组合来自不同推荐数据源的特征被另一种推荐算法所采用。
5)层叠(Cascade):先用一种推荐技术产生一种粗糙的推荐结果,第二种推荐技术在此推荐结果的基础上进一步作出更精确的推荐。
6)特征扩充(Feature augmentation):一种技术产生附加的特征信息嵌入到另一种推荐技术的特征输入中。
7)元级别(Meta-level):用一种推荐方法产生的模型作为另一种推荐方法的输入。
七、主要推荐方法的对比

各种推荐方法都有其各自的优点和缺点,见表1。

表1 主要推荐方法对比

推荐方法 优点 缺点
基于内容推荐 推荐结果直观,容易解释;

 

不需要领域知识

新用户问题;

 

复杂属性不好处理;

要有足够数据构造分类器

协同过滤推荐 新异兴趣发现、不需要领域知识;

 

随着时间推移性能提高;

推荐个性化、自动化程度高;

能处理复杂的非结构化对象

稀疏问题;

 

可扩展性问题;

新用户问题;

质量取决于历史数据集;

系统开始时推荐质量差;

基于规则推荐 能发现新兴趣点;

 

不要领域知识

规则抽取难、耗时;

 

产品名同义性问题;

个性化程度低;

基于效用推荐 无冷开始和稀疏问题;

 

对用户偏好变化敏感;

能考虑非产品特性

用户必须输入效用函数;

 

推荐是静态的,灵活性差;

属性重叠问题;

基于知识推荐 能把用户需求映射到产品上;

 

能考虑非产品属性

知识难获得;

 

推荐是静态的

 

 

[原]关于股子系统的优化

2008-6-25 0:18:58 原创 抢沙发(0)

参考:
DiceClass
原作者:
hexagonstar : http://www.hexagonstar.com/
详情:
http://bbs.actionscript3.cn/thread-2044-1-1.html
程序结构:
Dice+ArrayUtil+NumberUtil,全静态类
个人评论:
NumberUtil内数值方面的是最值得借鉴的部分。

由于目前本人Dice 需要应用于DND System中,所以改变了下结构和随机算法(目的在于工厂化生产Dice,以及Dice随机分布算法抽出方便以后采用不同的随机分布算法。)
 

  1. //系统结构伪码  
  2. Dice implements IDice;  
  3. RandomSystem implements IRandomSystem  
  4. Random48 extends RandomSystem;  
  5.  
  6. interface IRandomSystem {  
  7.     function random(min:Number, max:Number):Number;  
  8.     function randomByRound(min:Number, max:Number,round:int):Array;  
  9. }  
  10.  
  11. interface IDice  {  
  12.     function get sided():int;  
  13.     function roll(round:int, randomSystem:IRandomSystem):DiceArrayList;  
  14.     function toString():String   
  15. }  
  16.  
  17. class DiceArrayList extends com.xintend.as3.dnd.core.ArrayCollection {         
  18.     public function DiceArrayList(data:Array ) {              
  19.     }  
  20.           
  21.     public function get average():int {     }  
  22.     public function get max():int {     }  
  23.     public function get min():int {     }  
  24.     public function get sum():int {     }  
  25.           
  26.     protected function verifyInt():void {}  
  27. }  
  28.          

(测试类):
 

  1. package {  
  2.       
  3.     import com.xintend.as3.dnd.base.dice.Dice;  
  4.     import com.xintend.as3.dnd.util.Random48;  
  5.     import com.xintend.as3.dnd.util.RandomSystem;  
  6.     import flash.display.Sprite;  
  7.       
  8.     public class Main extends Sprite    {  
  9.         public function Main(){           
  10.             var d1:Dice = new Dice(4);  
  11.             trace(d1.roll(100,new Random48()))  
  12.             trace(d1.roll(100,new RandomSystem()))  
  13.         }  
  14.     }  

测试图(结构在output窗口):


再次感谢hexagonstar.com开源的DiceClass中的48位线性同余算法

[转]计算机中随机数的产生

2008-6-24 1:49:48 算法 抢沙发(0)

一.计算机中随机数的产生
现在,在计算机,用来产生随机数的算法是"线性同余"法。所谓线性同余,其实就是下面两个式子。假设I就是一个随机数的序列,Ij+1与Ij的关系如下:
Ij+1 =Ij * a+c  (mod m)
或是Ij+1 =Ij *a    (mod m),
其中,不妨取a=16807,m=2147483647,以为一常数。写个简单的程序就是:
long r;

void scand( long v)//初始化随机种子数
{
r = v;
}

long rand()//产生随机数
{
r = (r*a + c)%m;//a,c,m为常数
return r;
}
再看一下稍复杂一点的:(Random () 的 Borland 的实现)
long long RandSeed = #### ;
unsigned long Random(long max)
{
long long x ;
double i ;
unsigned long final ;
x = 0xffffffff;
x += 1 ;
RandSeed *= ((long long)134775813);
RandSeed += 1 ;
RandSeed = RandSeed % x ;
i = ((double)RandSeed) / (double)0xffffffff ;
final = (long) (max * i) ;
return (unsigned long)final;
}
二.计算机产生的随机数不是真的随机数
[引:]我们建立了真正调用伪随机数生成器的 random()。但什么是伪随机数生成器?假定需要生成介于 1 和 10 之间的随机数,每一个数出现的几率都是一样的。理想情况下,应生成 0 到 1 之间的一个值,不考虑以前值,这个范围中的每一个值出现的几率都是一样的,然后再将该值乘以 10。请注意,在 0 和 1 之间有无穷多个值,而计算机不能提供这样的精度。
为了编写代码来实现类似于前面提到的算法,常见情况下,伪随机数生成器生成 0 到 N 之间的一个整数,返回的整数再除以 N。得出的数字总是处于 0 和 1 之间。对生成器随后的调用采用第一次运行产生的整数,并将它传给一个函数,以生成 0 到 N 之间的一个新整数,然后再将新整数除以 N 返回。这意味着,由任何伪随机数生成器返回的数目会受到 0 到 N 之间整数数目的限制。
在大多数的常见随机数发生器中,N 是 232? (大约等于 40 亿),对于 32 位数字来说,这是最大的值。换句话说,我们经常碰到的这类生成器能够至多生成 40 亿个可能值。而这 40 亿个数根本不算大,只是指尖这么大。
伪随机数生成器将作为"种子"的数当作初始整数传给函数。这粒种子会使这个球(生成伪随机数)一直滚下去。伪随机数生成器的结果仅仅是不可预测。由伪随机数生成器返回的每一个值完全由它返回的前一个值所决定(最终,该种子决定了一切)。如果知道用于计算任何一个值的那个整数,那么就可以算出从这个生成器返回的下一个值。
结果,伪随机数生成器是一个生成完全可预料的数列(称为流)的确定性程序。一个编写得很好的的 PRNG 可以创建一个序列,而这个序列的属性与许多真正随机数的序列的属性是一样的。例如:
PRNG 可以以相同几率在一个范围内生成任何数字。
PRNG 可以生成带任何统计分布的流。
由 PRNG 生成的数字流不具备可辨别的模式。
PRNG 所不能做的是不可预测。如果知道种子和算法,就可以很容易地推算出这个序列。

计算机产生的随机数一般都只是一个周期很长的数列,不是真的随机数。也就是说,随机数一般是伪随机数,每个随机数都是由随机种子开始的一个已定的数列(周期很长)。一般地,为了随机数更真一点,随机种子在系统中通常是参照系统时钟生成的。
看看下面这个例子,从中,读者应能有所体会。
main()
{
  int i;
  scand(time(NULL)); /*可向计算机读取其时钟值,并把值自动设为随机数种子*/
  for(i=0;i<10;i++){
    printf("%10d",1+(rand()%6));/*这里1是移动值,他等于所需的连续整数*/
 }              /*数值范围的第一个数;b是比例因子;他*/
 return(0);            /*等于所需的连续整数值的范围宽度;*/
}
从数学上讲,为了得到一个周期性更长的随机序列,我们可以使用如下方法:(这是我在一个书上看到的,详细的情况大家可以查一查,我自己也记不清了,呵呵)
float rand(long* idum)
{
    int j;    long k;    static long iy=0;    static long iv[NTAB];
    float temp;    
    if(*idum<=0||!iy)
    {
        if(-(*idum)<1)            *idum=1;
        else            *idum=-(*idum);
        for(j=NTAB+7;j>=0;j--){
            k=(*idum)/IQ;
            *idum=IA*(*idum-k*IQ)-k*IR;
            if(*idum<0)
                *idum+=IM;
            if(j<NTAB)
                iv[j]=*idum;
        }    iy=iv[0];    }    
    k=(*idum)/IQ;
    *idum=IA*(*idum-k*IQ)-k*IR;
    if(*idum<0)        *idum+=IM;
     j=iy/NDIV;
    iy=iv[j];
    iv[j]=*idum;    
    if((temp=float(AM*iy))>RNMX)        return float(RNMX);
    else         return temp;
}

[注:]有文讲 ,根据Randomize的工作原理,利用函数Timer得到从午夜开始到现在经过的秒数,然后再根据要得到的随机数值大小对该数值进行""衰减"处理,这样得到的数值则可称得上是真正意义的随机数值,我认为,这也是人为的方法,仍有它的确定性和周期性,仍称不上是真正的随机数,单纯改变伪随机数的生成逻辑计算方法并不能达到目的,最有效的办法只能是改变rand_seed,就是种子。而且,改变后的rand_seed不应该是人为的。(注:目前,在 Intel 的PIII处理器中内置了一个与CPU温度相关的随机数生成器,算是一个比较有效的种子生成器。)更好的办法是根据"随机事件"生成随机数,如键盘和鼠标输入值、中断、磁盘读取等等。然而,许多服务器没有键盘和鼠标,许多"黑盒"产品也不带有硬盘,因此很难找到好的随机数源,当然,通讯密钥也就一样不安全。而如网络状态等也不能很好地保证随机数的"随机性"。电器噪声和声音频率也许是很好的随机数源,但大多数人恐怕并不愿意在计算机中增加这种设备,而且也可能出现设备失灵和外部操纵(影响)等问题。对于要处理大量连接的网关服务器,是必须要考虑的问题。如果可以通过,精确检测机器cpu的通电电流强度,来作为随机数种子,或是其他一些没有人为因素的干扰的,且瞬间变化快的方法获得种子,必将能产生符和要求的随机数。

三.几种随机数的获取办法
1.产生一个范围内的随机数
一般地,我们可用j=1+(int)(n*rand()/(RAND_MAX+1.0))来生成一个0到n之间的随机数。
若用int x = rand() % 100;来生成 0 到 100 之间的随机数这种方法是不可取的,比较好的做法是: j=(int)(100.0*rand()/(RAND_MAX+1.0)) ,当然,我们也可是使用random(100)。下面的例子都是用了random(n).
2、筛选型随机数 如希望取0-99的随机数,但不能是6。
解决方法:
x = random(100);
while (x==6) {
x = random(100);
}
又如希望取0-99的随机数,但不要5的倍数 解决方法:
x = random(100);
while ((x % 5)==0) {
x = random(100);
}
3、从连续的一段范围内取随机数。
如从40--50的范围内取随机数。 解决方法: x=random(11)+40
4、从一组乱数中取随机数。 如:从 67, 87, 34, 78, 12, 5, 9, 108, 999, 378十个数中随机取数。 解决方法:可以用数组将些十个数存贮,然后把0--9中取出的随机数作为序号,实现随机取数。
a = new Array(67, 87, 34, 78, 12, 5, 9, 108, 999, 378);
j = random(10);
x = a[j];
四.产生具有一定分布的随机数
关于这点,有一篇文章写得很好,请看:
非均匀分布随机数的产生及其在计算机模拟研究中的应用
作者:胡性本 刘向明 方积乾
单位:胡性本(湖北职工医学院 荆州434000); 刘向明(湖北职工医学院 荆州434000 现为华中理工大学生物工程系博士研究生); 方积乾(湖北职工医学院 荆州434000 中山医科大学)
关键词:非均匀分布随机数;计算机模拟;程序设计
摘 要:非均匀分布随机数在进行计算机模拟研究中有重要作用,但计算机高级语言通常都只提供产生均匀分布随机数的函数,给研究工作带来困难。该文提出的方法,较好地解决了这一问题,有很强的适用性。

中图分类号:O 242.1
文章编号:1004-4337(2000)01-0059-02▲
1 问题的提出
常用的计算机高级程序设计语言,大多提供了产生在[0,1]区间内连续均匀分布的独立随机数r的函数。若将产生的随机数作简单的变换X=a+(b-a)r,就能得到在区间[a,b]上均匀分布的随机数X。如果与取整或舍入函数结合运用,还可得到离散均匀分布的随机数,给计算机模拟提供了方便。但在很多情况下进行计算机模拟需要用到按某些特定规律分布的非均匀随机数。例如,在离子通道门控模型的模拟研究中,就经常要用到服从指数分布、对数分布、正态分布、普畦松分布等非均匀分布的随机数。这时可以在源程序中编写一个函数或过程来产生。我们在近年来所进行的计算机模拟研究工作[1,2]中,大量使用了非均们分布的随机数,获得成功。由于离散随机数可以由连续随机数通过取整或舍入等途径转换而得,本文只侧重介绍非均匀分布连续随机数的产生原理和应用实例,并给出了用类PASCAL语言[3]编写的相应的函数和过程。掌握了任何一种计算机高级语言编程技术和数据结构知识的人,都能很方便地转换成能上机运行的程序,有很大的灵活性与很强的实用性。
2 产生原理
假定连续随机变量X是连续随机变量R的函数
x= (r)                  (1)
由概率统计知识可知,X与R在对应点的分布函数的数值应当相等,即产生R的反变换
F(x)=F(r)                 (2)
其中,r为(1)式的解,即r= -1(x)=Ψ(x)
  在特殊情况下,若R是在[0,1]区间内的均匀分布的连续随机变量,那么R<r的概率P(R<r)=r。此时,(2)式可以简化为
F(x)=F(r)=r                (3)
其反函数
x=F-1(r)                  (4)
具有分布函数F,现予以证明:因为分布函数是单调递增函数,其反函数存在。由概率知识可知,对任意实数X,有
  P(X<x)=P(F-1(R)<x)=P(R<F(x))
  因为R是在[0,1]区间上的均匀分布的连续随机变量,故P(R<F(x))=F(x),即F-1(r)具有分布函数F。
  (4)式表明,要产生一个服从某种分布的随机数,可以先求出其分布函数的反函数的解析式,再将一个在[0,1]区间内的均匀随机数的值代入其中计算就可以了。
3 应用实例
例1 产生密度函数满足指数分布

的随机数,其中α>0。
因为  ,故分布函数为:

由(4)式可得
             (5)
当r为[0,1]区间内的均匀随机数时,1-r也是[0,1]区间内的均匀随机数,故(5)式还可以简化为:
                (6)
假定计算机高级语言已提供了产生在[0,1]区间内均匀分布的随机数的函数RND(0),则根据(6)式可以写出产生服从指数分布的随机数的类PASCAL语言的函数如下:
  FUNC get_exp_random(alpha:real):real;
  {产生服从指数分布的随机数,值参alpha为比例参数}
  get_exp_random=-ln(RND(0))/alpha;
ENDF; {get_exp_random}
  例2 产生服从正态分布的随机数
  正态分布X~N(a,σ)都可以由标准的正态分布X′~N(0,1)经过变换X=a+σX′得到,在此只讨论服从标准正态分布的随机数的产生方法。标准正态分布的密度函数为:
               (7)
但其分布函数不能用有限的解析形式来表示,给转换带来困难,但可以用以下的变换来产生随机数。
  假定r1与r2是[0,1]区间的两个独立的均匀分布随机数,现将其作如下的变换,令
             (8)
再将其反变换为:
              (9)
(9)式中的C为常数。由此可导出其密度函数为:
           (10)
比较(10)式与(7)式,可知X1与X2是两个相互独立的服从正态分布的随机变量,因而(8)式是与(4)相当的据以产生随机数的表达式。由此可以写出产生服从标准正态分布随机数的类PASCAL语言的过程如下:
  PROC gauss(VAR x1,x2:real);
  {产生服从正态分布的随机数对,用变量参数x1与x2传递随机数}
  pi:=3.14159265;  {赋π值}
  r1:=RND(0);  r2:=RND(0);
  s:=SQRT(-2*ln(r1));  {中间变量赋值}
  x1:=s*cos(2*pi*r2);
  x2:=s*sin(2*pi*r2);
  {正态分布随机数赋给变量参数}
ENDP; {gauss}
  此过程每调用一次能产生两个相互正交的标准正态分布随机数。

[原]horidream的水纹效果心得确实很不错

2008-6-13 21:28:53 算法 抢沙发(0)

效果请点击本文章察看内部

原作者:http://www.horidream.com/blog/?p=35#respond

实现代码:

  1. package {  
  2.     import flash.display.Bitmap;  
  3.     import flash.display.BitmapData;  
  4.     import flash.display.BitmapDataChannel;  
  5.     import flash.display.Sprite;  
  6.     import flash.events.TimerEvent;  
  7.     import flash.filters.DisplacementMapFilter;  
  8.     import flash.geom.Point;  
  9.     import flash.utils.Timer;  
  10.       
  11.     /**  
  12.     * ...  
  13.     * @author telds[kingfo]  
  14.     */ 
  15.     public class BitmapWater extends Sprite {  
  16.           
  17.           
  18.         public function BitmapWater() {  
  19.              var renderTimer:Timer;  
  20.                
  21.              var img:Bitmap = new IMG() as Bitmap;  
  22.              var imgH:Number = img.height;  
  23.              var imgW:Number = img.width;  
  24.              var bmd:BitmapData = new BitmapData(imgW, imgW, false, 0);  
  25.                            
  26.               
  27.                
  28.              var baseX:Number = 50;  
  29.              var baseY:Number = 50;  
  30.              var numOctaves:uint = 3;  
  31.              var randomSeed:int = Math.floor(Math.random() * 100000);  
  32.              var stitch:Boolean = true;  
  33.              var fractalNoise:Boolean = true;   
  34.              var channelOptions:uint = BitmapDataChannel.RED;  
  35.              var grayScale:Boolean = false;
  36. //Each of numOctaves 
  37.              var offsets:Array = [new Point()/*one of numOctaves*/];  
  38.               
  39.              addChild(img);  
  40.               
  41.             renderTimer = new Timer(20,0);  
  42.             renderTimer.addEventListener(TimerEvent.TIMER, function Todo(event:TimerEvent):void {  
  43.                 bmd.perlinNoise(baseX, baseY, numOctaves, randomSeed, stitch, fractalNoise, channelOptions, grayScale, offsets);  
  44.                   
  45.                 offsets[0].x = offsets[0].x + 20;  
  46.                 offsets[0].y = offsets[0].y - 20;  
  47.                 img.filters = [new DisplacementMapFilter(bmd, new Point(0, 0), channelOptions, channelOptions, 10, 10)];  
  48.             })  
  49.             renderTimer.start();  
  50.         }  
  51.           
  52.           
  53.           
  54.         [Embed(source = '../bin/123.jpg')]private var IMG:Class;  
  55.           
  56.     }  
  57.       

 

阿基米德螺旋公式

2008-6-12 21:42:42 算法 抢沙发(0)

r=a*θ,求出a,每度半径R=a*2π*(45+n)/360,n=1,2...360

[原]单像素扩增定位

2008-6-3 9:51:57 算法 抢沙发(0)

设物体对象左上角为 O1
某像素点为 A1
缩放后的A2 的位置为  A1*scale
相对中心位移offset (A2-O1)-(A1-O1)
对象相对位移 O2=O1-offset

另外以上式可缩为: O2=O1-A1*(scale -1)

有趣的Script_标准体型自测

2008-5-19 22:37:41 算法 抢沙发(0)

最近上健康咨询网发现的一个so easy的计算公式。。。。随意的摘录下。。。。 

 

JavaScript代码
  1. var Weight=70;   
  2. var Ht=175;   
  3. var difference;   
  4. difference = (Weight)/ ((Ht) * (Ht))*10000;   
  5. alert(difference)  

20以下 低体重
20~<25 正常体重
25~<27 超重
≥27 肥胖

1/1, 7«1»