4.3.1　计算topN相似度

该阶段要计算出任意两个标的物之间的相似度，有了任意两个标的物之间的相似度，我们就可以为每个标的物计算出与它最相似的N个标的物了。

假设有两个标的物v_i,v_j，它们对应的向量（即用户行为矩阵中的列向量，分别是第i列和第j列）如下：

其中，n是用户数。

那么v_i,v_j的相似度计算，可以细化成如下公式：

上述公式中，分子的计算方法是先将图4-1所示矩阵里i列和j列中同一行的两个元素（矩形框中的一对元素）相乘，然后将所有行上第i列和第j列的元素相乘得到的乘积相加（这里其实只需要考虑同一行对应的第i列和第j列的元素都非零的情况，因为只要第i列和第j列中有一个为零，乘积也为零）。公式中分母的计算方法是将第i列与第i列元素按照上面类似的方法相乘再相加后求平方根，再乘以第j列与第j列按照上面类似的方法相乘再相加后求平方根的值。

图4-1　计算两个列向量的余弦可以拆解为简单的加减乘除及求平方根运算

有了上面的简单分析，就容易采用分布式计算相似度了。下面就来讲解在Spark上简单地计算每个标的物的topN相似度的方法。在Spark上计算相似度，最主要的目标是将巨大的计算量（前面已经提到在互联网公司，往往用户数和标的物数都是非常巨大的）通过分布式技术实现，这样就可以利用多台服务器的计算能力，解决超大规模计算问题。

首先将所有用户操作过的标的物“收集”起来，形成一个用户行为弹性分布式数据集（Resilient Distributed Dataset，RDD），具体的数据格式如下：

RDD[(uid,Seq[(sid,R)])]

其中，uid是用户唯一识别编码，sid是标的物唯一识别编码，R是用户对标的物的评分（即矩阵中的元素）。

对RDD[(uid,Seq[(sid,R)])]中的某个用户来说，对于他操作过的标的物v_i和v_j，一定在该用户所在的行对应的第i列和第j列的元素非零，根据上面计算v_i,v_j相似度的公式，需要将该用户对应的v_i,v_j的评分乘起来。这个过程可以用图4-2来说明。

图4-2　用户U所有操作过的标的物的笛卡儿积

当所有用户都按照图4-2的方式转化为标的物对和得分（图4-2中右边的R_i×R_j）时，我们就可以对标的物对聚合（Group），即将相同的对合并，对应的得分相加，最终得到的RDD为

S1=RDD[((sid1,sid2),Score)]

图4-3　计算分母

注：这里及后面都是Scala代码，特此说明。

这样，式（4-1）中分子就计算出来了（上式中的Score即公式4-1中的分子）。现在我们需要计算分母，这非常简单，只要从上面的RDD中将标的物sid1等于标的物sid2的列过滤出来就可以了,通过图4-3的操作，我们可以得到一个map（S₂）。

从S₁中过滤出sid1=sid2的元素，用于计算式（4-1）中的分母。

S₂含有的元素个数不会多于标的物的数量（即m个），相对来说不大，我们可以将S₂广播（broadcast）出去，令S'₂=sparkContextbroadcast(S₂)，以方便我们按照式（4-1）除以分母，最终得到v_i,v_j的相似度。

通过上面这些步骤，式（4-1）中的分子和分母基本都计算出来了，可以看到很容易，通过图4-4的代码（下面的broadcast即S'₂），就可以计算出每组(v_i,v_j)对的相似度，最终得到的RDD为

S=RDD[((sid1,sid2),Sim)]

其中，Sim为sid1和sid2的相似度。

图4-4　计算每组v_i,v_j的相似度

有了上面的准备，下面来说明一下怎么计算每个标的物的topN标的物。

具体的计算过程可以用如下的Spark Transformation来实现。其中第三步的topN需要我们自己实现一个函数，求Seq[(sid,Score)]这样的列表中评分最大的topN个元素，实现也是非常容易的，这里不赘述。

图4-5　标的物相似度矩阵

如果我们把每个标的物最相似的N个标的物及相似度看成一个列向量，那么我们计算出的标的物相似度其实可以看作如图4-5所示的矩阵，该矩阵的每列最多有N个非零元素（即这N个最相似的标的物，该列其他元素都为0）。

到此为止，我们通过Spark提供的一些Transformation操作及一些工程实现上的技巧，计算出了每个标的物topN最相似的标的物。该计算方法可以横向拓展，所以再大的用户数和标的物数都可以轻松应对，最多可能需要多加一些服务器。