距離の尺度を用いた最近傍法とクラスタリング｜はじめてのパターン認識5章,10章 #3
#1では1章〜2章の内容、#2では3章〜4章の内容を取り扱いました。
#3では5章,10章の内容をベースに距離を用いた識別規則の構築について取り扱えればと思います。
以下、目次になります。
1. 5章内容（k最近傍法; kNN法）
1.1 最近傍法とボロノイ境界(5.1)
1.2 kNN法(5.2)
1.3 kNN法とベイズ誤り率(5.3)
1.4 kNN法の計算量とその低減法(5.4)
2. 10章内容（クラスタリング）
2.1 類似度と非類似度(10.1)
2.2 非階層型クラスタリング(10.2)
2.3 階層型クラスタリング(10.3)
2.4 確率モデルによるクラスタリング(10.4)
3. まとめ＆補足
1. 5章内容（k最近傍法; kNN法）
5章は近傍のサンプルを参考に識別を行う、最近傍法の説明が諸々されています。基本的には5.2のkNNまで理解しておけば、最近傍系のアルゴリズムの理解としては十分だと思います。
アルゴリズムについては非常にシンプルで、直感的に理解しやすい内容です。多少数式がわからないなどあっても直感的なイメージを数式にあてはめていけば理解していけるのではと思います。
1.1 最近傍法とボロノイ境界(5.1)
5.1は距離を用いたベーシックなアルゴリズムである最近傍法（NN; Nearest Neighbor）について説明されています。NN法はとてもシンプルなアルゴリズムで、近傍の学習データ一つに基づいて分類を行うアルゴリズムです。数式は若干難しそうに見えるのですが、見掛け倒しで表している内容自体は難しくありません。ちなみにmin関数を二回使った表記は個人的にはわかりづらいと思います（が、数式はあくまで考えを整理して定義するものであり、絶対的なものではないというのもここから読み取れるという意味では興味深いです）。
ボロノイ境界、ボロノイ領域という言葉が出てくるので、軽く抑えておくと良いかと思います。
1.2 kNN法(5.2)
図5.7のイメージで理解すると良いと思います。数式についてはこちらも定義を元にまとめたものの印象なので、そこまで難しく捉えなくて大丈夫です。
1.3 kNN法とベイズ誤り率(5.3)
5.3は興味があれば読むで、初見の際は飛ばして良いと思います。
1.4 kNN法の計算量とその低減法(5.4)
5.4も興味があれば読むで、初見の際は飛ばして良いと思います。
2. 10章内容（クラスタリング）
10章ではクラスタリングについて取り上げられています。難しいというより概念として言葉を覚える方が中心になると思いますので、抑えておきたい用語についてまとめておきます。
◆ 抑えておきたい用語まとめ
・類似度/非類似度(10.1)
-> クラスタリングの基本的な方法としてはデータ間の類似度や非類似度の値を用いて行われる。
・距離(10.1)
-> 類似度の尺度の一つ。ユークリッド距離がよく使われる。
・方向余弦(10.1)
-> 類似度の尺度の一つ。cosθ。文書分類などに用いることができる。
・ミンコフスキー距離(10.1)
-> ユークリッド距離の一般化（拡張）
・ユークリッド距離(10.1)
-> 日常生活でよく使用する距離の定義
・非階層型クラスタリング/K-means法(10.2)
-> 階層型でないクラスタリングのこと。K-meansが有名。
・階層型クラスタリング/ウォード法(10.3)
-> 階層的にボトムアップでクラスタリングする手法。
・デンドログラム(10.3)
-> 階層型クラスタリングを図式化したもの。
2.1 類似度と非類似度(10.1)
10.1では、クラスタリングを行うにあたって用いる類似度や非類似度を測る基本的な尺度が距離であると述べた上で10.1.1で距離の公理についてまとめられています。
距離の公理は(1)非負性、(2)反射律（距離がゼロなら同じ点）、(3)対称性（経路によらず距離は一定）、(4)三角不等式（ショートカットは存在しない）の四つでまとめられています。一旦は『距離の公理』ってあったな程度の認識で大丈夫だと思います（実際にそこまで意識しないことの方が多いですが、概念があるということだけ把握しておくと視野が広がります）。
10.1.2では、距離尺度としてよく使われるユークリッド距離について触れ、その定義を一般化したミンコフスキー距離を紹介しています。(10.1)がミンコフスキー距離の定義ですが、この式においてa=2、b=2の時にユークリッド距離となります。言葉の整理の際は、どちらがどちらに含まれるかを考えると早く物事を理解できるのですが、ミンコフスキー距離の方が広い概念なので、ミンコフスキー距離はユークリッド距離を含んでいることを把握することが重要です。また、ユークリッド距離以外の有名な例に市街地距離（マンハッタン距離）があり、これはa=1、b=1の場合になります。市街地距離は縦横にしか動けないため、市街地やマンハッタンを例に名付けられています。
また、距離ではないものの類似度の計算によく用いられる方向余弦（cosθ）についても触れられています。cosθは文書分類の簡単なケースを説明するのによく用いられています。実際に文書分類を行いたい際にもPoCの段階などシンプルで直感的に理解したいアルゴリズムを使いたい際はcosθを用いるのもありだと思います。
2.2 非階層型クラスタリング(10.2)
10.2では非階層クラスタリンングについて、例としてK-平均法（K-means法）を用いて解説してくれています。
クラスタリングは大きく階層型クラスタリングと非階層型クラスタリングに分かれるのですが、非階層型クラスタリングの代表例がK-means法です。K-means法はよく例として出てくる話なので抑えておく方が良いと思います。
K-meansのアルゴリズムとしては、クラスの割り当てとクラス毎の平均の更新を交互にするというものです。詳細はアルゴリズム10.1を見ていただければと思います。
ちなみにアルゴリズム10.1のような書き方は、機械学習の本や論文でよく出てくる書き方なので表記に慣れておくのが良いと思います。特に論文などを読む際は、一文一文を読んでいくと非常に時間がかかるので、アルゴリズムや図表から先に読んで本文を読みにいくような読み方もよく行います（文書よりも数式や表や図やアルゴリズムの方が解釈の違いが出にくいので把握しやすいです）。そのため、このような表記に慣れることはより高いレベルの文献を読みこなす上で非常に重要になります。
2.3 階層型クラスタリング(10.3)
10.3では階層型クラスタリングについて解説されています。
アルゴリズム10.2にアルゴリズムが載っているので、アルゴリズム10.1同様ご確認いただけたらと思います。
サンプル間の類似度は尺度として10.1節でまとめた尺度を用いる形になります。とりあえずイメージしやすいユークリッド距離で考えておくと良いと思います。
10.3.1〜10.3.5ではクラスタ間の類似度の定義についてまとめてくれています。色々とまとめてありますが、10.3.5のウォード法が一番精度が良いと書かれているのと、直感的にも妥当なのでウォード法を中心に確認するのが良いかと思います。（10.3.1〜10.3.4は読み流しで良いと思います）
また、10.3では樹形図（dendrogram）についても言及されていますが、図10.5のようなイメージを持つことでクラスタリングのイメージが掴みやすくなるので必ず抑えておくと良いかと思います。
2.4 確率モデルによるクラスタリング(10.4)
他の節に比べ若干レベルが高いので、一旦読み流して良いかと思います。
EMアルゴリズムについては、PRMLの下巻の9章などにも言及があり、そこでEMアルゴリズムの特殊な例がK-means法だということについてまとめられています。詳細の導出は余裕が出てきたタイミングでPRML9章を参照いただくのが良いと思います。
3. まとめ＆補足
概念的にはそれほど難しくないので、一旦は重要なキーワードを整理して覚えるのが中心だと思います。
取り上げていない内容については全体の流れを掴むにあたってそこまで重要でないので、一旦は読み流してしまって大丈夫です。
