推荐算法学习笔记
协同过滤推荐算法测评指标RMSE均方根误差
推荐系统笔记：
一、为什么需要推荐系统
为了解决互联网时代下的信息超载问题。
二、搜索引擎和推荐系统的区别
· 分类目录，是将著名网站分门别类，从而方便用户根据类别查找公司。
· 搜索引擎，用户通过输入关键字，查找自己需要的信息。
· 推荐系统，和搜索引擎一样，是一种帮助用户快速发展有用信息的工具。通过分析用户的历史行为，给用户的兴趣建模，从而主动给用户推荐能够满足他们兴趣和需求的信息。并且，推荐系统能够很好的发掘物品的长尾，挑战传统的2/8原则（80%的销售额来自20%的热门品牌）。
三、技术角度来看，搜索引擎和推荐系统的区别
1）搜索引擎，注重搜索结果之间的关系和排序；
2）推荐系统，需要研究用户的兴趣模型，利用社交网络的信息进行个性化的计算；
3）搜索引擎，由用户主导，需要输入关键词，自行选择结果。如果结果不满意，需要修改关键词，再次搜索；
4）推荐系统，由系统主导，根据用户的浏览顺序，引导用户发现自己感兴趣的信息；
四、推荐系统的定义
推荐系统通过发掘用户的行为，找到用户的个性化需求，从而将长尾物品准确推荐给需要它的用户，帮助用户找到他们感兴趣但很难发现的物品。
高质量的推荐系统会使用户对系统产生依赖，因此，推荐系统不仅能为用户提供个性化服务，还能与用户建立长期稳定的关系，提高用户忠诚度，防止用户流失。
五、推荐系统评测
一般推荐系统的参与方有3个：
- 用户
- 物品提供商
- 推荐系统提供网站
因此，评测一个推荐系统时，需要考虑3方的利益，一个好的推荐系统是能够令三方共赢的系统。
六、三个实验方法的优缺点
1）离线实验
离线实验的方法的步骤如下：
a）通过日志系统获得用户行为数据，并按照一定格式生成一个标准的数据集；
b）将数据集按照一定的规则分成训练集和测试集；
c）在训练集上训练用户兴趣模型，在测试集上进行预测；
d）通过事先定义的离线指标，评测算法在测试集上的预测结果。
从以上步骤看出，离线实验的都是在数据集上完成的。意味着，它不需要一个实际的系统作为支撑，只需要有一个从日志中提取的数据集即可。
离线实验的优点是：
不需要有对实际系统的控制权；
不需要用户参与实践；
速度快，可以测试大量算法；
缺点是：
数据集的稀疏性限制了适用范围，例如一个数据集中没有包含某用户的历史行为，则无法评价对该用户的推荐结果；
评价结果的客观性，无法得到用户主观性的评价；
难以找到离线评价指标和在线真实反馈(如 点击率、转化率、点击深度、购买客单价、购买商 品类别等)之间的关联关系；
2）用户调查
用户调查需要一些真实的用户，让他们在需要测试的推荐系统上完成一些任务。在他们完成任务时，需要观察和记录用户的行为，并让他们回答一些问题。
最后，我们通过分析他们的行为和答案，了解测试系统的性能。
用户调查的优点是：
可以获得用户主观感受的指标，出错后容易弥补；
缺点是：
招募测试用户代价较大；
无法组织大规模的测试用户，统计意义不足；
3）在线实验
在完成离线实验和用户调查之后，可以将系统上线做AB测试，将它和旧算法进行比较。
在线实验最常用的评测算法是【A/B测试】，它通过一定的规则将用户随机分成几组，对不同组的用户采用不同的算法，然后通过统计不同组的评测指标，比较不同算法的好坏。
它的核心思想是:
a) 多个方案并行测试;
b) 每个方案只有一个变量不同;
c) 以某种规则优胜劣汰。
其中第2点暗示了A/B 测试的应用范围：A/B测试必须是单变量。
对于推荐系统的评价中，唯一变量就是–推荐算法。
AB测试的优点是：
可以公平获得不同算法实际在线时的性能指标，包括商业上关注的指标；
缺点是：
周期较长，必须进行长期的实验才能得到可靠的结果；
大型网站做AB测试，可能会因为不同团队同时进行各种测试对结果造成干扰，所以切分流量是AB测试中的关键。
不同的层以及控制这些层的团队，需要从一个统一的地方获得自己AB测试的流量，而不同层之间的流量应该是正交的。
总结：一般来说，一个新的推荐算法最终上线，需要完成上述的3个实验。
- 首先，通过离线实验证明它在很多离线指标上优于现有的算法；
- 其次，通过用户调查确定用户满意度不低于现有的算法；
- 最后，通过在线AB测试确定它在我们关心的指标上优于现有的算法；
关于均方根误差（RMSE）：
RMSE是一个重要的预测评分的准确度指标，所谓预测评分的准确度衡量的是算法评测的评分与用户的实际评分之间的贴合度
RMSE越小表示误差越小，推荐系统的性能就越好
其中的平方根是RMSE加大了对预测不准的用户物品评分的惩罚（平方项的惩罚），因而对系统的评测更加苛刻。但是要注意研究表明，如果评分系统是基于整数建立的（即用户给的评分都是整数），那么对预测结果取整数会降低MAE的误差。
项目代码
一、实现原理和步骤
1、使用movielens数据集（943个用户，1682部电影，80000条评分数据）；
2、构建用户-电影评分矩阵；
二维矩阵，横坐标为943的用户的id，纵坐标为1682部电影的id，其中在用户打过分 的电影的下方标出对应的分数。
3、数据统计分析，可以直观地打印出比如电影的评分分布情况，可以明显的看出打高分的 数量和打低分的数量。
4、输入用户id（1-943）；
5、基于用户的协同过滤推荐算法；
1、根据用户历史行为信息构建用户-项目评分矩阵，用户历史行为信息包括项目评分、浏览历史、收藏历史、喜好标签等，本项目以单一的项目评分为例
2、根据用户-项目评分矩阵计算用户之间的相似度。计算相似度常用的方法有余弦算法、修正余弦算法、皮尔森算法等等，该项目为余弦算法。
3、根据用户之间的相似度得到目标用户的最近邻居KNN。KNN的筛选常用的有两种方式，一种是设置相似度阀值（给定一个相似度的下限，大于下限的相似度为最近邻居），一种是根据与目标用户相似度的高低来选择前N个最近邻居（本项目以前N个为例）。相似度排序可用经典冒泡排序法。
4、预测项目评分并进行推荐。
6、计算推荐算法测评指标rmse值。
7、冷启动推荐（扩展，暂未实现）；
在该推荐系统中用所拥有的用户-电影-评分数据集进行训练测试所产生的一个推荐算法进行一个冷启动推荐，冷启动推荐的场景分别为刚注册的新用户在没有用户使用系统历史数据的情况下进行一个合适的推荐，和刚刚上线一个新电影的时候在没有用户观看记录数据的情况下将该电影推荐给可能对该电影感兴趣的用户。
二、代码实现
项目目录：
Application：算法主运行算法
Base：基础常量接口
ComputeSimilarity：比较两个用户相似度的类
GetScore：获取预测评分
PearsonCorrelation:余弦算法/皮尔森算法
ProduceSimilarityMatrix：得到用户相似度矩阵
ReadFile：读取movielens
u1.base：训练集
ui.test：测试集
Application：
import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.Scanner; import java.util.Set; /** * 协同过滤推荐算法运行主方法 * @author line * */ public class Application implements Base { public static void main(String[] args) { // 输入userId，并获取 System.out.println("请输入一个用户Id（1、2、3……943）"); Scanner scanner = new Scanner(System.in); //获取得到输入的userId int userId = scanner.nextInt(); // 从文件中读取数据 int[][] user_movie_base = new int[PREFROWCOUNT][COLUMNCOUNT]; //读取文件中的数据 user_movie_base = new ReadFile().readFile(BASE); //产生相似度矩阵 double[] similarityMatrix = new ProduceSimilarityMatrix().produceSimilarityMatrix(user_movie_base, userId); // 知道每个用户之间的相似度值之后，开始获取每隔相似值对应的userId，然后和相似值关联，再根据相似值排序，即得到相似爱好的userId，然后再输出相似推荐的商品 int[] id = new int[KNEIGHBOUR];//存放K个最近邻userId //产生一个临时相似度矩阵变量，是为了相似度排序时和userid对应 double[] tempSimilarity = new double[similarityMatrix.length]; for (int j = 0; j < tempSimilarity.length; j++) { tempSimilarity[j] = similarityMatrix[j]; } Arrays.sort(tempSimilarity);//排序，升序 int flag = 0;//临时变量 double[] similarity = new double[KNEIGHBOUR];//保存前K个相似度，从大到小 for (int m = tempSimilarity.length - 1; m >= tempSimilarity.length - KNEIGHBOUR; m--) { for(int j = 0; j < similarityMatrix.length; j++) { if (similarityMatrix[j] == tempSimilarity[m] && similarityMatrix[j] != 0.0){ similarity[flag] = tempSimilarity[m]; id[flag]=j;//保存前K个相似度的userid flag++; } } } System.out.println("相似度最近的" + KNEIGHBOUR + "个用户是："); System.out.print("近邻用户"); System.out.printf("%25s","相似度");//格式化输出"%25s"是占多少位 System.out.printf("%30s\n","推荐产品"); Map<Integer, Double> map = new HashMap<Integer, Double>();//存放每件商品的id和期望值，是键值对关系，即一对一 for (int i = 0; i < KNEIGHBOUR; i++) {//按照k值得大小来循环 // 前k个近邻用户的推荐产品 int user_id = id[i];//数组id中的userid根据相似度大小顺序已经排好，从大到小 int[] items = user_movie_base[user_id];// 获取源数据K个邻近用户userid的所有评分 String str = ""; for (int j = 0; j < COLUMNCOUNT; j++) {//循环每件商品，如果相邻用户对某件商品的评分不为0，而目标用户的评分为0，该商品就为推荐商品 if ((items[j] != 0) && (user_movie_base[userId - 1][j] == 0)){ str += " " + (j + 1);//将推荐商品的id保存在一个字符串中，可以直接输出 //此时，可以通过循环计算某一件推荐商品的评分用户的相似度期望 //开始计算期望，将相同商品的相似度相加，并保存在map集合中 if(map.containsKey(j + 1)){//如果一件商品的值，已经保存在map集合的键中（键是唯一的，即不会和其他的数值一样），那么键对应的值，就会改变，加上该商品不用用户的相似度 double d = map.get(j+1); d+=similarity[i]; map.put(j+1,d);//修改map中的值 }else{ map.put(j+1, similarity[i]);//如果没有保存一件商品的id，那么开始保存 } } } System.out.print(id[i] + 1); System.out.printf("%16s\t" ,String.format("%.2f",similarity[i]*100)+"%");//输出的同时格式化数据 System.out.println(str);//输出每个用户的推荐商品 } //选择最好的推荐商品,期望加权 //循环map集合的键 Map<Integer,Double> map2 = new HashMap<Integer, Double>(); //保存商品id和加权期望,因为还要对加权期望排序，要和商品id对应 double s1 = 0; double s2 = 0; Set<Integer> set = map.keySet();//获取map集合中的所有键，输出是一个set集合 for(int key : set){//循环map中的所有键 for (int i = 0; i < KNEIGHBOUR; i++) { int score = user_movie_base[id[i]][key-1];//map中的键是商品id，i是userid，获取评分 s1+=score*map.get(key); s2+=score; } map2.put(key, s1/s2);//保存加权期望值，和商品id对应 } Object[] arr = map2.values().toArray();//获取map2中所有的值，也就是每件商品的加权期望 Arrays.sort(arr);//升序排列，调用系统数据包中的函数，自动排列数组 set = map2.keySet();//获取商品id int max=0;//最佳推荐项目id for(int key : set){//循环商品id，根据最大的加权期望，找到商品id if(map2.get(key)==arr[arr.length-1]){ max = key; break; } } System.out.println("最值得推荐的商品是："+max); // 误差率 int[][] test = new ReadFile().readFile(TEST); // 462个用户的实际评分 double[][] similarityMatrix2 = new ProduceSimilarityMatrix().produceSimilarityMatrix(user_movie_base);//获取任意两行之间的相似度矩阵 double[][] matrix = new GetScore().getScore(user_movie_base,similarityMatrix2); double[] mae = new ProduceMAE().produceMAE(matrix, test); double Mae = 0.0, MAE = 0.0;//平均绝对误差，通过两大组数据的相似度矩阵对比而来 for (int k = 0; k < mae.length; k++) { Mae += mae[k]; } MAE = Mae / TESTROWCOUNT; System.out.println("MAE=:" + MAE); double RMSE=new ProduceMSE().produceMSE(matrix,test); System.out.println("MSE=:" + RMSE); } }
Base
/** * 基础静态文件数据 * @author line * */ public interface Base { public static final int KNEIGHBOUR = 10; //number of neighbors最近邻个数 public static final int COLUMNCOUNT = 1682; //number of items 项目总数 public static final int PREFROWCOUNT = 943; //number of users in base训练集上的用户数目 public static final int TESTROWCOUNT = 462; //number of users in test测试集上的用户数目 public static final String BASE = "./ml-100k/u1.base";//训练集 public static final int BASE_LINE = 80000;//base数据集的行数 public static final String TEST = "./ml-100k/u1.test";//测试集 public static final int TEST_LINE = 20000;//test数据集的行数 public static final String BASE_GENRE = "./ml-100k/u.user";//用户属性集 public static final String BASE_ITEMS_GENRE = "./ml-100k/u.item";//用户属性集 public static final int ITEMS_GENRE_LINE = 19;//test数据集的行数 }
ComputeSimilarity
import java.util.ArrayList; import java.util.List; /** * 从两行数据中，获取需要对比的要求数据 * @author line * */ public class ComputeSimilarity { public double computeSimilarity(int[] item1,int[] item2) { List<Integer> list1 = new ArrayList<Integer>();//因为不知道两行userid的评分是否有效即都不为0，所以定义集合来储存不知道的有效评分 List<Integer> list2 = new ArrayList<Integer>(); for (int i = 0; i < item1.length; i++) { if(item1[i] != 0 || item2[i] !=0) {//如果相同列上有0就舍去 list1.add(new Integer(item1[i]));//因为合格数据个数不确定，所以用集合表示 list2.add(new Integer(item2[i])); } } return new PearsonCorrelation().pearsonCorrelation(list1,list2);//返回相似度值 } }
