记录两两相比问题
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的形式,通过矩阵运算来实现这个整体相似度的计算。这个过程的话,其实就跟前面提到的矩阵运算是一致的。这里比较关键的是他的这个转化过程。
然后还有这个文章[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/