元コンサルでデータサイエンティスト

スタートアップでAI関連の事業開発をしています。元コンサルでデータサイエンティスト

Local Outlier Factor (LOF) による外れ値検知についてまとめた

教師なし学習に分類される異常検知技術のなかでも、外れ値検知という分野は近年多くのシステムで導入され始めています。今回は、外れ値検知技術のひとつであるLocal Outlier Factor (LOF) について紹介します。

 

目次

Local Outlier Factor (LOF) とは

LOF はあるデータの集まりの中から外れ値を見つけ出す外れ値検知アルゴリズムのひとつです。原論文*1は2000年に発表で最新技術とは言えないものの、現在も実務に耐えうる検知性能とシンプルな実装が魅力的な手法です。

LOFは空間におけるデータの密度に着目します。特に、自身の点から近傍 k 個の点といかに密かであるかを表す局所密度 (Local density) という指標に注目します。なお、ここでいう 近傍とはある点から最も距離が近い 個の点のことです。この辺りが怪しい方は k-means や k-NNについて確認しておくといいでしょう。

hktech.hatenablog.com

 

 局所密度は、周りにある点との密度であるということをお伝えしました。これを簡単な式で書くと下記のように表すことができます。

 局所密度 = \frac{1}{近傍 k 個の点との距離の平均}

ここで、は考慮する近傍点の数を決めるパラメーターとします。

 図のように、プロット空間に存在するまとまったデータ群を考えると、点 A はデータ群から離れているため外れ値として検出されるべきであるということは言うまでもないでしょう。

まず、点A自身の局所密度について考えます。点Aは近傍の点 (点B, C, D) との距離が大きいため、前述した式より局所密度が低くなることがわかるかと思います。一方で、点B, C, D はそれぞれの近傍点との距離が近いため局所密度が高いといえるでしょう。

f:id:hktech:20180903234744p:plain

この性質に着目することで、外れ値検知を実現するのが Local Outlier Factor (LOF)です。

上記のイメージに注目すると、データ群に含まれている点は、自身の局所密度と近傍点の局所密度が同じような値をとるということは想像できるかと思います。一方で、外れ値である点Aに着目すると、自身の局所密度は低いけれど、近傍点である点B, C, D の局所密度は高くなっていることがわかります。

つまり、自身の局所密度近傍点の局所密度が等しいときほど正常データであり、その差が大きいほど外れ値である可能性が高いと解釈することができます。これを定式化することで、ある点が外れ値である可能性を表す外れ値スコアを求めることができます。 

 

Local Outlier Factor (LOF) のメリットとして、複雑な分布をしているデータにおける外れ値検知にも強いということがあります。このことをPythonとsklearnによる実装を通して確かめた記事を書きました。この記事では、分布が複数に分かれている場合の例について考えています。

 

hktech.hatenablog.com

 

定式化

局所密度 ld は次の式で表現することができます。ここで、 N_k(P) は点 P の 個の近傍点の集合を意味し、その要素として点Qを考えます。

 ld = 1/{\displaystyle \frac{\sum_{Q \in N_k(P)}d(P, Q)}{k}}

前段で、自身の局所密度近傍点の局所密度がいかに異なるかを外れ値スコアで表現したいということはお伝えしました。Local Outlier Factor (LOF) では、これを局所密度の比を用いて表現していきます。

ある点がデータ群からいかに外れているかを表す指標を外れ値スコアとすると、点Pの外れ値スコア lof は次のように表現することができます。

  lof(P) =\sum_{Q \in N_k(P)}\frac{ld(Q)}{ld(P)}/k

この外れ値スコア lof は、大きい値をとるほど外れ値である可能性が高いということを表しています。外れ値検知タスクでは、このような外れ値スコアに閾値を設けることで、それを超えるものを異常値と判断したりすることが多いです。

なお、実際のタスクではこのスコアに対する閾値設定は慎重に行う必要があります。本記事では、閾値の決め方に関する議論は割愛しますが、別記事でそのことについても紹介したいと思います。 

 

まとめ

異常検知技術のひとつである Local Outlier Factor (LOF) について紹介しました。ふたをあけてみると簡単な手法であることはお分りいただけたかと思います。LOFをPythonで実装した例を紹介した記事も書きましたので、ぜひ確認してみてください。

 

関連記事

hktech.hatenablog.com

 

 

異常検知と変化検知 (機械学習プロフェッショナルシリーズ)

異常検知と変化検知 (機械学習プロフェッショナルシリーズ)