记录两两相比问题

2020/07/05 -
刚刚就在思考，如果是利用spark或者hadoop的运算框架，来强行计算大量数据的两两相似度，应该怎么来编写呢？我想了一会，就感觉好像没有办法嵌入到这个模型中，这就比较困难了。

在百度上搜索这部分东西，然后看到了回答[1]，感觉应该是有相关的框架；然后普遍的回答都是利用LSH，然后分桶，然后计算小部分的，而不是说全部的。这里这个分桶是什么意思呢？不太理解。

回到上面这个问题，假设我先使用spark来实现，不考虑这个性能问题，就考虑这个东西应该怎么编程实现。
本身这个问题呢，我自己在实现的时候，就是如果不用大数据平台，我就是按照双循环的形式直接来进行比较。

for i in range (n):for j in range(i+1,n):

我是怎么也想不出来这个东西怎么弄，这个时候应该看看我知道什么他具备哪些基础操作，也就是原子操作。本质上，这种操作形式属于两个RDD的交叉工作。在RDD上好像是没有那种按照索引来选定元素的方式。

想不出来，哈哈哈哈哈哈哈，日了狗了。。

这么看来，就感觉就好像mapreduce这种模型并不是适用于这种计算，看来得进行转化了。

我来简单阐述一下我通过查找资料学习到的东西。

首先，直接搜索pair similar spark，首先找到的是一个ppt（这个ppt放在spark的同级目录下），ppt中含有一个All-pairs similarity compution。注意，这里他给出了一个形式化的描述，这一点是我没想到的。

问题的形式化描述

第一点，矩阵，这一点很重要，就是要把问题转化为数学问题。（但我感觉其实还是一个编程的问题，因为这个时候我没有想着去弄什么性能的优化，我只是想得到一个可行的编程方案）
然后就是矩阵的特点，属于行多列少，而且远大于；属于稀疏矩阵；这个矩阵不能存在与单个机器的内存。

我觉得这里面，矩阵的这个概念很重要，我记得当时最开始学习《海量数据挖掘》的时候，就有将矩阵运算转化为mapreduce的过程，这样的话，匹配前面的过程，前面寻找框架的时候，所以说，我还是没有将问题转化好。

mapreduce编程方式

普通的方式就是利用mapreduce的形式，通过矩阵运算来实现这个整体相似度的计算。这个过程的话，其实就跟前面提到的矩阵运算是一致的。这里比较关键的是他的这个转化过程。

然后还有这个文章[2]，他其实就是介绍了PPT后面的算法，就是某种逼近相似度？然后将这个东西引入到了spark中。他这里呢，将这个概念更明确了，本身叫做全对相似度比较，（all-pairs similarity），又是也被叫做similarity join问题。

然后按照这个关键词，我找到了文章[3]，他是来讲解文本的相似度比较问题的，但是说实话，我没弄懂他是怎么做的。但是，他这里有一个ID，这个应该是很重要的，这个是能够标识的。我觉得，他好像是使用了那种TF-IDF的样子一样，这个再仔细看看。

总结一下

实际上，这篇文章并没有给出具体的方案，但是我有点知道了到底应该怎么办。就是通过矩阵的方式，但是这里需要一个实体的ID来标识。
然后，实际上在业界更多的是进行那种大致相似，以及topk近邻的问题。这些在spark中都有涉及。

[1]Spark 千万级用户相似度计算？
[2]efficient-similarity-algorithm-now-in-spark-twitter.html
[3]similarity-join-spark/