MNISTのデータを読み込むPythonプログラム - まんぼう日記 のつづき．MNIST を nearest neighbor 法（最近傍法，NN法）で識別する実験やってみました．
プログラムはこんなん．
実行してみると，
# test error rate = 3.09 %
となって，MNIST handwritten digit database, Yann LeCun, Corinna Cortes and Chris Burges に載ってる値と一致してます．
さすがに学習データが6万個もあるのでNN法遅いんですが，一つ気になることが．実行中に OS X の「アクティビティモニタ」見てたら，ずっとスレッド数1…．一番計算量の多いのんは np.dot の内積計算で，これはマルチスレッドで動くはずちゃうん（cf. 初雪 ＆ 行列の積を計算するプログラム - まんぼう日記 ）？ あれぇ (?_?)
というとこまでが昨夜で，一晩寝かせてみたら原因に思い至りました．
元のデータが0から255の整数値なので，整数型で Numpy の array に入れてたんですが，どうも整数配列んときには並列計算せえへんみたいですね．デフォルトの（浮動小数点数の）array に入れるようにしたら，ちゃんとマルチスレッドで動きました．Numpy が行列演算のライブラリを呼び出すのは浮動小数点のときだけってことかも．というわけで比較実験．
環境はこんなん：
- Mac Pro Late 2013 ( Intel Xeon E5 3.5GHz 6-Core, memory 64GB )
- Python 2.7.9 + Numpy 1.9.1 （ +atlas の variant なし cf. Numpy / Theano で行列の積を高速に計算するには - まんぼう日記 ）
np.int32 の array の場合，スレッド数は1で，
$ time python knn0118.py # test error rate = 3.09 % real 5m5.361s user 5m4.714s sys 0m0.556s
となりました．一方，float の場合，スレッド数は6で，
real 1m42.744s user 8m38.222s sys 0m2.312s
という結果に．なるほど．intの方がCPU時間少なくて済むけどマルチスレッドで動かへん分，経過時間で負けてると．なかなか悩ましいですな．一つだけプログラム動かすんならマルチスレッドで経過時間短い方がうれしいけど，いろいろ条件変えながらとかで複数プロセス同時に実行したりするんやったら，シングルスレッドでええからCPU時間短い方がうれしいし．まあ，たかたかが扱うような問題はたいがい浮動小数点演算必要やから，どうでもええっちゃあどうでもええんですが．
と，ここまで書いてる途中で，ソースファイル名に knn (k-nearest neighbor)って付けてるのに k = 1 のときのことしか考えてないプログラムになってることに気づきました．でもがんばってk近傍法のプログラム書く元気はない…．
kNN法に拡張するためには，計算した距離の値の中から小さい方k個を選び出す必要があります．何も考えんと np.argmax 使うちうのもありかもしれませんが，データ数多い時にそんなことするんはださださです．「小さい方k個を選び出す」って手続きは全体をソートするより少ない手間でできる処理で，特に k << (データ数) ならその違いは無視できへんので．
で，以前は自分でそういうアルゴリズムを書くしかなかったんですが，ちょっと調べてみたところ，Numpy 1.8 で np.argpartition ちうんが入って，簡単にそういうことができるようになったみたいです．なのでメモメモ．
>>> x = np.random.random_sample(100000000)
>>> hoge = np.argsort(x)
>>> hoge[:10]
array([58163550, 41356074, 72295372, 58398635, 75118733, 29502686,
1350837, 88739577, 50651756, 41578775])
>>> x[hoge[:10]]
array([ 3.14821120e-08, 3.42063201e-08, 4.16967317e-08,
4.41130323e-08, 5.22648554e-08, 5.93282922e-08,
6.72973166e-08, 6.94729136e-08, 9.68035468e-08,
1.01417913e-07])
>>> fuga = np.argpartition(x,10)
>>> fuga[:10]
array([58163550, 75118733, 41356074, 58398635, 29502686, 72295372,
1350837, 41578775, 88739577, 50651756])
こんな感じです．実際に実行してみると，かかる時間の違いを体感できます．argpartitionの返り値 fuga は，「前の10個が全体のうち小さい方10個になってる」という条件だけが満たされてて，その並びまでソートされてるわけじゃないことに注意．ソートまでしたいなら，
>>> y = x[fuga[:10]]
>>> idx = np.argsort(y)
>>> fuga[:10][idx]
array([58163550, 41356074, 72295372, 58398635, 75118733, 29502686,
1350837, 88739577, 50651756, 41578775])
とかやればよいでしょう．
まあ本気でkNNやりたい人は巷の機械学習ライブラリ使うたらええと思いますが．
