Golang Machine Learning - K Nearest Neighbours Algorithm

iris.csv

main.go

package main

import (
	"math"
	"sort"
)

// KNNDistanceFn defines a function that returns the distance between two n dimension vectors
type KNNDistanceFn func(v1, v2 []float64) float64

// KNNClassifier defines a labelled example for training a KNN algorithm
type KNNClassifierLabelledExample struct {
	FeatureVector []float64
	Label         int
}

// KNNClassifier represents a KNN algorithm
type KNNClassifier struct {
	k                int
	labelledExamples []KNNClassifierLabelledExample
	distanceFn       KNNDistanceFn
}

func NewKNNClassifier(k int, labelledExamples []KNNClassifierLabelledExample, distanceFn KNNDistanceFn) *KNNClassifier {
	return &KNNClassifier{
		k:                k,
		labelledExamples: labelledExamples,
		distanceFn:       distanceFn,
	}
}

type knnClassifierNeighbour struct {
	distance float64
	label    int
}

// Classify executes the KNN algorithm
func (c *KNNClassifier) Classify(v []float64) int {
	neighbours := []knnClassifierNeighbour{}

	for _, example := range c.labelledExamples {
		neighbours = append(neighbours, knnClassifierNeighbour{
			distance: c.distanceFn(v, example.FeatureVector),
			label:    example.Label,
		})
	}

	sort.SliceStable(neighbours, func(i, j int) bool {
		return neighbours[i].distance < neighbours[j].distance
	})

	var result int
	nearestNeightbourLabelCounts := map[int]int{}
	for i := 0; i < c.k; i++ {
		nearestNeightbourLabelCounts[neighbours[i].label]++
		count := nearestNeightbourLabelCounts[neighbours[i].label]

		if count > nearestNeightbourLabelCounts[result] {
			result = neighbours[i].label
		}
	}

	return result
}

// EuclideanDistance returns the Euclidean distance between two n dimesional vectors. Implements KNNDistanceFn.
func EuclideanDistance(v1 []float64, v2 []float64) float64 {
	lenv1 := len(v1)
	lenv2 := len(v2)

	if lenv1 > lenv2 {
		v2 = append(v2, make([]float64, 0, lenv2-lenv1)...)
	}

	if lenv2 > lenv1 {
		v1 = append(v1, make([]float64, 0, lenv1-lenv2)...)
	}

	var result float64
	for i := 0; i < len(v1); i++ {
		result += math.Pow(v2[i]-v1[i], 2)
	}

	return math.Sqrt(result)
}

main_test.go

package main

import (
	"encoding/csv"
	"errors"
	"io"
	"log"
	"math"
	"math/rand"
	"os"
	"strconv"
	"strings"
	"testing"
	"time"
)

func TestKNNClassifier(t *testing.T) {
	f, err := os.Open("./iris.csv")
	if err != nil {
		t.Fatal(err)
	}
	defer f.Close()

	labelledExamples, err := prepareIrisDataset(f)
	if err != nil {
		t.Fatal(err)
	}

	// shuffle slice
	rand.Seed(time.Now().UnixNano())
	rand.Shuffle(len(labelledExamples), func(i, j int) {
		labelledExamples[i], labelledExamples[j] = labelledExamples[j], labelledExamples[i]
	})

	acceptableMarginOfError := 0.05

	// split data between training and test data 80/20
	splitIndex := int(0.8 * float64(len(labelledExamples)))
	trainingData := labelledExamples[:splitIndex]
	testData := labelledExamples[splitIndex:]

	type incorrectlyClassifiedResult struct {
		labelledExample KNNClassifierLabelledExample
		actual          int
	}

	errs := []incorrectlyClassifiedResult{}
	k := int(math.Sqrt(float64(len(trainingData))))
	knnClassifier := NewKNNClassifier(k, trainingData, EuclideanDistance)
	for _, test := range testData {
		if actual := knnClassifier.Classify(test.FeatureVector); actual != test.Label {
			errs = append(errs, incorrectlyClassifiedResult{
				labelledExample: test,
				actual:          actual,
			})
		}
	}

	actualMarginOfError := float64(len(errs)) / float64(len(labelledExamples))
	if actualMarginOfError > acceptableMarginOfError {
		log.Fatalf("margin of error exceeds acceptable level. actual %f acceptable %f\n%v", actualMarginOfError, acceptableMarginOfError, errs)
	}

	log.Printf("actual margin of error %f", actualMarginOfError)
}

func TestEuclideandistance(t *testing.T) {
	tests := []struct {
		title    string
		v1, v2   []float64
		expected float64
	}{
		{
			"3d",
			[]float64{3, 6, 5},
			[]float64{7, -5, 1},
			12.369,
		},
	}

	for _, test := range tests {
		t.Run(test.title, func(t *testing.T) {
			if actual := EuclideanDistance(test.v1, test.v2); approx(actual, test.expected) {
				t.Fatalf("expected %f got %f", test.expected, actual)
			}
		})
	}
}

func prepareIrisDataset(r io.Reader) ([]KNNClassifierLabelledExample, error) {
	records, err := csv.NewReader(r).ReadAll()
	if err != nil {
		return nil, err
	}

	labelledExamples := []KNNClassifierLabelledExample{}
	for i, record := range records {
		if i == 0 { // skip header row
			continue
		}

		labelledExample := KNNClassifierLabelledExample{}
		for i := 0; i < 4; i++ {
			v, err := strconv.ParseFloat(record[i], 64)
			if err != nil {
				return nil, err
			}
			labelledExample.FeatureVector = append(labelledExample.FeatureVector, v)
		}

		switch strings.ToLower(record[4]) {
		case "setosa":
			labelledExample.Label = 0
		case "versicolor":
			labelledExample.Label = 1
		case "virginica":
			labelledExample.Label = 2
		default:
			return nil, errors.New("unexpected species: " + record[4])
		}

		labelledExamples = append(labelledExamples, labelledExample)
	}

	return labelledExamples, nil
}

func approx(v1, v2 float64) bool {
	return math.Abs(v1-v2) < 0.00000001
}