局所外れ値因子法のソースを表示

{{Machine learning bar}}

[[異常検知]]における'''局所外れ値因子法'''（きょくしょはずれちいんしほう、{{Lang-en-short|local outlier factor, LOF}}）は Markus M. Breunig、{{仮リンク|Hans-Peter Kriegel|en|Hans-Peter Kriegel}}、Raymond T. Ng、Jörg Sander によって2000年に提案されたアルゴリズムで、任意のデータ点での、近傍点に対する局所的な変動を測ることによって異常を発見するものである<ref>{{Cite conference| doi = 10.1145/335191.335388| title = LOF: Identifying Density-based Local Outliers| year = 2000| last1 = Breunig | first1 = M. M.| last2 = Kriegel | first2 = H.-P. | authorlink2 = Hans-Peter Kriegel| last3 = Ng | first3 = R. T.| last4 = Sander | first4 = J.| work = Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data| series = [[SIGMOD]]| isbn = 1-58113-217-4| pages = 93–104| url = http://www.dbs.ifi.lmu.de/Publikationen/Papers/LOF.pdf}}</ref>。

局所外れ値因子法は、コア距離
（core distance）や到達可能性距離
（reachability distance）等の概念を[[DBSCAN]]や{{仮リンク|OPTICS|en|OPTICS}}といったアルゴリズムと共有しており、これらは局所密度の推定に用いられる<ref>{{Cite book| last1 = Breunig | first1 = M. M. | last2 = Kriegel | first2 = H.-P. | authorlink2 = Hans-Peter Kriegel| last3 = Ng | first3 = R. T. | last4 = Sander | first4 = J. R. | chapter = OPTICS-OF: Identifying Local Outliers | doi = 10.1007/978-3-540-48247-5_28 | title = Principles of Data Mining and Knowledge Discovery | series = Lecture Notes in Computer Science | volume = 1704 | pages = 262 | year = 1999 | isbn = 978-3-540-66490-1 | pmid =  | pmc = | url = http://www.dbs.ifi.lmu.de/Publikationen/Papers/PKDD99-Outlier.pdf}}</ref>。

== 基本的なアイディア ==

[[File:LOF-idea.svg|thumb|right|250px|LOFの基本的アイディア：ある点の局所密度をその近傍のものと比較する。点 A は近傍と比べて局所密度がずっと小さい。]]

局所外れ値因子法は局所密度の概念に基づいている。ここでの「局所（locality）」は <math>k</math> 個の最近傍で与えられ、それらの距離によって密度が推定される。あるオブジェクトの局所密度をその近傍群の局所密度と比較することで、密度が同程度であるような領域と、周囲と比べて密度が有意に低い点を特定することができる。こうした点が[[外れ値]]だと考えられる。

局所密度は、その近傍から「到達（reach）」するのにかかる標準的距離を使って推定される。局所外れ値因子法での「到達可能性距離（reachability distance）」は、クラスタ内でより安定的な値が生じるよう追加的に定義された尺度である。

== 正式な定式化 ==

<math>\mbox{k-distance}(A)</math> を、オブジェクト <math>A</math> の ''k'' 番目の近傍までの距離とする。ここで ''k'' 個の最近傍とはこの距離以下の全てのオブジェクトの集合で、「タイ」が存在する場合は個数が ''k'' より大きくなり得ることに注意する。''k'' 最近傍オブジェクトの集合を <math>N_k(A)</math> と書く。

[[File:Reachability-distance.svg|thumb|right|250px|到達可能性距離の図示。オブジェクト ''B'' と ''C'' は等しい到達可能性距離を持つ（k=3）。一方、''D'' は ''k'' 最近傍ではない。]]

この距離は、到達可能性距離（reachability distance）と呼ばれる値を定義するのに用いられる：

<math>\mbox{reachability-distance}_k(A,B)=\max\{\mbox{k-distance}(B), d(A,B)\}</math>

つまり、オブジェクト <math>A</math> の <math>B</math> からの「到達可能性距離」は、それが <math>B</math> の <math>\mbox{k-distance}</math> 以上である限りは、2オブジェクト間の真の距離と一致する。<math>B</math> の ''k'' 最近傍集合（<math>B</math> のコア（core）。[[DBSCAN|DBSCANクラスタ解析]]を参照）は全て等距離だと見なせる。このような距離を考えるのは、結果をより安定的なものにするためである。これは対称的でないので、数学的定義上の距離にはなっていないことに注意する。 （常に <math>\mbox{k-distance}</math> の方を使うのはよくある誤りで<ref name="generalized" />、そのような場合は Simplified-LOF と呼ばれるわずかに異なる手法になる<ref name="generalized" />。）

オブジェクト <math>A</math> の局所到達可能性密度（local reachability density）は

<math>\mbox{lrd}_k(A):=1/\left(\frac{\sum_{B\in N_k(A)}\mbox{reachability-distance}_k(A, B)}{|N_k(A)|}\right)</math>

と定義される。これはオブジェクト <math>A</math> の、その近傍群からの到達可能性距離の平均の逆数をとったものである。<math>A</math> から近傍へ到達する距離の平均ではなく（これは定義上 <math>\mbox{k-distance}(A)</math> に等しい）、近傍から <math>A</math> へ到達する距離の平均であることに注意する。オブジェクトが重なっている点ではこの値は無限大になり得る。

次に以下のようにして、近傍群と局所到達可能性密度が比較される。

<math>
\mbox{LOF}_k(A):=\frac{\sum_{B\in N_k(A)}\frac{\mbox{lrd}(B)}{\mbox{lrd}(A)}}{|N_k(A)|}
= \frac{\sum_{B\in N_k(A)}\mbox{lrd}(B)}{|N_k(A)|} / \mbox{lrd}(A)
</math>

これは「近傍群の局所到達可能性密度の平均」を「オブジェクト自身の局所到達可能性密度」で割ったものである。これが <math>1</math> に近い値であるとき、オブジェクトはその近傍と同程度（similar）である（よって外れ値ではない）。<math>1</math> を下回るとき、その点は密度が高い領域（内部点（inlier））に位置する。<math>1</math> を有意に上回るとき、外れ値である。

LOF(k) ~ 1 は、近傍と同程度の密度であることを意味する。 

LOF(k) < 1 は、近傍よりも高密度であることを意味する。

LOF(k) > 1 は、近傍よりも低密度であることを意味する。

== 利点 ==

[[File:LOF.svg|thumb|right|400px|{{仮リンク|ELKI|en|ELKI}}によって可視化されたLOFスコア。上方右側のクラスタ内の局所密度は、下方左側のクラスタに近接する外れ値における局所密度と同程度だが、これらの外れ値は正しく検知されている。]]

局所外れ値因子法は局所的なアプローチであるため、データセットの別の領域に位置していれば外れ値とはなっていないであろう点も、外れ値として検知できる。例えば、かなり密度の高いクラスタまでの距離が「小さい」点は、（まばらなクラスタ内の点も近傍までの距離は同程度かもしれないが）外れ値になる。

局所外れ値因子法を幾何学的な直観で捉えられるのは低次元ベクトル空間の場合に限られるが、このアルゴリズムは非類似度関数（dissimilarity function）が定義できるような任意の状況に対し適用できる。この手法は経験的に、数多くの設定下で非常に上手く働くことが示されており、例えば[[侵入検知システム]]<ref>{{cite journal | title=A comparative study of anomaly detection schemes in network intrusion detection | year=2003 | authors=Lazarevic, A.; Ozgur, A.; Ertoz, L.; Srivastava, J.; Kumar, V.; | journal=Proc. 3rd SIAM International Conference on Data Mining | url=http://www.siam.org/proceedings/datamining/2003/dm03_03LazarevicA.pdf | pages=25–36}}</ref>や加工（processed）分類ベンチマークデータ<ref name="CamposZimek2016">{{cite journal|last1=Campos|first1=Guilherme O.|last2=Zimek|first2=Arthur|last3=Sander|first3=Jörg|last4=Campello|first4=Ricardo J. G. B.|last5=Micenková|first5=Barbora|last6=Schubert|first6=Erich|last7=Assent|first7=Ira|last8=Houle|first8=Michael E.|title=On the evaluation of unsupervised outlier detection: measures, datasets, and an empirical study|journal=Data Mining and Knowledge Discovery|year=2016|issn=1384-5810|doi=10.1007/s10618-015-0444-8}}</ref>に関して、しばしば競合する手法より優れた結果を出す。

局所外れ値因子法や類似する手法群は、他の様々な問題、例えば地理データ、動画ストリーミング、著者ネットワーク（authorship network）における外れ値の検知に対しても容易に一般化できる<ref name="generalized" />。

== 欠点および拡張 ==

出力値が[[分数]]であるため、解釈が難しい。値が 1 またはそれ以下であれば明確に外れ値でないと判断できるが、外れ値であるかどうかに対する明確な規則は存在しない。あるデータセットでは値が 1.1 であれば外れ値とされる一方で、別のデータセットあるいは別の（局所的な変動の激しい）パラメータの下では値が 2 であってもなお、外れ値とされないかもしれない。手法の局所性のために、こうした相違は一つのデータセットの中でも発生し得る。これらの特質の改善を試みる、局所外れ値因子法の拡張が存在している。

* ''Feature Bagging for Outlier Detection''（外れ値に対する特徴バギング） <ref>{{Cite journal| doi = 10.1145/1081870.1081891| title = Feature bagging for outlier detection| year = 2005| last1 = Lazarevic | first1 = A.| last2 = Kumar | first2 = V.| pages = 157–166| journal = Proc. 11th ACM SIGKDD international conference on Knowledge Discovery in Data Mining}}</ref>は、データの複数の射影に対して局所外れ値因子法を実行し、結果を結合することで、高次元での検知の質を高める。これは異常検知に対する[[アンサンブル学習]]アプローチの最初の例であり、他の変種については脚注<ref>{{Cite journal | doi = 10.1145/2594473.2594476| title = Ensembles for unsupervised outlier detection| journal = ACM SIGKDD Explorations Newsletter| volume = 15| pages = 11| year = 2014| last1 = Zimek | first1 = A. | last2 = Campello | first2 = R. J. G. B. | last3 = Sander | first3 = J. R. }}</ref>を参照。
* ''Local Outlier Probability'' (LoOP)<ref>{{Cite conference| doi = 10.1145/1645953.1646195| isbn = 978-1-60558-512-3| title = LoOP: Local Outlier Probabilities| series = CIKM '09| year = 2009| last1 = Kriegel | first1 = H.-P. | authorlink1 =Hans-Peter Kriegel| last2 = Kröger | first2 = P.| last3 = Schubert | first3 = E.| last4 = Zimek | first4 = A.| pages = 1649–1652| journal = Proceedings of the 18th ACM conference on Information and knowledge management| url = http://www.dbs.ifi.lmu.de/Publikationen/Papers/LoOP1649.pdf}}</ref>（局所外れ値確率）は局所外れ値因子法から派生した手法だが、あまり込み入っていない（inexpensive）局所的統計量を用いることで、結果がパラメータ ''k'' の選択に鋭敏に左右されないようにしている。また出力値は <math>[0:1]</math> 区間の値に規格化されている。
* ''Interpreting and Unifying Outlier Scores'' <ref>{{Cite conference | doi = 10.1137/1.9781611972818.2| title = Interpreting and Unifying Outlier Scores| conference = Proceedings of the 2011 SIAM International Conference on Data Mining| pages = 13–24| year = 2011| last1 = Kriegel | first1 = H. P. | authorlink1 = Hans-Peter Kriegel| last2 = Kröger | first2 = P. | last3 = Schubert | first3 = E. | last4 = Zimek | first4 = A. | isbn = 978-0-89871-992-5| url = http://epubs.siam.org/doi/pdf/10.1137/1.9781611972818.2 | format=PDF}}</ref>（外れ値スコアの解釈および統合）は、[[ユーザビリティ]]向上のために統計的スケーリングを用いてLOFの外れ値スコアを区間 <math>[0:1]</math> の値へ規格化することを提案するもので、LoOPの改善案とみることができる。
* ''On Evaluation of Outlier Rankings and Outlier Scores'' <ref>{{Cite conference | doi = 10.1137/1.9781611972825.90| title = On Evaluation of Outlier Rankings and Outlier Scores| conference = Proceedings of the 2012 SIAM International Conference on Data Mining| pages = 1047–1058| year = 2012| last1 = Schubert | first1 = E. | last2 = Wojdanowski | first2 = R. | last3 = Zimek | first3 = A. | last4 = Kriegel | first4 = H. P. | authorlink4 = Hans-Peter Kriegel| isbn = 978-1-61197-232-0| url = http://epubs.siam.org/doi/pdf/10.1137/1.9781611972825.90 | format = PDF| citeseerx = 10.1.1.300.7205}}</ref>（外れ値ランキングと外れ値スコアの評価）は、LOFの変種や別のアルゴリズムを用いた、高度な異常検知アンサンブル構築法同士の類似度および相違度を測る手法を提案する。上述の ''Feature Bagging for Outlier Detection'' を改善したものである。
* ''Local outlier detection reconsidered: a generalized view on locality with applications to spatial, video, and network outlier detection''<ref name="generalized">{{Cite journal | last1 = Schubert | first1 = E. | last2 = Zimek | first2 = A. | last3 = Kriegel | first3 = H. -P. | authorlink3 = Hans-Peter Kriegel| doi = 10.1007/s10618-012-0300-z | title = Local outlier detection reconsidered: A generalized view on locality with applications to spatial, video, and network outlier detection | journal = Data Mining and Knowledge Discovery | year = 2012 | pmid =  | pmc = }}</ref>（局所外れ値検知再考：空間・映像・ネットワークでの外れ値検知を用いた局所性への一般的視点）は、様々な局所外れ値検知手法（例えば、LOF, simplified version of LOF, LoOP）における一般的なパターンを議論し、一般的なフレームワークを抽象している。このフレームワークは続いて、地理データ、動画ストリーミング、著者ネットワーク等における外れ値検知に応用される。

== 脚注 ==

<references />

{{DEFAULTSORT:きよくしよはすれちいんしほう}}
[[Category:機械学習]]
[[Category:機械学習アルゴリズム]]
[[Category:数学に関する記事]]