Hausdorff距離をpythonで実装してみる

## 数学的な定義
距離空間$(M, d)$内の部分集合$A, B$に対し、Hausdorff距離$d_H(A,B)$は数学的に
$$
d_H(A,B):=\max(\sup_{a\in A}\inf_{b\in B}d(a,b), \sup_{b\in B}\inf_{a\in A}d(a,b)) 
$$
と定義されます。無論 $d(a,b)\in\mathbb{R}$ for $a,b\in M$です。

## pythonで簡易実装
初見で何のことやら？？という感じだったので、試しにカンタンなデータでpythonプログラムを書いてみることにしました。
数学的な定義では、$\inf, \sup$が使われていましたが、プログラムで試せるのは言っても有限個の点ですので、それぞれ$\min, \max$と読み替えていいです
（$\inf, \sup$を使う場合は、その最小っぽい点や最大っぽい点を実現していなくても値は定まるよね、みたいな時に便利っていう感じですね。例：$\sup_{a\in [0, 2)}a^2=4$のように、$a^2=4$を実現するのは$a=2$ですが、残念ながら区間$[0,2)$からはギリギリはみ出していますよね。。）

まずは必要なライブラリの準備：
```py
import numpy as np
from sklearn.metrics.pairwise import euclidean_distances
from matplotlib import pyplot as plt
```

で、Hausdorff距離を実装：
```py
def hausdorff_distance(A: np.array,
                    B: np.array,):
    # とりあえず距離を一通り計算しておく
    distance_matrix = euclidean_distances(A, B)
    # 行方向にまずはinf(データポイントは有限なのでmin)をとり、その後でmax
    dist_1 = distance_matrix.min(axis=0).max()
    # 同じく列方向に
    dist_2 = distance_matrix.min(axis=1).max()
    # 最後に距離行列全体と、Hausdorff距離を返す
    return distance_matrix, max(dist_1, dist_2)
```

データを準備（お手元にデータを用意してもいいと思います）
```py
A = np.array([[0, 0], [1, 1], [2, 2], [3, 2]])
B = np.array([[3, 0], [4, 5], [2, 5]])
```

折角なので、図示してみます。

```py
# Hausdorff距離を求める
distance_matrix, length = hausdorff_distance(A=A, B=B)

# 距離を実現するデータポイントを取り出す
point_X = np.where(distance_matrix == length)[0][0]
point_Y = np.where(distance_matrix == length)[1][0]

# データセットAの描画
plt.scatter(A[:, 0], A[:, 1], label="A", color="red", marker="o")
# データセットBの描画
plt.scatter(B[:, 0], B[:, 1], label="B", color="blue", marker="x")

# どのデータポイントがHausdorff距離を実現しているかを図示します
plt.plot([A[point_X][0], B[point_Y][0]], [A[point_X][1], B[point_Y][1]], color="green")
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/80539/8549b952-6917-40d2-cfbf-f677cf9241a0.png)

## お気持ち的には、
<i>注意！：説明が鬱陶しいので、一旦$\inf$は最小、$sup$は最大、と解釈します（厳密には異なりますが、イメージを掴んでから厳密に考えてもバチは当たらないと思うので、そのお気持ちで。）</i>

まず$\inf d(a,b)$で、$a$または$b$を動かしますよね。
まず、$a\in A$を固定して$b$でいろんな$d(a,b)$の最小値を取る=その点$a$から最短で行けそうな距離の場所($b\in B$)を見つけるってことですよね。
その過程で、例えば、1.3, 3, 1.7,…のような距離の候補が見つけられ、その後に最大値($\sup$)を取っているので、要はその値より小さければ$A$の各点から$B$のどこかしらには行けるだろう、と。
$a,b$の役割を逆転して$b\in B$を固定して$a$を動かします。
で、計算結果としてHausdorff距離が3.5と出たとすると、$A$, $B$どの地点からでも、距離3.5だけ動けば相手側（A内の点ならBのどこか,B内の点ならA内のどこか）にたどり着くことになります。

## 喩え話的には、
$A,B$が国でそれに含まれる各データポイントが港で、輸出入を行うとします。タンカー等でモノを相互にやり取りするイメージです。
$A,B$が輸出入をする時の(最短)航路が定まっている場合に、Hausdorff距離分だけ見ておけば、取り敢えず$A$国の任意の港から$B$国のどこかの港、あるいは$B$国の港を出発にすれば$A$国の港にたどり着くってお話ですかね。

その意味で、Hausdorff距離が小さい、ということはより少ない距離で$A,B$間をやり取りできる(この場合は輸出入できる)、なんたって最大値を取った上で比較しているので、雑ではありますが最大それだけ見込んでおけばいいって意味で。

兎も角いろんなデータで遊んでみて下さい！

## おまけ
Hausdorff距離を使ったGromov-Hausdorff距離$d_{GH}(A,B)$をさっと見ておきますね。
ちゃんと定式化しようとすると長いので、触りだけ。

$A,B$を含んだ距離空間$C$があり、等長写像$\phi_A:A\to C, \phi_B:B\to C$があるとします。
そうすると、$\phi_A(A), \phi_B(B)$は定義から$C$内の距離なので、$d_H(\phi_A(A), \phi_B(B))$が定義できますよね。

で、$\phi_A, \phi_B$を動かして一番小さいやつ！というのがGromov-Hausdorff距離です。数式的には：

$$
d_{GH}(A,B):= \inf_{\phi_A,\phi_B}d_H(\phi_A(A), \phi_B(B))
$$

です。↑の図で言えば、赤い点と青い点が離れていますが、それを極力重ねるように並行移動＆回転した時に、Hausdorff距離を如何に小さくできるか？という話ですね。

さらに$A,B$がコンパクト集合（ex.有限集合、$\mathbb{R}^n$内の有界閉集合）の場合
$$
d_{GH}(A,B)=0 \Leftrightarrow A=B
$$
が[成立する](https://www2.math.upenn.edu/~brweber/Lectures/USTC2011/Lecture%205%20-%20Gromov-Hausdorff%20distance.pdf)ので、「どれだけ離れてるか？」と考えるのも一理ありますね。

## Reference
- [Gromov Hausdorff convergence in Wiki](https://en.wikipedia.org/wiki/Gromov%E2%80%93Hausdorff_convergence)