局所きょくしょ外はずれ値ち因子いんし法ほう

異常いじょう検知けんちにおける局所きょくしょ外はずれ値ち因子いんし法ほう（きょくしょはずれちいんしほう、英えい: local outlier factor, LOF）は Markus M. Breunig、Hans-Peter Kriegel、Raymond T. Ng、Jörg Sander によって2000年ねんに提案ていあんされたアルゴリズムで、任意にんいのデータ点てんでの、近傍きんぼう点てんに対たいする局所きょくしょ的てきな変動へんどうを測はかることによって異常いじょうを発見はっけんするものである。

局所きょくしょ外はずれ値ち因子いんし法ほうは、コア距離きょり （core distance）や到達とうたつ可能かのう性せい距離きょり （reachability distance）等とうの概念がいねんをDBSCANやOPTICSといったアルゴリズムと共有きょうゆうしており、これらは局所きょくしょ密度みつどの推定すいていに用もちいられる。

基本きほん的てきなアイディア

LOFの基本きほん的てきアイディア：ある点てんの局所きょくしょ密度みつどをその近傍きんぼうのものと比較ひかくする。点てん A は近傍きんぼうと比くらべて局所きょくしょ密度みつどがずっと小ちいさい。

局所きょくしょ外はずれ値ち因子いんし法ほうは局所きょくしょ密度みつどの概念がいねんに基もとづいている。ここでの「局所きょくしょ（locality）」は $k$ 個この最さい近傍きんぼうで与あたえられ、それらの距離きょりによって密度みつどが推定すいていされる。あるオブジェクトの局所きょくしょ密度みつどをその近傍きんぼう群ぐんの局所きょくしょ密度みつどと比較ひかくすることで、密度みつどが同どう程度ていどであるような領域りょういきと、周囲しゅういと比くらべて密度みつどが有意ゆういに低ひくい点てんを特定とくていすることができる。こうした点てんが外はずれ値ちだと考かんがえられる。

局所きょくしょ密度みつどは、その近傍きんぼうから「到達とうたつ（reach）」するのにかかる標準ひょうじゅん的てき距離きょりを使つかって推定すいていされる。局所きょくしょ外はずれ値ち因子いんし法ほうでの「到達とうたつ可能かのう性せい距離きょり（reachability distance）」は、クラスタ内ないでより安定あんてい的てきな値ねが生しょうじるよう追加ついか的てきに定義ていぎされた尺度しゃくどである。

正式せいしきな定式ていしき化か

${\mbox{k-distance}}(A)$ を、オブジェクト $A$ の k 番ばん目めの近傍きんぼうまでの距離きょりとする。ここで k 個この最さい近傍きんぼうとはこの距離きょり以下いかの全すべてのオブジェクトの集合しゅうごうで、「タイ」が存在そんざいする場合ばあいは個数こすうが k より大おおきくなり得えることに注意ちゅういする。k 最近さいきん傍はたオブジェクトの集合しゅうごうを $N_{k}(A)$ と書かく。

到達とうたつ可能かのう性せい距離きょりの図示ずし。オブジェクト B と C は等ひとしい到達とうたつ可能かのう性せい距離きょりを持もつ（k=3）。一方いっぽう、D は k 最近さいきん傍はたではない。

この距離きょりは、到達とうたつ可能かのう性せい距離きょり（reachability distance）と呼よばれる値ねを定義ていぎするのに用もちいられる：

${\mbox{reachability-distance}}_{k}(A,B)=\max\{{\mbox{k-distance}}(B),d(A,B)\}$

つまり、オブジェクト $A$ の $B$ からの「到達とうたつ可能かのう性せい距離きょり」は、それが $B$ の ${\mbox{k-distance}}$ 以上いじょうである限かぎりは、2オブジェクト間あいだの真しんの距離きょりと一致いっちする。$B$ の k 最近さいきん傍はた集合しゅうごう（$B$ のコア（core）。DBSCANクラスタ解析かいせきを参照さんしょう）は全すべて等距離とうきょりだと見みなせる。このような距離きょりを考かんがえるのは、結果けっかをより安定あんてい的てきなものにするためである。これは対称たいしょう的てきでないので、数学すうがく的てき定義ていぎ上じょうの距離きょりにはなっていないことに注意ちゅういする。 （常つねに ${\mbox{k-distance}}$ の方ほうを使つかうのはよくある誤あやまりで、そのような場合ばあいは Simplified-LOF と呼よばれるわずかに異ことなる手法しゅほうになる。）

オブジェクト $A$ の局所きょくしょ到達とうたつ可能かのう性せい密度みつど（local reachability density）は

${\mbox{lrd}}_{k}(A):=1/\left({\frac {\sum _{B\in N_{k}(A)}{\mbox{reachability-distance}}_{k}(A,B)}{|N_{k}(A)|}}\right)$

と定義ていぎされる。これはオブジェクト $A$ の、その近傍きんぼう群ぐんからの到達とうたつ可能かのう性せい距離きょりの平均へいきんの逆数ぎゃくすうをとったものである。$A$ から近傍きんぼうへ到達とうたつする距離きょりの平均へいきんではなく（これは定義ていぎ上じょう ${\mbox{k-distance}}(A)$ に等ひとしい）、近傍きんぼうから $A$ へ到達とうたつする距離きょりの平均へいきんであることに注意ちゅういする。オブジェクトが重かさなっている点てんではこの値ねは無限むげん大だいになり得える。

次つぎに以下いかのようにして、近傍きんぼう群ぐんと局所きょくしょ到達とうたつ可能かのう性せい密度みつどが比較ひかくされる。

${\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)$

これは「近傍きんぼう群ぐんの局所きょくしょ到達とうたつ可能かのう性せい密度みつどの平均へいきん」を「オブジェクト自身じしんの局所きょくしょ到達とうたつ可能かのう性せい密度みつど」で割わったものである。これが $1$ に近ちかい値ねであるとき、オブジェクトはその近傍きんぼうと同どう程度ていど（similar）である（よって外はずれ値ちではない）。$1$ を下回したまわるとき、その点てんは密度みつどが高たかい領域りょういき（内部ないぶ点てん（inlier））に位置いちする。$1$ を有意ゆういに上回うわまわるとき、外はずれ値ちである。

LOF(k) ~ 1 は、近傍きんぼうと同どう程度ていどの密度みつどであることを意味いみする。

LOF(k) < 1 は、近傍きんぼうよりも高密度こうみつどであることを意味いみする。

LOF(k) > 1 は、近傍きんぼうよりも低てい密度みつどであることを意味いみする。

利点りてん

ELKIによって可視かし化かされたLOFスコア。上方かみがた右側みぎがわのクラスタ内ないの局所きょくしょ密度みつどは、下方かほう左側ひだりがわのクラスタに近接きんせつする外はずれ値ちにおける局所きょくしょ密度みつどと同どう程度ていどだが、これらの外はずれ値ちは正まさしく検知けんちされている。

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

局所きょくしょ外はずれ値ち因子いんし法ほうを幾何きか学がく的てきな直観ちょっかんで捉とらえられるのは低てい次元じげんベクトル空間くうかんの場合ばあいに限かぎられるが、このアルゴリズムは非ひ類似るいじ度ど関数かんすう（dissimilarity function）が定義ていぎできるような任意にんいの状況じょうきょうに対たいし適用てきようできる。この手法しゅほうは経験けいけん的てきに、数すう多おおくの設定せってい下かで非常ひじょうに上手うまく働はたらくことが示しめされており、例たとえば侵入しんにゅう検知けんちシステムや加工かこう（processed）分類ぶんるいベンチマークデータに関かんして、しばしば競合きょうごうする手法しゅほうより優すぐれた結果けっかを出だす。

局所きょくしょ外はずれ値ち因子いんし法ほうや類似るいじする手法しゅほう群ぐんは、他たの様々さまざまな問題もんだい、例たとえば地理ちりデータ、動画どうがストリーミング、著者ちょしゃネットワーク（authorship network）における外はずれ値ちの検知けんちに対たいしても容易よういに一般いっぱん化かできる。

欠点けってんおよび拡張かくちょう

出力しゅつりょく値ちが分数ぶんすうであるため、解釈かいしゃくが難むずかしい。値ねが 1 またはそれ以下いかであれば明確めいかくに外はずれ値ちでないと判断はんだんできるが、外はずれ値ちであるかどうかに対たいする明確めいかくな規則きそくは存在そんざいしない。あるデータセットでは値ねが 1.1 であれば外はずれ値ちとされる一方いっぽうで、別べつのデータセットあるいは別べつの（局所きょくしょ的てきな変動へんどうの激はげしい）パラメータの下したでは値ねが 2 であってもなお、外はずれ値ちとされないかもしれない。手法しゅほうの局所きょくしょ性せいのために、こうした相違そういは一ひとつのデータセットの中なかでも発生はっせいし得える。これらの特質とくしつの改善かいぜんを試こころみる、局所きょくしょ外はずれ値ち因子いんし法ほうの拡張かくちょうが存在そんざいしている。

• Feature Bagging for Outlier Detection（外はずれ値ちに対たいする特徴とくちょうバギング） は、データの複数ふくすうの射影しゃえいに対たいして局所きょくしょ外はずれ値ち因子いんし法ほうを実行じっこうし、結果けっかを結合けつごうすることで、高こう次元じげんでの検知けんちの質しつを高たかめる。これは異常いじょう検知けんちに対たいするアンサンブル学習がくしゅうアプローチの最初さいしょの例れいであり、他たの変種へんしゅについては脚注きゃくちゅうを参照さんしょう。
• Local Outlier Probability (LoOP)（局所きょくしょ外はずれ値ち確かく率りつ）は局所きょくしょ外はずれ値ち因子いんし法ほうから派生はせいした手法しゅほうだが、あまり込こみ入いっていない（inexpensive）局所きょくしょ的てき統計とうけい量りょうを用もちいることで、結果けっかがパラメータ k の選択せんたくに鋭敏えいびんに左右さゆうされないようにしている。また出力しゅつりょく値ちは $[0:1]$ 区間くかんの値ねに規格きかく化かされている。
• Interpreting and Unifying Outlier Scores （外はずれ値ちスコアの解釈かいしゃくおよび統合とうごう）は、ユーザビリティ向上こうじょうのために統計とうけい的てきスケーリングを用もちいてLOFの外はずれ値ちスコアを区間くかん $[0:1]$ の値ねへ規格きかく化かすることを提案ていあんするもので、LoOPの改善かいぜん案あんとみることができる。
• On Evaluation of Outlier Rankings and Outlier Scores （外はずれ値ちランキングと外はずれ値ちスコアの評価ひょうか）は、LOFの変種へんしゅや別べつのアルゴリズムを用もちいた、高度こうどな異常いじょう検知けんちアンサンブル構築こうちく法ほう同士どうしの類似るいじ度どおよび相違そうい度どを測はかる手法しゅほうを提案ていあんする。上述じょうじゅつの Feature Bagging for Outlier Detection を改善かいぜんしたものである。
• Local outlier detection reconsidered: a generalized view on locality with applications to spatial, video, and network outlier detection（局所きょくしょ外はずれ値ち検知けんち再考さいこう：空間くうかん・映像えいぞう・ネットワークでの外はずれ値ち検知けんちを用もちいた局所きょくしょ性せいへの一般いっぱん的てき視点してん）は、様々さまざまな局所きょくしょ外はずれ値ち検知けんち手法しゅほう（例たとえば、LOF, simplified version of LOF, LoOP）における一般いっぱん的てきなパターンを議論ぎろんし、一般いっぱん的てきなフレームワークを抽象ちゅうしょうしている。このフレームワークは続つづいて、地理ちりデータ、動画どうがストリーミング、著者ちょしゃネットワーク等とうにおける外はずれ値ち検知けんちに応用おうようされる。