K近傍法
k近傍法は以下の手順からなる:
入力と全学習データとの類似度(距離)測定
類似度上位 k 個の選出
選出されたデータの多数決あるいは平均
すなわち「入力とよく似た k 個のデータで多数決/平均する」単純なアルゴリズムである。
例えば環境(気温/湿度/風速)から天気(雨/曇り/晴れ)を予測する分類問題を考える。k=5 のk近傍分類では、過去100日の環境-天気ペアを学習データとし、今日の環境類似度が高い上位 k=5 日をピックアップ、その5日の天気が雨/雨/晴れ/雨/雨であれば多数決で雨と予測する。
言い換えれば、あるオブジェクトの分類は、その近傍のオブジェクト群の投票によって決定される(すなわち、k 個の最近傍のオブジェクト群で最も一般的なクラスをそのオブジェクトに割り当てる)。k は正の整数で、一般に小さい。k = 1 なら、最近傍のオブジェクトと同じクラスに分類されるだけである。二項分類の場合、k を奇数にすると同票数で分類できなくなる問題を避けることができる。
同じ手法は回帰分析に使われる。この場合、オブジェクトの属性値を k 個の最近傍のオブジェクト群の属性値の平均値とする。より近いオブジェクトに大きく重み付けすることもできる。
近傍のオブジェクトは、正しい分類が判っているもの(あるいは回帰分析の場合、属性値が判っているもの)から選ばれる。これをアルゴリズムの訓練例と考えることもできるが、明確な訓練段階は不要である。近傍を選ぶにあたって、各オブジェクトは多次元の特徴空間における位置ベクトルで表される。通常、ユークリッド距離を使うが、マンハッタン距離などの他の距離も原理的には使うことができる。k近傍法は、データの局所的構造に左右されやすい。