KATOエンジニヤリング開発日誌

「アウトプット無きエンジニアにインプットもチャンスも無い」の精神で書いています

「なっとくアルゴリズム」を読んだ - k近傍法 -

前回に続いて「なっとくアルゴリズム」を読んで理解したことのまとめです。

www.kato-eng.info

k近傍法

k近傍法は単純だが有益なアルゴリズムである。何かを分類しようとしているときはk近傍法を最初に試してみるとよい。

オレンジとグレープフルーツの分類

オレンジとグレープフルーツを色とサイズで分類すると次のようになる。

f:id:masayuki_kato:20171011101556j:plain

大きくて赤いのがグレープフルーツだと言える。ここで得体の知れないフルーツをプロットする。

f:id:masayuki_kato:20171011104659j:plain

このフルーツをオレンジかグレープフルーツかに分類するため、得体の知れないフルーツの点に最も近い3つの近傍を調べてみる。

f:id:masayuki_kato:20171011105258j:plain

近傍の数はグレープフルーツよりオレンジの方が多いので、得体の知れないフルーツは恐らくオレンジであると考えられる。

この一連の流れがk近傍法である。

特徴抽出

上記の例では大きさと色でフルーツの比較をした。この「大きさ」と「色」が特徴、あるいは特徴量と呼ぶ。

次の図ではフルーツAとフルーツBが似ており、フルーツCは似ていないのが分かる。

f:id:masayuki_kato:20171011110134j:plain

これを見た目ではなく数値で表すにはピタゴラスの公式を使う。

{\sqrt{(x1 - x2)^2 + (y1 - y2)^2}}



フルーツAとフルーツBの距離をピタゴラスの公式を使うと次のようになる。

{\sqrt{(2 - 2)^2 + (2 - 1)^2}}

{= \sqrt{0 + 1}}

{= \sqrt{1}}

{= 1}

フルーツAとフルーツBの距離は1である。



フルーツAとフルーツCの距離をピタゴラスの公式を使うと次のようになる。

{\sqrt{(2 - 4)^2 + (2 - 5)^2}}

{= \sqrt{4 + 9}}

{= \sqrt{13}}

フルーツAとフルーツCの距離は約3.6である。



フルーツBとフルーツCの距離をピタゴラスの公式を使うと次のようになる。

{\sqrt{(2 - 4)^2 + (1 - 5)^2}}

{= \sqrt{4 + 16}}

{= \sqrt{20}}

フルーツBとフルーツCの距離は約4.5である。

回帰

k近傍法でグループに分類することを上記で記載してきたが、k近傍法は数値などの回答を予測することもできる。

パン屋が下記の特徴量から、その日に焼くパンの数を予測するときを例にする。

  • 特徴量
    • 天気
      • 1から5段階で表す(1=悪天候、5=晴天)
    • 土日祝日であるか
      • 土日祝日の場合は1、それ以外は0
    • 近くでイベントがある日かどうか
      • イベントがある日は1、ない日は0

この特徴量の組み合わせの過去のパンの販売数と予測したい日の特徴量は次の通り。

A = (5, 1, 0)  300本販売
B = (3, 1, 1)  225本販売
C = (1, 1, 0)  75本販売
D = (4, 0, 1)  200本販売
E = (4, 0, 0)  150本販売
F = (2, 0, 0)  50本販売

予測したい日 = (4, 1, 0)  

※括弧内は(天気, 土日祝日, イベント)の特徴量

ピタゴラスの公式を使うと次のような距離がわかる。

A = 1
B = 2
C = 9
D = 2
E = 1
F = 5

距離が近いのは「A, B, D, E」なので、これらの日のパン販売数の平均を計算すると218.75本となる。この数が今日焼くべきパンの本数であると予測できる。