《推荐系统技术预研报告(共24页).doc》由会员分享，可在线阅读，更多相关《推荐系统技术预研报告(共24页).doc（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上Mahout技术预研报告版本：V1.0文 档 编 号保 密 等 级作 者最后修改日期审 核 人最后审批日期批 准 人最后批准日期修订记录日期版本修订说明修订人2011-5-31V1.0创建专心-专注-专业目 录1 简介1.1 编写目的通过对Apache Mahout开源框架和推荐系统相关技术的学习，归纳出推荐系统领域目前的主要相关算法以及这些算法的应用场景及优缺点，为后续“金融产品推荐”产品提供理论支持和技术储备。1.2 背景1.2.1 任务的提出。1.2.2 使用者 金融产品推荐项目组开发者。 1.3 参考资料参考资料主要来源于互联网和相关算法的论文。2 协同过滤机
2、制分析2.1 基于协同过滤的推荐机制基本原理协同过滤是利用集体智慧的一个典型方法。协同过滤的核心思想是我们一般更倾向于从口味比较类似的朋友那里得到推荐。协同过滤一般是在海量的用户中发掘出一小部分和你品位比较类似的，在协同过滤中，这些用户成为邻居，然后根据他们喜欢的其他东西组织成一个排序的目录作为推荐给你。要实现协同过滤，需要以下几个步骤 ：l 收集用户偏好 l 找到相似的用户或物品 （计算相似度）l 计算推荐列表下面介绍mahout实现的的三种协同过滤推荐机制。2.2 基于用户的协同过滤推荐 1. 基本原理说明基于用户的协同过滤推荐的基本原理是，根据所有用户对物品或者信息的偏好，发现与当前用户
3、口味和偏好相似的“邻居”用户群，在一般的应用中是采用计算“K- 邻居”的算法；然后，基于这 K 个邻居的历史偏好信息，为当前用户进行推荐。下图给出了原理图。 基于用户的协同过滤推荐机制的基本原理上图示意出基于用户的协同过滤推荐机制的基本原理，假设用户A喜欢物品A，物品C，用户B喜欢物品B，用户C喜欢物品A ，物品C和物品D；从这些用户的历史喜好信息中，我们可以发现用户A和用户C的口味和偏好是比较类似的，同时用户C还喜欢物品D，那么我们可以推断用户A可能也喜欢物品 D，因此可以将物品D推荐给用户A。 基于用户的协同过滤推荐机制和基于人口统计学的推荐机制都是计算用户的相似度，并基于“邻居”用户群计
4、算推荐，但它们所不同的是如何计算用户的相似度，基于人口统计学的机制只考虑用户本身的特征，而基于用户的协同过滤机制可是在用户的历史偏好的数据上计算用户的相似度，它的基本假设是，喜欢类似物品的用户可能有相同或者相似的口味和偏好。 2. 基于mahout实现基于用户的协同过滤推荐给出示例代码如下：DataModel model = new FileDataModel(new File(preferences.dat); UserSimilarity similarity = new PearsonCorrelationSimilarity(model); UserNeighborhood neigh
5、borhood = new NearestNUserNeighborhood(100, similarity, model); Recommender recommender = new GenericUserBasedRecommender(model, neighborhood, similarity);2.3 基于项目的协同过滤推荐 1. 基本原理说明基于项目的协同过滤推荐的基本原理也是类似的，只是说它使用所有用户对物品或者信息的偏好，发现物品和物品之间的相似度，然后根据用户的历史偏好信息，将类似的物品推荐给用户，下图诠释了它的基本原理。 基于项目的协同过滤推荐机制的基本原理假设用户A喜
6、欢物品A和物品C，用户B喜欢物品A，物品B和物品C，用户C喜欢物品A，从这些用户的历史喜好可以分析出物品A和物品C时比较类似的，喜欢物品A的人都喜欢物品C，基于这个数据可以推断用户C很有可能也喜欢物品C，所以系统会将物品C推荐给用户C。基于项目的协同过滤推荐和基于内容的推荐其实都是基于物品相似度预测推荐，只是相似度计算的方法不一样，前者是从用户历史的偏好推断，而后者是基于物品本身的属性特征信息。 2. 基于mahout实现基于项目的协同过滤推荐给出示例代码如下：DataModel model = new FileDataModel(new File(preferences.dat); Item
7、Similarity similarity = new PearsonCorrelationSimilarity(model); Recommender recommender = new GenericItemBasedRecommender(model, similarity);2.4 Slope One协同过滤推荐1. 基本原理说明User CF 和 Item CF 是最常用最容易理解的两种 CF 的推荐策略，但在大数据量时，它们的计算量会很大，从而导致推荐效率较差。因此 Mahout 还提供了一种更加轻量级的 CF 推荐策略：Slope One。 Slope One 是有 Daniel
8、 Lemire 和 Anna Maclachlan 在 2005 年提出的一种对基于评分的协同过滤推荐引擎的改进方法，下面介绍一下它的基本思想。 上图给出了例子，假设系统对于物品 A，物品 B 和物品 C 的平均评分分别是 3，4 和 4。基于 Slope One 的方法会得到以下规律： l 用户对物品 B 的评分 = 用户对物品 A 的评分 + 1 l 用户对物品 B 的评分 = 用户对物品 C 的评分 基于以上的规律，我们可以对用户 A 和用户 B 的打分进行预测： l 对用户 A，他给物品 A 打分 4，那么我们可以推测他对物品 B 的评分是 5，对物品 C 的打分也是 5。 l 对用户
9、 B，他给物品 A 打分 2，给物品 C 打分 4，根据第一条规律，我们可以推断他对物品 B 的评分是 3；而根据第二条规律，推断出评分是 4。当出现冲突时，我们可以对各种规则得到的推断进行就平均，所以给出的推断是 3.5。 这就是 Slope One 推荐的基本原理，它将用户的评分之间的关系看作简单的线性关系。2. 基于mahout实现Slope One下面给出代码示例：DiffStorage diffStorage = new MemoryDiffStorage(model, Weighting.UNWEIGHTED, false, Long.MAX_VALUE); Recommender
10、 recommender = new SlopeOneRecommender(model, Weighting.UNWEIGHTED, Weighting.UNWEIGHTED, diffStorage); /Database-based Recommender AbstractJDBCDataModel model = new MySQLJDBCDataModel(); DiffStorage diffStorage = new MySQLJDBCDiffStorage(model); Recommender recommender = new SlopeOneRecommender(mod
11、el, Weighting.WEIGHTED, Weighting.WEIGHTED, diffStorage);2.5 协同过滤各种算法比较基于项目的协同过滤推荐机制是 Amazon 在基于用户的机制上改良的一种策略，因为在大部分的 Web 站点中，物品的个数是远远小于用户的数量的，而且物品的个数和相似度相对比较稳定，同时基于项目的机制比基于用户的实时性更好一些。但也不是所有的场景都是这样的情况，可以设想一下在一些新闻推荐系统中，也许物品，也就是新闻的个数可能大于用户的个数，而且新闻的更新程度也有很快，所以它的形似度依然不稳定。但在大数据量时，基于项目的协同过滤和基于用户的协同过滤计算量会很
12、大，从而导致推荐效率较差。所以，其实可以看出，推荐策略的选择其实和具体的应用场景有很大的关系。3 相似度的计算关于相似度的计算，现有的几种基本方法都是基于向量（Vector）的，其实也就是计算两个向量的距离，距离越近相似度越大。在推荐的场景中，在用 户 - 物品偏好的二维矩阵中，我们可以将一个用户对所有物品的偏好作为一个向量来计算用户之间的相似度，或者将所有用户对某个物品的偏好作为一个向量来计算物品 之间的相似度。下面我们详细介绍几种常用的相似度计算方法：3.1 皮尔逊相关系数（Pearson Correlation Coefficient）皮尔逊相关系数一般用于计算两个定距变量间联系的紧密程
13、度，它的取值在 -1，+1 之间。Sx, Sy是 x 和 y 的样品标准偏差。原理：用来反映两个变量线性相关程度的统计量 范围：-1,1，绝对值越大，说明相关性越强，负相关对于推荐的意义小。 基于皮尔森相关系数的相似度有以下缺点：l 没有考虑用户间重叠的评分项数量对相似度的影响；（共同评分项的数量）l 如果两个用户之间只有一个共同的评分项，相似度也不能被计算。l 如果重叠的值都相等，也无法计算相似性（标准差为0，做除数）。3.2 欧几里德距离（Euclidean Distance）最初用于计算欧几里德空间中两个点的距离，假设 x，y 是 n 维空间的两个点，它们之间的欧几里德距离是：可以看出，
14、当 n=2 时，欧几里德距离就是平面上两个点的距离。当用欧几里德距离表示相似度，一般采用以下公式进行转换：距离越小，相似度越大。原理：利用欧式距离d定义的相似度s，s=1 / (1+d)。 范围：0,1，值越大，说明d越小，也就是距离越近，则相似度越大。 说明：同皮尔森相似度一样，该相似度也没有考虑重叠数对结果的影响.只要至少有一个共同评分项，就能用欧几里德距离计算相似度；如果没有共同评分项，那么欧几里德距离也就失去了作用。3.3 Cosine 相似度（Cosine Similarity）Cosine 相似度被广泛应用于计算文档数据的相似度：原理：多维空间两点与所设定的点形成夹角的余弦值。 范
15、围：-1,1，值越大，说明夹角越大，两点相距就越远，相似度就越小。 余弦相似度的特点：只关注共同评分的项目l 对用户的绝对的数值不敏感l 计算时不考虑用户之间的共同评分项数量，即使仅仅有极少相同评分项，也有可能获得很大的相似度结果l 只要各个评分项之间越趋向于对应成比例，而不论数值差异如何，则相似度越趋近于1.000.欧式距离和余弦相似性的比较根据欧氏距离和余弦相似度各自的计算方式和衡量特征，分别适用于不同的数据分析模型：欧氏距离能够体现个体数值特征的绝对差异，所以更多的用于需要从维度的数值大小中体现差异的分析，如使用用户行为指标分析用户价值的相似度或差异；而余弦相似度更多的是从方向上区分差异
16、，而对绝对的数值不敏感，更多的用于使用用户对内容评分来区分用兴趣的相似度和差异，同时修正了用户间可能存在的度量标准不统一的问题（因为余弦相似度对绝对数值不敏感）。3.4 修正的余弦相似性在余弦相似度的介绍中说到：余弦相似度更多的是从方向上区分差异，而对绝对的数值不敏感。因此没法衡量每个维数值的差异，会导致这样一个情况：比如用户对内容评分，5分制，X和Y两个用户对两个内容的评分分别为(1,2)和(4,5)，使用余弦相似度得出的结果是0.98，两者极为相似，但从评分上看X似乎不喜欢这两个内容，而Y比较喜欢，余弦相似度对数值的不敏感导致了结果的误差，需要修正这种不合理性，就出现了调整余弦相似度，即所
17、有维度上的数值都减去一个均值，比如X和Y的评分均值都是3，那么调整后为(-2,-1)和(1,2)，再用余弦相似度计算，得到-0.8，相似度为负值并且差异不小，但显然更加符合现实。3.5 Spearman秩相关系数-Spearman Correlation原理：Spearman秩相关系数通常被认为是排列后的变量之间的Pearson线性相关系数。 范围：-1.0,1.0，当一致时为1.0，不一致时为-1.0。 说明：计算非常慢，有大量排序。针对推荐系统中的数据集来讲，用Spearman秩相关系数作为相似度量是不合适的。3.6 Tanimoto 系数（Tanimoto Coefficient）Tan
18、imoto 系数不关心用户对物品的具体评分值是多少，它关心用户与物品之间是否存在关联关系。Tanimoto 系数依赖于用户和物品之间的这种Boolean关系作为输入。更准确的说法为：Tanimoto 系数主要用于计算符号度量或布尔值度量的个体间的相似度，因为个体的特征属性都是由符号度量或者布尔值标识，因此无法衡量差异具体值的大小，只能获得“是否相同”这个结果，所以Tanimoto 系数只关心个体间共同具有的特征是否一致这个问题。Tanimoto 系数又被叫做Jaccard 系数，其值等于两个用户共同关联（不管喜欢还是不喜欢）的物品数量除于两个用户分别关联的所有物品数量。也就是关联的交集除于关联
19、的并集，用公式表示为：其值介于0, 1之间，如果两个用户关联的物品完全相同，交集等于并集，值为1；如果没有任何关联，交集为空，值为0。Tanimoto 系数多用于计算文档数据的相似度：原理：是对Jaccard系数的扩展，等式为 范围：0,1，完全重叠时为1，无重叠项时为0，越接近1说明越相似。 说明：处理无打分的偏好数据。3.7 对数似然相似度原理：重叠的个数，不重叠的个数，都没有的个数 说明：处理无打分的偏好数据，比Tanimoto系数的计算方法更为智能。3.8 曼哈顿距离原理：曼哈顿距离的实现，同欧式距离相似，都是用于多维数据空间距离的测度 范围：0,1，同欧式距离一致，值越小，说明距离值
20、越大，相似度越大。 说明：比欧式距离计算量少，性能相对高。4 降维算法分析4.1 主成分分析主成分分析将多个变量通过线性变换以选出较少个数重要变量的一种多元统计分析方法。又称主分量分析。在用统计分析方法研究多变量的课题时，变量个数太多就会增加课题的复杂性。人们自然希望变量个数较少而得到的信息较多。在很多情形，变量之间是有一定的相关关系的，当两个变量之间有一定相关关系时，可以解释为这两个变量反映此课题的信息有一定的重叠。主成分分析是对于原先提出的所有变量，建立尽可能少的新变量，使得这些新变量是两两不相关的，而且这些新变量在反映课题的信息方面尽可能保持原有的信息。算法原理：主成分分析所要做的就是设
21、法将原来众多具有一定相关性的变量，重新组合为一组新的相互无关的综合变量来代替原来变量。通常，数学上的处理方法就是将原来的变量做线性组合，作为新的综合变量，但是这种组合如果不加以限制，则可以有很多，应该如何选择呢？如果将选取的第一个线性组合即第一个综合变量记为，自然希望它尽可能多地反映原来变量的信息，这里“信息”用方差来测量，即希望越大，表示包含的信息越多。因此在所有的线性组合中所选取的应该是方差最大的，故称为第一主成分。如果第一主成分不足以代表原来个变量的信息，再考虑选取即第二个线性组合，为了有效地反映原来信息，已有的信息就不需要再出现在中，用数学语言表达就是要求=0，称为第二主成分，依此类推
22、可以构造出第三、四第个主成分。说明：主成分分析是采取一种数学降维的方法，找出几个综合变量来代替原来众多的变量，使这些综合变量能尽可能地代表原来变量的信息量，而且彼此之间互不相关。在推荐引擎中主要用来降维大规模的用户物品矩阵。4.2 奇异值分解奇异值分解是一种矩阵分解技术，可将一个矩阵R分解成为3个矩阵的乘积，即R=TSD，S=diag(s1,s2,s3,sr)，其中，s1=s2=s3=sr，T和D分别为两个正交矩阵，r是矩阵R的秩，S是一个对角矩阵，所有的si按照大小顺序排列，称为奇异值。奇异值分解有一个优点，它允许存在一个简化的近似矩阵。对于S，保留k个最大的奇异值，将其余的用0来代替，这样
23、，我们就可以将S简化为仅有k个奇异值的矩阵（kP(Cj|X) 1jm，ji根据贝叶斯定理由于P(X)对于所有类为常数，最大化后验概率P(Ci|X)可转化为最大化先验概率P(X|Ci)P(Ci)。如果训练数据集有许多属性和元组，计算P(X|Ci)的开销可能非常大，为此，通常假设各属性的取值互相独立，这样先验概率P(x1|Ci)，P(x2|Ci)，P(xn|Ci)可以从训练数据集求得。根据此方法，对一个未知类别的样本X，可以先分别计算出X属于每一个类别Ci的概率P(X|Ci)P(Ci)，然后选择其中概率最大的类别作为其类别。2. 优缺点优点：l 适用于训练数据集较大（远远大于逻辑回归）的情况。l
24、支持并行计算缺点：l 只适用于特性值为文本的情况（如文档分类，垃圾邮件判断等），l 前提是各属性之间互相独立。当数据集满足这种独立性假设时,分类的准确度较高，否则可能较低。另外，该算法没有分类规则输出。7.2.3 SVM（支持向量机）1. 工作原理支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力（泛化能力）。它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问
25、题中。2. 优缺点优点：l 不涉及概率测度及大数定律，避开了从归纳到演绎的传统过程,实现了高效的从训练样本到预报样本的“转导推理”,大大简化了通常的分类和回归等问题l SVM 的最终决策函数只由少数的支持向量所确定,计算的复杂性取决于支持向量的数目,而不是样本空间的维数,这在某种意义上避免了“维数灾难”。l 少数支持向量决定了最终结果,这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本l 不需要大量的训练样本，可以解决非线性的问题缺点：l SVM算法对大规模训练样本难以实施，由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存
26、储和计算，将耗费大量的机器内存和运算时间。l 用SVM解决多分类问题存在困难，经典的支持向量机算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。7.2.4 神经网络1. 工作原理人工神经网络是由大量的简单基本元件神经元相互联接而成的自适应非线性动态系统。每个神经元的结构和功能比较简单，但大量神经元组合产生的系统行为却非常复杂。 人工神经网络反映了人脑功能的若干基本特性，但并非生物系统的逼真描述，只是某种模仿、简化和抽象。与数字计算机比较，人工神经网络在构成原理和功能特点等方面更加接近人脑，它不是按给定的程序一步一步地执行运算
27、，而是能够自身适应环境、总结规律、完成某种运算、识别或过程控制。人工神经网络首先要以一定的学习准则（如果网络做出错误的判决，则通过网络的学习，应使得网络减少下次犯同样错误的可能性。）进行学习，然后才能工作。一般说来，网络中所含的神经元个数越多，则它能记忆、识别的模式也就越多。2. 优缺点l 自学习性较强，多用于分类。l 网络内的神经元按规则相互连接，信息在个神经元内是等势分布的，整个网络都会参与到对信息的处理，即使有部分神经元失效，网络仍能继续运作，有很强的容错性和鲁棒性。l 并行协同处理特性，随着计算机技术的发展，从而可以更快速的进行大量运算。l 联想式记忆功能，神经网络的运作依赖内部所有神
28、经元之间的相互连接和作用，这类似于大脑的发散性思维，使网络具有非局限性。l 自学习、自组织、自适应能力，可以处理位置系统，使网络具有很好的预测功能。l 解决优化问题，可以快速找到优化解。通常处理很费时间和需要大量计算的复杂问题时使用神经网络算法。7.2.5 HMM (隐马尔科夫模型)1. 工作原理HMM实质上就是隐藏了状态的马尔科夫模型，模型状态不能直接可见，只能观察到由状态到符号的映射过程所产生的观察值序列，是一个双重随机过程：一重是马尔科夫模型的概率状态转移过程，另一重是从底层状态到表层观察值的随机过程。它能够解决三个问题l 评估：对于一个给定的HMM其生成一个给定的观察序列的概率是多少，
29、前向算法可以有效的解决此问题；l 解码：什么样的隐藏状态序列最有可能生成一个给定的观察序列，Viterbi算法可以有效的解决此问题；l 学习：对于一个给定的观察序列样本，什么样的HMM最可能生成该序列也就是确定HMM的参数，这个问题可以使用Baum-Welch或是EM算法解决。注：mahout中分类器中使用到了HMM，用HMM的评估这部分2. 优缺点优点：l 算法成熟、高效l 拥有结实的统计学基础l 模型灵活、通用缺点：l 算法训练样本数据大l 初始值对结果的影响较大l 马尔科夫的假设在现实中并不一定成立7.2.6 决策树1. 工作原理一般都是自上而下的来生成的。每个或事件（即自然状态）都可能引出两个或多个事件，导致不同的结果，把这种决策分支画成图形很像一棵树的枝干，故称决策树。2. 优缺点优点： l 可生成可以理解的规则； l 计算量相对来说不是很大； l 可以处理连续和种类字段； l 决策树可以清晰的显示哪些字段比较重要。 缺点： l 对连续性的字段比较难； l 对有时间顺序的数据，需要很多预处理的工作； l 当类别太多时，错误可能就会增加的比较快； l 一般的算法分类的时候，只是根据一个字段来分类。