kd木を作って、k次元空間上の点間の最近傍構造を抽出したい
kd木*1という、k次元のユークリッド空間にある点の最近傍探索を分類する空間分割データ構造がある。学問分野では最近傍探索ってのに相当するそうだ。これをRでやりたい。
調べた所、以下３つのパッケージが見つかった。
この３つのライブラリ共、
というC++のライブラリに計算をブン投げるようになっていた。
RANNパッケージが一番作りがシンプルで、kd木を構成する関数しか機能として提供していない一方、FNN・yaImputeは機能が豊富で計算した最近接構造の"良さ"などを比較するためメソッドも提供されている。何個まで最近接を考慮したらいいのかなどの検証に使うわけですな。ちなみにFNNよりyaImputeの方が機能が更に豊富。パッケージのインストールと読み込みはinstall.packagesとlibrary関数でOK、dplyrとpipeRがないときはそれも入れておきましょう。
install.packages(c("FNN", "RANN", "yaImpute")) library(FNN) library(RANN) library(yaImpute) library(dplyr) library(pipeR)
まず、ダミーデーターを以下のように作成して、表示しておく。
#N個点をばらまく N <- 6 sample_data <- data.frame(x=rnorm(N), y=rnorm(N)) plot(sample_data) text(sample_data$x, sample_data$y, 1:N, cex=1, pos=4, col=\"red\")
この図に書いた点間の最近傍構造を取得したい、そういうことです。
で、実際に上記のFNN, RANN, yaImputeパッケージのそれぞれで計算させた結果が以下で、結論を先に書くと計算結果は一致している。読み方としては基本的に皆同じだが、説明を書いておくと
- nn2関数(RANN package)
- nn.idxの行方向が点の番号(sample_dataの行番号)、列方向が近い順に並べたsample_dataの行番号(ただし自分を含む)
- nn.distsの行方向が点の番号(sample_dataの行番号)、列方向が近い順に並べたsample_dataの行番号に相当するデータとの距離(ただし自分を含む)
- get.knn関数(FNN package)：
- nn.idxの行方向が点の番号(sample_dataの行番号)、列方向が近い順に並べたsample_dataの行番号
- nn.distsの行方向が点の番号(sample_dataの行番号)、列方向が近い順に並べたsample_dataの行番号に相当するデータとの距離
- ann関数(yaImpute package)
- knnIndexDistの行方向が点の番号(sample_dataの行番号)、列方向が近い順に並べたsample_dataの行番号(ただし前半分の列)
- knnIndexDistの行方向が点の番号(sample_dataの行番号)、列方向が近い順に並べたsample_dataの行番号に相当するデータとの距離(ただし後半分の列)
となっている。細かい仕様に違いはあるが、結果の読み方もだいたい同じだ。なので例えばnn2関数の結果をみると
- nn.idxの2行目をみると、2(自分自身),1,5,6,3,4の順番で点が2の傍にある
- nn.distsの2行目をみると、上に書いた点と2の点との距離は0, 0.7807924, 1.3328261, 1.3356298, 1.474876, 1.880671となっている
というように読めばよいわけです。実際、上の図の"2"の点に目視で見て一番近そうなのは1の点、その次が5の点のように見える(3もかなりいい線いってるが僅差で5の方が近いってのは出力された距離nn.distsを見ればわかる）ので、これでいいだろうと。
> #RANN(この関数しかない) > nn2(sample_data) $nn.idx [,1] [,2] [,3] [,4] [,5] [,6] [1,] 1 2 6 4 5 3 [2,] 2 1 5 6 3 4 [3,] 3 5 2 6 1 4 [4,] 4 6 1 5 2 3 [5,] 5 6 3 2 1 4 [6,] 6 4 5 1 2 3 $nn.dists [,1] [,2] [,3] [,4] [,5] [,6] [1,] 0 0.7807924 0.9674654 1.2762832 1.492233 2.067800 [2,] 0 0.7807924 1.3328261 1.3356298 1.474876 1.880671 [3,] 0 1.0764026 1.4748756 1.8956475 2.067800 2.571711 [4,] 0 0.6789893 1.2762832 1.5526944 1.880671 2.571711 [5,] 0 0.9114382 1.0764026 1.3328261 1.492233 1.552694 [6,] 0 0.6789893 0.9114382 0.9674654 1.335630 1.895648 > #FNN > get.knn(sample_data, k=N-1) $nn.index [,1] [,2] [,3] [,4] [,5] [1,] 2 6 4 5 3 [2,] 1 5 6 3 4 [3,] 5 2 6 1 4 [4,] 6 1 5 2 3 [5,] 6 3 2 1 4 [6,] 4 5 1 2 3 $nn.dist [,1] [,2] [,3] [,4] [,5] [1,] 0.7807924 0.9674654 1.2762832 1.492233 2.067800 [2,] 0.7807924 1.3328261 1.3356298 1.474876 1.880671 [3,] 1.0764026 1.4748756 1.8956475 2.067800 2.571711 [4,] 0.6789893 1.2762832 1.5526944 1.880671 2.571711 [5,] 0.9114382 1.0764026 1.3328261 1.492233 1.552694 [6,] 0.6789893 0.9114382 0.9674654 1.335630 1.895648 > #yaImpute > ann(as.matrix(sample_data), as.matrix(sample_data), k=N) Target points completed: $knnIndexDist [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [1,] 1 2 6 4 5 3 0 0.6096368 0.9359893 1.6288989 2.226759 4.275795 [2,] 2 1 5 6 3 4 0 0.6096368 1.7764254 1.7839069 2.175258 3.536924 [3,] 3 5 2 6 1 4 0 1.1586426 2.1752581 3.5934796 4.275795 6.613697 [4,] 4 6 1 5 2 3 0 0.4610265 1.6288989 2.4108599 3.536924 6.613697 [5,] 5 6 3 2 1 4 0 0.8307195 1.1586426 1.7764254 2.226759 2.410860 [6,] 6 4 5 1 2 3 0 0.4610265 0.8307195 0.9359893 1.783907 3.593480 ...(途中省略)... attr(,"class") [1] "ann"
で、３つあるパッケージのうち
- yaImputeパッケージは機能豊富なのはいいものの、肝心のann関数の引数がmatrix限定(data.frame入れたら怒られた）
- RANNパッケージは自分自身との距離の計算（つねに０）という冗長な結果が毎回帰ってくるので捌くのめんどい
という消去法的理由でとりあえずFNNパッケージを使わせていただくことにする。
*1:k-dimensional treeが正式名称らしい
