# k近傍法とk平均法について

2017 / 12 / 18

## 識別と分類

あるデータにおける何らかのパターンの **識別(Classification)** と **分類(Clustering)** を総称して **パターン認識(Pattern Recognition)** と呼ぶ．以下，簡潔に定義を述べる，

### 識別
与えられたデータの特徴f_1, f_2, ..., f_nから，予め知っているいくつかのクラスc_1, c_2, ..., c_kのどれに当てはまるのかを推論するタスクである．

### 分類
与えられたデータ集合X_1, X_2, ..., X_mを，その特徴に基づいていくつかのデータ集合に分割するタスクである．

ここでは，識別と分類それぞれの代表的な手法である **k近傍法(k-nearest neighbor algorithm)** と **k平均法(k-means clustering)** について述べる．

## k近傍法
識別タスクに適応可能な手法である．ここで，k近傍とは，特徴空間におけるある1つの点との距離が近い順からk個の点からなる集合を意味する．

例えば以下の特徴空間では，
以下がk近傍(k=5)である．

k近傍法では，ある1点の作るk近傍に含まれるデータの所属するクラスの数で多数決を取り，最多クラスをその点のクラスとする．

上の図の例だと，●は○と識別される．

しかし，kの値を大きくすれば，今度は●は×と識別される．

このkの値を決定することがk近傍法における課題の1つでもある．また，同数票を避けるため，kは基本的に奇数とされる．特にk=1の場合，最近傍法とも呼ばれる．

距離尺度としては主にユークリッド距離が用いられるが，他にもマンハッタン距離なども用いられる．

## k平均法
分類タスクに適応可能な手法である．ここで，kは分割数であり，事前に与える必要がある．

例えば以下の特徴空間を考える．

まず，適当なデータをk個選び，距離の近さに応じて全てのデータの所属クラスタを決定する．

そして，各クラスタに所属するデータの平均を計算することでそのクラスタの重心(セントロイド)を更新し，また新たに全てのデータの所属クラスタを決定する．これを繰り返す．

繰り返すことで，全てのデータの所属クラスタが一定に収束する．収束したクラスタが最終的に得られる結果である．


k平均法では，初期のクラスタ重心によって最終的な結果が左右される．そのため，最初の重心の選び方が課題の1つとされている．これを解決した手法として **k-means++** が存在する．
また，kの値が既知でなければならないことから，kを自動的に決定する **X-means** なる手法も存在する．