異常検知アルゴリズム Random Cut Forest(ランダムカットフォレスト)について調べてメモする

概要

異常検知アルゴリズム Random Cut Forest(ランダムカットフォレスト)について、わからない部分を調べた自分用メモ。

---

背景と目的

OpenSearch(旧AWSにあったElasticsearch)では、異常検知(Anomaly Detection)機能として、(Robust) Random Cut Forestというアルゴリズムが用いられている。OpenSearchで使ってみたものの、アルゴリズムとしての動きがよくわかっていない。なので、自分用に関心のある部分に的を絞って、雑多に調べてみる。

---

詳細

参考資料、ツールなど

• [1]Random Cut ForestのPython実装ライブラリ

klabum.github.io

• [2]AWSの人たちが書いたRCFの原論文

proceedings.mlr.press

• [3]OpenSearchのドキュメント

opensearch.org

• [4]RCFを用いた研究例

www.jstage.jst.go.jp

1. 重複するサンプルはどう扱われるのか？異常度の計算にどう影響があるのか？

[1]のPython実装を見る限り、insert_pointメソッド内で、

• 重複したサンプルがあるか調べる
• 重複がある場合は、当該の葉(Leafクラスインスタンス)のプロパティnをカウントアップ

している。そして、codispメソッドで、

            num_deleted = node.n
            displacement = sibling.n
            result = (displacement / num_deleted)

とある。つまり、num_deletedは、異常スコア計算対象となるサンプル自身のn。displacementは、計算対象となるサンプルがぶら下がる分枝(ブランチ)のもう一方にぶら下がるすべてのサンプル数だ。自身だろうが、もう一方側だろうがとにかく

重複サンプルの数は、異常スコア計算時に重みとして効いてくる

ということだ。

実際に、非常にたくさんの同じ値が出現するデータをこのアルゴリズムで動かすと、その値にひっぱられて、重複しないサンプルは重複サンプルたちに比べてかなり大きな異常スコアとなった。もちろん、データの特徴に応じて異常度の評価がなされているので、この結果自体がおかしいわけではないのだが、この大多数の同一値サンプルたちが、異常判定するための正常データ群として意味を持つサンプルかどうか？ということはよく考えねばならないかもしれない。たとえば、機器が停止中のときに値が動かないようなデータ群を学習データとして食わせると、停止中のデータを正常群の代表のように扱われてしまい、運転中で多少ばらついているデータたちの異常度と本当の異常度の差があまりなくなってしまわないだろうか？

2. ハイパーパラメータ ツリーサイズ(tree size)およびツリーの数(num_trees)

OpenSearchでは、ハイパーパラメータはwindow サイズのみとなっており、ツリーサイズやツリーの数は設定できないし、いろいろ参考文献を見てもわからなかった。 ただ、ツリーサイズの設定は、自動的に決められているような気がする。なぜなら、学習に使用するデータ量によって、設定可能な値が決まってくるだろうから。 ツリーの数は、全くわからない。数10～200くらいだろうか？原論文では200を使用している例が載っている。実際にPython実装でやってみると、値を大きくした方が安定している感じはするが、数10でも十分な感じがする。ちょっと、感覚的で何とも言えない。

3. OpenSearchでのwindow size(shingle)の影響

追記中。

window sizeが深く影響していそうな部分は、[1]のPython実装でいうとinsert_pointメソッド内で呼ばれている_insert_point_cutメソッド。

引数のバウンディングボックスとは、値の存在範囲をあらわす行列。window sizeが2以上に設定されると、1サンプルはwindow size次元(※)ベクトルになるから、各次元ごとに値を持つ。具体例でいえば、

x = [
    [1, 3, 5],
    [3, 2, 6],
    [2, 5, 7],
    [4, 4, 4]
]

であれば、3次元

bbox = [
    [1, 2, 4],
    [4, 5, 7]
]

となる。

※次元とは言っているが、RCFが用いられる時系列の場合、時間的に連続したwindow size個の値をまとめたものが1サンプルのデータを構成するので、次元というよりもサンプル内での時刻だが、[1]Python実装内の変数名としてdimensionという文字列が使われているので、次元と呼んでおく。

_insert_point_cutメソッドを具体的に見ていくと、まず、バウンディングボックスの幅とその合計を求めている。上の例でいえば、b_span=[3, 3, 3]、b_rangeは9。

        # 挿入するサンプルがバウンディングボックスから
        # はみ出ている場合は広げる
        bbox_hat = np.empty(bbox.shape)
        bbox_hat[0, :] = np.minimum(bbox[0, :], point)
        bbox_hat[-1, :] = np.maximum(bbox[-1, :], point)
        # バウンディングボックスの幅
        b_span = bbox_hat[-1, :] - bbox_hat[0, :]
        # 幅の合計
        b_range = b_span.sum()

次に、0～9の中で乱数rを求める。

        # 0～幅の合計の間に入る乱数値を1つ生成
        r = self.rng.uniform(0, b_range)

次に、累積和を求めている。上の例でいえば、span_sum=[3, 6, 9]。

        # 幅の累積和を計算
        span_sum = np.cumsum(b_span)

累積和と乱数とを比較。乱数以上のdemensionのうち最小をcut_demensionとする。 上の例でr = 4.5であれば、cut_demension = 1。

        cut_dimension = np.inf
        for j in range(len(span_sum)):
            if span_sum[j] >= r:
                cut_dimension = j
                break
        if not np.isfinite(cut_dimension):
            raise ValueError("Cut dimension is not finite.")

カットポイントcutは、cut_demensionのバウンディングボックス下端 + cut_demensionまでの累積値 - 乱数。つまり、いずれかの次元およびその次元で値が存在する範囲内でのランダムな位置がcutとして選ばれる。

        cut = bbox_hat[0, cut_dimension] + span_sum[cut_dimension] - r
        return cut_dimension, cut

r = 4.5、cut_demension = 1の場合なら、cutは3.5となる。

cut = 2 + 6 - 4.5 = 3.5

---

まとめと今後の課題

特になし。今後も適宜追記する。