2
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Tip: As for me the last AppendLine in ToString should be Append as line shouldnt contain CRLF at the end, otherwise you'll get double CRLF output while using something like WriteLine. Unexpected behavior. \$\endgroup\$ – aepot Oct 12 at 21:31
  • \$\begingroup\$ You can skip Math.Pow if you need distances for sorting only – it performs calculation which does not affect the result. You can sort by a distance squared as well. \$\endgroup\$ – CiaPan Nov 10 at 16:06
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you for the comments. About the naming to the class Point, I want to keep the scalability on the dimension property but also simplify the name. If the point class is designed for 2D case, the definition you mentioned is a good idea. As your suggestion, using the name MultiDimensionalPoint is more clear for this case. Otherwise, the performance impact of using Parallel.ForEach syntax is seems a good issue to discuss. I wondering that how to determine using parallel or not in order to reach the optimal performance. \$\endgroup\$ – JimmyHu Oct 11 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.