二分探索木の平均探索回数(失敗時)に関するメモ

Isolation Forestの論文に出てくる

c(n) = 2H(n-1)-(2(n-1)/n)

を理解するためにあちこち調べて苦労してしまったのでメモ。

これは二分探索木の平均探索回数(失敗時=外点に到達)を意味している。そのため二分探索木について詳しく記述されている文献や発表資料を見ると、あちこちで証明つきで説明されている。

結局僕が理解できたのは日本語書籍の「アルゴリズムの基礎とデータ構造」のおかげ。Isolation Forestの場合には内点と外点の数え方の関係なのか、上の式は右側がn-1を中心に構成されている。仮に1つずらしてn-1をnとした場合には

c(n)=2H(n)-(2n/n+1)

となる。そしてこれは「アルゴリズムの基礎とデータ構造」で導出される

c(n)=2H(n+1)-2

と同じである。

この式の導出には「アルゴリズムの基礎とデータ構造」のP.99上の方にある

c(n+1)=c(n) + 2/(n+2)

という式がキモになるのだが、この式に至る過程は(この書籍に紹介されている以外のものも含めて)結構面倒くさい。

しかし実は上の式は直感的に理解できるので、その内容をここにメモしておく。

c(n)はn個の内点から構成され得るさまざまな形の、すべてのパターンの木におけるすべての外点のパス長の平均値である。上の式に出てくるのはどちらもcであるので、平均値についてのみ考えればよい。

n個の内点から構成される木(Tnとする)がn+1個の内点から構成される木(Tn+1とする)に変わるときには、Tnでは外点だったある1つの点(vとする)が内点に変わり、さらにその内点に2つの外点がぶら下がることになる。

前述したように「平均についてのみ考える」ことにする。実際には根に近い(浅い)ところにいる点も、深い所にある点も存在しているのだが、それらを全て仮の平均化、均質化された世界に移して考えてみる。するとTnのすべての外点のパス長はc(n)である。このうちの1つがvである。

Tn+1では、vは内点になってしまったが、その内点の先に2つの外点がある。この2つの外点のうち1つは、Tnで外点だったvが移動した先だと考えよう。すると平均値+1の長さの外点となる。もう一方の外点はnがn+1になった際に追加された外点だと考える。こちらもvと同じように平均値+1の長さの外点である。(ここでの平均値はTnについてのものであり、Tn+1ではない)

この2つの外点以外の全ての外点は、まったく長さが変わっていない。つまりすべての外点について平均からの変動を考えると、全体で2だけ増えているのである。

この「増えた2」も平均値として考える場合は全ての外点において平均的に増えたと考え直す必要がある。そのため2を外点の数すなわち「n+2」で割った2/(n+2)が、その差となる。

つまりc(n)に2/(n+2)を足したものがc(n+1)になるのだ。

おしまい。

XBOS Anomaly Detection

What is XBOS?

Cross interaction based outlier score (XBOS) is a cluster-based algorithm for unsupervised anomaly detection. It uses k-means clustering for the first stage, and then calculate cross interaction between clusters as the second stage. Because of this second stage, A small cluster near another large cluster is treated as if that is a middle cluster, so that the data points belong to the cluster is scored ‘not so anomalous’ as a result.

XBOS assumes independence of the features as same as HBOS. XBOS shows very good performance on Kaggle credit card dataset compared to Isolation Forest and HBOS.

kaggle1.png

XBOS is a really simple algorithm and implemented in just 55 lines of Python code.

Source code is available at GitHub.

Stravaヒートマップで米軍(?)の裏道ぽいの

Stravaのヒートマップが面白い。筆者は横浜市港南区在住で、たまに鎌倉・逗子・田浦あたりのハイキングに出かける。神武寺駅の北側にはいい山があるのに、米軍施設であるため探索することができない。

山レコの地図でこのエリアを見てもらえればわかるが、基本的にハイカーがこのエリアに入っている様子は無い。

Stravaでみたところ、どうやら米軍関係者にも山を愛するものがいるようで、下図の紫の矢印の2つの裏道が存在するようだ。どちらもハイキングコース(紫矢印の上、斜めに地図を横切る、やや明るいオレンジのライン)に到達している。実に興味深いw

繰り返しになるがこの2本のラインは山レコ登録者が通っている形跡はない。

この2つの道に一般人が入ると、おそらく怖いひとに怒られるのだろうと思う。今度、合流点がどうなっているのか気にしながら歩いてみようと思う。

strava_ikego

単純なラベルよりもスコアや確率で表現する方がよい…説

いわゆる教師有り学習の「ラベル」は、例えば

  • このインスタンスはクラス2です
  • このインスタンスはクラス3です
  • このインスタンスはクラス3です

という形で与えられる。これは一般的なので皆あまり疑問に思わなくなってしまっているかもしれないが、実は情報量としてはかなり少ない状態だ。

  • このインスタンスは明らかにクラス2です。
  • このインスタンスはクラス2に近いが、クラス3です
  • このインスタンスは明らかにクラス3です。

という形の方が、より情報量が多い。

普段ベイジアンネットワークを使っていると「迷いのない状況」と「迷う状況」が確率の値として出てくるので、個別にチューニング等がうまくいっているか(=モデルが良くできているか)を把握しやすくかなりいい。
そのため、前者のような「単純なラベルのみが付与されたデータに基づくデータサイエンス」が圧倒的に良く使われている状況に疑問を持っていた。もっとスコアや確率的な情報が与えられる方が良いのではないか、と。

今日偶然アノマリ検知について調べていたら

http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0152173
の「Anomaly Detection Algorithm Output」の項目で(つまり正確には教師有りデータのラベルではなくモデルの出力に関する項目だが)

First, a label can be used as a result indicating whether an instance is an anomaly or not. Second, a score or confidence value can be a more informative result indicating the degree of abnormality.

という記述に出会うことができて、自分がモヤモヤ思っていた事が間違いではなかったと確信できてよかった(興味ある人はこの項全体を読むことをオススメ)。

大量のラベルなしデータを異常検知にどう活かすか

先のエントリで紹介したアノマリ検知の性能評価用フレームワークを作る際に思いついた手法は

インスタンスを正しいクラスに分類できたかどうか(あるいはできなかったかどうか)

ではなく、

あるインスタンスがあるクラスである、と「どの程度の確信の強さで分類するか」

に注目してみた。これはノリとしてはloglossに似ている。モデルがはじき出した結果そのものではなく確率(あるいはスコア)を見る。

http://data.gunosy.io/entry/2016/08/05/115345
より引用
『予測モデルの出力が特定のクラスに属する確率であることが多いので』
『上図の場合には、予測モデル2の評価が高くなります(Multi-class logarithmic loss自体は0に近い方がよい)。
Accuracyで評価した場合には予測モデル1、予測モデル2の双方とも同じ評価になります。』

 

アノマリ検知のモデルを作った後、評価を下記の2つのデータセットで行う。

  • ラベル付きの、少量の「異常」のデータのみのデータセット
  • ラベルなしの大量のデータからなるデータセット。こちらはラベルは付いていないが実際には「正常」と「異常」両方を含む。「正常」が「異常」よりもかなり多いことはわかっている。つまり現場で収集するのが容易なもの。

上記2つのデータセットをそれぞれをA,Bとする。

モデルに求められることは

  • Aを適切な確率(あるいはスコア)で「異常である」と分類(認識)すること
  • Bのデータに対する「異常である確率(あるいはスコア)」の平均値が、より低いこと(この理由は、Bは多くの正常なデータを多く含むため)

の両方を満たすこと。

2つモデルを作って、それぞれについて下記v1/v2を計算する

  • Aの全データについての「異常である」確率(あるいはスコア)の平均値(v1)
  • 同じくBについての平均値(v2)

v1が適切な範囲であれば、v1とv2の差が大きい方が、より優れたモデルである、と言えることになる。これによって複数のモデルの比較を定量的に行うことが可能になる。

上記手法により、ラベル無しの大量のデータを使って自動的にモデルの性能を高めることなどが可能になり特徴エンジニアリング等が客観的に実施できるようになる。

この手法は偶然思いついたのだが、たぶん既に研究者が発見しているのではないかと思う。これから探してみて、見つけたら追記する予定。

(2018/01/23追記)

散々論文等を読み漁ったが、この手法(おそらくメタアルゴリズムに分類されるものだと思う)は誰も紹介していないようだった。もしかしたら結構すごい発見かも…?

(2020/05/03追記)

これは半教師あり学習に分類される方法になると思われるが、Aのデータに対して過剰適合する可能性があるので、それほど最高の方法ではなさそう。Aのデータを増やせば増やすほどよいが、結局Aの数を十分に確保できるのであれば、そのラベル付け(アノテーション)の過程で教師あり学習用のデータを確保できる可能性があり、それならば最初から教師あり学習をした方が精度が高まると考えられる。