基于常数复杂度距离函数的推荐算法研究

作     者：郑梅 

作者单位：西南石油大学 

学位级别：硕士

导师姓名：陈汶滨

授予年度：2017年

学科分类：08[工学] 081203[工学-计算机应用技术] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：距离函数 邻居 时间复杂度 推荐系统 

摘      要：推荐系统是指通过分析用户的历史行为,主动给用户推荐他们可能感兴趣的信息。它能够大大缩短用户筛选信息的时间,从而被广泛应用于电子商务,电影视频网络,社交网络等领域。推荐系统的研究方法有很多,其中应用最广泛的是协同过滤推荐算法。该算法的核心思想是寻找与目标兴趣爱好相似的对象作为样本的邻居,然后通过分析其邻居的行为来预测目标的行为。现有大量距离度量函数可以用来确定目标的邻居,例如余弦相似度,Pearson相关系数,欧几里得距离等。但这些距离度量函数的计算过程均比较复杂,当数据规模较大时,距离的计算会非常耗时。本文提出了一个以平均距离为核心的协同过滤推荐算法MBR（M-distance based recommend）。该算法首先定义了一个新的距离函数M-distance,该函数的复杂度仅有常数级。M-distance将对象与样本之间的平均评分差作为二者之间的距离,当已知对象与样本的平均评分后,计算二者距离的时间复杂度仅为O（1）。其次提出了以半径5来寻找邻居的方法。在计算出对象间的距离后,kNN算法将距离样本最近的k个对象作为样本的邻居,但是这样预先设定好邻居数量的方法不够灵活。而以半径来寻找邻居是通过样本的平均评分和δ先确定出样本的邻居域,当对象与样本的距离在这个邻居域范围内时,我们就将该对象作为待选邻居。通过这样的方法来选择邻居,邻居数量的多少完全取决于对象与样本之间的相似程度,相似度越高,选择出来的邻居就越多,预测也就越准确。然后定义了评分预测方法。当选择出样本的所有邻居后,就可以根据用户对邻居的行为来预测用户对样本的行为。当有邻居时,将邻居的平均评分作为样本的最终预测值,而没有邻居时将用户对样本的平均评分值作为最终的预测值。最后在MBR推荐算法的基础上继续定义了一个推荐阈值（threshold）。当MBR算法计算出的预测值大于推荐阈值时,就将样本推荐给用户,反之不推荐。threshold主要由误推荐率和误推荐代价两者共同决定。本文选取了四个常用的公开数据集:MovieLens,DouBan,EachMovie,Netflix来进行试验。主要比较了 MBR推荐算法与kNN,Slope One算法在运行效率和预测精确上的优劣。通过大量的实验可知MBR推荐算法在保证了精确度的前提下大大提高了推荐效率,特别是在大型数据集上表现更为突出。而最优的门限值一般在3.4与3.5之间产生。