BrainPad株式会社ブレインパッドのデータ活用に関する取り組みや製品・サービス開発の裏側、社員の日常などをご紹介します。分析エントリークレジットカードの不正利用検出などに代表される異常検知。用いた異常検知についてご紹介します!こんにちは、アナリティクスサービス本部の安田です。用いた異常検知について、ご紹介します。detection)というのは、データから「いつもとは異なる振舞い」(=異常値)を見つけて、物体や事象の異常を見つけることです。代表的な例としてよく見聞きするのは、クレジットカードの不正利用検出などですね。これは、いつもと違うクレジットカードを用いた購買行動を観測することで、泥棒などによる不正利用を発見することです。不正利用を見つけることができれば、カード会社は口座を凍結するなどの対策を取ることができます。やって我々のクレジットカードも守られているということを考えると、少し異常検知が身近に感じられますよね。Determinant」は、異常値や外れ値に対して頑健な分散共分散行列を推定するためのアルゴリズムです。Determinant」はあくまでも共分散行列を推定するための手法です。そのため異常検知だけではなく、主成分分析などの共分散行列に関係するさまざまな手法、アルゴリズムに対して応用可能です。基本的な手法について異常検知の手法としてはさまざまなものが知られていますが、その中でも最もナイーブな手法としてデータに多変量正規分布を仮定するものがあります。多変量正規分布とは、次のような確率密度関数を持つ多次元の確率分布です。$$多変量正規分布はデータの生成過程に関する知見が無い場合に、最も自然と考えられる確率分布です。異常検知の枠組みでは、この分布を仮定したときに確率的に起こりにくい値を異常値とみなします。やって確率的に起こりにくい値かどうかを判別するかのというと、マハラノビス距離を用います。マハラノビス距離とは以下で定義される、共分散行列(つまり、分散と相関)を考慮した平均からの距離です。$$比べると一目瞭然ですが、多変量正規分布の密度関数の中にマハラノビス距離の二乗が含まれていることがわかります。これは、マハラノビス距離が大きいほど多変量正規分布の確率密度は小さくなる(⇔確率的に起こりにくい)ということを意味しています。マハラノビス距離を用いて実際に異常度を測る場合は、データから標本平均と標本共分散行列を推定して、上記の式に代入することでそれぞれのデータの標本平均からの距離を計算します。マハラノビス距離がどのくらい大きければ異常と判断するかは、マハラノビス距離が従う分布を利用する方法や、あらかじめ異常値だとわかっているデータがあれば、最もよく異常を捉えられるように閾値を設定する方法(=validation)などが用いられます。マハラノビス距離の計算に必要となる標本共分散行列は学習データに異常値が混ざっているとそれに大きく引きずられてしまい、正常データだけを用いて推定を行った場合と大きく結果が異なってしまいます。以下はそのイメージ図です。青い点が正常データ、オレンジの点が異常データ、青い実線が正常データのみを用いて共分散行列を推定したときのマハラノビス距離の等高線、赤い点線は異常データも混ぜて推定したときのものです。正常データのみで学習した場合と異常値を混ぜて推定した場合とで、大きく結果が違っていることが見て取れます。学習データに異常値が混ざっていなければ問題無いのですが、実際の異常を検知するシチュエーションでは学習データに異常値が混ざっていてかつ、そのうちどれが異常なのかがわからない場合が往々にしてあります。そのような場合だと、上記の単純なマハラノビス距離を用いた異常検知手法が、機能しないであろうことは想像に難くありません。Determinant(以下MCD)というのは、異常値に対して頑健な共分散行列の推定アルゴリズムです。統計学において、頑健(robust)というのは、異常値(外れ値)に対してであったり、分布に対してであったりといくつかの意味で用いられます。そのため、本来であれば「~に対して頑健」と書くのが正確だと思うのですが、以下では異常値に対してという意味で単に頑健と表記します。頑健とは何か?と聞かれたとき、はっきりとした定義はやや曖昧ですが、基本的には対象が何であれ、ある手法、モデル、推定量などが前提とする仮定を完全には満たさない状況でも、その結果が大きく変化しないことを指しているのだと考えています。(例えば、異常値に対して頑健であるというならば、異常値がデータに多少入っても推定量が大きく変わらないなど)今回は簡単に実施できるように、異常値の定義に関しては、データの大部分とは明らかに異なる特徴を持つデータ程度にしておきます。異常値に対して頑健な推定量としては、中央値や刈り込み平均などが知られています。頑健性を図る指標としては、以下の2つがよく知られています。function詳細に関してはここでは触れませんが、簡単な意味と例だけをご紹介します。参考程度なので以下は読み飛ばしていただいて構いません。するために必要な標本比率です。$$のように定義されます。イメージとしては、次のような感じです。データ点を20個用意しました(青い点)、そしてこれらの標本平均を赤い点、中央値を黄色い点で表しています。近づけていった様子を、以下のアニメーションに書いています。このようにデータのうち、たったひとつの値を極限に持っていくだけで標本平均という推定量は、データの分布の位置を示すという本来の意味をなさなくなってしまいます。中央値は全く変動しません。ような極端な値を取ることはまずないと思いますが、桁が1つや2つ違う異常値が紛れることは、まぁまぁあります。valueは無限標本系において0.5となります。ならないことを意味しており、中央値が非常に頑健であることがわかります。functionはデータを変更させたときの推定量の変化を確認するものです。微小な変化を与えたものです。functionが大きい場合、データが変わると推定量も大きく変わる可能性があり、頑健性が低いとみなされます。このような指標を用いて、推定量の頑健性が確認されます。Determinant(MCD)って?さて、前置きが長くなりましたが、本題のMCDの説明に入ります。MCDとは頑健な共分散行列を推定するためのアルゴリズムです。どのように頑健な共分散行列を推定するかというと、データの中から予め決めた割合の標本を抽出して共分散行列を推定する操作を繰り返し、その行列式が最小となるようなデータの組合せから推定した共分散行列の推定値を求めます。共分散行列の行列式最小?と思われると思いますが、この(個人的な)直感的理解を以下に述べます。任意の行列に対して、行列式は以下のようにその固有値の総乗で表せます。共分散行列の場合、固有値は主成分分析の主成分の分散に一致します。共分散行列の行列式最小とは、主成分の分散の積(=データのちらばり)が一番小さくなることを意味しています。密集している部分のデータのみを使えば異常値が混ざらなさそう、というのは感覚と一致するのではないでしょうか。equivalent」と呼ばれる、以下のような良い性質があります。推定を行った後、データの場所を一律に動かそうが、回転を加えようが同じ処理をその推定値に行えば、変更後のデータに対して推定を行った結果と同じになるということです。equivalentな変換にあたるので、これらの操作の際にも再計算をしなくて良いことが担保されているのは、大きいです。標本平均や標本共分散行列にもこの性質はあります。これで、MCDの大まかな仕組みがわかりました。標本の一部を取ってきて、共分散行列とその行列式を計算。できれば良いのですが、実際は計算時間の都合から困難です。そのため、実応用に耐えうる高速な次のアルゴリズムが考案されています。Fast-MCDについて先程述べたように、もともとのMCDは非常に計算量が多いです。いう途方もない組合せ数の計算量を必要とします。これは、すべての組合せを計算しているために時間がかかるのですが、我々の目的は共分散の行列式が最も小さくなるサンプルの組合せを見つけることです。そのため、何らかの基準で、常に「今まで計算したものよりもより小さい行列式をもつサンプルの組合せ」を見つけることを繰り返せばよい、というのがこれから説明するFast-MCDの考え方です。具体的には、次の手順で計算を行います。