A Tiny Nearest Neighbor Classification Implementation in C#

Question

I am practicing to implement the KNN classification tool in C#. The basic point structure is constructed by the class Point, and there are two members in Point class: a list of double number and a string. A list of double number is used in order to represent location data in multi-dimensional space. A string is to represent the point label. For example, there are five points (on X-Y plane) here: A(0, 0), B(1, 0), C(0,1), D(10, 0) and E(10, 1). Moreover, point A, B and C are belong to class1, and point D and E are belong to class 2. They can be constructed as the following code.

var pointA = new Point(new List<double>() {0, 0}, "class1");
var pointB = new Point(new List<double>() {1, 0}, "class1");
var pointC = new Point(new List<double>() {0, 1}, "class1");
var pointD = new Point(new List<double>() {10, 0}, "class2");
var pointE = new Point(new List<double>() {10, 1}, "class2");

The Point class implementation.

public class Point
{
    List<double> location;
    string label;
    public Point(List<double> newLocation, string newLabel)
    {
        this.location = newLocation;
        this.label = newLabel;
    }

    public Point(List<double> newLocation, char newLabel)
    {
        this.location = newLocation;
        this.label = newLabel.ToString();
    }

    public Point(List<double> newLocation, int newLabel)
    {
        this.location = newLocation;
        this.label = newLabel.ToString();
    }

    public Point(List<double> newLocation, long newLabel)
    {
        this.location = newLocation;
        this.label = newLabel.ToString();
    }

    public Point(List<double> newLocation, float newLabel)
    {
        this.location = newLocation;
        this.label = newLabel.ToString();
    }
    public Point(List<double> newLocation, double newLabel)
    {
    this.location = newLocation;
        this.label = newLabel.ToString();
    }

    public Point(List<double> newLocation, uint newLabel)
    {
        this.location = newLocation;
        this.label = newLabel.ToString();
    }

    public Point(List<double> newLocation, ulong newLabel)
    {
        this.location = newLocation;
        this.label = newLabel.ToString();
    }

    public List<double> GetPoint()
    {
        return this.location;
    }

    public string GetLabel()
    {
        return this.label;
    }
    public override string ToString()
    {
        System.Text.StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.Append(this.label);
        stringBuilder.Append(" (");
        foreach (var eachNumber in this.location)
        {
            stringBuilder.Append(eachNumber.ToString());
            stringBuilder.Append(", ");
        }
        stringBuilder.Remove(stringBuilder.Length - 2, 2);
        stringBuilder.AppendLine(")");
        return stringBuilder.ToString();
    }
}

Then, the object counter which is used to store the number of existence of specific object is created as the following class ObjectCounter.

public class ObjectCounter<T>
{
    private T Object;
    private ulong count;
    public ObjectCounter(T newObject)
    {
        Object = newObject;
        count = 1;
    }
    public void IncreaseCount()
    {
        count = count + 1;
    }
    public T GetObject()
    {
        return this.Object;
    }

    public ulong GetCount()
    {
        return count;
    }
}

Next, the main structure of this Unique class is a list of ObjectCounter, and each object is unique.

public class Unique
{
    private List<ObjectCounter<string>> uniqueStrings;
    public Unique()
    {
        uniqueStrings = new List<ObjectCounter<string>>();
    }
    public void AddData(string NewString)
    {
        if (IsDataExist(NewString) ==true)
        {
        IncreaseSpecificUniqueObject(NewString);
        return;
        }
        else
        {
        uniqueStrings.Add(new ObjectCounter<string>(NewString));
        return;
        }
    }
    public ObjectCounter<string> GetMaxCountObject()
    {
        var SortedUniqueStrings = uniqueStrings.OrderByDescending(x => x.GetCount()).ToList();
        return SortedUniqueStrings[0];
    }
    public List<ObjectCounter<string>> GetUniqueStrings()
    {
        return uniqueStrings;
    }
    
    private void IncreaseSpecificUniqueObject(string InputString)
    {
        Parallel.ForEach(uniqueStrings, (Item, state) =>
        {
        if (Item.GetObject().ToString().Equals(InputString))
        {
            Item.IncreaseCount();
            state.Break();
        }
        });
        return;
    }

    private bool IsDataExist(string NewData)
    {
        bool ReturnValue = false;
        Parallel.ForEach(uniqueStrings, (Item, state) =>
        {
        if (Item.GetObject().ToString().Equals(NewData))
        {
            ReturnValue = true;
            state.Break();
        }
        });
        return ReturnValue;
    }

    public override string ToString()
    {
        System.Text.StringBuilder stringBuilder = new StringBuilder();
        foreach (var item in uniqueStrings)
        {
        stringBuilder.AppendLine(item.GetObject().ToString() + "," + item.GetCount().ToString());
        }
        return stringBuilder.ToString();
    }
}

The main KNN class is here. The distance calculation here is using Euclidean distance.

public class KNNObject
{
    private List<Point> listOfPoints;
    public KNNObject()
    {
        this.listOfPoints = new List<Point>();
    }

    public void AddData(Point newPoint)
    {
        this.listOfPoints.Add(newPoint);
    }

    public void AddData(List<Point> newListOfPoints)
    {
        this.listOfPoints.AddRange(newListOfPoints);
    }

    public string Test(List<double> testPointData, int k)
    {
        List<Point> sortedListOfPoints = this.listOfPoints.OrderBy(x => Distance(x, new Point(testPointData, ""))).ToList();

        List<Point> filtingByK = sortedListOfPoints.GetRange(0, ((sortedListOfPoints.Count > k) ? k : sortedListOfPoints.Count));

        Unique LabelAnalysis = new Unique();
        foreach (var item in filtingByK)
        {
        LabelAnalysis.AddData(item.GetLabel());
        }

        return LabelAnalysis.GetMaxCountObject().GetObject().ToString();
    }
    
    private double Distance(Point point1, Point point2)
    {
        double sum = 0.0;
        if (point1.GetPoint().Count != point2.GetPoint().Count)
        {
        return double.NaN;
        }
        for (int Loopnum = 0; Loopnum < point1.GetPoint().Count; Loopnum++)
        {
        sum = Math.Pow((point1.GetPoint()[Loopnum] - point2.GetPoint()[Loopnum]), 2.0);
        }
        return Math.Pow(sum, 0.5);
    }
}

The test of this KNNObject class.

KNNObject kNNObject = new KNNObject();
kNNObject.AddData(new Point(new List<double>() { 1.234, 1.1 }, "class1"));
kNNObject.AddData(new Point(new List<double>() { 1.23, 1.11 }, "class1"));
kNNObject.AddData(new Point(new List<double>() { 1.0, 1.011 }, "class1"));
kNNObject.AddData(new Point(new List<double>() { 2.0, 1.023 }, "class1"));
kNNObject.AddData(new Point(new List<double>() { 111, 112 }, "class2"));
kNNObject.AddData(new Point(new List<double>() { 110.2, 112.7 }, "class2"));
kNNObject.AddData(new Point(new List<double>() { 109.5, 110.5 }, "class2"));
kNNObject.AddData(new Point(new List<double>() { 111.5, 112.3 }, "class2"));
Console.WriteLine(kNNObject.Test(new List<double>() { 1.0, 1.0 }, 2));
Console.WriteLine(kNNObject.Test(new List<double>() { 116, 110 }, 2));

The output would be as following.

class1
class2

Is there any possible improvement of this code?

Answer 1

I think there is plenty of room for improvement. Whenever I write code I try to focus on 3 things in this order:

1. Does the code correctly perform its purpose?
2. If another developer reads this code in 6 months, will they understand it?
3. Does the code perform optimally?

I think you fall short of (2). The thing that slaps me in the face is why is a List used as the inner data for the Point, especially since all other coding suggests it is a 2D point? If you intend to have this be a multi-dimensional point, I would consider renaming the class to be MultiDimensionalPoint. If you intend it to only be 2D, the name Point may be sufficient but the name Point2D would be more descriptive.

For a 2D point, I would not expect to receive a List. Rather I would either be expecting to see an X and Y property, or perhaps have them named Longitude and Latitude.

And you have way to many constructors for the class. Here is my attempt at it free-hand here in the CR editor:

public struct Point2D
{
    public double X { get; }
    public double Y { get; }
    public double Label { get; }
    
    public Point2D(double x, double y, object label)
    {
        X = x;
        Y = y;
        Label = label?.ToString() ?? "";
    }

    public override string ToString() => $"{(string.IsNullOrWhitespace(label) ? label + " " : "")}({X}, {Y})";

}

I would even suggest that the Distance formula would go inside the Point2D struct or the MultiDimensionalPoint class, if that's what you need. Again, the need and intent is not immediately discernible by someone reading your code.

Let's review my version. I made it a struct instead of a class. The X, Y, and Label are read-only properties that are set in the constructor.

Elsewhere, it is also more idiomatic to use counter++ rather than counter = counter + 1.

I've seen some of your other posts here and you have an affinity for Parallel.ForEach. Have you actually tested performance with this? Parallel has the potential to boost performance. But it equally has the potential to degrade performance. If you have a small enough collection, a straight-up foreach is better than parallel. And you have a huge collection, than the way you use Parallel.ForEach can also degrade performance since each iteration must spin up a task. Now spinning up a single task is only a tiny performance hit. But spinning up 1 million adds up to a big hit. Rather its better to chop up the collection into partitions, and then each partition can be run in parallel.