「金塊か、キノコ料理か」（外れ値検出問題）を解く［LOF(local outlier factor)］

LOF(local outlier factor)とは密度ベースの外れ値検出法です。ある点のまわりの密度がほかの点と比べて小さければ小さいほど、LOFの値は大きくなります。したがって、LOFの最も大きいデータを外れ値すればいいことになります。
LOFアルゴリズムについては後述のアルゴリズム概要に書きましたので興味ある方は参考にしてください。

早速結果を見てみましょう。図から明らかなように、８７番目のLOFが突出して大きいので、これが外れ値となります。

library(DMwR)
max.k <- 50
gold.lof <- matrix(0,max.k,100)
for(i in 2:max.k){
  gold.lof[i,] <- lofactor(gold, k=i)  # ここでLOFを計算しています。kはパラメータです。
}

f:id:sudillap:20130325201015p:plain

なお、このグラフはLOFのパラメータ$k$が１０～２０のときの結果です（パラメータ$k$については後述のアルゴリズム編を参照してください）。

ところで、naoya_tさんは「「機械学習基礎」簡単な問題を解いて理解しよう！後篇」で、LOFについて次のように説明されています。

 LOF（Local Outlier Factor）とは

    それぞれのデータ点について、その点からk番目に近い点までの距離を求め、その点のスコアとする
    異常値は近傍にデータ点が少ないため、スコアが大きくなる

こうして得られたスコアが基準値を超えるものを検出する手法です。

naoya_tさんは、LOFのことを距離によるスコアをもとに外れ値を求めるアルゴリズムと書かれているようですが、実際は異なります。LOFは距離をベースとした外れ値検出法ではなく、密度をベースとした外れ値検出法です。事実、距離ベースの方法では外れ値をうまく検出できないという問題意識から、LOFは密度ベースの方法を採用しています。

さらに言えば、この文章からはLOFアルゴリズムには外れ値の判断基準値が内在する、または客観的な基準値が存在するようにも読めますが、そのような基準値はなく、外れ値の判定基準はユーザーが決める必要があります。ただし、後述のアルゴリズムを見ればわかるように、あるデータのLOFが１よりかなり大きければ、そのデータが外れ値だろう、とは言えますが、明確な基準値があるわけではありません。

アルゴリズム概要

LOFのアルゴリズムについて簡単に説明します。詳細は参考文献を参照してください。

まず次の記号を導入します。
$D$：データセット
$k$：任意の正数
$d(p,o)$：データ$p \in D$と$o \in D$の距離

なお、この$D$はRの関数lofactor(data, k)の引数dataに、$k$はkに対応します。

定義１

次の関係を満たすデータ$o \in D$と$p$の距離を、$p$の$k$距離（$k-distance(p)$と記述）といいます。
(i)少なくとも$k$個のデータ$o' \in D-\{p\}$に対して、$d(p,o') \leq d(p,o)$が成り立つ
(ii)高々$k-1$個のデータ$o' \in D-\{p\}$に対して、$d(p,o') < d(p,o)$が成り立つ

定義２

$p$の$k$距離が与えられたとき、$p$の$k$距離近傍[$k$-distance neighborhood of $p$]（$N_{k-distance(p)}(p)$または$N_k(p)$と記述）を次で定義します。
$$
N_{k-distance(p)}(p)=\{q \in D-\{p\}|d(p,q) \leq k-distance(p)\}
$$

すなわち、$N_{k-distance(p)}(p)$は$p$の$k$最近傍の含まれるデータのことです。

定義３

データ$p$の$o$に関する到達可能距離[reachability distance of $p$ with respect to $o$]（$reach-dist_{k}(p,o)$と記述）を次の式で定義します。
$$
reach-dist_{k}(p,o)=\max\{k-distance(o), d(p,o)\}
$$

データ$p$が$o$から離れているときには、両データ間の到達可能距離は単純に両データ間の距離となります。一方、両データが十分近いときには、距離の代わりに$o$の$k$距離が到達可能距離となります。
このようにすると、データ$p$が$o$に近くにある場合の距離$d(p,o)$の変動を緩和することができます。

定義４

$p$の局所到達可能密度[local reachability density of $p$]（$lrd_{k}(p)$と記述）を次の式で定義します。
$$
lrd_{k}(p)=\frac{|N_k(p)|}{\sum_{o \in N_k(p)}reach-dist_{k}(p,o)}
$$

すなわち$p$の局所到達可能密度とは、$p$の$k$最近傍あるデータの到達可能距離の平均の逆数です。

以上で準備が整いましたので、LOF(local outlier factor)を定義しましょう。

定義５

$p$の局所外れ係数［local outlier factor of $p$]（$LOF_{k}(p)$と記述）を次の式で定義します。
$$
LOF_{k}(p)=\frac{\sum_{o \in N_k(p)}\dfrac{lrd_{k}(o)}{lrd_{k}(p)}}{|N_k(p)|}
$$

$LOF(p)$は、$p$の局所到達可能密度と$p$の$k$近傍の局所到達可能密度との平均で、$p$の外れ度合いを表しています。
$p$の局所到達可能密度が小さく、そして、$p$の$k$近傍の局所到達可能密度が高くなるにつれて、$LOF(p)$は大きくなります。

LOFの性質として、かたまっている（密集している）データのLOFは１に近いことが知られています。すなわち、LOFが１に近いデータは外れ値の可能性が低く、１からかなり離れているデータでは外れ値の可能性が高くなります。
実際、課題データのLOFのグラフを見ると、多くのデータのLOFがほぼ１であることがわかります。

さて、定義５からわかるように、LOFにはパラメータ$k$（正の整数）があり、その値はユーザーが指定します。
$k$にはどのような値を指定すればよいのでしょうか。

$k$を変化させると、LOF値が変動します。そこでLOF開発者たちはLOF値の標準偏差の変動が安定し始める時点を$k$の最小値としています。
そこで、開発者と同様な方法で今回の課題データに対するパラメータ$k$の範囲を検討してみました。下図は、LOFの標準偏差のグラフとLOFの最小値、最大値、平均値をプロットしたグラフです（標準化した課題データの場合）。
標準偏差のグラフから判断して、$k=$14～20が妥当と思われます。
f:id:sudillap:20130325204330p:plain

一方、naoya_tさんは元の課題データを標準化されていませんので、その場合の$k$の範囲がどうなるか検討しましょう。次の標準偏差のグラフ（Indexは２から始まることに注意してください）から、およそ$k=$8～15くらいでしょうか。
f:id:sudillap:20130325204352p:plain

naoya_tさんは「ここでは k=3 としていますが、本設問ではk=2～10ぐらいの範囲なら同じ玉がトップに来るようなデータになっています。」と書かれていますので、上述の手順ではなくエイヤッと$k$を決められたのかもしれません。

ところで、論文では$k$の推奨値として、１０～２０を推奨しています。
標準化していないデータに対して、このガイドラインに従った$k$を指定するとどうなるでしょうか。次の図は、$k$（横軸）を変化させたときの外れ値の番号（縦軸）のグラフです。
$k$が１３以上になると外れ値が正解の８７番から１番に変わってしまいます。回答者の中には運悪く、$k=13$以上でLOFを計算してしまい、１番を外れ値とした人もいるかもしれません。
f:id:sudillap:20130325204435p:plain