K近傍法の核心的な数学的知識は、距離の計算と重みの計算です。予測したい点を中心点とし、その周囲の一定半径内にある既知の点との距離を計算し、上位k個の点を選び、投票を行います。このk個の点の中で、どのクラスの点が多いかによって、予測点がどのクラスに属するかを判定します。

1. 2点間の距離公式

座標系に2つの点、三角形の座標(3,4)と円の座標(7,7)があるとします。図1のように、これらの点間の距離はどのように計算すればよいでしょうか？

一般的にはユークリッド距離、つまり高校で習った2点間の距離公式を使います。図2のように、その本質はピタゴラスの定理です。

a²+b²=c²

ピタゴラスの定理により、2点間の距離は5と計算できます。

図1：直交座標系に2つの点(3,4),(7,7)
 

図2：ピタゴラスの定理を使って2点間の距離を5と計算する

2. 重み

重みとは、ある要素が全体に対する重要度を指します。各要素が占める割合を表すと同時に、要素の相対的な重要度と貢献度を強調します。

例えば、成績評価は平日の成績と試験の成績に分けられ、平日の成績は総成績の30%、試験の成績は70%を占めます。つまり、平日の成績が90点、試験の成績が80点の場合、総成績は90×0.3 + 80×0.7 = 83点になります。

この重みの割合から見ると、学校は平日の成績よりも試験の成績を重視していることがわかります。

3. K近傍法の原理

ここで点(2,5)が与えられたとします。この点は周囲がすべて三角形であるため、容易に三角形のクラスに属すると判別できます。図3のように。

図3：座標系にいくつかの点が分布している
 

図4：新たに点(2,5)が出現する
 

同様に、点(8,5)が与えられた場合も、容易に円のクラスに属すると判別できます。図5のように。

図5：新たに点(8,5)が出現する
 

しかし、点が(5,5)の位置に出現した場合、図6のように、どのクラスに属するかを判別するのは難しいです。周囲に三角形と円の両方があるからです。

図6：新たに点(5,5)が出現する

K近傍法がこの問題をどのように解決するか見てみましょう。図7のように、K近傍法はまず画像中の各サンプル点と観測点との距離を計算します。

図7：すべての点との距離を計算する

次に、距離を小さい順にソートし、上位k個の値を取り出します。ここではk = 5と仮定します。つまり、観測値に最も近い5つの点を取ります。図8のように。

図8：k = 5個の点を取る

そして、この5つの値の中で各クラスの個数を計算し、個数が最も多いクラスが観測値のクラスとなります。例えば、ここで三角形が3個、円が2個であり、三角形の個数が円の個数より多いため、観測値は三角形と判定されます。

この節の冒頭で示した2つの図、図4と図5を思い出してみましょう。k = 5のとき、点(2,5)の周囲の最も近い5つの点はすべて三角形であるため、この点は三角形と判定されます。図9のように。

図9：周囲がすべて三角形の場合は三角形と判定される
 

k = 5のとき、点(8,5)の周囲の最も近い5つの点はすべて円であるため、この点は円と判定されます。図10のように。

図10：周囲がすべて円の場合は円と判定される

http://www.weixueyuan.net/a/919.html