<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Turner Luke on Medium]]></title>
        <description><![CDATA[Stories by Turner Luke on Medium]]></description>
        <link>https://medium.com/@turnermluke?source=rss-ebd5762d3562------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*vmVUFa7lcjHuyhgvWaqokw.jpeg</url>
            <title>Stories by Turner Luke on Medium</title>
            <link>https://medium.com/@turnermluke?source=rss-ebd5762d3562------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Mon, 16 Nov 2026 08:06:50 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@turnermluke/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Create a Gradient Descent Algorithm with Regularization from Scratch in Python]]></title>
            <link>https://medium.com/data-science/create-a-gradient-descent-algorithm-with-regularization-from-scratch-in-python-571cb1b46642?source=rss-ebd5762d3562------2</link>
            <guid isPermaLink="false">https://medium.com/p/571cb1b46642</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[coding]]></category>
            <dc:creator><![CDATA[Turner Luke]]></dc:creator>
            <pubDate>Sun, 01 May 2022 21:23:20 GMT</pubDate>
            <atom:updated>2022-05-03T17:25:51.819Z</atom:updated>
            <content:encoded><![CDATA[<h4>Cement your knowledge of gradient descent by implementing it yourself</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*d9uP3lRksNU9fnAM" /><figcaption>Photo by <a href="https://unsplash.com/@blurredpictures?utm_source=medium&amp;utm_medium=referral">Andre Bernhardt</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><h3>Introduction</h3><p>Gradient descent is a fundamental algorithm used for machine learning and optimization problems. Thus, fully understanding its functions and limitations is critical for anyone studying machine learning or data science. This tutorial will implement a from-scratch gradient descent algorithm, test it on a simple model optimization problem, and lastly be adjusted to demonstrate parameter regularization.</p><h3>Background</h3><p>Gradient descent seeks to find a local minimum of the <strong>cost function</strong> by adjusting model parameters. The <strong>cost function</strong> (or loss function) maps variables onto a real number representing a “cost” or value to be minimized.</p><p>For our model optimization, we’ll perform <strong>least squares optimization</strong>, where we seek to minimize the sum of the differences between our predicted values, and the data values. <strong>Equation 1</strong> presents the quadratic cost function we’ll use.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/722/1*JCSegVSqJ253Xvmdb44WQA.png" /><figcaption>Image by author.</figcaption></figure><p><strong>Equation 1:</strong> <em>The least squares optimization cost function.</em></p><p>Here, yhat is the model prediction from the independent variable. For this analysis we’ll use a general polynomial model, presented in <strong>Equation 2</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1008/1*F5h7ctKkqcVL6K-1neVFWw.png" /><figcaption>Image by author.</figcaption></figure><p><strong>Equation 2:</strong> <em>The general polynomial model used in this analysis.</em></p><p>For simplicity, we’ll keep these equations in matrix form. Doing so presents our new model in <strong>Equation 3</strong> with the X matrix structure presented in <strong>Equation 4</strong>. Notice that yhat has size (n,), beta has size (m,), and X has size (n, m).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/274/1*j9I4EAc7354HEpxFAMjcBg.png" /><figcaption>Image by author.</figcaption></figure><p><strong>Equation 3:</strong> <em>The matrix form of our model.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*VXF5XjgLboYP0-tkugW8tA.png" /><figcaption>Image by author.</figcaption></figure><p><strong>Equation 4:</strong> <em>The polynomial matrix, X.</em></p><p>Now with this background of our cost function and the model we’ll be deploying, we can finally dive into the gradient descent algorithm.</p><h3>Algorithm</h3><p>Gradient descent works by calculating the <em>gradient</em> of the cost, and adjusting the parameters to <em>descend</em> the gradient like a slope.</p><p>The chain rule (recall multivariable calculus) provides us with a method of approximating the change in cost for a given change in parameters. This relationship is presented in <strong>Equation 5</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fbWVovPzUKbTktpm8dnQRw.png" /><figcaption>Image by author.</figcaption></figure><p><strong>Equation 5:</strong> <em>The chain rule applied to determine changes in cost for changes in parameters.</em></p><p>Knowing this, we can define a change in parameters to be proportional to the cost gradient, as presented in <strong>Equation 6</strong>. The learning rate (eta) is chosen to be a small, positive number.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/470/1*5TbUlnF5qN3Liop_splBVQ.png" /><figcaption>Image by author.</figcaption></figure><p><strong>Equation 6:</strong> <em>Parameter update rules.</em></p><p>When this rule to update parameters is plugged into <strong>Equation 5</strong>, we recieve our proof that the chosen parameter updating rule will always descend the cost.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XiEQ-QAHIlUyTQgq27C0wg.png" /><figcaption>Image by author.</figcaption></figure><p><strong>Equation 7:</strong> <em>Proof the parameter updating rule will decrease the cost.</em></p><p>If we recall linear algebra, we can remember that the square of the cost gradient vector will always be positive. Thus, provided the learning rate is small enough, this updating method will <em>descend the gradient</em> of the cost function.</p><p>Now, to finally implement this algorithm we need a method of numerically calculating the gradient. For this example we could sit with a pen and paper performing derivitives, however we’d like our algorithm to work for any model and cost function. <strong>Equation 8</strong> presents our method of doing so, where we will adjust each parameter by a small value and observe the change in cost.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1005/1*HZTrn86sSFHmRQd0wbovFg.png" /></figure><p><strong>Equation 8:</strong> <em>Numerical method of calculating the cost gradient.</em></p><h3>Data</h3><p>We’ll generate our own dataset for this project. We’ll simply generate a linearly spaced vector of independent values, and calculate the dependent variables from these, with some noise introduced. I’ve set a random seed, to allow you to see if you get the same results.</p><pre>import numpy as np<br>import matplotlib.pyplot as plt<br>np.random.seed(1234)</pre><pre>def polynomial_model(beta, x):<br>    &#39;&#39;&#39;<br>    A polynomial model.<br>    beta: numpy array of parameters of size (m,)<br>    x: numpy array of size (n,)</pre><pre>    return yhat: prediction of the model of size (n,)<br>    &#39;&#39;&#39;<br>    # Turn x (n,) to X (n, m) where m is the order of the polynomial<br>    # The second axis is the value of x**m<br>    X = x[:, np.newaxis] ** np.arange(0, len(beta))</pre><pre>    # Perform model prediction<br>    yhat = np.sum(beta * X, axis=1)</pre><pre>    return yhat</pre><pre># Construct a dataset<br>x = np.arange(-2, 3)<br>beta_actual = [1, 2, 1]<br>y = polynomial_model(beta_actual, x) + np.random.normal(size=x.size, scale=1)</pre><p>I’ve chosen the actual model parameters to be [1, 2, 3], and the noise to be a normal distribution with standard deviation of 1. Lets view the data below.</p><pre># Plot results<br>fig, ax = plt.subplots()<br>ax.plot(x, y, &#39;.&#39;)<br>xplt = np.linspace(min(x), max(x), 100)<br>yplt = polynomial_model(beta_actual, xplt)<br>plt.plot(xplt, yplt, &#39;-&#39;)</pre><pre>ax.legend([&#39;Data&#39;, &#39;Actual Relationship&#39;])</pre><pre>plt.show()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*xjZIkDFOKfGmjL4iTcOKaQ.png" /><figcaption>Image by author.</figcaption></figure><p><strong>Figure 1:</strong> <em>Our data and actual model.</em></p><h3>Model Creation</h3><h3>Functions</h3><p>Our cost function is defined below. Notice we’ll only make beta to be a positional, the rest we’ll pass with keyword arguments. This is to improve readability of our final gradient descent algorithm, which we’ll see later.</p><pre>def cost(beta, **kwargs):<br>    &quot;&quot;&quot;<br>    Calculates the quadratic cost, with an optional regularization<br>    :param beta: Model Parameters<br>    :param kwargs:<br>    :return:<br>    &quot;&quot;&quot;<br>    x = kwargs[&#39;x&#39;]<br>    y = kwargs[&#39;y&#39;]<br>    model = kwargs[&#39;model&#39;]</pre><pre>    # Calculate predicted y given parameters<br>    yhat = model(beta, x)</pre><pre>    # Calculate the cost<br>    C = sum((y-yhat)**2) / len(y)<br>    return C</pre><h3>Algorithm</h3><p>Our gradient descent class requires our model, cost function, an initial parameter guess, and our data. We could also tweak parameters like the learning rate or step in parameters to calculate the gradient, but for this analysis I set them to be sufficiently small numbers and did not optimize their values.</p><pre>class GradDescent:</pre><pre>    def __init__(self, model, C, beta0, x, y, dbeta=1E-8, eta=0.0001, ftol=1E-8):<br>        self.model = model<br>        self.C = C<br>        self.beta = beta0<br>        self.x = x<br>        self.y = y<br>        self.dbeta = dbeta<br>        self.eta = eta<br>        self.ftol = ftol</pre><p>Now we can finally implement the gradient descent algorithm. We’ll begin by creating a dictionary of inputs to our cost function that do not change by iteration.</p><pre>def descend(self):<br>        # This dict of cost parameters does not change between calls<br>        cost_inputs = {&#39;x&#39;: self.x,<br>                       &#39;y&#39;: self.y,<br>                       &#39;model&#39;: self.model<br>                       }</pre><p>Next we’ll initialize a list of costs, and begin iterating.</p><pre># Initialize a list of costs, with the indices being the iteration<br>        costs = [self.C(self.beta, **cost_inputs)]</pre><pre>        run_condition = True</pre><p>For each iteration we must:</p><ol><li>Calculate the gradient</li><li>Update the parameters</li><li>Calculate the new cost</li><li>Evaluate our running condition</li></ol><p>This process is presented below</p><pre>while run_condition:<br>            # Get the gradient of the cost<br>            delC = []</pre><pre>            for n, beta_n in enumerate(self.beta):<br>                # Create a temporary parameters vector, to change the nth parameter<br>                temp_beta = self.beta<br>                temp_beta[n] = beta_n + self.dbeta  # Adjusts the nth parameter by dbeta<br>                C_n = self.C(temp_beta, **cost_inputs)<br>                dC = C_n - costs[-1]<br>                delC.append(dC / self.dbeta)</pre><pre>            # Update the parameters<br>            self.beta = self.beta - self.eta * np.array(delC)</pre><pre>            # Re calc C<br>            costs.append(self.C(self.beta, **cost_inputs))</pre><pre>            # Evaluate running condition<br>            run_condition = abs(costs[-1] - costs[-2]) &gt; self.ftol</pre><p>Now we’re ready to implement our model. Lets initialize starting parameters, create a gradient descent object, optimize our model and plot the results.</p><pre># Initialize parameters, use a polynomial of order 5<br>beta0 = np.random.normal(size=(5,), scale=1)</pre><pre># Initialize a GradDescent object, perform descent and get parameters<br>gd = GradDescent(polynomial_model, cost, beta0, x, y)<br>gd.descend()</pre><pre>beta = gd.beta</pre><pre># Make model prediction with parameters<br>yhat = polynomial_model(beta, x)</pre><pre># Plot results<br>fig, ax = plt.subplots()<br>ax.plot(x, y, &#39;.&#39;)<br>ax.plot(x, yhat, &#39;x&#39;)<br>xplt = np.linspace(min(x), max(x), 100)<br>yplt = polynomial_model(beta_actual, xplt)<br>plt.plot(xplt, yplt, &#39;-&#39;)<br>yplt = polynomial_model(beta, xplt)<br>plt.plot(xplt, yplt, &#39;--&#39;)</pre><pre>ax.legend([&#39;Data&#39;, &#39;Predicted Values&#39;, &#39;Actual Relationship&#39;, &#39;Predicted Model&#39;])</pre><pre>plt.show()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*4cfEi_60lo7weCUIAMgLug.png" /><figcaption>Image by author.</figcaption></figure><p><strong>Figure 2:</strong> <em>4th order polynomial fit of our data.</em></p><p>Notice our model is intentionally overfitted. We have a 4th order polynomial fit to 5 data points, recall that an nth order polynomial can always perfectly predict n+1 data points, without any consideration to the underlying model.</p><p>Lets slightly modify our cost function to penalize the size of parameters. This process is referred to as <strong>regularization</strong> defined as the process of adding information in order to solve an ill-posed problem to prevent overfitting. We’ll perform two types of regularization, <strong>L1</strong> or <strong>Lasso Regression</strong> (Least absolute shrinkage and selection operator) and <strong>L2</strong> or <strong>Ridge Regression</strong>. The modified cost functions for these techniques are presented below in <strong>Equations 9 &amp; 10</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OU-fS_Q9UZxFgoxKAtzUNA.png" /><figcaption>Image by author.</figcaption></figure><p><strong>Equation 9:</strong> <em>Cost function for L1 Regularization.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ABjSpJQN7mzIhOgP6bwHXQ.png" /><figcaption>Image by author.</figcaption></figure><p><strong>Equation 10:</strong> <em>Cost function for L2 Regularization.</em></p><p>We can easily modify our code to handle these regularization techniques. The only changes will occur in the cost function and the GradDescent object, shown below.</p><pre>class GradDescent:</pre><pre>    def __init__(self, model, C, beta0, x, y, reg=None, lmda=0, dbeta=1E-8, eta=0.0001, ftol=1E-8):<br>        self.model = model<br>        self.C = C<br>        self.beta = beta0<br>        self.x = x<br>        self.y = y<br>        self.reg = reg<br>        self.lmda = lmda<br>        self.dbeta = dbeta<br>        self.eta = eta<br>        self.ftol = ftol<br></pre><pre>    def descend(self):<br>        # This dict of cost parameters does not change between calls<br>        cost_inputs = {&#39;x&#39;: self.x,<br>                       &#39;y&#39;: self.y,<br>                       &#39;reg&#39;: self.reg,<br>                       &#39;lmda&#39;: self.lmda,<br>                       &#39;model&#39;: self.model<br>                       }<br>        # Initialize a list of costs, with the indices being the iteration<br>        costs = [self.C(self.beta, **cost_inputs)]</pre><pre>        run_condition = True<br>        while run_condition:</pre><pre>            # Get the gradient of the cost<br>            delC = []</pre><pre>            for n, beta_n in enumerate(self.beta):<br>                # Create a temporary parameters vector, to change the nth parameter<br>                temp_beta = self.beta<br>                temp_beta[n] = beta_n + self.dbeta  # Adjusts the nth parameter by dbeta<br>                C_n = self.C(temp_beta, **cost_inputs)<br>                dC = C_n - costs[-1]<br>                delC.append(dC / self.dbeta)</pre><pre>            # Update the parameters<br>            self.beta = self.beta - self.eta * np.array(delC)</pre><pre>            # Re calc C<br>            costs.append(self.C(self.beta, **cost_inputs))</pre><pre>            # Evaluate running condition<br>            run_condition = abs(costs[-1] - costs[-2]) &gt; self.ftol</pre><pre>def cost(beta, **kwargs):<br>    &quot;&quot;&quot;<br>    Calculates the quadratic cost, with an optional regularization<br>    :param beta: Model Parameters<br>    :param kwargs:<br>    :return:<br>    &quot;&quot;&quot;<br>    x = kwargs[&#39;x&#39;]<br>    y = kwargs[&#39;y&#39;]<br>    reg = kwargs[&#39;reg&#39;]<br>    lmda = kwargs[&#39;lmda&#39;]<br>    model = kwargs[&#39;model&#39;]</pre><pre>    # Calculate predicted y given parameters<br>    yhat = model(beta, x)</pre><pre>    # Calculate the cost<br>    C = sum((y-yhat)**2) / len(y)<br>    if reg is not None:<br>        if reg == &#39;L1&#39;:  # For Lasso Regression (L1), add the magnitudes<br>            C += lmda * sum(abs(beta))<br>        elif reg == &#39;L2&#39;:  # For Ridge Regression (L2), add the squared magnitude<br>            C += lmda * sum(beta**2)<br>    return C</pre><p>Lets do a bit of tuning and see how this effects the bias and variance of our predicted model. This code is shown below, with the plot of comparisons in <strong>Figure 3</strong>.</p><pre>fig, axs = plt.subplots(1, 3, figsize=(15, 5))<br></pre><pre>for i, (reg, lmda) in enumerate(zip([None, &#39;L1&#39;, &#39;L2&#39;], [0, 1, 1])):<br>    # Initialize a GradDescent object, perform descent and get parameters<br>    gd = GradDescent(polynomial_model, cost, beta0, x, y, reg=reg, lmda=lmda)<br>    gd.descend()</pre><pre>    beta = gd.beta</pre><pre>    # Make model prediction with parameters<br>    yhat = polynomial_model(beta, x)</pre><pre>    axs[i].plot(x, y, &#39;.&#39;)<br>    axs[i].plot(x, yhat, &#39;x&#39;)<br>    xplt = np.linspace(min(x), max(x), 100)<br>    yplt = polynomial_model(beta_actual, xplt)<br>    axs[i].plot(xplt, yplt, &#39;--&#39;)<br>    yplt = polynomial_model(beta, xplt)<br>    axs[i].plot(xplt, yplt, &#39;--&#39;)</pre><pre>    # Set title<br>    if reg is not None:<br>        axs[i].set_title(reg)<br>    else:<br>        axs[i].set_title(&quot;No Regularization&quot;)</pre><pre>    # Clean up the plots - remove x,y ticks and labels<br>    axs[i].axes.xaxis.set_ticklabels([])<br>    axs[i].axes.yaxis.set_ticklabels([])<br>    axs[i].axes.xaxis.set_visible(False)<br>    axs[i].axes.yaxis.set_visible(False)<br></pre><pre>fig.legend([&#39;Data&#39;, &#39;Predicted Values&#39;, &#39;Actual Relationship&#39;, &#39;Predicted Model&#39;])</pre><pre>plt.show()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*SDI0OqqrXDlYJaAK0AEFzA.png" /><figcaption>Image by author.</figcaption></figure><p><strong>Figure 3:</strong> <em>Comparison of regularization methods.</em></p><p>We can qualitatively see that regularizing our parameters has improved our fit (i.e. made it more similar to the actual underlying model.) Try iterating on the parameter weight to see its effect on the final model.</p><h3>Conclusion</h3><p>We learned the fundamentals of gradient descent and implemented an easy algorithm in Python. After doing so, we made minimal changes to add regularization methods to our algorithm and learned about L1 and L2 regularization. I hope you enjoyed.</p><p><a href="https://github.com/turnerluke/ML-algos/blob/main/gradient_descent/GradDescent.py">See this project on GitHub</a><br><a href="https://www.linkedin.com/in/turnermluke/">Connect with me on LinkedIn</a><br><a href="https://medium.com/@turnermluke">Read some of my other Data Science articles</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=571cb1b46642" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/create-a-gradient-descent-algorithm-with-regularization-from-scratch-in-python-571cb1b46642">Create a Gradient Descent Algorithm with Regularization from Scratch in Python</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Create a K-Means Clustering Algorithm from Scratch in Python]]></title>
            <link>https://medium.com/data-science/create-your-own-k-means-clustering-algorithm-in-python-d7d4c9077670?source=rss-ebd5762d3562------2</link>
            <guid isPermaLink="false">https://medium.com/p/d7d4c9077670</guid>
            <category><![CDATA[data]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[unsupervised-learning]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[Turner Luke]]></dc:creator>
            <pubDate>Mon, 11 Apr 2022 00:14:20 GMT</pubDate>
            <atom:updated>2022-05-03T17:20:22.495Z</atom:updated>
            <content:encoded><![CDATA[<h4>Cement your knowledge of k-means clustering by implementing it yourself</h4><h3>Introduction</h3><p>k-means clustering is an <strong>unsupervised</strong> machine learning algorithm that seeks to segment a dataset into groups based on the similarity of datapoints. An unsupervised model has <strong>independent variables</strong> and no <strong>dependent variables</strong>.</p><p>Suppose you have a dataset of 2-dimensional scalar attributes:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1016/1*H_aefoRr0TPnkQWD9hbgrQ.png" /><figcaption>Image by author.</figcaption></figure><p>If the points in this dataset belong to distinct groups with attributes significantly varying between groups but not within, the points should form clusters when plotted.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*ea78Wc_MEd7esuzYkeoANg.png" /><figcaption>Image by author.</figcaption></figure><p><strong>Figure 1:</strong> <em>A dataset of points with groups of distinct attributes.</em></p><p>This dataset clearly displays 3 distinct classes of data. If we seek to assign a new data point to one of these three groups, it can be done by finding the midpoint of each group (centroid) and selecting the nearest centroid as the group of the unassigned data point.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*5D4A2q1wNYlD2AMkO3GjUg.png" /><figcaption>Image by author.</figcaption></figure><p><strong>Figure 2:</strong> <em>The data points are segmented into groups denoted with differing colors.</em></p><h3>Algorithm</h3><p>For a given dataset, k is specified to be the number of distinct groups the points belong to. These k centroids are first randomly initialized, then iterations are performed to optimize the locations of these k centroids as follows:</p><ol><li>The distance from each point to each centroid is calculated.</li><li>Points are assigned to their nearest centroid.</li><li>Centroids are shifted to be the average value of the points belonging to it. If the centroids did not move, the algorithm is finished, else repeat.</li></ol><h3>Data</h3><p>To evaluate our algorithm, we’ll first generate a dataset of groups in 2-dimensional space. The sklearn.datasets function make_blobs creates groupings of 2-dimensional normal distributions, and assigns a label corresponding to the group said point belongs to.</p><pre>import seaborn as sns<br>from sklearn.datasets import make_blobs<br>import matplotlib.pyplot as plt<br>from sklearn.preprocessing import StandardScaler</pre><pre>centers = 5<br>X_train, true_labels = make_blobs(n_samples=100, centers=centers, random_state=42)<br>X_train = StandardScaler().fit_transform(X_train)</pre><pre>sns.scatterplot(x=[X[0] for X in X_train],<br>                y=[X[1] for X in X_train],<br>                hue=true_labels,<br>                palette=&quot;deep&quot;,<br>                legend=None<br>                )</pre><pre>plt.xlabel(&quot;x&quot;)<br>plt.ylabel(&quot;y&quot;)<br>plt.show()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*dXBPArvY86zKzV71Z8Q6Bg.png" /><figcaption>Image by author.</figcaption></figure><p><strong>Figure 3:</strong> <em>The dataset we will use to evaluate our k means clustering model.</em></p><p>This dataset provides a unique demonstration of the k-means algorithm. Observe the orange point uncharacteristically far from its center, and directly in the cluster of purple data points. This point cannot be accurately classified as belonging to the right group, thus even if our algorithm works well it should incorrectly characterize it as a member of the purple group.</p><h3>Model Creation</h3><h3>Helper Functions</h3><p>We’ll need to calculate the distances between a point and a dataset of points multiple times in this algorithm. To do so, lets define a function that calculates Euclidean distances.</p><pre>def euclidean(point, data):<br>    &quot;&quot;&quot;<br>    Euclidean distance between point &amp; data.<br>    Point has dimensions (m,), data has dimensions (n,m), and output will be of size (n,).<br>    &quot;&quot;&quot;<br>    return np.sqrt(np.sum((point - data)**2, axis=1))</pre><h3>Implementation</h3><p>First, the k-means clustering algorithm is initialized with a value for k and a maximum number of iterations for finding the optimal centroid locations. If a maximum number of iterations is not considered when optimizing centroid locations, there is a risk of running an infinite loop.</p><pre>class KMeans:</pre><pre>    def __init__(self, n_clusters=8, max_iter=300):<br>        self.n_clusters = n_clusters<br>        self.max_iter = max_iter</pre><p>Now, the bulk of the algorithm is performed when fitting the model to a training dataset.</p><p>First we’ll initialize the centroids randomly in the domain of the test dataset, with a uniform distribution.</p><pre># Randomly select centroid start points, uniformly distributed across the domain of the dataset<br>min_, max_ = np.min(X_train, axis=0), np.max(X_train, axis=0)<br>self.centroids = [uniform(min_, max_) for _ in range(self.n_clusters)]</pre><p>Next, we perform the iterative process of optimizing the centroid locations.</p><p>The optimization process is to readjust the centroid locations to be the means of the points belonging to it. This process is to repeat until the centroids stop moving, or the maximum number of iterations is passed. We’ll use a while loop to account for the fact that this process does not have a fixed number of iterations. Additionally, you could also use a for loop that repeats max_iter times and breaks when the centroids stop changing.</p><p>Before beginning the while loop, we’ll initialize the variables used in the exit conditions.</p><pre>iteration = 0<br>prev_centroids = None</pre><p>Now, we begin the loop. We’ll iterate through the data points in the training set, assigning them to an initialized empty list of lists. The sorted_points list contains one empty list for each centroid, where data points are appended once they’ve been assigned.</p><pre>while np.not_equal(self.centroids, prev_centroids).any() and iteration &lt; self.max_iter:<br>    # Sort each data point, assigning to nearest centroid<br>    sorted_points = [[] for _ in range(self.n_clusters)]<br>    for x in X_train:<br>        dists = euclidean(x, self.centroids)<br>        centroid_idx = np.argmin(dists)<br>        sorted_points[centroid_idx].append(x)</pre><p>Now that we’ve assigned the whole training dataset to their closest centroids, we can update the location of the centroids and finish the iteration.</p><pre># Push current centroids to previous, reassign centroids as mean of the points belonging to them<br>    prev_centroids = self.centroids<br>    self.centroids = [np.mean(cluster, axis=0) for cluster in sorted_points]<br>    for i, centroid in enumerate(self.centroids):<br>        if np.isnan(centroid).any():  # Catch any np.nans, resulting from a centroid having no points<br>            self.centroids[i] = prev_centroids[i]<br>    iteration += 1</pre><p>After the completion of the iteration, the while conditions are checked again, and the algorithm will continue until the centroids are optimized or the max iterations are passed. The full fit method is included below.</p><pre>class KMeans:</pre><pre>    def __init__(self, n_clusters=8, max_iter=300):<br>        self.n_clusters = n_clusters<br>        self.max_iter = max_iter</pre><pre>    def fit(self, X_train):</pre><pre>        # Randomly select centroid start points, uniformly distributed across the domain of the dataset<br>        min_, max_ = np.min(X_train, axis=0), np.max(X_train, axis=0)<br>        self.centroids = [uniform(min_, max_) for _ in range(self.n_clusters)]</pre><pre>        # Iterate, adjusting centroids until converged or until passed max_iter<br>        iteration = 0<br>        prev_centroids = None<br>        while np.not_equal(self.centroids, prev_centroids).any() and iteration &lt; self.max_iter:<br>            # Sort each datapoint, assigning to nearest centroid<br>            sorted_points = [[] for _ in range(self.n_clusters)]<br>            for x in X_train:<br>                dists = euclidean(x, self.centroids)<br>                centroid_idx = np.argmin(dists)<br>                sorted_points[centroid_idx].append(x)</pre><pre>            # Push current centroids to previous, reassign centroids as mean of the points belonging to them<br>            prev_centroids = self.centroids<br>            self.centroids = [np.mean(cluster, axis=0) for cluster in sorted_points]<br>            for i, centroid in enumerate(self.centroids):<br>                if np.isnan(centroid).any():  # Catch any np.nans, resulting from a centroid having no points<br>                    self.centroids[i] = prev_centroids[i]<br>            iteration += 1</pre><p>Lastly, lets make a method to evaluate a set of points to the centroids we’ve optimized to our training set. This method returns the centroid and the index of said centroid for each point.</p><pre>def evaluate(self, X):<br>        centroids = []<br>        centroid_idxs = []<br>        for x in X:<br>            dists = euclidean(x, self.centroids)<br>            centroid_idx = np.argmin(dists)<br>            centroids.append(self.centroids[centroid_idx])<br>            centroid_idxs.append(centroid_idx)</pre><pre>        return centroids, centroid_idx</pre><h3>First Model Evaluation</h3><p>Now we can finally deploy our model. Lets train and test it on our original dataset and see the results. We’ll keep our original method of plotting our data, by separating the true labels by color, but now we’ll additionally separate the predicted labels by marker style, to see how the model performs.</p><pre>kmeans = KMeans(n_clusters=centers)<br>kmeans.fit(X_train)</pre><pre># View results<br>class_centers, classification = kmeans.evaluate(X_train)<br>sns.scatterplot(x=[X[0] for X in X_train],<br>                y=[X[1] for X in X_train],<br>                hue=true_labels,<br>                style=classification,<br>                palette=&quot;deep&quot;,<br>                legend=None<br>                )<br>plt.plot([x for x, _ in kmeans.centroids],<br>         [y for _, y in kmeans.centroids],<br>         &#39;+&#39;,<br>         markersize=10,<br>         )</pre><pre>plt.show()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*E3CJkzy-1sIMKi8KzSby5Q.png" /><figcaption>Image by author.</figcaption></figure><p><strong>Figure 4:</strong> <em>A failed example where one centroid has no points, and one contains two clusters.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*maxReYnbwcDAM-DspFaCjg.png" /><figcaption>Image by author.</figcaption></figure><p><strong>Figure 5:</strong> <em>A failed example where one centroid has no points, two contains two clusters, and two split one cluster.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*5IYsuMbelEwhgt1dNnHglg.png" /><figcaption>Image by author.</figcaption></figure><p><strong>Figure 6:</strong> <em>A failed example where two centroids contain one and a half clusters, and two centroids split a cluster.</em></p><h3>Re-evaluating Centroid Initialization</h3><p>Looks like our model isn’t performing very well. We can infer two primary problems from these three failed examples.</p><ol><li>If a centroid is initialized far from any groups, it is unlikely to move. (Example: the bottom right centroid in <strong>Figure 4</strong>.)</li><li>If centroids are initialized too close, they’re unlikely to diverge from one another. (Example: the two centroids in the green group in <strong>Figure 6</strong>.)</li></ol><p>We’ll begin to remedy these problems with a new process of initializing the centroid locations. This new method is referred to as the k-means++ algorithm.</p><ol><li>Initialize the first centroid as a random selection of one of the data points.</li><li>Calculate the sum of the distances between each data point and all the centroids.</li><li>Select the next centroid randomly, with a probability proportional to the total distance to the centroids.</li><li>Return to step 2. Repeat until all centroids have been initialized.</li></ol><p>This code is included below.</p><pre># Initialize the centroids, using the &quot;k-means++&quot; method, where a random datapoint is selected as the first,<br># then the rest are initialized w/ probabilities proportional to their distances to the first<br># Pick a random point from train data for first centroid<br>self.centroids = [random.choice(X_train)]</pre><pre>for _ in range(self.n_clusters-1):<br>    # Calculate distances from points to the centroids<br>    dists = np.sum([euclidean(centroid, X_train) for centroid in self.centroids], axis=0)<br>    # Normalize the distances<br>    dists /= np.sum(dists)<br>    # Choose remaining points based on their distances<br>    new_centroid_idx, = np.random.choice(range(len(X_train)), size=1, p=dists)<br>    self.centroids += [X_train[new_centroid_idx]]</pre><p>If we run this new model a few times we’ll see it performs much better, but still not always perfect.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*-6SIYlCcluy72uewowcypA.png" /><figcaption>Image by author.</figcaption></figure><p><strong>Figure 7:</strong> <em>An ideal convergence, after implementing the k-means++ initialization method.</em></p><h3>Conclusion</h3><p>And with that, we’re finished. We learned a simple, yet elegant implementation of an unsupervised machine learning model. The complete project code is included below.</p><pre>import numpy as np<br>import matplotlib.pyplot as plt<br>from sklearn.preprocessing import StandardScaler<br>from numpy.random import uniform<br>from sklearn.datasets import make_blobs<br>import seaborn as sns<br>import random<br></pre><pre>def euclidean(point, data):<br>    &quot;&quot;&quot;<br>    Euclidean distance between point &amp; data.<br>    Point has dimensions (m,), data has dimensions (n,m), and output will be of size (n,).<br>    &quot;&quot;&quot;<br>    return np.sqrt(np.sum((point - data)**2, axis=1))<br></pre><pre>class KMeans:</pre><pre>    def __init__(self, n_clusters=8, max_iter=300):<br>        self.n_clusters = n_clusters<br>        self.max_iter = max_iter</pre><pre>    def fit(self, X_train):</pre><pre>        # Initialize the centroids, using the &quot;k-means++&quot; method, where a random datapoint is selected as the first,<br>        # then the rest are initialized w/ probabilities proportional to their distances to the first<br>        # Pick a random point from train data for first centroid<br>        self.centroids = [random.choice(X_train)]</pre><pre>        for _ in range(self.n_clusters-1):<br>            # Calculate distances from points to the centroids<br>            dists = np.sum([euclidean(centroid, X_train) for centroid in self.centroids], axis=0)<br>            # Normalize the distances<br>            dists /= np.sum(dists)<br>            # Choose remaining points based on their distances<br>            new_centroid_idx, = np.random.choice(range(len(X_train)), size=1, p=dists)<br>            self.centroids += [X_train[new_centroid_idx]]</pre><pre>        # This initial method of randomly selecting centroid starts is less effective<br>        # min_, max_ = np.min(X_train, axis=0), np.max(X_train, axis=0)<br>        # self.centroids = [uniform(min_, max_) for _ in range(self.n_clusters)]</pre><pre>        # Iterate, adjusting centroids until converged or until passed max_iter<br>        iteration = 0<br>        prev_centroids = None<br>        while np.not_equal(self.centroids, prev_centroids).any() and iteration &lt; self.max_iter:<br>            # Sort each datapoint, assigning to nearest centroid<br>            sorted_points = [[] for _ in range(self.n_clusters)]<br>            for x in X_train:<br>                dists = euclidean(x, self.centroids)<br>                centroid_idx = np.argmin(dists)<br>                sorted_points[centroid_idx].append(x)</pre><pre>            # Push current centroids to previous, reassign centroids as mean of the points belonging to them<br>            prev_centroids = self.centroids<br>            self.centroids = [np.mean(cluster, axis=0) for cluster in sorted_points]<br>            for i, centroid in enumerate(self.centroids):<br>                if np.isnan(centroid).any():  # Catch any np.nans, resulting from a centroid having no points<br>                    self.centroids[i] = prev_centroids[i]<br>            iteration += 1</pre><pre>    def evaluate(self, X):<br>        centroids = []<br>        centroid_idxs = []<br>        for x in X:<br>            dists = euclidean(x, self.centroids)<br>            centroid_idx = np.argmin(dists)<br>            centroids.append(self.centroids[centroid_idx])<br>            centroid_idxs.append(centroid_idx)</pre><pre>        return centroids, centroid_idxs<br></pre><pre># Create a dataset of 2D distributions<br>centers = 5<br>X_train, true_labels = make_blobs(n_samples=100, centers=centers, random_state=42)<br>X_train = StandardScaler().fit_transform(X_train)</pre><pre># Fit centroids to dataset<br>kmeans = KMeans(n_clusters=centers)<br>kmeans.fit(X_train)</pre><pre># View results<br>class_centers, classification = kmeans.evaluate(X_train)<br>sns.scatterplot(x=[X[0] for X in X_train],<br>                y=[X[1] for X in X_train],<br>                hue=true_labels,<br>                style=classification,<br>                palette=&quot;deep&quot;,<br>                legend=None<br>                )<br>plt.plot([x for x, _ in kmeans.centroids],<br>         [y for _, y in kmeans.centroids],<br>         &#39;k+&#39;,<br>         markersize=10,<br>         )</pre><pre>plt.show()</pre><p>Thanks for reading!<br><a href="https://www.linkedin.com/in/turnermluke/">Connect with me on LinkedIn</a><br><a href="https://github.com/turnerluke/ML-algos/blob/main/k_means/k_means.py">See this project in GitHub</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d7d4c9077670" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/create-your-own-k-means-clustering-algorithm-in-python-d7d4c9077670">Create a K-Means Clustering Algorithm from Scratch in Python</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Create Your Own k-Nearest Neighbors Algorithm in Python]]></title>
            <link>https://medium.com/data-science/create-your-own-k-nearest-neighbors-algorithm-in-python-eb7093fc6339?source=rss-ebd5762d3562------2</link>
            <guid isPermaLink="false">https://medium.com/p/eb7093fc6339</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[tutorial]]></category>
            <category><![CDATA[data-science]]></category>
            <dc:creator><![CDATA[Turner Luke]]></dc:creator>
            <pubDate>Sat, 09 Apr 2022 01:26:28 GMT</pubDate>
            <atom:updated>2022-05-03T17:18:17.420Z</atom:updated>
            <content:encoded><![CDATA[<h3>Create a K-Nearest Neighbors Algorithm from Scratch in Python</h3><h4>Cement your knowledge of KNN by implementing it yourself</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*BuernlLyuIvHAgb5" /><figcaption>Photo by <a href="https://unsplash.com/@markusspiske?utm_source=medium&amp;utm_medium=referral">Markus Spiske</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><h3>Introduction</h3><p>A famous quote states: “You are the average of the five people you spend the most time with.” Although we won’t be modelling the qualities of your friendships (portfolio project anyone?), this tutorial will teach a simple and intuitive algorithmic approach to classifying data based on their neighbors. The k-nearest neighbors (knn) algorithm is a supervised learning algorithm with an elegant execution and a surprisingly easy implementation. Because of this, knn presents a great learning opportunity for machine learning beginners to create a powerful classification or regression algorithm, with a few lines of Python code.</p><h3>Algorithm</h3><p>Knn is a <strong>supervised</strong> machine learning algorithm. A supervised model has both a <strong>target variable</strong> and <strong>independent variables</strong>. The <strong>target variable</strong> or dependent variable, denoted y, depends on the independent variables and is the value you seek to predict. The <strong>independent variables</strong>, denoted x (single valued) or X (multi valued), are known ahead of time and are used to predict y.</p><p>Knn can be used for both <strong>classification</strong> and <strong>regression</strong>. <strong>Classification</strong> models predict a <em>categorical</em> target variable and <strong>regression</strong> models predict a <em>numeric</em> target.</p><p>Suppose you have a dataset of scalar attributes and classes corresponding to those attributes.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*iM3GTYZdDhkLz8Ob9QkZrQ.png" /><figcaption>Image by author.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/623/1*_KWItDJn99blfo_KUtSN-Q.png" /><figcaption>Image by author.</figcaption></figure><p>Here, n is the total number of data points and m is the total number of classes. Instead of y being a class, it could also be a scalar value, and knn can be used as a regression, but for this tutorial we will focus on classification.</p><p>With this two dimensional example we can easily visualize these points in two-dimensional space. Assuming that classes will tend to cluster with points of the same class in this space, we can classify a new point by the most frequently occurring class near it. Thus, at a given point k is specified as the number of neighbors to consider near said point, and from those neighbors the most frequently occurring class is predicted to be the class of the point at hand.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/532/1*3YDJqw62VAxkHjgQkmWm_g.png" /><figcaption>Image by author.</figcaption></figure><p><strong>Figure 1:</strong> <em>This point is classified as group 1 when k=1.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/532/1*IGJ9zJd_nLJcnlnT4_lHew.png" /><figcaption>Image by author.</figcaption></figure><p><strong>Figure 2:</strong> <em>This point is classified as group 0 when k=3.</em></p><h3>Data</h3><p>We’ll evaluate our algorithm with the <a href="https://archive.ics.uci.edu/ml/datasets/iris">UCI Machine Learning Repository iris dataset</a>. However, any classification dataset consisting of scalar inputs will do. We’ll unpack the dataset, and standardize the attributes to have zero mean and unit variance. This is done because we don’t want to pass any judgements on which features are most important for predicting the class (for this analysis!). Lastly, we’ll split our dataset into training and testing sets, with the test set consisting of 20% of the original dataset.</p><pre>from sklearn import datasets<br>from sklearn.model_selection import train_test_split<br>from sklearn.preprocessing import StandardScaler</pre><pre># Unpack the iris dataset, from UCI Machine Learning Repository<br>iris = datasets.load_iris()<br>X = iris[&#39;data&#39;]<br>y = iris[&#39;target&#39;]</pre><pre># Preprocess data<br>X = StandardScaler().fit_transform(X)</pre><pre># Split data into train &amp; test sets<br>X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)</pre><h3>Model Creation</h3><p><strong>Helper Functions</strong></p><p>We’ll need to figure out the most commonly occuring element in a given group at numerous times in this algorithm. The following function presents an intuitive and Pythonic method of finding the most common element in a list.</p><pre>def most_common(lst):<br>    &#39;&#39;&#39;Returns the most common element in a list&#39;&#39;&#39;<br>    return max(set(lst), key=lst.count)</pre><p>Next, we’ll need to calculate the distance between a point and every point in a dataset. The most common and intuitive method of doing this is by euclidean distance, however other distance methods can be used.</p><pre>def euclidean(point, data):<br>    &#39;&#39;&#39;Euclidean distance between a point  &amp; data&#39;&#39;&#39;<br>    return np.sqrt(np.sum((point - data)**2, axis=1))</pre><p><strong>Implementation</strong></p><p>Now, lets begin to construct a knn class. For a given knn classifier, we’ll specify k and a distance metric. To keep the implementation of this algorithm similar to that of the widely-used scikit-learn suite, we’ll initialize the self.X_train and self.y_train in a fit method, however this could be done on initialization.</p><pre>class KNeighborsClassifier():<br>    def __init__(self, k=5, dist_metric=euclidean):<br>        self.k = k<br>        self.dist_metric = dist_metric</pre><pre>    def fit(self, X_train, y_train):<br>        self.X_train = X_train<br>        self.y_train = y_train</pre><p>Next, the bulk of the knn algorithm is performed by the prediction method. A dataset of attributes (X_test) is iterated through, point by point. For each datapoint the following steps are performed:</p><ol><li>Distances to every point in the training dataset is calculated</li><li>The training dataset classes are sorted by distance to the data point</li><li>The first k classes are kept and stored in the neighbors list Now we simply map the list of nearest neighbors to our most_common function, returning a list of predictions for each point passed in X_test.</li></ol><pre>class KNeighborsClassifier():<br>    def __init__(self, k=5, dist_metric=euclidean):<br>        self.k = k<br>        self.dist_metric = dist_metric</pre><pre>    def fit(self, X_train, y_train):<br>        self.X_train = X_train<br>        self.y_train = y_train</pre><pre>    def predict(self, X_test):<br>        neighbors = []<br>        for x in X_test:<br>            distances = self.dist_metric(x, self.X_train)<br>            y_sorted = [y for _, y in sorted(zip(distances, self.y_train))]<br>            neighbors.append(y_sorted[:self.k])</pre><pre>        return list(map(most_common, neighbors))</pre><p>Lastly, an evaluate method is defined to conveniently evaluate the performance of our model. A dataset of attributes and their classes are passed as X_test and y_test, and the predictions of the model from the attributes are compared to the actual classes.</p><pre>class KNeighborsClassifier():<br>    def __init__(self, k=5, dist_metric=euclidean):<br>        self.k = k<br>        self.dist_metric = dist_metric</pre><pre>    def fit(self, X_train, y_train):<br>        self.X_train = X_train<br>        self.y_train = y_train</pre><pre>    def predict(self, X_test):<br>        neighbors = []<br>        for x in X_test:<br>            distances = self.dist_metric(x, self.X_train)<br>            y_sorted = [y for _, y in sorted(zip(distances, self.y_train))]<br>            neighbors.append(y_sorted[:self.k])</pre><pre>        return list(map(most_common, neighbors))</pre><pre>    def evaluate(self, X_test, y_test):<br>        y_pred = self.predict(X_test)<br>        accuracy = sum(y_pred == y_test) / len(y_test)<br>        return accuracy</pre><p>Believe it or not, we’re finished — we can easily deploy this algorithm to model classification problems. But, for completeness we should optimize k for the iris dataset. We can do this by iterating through a range of k and plotting the performance of the model.</p><pre>accuracies = []<br>ks = range(1, 30)<br>for k in ks:<br>    knn = KNeighborsClassifier(k=k)<br>    knn.fit(X_train, y_train)<br>    accuracy = knn.evaluate(X_test, y_test)<br>    accuracies.append(accuracy)</pre><pre>fig, ax = plt.subplots()<br>ax.plot(ks, accuracies)<br>ax.set(xlabel=&quot;k&quot;,<br>       ylabel=&quot;Accuracy&quot;,<br>       title=&quot;Performance of knn&quot;)<br>plt.show()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/0*HEx1LkdHYSLCM2qx" /><figcaption>Image by author.</figcaption></figure><p><strong>Figure 3:</strong> <em>knn accuracy versus k</em></p><p>Looks like our knn model performs best at low k.</p><h3>Conclusion</h3><p>And with that we’re done. We’ve implemented a simple and intuitive k-nearest neighbors algorithm with under 100 lines of python code (under 50 excluding the plotting and data unpacking). The entire project code is included below.</p><pre>import numpy as np<br>import matplotlib.pyplot as plt<br>from sklearn import datasets<br>from sklearn.model_selection import train_test_split<br>from sklearn.preprocessing import StandardScaler<br></pre><pre>def most_common(lst):<br>    return max(set(lst), key=lst.count)<br></pre><pre>def euclidean(point, data):<br>    # Euclidean distance between points a &amp; data<br>    return np.sqrt(np.sum((point - data)**2, axis=1))<br></pre><pre>class KNeighborsClassifier:<br>    def __init__(self, k=5, dist_metric=euclidean):<br>        self.k = k<br>        self.dist_metric = dist_metric</pre><pre>    def fit(self, X_train, y_train):<br>        self.X_train = X_train<br>        self.y_train = y_train</pre><pre>    def predict(self, X_test):<br>        neighbors = []<br>        for x in X_test:<br>            distances = self.dist_metric(x, self.X_train)<br>            y_sorted = [y for _, y in sorted(zip(distances, self.y_train))]<br>            neighbors.append(y_sorted[:self.k])</pre><pre>        return list(map(most_common, neighbors))</pre><pre>    def evaluate(self, X_test, y_test):<br>        y_pred = self.predict(X_test)<br>        accuracy = sum(y_pred == y_test) / len(y_test)<br>        return accuracy<br></pre><pre># Unpack the iris dataset, from UCI Machine Learning Repository<br>iris = datasets.load_iris()<br>X = iris[&#39;data&#39;]<br>y = iris[&#39;target&#39;]</pre><pre># Split data into train &amp; test sets<br>X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)</pre><pre># Preprocess data<br>ss = StandardScaler().fit(X_train)<br>X_train, X_test = ss.transform(X_train), ss.transform(X_test)</pre><pre># Test knn model across varying ks<br>accuracies = []<br>ks = range(1, 30)<br>for k in ks:<br>    knn = KNeighborsClassifier(k=k)<br>    knn.fit(X_train, y_train)<br>    accuracy = knn.evaluate(X_test, y_test)<br>    accuracies.append(accuracy)</pre><pre># Visualize accuracy vs. k<br>fig, ax = plt.subplots()<br>ax.plot(ks, accuracies)<br>ax.set(xlabel=&quot;k&quot;,<br>       ylabel=&quot;Accuracy&quot;,<br>       title=&quot;Performance of knn&quot;)<br>plt.show()</pre><p>Returning to our quote “You are the average of the five people you spend the most time with”, knn classification should instead say “You are the most frequent of the k people you spend the most time with.” For an independent challenge adapt this code to better fit the original code by creating a knn regression model, where a point is interpreted as the average scalar target value of its k nearest neighbors.</p><p>Thanks for reading!<br><a href="https://www.linkedin.com/in/turnermluke/">Connect with me on LinkedIn</a><br><a href="https://github.com/turnerluke/ML-algos/blob/main/knn/KNeighborsClassifier.py">See this project in GitHub</a><br><a href="https://github.com/turnerluke/ML-algos/blob/main/knn/KNeighborsRegressor.py">See a knn regression implementation</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=eb7093fc6339" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/create-your-own-k-nearest-neighbors-algorithm-in-python-eb7093fc6339">Create Your Own k-Nearest Neighbors Algorithm in Python</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>