介绍相似度计算的方法，着重于spark编程方面。。。
背景介绍：
在推荐系统中，基于内容的推荐方法和协同过滤方法都会用到相似度计算。最简单的就是计算行（用户）或列（项）的余弦或其他相似性，并推荐k个用户最喜欢的最近邻项。
在Word2vector中，文本内容的处理被简化成k维向量空间中的向量运算，其向量之间的相似度可以用来表示文本语义的相似度。
由此可知，相似度度量是一个很重要并且很基础的内容，因此本文介绍一下，spark中计算相似度的若干种方法。
我们假设已经得到了向量或者矩阵，本文主要讨论如何使用spark来计算他们之间的相似度。（作为一个编程 slow learner，好不容易把Python用顺手了，又让我学Scala，想哭:sob:).
数据准备：
本文开始使用一个简单的例子，使用GitHub上一个中文词向量项目中预训练好的词向量作为我们的实验数据。Chinese Word Vector.这个项目提供了100多个不同形式的（密集和稀疏），上下文特征（单词，ngram，字符等）和语料库训练的中文单词向量（嵌入）。可以轻松获得具有不同属性的预先训练的向量，并将它们用于其他任务。
格式：
预训练的向量文件是txt格式，第一行表示元数据信息：第一个数字表示本文件的单词个数，第二个表示向量维数。
我们以微博语料库训练的、context feature为Word+Ngram的向量包sgns.weibo.bigram-char为例：
1 | 191321 300 |
表示本文件的词数量以及向量维度为300维。
取某向量示意：
1 | 我们 0.838326 0.401992 0.312874…… 0.886258 [total 300-d] |
每行数据以空格" "分隔。
代码：
我们读入该词向量包，在spark中自动存成RDD数据格式。
假设我们取”春”、“夏”，”秋”，”冬”四个词：
1 | //环境 |
My approach:使用breeze库计算
breeze 作为一个scala 线性代数库 ，spark mlib机器学习使用了其中实现 ，最重要的是它相当于python的numpy 使用方法也很类似，这很重要。具体的breeze的使用见：saprk向量矩阵的使用
step1：数据转换
首先，我们将之前读入的RDD数据要转换为breeze中向量或者矩阵的形式。
尝试1：
将读入的RDD数据直接转换为breeze vector
1 | val dm = rows.map(x => DenseVector(x._2)) |
因为是RDD格式，是没有办法进行各种breeze向量或者矩阵的操作的
1 | dm.t |
即便每条转换成向量，因为还是RDD数据，也不行：
1 | val v2 = DenseVector(denserows.filter(x => x._1.equals("夏"))) |
尝试2：
RDD->Array->DenseMatrix
原始读进去的数据rows是rdd.RDD[(String, Array[Double])]格式。
- 首先将其转换成
Array[Array[Double]]格式，并读取行列数，此时一个二维数组，在铺平成一维数组。
1 | val Array_rows = rows.map(x => x._2).collect() |
- 从一维数组创建Breeze矩阵：
1 | import breeze.linalg._ |
注意：因为平铺数组（按行）与创建二维数组（按列）的方式正好相反，因此在创建二维矩阵时需要交换行数和列数，并在最后把矩阵转置即可。不可以在创建的时候交换行列数哦！
step2：建立相似度算法计算公式
尝试1：
有了breeze矩阵之后，就可以对其进行索引操作：
1 | //取第一行，即"春"的word vector |
依次可以得到各个vector，并计算余弦相似度。breeze库支持点积（内积），对应元素操作等，因此计算方便，但是，这种对量量向量计算相似度的话，需要计算六次，有点麻烦。我们直接对矩阵进行操作，如下:
尝试2：
- 设$A_i$为breeze矩阵第$i$个行向量，则矩阵表示为：
$$
mat = \begin{bmatrix}
A_1 \
A_2 \
A_3 \
A_4 \
\end{bmatrix}
$$
- 假设我们计算$A_1,A_2$的余弦相似度：
$$
cos(A_1,A_2) = \frac{A_1\cdot A_2}{|A_1|\cdot |A_2|} \=\frac{A_1\cdot A_2}{\sqrt{\sum_i^{300}a_{1i}^2}\cdot \sqrt{\sum_i^{300}a_{2i}^2}}
$$
- 所以我们可以通过直接操作矩阵来计算：
$$
mat \cdot mat^T = \begin{bmatrix}
A_1 \
A_2 \
A_3 \
A_4 \
\end{bmatrix}\cdot \begin{bmatrix}
A_1^T&
A_2 ^T&
A_3 ^T&
A_4 ^T&
\end{bmatrix} \
= \begin{bmatrix}
A_1 \cdot A_1^T & A_1 \cdot A_2^T & A_1 \cdot A_3^T & A_1 \cdot A_4^T \
…… & A_2 \cdot A_2^T & A_2 \cdot A_3^T & A_2 \cdot A_4^T \
…… &…… & A_3 \cdot A_3^T & A_3 \cdot A_4^T \
…… & …… & …… & A_4 \cdot A_4^T \
\end{bmatrix}
$$
代码：
1 | mat*mat_t |
- 对$mat$的每一行求模：
$$
|mat| = \begin{bmatrix}
|A_1| \
|A_2| \
|A_3| \
|A_4 |\
\end{bmatrix} = \begin{bmatrix}
\sqrt{\sum_i^{300} a_{1i}^2} \
\sqrt{\sum_i^{300} a_{2i}^2}\
\sqrt{\sum_i^{300} a_{3i}^2} \
\sqrt{\sum_i^{300} a_{4i}^2} \
\end{bmatrix}
$$
代码：
1 | val A1_2 = sum(mat :*mat,Axis._1) |
- 最后求的相似度矩阵为，
:/表示对应元素相除：
$$
cosmat = mat\cdot mat^T :/ (|mat|\cdot |mat|^T) \
=\begin{bmatrix}
A_1 \
A_2 \
A_3 \
A_4 \
\end{bmatrix}\cdot \begin{bmatrix}
A_1^T&
A_2 ^T&
A_3 ^T&
A_4 ^T
\end{bmatrix} \
:/ \
\begin{bmatrix}
|A_1| \
|A_2| \
|A_3|\
|A_4 |\
\end{bmatrix}\cdot \begin{bmatrix}
|A_1|&
|A_2| &
|A_3|&
|A_4 |
\end{bmatrix} \
= \begin{bmatrix}
\frac{A_1 \cdot A_1^T}{|A_1||A_1|} & \frac{A_1 \cdot A_2^T}{|A_1||A_2|} & \frac{A_1 \cdot A_3^T}{|A_1||A_3|} & \frac{A_1 \cdot A_4^T}{|A_1||A_4|} \
…… & \frac{A_2 \cdot A_2^T}{|A_2||A_2|} & \frac{A_2 \cdot A_3^T}{|A_2||A_3|} & \frac{A_2\cdot A_4^T}{|A_2||A_4|} \
…… &…… & \frac{A_3 \cdot A_3^T}{|A_3||A_3|}& \frac{A_3 \cdot A_4^T}{|A_3||A_4|}\
…… & …… & …… & \frac{A_4 \cdot A_4^T}{|A_4||A_4|}\
\end{bmatrix} \
=\begin{bmatrix}
cos(A_1,A_1) & cos(A_1,A_2) & cos(A_1,A_3) & cos(A_1,A_4) \
…… &…… & …… & …… \
…… &…… & …… & …… \
…… & …… & …… & cos(A_4,A_4)\
\end{bmatrix}
$$
代码：
1 | val mo = A1_abs*A1_abs.t |
最后的相似度矩阵为：
1 | 1.0 0.3360632195747908 0.4942891722056013 0.4423001538457035 |
Method1:map-reduce方法
这是种很笨的方法
step1.创建数组
1 | val array = rows.map(x => x._2).collect |
step2.组成行向量
1 | val vector1 = array(0).toVector |
step3.计算相似度
以vector1和vector2计算余弦距离为例：
1 | vector1.zip(vector2) |
和之前求出的相似度矩阵的第一行第二列相同，为春和夏的相似度。
Method2:RowMatrix方法
spark自带org.apache.spark.mllib.linalg.distributed.IndexedRowMatrix
这个类有个方法叫 columnSimilarities 就是计算矩阵列向量间的两两余弦相似度。
返回类型是CoordinateMatrix，一个矩阵，该矩阵下标为(x,y)的元素就是原矩阵第x列和第y列的相似度。
代码如下：
1 | import org.apache.spark.mllib.linalg.distributed.{MatrixEntry, RowMatrix} |
他计算的是列与列之间的相似度，生成的是一个坐标矩阵，无法直接访问：
1 | //报错 |
可以看出列相似度矩阵不是我们想要的，出来$300\times300$大小。
而且我也不知道怎么使用RDD矩阵的转置，而且RowMatrix没有专转置方法所有就不搞了。。。。。
几种Vector创建方式
1.mllib
MLLib提供了一序列基本数据类型以支持底层的机器学习算法。主要的数据类型包括：本地向量、标注点（Labeled Point）、本地矩阵、分布式矩阵等。单机模式存储的本地向量与矩阵，以及基于一个或多个RDD的分布式矩阵。其中本地向量与本地矩阵作为公共接口提供简单数据模型，底层的线性代数操作由Breeze库和jblas库提供。标注点类型用来表示监督学习（Supervised Learning）中的一个训练样本。
1 | import org.apache.spark.mllib.linalg.{Vector, Vectors} |
无法进行zip操作。
2.toVector方法
EEE,这是RDD[vector]自带的方法
1 | scala> val rows_2 = rows.map(x => x._2.toVector) |
3.Breeze库的DenseVector方法
1 | val dm = rows.map(x => DenseVector(x._2)) |
Reference
- 怎样使用Spark计算一个集合各个元素（向量表示的）的两两之间的余弦相似度
- RowMatrix 列相似度计算
- breeze向量矩阵的使用
- scala如何从文件读取数据并转换成矩阵
- Spark 相似度算法,map,zip,reduce
- 分布式矩阵之坐标矩阵使用方法
- 子雨大数据之spark教程
- 使用inverted index方法实现大型稀疏向量相似度计算
- Spark 协同过滤ALS之Item2Item相似度计算优化
- Spark Mllib里相似度度量（基于余弦相似度计算不同用户之间相似性）
- 【干货】推荐系统中的机器学习算法与评估实战
- Spark成长之路(6)-Correlation
- 【入门篇】如何在spark分布式矩阵实现协同过滤推荐？
- Data Types - RDD-based API