# Non Metric Space (Approximate) Library in R

**mlampros**, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

The **nmslibR** package is a wrapper of *NMSLIB*, which according to the authors “… is a similarity search library and a toolkit for evaluation of similarity search methods. The goal of the project is to create an effective and comprehensive toolkit for searching in generic non-metric spaces. Being comprehensive is important, because no single method is likely to be sufficient in all cases. Also note that exact solutions are hardly efficient in high dimensions and/or non-metric spaces. Hence, the main focus is on approximate methods”.

I’ve searched for some time (before wrapping NMSLIB) for a nearest neighbor library which can work with high dimensional data and can scale with big datasets. I’ve already written a package for k-nearest-neighbor search (KernelKnn), however, it’s based on brute force and unfortunately, it requires a certain computation time if the data consists of many rows. The *nmslibR* package, besides the main functionality of the NMSLIB python library, also includes an Approximate Kernel k-nearest function, which as I will show in the next lines is both fast and accurate. A comparison of NMSLIB with other popular approximate k-nearest-neighbor methods can be found here.

The NMSLIB Library,

- is a collection of search methods for generic spaces
- has both metric and non-metric search algorithms
- has both exact and approximate search algorithms
- is an evaluation toolkit that simplifies experimentation and processing of results
- is extensible (new spaces and methods can be added)
- It was designed to be efficient

Details can be found in the NMSLIB-manual.

**The nmslibR package**

The *nmslibR* package includes the following R6-class / functions,

**class**

NMSlib |
---|

Knn_Query() |

knn_Query_Batch() |

save_Index() |

**functions**

KernelKnn_nmslib()

KernelKnnCV_nmslib()

dgCMatrix_2scipy_sparse()

mat_2scipy_sparse()

The package documentation includes details and examples for the R6-class and functions. I’ll start explaining how a user can work with sparse matrices as the input can also be a **python sparse matrix**.

**Sparse matrices as input**

The nmslibR package includes two functions (**mat_2scipy_sparse** and **dgCMatrix_2scipy_sparse**) which allow the user to convert from a *matrix* / *dgCMatrix* to a *scipy sparse matrix*,

library(nmslibR) # conversion from a matrix object to a scipy sparse matrix #---------------------------------------------------------- set.seed(1) x = matrix(runif(1000), nrow = 100, ncol = 10) x_sparse = mat_2scipy_sparse(x, format = "sparse_row_matrix") print(dim(x)) [1] 100 10 print(x_sparse$shape) (100, 10)

# conversion from a dgCMatrix object to a scipy sparse matrix #------------------------------------------------------------- data = c(1, 0, 2, 0, 0, 3, 4, 5, 6) # by default column-oriented format dgcM = Matrix::Matrix(data = data, nrow = 3, ncol = 3, byrow = TRUE, sparse = TRUE) print(dim(dgcM)) [1] 3 3 x_sparse = dgCMatrix_2scipy_sparse(dgcM) print(x_sparse$shape) (3, 3)

**The NMSlib R6-class**

The parameter settings for the *NMSlib* R6-class can be found in the Non-Metric Space Library (NMSLIB) Manual, which explains the NMSLIB Library in detail. In the following code chunk, I’ll show the functionality of the methods included using a data set from my Github repository (it appears as .ipynb notebook in the nmslib Github repository)

library(nmslibR) # download the data from my Github repository (tested on a Linux OS) #------------------------------------------------------------------- system("wget https://raw.githubusercontent.com/mlampros/DataSets/master/sift_10k.txt") # load the data in the R session #------------------------------- sift_10k = read.table("~/sift_10k.txt", quote="\"", comment.char="") # index parameters #----------------- M = 15 efC = 100 num_threads = 5 index_params = list('M'= M, 'indexThreadQty' = num_threads, 'efConstruction' = efC, 'post' = 0, 'skip_optimized_index' = 1 ) # query-time parameters #---------------------- efS = 100 query_time_params = list('efSearch' = efS) # Number of neighbors #-------------------- K = 100 # space to use #--------------- space_name = 'l2sqr_sift' # initialize NMSlib [ the data should be a matrix ] #-------------------------------------------------- init_nms = NMSlib$new(input_data = as.matrix(sift_10k), Index_Params = index_params, Time_Params = query_time_params, space = space_name, space_params = NULL, method = 'hnsw', data_type = 'DENSE_UINT8_VECTOR', dtype = 'INT', index_filepath = NULL, print_progress = FALSE)

# returns a 1-dimensional vector #------------------------------- init_nms$Knn_Query(query_data_row = as.matrix(sift_10k[1, ]), k = 5)

[[1]] [1] 2 6 4585 9256 140 # indices [[2]] [1] 18724 24320 68158 69067 70321 # distances

# returns knn's for all data #--------------------------- all_dat = init_nms$knn_Query_Batch(as.matrix(sift_10k), k = 5, num_threads = 1) str(all_dat)

# a list of indices and distances for all observations #------------------------------------------------------ List of 2 $ knn_idx : num [1:10000, 1:5] 3 4 1 2 13 14 1 2 30 31 ... $ knn_dist: num [1:10000, 1:5] 18724 14995 18724 14995 21038 ...

Details on the various methods and parameter settings can be found in the manual of the NMSLIB python Library.

**KernelKnn using the nmslibR package**

In the Vignette of the KernelKnn (*Image classification of the MNIST and CIFAR-10 data using KernelKnn and HOG (histogram of oriented gradients)*) package I experimented with the **mnist dataset** and a cross-validated kernel k-nearest-neighbors model gave **98.4 % accuracy** based on **HOG** (histogram of oriented gradients) features. However, it took almost **30 minutes** (depending on the system configuration) to complete using **6 threads**. I’ve implemented a similar function using NMSLIB (**KernelKnnCV_nmslib**), so in the next code chunk I’ll use the *same parameter setting* and I’ll compare *computation time* and *accuracy*.

First load the data,

# using system('wget..') on a linux OS system("wget https://raw.githubusercontent.com/mlampros/DataSets/master/mnist.zip") mnist <- read.table(unz("mnist.zip", "mnist.csv"), nrows = 70000, header = T, quote = "\"", sep = ",")

X = mnist[, -ncol(mnist)] dim(X) ## [1] 70000 784 # the 'KernelKnnCV_nmslib' function requires that the labels are numeric and start from 1 : Inf y = mnist[, ncol(mnist)] + 1 table(y) ## y ## 1 2 3 4 5 6 7 8 9 10 ## 6903 7877 6990 7141 6824 6313 6876 7293 6825 6958 # evaluation metric acc = function (y_true, preds) { out = table(y_true, max.col(preds, ties.method = "random")) acc = sum(diag(out))/sum(out) acc }

then compute the HOG features,

library(OpenImageR) hog = HOG_apply(X, cells = 6, orientations = 9, rows = 28, columns = 28, threads = 6) ## ## time to complete : 2.101281 secs dim(hog) ## [1] 70000 324

then compute the **approximate** kernel k-nearest-neighbors using the **cosine** distance,

# parameters for 'KernelKnnCV_nmslib' #------------------------------------ M = 30 efC = 100 num_threads = 6 index_params = list('M'= M, 'indexThreadQty' = num_threads, 'efConstruction' = efC, 'post' = 0, 'skip_optimized_index' = 1 ) efS = 100 query_time_params = list('efSearch' = efS) # approximate kernel knn #----------------------- fit_hog = KernelKnnCV_nmslib(hog, y, k = 20, folds = 4, h = 1, weights_function = 'biweight_tricube_MULT', Levels = sort(unique(y)), Index_Params = index_params, Time_Params = query_time_params, space = "cosinesimil", space_params = NULL, method = "hnsw", data_type = "DENSE_VECTOR", dtype = "FLOAT", index_filepath = NULL, print_progress = FALSE, num_threads = 6, seed_num = 1) # cross-validation starts .. # |=================================================================================| 100% # time to complete : 32.88805 secs str(fit_hog)

List of 2 $ preds:List of 4 ..$ : num [1:17500, 1:10] 0 0 0 0 0 0 0 0 0 0 ... ..$ : num [1:17500, 1:10] 0 0 0 0 1 ... ..$ : num [1:17500, 1:10] 0 0 0 0 0 ... ..$ : num [1:17500, 1:10] 0 0 0 0 0 0 0 0 0 0 ... $ folds:List of 4 ..$ fold_1: int [1:17500] 49808 21991 42918 7967 49782 28979 64440 49809 30522 36673 ... ..$ fold_2: int [1:17500] 51122 9469 58021 45228 2944 58052 65074 17709 2532 31262 ... ..$ fold_3: int [1:17500] 33205 40078 68177 32620 52721 18981 19417 53922 19102 67206 ... ..$ fold_4: int [1:17500] 28267 41652 28514 34525 68534 13294 48759 47521 69395 41408 ...

acc_fit_hog = unlist(lapply(1:length(fit_hog$preds), function(x) acc(y[fit_hog$folds[[x]]], fit_hog$preds[[x]]))) acc_fit_hog ## [1] 0.9768000 0.9786857 0.9763429 0.9760000 cat('mean accuracy for hog-features using cross-validation :', mean(acc_fit_hog), '\n') ## mean accuracy for hog-features using cross-validation : 0.9769571

It took approx. **33 seconds** to return with an accuracy of **97.7 %** . Almost **47 times faster** than KernelKnn’s corresponding function (brute force) with a **slight lower accuracy** rate (the *braycurtis* distance metric might be better suited for this dataset).

I also run the corresponding brute-force algorithm of the NMSLIB Library by setting the *method* parameter to **seq_search**,

# brute force of NMSLIB [ here we set 'Index_Params' and 'Time_Params' to NULL ] #---------------------- fit_hog_seq = KernelKnnCV_nmslib(hog, y, k = 20, folds = 4, h = 1, weights_function = 'biweight_tricube_MULT', Levels = sort(unique(y)), Index_Params = NULL, Time_Params = NULL, space = "cosinesimil", space_params = NULL, method = "seq_search", data_type = "DENSE_VECTOR", dtype = "FLOAT", index_filepath = NULL, print_progress = FALSE, num_threads = 6, seed_num = 1) # cross-validation starts .. # |=================================================================================| 100% # time to complete : 4.506177 mins acc_fit_hog_seq = unlist(lapply(1:length(fit_hog_seq$preds), function(x) acc(y[fit_hog_seq$folds[[x]]], fit_hog_seq$preds[[x]]))) acc_fit_hog_seq ## [1] 0.9785143 0.9802286 0.9783429 0.9784571 cat('mean accuracy for hog-features using cross-validation :', mean(acc_fit_hog_seq), '\n') ## mean accuracy for hog-features using cross-validation : 0.9788857

The brute-force algorithm of the NMSLIB Library is almost **6 times faster** than KernelKnn giving an accuracy of approx. **97.9 %**.

The *README.md* file of the *nmslibR* package includes the SystemRequirements and installation instructions.

An updated version of the nmslibR package can be found in my Github repository and to report bugs/issues please use the following link, https://github.com/mlampros/nmslibR/issues.

**leave a comment**for the author, please follow the link and comment on their blog:

**mlampros**.

R-bloggers.com offers

**daily e-mail updates**about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.