BigQueryで時系列データから異常部位検出 (k近傍法) - アクセス解析担当者のBigQuery日記

概要

手法についてはこちらの異常部位検出の解説部分が、分かりやすかったです。
www.albert2005.co.jp

用途としては、ネット広告について言うと、配信全体の異常なクリック増加・減少や、特定のキーワードの異常検知に使えると考えている。
具体的に何をやっているかと言うと、例えばある日の異常度として、その日の直近7日と、それ以前の連続した7日との距離を計算し、距離の最小値を出している。

※異常検知にはいくつか手法がありますが、k近傍法を使おうと思ったのは、BigQueryで実装が簡単そうだったからです。

なお、今回はBigQueryのUDFを使っているが、UDFについての詳細な解説はしない。
cloud.google.com

今回のゴール

異常度を計算し、データポータルで可視化

アウトプットのイメージ

f:id:sem-aa-bq:20190208225648p:plain — 異常度をデータポータルで可視化

青がデータで、赤が計算された異常度。左始まりの時系列データとして処理している。左の方、即ち時系列の最初の方で異常度が高く出ているのは、計算上やむを得ない部分だが、真ん中あたりで、青いグラフがそれまでと異なる動きをした際に、それに追従して赤の異常度も高くなっている。

今回のキーワード

UDF
ARRAY_AGG関数
ウィンドウ関数
サンプルデータ生成

コードサンプル

#StandardSQL
CREATE TEMPORARY FUNCTION calc_min_distance(part_arr ARRAY<FLOAT64>,part_arr_arr ARRAY<STRUCT< inner_arr ARRAY<FLOAT64>>>) RETURNS FLOAT64
LANGUAGE js AS """
  function calc_distance(x,y) {
    if(x.length != y.length) {
      return null
    } else {
      var d = 0
      for(var i = 0;i<x.length;i++){
        d += Math.pow(x[i] - y[i],2)
      }
      return Math.sqrt(d)
    }
  }
  
  var ret = null
  if(part_arr_arr == null){
    return ret
  }
  for(var i = 0 ; i < part_arr_arr.length;i++){
    var distance = calc_distance(part_arr,part_arr_arr[i].inner_arr)
    if(distance!=null){
      if(ret==null || ret > distance){
        ret = distance
      }
    }
  }
  
  return ret
""";
WITH
  sample1 AS (
    #およそ周期が7のデータを生成する
  SELECT
    x AS id,
    3 + 10 * SIN( x * 3.14 /3.5) + RAND() AS x
  FROM
    UNNEST(GENERATE_ARRAY(0,100)) AS x ),
    sample2 AS (
    #異常値を載せたデータを作成する
  SELECT
    *,
    IF(id = 50,x + 10,x) AS abnomal_x
  FROM
    sample1
  ),
  #####################
  #k近傍法による異常検知の実装
  #####################
  t1 AS (
     #部分系列の生成
  SELECT
     *,
     ARRAY_AGG(abnomal_x) OVER(ORDER BY id asc ROWS BETWEEN 6 PRECEDING AND CURRENT ROW) AS part_arr # 6 PRECEDINGを、使用したい系列の長さにより変更してください
  FROM sample2
  ),
  t2 AS (
    #比較したいウィンドウで、部分系列の系列を生成します。
    SELECT
      *,
      ARRAY_AGG(STRUCT(part_arr)) OVER(ORDER BY id asc ROWS BETWEEN 30 PRECEDING AND 1 PRECEDING)　AS part_arr_arr # 30 PRECEDINGを、比較したいウィンドウサイズにより変更してください
    FROM
      t1
  )
  SELECT
    id,
    abnomal_x,
    calc_min_distance(part_arr,part_arr_arr) AS min_distance
  FROM
    t2

解説

上から順に見ていく。

UDF部分

まず、UDFで異常度の計算部分する関数を定義している。javaScriptで書いているおり詳細は省略するが、ざっくりした処理のイメージは下記である。

ざっくりした処理のイメージ

引数として、part_arrとpart_arr_arrを受け取る

part_arr = [1,2,3,2,1,4,3]
part_arr_arr = [
{inner_arr : [2,3,4,5,6,4,1]},
{inner_arr : [3,4,5,6,4,1,5]},
{inner_arr : [4,5,6,4,1,5,2]},
{inner_arr : [5,6,4,1,5,2,3]},
{inner_arr : [6,4,1,5,2,3,3]},
{inner_arr : [4,1,5,2,3,3,2]},
{inner_arr : [1,5,2,3,3,2,4]},
{inner_arr : [5,2,3,3,2,4,3]},
...
]


part_arr([1,2,3,2,1,4,3])と、part_arr_arrの1つめの要素の配列([2,3,4,5,6,4,1])を比較、距離はd1,
part_arr([1,2,3,2,1,4,3])と、part_arr_arrの2つめの要素の配列([3,4,5,6,4,1,5])を比較、距離はd2,
...

距離の最小値は dn
dnを関数の処理結果として返す

※なお、part_arr_arr内の要素をオブジェクトとして格納しているのは、BigQueryがネストしたARRAYを扱えないためである。

ARRAY<ARRAY<INT64>>
（サポート対象外）
これは無効な型の宣言です。マルチレベル ARRAY の作成方法を調べるためにこのページにアクセスした場合に備え、ここに記載しておきます。ARRAY には直接 ARRAY を含めることはできません。代わりに次の例をご覧ください。

ARRAY<STRUCT<ARRAY<INT64>>>
64 ビット整数の ARRAY からなる ARRAY。ARRAY には直接他の ARRAY を含めることができないため、2 つの ARRAY の間に STRUCT が挿入されています。

cloud.google.com