python - Jaccard 文本行之间的相似度 Apache Spark

Question

我需要计算所有文本行对的杰卡德相似度。我只希望输出相似度高于 80% 的对。过去我研究过 Hadoop MapReduce 框架，这就是我如何使用 Map 和 Reduce 函数解决这个问题:

map(lineID, text):
    for each word in text:
         emit(word, (len(text), lineID))

reduce(word, list(v)):
    if len(list(v)) < 2:
        do nothing
    else 
        for each pair ((len1, 1), (len2, 2)):
             emit ((1, 2, len, len2), 1)

map(k, v):
    emit (k, v)

reduce(k, v):
    similarity = len(v)/(k[2]+k[3]-len(v))
    if similarity > 0.80
         emit((k[0], k[1]), similarity)

现在我需要在 PySpark 中实现这个伪代码，但我有点卡住了。我所做的只是第一张 map ，例如:

def mapping(line):
    length = len(line.split())-1
    jobID = line.split()[0]
    return (length, jobID)

c = textFile.map(lambda line: [(c, (mapping(line))) for c in line.split()[1:]])

我不考虑第一个单词，因为该单词是 lineID。这是我的另一个疑问，如何获取输入文本的行索引？任务是如何分配给 worker 的？我对 Apache Spark 的工作方式感到非常困惑。

您对我可以使用哪些方法以及以什么顺序实现我在 MapReduce 中获得的结果有什么建议吗？

Answer 1

除非您的数据非常大，否则最简单、最容易的方法也可能是最快的。让我们分而治之:

1. 使用crossJoin获取所有线对的数据帧。

2. 删除左手线与右手线相同的行，因为您不关心 self 比较。

3. 使用简单的 UDF jaccard(left, right) 返回 Jaccard 相似度。

4. 按相似度过滤 > 0.8

我通过 Scala 使用 Spark，所以我会为您提供 Scala 代码； Python DSL 应该非常相似。

val lines = spark.read.text(...)
lines.alias("lhs").crossJoin(lines.alias("rhs"))
  .where($"lhs.value" =!= $"rhs.value")
  .withColumn("similarity", jaccard($"lhs.value", $"rhs.value"))
  .where($"similarity" > 0.8)