<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/non-metric-space-approximate-library-in-r/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://mlampros.github.io/mlampros.github.io/2018/02/27/the_nmslibR_package/"> mlampros</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p>The <strong>nmslibR</strong> package is a wrapper of <a rel="nofollow" href="https://github.com/searchivarius/nmslib" target="_blank"><em>NMSLIB</em></a>, 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”.</p>
<p>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 (<a rel="nofollow" href="https://cran.r-project.org/package=KernelKnn" target="_blank">KernelKnn</a>), however, it’s based on brute force and unfortunately, it requires a certain computation time if the data consists of many rows. The <em>nmslibR</em> 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 <a rel="nofollow" href="https://github.com/erikbern/ann-benchmarks" target="_blank">here</a>.</p>
<p></p>
<p>The NMSLIB Library,</p>
<ul>
<li>is a collection of search methods for generic spaces</li>
<li>has both metric and non-metric search algorithms</li>
<li>has both exact and approximate search algorithms</li>
<li>is an evaluation toolkit that simplifies experimentation and processing of results</li>
<li>is extensible (new spaces and methods can be added)</li>
<li>It was designed to be efficient</li>
</ul>
<p></p>
<p>Details can be found in the <a rel="nofollow" href="https://github.com/searchivarius/nmslib/blob/master/manual/manual.pdf" target="_blank">NMSLIB-manual</a>.</p>
<p></p>
<h4><strong>The nmslibR package</strong></h4>
<p></p>
<p>The <em>nmslibR</em> package includes the following R6-class / functions,</p>
<p></p>
<h5><strong>class</strong></h5>
<p></p>
<table>
<thead>
<tr>
<th>NMSlib</th>
</tr>
</thead>
<tbody>
<tr>
<td>Knn_Query()</td>
</tr>
<tr>
<td>knn_Query_Batch()</td>
</tr>
<tr>
<td>save_Index()</td>
</tr>
</tbody>
</table>
<p></p>
<h5><strong>functions</strong></h5>
<p></p>
<p>KernelKnn_nmslib()</p>
<p>KernelKnnCV_nmslib()</p>
<p>dgCMatrix_2scipy_sparse()</p>
<p>mat_2scipy_sparse()</p>
<p></p>
<p>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 <strong>python sparse matrix</strong>.</p>
<p></p>
<h4><strong>Sparse matrices as input</strong></h4>
<p></p>
<p>The nmslibR package includes two functions (<strong>mat_2scipy_sparse</strong> and <strong>dgCMatrix_2scipy_sparse</strong>) which allow the user to convert from a <em>matrix</em> / <em>dgCMatrix</em> to a <em>scipy sparse matrix</em>,</p>
<p></p>
<div>
<div>
<pre><code><span>
</span><span>library</span><span>(</span><span>nmslibR</span><span>)</span><span>
</span><span># conversion from a matrix object to a scipy sparse matrix</span><span>
</span><span>#----------------------------------------------------------</span><span>
</span><span>set.seed</span><span>(</span><span>1</span><span>)</span><span>
</span><span>x</span><span> </span><span>=</span><span> </span><span>matrix</span><span>(</span><span>runif</span><span>(</span><span>1000</span><span>),</span><span> </span><span>nrow</span><span> </span><span>=</span><span> </span><span>100</span><span>,</span><span> </span><span>ncol</span><span> </span><span>=</span><span> </span><span>10</span><span>)</span><span>
</span><span>x_sparse</span><span> </span><span>=</span><span> </span><span>mat_2scipy_sparse</span><span>(</span><span>x</span><span>,</span><span> </span><span>format</span><span> </span><span>=</span><span> </span><span>&quot;sparse_row_matrix&quot;</span><span>)</span><span>
</span><span>print</span><span>(</span><span>dim</span><span>(</span><span>x</span><span>))</span><span>
</span><span>[</span><span>1</span><span>]</span><span> </span><span>100</span><span> </span><span>10</span><span>
</span><span>print</span><span>(</span><span>x_sparse</span><span>$</span><span>shape</span><span>)</span><span>
</span><span>(</span><span>100</span><span>,</span><span> </span><span>10</span><span>)</span><span>
</span></code></pre>
</div>
</div>
<p></p>
<div>
<div>
<pre><code><span>
</span><span># conversion from a dgCMatrix object to a scipy sparse matrix</span><span>
</span><span>#-------------------------------------------------------------</span><span>
</span><span>data</span><span> </span><span>=</span><span> </span><span>c</span><span>(</span><span>1</span><span>,</span><span> </span><span>0</span><span>,</span><span> </span><span>2</span><span>,</span><span> </span><span>0</span><span>,</span><span> </span><span>0</span><span>,</span><span> </span><span>3</span><span>,</span><span> </span><span>4</span><span>,</span><span> </span><span>5</span><span>,</span><span> </span><span>6</span><span>)</span><span>
</span><span># by default column-oriented format</span><span>
</span><span>dgcM</span><span> </span><span>=</span><span> </span><span>Matrix</span><span>::</span><span>Matrix</span><span>(</span><span>data</span><span> </span><span>=</span><span> </span><span>data</span><span>,</span><span> </span><span>nrow</span><span> </span><span>=</span><span> </span><span>3</span><span>,</span><span>
</span><span>ncol</span><span> </span><span>=</span><span> </span><span>3</span><span>,</span><span> </span><span>byrow</span><span> </span><span>=</span><span> </span><span>TRUE</span><span>,</span><span>
</span><span>sparse</span><span> </span><span>=</span><span> </span><span>TRUE</span><span>)</span><span>
</span><span>print</span><span>(</span><span>dim</span><span>(</span><span>dgcM</span><span>))</span><span>
</span><span>[</span><span>1</span><span>]</span><span> </span><span>3</span><span> </span><span>3</span><span>
</span><span>x_sparse</span><span> </span><span>=</span><span> </span><span>dgCMatrix_2scipy_sparse</span><span>(</span><span>dgcM</span><span>)</span><span>
</span><span>print</span><span>(</span><span>x_sparse</span><span>$</span><span>shape</span><span>)</span><span>
</span><span>(</span><span>3</span><span>,</span><span> </span><span>3</span><span>)</span><span>
</span></code></pre>
</div>
</div>
<p></p>
<h4><strong>The NMSlib R6-class</strong></h4>
<p></p>
<p>The parameter settings for the <em>NMSlib</em> R6-class can be found in the <a rel="nofollow" href="https://github.com/searchivarius/nmslib/blob/master/manual/manual.pdf" target="_blank">Non-Metric Space Library (NMSLIB) Manual</a>, which explains the NMSLIB Library in detail. In the following code chunk, I’ll show the functionality of the methods included using a <a rel="nofollow" href="https://github.com/mlampros/DataSets" target="_blank">data set from my Github repository</a> (it appears as <a rel="nofollow" href="https://github.com/searchivarius/nmslib/blob/master/python_bindings/notebooks/search_sift_uint8.ipynb" target="_blank">.ipynb notebook in the nmslib Github repository</a>)</p>
<p></p>
<div>
<div>
<pre><code><span>
</span><span>library</span><span>(</span><span>nmslibR</span><span>)</span><span>
</span><span># download the data from my Github repository (tested on a Linux OS)</span><span>
</span><span>#-------------------------------------------------------------------</span><span>
</span><span>system</span><span>(</span><span>&quot;wget https://raw.githubusercontent.com/mlampros/DataSets/master/sift_10k.txt&quot;</span><span>)</span><span>
</span><span># load the data in the R session</span><span>
</span><span>#-------------------------------</span><span>
</span><span>sift_10k</span><span> </span><span>=</span><span> </span><span>read.table</span><span>(</span><span>&quot;~/sift_10k.txt&quot;</span><span>,</span><span> </span><span>quote</span><span>=</span><span>&quot;\&quot;&quot;</span><span>,</span><span> </span><span>comment.char</span><span>=</span><span>&quot;&quot;</span><span>)</span><span>
</span><span># index parameters</span><span>
</span><span>#-----------------</span><span>
</span><span>M</span><span> </span><span>=</span><span> </span><span>15</span><span>
</span><span>efC</span><span> </span><span>=</span><span> </span><span>100</span><span>
</span><span>num_threads</span><span> </span><span>=</span><span> </span><span>5</span><span>
</span><span>index_params</span><span> </span><span>=</span><span> </span><span>list</span><span>(</span><span>'M'</span><span>=</span><span> </span><span>M</span><span>,</span><span> </span><span>'indexThreadQty'</span><span> </span><span>=</span><span> </span><span>num_threads</span><span>,</span><span> </span><span>'efConstruction'</span><span> </span><span>=</span><span> </span><span>efC</span><span>,</span><span> </span><span>'post'</span><span> </span><span>=</span><span> </span><span>0</span><span>,</span><span> </span><span>'skip_optimized_index'</span><span> </span><span>=</span><span> </span><span>1</span><span> </span><span>)</span><span>
</span><span># query-time parameters</span><span>
</span><span>#----------------------</span><span>
</span><span>efS</span><span> </span><span>=</span><span> </span><span>100</span><span>
</span><span>query_time_params</span><span> </span><span>=</span><span> </span><span>list</span><span>(</span><span>'efSearch'</span><span> </span><span>=</span><span> </span><span>efS</span><span>)</span><span>
</span><span># Number of neighbors </span><span>
</span><span>#--------------------</span><span>
</span><span>K</span><span> </span><span>=</span><span> </span><span>100</span><span>
</span><span># space to use</span><span>
</span><span>#---------------</span><span>
</span><span>space_name</span><span> </span><span>=</span><span> </span><span>'l2sqr_sift'</span><span> </span><span># initialize NMSlib [ the data should be a matrix ]</span><span>
</span><span>#--------------------------------------------------</span><span>
</span><span>init_nms</span><span> </span><span>=</span><span> </span><span>NMSlib</span><span>$</span><span>new</span><span>(</span><span>input_data</span><span> </span><span>=</span><span> </span><span>as.matrix</span><span>(</span><span>sift_10k</span><span>),</span><span> </span><span>Index_Params</span><span> </span><span>=</span><span> </span><span>index_params</span><span>,</span><span> </span><span>Time_Params</span><span> </span><span>=</span><span> </span><span>query_time_params</span><span>,</span><span> </span><span>space</span><span> </span><span>=</span><span> </span><span>space_name</span><span>,</span><span> </span><span>space_params</span><span> </span><span>=</span><span> </span><span>NULL</span><span>,</span><span> </span><span>method</span><span> </span><span>=</span><span> </span><span>'hnsw'</span><span>,</span><span> </span><span>data_type</span><span> </span><span>=</span><span> </span><span>'DENSE_UINT8_VECTOR'</span><span>,</span><span> </span><span>dtype</span><span> </span><span>=</span><span> </span><span>'INT'</span><span>,</span><span>
</span><span>index_filepath</span><span> </span><span>=</span><span> </span><span>NULL</span><span>,</span><span> </span><span>print_progress</span><span> </span><span>=</span><span> </span><span>FALSE</span><span>)</span><span>
</span></code></pre>
</div>
</div>
<p></p>
<div>
<div>
<pre><code><span>
</span><span># returns a 1-dimensional vector</span><span>
</span><span>#-------------------------------</span><span>
</span><span>init_nms</span><span>$</span><span>Knn_Query</span><span>(</span><span>query_data_row</span><span> </span><span>=</span><span> </span><span>as.matrix</span><span>(</span><span>sift_10k</span><span>[</span><span>1</span><span>,</span><span> </span><span>]),</span><span> </span><span>k</span><span> </span><span>=</span><span> </span><span>5</span><span>)</span><span>
</span></code></pre>
</div>
</div>
<p></p>
<div>
<div>
<pre><code><span>
</span><span>[[</span><span>1</span><span>]]</span><span>
</span><span>[</span><span>1</span><span>]</span><span> </span><span>2</span><span> </span><span>6</span><span> </span><span>4585</span><span> </span><span>9256</span><span> </span><span>140</span><span> </span><span># indices</span><span>
</span><span>[[</span><span>2</span><span>]]</span><span>
</span><span>[</span><span>1</span><span>]</span><span> </span><span>18724</span><span> </span><span>24320</span><span> </span><span>68158</span><span> </span><span>69067</span><span> </span><span>70321</span><span> </span><span># distances</span><span>
</span></code></pre>
</div>
</div>
<p></p>
<div>
<div>
<pre><code><span>
</span><span># returns knn's for all data</span><span>
</span><span>#---------------------------</span><span>
</span><span>all_dat</span><span> </span><span>=</span><span> </span><span>init_nms</span><span>$</span><span>knn_Query_Batch</span><span>(</span><span>as.matrix</span><span>(</span><span>sift_10k</span><span>),</span><span> </span><span>k</span><span> </span><span>=</span><span> </span><span>5</span><span>,</span><span> </span><span>num_threads</span><span> </span><span>=</span><span> </span><span>1</span><span>)</span><span>
</span><span>str</span><span>(</span><span>all_dat</span><span>)</span><span>
</span></code></pre>
</div>
</div>
<p></p>
<div>
<div>
<pre><code><span>
</span><span># a list of indices and distances for all observations</span><span>
</span><span>#------------------------------------------------------</span><span>
</span><span>List</span><span> </span><span>of</span><span> </span><span>2</span><span>
</span><span>$</span><span> </span><span>knn_idx</span><span> </span><span>:</span><span> </span><span>num</span><span> </span><span>[</span><span>1</span><span>:</span><span>10000</span><span>,</span><span> </span><span>1</span><span>:</span><span>5</span><span>]</span><span> </span><span>3</span><span> </span><span>4</span><span> </span><span>1</span><span> </span><span>2</span><span> </span><span>13</span><span> </span><span>14</span><span> </span><span>1</span><span> </span><span>2</span><span> </span><span>30</span><span> </span><span>31</span><span> </span><span>...</span><span>
</span><span>$</span><span> </span><span>knn_dist</span><span>:</span><span> </span><span>num</span><span> </span><span>[</span><span>1</span><span>:</span><span>10000</span><span>,</span><span> </span><span>1</span><span>:</span><span>5</span><span>]</span><span> </span><span>18724</span><span> </span><span>14995</span><span> </span><span>18724</span><span> </span><span>14995</span><span> </span><span>21038</span><span> </span><span>...</span><span>
</span></code></pre>
</div>
</div>
<p></p>
<p>Details on the various methods and parameter settings can be found in the <a rel="nofollow" href="https://github.com/searchivarius/nmslib/blob/master/manual/manual.pdf" target="_blank">manual of the NMSLIB python Library</a>.</p>
<p></p>
<h4><strong>KernelKnn using the nmslibR package</strong></h4>
<p></p>
<p>In the <a rel="nofollow" href="https://cran.r-project.org/package=KernelKnn" target="_blank">Vignette of the KernelKnn</a> (<em>Image classification of the MNIST and CIFAR-10 data using KernelKnn and HOG (histogram of oriented gradients)</em>) package I experimented with the <strong>mnist dataset</strong> and a cross-validated kernel k-nearest-neighbors model gave <strong>98.4 % accuracy</strong> based on <strong>HOG</strong> (histogram of oriented gradients) features. However, it took almost <strong>30 minutes</strong> (depending on the system configuration) to complete using <strong>6 threads</strong>. I’ve implemented a similar function using NMSLIB (<strong>KernelKnnCV_nmslib</strong>), so in the next code chunk I’ll use the <em>same parameter setting</em> and I’ll compare <em>computation time</em> and <em>accuracy</em>.</p>
<p></p>
<p>First load the data,</p>
<p></p>
<div>
<div>
<pre><code><span>
</span><span># using system('wget..') on a linux OS </span><span>
</span><span>system</span><span>(</span><span>&quot;wget https://raw.githubusercontent.com/mlampros/DataSets/master/mnist.zip&quot;</span><span>)</span><span> </span><span>mnist</span><span> </span><span>&lt;-</span><span> </span><span>read.table</span><span>(</span><span>unz</span><span>(</span><span>&quot;mnist.zip&quot;</span><span>,</span><span> </span><span>&quot;mnist.csv&quot;</span><span>),</span><span> </span><span>nrows</span><span> </span><span>=</span><span> </span><span>70000</span><span>,</span><span> </span><span>header</span><span> </span><span>=</span><span> </span><span>T</span><span>,</span><span> </span><span>quote</span><span> </span><span>=</span><span> </span><span>&quot;\&quot;&quot;</span><span>,</span><span> </span><span>sep</span><span> </span><span>=</span><span> </span><span>&quot;,&quot;</span><span>)</span><span>
</span></code></pre>
</div>
</div>
<p></p>
<div>
<div>
<pre><code><span>
</span><span>X</span><span> </span><span>=</span><span> </span><span>mnist</span><span>[,</span><span> </span><span>-</span><span>ncol</span><span>(</span><span>mnist</span><span>)]</span><span>
</span><span>dim</span><span>(</span><span>X</span><span>)</span><span>
</span><span>## [1] 70000 784</span><span>
</span><span># the 'KernelKnnCV_nmslib' function requires that the labels are numeric and start from 1 : Inf</span><span>
</span><span>y</span><span> </span><span>=</span><span> </span><span>mnist</span><span>[,</span><span> </span><span>ncol</span><span>(</span><span>mnist</span><span>)]</span><span> </span><span>+</span><span> </span><span>1</span><span> </span><span>table</span><span>(</span><span>y</span><span>)</span><span>
</span><span>## y</span><span>
</span><span>## 1 2 3 4 5 6 7 8 9 10 </span><span>
</span><span>## 6903 7877 6990 7141 6824 6313 6876 7293 6825 6958</span><span>
</span><span># evaluation metric</span><span>
</span><span>acc</span><span> </span><span>=</span><span> </span><span>function</span><span> </span><span>(</span><span>y_true</span><span>,</span><span> </span><span>preds</span><span>)</span><span> </span><span>{</span><span>
</span><span>out</span><span> </span><span>=</span><span> </span><span>table</span><span>(</span><span>y_true</span><span>,</span><span> </span><span>max.col</span><span>(</span><span>preds</span><span>,</span><span> </span><span>ties.method</span><span> </span><span>=</span><span> </span><span>&quot;random&quot;</span><span>))</span><span>
</span><span>acc</span><span> </span><span>=</span><span> </span><span>sum</span><span>(</span><span>diag</span><span>(</span><span>out</span><span>))</span><span>/</span><span>sum</span><span>(</span><span>out</span><span>)</span><span>
</span><span>acc</span><span>
</span><span>}</span><span>
</span></code></pre>
</div>
</div>
<p></p>
<p>then compute the HOG features,</p>
<p></p>
<div>
<div>
<pre><code><span>
</span><span>library</span><span>(</span><span>OpenImageR</span><span>)</span><span>
</span><span>hog</span><span> </span><span>=</span><span> </span><span>HOG_apply</span><span>(</span><span>X</span><span>,</span><span> </span><span>cells</span><span> </span><span>=</span><span> </span><span>6</span><span>,</span><span> </span><span>orientations</span><span> </span><span>=</span><span> </span><span>9</span><span>,</span><span> </span><span>rows</span><span> </span><span>=</span><span> </span><span>28</span><span>,</span><span> </span><span>columns</span><span> </span><span>=</span><span> </span><span>28</span><span>,</span><span> </span><span>threads</span><span> </span><span>=</span><span> </span><span>6</span><span>)</span><span>
</span><span>## </span><span>
</span><span>## time to complete : 2.101281 secs </span><span>
</span><span>dim</span><span>(</span><span>hog</span><span>)</span><span>
</span><span>## [1] 70000 324</span><span>
</span></code></pre>
</div>
</div>
<p></p>
<p>then compute the <strong>approximate</strong> kernel k-nearest-neighbors using the <strong>cosine</strong> distance,</p>
<p></p>
<div>
<div>
<pre><code><span>
</span><span># parameters for 'KernelKnnCV_nmslib'</span><span>
</span><span>#------------------------------------</span><span>
</span><span>M</span><span> </span><span>=</span><span> </span><span>30</span><span>
</span><span>efC</span><span> </span><span>=</span><span> </span><span>100</span><span>
</span><span>num_threads</span><span> </span><span>=</span><span> </span><span>6</span><span>
</span><span>index_params</span><span> </span><span>=</span><span> </span><span>list</span><span>(</span><span>'M'</span><span>=</span><span> </span><span>M</span><span>,</span><span> </span><span>'indexThreadQty'</span><span> </span><span>=</span><span> </span><span>num_threads</span><span>,</span><span> </span><span>'efConstruction'</span><span> </span><span>=</span><span> </span><span>efC</span><span>,</span><span>
</span><span>'post'</span><span> </span><span>=</span><span> </span><span>0</span><span>,</span><span> </span><span>'skip_optimized_index'</span><span> </span><span>=</span><span> </span><span>1</span><span> </span><span>)</span><span>
</span><span>efS</span><span> </span><span>=</span><span> </span><span>100</span><span>
</span><span>query_time_params</span><span> </span><span>=</span><span> </span><span>list</span><span>(</span><span>'efSearch'</span><span> </span><span>=</span><span> </span><span>efS</span><span>)</span><span>
</span><span># approximate kernel knn</span><span>
</span><span>#-----------------------</span><span>
</span><span>fit_hog</span><span> </span><span>=</span><span> </span><span>KernelKnnCV_nmslib</span><span>(</span><span>hog</span><span>,</span><span> </span><span>y</span><span>,</span><span> </span><span>k</span><span> </span><span>=</span><span> </span><span>20</span><span>,</span><span> </span><span>folds</span><span> </span><span>=</span><span> </span><span>4</span><span>,</span><span> </span><span>h</span><span> </span><span>=</span><span> </span><span>1</span><span>,</span><span> </span><span>weights_function</span><span> </span><span>=</span><span> </span><span>'biweight_tricube_MULT'</span><span>,</span><span> </span><span>Levels</span><span> </span><span>=</span><span> </span><span>sort</span><span>(</span><span>unique</span><span>(</span><span>y</span><span>)),</span><span> </span><span>Index_Params</span><span> </span><span>=</span><span> </span><span>index_params</span><span>,</span><span>
</span><span>Time_Params</span><span> </span><span>=</span><span> </span><span>query_time_params</span><span>,</span><span> </span><span>space</span><span> </span><span>=</span><span> </span><span>&quot;cosinesimil&quot;</span><span>,</span><span> </span><span>space_params</span><span> </span><span>=</span><span> </span><span>NULL</span><span>,</span><span> </span><span>method</span><span> </span><span>=</span><span> </span><span>&quot;hnsw&quot;</span><span>,</span><span> </span><span>data_type</span><span> </span><span>=</span><span> </span><span>&quot;DENSE_VECTOR&quot;</span><span>,</span><span> </span><span>dtype</span><span> </span><span>=</span><span> </span><span>&quot;FLOAT&quot;</span><span>,</span><span> </span><span>index_filepath</span><span> </span><span>=</span><span> </span><span>NULL</span><span>,</span><span> </span><span>print_progress</span><span> </span><span>=</span><span> </span><span>FALSE</span><span>,</span><span> </span><span>num_threads</span><span> </span><span>=</span><span> </span><span>6</span><span>,</span><span> </span><span>seed_num</span><span> </span><span>=</span><span> </span><span>1</span><span>)</span><span>
</span><span># cross-validation starts .. </span><span>
</span><span># |=================================================================================| 100%</span><span>
</span><span># time to complete : 32.88805 secs </span><span>
</span><span>str</span><span>(</span><span>fit_hog</span><span>)</span><span>
</span></code></pre>
</div>
</div>
<p></p>
<div>
<div>
<pre><code><span>
</span><span>List</span><span> </span><span>of</span><span> </span><span>2</span><span>
</span><span>$</span><span> </span><span>preds</span><span>:</span><span>List</span><span> </span><span>of</span><span> </span><span>4</span><span>
</span><span>..</span><span>$</span><span> </span><span>:</span><span> </span><span>num</span><span> </span><span>[</span><span>1</span><span>:</span><span>17500</span><span>,</span><span> </span><span>1</span><span>:</span><span>10</span><span>]</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>...</span><span>
</span><span>..</span><span>$</span><span> </span><span>:</span><span> </span><span>num</span><span> </span><span>[</span><span>1</span><span>:</span><span>17500</span><span>,</span><span> </span><span>1</span><span>:</span><span>10</span><span>]</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>1</span><span> </span><span>...</span><span>
</span><span>..</span><span>$</span><span> </span><span>:</span><span> </span><span>num</span><span> </span><span>[</span><span>1</span><span>:</span><span>17500</span><span>,</span><span> </span><span>1</span><span>:</span><span>10</span><span>]</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>...</span><span>
</span><span>..</span><span>$</span><span> </span><span>:</span><span> </span><span>num</span><span> </span><span>[</span><span>1</span><span>:</span><span>17500</span><span>,</span><span> </span><span>1</span><span>:</span><span>10</span><span>]</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>0</span><span> </span><span>...</span><span>
</span><span>$</span><span> </span><span>folds</span><span>:</span><span>List</span><span> </span><span>of</span><span> </span><span>4</span><span>
</span><span>..</span><span>$</span><span> </span><span>fold_1</span><span>:</span><span> </span><span>int</span><span> </span><span>[</span><span>1</span><span>:</span><span>17500</span><span>]</span><span> </span><span>49808</span><span> </span><span>21991</span><span> </span><span>42918</span><span> </span><span>7967</span><span> </span><span>49782</span><span> </span><span>28979</span><span> </span><span>64440</span><span> </span><span>49809</span><span> </span><span>30522</span><span> </span><span>36673</span><span> </span><span>...</span><span>
</span><span>..</span><span>$</span><span> </span><span>fold_2</span><span>:</span><span> </span><span>int</span><span> </span><span>[</span><span>1</span><span>:</span><span>17500</span><span>]</span><span> </span><span>51122</span><span> </span><span>9469</span><span> </span><span>58021</span><span> </span><span>45228</span><span> </span><span>2944</span><span> </span><span>58052</span><span> </span><span>65074</span><span> </span><span>17709</span><span> </span><span>2532</span><span> </span><span>31262</span><span> </span><span>...</span><span>
</span><span>..</span><span>$</span><span> </span><span>fold_3</span><span>:</span><span> </span><span>int</span><span> </span><span>[</span><span>1</span><span>:</span><span>17500</span><span>]</span><span> </span><span>33205</span><span> </span><span>40078</span><span> </span><span>68177</span><span> </span><span>32620</span><span> </span><span>52721</span><span> </span><span>18981</span><span> </span><span>19417</span><span> </span><span>53922</span><span> </span><span>19102</span><span> </span><span>67206</span><span> </span><span>...</span><span>
</span><span>..</span><span>$</span><span> </span><span>fold_4</span><span>:</span><span> </span><span>int</span><span> </span><span>[</span><span>1</span><span>:</span><span>17500</span><span>]</span><span> </span><span>28267</span><span> </span><span>41652</span><span> </span><span>28514</span><span> </span><span>34525</span><span> </span><span>68534</span><span> </span><span>13294</span><span> </span><span>48759</span><span> </span><span>47521</span><span> </span><span>69395</span><span> </span><span>41408</span><span> </span><span>...</span><span>
</span></code></pre>
</div>
</div>
<p></p>
<div>
<div>
<pre><code><span>
</span><span>acc_fit_hog</span><span> </span><span>=</span><span> </span><span>unlist</span><span>(</span><span>lapply</span><span>(</span><span>1</span><span>:</span><span>length</span><span>(</span><span>fit_hog</span><span>$</span><span>preds</span><span>),</span><span> </span><span>function</span><span>(</span><span>x</span><span>)</span><span> </span><span>acc</span><span>(</span><span>y</span><span>[</span><span>fit_hog</span><span>$</span><span>folds</span><span>[[</span><span>x</span><span>]]],</span><span> </span><span>fit_hog</span><span>$</span><span>preds</span><span>[[</span><span>x</span><span>]])))</span><span>
</span><span>acc_fit_hog</span><span>
</span><span>## [1] 0.9768000 0.9786857 0.9763429 0.9760000</span><span>
</span><span>cat</span><span>(</span><span>'mean accuracy for hog-features using cross-validation :'</span><span>,</span><span> </span><span>mean</span><span>(</span><span>acc_fit_hog</span><span>),</span><span> </span><span>'\n'</span><span>)</span><span>
</span><span>## mean accuracy for hog-features using cross-validation : 0.9769571</span><span>
</span></code></pre>
</div>
</div>
<p></p>
<p>It took approx. <strong>33 seconds</strong> to return with an accuracy of <strong>97.7 %</strong> . Almost <strong>47 times faster</strong> than KernelKnn’s corresponding function (brute force) with a <strong>slight lower accuracy</strong> rate (the <em>braycurtis</em> distance metric might be better suited for this dataset).</p>
<p>I also run the corresponding brute-force algorithm of the NMSLIB Library by setting the <em>method</em> parameter to <strong>seq_search</strong>,</p>
<p></p>
<div>
<div>
<pre><code><span>
</span><span># brute force of NMSLIB [ here we set 'Index_Params' and 'Time_Params' to NULL ]</span><span>
</span><span>#----------------------</span><span>
</span><span>fit_hog_seq</span><span> </span><span>=</span><span> </span><span>KernelKnnCV_nmslib</span><span>(</span><span>hog</span><span>,</span><span> </span><span>y</span><span>,</span><span> </span><span>k</span><span> </span><span>=</span><span> </span><span>20</span><span>,</span><span> </span><span>folds</span><span> </span><span>=</span><span> </span><span>4</span><span>,</span><span> </span><span>h</span><span> </span><span>=</span><span> </span><span>1</span><span>,</span><span> </span><span>weights_function</span><span> </span><span>=</span><span> </span><span>'biweight_tricube_MULT'</span><span>,</span><span> </span><span>Levels</span><span> </span><span>=</span><span> </span><span>sort</span><span>(</span><span>unique</span><span>(</span><span>y</span><span>)),</span><span> </span><span>Index_Params</span><span> </span><span>=</span><span> </span><span>NULL</span><span>,</span><span>
</span><span>Time_Params</span><span> </span><span>=</span><span> </span><span>NULL</span><span>,</span><span> </span><span>space</span><span> </span><span>=</span><span> </span><span>&quot;cosinesimil&quot;</span><span>,</span><span> </span><span>space_params</span><span> </span><span>=</span><span> </span><span>NULL</span><span>,</span><span> </span><span>method</span><span> </span><span>=</span><span> </span><span>&quot;seq_search&quot;</span><span>,</span><span> </span><span>data_type</span><span> </span><span>=</span><span> </span><span>&quot;DENSE_VECTOR&quot;</span><span>,</span><span> </span><span>dtype</span><span> </span><span>=</span><span> </span><span>&quot;FLOAT&quot;</span><span>,</span><span> </span><span>index_filepath</span><span> </span><span>=</span><span> </span><span>NULL</span><span>,</span><span> </span><span>print_progress</span><span> </span><span>=</span><span> </span><span>FALSE</span><span>,</span><span> </span><span>num_threads</span><span> </span><span>=</span><span> </span><span>6</span><span>,</span><span> </span><span>seed_num</span><span> </span><span>=</span><span> </span><span>1</span><span>)</span><span>
</span><span># cross-validation starts .. </span><span>
</span><span># |=================================================================================| 100%</span><span>
</span><span># time to complete : 4.506177 mins </span><span>
</span><span>acc_fit_hog_seq</span><span> </span><span>=</span><span> </span><span>unlist</span><span>(</span><span>lapply</span><span>(</span><span>1</span><span>:</span><span>length</span><span>(</span><span>fit_hog_seq</span><span>$</span><span>preds</span><span>),</span><span> </span><span>function</span><span>(</span><span>x</span><span>)</span><span> </span><span>acc</span><span>(</span><span>y</span><span>[</span><span>fit_hog_seq</span><span>$</span><span>folds</span><span>[[</span><span>x</span><span>]]],</span><span> </span><span>fit_hog_seq</span><span>$</span><span>preds</span><span>[[</span><span>x</span><span>]])))</span><span>
</span><span>acc_fit_hog_seq</span><span>
</span><span>## [1] 0.9785143 0.9802286 0.9783429 0.9784571</span><span>
</span><span>cat</span><span>(</span><span>'mean accuracy for hog-features using cross-validation :'</span><span>,</span><span> </span><span>mean</span><span>(</span><span>acc_fit_hog_seq</span><span>),</span><span> </span><span>'\n'</span><span>)</span><span>
</span><span>## mean accuracy for hog-features using cross-validation : 0.9788857</span><span>
</span></code></pre>
</div>
</div>
<p></p>
<p>The brute-force algorithm of the NMSLIB Library is almost <strong>6 times faster</strong> than KernelKnn giving an accuracy of approx. <strong>97.9 %</strong>.</p>
<p></p>
<p>The <em>README.md</em> file of the <em>nmslibR</em> package includes the SystemRequirements and installation instructions.</p>
<p>An updated version of the nmslibR package can be found in my <a rel="nofollow" href="https://github.com/mlampros/nmslibR" target="_blank">Github repository</a> and to report bugs/issues please use the following link, <a rel="nofollow" href="https://github.com/mlampros/nmslibR/issues" target="_blank">https://github.com/mlampros/nmslibR/issues</a>.</p>
<p></p>
	<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="http://mlampros.github.io/mlampros.github.io/2018/02/27/the_nmslibR_package/"> mlampros</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a rel="nofollow" href="https://www.r-project.org/" title="The R Project for Statistical Computing">R</a> news and <a rel="nofollow" href="https://www.r-bloggers.com/search/tutorial" title="R tutorials">tutorials</a> on topics such as: <a rel="nofollow" href="https://www.r-bloggers.com/search/data%20science" title="Data science">Data science</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data" title="Big Data">Big Data, <a rel="nofollow" href="https://www.r-users.com/" title="R jobs">R jobs</a>, visualization (<a rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2" title="ggplot and ggplot2 tutorials">ggplot2</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/boxplot" title="Boxplots using lattice and ggplot2 tutorials">Boxplots</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/map" title="Maps and gis">maps</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/animation" title="Animation in R">animation</a>), programming (<a rel="nofollow" href="https://www.r-bloggers.com/search/RStudio" title="RStudio IDE for R">RStudio</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/sweave" title="Sweave and literate programming">Sweave</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX" title="LaTeX in R">LaTeX</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/SQL" title="SQL and databases">SQL</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/eclipse" title="Eclipse IDE for R">Eclipse</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/git" title="git and github, Version Control System">git</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/hadoop" title="Large data in R using Hadoop">hadoop</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping" title="Web Scraping of google, facebook, yahoo, twitter and more using R">Web Scraping</a>) statistics (<a rel="nofollow" href="https://www.r-bloggers.com/search/regression" title="Regressions and ANOVA analysis tutorials">regression</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/PCA" title="principal component analysis tutorial">PCA</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/time+series" title="Time series">time series</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/trading" title="finance trading">trading</a>) and more...
<img width="1" alt="" src="http://feeds.feedburner.com/~r/RBloggers/~4/_hntQPtAkiE" height="1"></a></div>