# ぱたーん認識
* 1/19 小テスト
*
## 距離と類似性

### 特徴について
* 値の大きさに意味のあるもの(体重、身長)
-- **その値をそのまま特徴量として用いることが多い**
* カテゴリーを表すもの(男女、職業、人種など)
-- カテゴリーごとに何らかの数値を与える
-- 数値の大きさに特に意味は無い

### 距離尺度
* パターン同士が、どれだけ似ているか、どれだけ違っているかを測る尺度
* 距離尺度として満たすべき性質
-- 正値性
-- 対称性
-- 三角不等式
* 一般的な距離尺度: ミンコフスキー計量
$$
d^m(X,Y)=(\Sigma|x_k-y_k|^m)^{\frac{1}{m}}
$$

### よく使われる距離尺度
* m = 1: マンハッタン距離
$$
d(X,Y) = \Sigma|x_k-y_k|
$$
* m = 2: ユークリッド距離
$$
d^2(X,Y)=(\Sigma|x_k-y_k|^2)^{\frac{1}{2}}
$$

### ユークリッド距離を計算
* 単純に距離を計算してしまうと、大きな値を持つ属性に大きく影響されてしまう

### 属性値の大きさを揃える
* 基準となるA=(1, 10, 50)に対して、A'=(1, 1, 1)となるように、重み付けW=(1,1/10,1/50)を考える
* 属性の大きさを揃えること
-> 正規化
* Wを距離計算に用いる: 重み付き距離
$$
d(X, Y)=(\Sigma w_k \times (x_k-y_k)^2)^{\frac{1}{2}}
$$
### 属性値の分散を考慮した重み付け
* 平均値からの差分を用いることでも、属性値の大きさの違いの影響を軽減することができる
* どのような重み付けが効果的か？
-> 数値の散らばり方(分散 $\sigma^2$)で正規化する。

### マラビノス距離
* マラビノス距離
* 分散で正規化された距離
$$
d(X, Y)^2 = (X-Y)^T\Sigma^{-1}(X-Y)
$$
$$
d(X, Y) = \sqrt{ (X-Y)^T\Sigma^{-1}(X-Y) }
$$
* $\Sigma$は共分散行列
$$
\Sigma=\left[
\begin{array}{cc}
\sigma^2_1 & 0\\
0 & \sigma^2_2
\end{array}
\right]
$$
### 画像に対しての距離尺度の適用
* 画像パターンに対しては、属性値の正規化重み付けはあまり考えなくてよい事が多い
-- 輝度値の範囲が全画素について共通
-- 画素によって輝度の分散が必ず異なるという前提は持てない
* 画像全体の大きさの影響は必ず考慮する必要がある
* 画素数の大きな画像同士の差分は、画素数が小さな画像同士の差分よりも必ず大きくなってしまう
* 画素数で正規化する or 画像サイズを揃える
### パターン表現と距離尺度
* いろいろなパターンの表現方法があり、それに対応する距離尺度が考えられる
* 距離尺度として満たすべき3つの性質
* 必ずしもこの3条件を満たすものばかりではない
### 線画の類似性
* ハウスドルフ距離
* 二つの図形のなかで、最も相手に近い点の中で最も遠い点同士の距離
* ハウスドルフ距離は、二つの線画の一点同士の距離
* チャンファー距離
* チャンファー距離は、二つの線画全体での最小距離の総和
$$
Ch(I, J)=\Sigma_{i \in I}||i-j||
$$
* このままでは対称性を満たさないので
$$
Ch'(I, J) = max(Ch(I, J), Ch(J, I))
$$
or
$$
Ch'(I, J) = Ch(I, J) + Ch(J, I)
$$
* ハウスドルフ距離も、チャンファー距離も図形の位置関係により、距離が変化してしまう
* 最小チャンファー距離
* 図形を移動、回転させ、最小となったチャンファー距離を図形の類似性と考える

### 文字列によるパターン表現
* 言語(単語、文章)などをパターンとして考える場合（最近ではDNAシーケンス分析など）
* 単語解析
* DNAシーケンス: A,G,C,Tの並びで表現される

### 文字列パターンの距離尺度
* ハミング距離
* 等しい文字数を持つ二つの文字列の中で、対応する位置にある異なった文字の個数
* "toned"と"roses"の間のハミング距離は3
* 編集距離
* レーベンシュタイン距離とも言う
* 文字の挿入や削除、置換によって、一つの文字列を別の文字列に変形するのに必要な手順の最小回数

### 論理表現
* 論理式で表現することもできる
$$
(x_1 = a_1\cdot a_2) \land (x_2 = a_3 \cdot a_4) \land...
$$
### 相互隣接距離
* Mutual Neighborhood Distance(MND)
* $MND(A, B) = NN(A, B) + NN(B, A)$
* NNは最近防
### 木(Tree)とグラフ(Graph)
* 木構造、グラフ構造は、ノードとエッジ(あるいはリンク)から成る
* ノードはパターンを表す
* エッジはノード間のつながりを表す

### Minimum Spanning Tree
* ノードのパターンは空間上の点として表される
* minimum spanning tree
* エッジの距離の合計が最小となるようにノードを繋いだもの

### Frequent Pattern Tree
* 現れるパターンの頻度をもとに木構造を作る
### Tree, Graph間の距離
* 同じ構造をしたもの同士であれば、ハミング距離が適用できる
* 編集距離が適用可能