どうも、期末でひぃひぃツイッター上で言っているのーまっどです。
もうだめです、死ぬしかありません。
まぁまだ死んでないので元気にブログ記事を書いてテンションを上げて生きていこうと思います。
といわけで今回はロボット知能システムという授業で実装したK-近傍法について記事を書きたいと思います。
====
K-近傍法とは？
ウィキペディアの記事を読むと良いと思います。簡単にいえば、機械学習の方法の一種です。
http://ja.wikipedia.org/wiki/K%E8%BF%91%E5%82%8D%E6%B3%95
いま識別問題を考えているとすると、未知のデータ（一般のｎ次元ベクトルです）に一番近い既知のデータにその未知のデータも属している！と考えるのが最短近傍法です。
その時に、一番近いのだけじゃなくて、近い順からK個くらいで多数決しようぜ、というのがK-近傍法になります。最短近傍法はK=1のときのK-近傍法ですね。
一般に機械学習（パターン認識？）の基本は分類問題です。授業であった例だと、キノコの例があります。きのこの斑点の数・かさの大きさ、などの分かっている特徴からそのキノコのクラス（例えば毒入りか・毒がないか）を推定します。自分の理解がだとこんな感じです…。
今回使ったデータ
プログラム書いてると、なんだか題材が欲しくなります。現実のデータ扱いたいなーと思う時が僕は多々あるのですが、なかなか難しかったりします。
PCにUSBで湿度計とか温度計とか、色々計測機器を付けられるといいのですが。
今回機械学習を気合を入れてやるために、UCI Machine Learning Repository からデータを借りてきます。今回用いたのは、Wine Data Set のwine.dataです。
このデータセットは、３つのクラスに分けられているワインの明るさとかリンゴ酸の寮とか化学的な分析を行った結果が１７８個集まってるものです。１７８個のデータに、１３個の特徴量があります。
このデータセットは説明文によると、
In a classification context, this is a well posed problem with "well behaved" class structures. A good data set for first testing of a new classifier, but not very challenging.
ということで、日本語訳すると”分類の文脈では、よく振る舞われるクラス構造のある、よく課す問題である。新しい分類器の最初のテストには良いデータセットであるがそんなに挑戦的ではない”そうです。まぁ初めて機械学習の実装してみますしいいですよね。
下のようにんなデータがずらずら並んでいます…。
| 1 | 14.23 | 1.71 | 2.43 | 15.6 | 127 | 2.8 | 3.06 | 0.28 | 2.29 | 5.64 | 1.04 | 3.92 | 1065 |
| 1 | 13.2 | 1.78 | 2.14 | 11.2 | 100 | 2.65 | 2.76 | 0.26 | 1.28 | 4.38 | 1.05 | 3.4 | 1050 |
| 1 | 13.16 | 2.36 | 2.67 | 18.6 | 101 | 2.8 | 3.24 | 0.3 | 2.81 | 5.68 | 1.03 | 3.17 | 1185 |
| 1 | 14.37 | 1.95 | 2.5 | 16.8 | 113 | 3.85 | 3.49 | 0.24 | 2.18 | 7.8 | 0.86 | 3.45 | 1480 |
今回やったこと
Kー近傍法を実装した。Cで。もう書きたくない。
ソースはこちら
ｋ近傍法のプログラム gcc k-nearest.c -lm でコンパイル
数１００のオーダーならOCaml使えばよかったですね。はい。
ソースコードは最終的にはK-近傍法というより最短近傍法を含む一般的な形で書いてあるのですが、実装の流れとしては
- 最短近傍法を実装する
- あ、駄目だ。正規化実装する
- ｋ－近傍法を実装する
という流れだったので、そういう順序で説明して行きたいと思います。
最短近傍法
上の説明以上に特に言及することはないのですが、最短近傍法では、まずとあるクラスのわかってないベクトルｖi= (ai1,ai2, ... , ai13) と他のベクトルvj = (aj1, aj2, ..., aj13)に対して普通にユークリッド距離を求めます。
| vi - vj | = sqrt( (ai1 - aj2) ^ 2 + .....)
次に、未知のデータ一つ一つに対して既知のデータとの距離を計算して一番小さいのを求める。と。結果は下の通り。
success:58, fail:31, rate:0.651685
real class=1, output = 2: 2
real class=1, output = 3: 2
real class=2, output = 1: 2
real class=2, output = 3: 9
real class=3, output = 1: 3
real class=3, output = 2: 13
識別率65%かぁ。まぁこんなものでしょうね。
あんまり識別率が高くないのは、恐らく正規化されてないせいで、データの特徴をきちんと取り出せてないからなんだろうとこの時分析しました。
どういうことかというと、上で貼ったデータサンプルをもう一度確認してみると
| 1 | 14.23 | 1.71 | 2.43 | 15.6 | 127 | 2.8 | 3.06 | 0.28 | 2.29 | 5.64 | 1.04 | 3.92 | 1065 |
| 1 | 13.2 | 1.78 | 2.14 | 11.2 | 100 | 2.65 | 2.76 | 0.26 | 1.28 | 4.38 | 1.05 | 3.4 | 1050 |
| 1 | 13.16 | 2.36 | 2.67 | 18.6 | 101 | 2.8 | 3.24 | 0.3 | 2.81 | 5.68 | 1.03 | 3.17 | 1185 |
| 1 | 14.37 | 1.95 | 2.5 | 16.8 | 113 | 3.85 | 3.49 | 0.24 | 2.18 | 7.8 | 0.86 | 3.45 | 1480 |
このデータみてみると、スケールに偏りがあるんですよね。最後のデータが明らかにスケールがデカイ。ほぼこの値で決まってしまうのではないでしょうか。
というわけで正規化してみましょう。
正規化って？
上で議論したようにスケールが恐らく問題なんだろ、ということで一度変換して大体同じスケールに落ち着くようにしましょう。今回の正規化の方法は、各パターン間の距離が最小になるように変換しました。
詳しい数式の議論は教科書に任せるとして、直感的には各特徴量（hueとかMalic acidとか）の分散の逆数で割ればよろしいということが知られています。
今回は分散は、
| 0.659062 | 1.248015 | 0.075265 | 11.15269 | 203.9893 | 0.39169 | 0.997719 | 0.015489 | 0.327595 | 5.374449 | 0.052245 | 0.504086 | 99166.72 |
だいたいスケールと散らばり具合に応じて数の大きさが決まってますね。
で、割ってみた結果
| 1 | 21.5913 | 1.3702 | 32.2861 | 1.3988 | 0.6226 | 7.1485 | 3.067 | 18.0778 | 6.9903 | 1.0494 | 19.9062 | 7.7764 | 0.0107 |
| 1 | 20.0285 | 1.4263 | 28.433 | 1.0042 | 0.4902 | 6.7656 | 2.7663 | 16.7865 | 3.9073 | 0.815 | 20.0976 | 6.7449 | 0.0106 |
| 1 | 19.9678 | 1.891 | 35.4748 | 1.6678 | 0.4951 | 7.1485 | 3.2474 | 19.369 | 8.5777 | 1.0569 | 19.7148 | 6.2886 | 0.0119 |
ちょっとさっきと違い見づらいかもしれませんが数のスケールがだいたい整ったことが分かります。最後の特徴量はむしろスケールからするとあんまり変化してない値なのでガッツリ小さくなってますね。
正規化後の最短近傍法の識別結果
success:68, fail:21, rate:0.764045
real class=1, output = 2: 14
real class=1, output = 3: 0
real class=2, output = 1: 3
real class=2, output = 3: 2
real class=3, output = 1: 0
real class=3, output = 2: 2
すごい、１０％程度精度が上昇しました。おお、ワザマエ！
k－近傍法
はい、最後にｋ近傍法を実装しました。これは説明した通り近くにある点をｋ個近い順番に考慮に入れるというものでした。
早速結果を
|
k/正規化の有無 |
正規化 |
正規化してない |
k/正規化の有無 |
正規化 |
正規化してない |
|
1 |
0.764045 |
0.651685 |
11 |
0.797753 |
0.752809 |
|
2 |
0.764045 |
0.674157 |
12 |
0.786517 |
0.730337 |
|
3 |
0.808989 |
0.707865 |
13 |
0.775281 |
0.752809 |
|
4 |
0.831461 |
0.741573 |
14 |
0.741573 |
0.741573 |
|
5 |
0.831461 |
0.730337 |
15 |
0.764045 |
0.752809 |
|
6 |
0.820225 |
0.741573 |
16 |
0.775281 |
0.719101 |
|
7 |
0.808989 |
0.707865 |
17 |
0.764045 |
0.752809 |
|
8 |
0.797753 |
0.696629 |
18 |
0.764045 |
0.719101 |
|
9 |
0.797753 |
0.752809 |
19 |
0.741573 |
0.741573 |
|
10 |
0.808989 |
0.752809 |
|
|
|
ｋは大きいほうが良い気もするのですが境界面がぼやっとしてきて、K=5くらいから早速精度が落ち始めます。でもK=4,5で83%いくのですね。すごい。
K-近傍法はなんと言いますか、非常に単純な実装なのですが思いの外精度が出るなぁと思った次第です。
考察
実はまだやるべきことやってなくて次元削減をするべきなんですよね。一般一つのデータに対して特徴量がいっぱいあったほうが嬉しそうな気がするのですが、次元が大きくなればなるほど逆に精度が下がるという事が知られておりまして、減らしたほうがいいのです。
また次元が多い状態ですと、どれか特徴量が他の特徴量と相関があったり、有効に働かないことがあります。
あとはCをは辛いです。高速に動いてかつそこそこ書きやすい言語でも覚えるべきでしょうか。C++とかDとか？
おまけ
みんなCってどうやって書いてるの？
— Ocamlアイドル (@no_maddo) July 13, 2013@no_maddojjjjjj まずSchemeを実装します
— ELD-R-ESH-2 (@eldesh) July 13, 2013
ワロタｗｗｗ Lisper怖いです。
