Apache Сравнение нечетких массивов искр

Question

У меня есть следующий DataFrame:

function_name |   result_list
--------------------------------
     f1       |  [1,0,0,0,1,0]
     f2       |  [0,0,1,0,1,1]
     f3       |  [1,1,1,0,0,0]
     f4       |  [1,0,0,0,1,0]

каждый массив в столбце result_list всегда имеет одинаковую длину. Чтобы найти 100% похожие массивы - я могу просто сгруппировать их по столбцу result_list.

Но мне также нужно найти почти похожие массивы, скажем, массивы, равные 95% или 90% или около того. , Есть ли в Apache Spark возможность этого добиться? Если да, не могли бы вы показать пример.

Answer 1

levenshtein-distance может быть подходящей мерой для сходства:

val df : DataFrame = Seq(
  ("f1",Seq(1,0,0,0,1,0)),
  ("f2",Seq(0,0,1,0,1,1)),
  ("f3",Seq(1,1,1,0,0,0)),
  ("f4",Seq(1,1,0,0,1,0)) // very similar to f1
).toDF("function_name","result_list")


df.alias("a").join(
  df.alias("b"),
    $"a.function_name" =!= $"b.function_name"
)
.withColumn("distance",levenshtein($"a.result_list".cast("string"),$"b.result_list".cast("string")))
  .where($"distance"<=1) // similarity threshold
  // avoid duplication
  .select(sort_array(array($"a.function_name",$"b.function_name")).as("pairing"),$"distance")
  .dropDuplicates("pairing")
  .show()

дает:

+--------+--------+
| pairing|distance|
+--------+--------+
|[f1, f4]|       1|
+--------+--------+

Вы также можете использовать levenshtein в условии соединения, но тогда вы потеряете информация о расстоянии:

df.alias("a").join(
  df.alias("b"),
    $"a.function_name" =!= $"b.function_name" and levenshtein($"a.result_list".cast("string"),$"b.result_list".cast("string")) <= 1)