webdevqa.jp.net

Sparkデータフレームのシーケンス

Sparkにデータフレームがあります。このように見えます:

_+-------+----------+-------+
|  value|     group|     ts|
+-------+----------+-------+
|      A|         X|      1|
|      B|         X|      2|
|      B|         X|      3|
|      D|         X|      4|
|      E|         X|      5|
|      A|         Y|      1|
|      C|         Y|      2|
+-------+----------+-------+
_

最終目標:_A-B-E_(シーケンスは後続の行の単なるリストです)がいくつあるかを調べたいと思います。シーケンスの後続の部分は最大n行離れているという制約が追加されています。この例では、nが2であると考えてみましょう。

グループXについて考えてみます。この場合、DBの間に正確に1つのEがあります(複数の連続するBsは無視されます)。つまり、BEは1行離れているため、シーケンス_A-B-E_があります。

collect_list()の使用、文字列(DNAなど)の作成、正規表現での部分文字列検索の使用について考えました。しかし、おそらくウィンドウ関数を使用して、よりエレガントな分散方法があるかどうか疑問に思いましたか?

編集:

提供されているデータフレームは単なる例であることに注意してください。実際のデータフレーム(したがってグループ)は任意の長さにすることができます。

7
Tim

@Timのコメントに答えるために編集+タイプ「AABE」のパターンを修正

はい、ウィンドウ関数を使用すると役立ちますが、順序付けを行うためにidを作成しました。

val df = List(
  (1,"A","X",1),
  (2,"B","X",2),
  (3,"B","X",3),
  (4,"D","X",4),
  (5,"E","X",5),
  (6,"A","Y",1),
  (7,"C","Y",2)
).toDF("id","value","group","ts")

import org.Apache.spark.sql.expressions.Window
val w = Window.partitionBy('group).orderBy('id)

次に、lagは必要なものを収集しますが、Column式を生成するための関数が必要です(「AABE」の二重カウントを排除するための分割に注意してください。警告:これは「ABAEXX」タイプのパターンを拒否します"):

def createSeq(m:Int) = split(
  concat(
    (1 to 2*m)
      .map(i => coalesce(lag('value,-i).over(w),lit("")))
  :_*),"A")(0)


val m=2
val tmp = df
  .withColumn("seq",createSeq(m))

+---+-----+-----+---+----+
| id|value|group| ts| seq|
+---+-----+-----+---+----+
|  6|    A|    Y|  1|   C|
|  7|    C|    Y|  2|    |
|  1|    A|    X|  1|BBDE|
|  2|    B|    X|  2| BDE|
|  3|    B|    X|  3|  DE|
|  4|    D|    X|  4|   E|
|  5|    E|    X|  5|    |
+---+-----+-----+---+----+

Column AP​​Iで使用できる収集関数のセットが不十分なため、UDFを使用すると正規表現を完全に回避する方がはるかに簡単です。

def patternInSeq(m: Int) = udf((str: String) => {
  var notFound = str
    .split("B")
    .filter(_.contains("E"))
    .filter(_.indexOf("E") <= m)
    .isEmpty
  !notFound
})

val res = tmp
  .filter(('value === "A") && (locate("B",'seq) > 0))
  .filter(locate("B",'seq) <= m && (locate("E",'seq) > 1))
  .filter(patternInSeq(m)('seq))
  .groupBy('group)
  .count
res.show

+-----+-----+
|group|count|
+-----+-----+
|    X|    1|
+-----+-----+

一般化(範囲外)

より長い文字のシーケンスを一般化したい場合は、質問を一般化する必要があります。些細なことかもしれませんが、この場合、タイプ( "ABAE")のパターンは拒否されるべきです(コメントを参照)。したがって、一般化する最も簡単な方法は、次の実装のようにペアワイズルールを設定することです(このアルゴリズムの動作を説明するためにグループ「Z」を追加しました)

val df = List(
  (1,"A","X",1),
  (2,"B","X",2),
  (3,"B","X",3),
  (4,"D","X",4),
  (5,"E","X",5),
  (6,"A","Y",1),
  (7,"C","Y",2),
  ( 8,"A","Z",1),
  ( 9,"B","Z",2),
  (10,"D","Z",3),
  (11,"B","Z",4),
  (12,"E","Z",5)
).toDF("id","value","group","ts")

まず、ペアのロジックを定義します

import org.Apache.spark.sql.DataFrame
def createSeq(m:Int) = array((0 to 2*m).map(i => coalesce(lag('value,-i).over(w),lit(""))):_*)
def filterPairUdf(m: Int, t: (String,String)) = udf((ar: Array[String]) => {
  val (a,b) = t
  val foundAt = ar
    .dropWhile(_ != a)
    .takeWhile(_ != a)
    .indexOf(b)
  foundAt != -1 && foundAt <= m
})

次に、このロジックを適用する関数を定義します。データフレームに繰り返し適用されます。

def filterSeq(seq: List[String], m: Int)(df: DataFrame): DataFrame = {
  var a = seq(0)
  seq.tail.foldLeft(df){(df: DataFrame, b: String) => {
    val res  = df.filter(filterPairUdf(m,(a,b))('seq))
    a = b
    res
  }}
}

最初の文字で始まるシーケンスで最初にフィルタリングするため、単純化と最適化が得られます

val m = 2
val tmp = df
  .filter('value === "A") // reduce problem
  .withColumn("seq",createSeq(m))

scala> tmp.show()
+---+-----+-----+---+---------------+
| id|value|group| ts|            seq|
+---+-----+-----+---+---------------+
|  6|    A|    Y|  1|   [A, C, , , ]|
|  8|    A|    Z|  1|[A, B, D, B, E]|
|  1|    A|    X|  1|[A, B, B, D, E]|
+---+-----+-----+---+---------------+

val res = tmp.transform(filterSeq(List("A","B","E"),m))

scala> res.show()
+---+-----+-----+---+---------------+
| id|value|group| ts|            seq|
+---+-----+-----+---+---------------+
|  1|    A|    X|  1|[A, B, B, D, E]|
+---+-----+-----+---+---------------+

transformDataFrame => DataFrame変換の単純なシュガーコーティングです)

res
  .groupBy('group)
  .count
  .show

+-----+-----+
|group|count|
+-----+-----+
|    X|    1|
+-----+-----+

私が言ったように、シーケンスをスキャンするときに「リセットルール」を一般化するさまざまな方法がありますが、この例は、より複雑なルールの実装に役立つことを願っています。

6
Wilmerton