---
# System prepended metadata

title: ぱたーん認識

---

# ぱたーん認識
* 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間の距離
* 同じ構造をしたもの同士であれば、ハミング距離が適用できる
* 編集距離が適用可能