kNN関連パッケージの紹介
皆様こんばんは。
今回、https://atnd.org/events/58648 13日目の記事を担当することになったので
久しぶりのブログを書いています。
本記事でご紹介するのはRでkNN（k最近傍法）を実行するためのパッケージです。
kNNについて知らない方はwikipediak近傍法 - Wikipediaに簡単にまとまっているので見てもらうと良いと思います。
要は、入力データに似ているものを訓練データの中からk個探してきて、
それらの多数決で出力を決めるアルゴリズムです。
個人的な印象としては検索のイメージが強く、
例えば、訓練データの中から似ているレコード（商品やユーザー、事例など）を引っ張ってくるときに使ったりしています。
それでは早速パッケージの紹介に入ります。
｛class｝パッケージ
RでkNNをやろうとすると最初に見つかるのがこのパッケージだと思います。
とりあえずkNNで分類をやってみるという意味ではこのパッケージで十分です。
本記事では{kernlab}パッケージのspamデータセットを使って実行してみます。
因みにこのデータセットは約5000件のe-mailに対してスパムかどうかを判定したものです。
各レコードは各ワードや記号などの出現回数から作った特徴量（1～54列目）と
大文字に関する単語の長さなどから作った特徴量（55～57列目）と
スパムかどうかのクラス（58列目）から成っており、
今回は話を単純にするために1～54列目と58列目を対象としています。
library(kernlab) data(spam) data <- spam[,-(55:57)] #55列目がクラスになる library(class) i <- 1 classres <- class::knn(train=data[-i,-55],test=data[i,-55],cl=data[-i,55],k=100,prob=T)
実行結果：
> classres [1] spam attr(,"prob") [1] 0.74 Levels: nonspam spam
trianとtestをセットし、求めるクラスを決めてあげると実行できます。
probで確率値を出力する様に設定でき、設定すると
勝ったクラスの割合がどのくらいだったかが分かります。
ただ、今回の場合の様に2クラスの場合は良いのですが、
3クラス以上の分類で2位以下の確率値が分からないのは残念です。
上記は1レコードに対してknnを実行する方法でしたが
全レコードに対してknnを実行する（leave-one-out）する場合は以下の様にします。
classrescv <- class::knn.cv(train=data[,-55],cl=data[,55],k=100,prob=T)
実行結果：
> head(classrescv) [1] spam spam spam nonspam nonspam spam Levels: nonspam spam > head(attr(classrescv,"prob")) [1] 0.74 0.90 0.93 0.58 0.58 0.50
{class}パッケージのknnは各レコードごとに全探索を行っている様で、
spamデータぐらいではなんとも感じませんが、
データ量が大きくなってくるとパフォーマンスは辛くなってきます。
そこで、｛FNN｝パッケージです。
｛FNN｝パッケージ
FNNのFはFastのFなのですが、探索アルゴリズムを選択できる様になっており
全レコードに対してknnを実行する場合はこちらが速いです。
デフォルトのアルゴリズムであるkd_treeで実施した場合の計算時間は
理論的にはO(NlogN)となるそうです。
#classパッケージで実行 system.time(classrescv <- class::knn.cv(train=data[,-55],cl=data[,55],k=1,prob=T)) #FNNパッケージ"kd_tree"で実行 system.time(FNNrescv <- FNN::knn.cv(train=data[,-55],cl=data[,55],k=1,prob=T,algorithm="kd_tree"))
実行結果：
> system.time(classrescv <- class::knn.cv(train=data[,-55],cl=data[,55],k=1,prob=T)) user system elapsed 3.40 0.00 3.43 > system.time(FNNrescv <- FNN::knn.cv(train=data[,-55],cl=data[,55],k=1,prob=T,algorithm="kd_tree")) user system elapsed 2.69 0.00 2.70
spamデータぐらいの規模では大きな差はでませんが、数十万件を超える様なデータですと明確な差がでてきます。
補足：この記事を書いていて気付きましたが、kの数を大きくするとそれほど計算時間の差は出なくなってくるみたいです。
アルゴリズムと実装について理解が追い付いていないので原因は不明です。
｛FNN｝パッケージはkd_treeを設定した場合、Approximate Near Neighbor（ANN）というC++のライブラリを呼んでいますが、
このパッケージにおいては近似していないとマニュアルに書いてあるので、
その辺り調整できればkの数が増えても差が保てるのかもしれません。
この調整を行うには｛RANN｝のnn2や｛yaImpute｝のannを使わないと難しそうです。私はまだ試していません。。
｛FNN｝を使う利点はもう1つあります。（他にもありそうですが）
FNNのknn.cvは最近傍k個のレコードのインデックスを返してくれるので、
本記事冒頭で述べた様に似ているレコードを引っ張ってくることができます。
また、引っ張ってきたレコードのクラスを集計すれば2位以下のクラスの確率値を知ることも可能です。
FNNrescv <- FNN::knn.cv(train=data[,-55],cl=data[,55],k=3,prob=T,algorithm="kd_tree") i <- 1 data[c(i,attr(FNNrescv,"nn.index")[i,]),]
実行結果：
> data[c(i,attr(FNNrescv,"nn.index")[i,]),] make address all num3d our over remove internet order mail receive will people report addresses 1 0 0.64 0.64 0 0.32 0 0 0 0 0 0 0.64 0 0 0 13 0 0.69 0.34 0 0.34 0 0 0 0 0 0 0.69 0 0 0 312 0 0.68 0.34 0 0.34 0 0 0 0 0 0 0.68 0 0 0 168 0 0.71 0.35 0 0.35 0 0 0 0 0 0 0.71 0 0 0 free business email you credit your font num000 money hp hpl george num650 lab labs telnet num857 1 0.32 0 1.29 1.93 0 0.96 0 0 0 0 0 0 0 0 0 0 0 13 0.34 0 1.39 2.09 0 1.04 0 0 0 0 0 0 0 0 0 0 0 312 0.34 0 1.37 1.72 0 1.03 0 0 0 0 0 0 0 0 0 0 0 168 0.35 0 1.42 1.77 0 1.06 0 0 0 0 0 0 0 0 0 0 0 data num415 num85 technology num1999 parts pm direct cs meeting original project re edu table 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 312 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 168 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 conference charSemicolon charRoundbracket charSquarebracket charExclamation charDollar charHash type 1 0 0 0.000 0 0.778 0 0 spam 13 0 0 0.056 0 0.786 0 0 spam 312 0 0 0.055 0 0.718 0 0 spam 168 0 0 0.058 0 0.700 0 0 spam
上記、knn.cvを利用しましたが、インデックスが欲しいだけならば、
同パッケージ内のget.knnを使った方が速いです。
system.time(FNNrescv <- FNN::knn.cv(train=data[,-55],cl=data[,55],k=3,prob=F,algorithm="kd_tree")) system.time(FNNresget <- FNN::get.knn(data=data[,-55],k=3,algorithm="kd_tree"))
> system.time(FNNrescv <- FNN::knn.cv(train=data[,-55],cl=data[,55],k=3,prob=F,algorithm="kd_tree")) user system elapsed 3.07 0.00 3.12 > system.time(FNNresget <- FNN::get.knn(data=data[,-55],k=3,algorithm="kd_tree")) user system elapsed 0.76 0.00 0.76
因みにget.knnの方はattrではなく、リストで値を返してくるのでご注意を。
｛kknn｝パッケージ
そして、最後に｛kknn｝パッケージの紹介をしようと思っていましたが、
長くなってしまったので省略します。
多数決を行う時に最近傍k個の重みを調整できたり
クロスバリデーションの機能が充実していたりするのですが、
実務的にはややオーバースペックな印象で、私は使ったことがないです。
本記事では割愛しましたが、多数決の重みやkの数の調整よりも
特徴量自体の正規化や重み付けの方が効くことが多いのかなと思っています。
それでは皆様、来年も宜しくお願い致します。
※間違い等ありましたらご指摘いただけますと幸いです。
