マンハッタン距離は距離空間
マンハッタン距離は距離空間
\(\mathbb{R}^{n}\)に対し距離関数\(d_{1}:\mathbb{R}^{n}\times\mathbb{R}^{n}\)\(\rightarrow\mathbb{R}\)を
\[ d_{1}\left(\boldsymbol{x},\boldsymbol{y}\right)=\sum_{k=1}^{n}\left|x_{k}-y_{k}\right| \] で定めると、\(\left(\mathbb{R}^{n},d_{1}\right)\)は距離空間になる。
この距離をマンハッタン距離といい、距離空間をマンハッタン距離空間または\(L^{1}\)距離という。
\(\mathbb{R}^{n}\)に対し距離関数\(d_{1}:\mathbb{R}^{n}\times\mathbb{R}^{n}\)\(\rightarrow\mathbb{R}\)を
\[ d_{1}\left(\boldsymbol{x},\boldsymbol{y}\right)=\sum_{k=1}^{n}\left|x_{k}-y_{k}\right| \] で定めると、\(\left(\mathbb{R}^{n},d_{1}\right)\)は距離空間になる。
この距離をマンハッタン距離といい、距離空間をマンハッタン距離空間または\(L^{1}\)距離という。
2次元すなわち平面上で考える。
マンハッタン距離空間の名前の由来は、マンハッタンは縦横に道が区画されていて斜めには移動が出来ないので実際の道のりはこの距離関数で表されるからである。
マンハッタン距離空間の名前の由来は、マンハッタンは縦横に道が区画されていて斜めには移動が出来ないので実際の道のりはこの距離関数で表されるからである。
(0)
非退化性
\(\boldsymbol{x}=\boldsymbol{y}\)のとき、\begin{align*} d_{1}\left(\boldsymbol{x},\boldsymbol{y}\right) & =\sum_{k=1}^{n}\left|x_{k}-y_{k}\right|\\ & =\sum_{k=1}^{n}0\\ & =0 \end{align*} となるので、\(\boldsymbol{x}=\boldsymbol{y}\Rightarrow d_{1}\left(\boldsymbol{x},\boldsymbol{y}\right)=0\)
\(d_{1}\left(\boldsymbol{x},\boldsymbol{y}\right)=0\)のとき、
\begin{align*} d_{1}\left(\boldsymbol{x},\boldsymbol{y}\right) & =\sum_{k=1}^{n}\left|x_{k}-y_{k}\right|\\ & =0 \end{align*} が成り立つためには、\(\forall k\in\left\{ 1,\cdots,n\right\} ,\left|x_{k}-y_{k}\right|=0\)すなわち、\(\forall k\in\left\{ 1,\cdots,n\right\} ,x_{k}=y_{k}\)とならなければいけないがこれは\(\boldsymbol{x}=\boldsymbol{y}\)である。
これより、\(d_{1}\left(\boldsymbol{x},\boldsymbol{y}\right)=0\Rightarrow\boldsymbol{x}=\boldsymbol{y}\)となる。
故に\(\boldsymbol{x}=\boldsymbol{y}\Leftrightarrow d_{1}\left(\boldsymbol{x},\boldsymbol{y}\right)=0\)となり非退化性は満たされる。
対称性
\begin{align*} d_{1}\left(\boldsymbol{x},\boldsymbol{y}\right) & =\sum_{k=1}^{n}\left|x_{k}-y_{k}\right|\\ & =\sum_{k=1}^{n}\left|y_{k}-x_{k}\right|\\ & =d_{1}\left(\boldsymbol{y},\boldsymbol{x}\right) \end{align*} となるので、対称性は満たされる。3角不等式
ミンコフスキーの不等式より、\begin{align*} d_{1}\left(\boldsymbol{x},\boldsymbol{z}\right) & =\left\Vert \boldsymbol{x}-\boldsymbol{z}\right\Vert _{1}\\ & =\left\Vert \boldsymbol{x}-\boldsymbol{y}+\boldsymbol{y}-\boldsymbol{z}\right\Vert _{1}\\ & \leq\left\Vert \boldsymbol{x}-\boldsymbol{y}\right\Vert _{1}+\left\Vert \boldsymbol{y}-\boldsymbol{z}\right\Vert _{1}\\ & =d_{1}\left(\boldsymbol{x},\boldsymbol{y}\right)+d_{1}\left(\boldsymbol{y},\boldsymbol{z}\right) \end{align*} となるので、\(d_{1}\left(\boldsymbol{x},\boldsymbol{z}\right)\leq d_{1}\left(\boldsymbol{x},\boldsymbol{y}\right)+d_{1}\left(\boldsymbol{y},\boldsymbol{z}\right)\)となる。
-
これより、非退化性・対称性・3角不等式を満たすのでマンハッタン距離は距離空間になる。(0)-2
3角不等式を直接計算してみる。1次元ユークリッド空間の3角不等式\(\left|a+b\right|\leq\left|a\right|+\left|b\right|\)を使うと、
\begin{align*} d_{1}\left(\boldsymbol{x},\boldsymbol{z}\right) & =\sum_{k=1}^{n}\left|x_{k}-z_{k}\right|\\ & =\sum_{k=1}^{n}\left|x_{k}-y_{k}+y_{k}-z_{k}\right|\\ & \leq\sum_{k=1}^{n}\left(\left|x_{k}-y_{k}\right|+\left|y_{k}-z_{k}\right|\right)\\ & =\sum_{k=1}^{n}\left|x_{k}-y_{k}\right|+\sum_{k=1}^{n}\left|y_{k}-z_{k}\right|\\ & =d_{1}\left(\boldsymbol{x},\boldsymbol{y}\right)+d_{1}\left(\boldsymbol{y},\boldsymbol{z}\right) \end{align*} となるので、\(d_{1}\left(\boldsymbol{x},\boldsymbol{z}\right)\leq d_{1}\left(\boldsymbol{x},\boldsymbol{y}\right)+d_{1}\left(\boldsymbol{y},\boldsymbol{z}\right)\)となる。
ページ情報
| タイトル | マンハッタン距離は距離空間 |
| URL | https://www.nomuramath.com/sjp1u0rg/ |
| SNSボタン |
離散位相は距離化可能
離散位相$\left(X,2^{X}\right)$は離散距離空間$\left(X,d\right)$で距離化可能である。
距離空間ならば第1可算公理を満たす
完備距離空間の像は完備部分集合とは限らない
完備距離空間の像は完備部分集合とは限らない
距離空間での内点(内部)・外点(外部)・境界(境界点)・触点(閉包)・集積点(導集合)・孤立点の定義
\[
\exists\epsilon>0,U_{\epsilon}\left(x\right)\subseteq A
\]