k Nearest Neighbours Classifier (kNN) with Javascript Implementation for Beginners

k Nearest Neighbours Classifier (kNN) is a powerful but computational costly nonlinear classifier. Basically, kNN works based on distance calculation and finding of closest neighbour vectors according to a distance function. Distance function can be l1 (Manhattan distance), l2 (Euclidean distance) or a different available appropriate distance function. kNN uses a hyper parameter (k) that implies count of closest neighbours. 

Algorithm find closest k vector to current vector, and returns classification result as class label of the largest matched number of class between these k closest vectors.

In this example; classes 1,2,3 corresponds to red, green and purple respectively. Algorithm takes k, x and y as input and return class label as color and draw last input point as a orange point. 

->k

->X

->Y

Javascript Codes:

document.addEventListener('DOMContentLoaded', (e) => {

            drawPoints();
        });

        var point = { x: 0, y: 0 };
        var k = 3;

        var datas = [

            { c: 1, x: 10, y: 100 },
            { c: 1, x: -10, y: 50 },
            { c: 1, x: 50, y: 150 },
            { c: 2, x: 100, y: 80 },
            { c: 1, x: 30, y: 200 },
            { c: 2, x: 200, y: 50 },
            { c: 2, x: 120, y: 30 },
            { c: 2, x: 100, y: 150 },
            { c: 3, x: 300, y: 50 },
            { c: 1, x: -150, y: 200 },
            { c: 3, x: -300, y: 400 },
            { c: 3, x: 233, y: 333 },
            { c: 2, x: 127, y: 190 },
            { c: 3, x: 100, y: -32 },
            { c: 1, x: -50, y: -12 },
            { c: 1, x: -101, y: -50 },
            { c: 1, x: -301, y: -19 },
            { c: 2, x: 127, y: -22 },
            { c: 3, x: 120, y: -100 },
            { c: 2, x: -50, y: -200 },
            { c: 3, x: 800, y: 100 },
            { c: 3, x: 150, y: -150 },
            { c: 3, x: 70, y: -80 },
            { c: 3, x: 70, y: -500 },
            { c: 3, x: 200, y: -300 },
            { c: 2, x: -50, y: -150 },
            { c: 3, x: 111, y: -200 },
            { c: 3, x: 301, y: -310 },
            { c: 3, x: 200, y: -151 },
            { c: 1, x: -122, y: -99 },
            { c: 1, x: -301, y: -499 },
            { c: 1, x: 401, y: -1 },
        ];

        function start() {

            let classColor = "";

            setValues();

            drawCurrentPoint();

            let c = knnClassify();

            if (c == 1)
                classColor = "red";
            else if (c == 2)
                classColor = "green";
            else
                classColor = "purple";

            alert(classColor);
        }

        function knnClassify() {

            var classificationResults = [

                { c: 1, count: 0 },
                { c: 2, count: 0 },
                { c: 3, count: 0 }
            ];

            let distances = [];

            for (let i = 0; i < datas.length; i++) {

                let distance = l2Distance(datas[i], point);
                let distanceToClass = { c: datas[i].c, d: distance };

                distances.push(distanceToClass);
            }

            distances.sort(function (a, b) {

                return a.d - b.d;
            });

            for (let i = 0; i < k; i++) {

                for (let k = 0; k < classificationResults.length; k++) {

                    if (classificationResults[k].c == distances[i].c) {

                        classificationResults[k].count++;
                    }
                }
            }

            classificationResults.sort(function (a, b) {

                return b.count - a.count;
            });

            return classificationResults[0].c;
        }

        function l2Distance(point1, point2) {

            return Math.sqrt(Math.pow(point1.x - point2.x, 2) + Math.pow(point1.y - point2.y, 2));
        }

        function drawPoints() {

            var canvas = document.getElementById("g");

            for (let i = 0; i < datas.length; i++) {

                let circle = document.createElementNS('http://www.w3.org/2000/svg', 'circle');;
                circle.setAttributeNS(null, "cx", datas[i].x);
                circle.setAttributeNS(null, "cy", datas[i].y);
                circle.setAttributeNS(null, "r", 3);

                if (datas[i].c == 1)
                    circle.setAttributeNS(null, "fill", "red");
                else if (datas[i].c == 2)
                    circle.setAttributeNS(null, "fill", "green");
                else
                    circle.setAttributeNS(null, "fill", "purple");

                canvas.appendChild(circle);
            }
        }

        function drawCurrentPoint() {

            var canvas = document.getElementById("g");

            let circle = document.createElementNS('http://www.w3.org/2000/svg', 'circle');
            circle.setAttributeNS(null, "cx", point.x);
            circle.setAttributeNS(null, "cy", point.y);
            circle.setAttributeNS(null, "r", 3);

            circle.setAttributeNS(null, "fill", "orange");

            canvas.appendChild(circle);
        }
                   
        function setValues() {

            k = parseFloat(document.getElementById("pk").value);
            point.x = parseFloat(document.getElementById("pX").value);
            point.y = parseFloat(document.getElementById("pY").value);
        }

HTML Codes:

    <div>
        <input id="pk" type="text" value="3" />->k
    </div>
    <div>
        <input id="pX" type="text" value="0" />->X
    </div>
    <div>
        <input id="pY" type="text" value="0" />->Y
    </div>

    <div id="resultDiv" style="margin-top: 20px;"></div>
    <div style="margin-top: 20px;">
        <button onclick="start()" type="button">CLASSIFY</button>
    </div>

    <div style="margin-top: 50px;">
        <svg height="500" id="canvas" width="500">
            <g id="g" transform="translate(250 250) scale(1,-1)">
                <line style="stroke-width: 1; stroke: rgb(0, 0, 255);" x1="-1000" x2="1000" y1="0" y2="0"></line>
                <line style="stroke-width: 1; stroke: rgb(0, 0, 255);" x1="0" x2="0" y1="-1000" y2="1000"></line>

            </g>
        </svg>
    </div>

Support Vector Machines (SVM) with Javascript Implementation for Beginners

I give an example of javascript implementation of support vector machines (SVM) and I explain SVM algorithm with hinge loss function in this article.

SVM algorithm aims to find a hyperplane that separates dataset in two classes:

For SVM, classes take values {1,-1}. Algorithm tries to find a hyperplane by maximizing margin between support vectors and hyperplane. We can describe support vectors as closest vectors to hyperplane. In 2 dimensional space, a hyperplane corresponds to a line.

So, to calculate a hyperplane, we must define hyperplane function:

f(x) = wx + b;

In this example, our space is 2 dimensional, so we have a coordinate point (x,y) and a class label (c).

As a result, we have a dataset that consists of javascript objects that includes {c,x,y} properties. Before going to optimization step, we must define SVM loss function. In this loss function, yi corresponds to c and xi corresponds to x,y for our case.

SVM algorithm uses hinge loss function. This loss function penalizes incorrect classifications. Max function is a convex function, so we can use gradient descent algorithm (GDA) as optimization algorithm. In 2 dimension, we have w1, w2 and b as optimization parameters. So we calculate partial derivatives:

d/dw1 Loss(w1,w2,c,x,y,b) = -1 * c * x

d/dw2 Loss(w1,w2,c,x,y,b) = -1 * c * y

d/b Loss(w1,w2,c,x,y,b) = -1 * c

While calculating loss, we calculate all losses for all points and take their mean value. As a result, we can calculate w1,w2 and b by using GDA. In our example, 1 labeled class and -1 labeled class are drawn red and blue respectively.

->alfa (learning parameter)

->maxIteration

Javascript codes:

<script>

        var alfa = 0.001;
        var maxIteration = 300000;

        var w1 = 1;
        var w2 = 1;
        var b = 1;
        var dw1 = 0;
        var dw2 = 0;
        var db = 0;

        var datas = [

            { c: 1, x:10, y: 100 },
            { c: 1, x:-10, y: 50 },
            { c: 1, x:50, y: 150 },
            { c: 1, x:100, y: 80 }, 
            { c: 1, x:30, y: 200 },
            { c: 1, x:200, y: 50 },
            { c: 1, x: 120, y: 30 },
            { c: 1, x: 100, y: 150 },
            { c: 1, x: 300, y: 50 },
            { c: 1, x: -150, y: 200 },
            { c: 1, x: -300, y: 400 },
            { c: 1, x: 233, y: 333 },
            { c: 1, x: 127, y: 190 },
            { c: 1, x: 100, y: -32},
            { c: 1, x: -50, y: -12 },
            { c: 1, x: -101, y: -50 },
            { c: 1, x: -301, y: -19 },
            { c: 1, x: 127, y: -22 },
            { c: -1, x:120, y: -100 },
            { c: -1, x:-50, y: -200 },
            { c: -1, x:800, y: 100 },
            { c: -1, x:150, y: -150 },
            { c: -1, x:70, y: -80 },
            { c: -1, x: 70, y: -500 },
            { c: -1, x: 200, y: -300 },
            { c: -1, x: -50, y: -150 },
            { c: -1, x: 111, y: -200 },
            { c: -1, x: 301, y: -310 },
            { c: -1, x: 200, y: -151 },
            { c: -1, x: -122, y: -99 },
            { c: -1, x: -301, y: -499 },
            { c: -1, x: 401, y: -1 },
        ]

        function getHingeLoss(data) {

            let loss = 1 - (w1 * data.x + w2 * data.y + b) * data.c;

            if (loss > 0)
                return loss;
            else
                return 0;
        }

        function setGradients() {

            let cost = 0;

            for (let i = 0; i < datas.length; i++) {

                let loss = getHingeLoss(datas[i]);
                cost += loss;

                if (loss > 0) {

                    dw1 += (-1 * datas[i].x * datas[i].c);
                    dw2 += (-1 * datas[i].y * datas[i].c);
                    db += (-1 * datas[i].c);
                }
            }

            cost /= datas.length;
            dw1 /= datas.length;
            dw2 /= datas.length;
            db /= datas.length;

            return cost;
        }

        function train() {

            setValues();
            drawPoints();

            for (var i = 0; i < maxIteration; i++) {

                setGradients();

                w1 -= alfa * dw1;
                w2 -= alfa * dw2;
                b -= alfa * db;             
            }

            drawLine();

            let resultDiv = document.getElementById("resultDiv");
            resultDiv.innerHTML = "w1:" + w1 + ", w2:" + w2 + ",b:" + b;
        }

        function drawPoints() {

            var canvas = document.getElementById("g");

            for (let i = 0; i < datas.length; i++) {

                let circle = document.createElementNS('http://www.w3.org/2000/svg', 'circle');;
                circle.setAttributeNS(null, "cx", datas[i].x);
                circle.setAttributeNS(null, "cy", datas[i].y);
                circle.setAttributeNS(null, "r", 1);

                if (datas[i].c == 1)
                    circle.setAttributeNS(null, "fill", "red");
                else
                    circle.setAttributeNS(null, "fill", "blue");

                canvas.appendChild(circle);
            }
        }

        function drawLine() {

            var canvas = document.getElementById("g");

            let point1x = 1000;
            let point1y = (w1 * point1x + b) / (-1 * w2);
            let point2x = -1000;
            let point2y = (w1 * point2x + b) / (-1 * w2);

            let line = document.createElementNS('http://www.w3.org/2000/svg', 'line');
            line.setAttributeNS(null, "x1", point1x);
            line.setAttributeNS(null, "y1", point1y);
            line.setAttributeNS(null, "x2", point2x);
            line.setAttributeNS(null, "y2", point2y);
            line.setAttributeNS(null, "style", "stroke: rgb(0, 255, 0); stroke-width:1");
            canvas.appendChild(line);
        }

        function setValues() {

            alfa = parseFloat(document.getElementById("alfa").value);
            maxIteration = parseFloat(document.getElementById("maxIteration").value);
        }

    </script>

HTML codes:

<div>
        <input id="alfa" type="text" value="0.001" />->alfa
    </div>
    <div>
        <input id="maxIteration" type="text" value="300000" />->maxIteration
    </div>

    <div id="resultDiv" style="margin-top: 20px;"></div>
    <div style="margin-top: 20px;">
        <button onclick="train()" type="button">START</button>
    </div>

    <div style="margin-top: 50px;">
        <svg height="500" id="canvas" width="500">
            <g id="g" transform="translate(250 250) scale(1,-1)">
                <line style="stroke-width: 1; stroke: rgb(0, 0, 255);" x1="-1000" x2="1000" y1="0" y2="0"></line>
                <line style="stroke-width: 1; stroke: rgb(0, 0, 255);" x1="0" x2="0" y1="-1000" y2="1000"></line>

            </g>
        </svg>
    </div>