<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/create-your-machine-learning-library-from-scratch-with-r-3-5-knn/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://enhancedatascience.com/2018/05/23/create-your-machine-learning-library-from-scratch-with-r-3-5-knn/"> Enhance Data Science</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p>This is this second post of the “Create your Machine Learning library from scratch with R !” series. Today, we will see how you can implement K nearest neighbors (KNN) using only the linear algebra available in R. Previously, we managed to implement <a rel="nofollow" href="http://enhancedatascience.com/2018/01/30/your-own-machine-learning-library-from-scratch-with-r/" target="_blank">PCA</a> and next time we will deal with SVM and decision trees.</p>
<p>The K-nearest neighbors (KNN) is a simple yet efficient classification and regression algorithm. KNN assumes that an observation will be similar to its K closest neighbors. For instance, if most of the neighbors of a given point belongs to a given class, it seems reasonable to assume that the point will belong to the same given class.</p>
<h2> The mathematics of KNN </h2>
<p>Now, let’s quickly derive the mathematics used for KNN regression (they are similar for classification).</p>
<p>Let <img src="https://i2.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-3981a72eefc3ea28c988345ea7f9de44_l3.png?resize=60%2C12" alt="mathbf{x}_1, ... mathbf{x}_n" width="60" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="12"> be the observations of our training dataset. The points are in <img src="https://i2.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-1c0482903eca270e22dc7029f25a70a3_l3.png?resize=20%2C12" alt="mathbb{R}^{p}" width="20" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="12">. We denote <img src="https://i0.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-06b9241bb6853722dafd259858bbe7d2_l3.png?resize=64%2C12" alt="y_1, ..., y_n" width="64" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="12"> the variable we seek to estimate. We know its value for the train dataset.<br>
Let <img src="https://i2.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-975210d3049a3072b4e1dace4c33d1ef_l3.png?resize=36%2C13" alt="mathbf{x}_{n+1}" width="36" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="13"> be a new point in <img src="https://i2.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-1c0482903eca270e22dc7029f25a70a3_l3.png?resize=20%2C12" alt="mathbb{R}^{p}" width="20" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="12">. We do not know <img src="https://i1.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-291357f9313e465b24df85cb0342108d_l3.png?resize=34%2C13" alt="y_{n+1}" width="34" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="13"> and will estimate it using our train dataset.</p>
<p>Let <img src="https://i1.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-d42bc2203d6f76ad01b27ac9acc0bee1_l3.png?resize=9%2C13" alt="k" width="9" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="13"> be a positive and non-zero integer (the number of neighbors used for estimation). We want to select the <img src="https://i1.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-d42bc2203d6f76ad01b27ac9acc0bee1_l3.png?resize=9%2C13" alt="k" width="9" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="13"> points from the dataset which are the closest to <img src="https://i2.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-975210d3049a3072b4e1dace4c33d1ef_l3.png?resize=36%2C13" alt="mathbf{x}_{n+1}" width="36" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="13">. To do so, we compute the euclidean distance <img src="https://i2.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-3712564e2778cb5598cf0d315496722a_l3.png?resize=150%2C19" alt="d_i=||mathbf{x}_i-mathbf{x}_{n+1}||_{L2}" width="150" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="19">. From all the distance, we can compute <img src="https://i2.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-99ae29b7c7559ce378c0e9a84e6d671a_l3.png?resize=22%2C15" alt="D_k" width="22" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="15">, the smallest radius of the circle centered on <img src="https://i2.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-975210d3049a3072b4e1dace4c33d1ef_l3.png?resize=36%2C13" alt="mathbf{x}_{n+1}" width="36" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="13"> which includes exactly <img src="https://i1.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-d42bc2203d6f76ad01b27ac9acc0bee1_l3.png?resize=9%2C13" alt="k" width="9" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="13"> points from the training sample.</p>
<p>An estimation <img src="https://i0.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-79a60314000f085735242b22ee5c3a09_l3.png?resize=34%2C18" alt="hat{y}_{n+1}" width="34" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="18"> of <img src="https://i1.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-291357f9313e465b24df85cb0342108d_l3.png?resize=34%2C13" alt="y_{n+1}" width="34" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="13"> is now easy to construct. This is the mean of the <img src="https://i0.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-761333a1d61654bd1cb5c7224b0d1994_l3.png?resize=14%2C12" alt="y_i" width="14" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="12"> of the <img src="https://i1.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-d42bc2203d6f76ad01b27ac9acc0bee1_l3.png?resize=9%2C13" alt="k" width="9" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="13"> closest points to <img src="https://i2.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-975210d3049a3072b4e1dace4c33d1ef_l3.png?resize=36%2C13" alt="mathbf{x}_{n+1}" width="36" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="13">:</p>
<p><span>   </span><span>   </span><img src="https://i0.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-a784f7618ac2186b10736ebb6e7f1c61_l3.png?resize=167%2C47" width="167" alt="[hat{y}_{n+1} = frac{1}{k} sum_{ileq n} y_i 1_{d_i leq D_k}]" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="47"></p>
<h3> KNN regression in R </h3>
<p>First, we build a “my_knn_regressor” object which stores all the training points, the value of the target variable and the number of neighbors to use.</p>
<pre>
my_knn_regressor &lt;- function(x,y,k=5)
{
  if (!is.matrix(x))
  {
    x &lt;- as.matrix(x)
  }
  if (!is.matrix(y))
  {
    y &lt;- as.matrix(y)
  }
  my_knn &lt;- list()
  my_knn[['points']] &lt;- x
  my_knn[['value']] &lt;- y
  my_knn[['k']] &lt;- k
  attr(my_knn, &quot;class&quot;) &lt;- &quot;my_knn_regressor&quot;
  return(my_knn)
}
</pre>
<p>The tricky part of KNN is to compute efficiently the distance. We will use the function we created in our <a rel="nofollow" href="http://enhancedatascience.com/2018/05/06/machine-learning-explained-vectorization-and-matrix-operations/" target="_blank">previous post on vectorization</a>. The function and mathematical derivations are specified in this post.</p>
<pre>
gramMatrix &lt;- function(X,Y)
{
  tcrossprod(X, Y)
}
compute_pairwise_distance=function(X,Y)
{
  xn &lt;- rowSums(X ** 2)
  yn &lt;- rowSums(Y ** 2)
  outer(xn, yn,'+') - 2 * tcrossprod(X, Y)
}
</pre>
<p>Now we can build our predictor:</p>
<pre>
predict.my_knn_regressor &lt;- function(my_knn,x)
{
  if (!is.matrix(x))
  {
    x=as.matrix(x)
  }
  ##Compute pairwise distance
  dist_pair &lt;- compute_pairwise_distance(x,my_knn[['points']])
  ##as.matrix(apply(dist_pair,2,order) &lt;= my_knn[['k']]) orders the points by distance and select the k-closest points
  ##The M[i,j]=1 if x_j is on the k closest point to x_i
  t(as.matrix(apply(dist_pair,2,order) &lt;= my_knn[['k']])) %*% my_knn[['value']] / my_knn[['k']]
}
</pre>
<p>The last line may seem complicated:</p>
<ol>
<li> <code>apply(dist_pair,2,order)</code> orders the points by distance</li>
<li> <code>apply(dist_pair,2,order)&lt;=my_knn[['k']]</code> selects the k-closest points to each point in our new dataset </li>
<li> <code>M=t(as.matrix(apply(dist_pair,2,order) &lt;= my_knn[['k']])) </code> cast the matrix into a one hot matrix. <img src="https://i2.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-668b97602ee1b5f1425ca1746c2a23aa_l3.png?resize=67%2C18" alt="mathbf{M}_{i,j}=1" width="67" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="18"> if <img src="https://i0.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-c8cc5773890e905b537e12904245f3bf_l3.png?resize=17%2C14" alt="mathbf{x}_j" width="17" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="14"> is one of the k closest points to <img src="https://i0.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-401eedfa05ced230d5b10904f01fbd32_l3.png?resize=16%2C11" alt="mathbf{x}_i" width="16" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="11">. <img src="https://i2.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-569d20614ce104d8380e64d5ff81ed40_l3.png?resize=34%2C18" alt="mathbf{M}_{i,j}" width="34" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="18"> is zero otherwise.</li>
<li> <code>M %*% my_knn[['value']] / my_knn </code> sums the value of the k closest points and normalises it by k </li>
</ol>
<h2>KNN Binary Classification in R </h2>
<p>The previous code can be reused as it is for binary classification. Your outcome should be encoded as a one-hot variable. If the estimated output is greater (resp. less) than 0.5, you can assume that your point belongs to the class encoded as one (resp. zero). We will use the classical Iris dataset and classify the setosa versus the virginica specy.</p>
<pre>
iris_class &lt;- iris[iris[[&quot;Species&quot;]]!=&quot;versicolor&quot;,]
iris_class[[&quot;Species&quot;]] &lt;- as.numeric(iris_class[[&quot;Species&quot;]]!=&quot;setosa&quot;)
knn_class &lt;- my_knn_regressor(iris_class[,1:2],iris_class[,5])
predict(knn_class,iris_class[,1:2])
</pre>
<p>Since, we only used 2 variables, we can easily plot the decision boundaries on a 2D plot.</p>
<pre>
#Build grid
x_coord &lt;- seq(min(iris_class[,1]) - 0.2,max(iris_class[,1]) + 0.2,length.out = 200)
y_coord &lt;- seq(min(iris_class[,2])- 0.2,max(iris_class[,2]) + 0.2 , length.out = 200)
coord &lt;- expand.grid(x=x_coord, y=y_coord)
#predict probabilities
coord[['prob']] &lt;- predict(knn_class,coord[,1:2])

library(ggplot2)
ggplot() + 
  ##Ad tiles according to probabilities
  geom_tile(data=coord,mapping=aes(x, y, fill=prob)) + scale_fill_gradient(low = &quot;lightblue&quot;, high = &quot;red&quot;) +
  ##add points
  geom_point(data=iris_class,mapping=aes(Sepal.Length,Sepal.Width, shape=Species),size=3 ) + 
  #add the labels to the plots
  xlab('Sepal length') + ylab('Sepal width') + ggtitle('Decision boundaries of KNN')+
  #remove grey border from the tile
  scale_x_continuous(expand=c(0,0)) + scale_y_continuous(expand=c(0,0))
</pre>
<p>And this gives us this cool plot:<img data-orig-file="https://i2.wp.com/enhancedatascience.com/wp-content/uploads/2018/05/decision_boundary.png?fit=833%2C560" data-orig-size="833,560" data-medium-file="https://i2.wp.com/enhancedatascience.com/wp-content/uploads/2018/05/decision_boundary.png?fit=300%2C202" data-attachment-id="3063" data-image-meta="{" data-image-description="" src="https://i2.wp.com/enhancedatascience.com/wp-content/uploads/2018/05/decision_boundary.png?resize=640%2C430" data-permalink="http://enhancedatascience.com/2018/05/23/create-your-machine-learning-library-from-scratch-with-r-3-5-knn/decision_boundary/" data-large-file="https://i2.wp.com/enhancedatascience.com/wp-content/uploads/2018/05/decision_boundary.png?fit=640%2C430" alt="" data-image-title="Decision boundary" sizes="(max-width: 640px) 100vw, 640px" width="450" data-comments-opened="1" class="wp-image-3063" data-recalc-dims="1"></p>
<h2>Possible extensions </h2>
<p>Our current KNN is basic, but you can improve and test it in several ways:</p>
<ul>
<li> What is the influence of the number of neighbors ? (You should see some overfitting/underfitting)</li>
<li> Can you implement other metrics than <img src="https://i0.wp.com/enhancedatascience.com/wp-content/ql-cache/quicklatex.com-a84cb3ce6c36a1bd1f3c19c9a488afeb_l3.png?resize=19%2C15" alt="L_2" width="19" title="Rendered by QuickLaTeX.com" data-recalc-dims="1" height="15"> distance ? Can you create kernel KNNs ? </li>
<li> Instead of doing estimations using only the mean, could you use a more complex mapping ?</li>
</ul>
<p>Thanks for reading ! To find more posts on Machine Learning, Python and R, you can follow us on <a rel="nofollow" href="https://www.facebook.com/EnhanceDataScience/" target="_blank">Facebook</a> or <a rel="nofollow" href="https://twitter.com/AntGuilllot" target="_blank">Twitter</a>.</p>
<p>The post <a rel="nofollow" href="http://enhancedatascience.com/2018/05/23/create-your-machine-learning-library-from-scratch-with-r-3-5-knn/" target="_blank">Create your Machine Learning library from scratch with R ! (3/5) – KNN</a> appeared first on <a rel="nofollow" href="http://enhancedatascience.com/" target="_blank">Enhance Data Science</a>.</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://enhancedatascience.com/2018/05/23/create-your-machine-learning-library-from-scratch-with-r-3-5-knn/"> Enhance Data Science</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 alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/tAndccwKnEM" height="1"></a></div>