第二章
推荐系统的数据挖掘方法
Xavier Amatriain, Alejandro Jaimes, Nuria Oliver和Josep M. Pujol
在本章的摘要中，我们概述了在推荐系统的环境下所使用的主要的数据挖掘技术。我们首先来描述一下通用的预处理技术例如：采样或维数约简等方法。接下来，我们回顾了最重要的一些分类技术，包括贝叶斯网络和支持向量机。我们描述了K-means聚类算法并讨论了一些其他可供选择的算法。我们还提出了一个有效的训练过程的关联规则和相关算法。除了介绍这些技术以外，我们调研了它们在推荐系统中的使用情况以及展示了一些成功应用的实例。
2.1 介绍
推荐系统（RS）通常应用其他相近领域的技术和方法——例如人机交互（HCI）或是信息检索（IR）。然而，大部分的这些系统的核心中都具有一种可以理解为数据挖掘（DM）技术的一种特殊实例的算法。
数据挖掘的步骤通常由3个连续开展的步骤组成：数据预处理，数据分析和结果分析（见图2.1）。我们将在2.2节分析一些最重要的数据预处理方法。特别是，由于它们在推荐系统中扮演了重要角色，我们将重点放在采样和维数约简和距离函数的使用上。在第2.3节至第2.5节中，我们给出了一个在推荐系统中最常用的数据挖掘算法：分类，聚类和关联规则挖掘（本章所涉及的不同主题的详细视图如图2.1）的概述介绍。
图2.1 在一个数据挖掘问题中的主要步骤和方法，以及
它们与章节的对应关系。
本章不打算给出一个关于数据挖掘方法详细的回顾，而是强调数据挖掘算法在推荐系统领域的影响，并提供了一个关于数据挖掘核心技术成功使用的概述。我们将引导感兴趣的读者去阅读数据挖掘手册（参见[28,73]）或是本章中提供的更多重点参考文献。
2.2 数据预处理
我们将数据定义为对象及其属性的集合，其中属性被定义为对象的一种属性或特性。对象的其他名包括记录，项目，点，样本，观察或实例。一个属性也可以相当于一个变量，字段，特征或是特点。
通常需要对实际生活中的数据进行预处理（例如：清理、过滤、变换），以便在分析步骤中被机器学习技术所使用。在本节中，我们着重讨论设计一个推荐系统尤其重要的三个问题。第一，我们回顾不同的相似度或是距离度量。然后，我们讨论采样的问题作为减少超大集合中的项目数量同时保留其主要特征。最后，我们描述了在维数约简中最常用的技术。
2.2.1 相似性测量
协同过滤（CF）推荐器的首选方法是使用在第2.3节中描述的k最邻近算法分类器。这种分类方法——作为最主要的分类器和聚类技术——是高度依赖于定义一个合适的相似度或距离度量。
距离测量的最简单和最常见的例子是欧几里得距离：
其中n是维数（属性），其中n是维数（属性），和分别是数据对象x和y的第k个属性（分量）。
闵可夫斯基距离是欧几里得距离的推广：
其中r是距离的角度。取决于r的值，泛型闵可夫斯基距离是已知的具体名称：
当r = 1，城市街区（曼哈顿，出租车或L1范数）距离；
当r = 2，欧几里得距离；
当r→，上确界（范数或范数）的距离，对应计算任何维度的数据对象之间的最大差异。
马哈拉诺比斯距离定义为：
其中是数据的协方差矩阵。
另一种非常常见的方法是将项目作为n维空间的文档向量，并将它们的相似度计算为它们形成的角度的余弦：
其中表示向量点积和|| x ||是向量x的范数。这种相似性被称为余弦相似性或L2范数。
项目之间的相似性也可以通过它们衡量对象之间的线性关系的相关度来给出。尽管有多个相关系数可供使用，但Pearson相关是最常用的。给定数据点x，ySigma;的协方差及其标准差，我们可以用下式计算Pearson相关：
推荐系统通常使用余弦相似性（式2.4）或Pearson相关（式2.5）— 或他们的变式之一如加权方案 — 在第五章和第四章都详细介绍了CF的不同距离函数的使用。然而，以前回顾的大多数都是可以的。Spertus等人[69]做了大规模的研究来评估Orkut社交网络环境中的6种不同的相似性度量。尽管他们的结果可能因其实验的特殊设定而有偏差，但有趣的是，对推荐给出最好的响应的是使用余弦相似性生成的结果。Lathia等人[48]也开展了关于几个相似性度量的研究，他们得出结论：在一般情况下，一个推荐系统的预测精度不受相似性度量的选择不同的影响。事实上，在他们的工作环境中，使用一个随机的相似性度量方法有时会比使用其他任何众所周知的方法产生更好的结果。
最后，在只具有二个属性的项目总，已经提出了几种相似性度量。首先，计算M01,M10,M11和M00的值，其中M01等于当x=0，y=1的时候属性的数字；其中M10等于当x=1，y=0的时候属性的数字，以此类推。通过这些量我们可以计算简单匹配系数（SMC）
Jaccard系数。扩展Jaccard（Tanimoto）系数，Jaccard系数的一个连续变量或计算属性，由计算。
2.2.2 采样
采样是在数据挖掘中用于从大型数据集中选择相关数据子集的主要技术。它用在预处理和最终数据解释的步骤。使用采样是因为处理整个数据集从计算上来说过于昂贵。它也可以用来创建训练和测试数据集。在这种情况下，训练数据集用于学习参数或配置分析步骤使用的算法，而测试数据集用于评估在训练阶段获得的模型或配置，确保其与以前未见的数据之间运转良好（广义上）。
抽样的关键问题是找到代表整个集合的具有代表性的原始数据集的子集，即它具有与其相同的感兴趣的性质。最简单的抽样技术是随机抽样，其中有相同的概率去选择任何项目。然而，更复杂的方法也有。例如：在分层采样中，根据特定特征将数据分成多个分区，然后独立地对每个分区进行随机采样。
最常见的取样方法包括使用无需更换的取样：当选择了某个项目时，将其从总体中移除。但是，也可以使用替换进行采样，一旦选择了物品，就不会从物品中移除物品，从而允许多次选择相同的样品。在分离训练和测试数据集时，通常使用标准随机抽样，而不是用80/20的比例进行替换。这意味着我们使用无需更换的随机抽样来为测试集选择20％的实例，并将剩余的80％用于训练。80/20的比例应该将作为经验法则，因为一般来说，高于训练集的2/3以上的任何值都是合适的。
抽样可能导致训练和测试数据集的特定划分过于专业化。出于这个原因，训练过程可能会重复多次。训练和测试集是从原始数据集创建的，该模型使用训练数据进行训练，并使用测试集中的例子进行测试。接下来，选择不同的训练/测试数据集以再次开始重复K次的训练/测试过程。最后，报告K学习模型的平均性能。这个过程被称为交叉验证。一共有几种交叉验证技术。在重复随机抽样中，标准随机抽样过程进行K次。在n倍交叉验证中，数据集分为n个折。其中一个折用于测试模型，剩下的n-1个折用于训练。然后交叉验证过程重复n次，n个子样本中的每一个样本用于验证数据并仅使用一次。最后，leave-one-out（LOO）方法可以被看作是n折交叉验证的极端情况，其中n被设置为数据集中的项目数。因此，每次只使用其中一个数据点作为测试，算法运行的次数与数据点一样多。但应该注意的是，如Isaksson等人在[44]中讨论的，交叉验证可能是不可信的，除非数据集足够大。
推荐系统中的一种常见方法是从用户那里获得有效反馈的采样 — 例如： 以评级形式 — 将其分为培训和测试。交叉验证也很常见。尽管在一般情况下标准随机抽样是可接受的，但在其他情况下，我们可能需要以不同方式对测试集的采样进行偏置。例如：决定仅从最近的评级中来采样 — 因为那些是我们在现实世界情况中预测的。我们也可能有兴趣确保在测试集中保留每个用户的评分比例，并因此规定随机抽样是以每个用户为基础进行的。然而，所有这些问题都与评估推荐系统的问题有关，这仍然是一个需要研究和讨论的问题。
2.2.3 维数约简
在推荐系统中通常不仅具有定义高维空间特征的数据集，还在该空间中还有非常稀疏的信息 — 即每个对象具有有限数量的特征值。密度和点之间距离的概念，对于聚类和异常值检测来说很重要，而在高维空间中变得没有意义。这就是所谓的维度灾难。维数约简技术通过将原始的高维空间转化为低维来帮助克服这个问题。
稀疏性和维度灾难是推荐系统中反复出现的问题。即使在最简单的情况下，我们也可能有一个包含数千行和列（即用户和项目）的稀疏矩阵，其中大部分都是零。因此，维数约简自然会出现。应用维数约简会产生相当的差异，其结果可直接应用于预测值的计算。因此现在认为这是推荐系统设计的一种方法，而不是一种预处理技术。
接下来，我们总结推荐系统中的两个最相关的维数约简算法：主成分分析（PCA）和奇异值矩阵分解（SVD）。 这些技术可以单独使用，也可以作为本章所述任何其他技术的预处理步骤。
2.2.3.1 主成分分析
主成分分析（PCA）[45]是一种经典的统计方法，用于查找高维数据集中的模式。 PCA允许从最小平方误差的角度获得一个有序的组件列表，用于解释数据中的方差：第一个组件获取的变化量大于第二个组件的变化量等等。我们可以通过忽略那些对方差影响较小的成分来降低数据的维数。
图2.2显示了由高斯组合生成的二维点云的PCA分析。在数据集中后，获得主成分并用u1和u2表示。注意：新坐标的长度与其特征向量中包含的能量有关。因此，对于图2.2所示的具体示例，第一个分量u1占能量的83.5％，这意味着去除第二个分量u2意味着仅损失16.5％的信息。根据经验法则选择m#39;，所以累积能量会高于某个阈值，一般为90％。 PCA允许我们通过将数据投射到新坐标系上来检索原始数据矩阵 。新的数据矩阵X#39;包含原始X的大部分信息，其维数降低了m-m#39;。
PCA是一种强大的技术，但它确实有的很大的局限。 PCA依赖于经验数据集形成某一基础的线性组合 — 尽管已经提出了用于非线性数据的泛型PCA。 PCA的另一个重要假设是原始数据集是从高斯分布中提取的。如果这种假设不成立的话，则不保证主要部分是有意义的。
图2.2：来自高斯组合的二维点云的PCA分析。 使用PCS导出的主要分量是u1和u2，其长度与组件中包含的能量有关。
虽然目前的趋势似乎表明其他矩阵分解技术（如奇异值矩阵分解或非负矩阵分解）是首选，但早期的工作中使用PCA。Goldberg等人提出了一种在线笑话推荐系统中使用PCA的方法[37]。他们的系统，Eigentaste 1，从用户对项目评分的标准矩阵开始。然后，他们通过选择所有用户有评价的项目的子集来选择他们的计量标准集。这个新矩阵用来计算应用标准二维PCA方法的全局相关矩阵。
2.2.3.2 奇异值分解
奇异值分解[38]是一种强大的维数约简技术。它是矩阵分解方法的一个特殊实现，因此它也与主成分分析有关。 SVD分解中的关键问题是找到一个低维特征空间，其中新特征表示“概念”，并且在集合上下文中每个概念的强度是可计算的。因为SVD允许在低维空间自动派生语义“概念”，所以它可以用作潜在语义分析的基础[24]，这是一种信息检索中非常受欢迎的文本分类技术。
SVD算法的核心在于以下定理：总是可以将给定的矩阵A分解为A =。给定ntimes;m矩阵数据A（n项，m个特征），我们可以得到一个ntimes;r矩阵U（n项，r个概念），一个rtimes;r对角矩阵（每个概念的强度）和一个m times;r矩阵V（m特征，r概念）。图2.3阐述了这个方法。对角矩阵包含奇异值，奇异值将始终为正，并降序排列。 U矩阵被解释为“项目到概念”的相似度矩阵，而V矩阵是“从术语到概念”的相似度矩阵。
图2.3：阐述基本奇异值分解理论：一个项目times;特征矩阵可以分解为三个不同的成分：项目times;概念、概念强度和概念times;特征。
为了计算矩形矩阵A的奇异值分解，我们考虑使用和。U的列是的特征向量，V的列是的特征向量。lambda;的对角线上的奇异值是和的非零特征值的正平方根。因此，为了计算矩阵A的奇异值分解，我们首先计算T来算、D来算，然后计算T和D的特征向量和特征值。
lambda;中的r特征值的大小递减排列。因此，原始矩阵A可以通过简单地截断给定k处的特征值来近似。截断SVD产生一个A的k阶近似，使得。是与A最接近的k阶矩阵。术语“最接近”意味着使A和的元素差异的平方和最小化。截断SVD是一个约简的k维空间中的潜在结构的表示，这通常意味着特征中的干扰已经消除了。
使用SVD作为提高协同过滤的工具已经有一段时间了。Sarwar等人[66]描述了在这种情况下使用SVD的两种不同方式。首先，SVD可以用来揭示客户和产品之间的潜在关系。为了实现这个目标，他们首先用项目平均评分代替用户项目矩阵中的零点，然后通过减去用户平均值来归一化。然后使用SVD分解这个矩阵并可以使用结果分解 — 在一些琐碎的的操作之后 — 直接计算预测值。另一种方法是使用由SVD产生的低维空间来改善邻域的形成以便以后在kNN方法中使用。
正如Sarwar等人[65]所描述的那样，SVD的最大优点之一
全文共6899字，剩余内容已隐藏，支付完成后下载完整资料
英语原文共 872 页，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[15889]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
