KNN Classifier

A K-Nearest Neighbors (KNN) classifier implemented from scratch in Java, featuring an interactive command-line interface.

Overview

KNN is a simple, non-parametric classification algorithm. To classify a new data point:

1. Compute the Euclidean distance from that point to every point in the training set.
2. Select the k nearest neighbors.
3. Assign the class that appears most frequently among those neighbors (majority vote).

This implementation includes:

• Custom QuickSort for sorting distances
• Stratified 66/34 train/test split
• k-value benchmarking across the entire valid range
• Interactive classification of new vectors at runtime

Project Structure

.
├── pom.xml
├── iris.csv
└── src/
    ├── main/java/
    │   ├── Main.java                   # Entry point — interactive CLI menu
    │   └── knn/
    │       ├── KNearestNeighbours.java # KNN algorithm (distance, voting)
    │       ├── PrepareDataset.java     # Dataset loading, splitting, evaluation
    │       ├── LabeledVector.java      # Data structure for feature vectors with labels
    │       ├── EvaluationMetrics.java  # Accuracy metric
    │       └── CustomQuickSort.java    # QuickSort for LabeledVector by distance
    └── test/java/knn/
        ├── KNearestNeighboursTest.java
        ├── LabeledVectorTest.java
        ├── EvaluationMetricsTest.java
        └── PrepareDatasetTest.java

Requirements

• Java 8 or higher
• Maven 3.6+

Compilation & Running

# Run (compiles automatically)
mvn exec:java

# Run tests
mvn test

# Build executable jar
mvn package
java -jar target/knn-classifier-1.0.0.jar

Make sure iris.csv is in the project root when running.

Usage

On startup the menu is displayed:

========== KNN Classifier ==========
  Dataset : ./iris.csv
  k       : 3
-------------------------------------
  [1] Run classifier
  [2] Run k benchmark
  [3] Set dataset path
  [4] Add vector
  [5] Info
  [exit] Quit
=====================================

Option	Description
1	Perform a 66/34 stratified train/test split and print accuracy
2	Benchmark all valid k values (1 … n-1) on the current dataset
3	Load a different CSV dataset for testing against the trained model
4	Classify a single new vector (requires training first)
5	Display current model info (dataset, k, trained status)
exit	Quit the program

Classifying a new vector (option 4)

After training (option 1), select option 4 and enter comma-separated feature values matching the dataset dimensionality:

Please provide 4 values separated by commas
5.1, 3.5, 1.4, 0.2
class-a

Using a different dataset (option 3)

The classifier supports any CSV file where:

• The first row is a header (skipped automatically)
• Each subsequent row contains numeric feature values followed by a class label in the last column
• All rows have the same number of features as the training dataset

Example row: 5.1,3.5,1.4,0.2,class-a

Dataset

iris.csv — 150 samples, 4 numeric features, 3 balanced classes (50 samples each).

Typical accuracy with k=3 is ~97%.

Algorithm Details

Distance metric

Euclidean (L2) distance between two n-dimensional vectors:

d(a, b) = sqrt( sum_i (a_i - b_i)^2 )

Majority voting

Among the k nearest neighbors, the class with the highest frequency is returned. Ties are broken by random selection.

Train/test split

Stratified split: indices within each class are divided 66% train / 34% test, preserving class proportions in both sets.

k benchmark

Runs classification for every k from 1 to (dataset size − 1) on the same train/test split and prints accuracy for each value. Useful for finding the optimal k.

Implementation Notes

• CustomQuickSort — in-place quicksort on ArrayList<LabeledVector> ordered by computed distance; avoids dependency on Collections.sort.
• LinkedHashMap — used for both the full dataset and train/test subsets to preserve insertion order, which ensures deterministic stratified splits.
• Optional<Double> on LabeledVector.distance — distance is only meaningful after a nearest-neighbor search; using Optional makes the unset state explicit rather than relying on a sentinel value like 0.0 or -1.0.