本节书摘来自华章出版社《推荐系统：技术、评估及高效算法》一书中的第2章，第2.2节，作者 [ 美］弗朗西斯科·里奇（Francesco Ricci）利奥·罗卡奇（Lior Rokach）布拉哈·夏皮拉（Bracha Shapira）保罗 B.坎特（Paul B.Kantor），更多章节内容可以访问云栖社区“华章计算机”公众号查看
2.2 数据预处理
我们把数据定义为一组对象及其属性的集合，其中属性定义为性质或者是对象的特征。对象的其他名称包括记录、物品、得分、样本、观察值或者实例。属性也可以称为变量、字段、特性或者特征。
真实数据通常需要经过预处理，以便于机器学习技术在分析阶段使用。本节紧紧围绕推荐系统设计三个尤为重要的问题展开。首先，我们回顾不同的相似度，或者距离度量方式。其次，我们需要讨论抽样问题，一种可以减少大数据集中物品数量并保持其主要特征的方法。最后，我们将阐述降维方法中最常用的技术。
2.2.1 相似度度量方法
协同过滤推荐备受青睐方法之一是使用kNN分类，我们将在2.3.1节中讨论。这种分类技术（如同大多数的分类和聚类技术）主要取决于定义合适的相似度或者距离度量方法。
最简单、最常用的距离度量是欧几里得距离：
其中,n是维数（属性数），xk和yk分别是数据对象x和y的第k个属性值（分量）。
闵可夫斯基距离是欧几里得距离的推广：
其中，r是距离的度（参数）。取决于r值的不同，一般的闵可夫斯基距离有专用的名称：
r=1，城市街区（也叫曼哈顿、出租车、L1范数）距离。
r=2，欧几里得距离（L2范数）。
r=∞，上确界（Lmax或L∞范数），这是任意维度对象属性间的最大距离。
马氏距离定义如下：
其中，σ是数据的协方差矩阵。
另一个常用的方法是把物品看作n维空间的文档向量，并且计算它们相似度作为形成夹角的余弦值，其公式如下：
其中,•表示向量的点积，x是向量x的长度。这个相似度称为余弦相似度或者是L2范数。
物品之间的相似度还可以用他们的相关度计算，用以度量对象间的线性关系。尽管有几个相关系数可能被应用,但皮尔逊相关性系数是最常用的。给出点x和y的协方差及它们的标准差σ,我们用以下公式计算皮尔逊相关性:
推荐系统一般会使用余弦相似度式（2.4）或者是皮尔逊相关性（或者它们的许多变种方法中的一种，如加权方案）。第4和5章详述在协同过滤中不同距离函数的使用。但是，前面提到的大部分其他距离度量方法都可能用到。Spertus等［69］在Orkut社交网络的环境中做了大规模的研究来评估六种不同的相似度度量方法。尽管由于实验的特殊设置，结果会有偏差,但有趣的是余弦相似度是其中效果最好的度量方法。Lathia等［48］也做了一些相似度度量的研究，其总结，在一般的案例中，推荐系统的预测精确性不受相似度度量方法选择的影响。事实上，在他们的工作中，使用随机的相似度度量有时会产生比使用已知任何众所周知的方法更好的结果。
最后，在一些只有二进制属性的物品案例中，可以采用几个相似度度量方法。首先，计算M01、M10、M11和M00数量，其中M01代表x是0同时y是1这个属性的数量，M10代表x是1同时y是0这个属性的数量，以此类推。根据这些数值我们可以计算得到：简单匹配系数SMC=number of matchesnumber of attributes=M11+M00M01+M10+M00+M11；Jaccard系数JC=M11M01+M10+M11。广义Jaccard（Tanimoto）系数，是JC关于连续值属性或计数属性的一个变型，计算为d=x•yx2+y2-x•y。
2.2.2 抽样
抽样是数据挖掘从大数据集中选择相关数据子集的主要技术。它用于数据预处理和最终解释步骤中。之所以使用抽样是因为处理全部数据集的计算开销太大。它也可以被用来创建训练和测试数据集。这个情况下,训练集被用于分析阶段学习参数或配置算法，而测试集被用来评估训练阶段获得的模型或者配置,确保它在将来产生的未知数据上运行良好。
抽样的关键是发现具有整个原始数据集代表性的子集，也就是说，其具有与整个数据集大概类似的兴趣属性。最简单的抽样技术是随机抽样，任意物品被选中的概率相同。但也有更复杂的方法。例如,在分层抽样中数据基于特殊特征被分成几个部分，之后对每个部分独立进行随机抽样。
最常用的抽样方法包含使用无取代的抽样：当物品被选择的时候，物品被从整体中取走。但是，执行取代抽样也是可以的，物品即使被选择也不用从整体中去除，允许同样的样本被选择多次。
在分离训练集和测试集时，通常做法是使用80/20的训练集和测试集比例，并使用无替代的标准随机抽样。这意味着我们使用无替代随机抽样方法去选择20%的实例为测试集,把剩下的80%进行训练。80/20的比例应该作为一个经验规则,一般来说,超过2/3的任何值作为训练集是合适的。
抽样可能导致过特殊化划分的训练和测试数据集。因此,训练过程可以重复好几次。从原始数据集中创建训练集和测试集,使用训练数据进行模型训练并且使用测试集中的样例进行测试。接下来,选择不同的训练/测试集进行训练/测试过程，这个过程会重复K次。最后，给出K次学习模型的平均性能。这个过程是著名的交叉验证。交叉验证技术有很多种。在重复随机样本中，标准的随机抽样过程要执行K次。在n折交叉校验中，数据集被分成n份。其中一份被用来测试模型，剩下n-1份被用来进行训练。交叉验证过程重复n次，n个子样本中每一个子样本都只使用一次作为验证数据。最后，留一法（LOO）可以看作n折交叉验证的极端例子，其中n被设置为数据集中物品的数量。因此，算法运行许多次而每次数据点只使用其中一个作为测试。我们需要注意的是，正如Isaksson等讨论的那样［44］,除非数据集足够大，否则交叉验证可能不可信。
在推荐系统中常用的方法是从用户中抽取可用的反馈以用户评分的形式来划分训练和测试。交叉验证的方法同样也很常见。尽管在一般的案例中标准随机抽样是可接受的，但是在其他场景中我们需要用不同的方法定向调整抽样出来的测试集。例如，我们可能决定只抽样最近的评分数据，因为这些是现实情况下我们需要预测的。我们可能还有兴趣确保每个用户的评分比例被保存在测试集,因此需要对每一个用户使用随机抽样。然而,所有这些涉及评估推荐的问题仍是一个探讨和研究点。
2.2.3 降维
推荐系统中不仅有定义高维空间特征的数据集，而且在空间中信息非常稀疏，例如，每个对象就那么几个有限的特征有值。密度，以及点之间的距离，这些对于聚类和孤立点检测非常重要，但在高维空间中的意义并不大。这就是著名的维度灾难。降维技术通过把原始高维空间转化成低维有助于克服这类问题。
稀疏和维度灾难是推荐系统中反复出现的问题。即使在最简单的背景下，我
们很可能都会有成千上万行的行和列稀疏矩阵，其中大部分值是零。因此，降低维度就自然而然了。应用降维技术带来这样的结果，其也可以直接适用于计算推荐的预测值，即它可以作为推荐系统设计的方法，而不仅是数据预处理技术。
接下来，我们概述两个在推荐系统中最相关的降维算法：主成分分析（PCA）和奇异值分解（SVD）。这些技术可以单独作为推荐方法使用，或作为在本章提到的其他任何技术的预处理步骤。
2.2.3.1 主成分分析
主成分分析（PCA）［45］是一种经典统计方法，用来发现高维数据集中的模式。主成分分析可以获得一组有序的成分列表，其根据最小平方误差计算出变化最大的值。列表中第一个成分所代表的变化量要比第二个成分所代表的变化量大，以此类推。我们可以通过忽略这些对变化贡献较小的成分来降低维度。
图2.2显示了通过高斯合并产生的二维点云中的PCA分析结果。数据集中之后，主要成分由u1和u2来表示。考虑到新坐标轴的长度所涉及的能量被包含在它们的特征向量中。因此，对于图2.2中列举的特殊例子，第一个成分u1占能量的83.5%，这意味着移除第二个成分u2将只失去16.5%的信息。根据经验规则选择m′以便于累计能量超过一定的阈值，一般是90%。PCA允许我们把数据投影到新的坐标系中来重新表示原始数据矩阵：X′n×m′=Xn×mW′m×m′。新的数据矩阵X′降低了m-m′维度并保证包含大部分的原始数据X的信息。
PCA是一种强大的技术，但也有重要的限制。PCA依赖于以线性合并为基础的经验数据集,尽管一般的非线性PCA方法已经提出。PCA的另一个重要假设是原始数据集是从高斯分布中抽取出来的。当这个假设不正确时，就无法保证主要成分的有效性。
尽管目前的趋势似乎表明其他的矩阵分解技术更受欢迎，如SVD或者非负矩阵分解，但是早期用得最多还是PCA。Goldberg等在在线笑话推荐的内容中提出使用PCA方法［37］。他们的系统，著名的Eigentaste，开始于标准的用户评分矩阵。然后从所有用户都评分过的item里选出一个子集作为测试集。这个新矩阵被用来计算全局相关矩阵，这些矩阵使用了标准的二维PCA。
2.2.3.2 奇异值分解
奇异值分解［38］是一个强大的降维工具。它是矩阵分解方法的特殊实现，因此它也和PCA相关。在SVD分解中的关键问题是发现低维特征空间，这些新特征代表概念以及在集合内容中的每一个概念强度都是可计算的。因为SVD可以自动获取到低维空间上的语义概念，它可以被用来当作潜在语义分析的基础，潜在语义分析［24］是一种在信息检索中非常受欢迎的文本分类技术。
SVD的核心算法基于以下的理论：把矩阵A分解成A＝UλVT是可行的。给出ｎ×ｍ矩阵的数据A(n个物品，m个特征)，我们可以获得一个n×r的矩阵U（n个物品，r个概念），一个r×r的对角矩阵R（概念的长度），以及m×r的矩阵V（m特征，r概念）。图2.3阐述了这个想法。R的对角矩阵包含奇异值，其总是为正并且是降序排列。U矩阵可以解释成物品概念相似矩阵，矩阵Ｖ是特征概念相似性矩阵。
为了计算矩形矩阵A的SVD，我们考虑如下公式AAT和ATA。U的列是AAT的特征向量，V的列是ATA的特征向量。矩阵对角线上的奇异值是AAT和ATA非零特征值的平方根。因此，为了计算矩阵A的SVD，首先计算AAT(T)以及ATA(D)，然后计算T和D的特征向量和特征值。
在λ中的特征值r是有序递减的。因此，初始矩阵A可以通过截取前k个特征值来近似构造。截取的SVD构造了一个近似矩阵A的k秩矩阵Ak=UkλkVT。Ak是最近似原始矩阵的K秩矩阵。最近似表达的是最小化A与Ak元素之间的平方差之和。被截取的SVD代表降维成k维空间后的潜在结构，这一般意味着特征向量中的噪声被降低。
使用SVD作为工具来提高协同过滤已经有一段时间了。Sarwar等［66］在论文中描述了使用SVD的两种不同方法。首先，SVD可以用来发现用户与产品之间的潜在关系。为了完成这个目的，他们首先用物品平均评分值去填充用户物品矩阵的0值项，然后通过减去用户对所有物品平均评分来正规化这些矩阵。这些矩阵用SVD来分解，其分解结果在一些细微的操作之后可以直接用来计算预测值。其他方法是使用从SVD中提取出的低维空间中的结果来提高在kNN方法的邻居信息。
正如Sarwar等［65］描述的那样，SVD的一大优势是有增量算法来计算近似的分解。这使得我们在接收到新用户或者是评分的时候，没有必要重新计算用先前存在的数据构建的模型。同样的想法后来被Brand［14］的在线SVD模型扩充和正式采纳。在成功应用到Netflix Prize之后，增量SVD方法的使用最近已经成为常用的方法。Simon Funk的简单增量SVD方法的发表被标志为竞赛中的转折点［35］。自从它发表之后，在该领域已经发表了几篇改进的SVD（详细信息可以参考Paterek的全部SVD的算法［56］，或者是Kurucz等的SVD参数评估［47］）。
最后，应该注意的是矩阵分解（MF）的不同变化方法，如非负的矩阵分解（NNMF）已经被使用［74］。本质上来说，这些算法类似于SVD。最基本的想法是把评分矩阵分解成两个部分：一个部分包含描述用户的特征，另一个部分包含描述物品的特征。矩阵分解通过引入偏项到模型中来处理缺失数据比SVD方法要好。但是，SVD方法中也可以在预处理阶段通过用物品的平均值来取代零值来处理。需要注意的是SVD和MF都可能产生过拟合的问题。但是已存在改进的MF，如正规化内核矩阵分解，能有效地避免这个问题。MF和SVD方法的主要问题是，由于计算的复杂性每次数据升级更新时重新计算分解是不现实的。但是，Rendle和Schmidt-Thieme［62］提出一种在线的方法允许不用重新计算所有整个模型来更新分解近似值。
第5章会详细介绍在Netflix Prize的环境中SVD和MF的使用，是对本章简介的详细补充。
2.2.4 去噪
数据挖掘中采集的数据可能会有各种噪声，如缺失数据，或者是异常数据。去噪是非常重要的预处理步骤，其目的是在最大化信息量时去除掉不必要的影响。
在一般意义上我们把噪声定义为在数据收集阶段收集到的一些可能影响数据分析和解释结果的伪造数据。在推荐系统的环境中，我们区分自然的和恶意的噪声［55］。前者提到的噪声是用户在选择偏好反馈时无意产生的。后者是为了偏离结果在系统中故意引入的。
很显然恶意的噪声能够影响推荐的输出。但是，我们的研究推断正常的噪声对推荐系统性能的影响是不可忽略的［4］。为了解决这个问题，我们设计了一个去噪方法，能够通过要求用户重新评价一些物品来提高精确度［5］。我们推断通过预处理步骤来提高精确度能够比复杂的算法优化效果要好得多。
