kNNによる手書き文字の分類

はじめに

機械学習による手書き文字(数字)の多クラス分類を行う。今回用いる学習アルゴリズムはk近傍法分類器(k-nearest neighbor classifier)である。 kNNは特徴ベクトルとラベルを結ぶような関数(重みやバイアス)を最適化することはなく、逐一入力された特徴ベクトルがどの学習データと類似しているかを求め( $k$ 個のもっとも類似する学習データを拾い)、ラベルを予測する点が特徴的な学習方法である。今回はMNISTの手書き数字を用いて数字の分類を様々な $k$ について実行し、正解率を調べた。

理論

アルゴリズムは以下の通りである。

1. 入力した特徴ベクトルとトレーニングデータとの類似度(距離)を計算する。

2. 入力データからもっとも近い $k$ 個のデータ点を集める。

3. 集めた $k$ 個のデータ点で多数決をとり予測ラベルを決定する。

例えば、下の図では入力データ近傍の5個の学習データは黒丸および三角がそれぞれ4個と1個であることがわかる。したがって、入力データのラベルは黒丸と予測される。

f:id:kdog08:20170510014846p:plain:w300

距離関数としてcosine類似度を用いる。

$\begin{eqnarray} \cos \left({\bf a},{\bf b}\right) = \frac{{\bf a}\cdot{\bf b}}{\|{\bf a}\| \|{\bf b}\|} = \frac{\sum^{n}_{i} a_i b_i}{\sqrt{\sum^{n}_{i} a^2_i} \sqrt{\sum^{n}_{i} b^2_i}} \end{eqnarray}$

この距離関数では値が1に近づくほど ${\bf a}$ と ${\bf b}$ は似ていると言える。

また、予測ラベルの正解率の指標としてf値を用いる。

実装

def predict(train_X, train_y, test_X):
    k = 2
    train_X = norm(train_X)
    test_X = norm(test_X)
    pred_y = np.zeros(test_X.shape[0])
    
    for i in range(test_X.shape[0]):
        icosine = np.dot(test_X[i],train_X.T)
        iknn = train_y[np.argsort(-icosine)[:k]]
        num_count = np.zeros(10)
        for j in iknn:
            num_count[j] += 1
        pred_y[i] = np.argmax(num_count)
        
    return pred_y
def norm(X):
    norm_X = np.linalg.norm(X, ord=2, axis=1)
    return X / norm_X[:,np.newaxis]

結果

$k = 1,2,3,5,10,20$ の場合についてそれぞれ分類をおこない、f値を求めた。

k	f-measure
1	0.97460
2	0.97203
3	0.97506
5	0.97542
10	0.97430
20	0.96993

$k=5$ でもっとも高いf値を示した。 $k$ が10以上になると分類の性能は減少傾向にあると考えられる。

メモ

今回ハイパーパラメータ $k$ が $k=1,2,3,5,10,20$ の場合について予測ラベルの正解率を調べた。f値の高さについて注目すれば $k=5$ がもっとも良いパラメータということができる。しかし、良いモデルを求めるためには未知のデータに対する予測の良さが不可欠になる。過学習および学習不足について検証することがモデル評価の一つの手段になる。k分割交差検証などが検証法として考えられる。