データサイエンス設計マニュアル

318 10 章 ネットワーク分析と距離

10.8 演習問題

距離

10-1. [3] ユークリッド距離がメトリックであることを証明しなさい。

10-2. [5] すべての p ≧ 1 で L

p

距離がメトリックであることを証明しなさい。

10-3. [5] すべての p ≧ 1 で次元ごとに重みを付けられた L

p

距離がメトリックであることを証明しなさい。

10-4. [3] (a) コ

サイン距離はメトリックではないことと (b) 単位長ベクトルの角距離はメトリックであるこ

とが納得できるようなデータを使った実験をしなさい。

10-5. [5] 文字列の編集距離がメトリックを定義していることを証明しなさい。

10-6. [8]

長さ

1

の直線から一様、独立に選ばれた

2

つの点の距離の期待値が

1/3

であることを示しなさい。

この距離の期待値の上限と下限を納得できるように示すことができれば、部分点とする。

最近傍分類

10-7. [3] 与えられた点 p が 2 次元で表現できる最近傍の点の数を求めなさい。ただし、同順位もある。

10-8. [5] 前問の続き。同じく 2 次元で与えられた点 p が最近傍の点として表現できる異なる点の最大数を

求めなさい。

10-9. [3] 最近傍の点を使って分類するとすべての点の分類が誤りになるような 2 次元の n ≧ 10 個の点で

2 クラスの点の集合を作りなさい。

10-10. [5] 3 個の近傍点（k = 3）に従って各点を分類するようにして、前問を繰り返しなさい。

10-11. ...