はじめに
普段は教師あり学習を使用して画像検査の応用を研究しているのですが，文献[1,2]を見ていると教師なし学習でも実用的で面白い結果が得られるのではと思い実装を参考に自身のデータにも試していました．その中で，マハラノビス距離が次元の増加と共に増えていく現象を見ていて次元の呪いは発生するのか気になったため，この記事を書いています．間違いがあるかもしれませんが温かい目で見てもらえると嬉しいです．
結論
入力されるデータが一様分布を仮定するとマハラノビス距離は次元の増加と共に距離も増加することが分かりました．
ソースコード
import numpy as np
from scipy.spatial import distance
dim_list = [2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]
data_num = 100000
np.random.seed(42)
for dim in dim_list:
print(f"dim,{dim}")
feat_X = []
for d_num in range(data_num):
X = np.random.random((dim,))
Y = np.random.random((dim,))
feat_X.append(X)
feat_X = np.array(feat_X)
feat_X_mean = np.mean(feat_X, axis=0)
feat_X_cov_i = np.linalg.pinv(np.cov(feat_X.T))
print(f"feat_X shape,{feat_X.shape}")
print(f"feat_X_mean shape,{feat_X_mean.shape}")
print(f"feat_X_cov_i shape,{feat_X_cov_i.shape}")
euclidean_distance = distance.euclidean(feat_X_mean, Y)
maha = distance.mahalanobis(Y, feat_X_mean, feat_X_cov_i)
print(f"dim, {dim}, euclidean_distance, {euclidean_distance}")
print(f"dim, {dim}, maha, {maha}")
print()
準備
まずは距離の準備です．次元の増加がすでに存在しているユークリッド距離と比較していきたいと思います．
次元の候補：{2, 4, 8, 16, 32, 64, 128, 256, 512, 1024}
データの数：100000個 (一様分布($[0,1.0)$)
X = (x_1, x_2, ...x_{\rm{dim}}) \\
Y = (y_1, y_2, ...y_{\rm{dim}}) \\
\rm{where} \\
dim = \{2, 4, 8, 16, 32, 64, 128, 256, 512, 1024\}
ユークリッド距離
D_{L2} = \sqrt{(X-Y)^T(X-Y)}
マハラノビス距離
D_{maha} = \sqrt{(X-Y)^T\Sigma^{-1}(X-Y)}
ここでさらっとだけ解説すると，マハラノビス距離はユークリッド距離にデータの散らばり具合を係数としてかけるため分散共分散行列 $\Sigma$ の逆行列 $\Sigma^{-1}$ を掛け合わせた数式になっています．なので，分散共分散行列が単位行列の時にユークリッド距離と同じになります．また入力するデータは一様分布を仮定するため，分散共分散行列の対角成分以外はほぼ0になり単位行列に近づけたい意図があります．
今回の比較方法は以下の手順で行っています．
1. dim次元のデータXを100000個作り平均及び分散共分散行列の逆行列を求める
1. dim次元のデータYを一様分布 $[0,1.0)$ の範囲で生成する
1. データXの平均と新しく入ったデータYのユークリッド距離とマハラノビス距離をそれぞれ求める
実験結果
dim,2
feat_X shape,(100000, 2)
feat_X_mean shape,(2,)
feat_X_cov_i shape,(2, 2)
dim, 2, euclidean_distance, 0.3923112976578895
dim, 2, maha, 1.3571263606046908
dim,4
feat_X shape,(100000, 4)
feat_X_mean shape,(4,)
feat_X_cov_i shape,(4, 4)
dim, 4, euclidean_distance, 0.644752254520177
dim, 4, maha, 2.2345446964346456
dim,8
feat_X shape,(100000, 8)
feat_X_mean shape,(8,)
feat_X_cov_i shape,(8, 8)
dim, 8, euclidean_distance, 0.7863592005589978
dim, 8, maha, 2.718332502305865
dim,16
feat_X shape,(100000, 16)
feat_X_mean shape,(16,)
feat_X_cov_i shape,(16, 16)
dim, 16, euclidean_distance, 1.1786731267739012
dim, 16, maha, 4.091215687093391
dim,32
feat_X shape,(100000, 32)
feat_X_mean shape,(32,)
feat_X_cov_i shape,(32, 32)
dim, 32, euclidean_distance, 1.731927838761436
dim, 32, maha, 5.996477531699779
dim,64
feat_X shape,(100000, 64)
feat_X_mean shape,(64,)
feat_X_cov_i shape,(64, 64)
dim, 64, euclidean_distance, 2.3969689647370873
dim, 64, maha, 8.285514976256867
dim,128
feat_X shape,(100000, 128)
feat_X_mean shape,(128,)
feat_X_cov_i shape,(128, 128)
dim, 128, euclidean_distance, 3.4282036167430934
dim, 128, maha, 11.8802901681573
dim,256
feat_X shape,(100000, 256)
feat_X_mean shape,(256,)
feat_X_cov_i shape,(256, 256)
dim, 256, euclidean_distance, 4.4731757247985025
dim, 256, maha, 15.462537289283256
dim,512
feat_X shape,(100000, 512)
feat_X_mean shape,(512,)
feat_X_cov_i shape,(512, 512)
dim, 512, euclidean_distance, 6.420827730770516
dim, 512, maha, 22.33331992765139
dim,1024
feat_X shape,(100000, 1024)
feat_X_mean shape,(1024,)
feat_X_cov_i shape,(1024, 1024)
dim, 1024, euclidean_distance, 9.228567692567323
dim, 1024, maha, 32.124943791487
考察
自分が思っていた以上に一様分布を仮定するとマハラノビス距離が増加したことが分かりました．これは，実際の共分散行列を見てみると分散が小さくなっていくことで読み解けます．
dim = 2の時に出力された分散共分散行列
array([[ 0.08357548, -0.00053497],
[-0.00053497, 0.0831366 ]])
dim = 8の時に出力された分散共分散行列
array([[ 8.30611357e-02, 1.27284049e-04, -7.50527636e-05, 4.89396346e-05, -4.00677523e-04, -6.05165471e-05, 2.21935437e-05, 9.74604751e-05],
[ 1.27284049e-04, 8.33038783e-02, 4.99688924e-04, -2.04796902e-04, -3.51604995e-04, 5.70050751e-04, 8.76718798e-05, 1.08555784e-04],
[-7.50527636e-05, 4.99688924e-04, 8.30660281e-02, -1.18739374e-04, -2.86492973e-04, 1.46684824e-04, 7.54361348e-05, 8.47529782e-05],
[ 4.89396346e-05, -2.04796902e-04, -1.18739374e-04, 8.31636987e-02, 1.72708683e-04, 1.47102938e-04, 1.25585743e-04, 3.12308805e-04],
[-4.00677523e-04, -3.51604995e-04, -2.86492973e-04, 1.72708683e-04, 8.35563484e-02, 2.24267209e-04, 1.35502592e-04, -5.04595145e-05],
[-6.05165471e-05, 5.70050751e-04, 1.46684824e-04, 1.47102938e-04, 2.24267209e-04, 8.28400407e-02, -3.38325624e-05, -1.14849109e-04],
[ 2.21935437e-05, 8.76718798e-05, 7.54361348e-05, 1.25585743e-04, 1.35502592e-04, -3.38325624e-05, 8.31931734e-02, -2.61172389e-04],
[ 9.74604751e-05, 1.08555784e-04, 8.47529782e-05, 3.12308805e-04, -5.04595145e-05, -1.14849109e-04, -2.61172389e-04, 8.32954255e-02]])
上記の出力より分散共分散行列における分散が1より小さく対角成分以外の要素は0に近いことが分かります．今回は意図的に共分散の要素を0に近くしたためマハラノビス距離にとっては意図しない入力となっているため，実際の特徴ではもう少し共分散の要素が現れ距離が小さくなる可能性があります．
さいごに
以上の結果からマハラノビス距離は次元の呪いを受けることが分かりました．きっかけは教師なし学習でうまくできるよ！と書かれており実際に自身のデータでも結果は出ていたので距離に関して考えるのは蛇足だと思いますが，考えるきっかけになりそれらしい答えが導き出せたので良かったです．本来であれば距離の計算からうまくクラスタリングができるか？が肝です．もし距離の増加に悩まされた方がこの記事をみて解決の糸口になれば幸いです！