マハラノビス距離についてアレコレ

マハラノビス距離は好きですか。私は好きです。
好きなので、マハラノビス距離に関するアレコレをすべて詰め込んでしまった。
すると逆に良いタイトルが思いつかない。そしてすごい長い。
また、最近日本語を書くのがつらいので、全部箇条書きで。

# マハラノビス変換

* ユークリッド距離はユークリッド空間における距離であり、ユークリッド空間上のベクトルの長さはノルム（L2ノルム：原点とのユークリッド距離）と呼ばれる
    * 厳密に言えば「ユークリッド距離を距離関数とすれば、ユークリッド空間は距離空間となる」なので、この表現は因果が逆だが、こっちの方が分かりやすいかと・・・
* 実は、ユークリッド空間の各軸（＝特徴量）は直行している（相関が無い）ことが前提である
* しかし一般的なデータの場合、特徴量間には少なからず相関があることがほとんどである
* 特徴量間に相関がある場合の距離として、[マハラノビス距離](https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%8F%E3%83%A9%E3%83%8E%E3%83%93%E3%82%B9%E8%B7%9D%E9%9B%A2) が良く使われる
	* $D_{M}(X)=\sqrt{(X-\mu)S^{-1}(X-\mu)^{T}}$
        * 上記の $X$ は pandas, scikit-learn における DataFrame を想定し (n\_sample, n\_feature) 行列を考えているので、Wikipedia の表記とは行と列が逆（転置している）
        * $S$ はデータの [共分散行列](https://ja.wikipedia.org/wiki/%E5%88%86%E6%95%A3%E5%85%B1%E5%88%86%E6%95%A3%E8%A1%8C%E5%88%97) （ $(X-\mu)^{T}(X-\mu)$ である (n\_feature, n\_feature) 行列（Wikipedia の表記とは行と列が逆））
        * この場合の原点は、各特徴量毎の平均ベクトル $\mu$
        * 行列からベクトルを引き算しちゃっているけど、numpy でも暗黙的に計算してくれるし、良い感じに脳内補間してください
* マハラノビス距離は便利
    * 軸間に相関が無い（ホワイトノイズ化）
    * ｎ次元空間におけるマハラノビス距離の２乗の分布は、自由度ｎのカイ２乗分布に従う
        * 各変数が正規分布に従う場合（ [多変量正規分布](https://ja.wikipedia.org/wiki/%E5%A4%9A%E5%A4%89%E9%87%8F%E6%AD%A3%E8%A6%8F%E5%88%86%E5%B8%83) ）
    * 実際に使う場合、この「各変数が正規分布に従う」ということをあまり気にしないで使っても、意外と良い結果が得られたりする
    * そこで、カイ２乗分布（の [信頼区間](https://ja.wikipedia.org/wiki/%E4%BF%A1%E9%A0%BC%E5%8C%BA%E9%96%93) 的なもの）から外れるものを異常値であるとすれば、「異常検知」（Anomaly Detection）が実現でき、これは意外と良く使われたりする
    * 特徴量の中に、実数の変数だけではなく、バイナリ変数が混じっていても、マハラノビス距離を使うことが出来ちゃったりする
        * バイナリ変数：値として 0 と 1 だけが存在する変数
        * そのまま使っちゃっても意外と大丈夫
	* なので、カテゴリ変数がある場合でも、マハラノビス距離が使える
        * カテゴリ変数をダミー変数化する
        * もちろんマルチコ防止のためにダミー変数を１個削除するんやで
* 特徴量の中にカテゴリ変数（バイナリ変数）が混じっていても距離が計算できるというのは非常に強力なので、是非使いたい
    * 例えば k-Means とか k-Means とか
    * しかし、このようなモデルのライブラリ（scikit-learn 等）は、距離の計算は決め打ちでユークリッド距離を使うことがほとんどで、マハラノビス距離を使うには自前で実装しなければならない
    * そして多くの機械学習モデルはユークリッド距離を使う！
* そこで、ユークリッド距離（L2ノルム）を計算したらマハラノビス距離になるように、データの方を変換してしまえば、色々なライブラリをそのまま使っても距離としてマハラノビス距離を利用することが出来る
* この「ユークリッド距離を計算したらそれは実はマハラノビス距離になるようにデータを変換する」変換を「マハラノビス変換」と呼ぶことにする

# マハラノビス変換の方法

* $X$ を正規化する
    * $\mu=0$ になる
* $S^{-1}$ を [コレスキー分解](https://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%AC%E3%82%B9%E3%82%AD%E3%83%BC%E5%88%86%E8%A7%A3) する
    * $S$ は共分散行列なので、明らかに [対称行列](https://ja.wikipedia.org/wiki/%E5%AF%BE%E7%A7%B0%E8%A1%8C%E5%88%97) である
    * 対称行列の逆行列は対称行列である
        * $A$ を対称行列とする（ $A^{T}=A$ ）
        * 逆行列の定義より $AA^{-1}=I$
        * 両辺の転置を取る $(A^{-1})^{T}A^{T}=I^{T}$
        * 対称行列なので $(A^{-1})^{T}A=I$
        * $A$ を右辺にもっていくと $(A^{-1})^{T}=A^{-1}$
        * $A^{-1}$ は対称行列である
    * よって $S^{-1}=LL^{T}$ のように、コレスキー分解の共役転置は単なる転置になる
	* $L$ は下三角行列とする
* $D_{M}(X)^2=XLL^{T}X^{T}=(XL)(XL)^{T}$
* よって $XL$ を２乗する（内積を取る）とそれがマハラノビス距離の２乗になる
* すなわち $XL$ が求めるマハラノビス変換である

## 頭の整理

* $XS^{-1}X^{T}=X(X^{T}X)^{-1}X^{T}=XX^{-1}(X^{T})^{-1}X^{T}=(XX^{-1})(XX^{-1})^{T}$ じゃないかよ、と思ってしまうことがある
* これは間違い
    * $(AB)^{-1}=B^{-1}A^{-1}$ は、$A$, $B$ ともに [正則行列](https://ja.wikipedia.org/wiki/%E6%AD%A3%E5%89%87%E8%A1%8C%E5%88%97) の場合のみ
    * $(A^{T})^{-1}=(A^{-1})^{T}$ も、$A$ が正則行列の場合のみ
    * $X$ は一般的に正則行列ではない
        * n\_sample >> n\_feature

# で、作った

https://github.com/tetutaro/mahalanobis_transformer/

scikit-learn like な API を持つマハラノビス変換器を作りました。
これであなたも明日からマハラノビス。

# マハラノビス変換とは何かを考える

* 多くの機械学習ライブラリにおける距離の計算はユークリッド距離決め打ちなので、距離としてマハラノビス距離を使うことは難しい
* そこで、ユークリッド距離を計算したらマハラノビス距離になるようにデータを変換した
* これをマハラノビス変換と呼んだ
* このマハラノビス変換には以下のような性質がある
    * 変換された各特徴量（軸）は正規化（平均0, 分散1）されている
    * 軸はすべて直行する（特徴量間の相関を無くす：ホワイトノイズ化）
    * バイナリ変数、そしてダミー変数化すればカテゴリ変数も使うことが出来る
* ３つ目の特徴はマハラノビス変換にしかないが、相関を無くすといえば PCA（主成分分析）も同じような性質を持っている
* PCA と比較し、軸や固有ベクトルについて考えることで、マハラノビス変換とは何なのかを考えたい

## 元となるデータ

![fig1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/84885/b7ee8a1e-c4a0-bc33-ad4b-6d070e78569a.png)

* 元となるデータの精製方法
    * 多変量正規分布に従う乱数を生成
    * さらに各軸（特徴量）が平均0, 分散1 になるよう正規化した
* 上の図の説明
    * データを散布図に表した
    * 赤の矢印が軸（基底ベクトル）を表し、オレンジの矢印が共分散行列の固有ベクトルを表している
* 確認
    * 軸はもちろん直行している
    * 固有ベクトルも勿論直行していて、分散が最も大きい方向（とそれに直行して分散が最も大きい方向）を表している

## PCA（主成分分析）したデータ

![fig2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/84885/157c2e5f-8752-dc3f-4f72-74f44fff2b67.png)

* 上の図の説明
    * 元データを PCA して、そのデータ点を同様に散布図にプロット
    * 元データにおける軸のベクトル（基底ベクトル）を学習した PCA を使って同様に変換したものが、赤の矢印
        * 元の空間がどのように変形されたのかを表す
    * PCA したデータの共分散行列の固有ベクトルがオレンジの矢印
* ここから分かること
    * PCA というのは、空間を回転（＆反転）して、固有ベクトルがちょうど軸（基底）の方向になるようにする変換
        * 元の空間の基底ベクトルを変換しても、それらは長さを変えずまだ直行する
        * 変換した基底ベクトルと変換後の共分散行列の固有ベクトルのなす角が変化しない

## マハラノビス変換したデータ

![fig3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/84885/91afc53d-041c-abbf-102a-8a72a9240a9a.png)

* 上の図の説明
    * 元データをマハラノビス変換して、そのデータ点を同様に散布図にプロット
    * 元データにおける軸のベクトル（基底ベクトル）を学習したマハラノビス変換で同様に変換したものが、赤の矢印
    * マハラノビス変換したデータの共分散行列の固有ベクトルがオレンジの矢印
* ここから分かること
    * マハラノビス変換は、元の空間を縮めたり伸ばしたりしている
        * 元データの基底ベクトルをマハラノビス変換すると、それらは直行しなくなる
    * 縮めたり伸ばしたりすることで、変換後の各軸の相関を無くしている
    * 共分散行列の固有ベクトルも、変換後の軸と一致するとは限らない

## 考察

* PCA とは何か
    * データにおいて分散が最も大きい要素が結果（目的変数）に最も強く影響を与えるという仮説の下、その分散が一番大きい要素とは何かを探すのが、そもそもの PCA の狙い
    * 分散が一番大きい方向とは、固有値（の絶対値）が最も大きい固有ベクトルの方向である
    * そのため、空間を回転（＆反転）させて、固有ベクトルに軸を合わせていくのが PCA
        * 固有ベクトル同士は直行するため、すべての軸を固有ベクトルに合わせるよう回転させれば、変換後の各軸は自然と相関が無くなるが、これは言わば PCA の副産物
    * いわば、PCA とは「データ自体は何もいじらずに、データを見る方向を色々変えて、最も良さげな解釈を探す」方法である
* そもそも軸って何だっけ
    * 例えば、お菓子の味を数値で表現したいとする
    * この時、「甘さ」「しょっぱさ」という２軸で数値化し、お菓子の味を表現するとする
        * この２つだけでは少なすぎるだろうけど（笑）、簡単のため
        * この「甘さ」「しょっぱさ」のデータ（ビッグデータ）と「このお菓子は好きか嫌いか」（アノテーション）を学習し、どんな味がみんな好きな味なのかを予測するのが、AI（機械学習）
    * 要するに、「お菓子の味」というものを表す特徴が、軸（だから特徴量というのだ）
    * 「甘さ」「しょっぱさ」は、良い特徴だと思われる
        * いくら甘くしても、しょっぱくはならない
        * いくらしょっぱくしても、甘くはならない
        * 「甘さ」と「しょっぱさ」には関係が無い、すなわち、相関が無い
    * しかし、もしも「甘さ」「甘じょっぱさ」だったら、悪い特徴だろう
        * 「甘じょっぱさ」が増えても、それは単に「甘さ」が増えたのか、それとも「しょっぱさ」が増えたのか、原因が分からない
        * それはひとえに、「甘さ」と「甘じょっぱさ」にはかなり関係がある、すなわち、相関があるから
    * すなわち、目的を良く表現する特徴、本質を捉えた特徴は、互いに相関が無いはず
* 再び、PCA とは何か
    * 何を軸とするか＝特徴の取り方＝解釈、と言える
    * 特徴量間に相関があるのは、解釈（特徴の取り方）が悪いだろう
    * だからデータを変えずに空間をくるくる回すことで解釈を変え、良い特徴を探そう、というのが PCA
* マハラノビス変換とは何か
    * PCA とは異なり、データ自体を変形させている
        * PCA では分布の形は変わらないのに、マハラノビス変換では分布の形が変わっている
    * これは、良くない特徴量なのは相関があるのが悪いので、無理やりデータから相関要素を取り除くことをやっているに相当すると考える
        * 「甘じょっぱさ」から相関の原因である「甘さ」成分を取り除いて、良い特徴である「しょっぱさ」に変換するように
* まとめ
    * PCA は、解釈（特徴量の取り方）を変えて、良い特徴量を探す方法
    * マハラノビス変換は、解釈自体は良いとして、悪さをする相関成分を特徴量から取り除く方法
* 想定される使い分け
    * PCA
        * 次元削減（分散＝固有値が小さい次元を削除する）
        * 検定（分布を変えたくない）
        * 回帰（分散が重要）
        * バイナリ変数・カテゴリ変数が無い場合
        * そこそこ相関が高い変数がある場合
    * マハラノビス変換
        * 分類・異常検知（ホワイトノイズ化が有効）
        * バイナリ変数・カテゴリ変数がある場合
        * 相関はそれほど高くない場合（逆行列計算がホゲる可能性）

# マハラノビス距離の分布と異常検知

![fig4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/84885/ef38c78d-0b94-db62-8f36-c6d2bafe6974.png)

* マハラノビス距離は異常検知によく使われる
    * データが多変量正規分布に従うならば、そのマハラノビス距離の２乗は、特徴量次元を自由度としたカイ２乗分布に従う
    * で、データが正規分布に従わなくても、結構カイ２乗分布に従ってくれる
        * もちろん、大数の法則とか、２項分布と正規分布の関係とか、色々考えられることはある
    * なので実際に見てみる
* 元となるデータ
    *　多変量正規分布に従うよう乱数で作ったデータなので、理想的なデータになる
    *　実際にマハラノビス変換・ノルム計算で計算すると、上の図のように綺麗にカイ２乗分布に従うことが分かる
* 異常検知を行うには
    * データから異常でないデータだけを使って、マハラノビス距離を計算
    * 異常なデータも、上記で学習した分布を使ってマハラノビス距離を計算
    * 上の図のようなヒストグラムを描き、正常と異常が離れているか確認
    * 離れていれば、その隙間に入るように閾値を設定
        * 離れてない場合は、誤検出のリスクをきちんと算出・想定し、閾値を設定
    * 新しく来たデータに対して、同様に今までの分布を使ってマハラノビス距離を計算し、閾値を超えてたら異常検知
* 上の図での異常検知サンプル
    * すべて正常データなので、とりあえず自由度２のカイ２乗分布の累積密度関数に 0.99 を与えた時の値で閾値を設定
        * 緑の縦線
    * いくつかの正常データが閾値より大きいので、良い閾値ではないが、とりあえず例なので

![fig5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/84885/975ccdeb-4f49-4f63-fdfb-763973e8efd3.png)

* マハラノビス距離が閾値であるデータを生成し、それを逆マハラノビス変換して、下のデータの散布図に境界線を描いた
* このように描いた境界線から、綺麗に分布を認識しており、異常検知できるだろうことが分かる
* いくつかの点は境界線の外にあるが、これは閾値の設定が悪いせい（笑）