データサイエンス講義 3章「アルゴリズム」 その2

前回は線形回帰の話でしたが、今回はk近傍法について。

データサイエンス講義

3.2.2 k近傍法

通称k-NN(k-Nearest Neighbors)。
あらかじめ分類/ラベル付けされたオブジェクト群から、分類/ラベル付けされていないオブジェクトを自動的に分類/ラベル付けするためのアルゴリズム。

■線形回帰ではできないのか
「閾値」を利用すれば可能。
しかし、以下の問題が存在。
・閾値をどう決めるか。
(e.g.) 従属変数の値が500以上ならラベル「高」を付与。
・元々のデータに定性ラベルが付与されている場合(離散データの場合)にどうするか。具体的にはどう定性ラベルを定量化し、閾値を定めるか。
(e.g.) 好きな政党として、ラベル「自民党」、「民主党」、「公明党」etc.の離散データ

■k-NNの直感的説明
属性が最も似ている他の項目を考慮し、そのラベルを見て多数決で付与するラベルを決定。
kとは、多数決に利用するデータ数と考えて良い。

■k-NNの自動化のために
1.類似度の定義が必要。
2.いくつの近傍を取り出せば良いか。kの設定。

■k-NNのアルゴリズム
1. 類似度/距離指標を決定
- 変数は、同じスケールにする必要有。要正規化。
(e.g.) 変数1はおおよそ1-10の範囲であるが、変数2はおおよそ1,000-10,000の範囲である場合は、変数1,2共に0-1の範囲に正規化する。
- 類似度としては、以下がよく利用される。
・ユークリッド距離
・コサイン類似度
・Jaccard距離
・マハラノビス距離
・ハミング距離
・マンハッタン距離

2. ラベル付けされたデータを用意し、トレーニングデータとテストデータに分類

3. 評価指標を選択
- 誤分類率を利用することが多い
- 再現率(全テストデータの中で、どれだけ正しく分類できたか)
- 適合率(分類できたデータの中で、どれだけ正しく分類できたか)

4. kを変更して評価指標を確認

5. 評価指標が最高になるkを選択

6. 同じトレーニングデータを使い、ラベルを予測したい新テストデータを作成。

■k-NNの前提
・kをヒューリスティックに定める必要がある。
・特定の「距離」を定義する必要がある。
・トレーニングデータは2カテゴリ以上に分類されている必要がある。

■演習(コーディング)
次回掲載予定。

■参考にできそうなページ(学術的)
上手くまとめられたスライド。

はじめてのパターン認識 第5章 k最近傍法(k_nn法)