TypeScript KNN

A custom implementation of the K-Nearest Neighbors (KNN) algorithm in TypeScript, built with 2D spatial grid partitioning for faster neighbor lookups.

How It Works

Standard KNN implementations compute the distance between a query point and every single point in the dataset. That brute-force approach has an $O(N)$ time complexity per prediction, which becomes slow as dataset size increases.

This implementation speeds up candidate selection by spatially indexing normalized 2D data points into a fixed $10 \times 10$ matrix of buckets.

1. Feature Normalization

Because features like Age (e.g. 18–60) and EstimatedSalary (e.g. $15,000–$150,000) have vastly different ranges, salaries would dominate Euclidean distance calculations. The normalization function applies min-max scaling to project each feature onto the $[0, 1]$ interval:

$$x_{norm} = \frac{x - x_{min}}{x_{max} - x_{min}}$$

2. Spatial Grid Binning (toNumber)

The feature space is represented as a 10x10 2D grid (temp_matrix), where each cell [x][y] holds an array of data points located within that coordinate region:

• A point's grid indices are calculated as: $$x = \min(\lfloor 10 \cdot \text{Age}{norm} \rfloor, 9)$$ $$y = \min(\lfloor 10 \cdot \text{Salary}{norm} \rfloor, 9)$$
• Each point stores its normalized coordinates along with its target label (e.g. Purchased: 0 or 1).

3. Spatial Slicing (slicer)

When querying a target point $(x, y)$, instead of searching the entire dataset, the slicer function inspects only the 9 adjacent grid cells:

$${ (a, b) \mid a \in [x - 1, x + 1], b \in [y - 1, y + 1] }$$

This drastically reduces the number of candidate points that need exact distance calculations.

4. Distance and Prediction (predict)

For the candidate points gathered from the neighboring cells:

1. Calculates the Euclidean distance: $$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$$
2. Selects the top $k$ closest neighbors (default $k = 5$).
3. Returns the nearest neighbor points with their labels and distances.

Project Structure

.
├── .github/
│   └── workflows/
│       ├── ci.yml            # CI workflow for typecheck, tests, and build
│       └── release.yml       # Release workflow triggered on version tags
├── tests/
│   ├── knn.test.ts           # Vitest tests for KNN grid, distance, and prediction
│   └── normalization.test.ts # Vitest tests for min-max scaling
├── index.ts                  # Core KNN spatial grid implementation and demo
├── normalization.ts          # Feature normalization utility functions
├── social_ads.csv            # Sample dataset for classification
├── tsconfig.json             # TypeScript configuration
└── package.json              # Dependencies, scripts, and build configuration

Getting Started

Prerequisites

• Node.js 18 or newer
• npm

Installation

git clone https://github.com/walid2004/KNN.git
cd KNN
npm install

Running the Demo

To run the algorithm against social_ads.csv:

npm start

Running Tests

# Run all unit tests
npm test

# Run tests in watch mode
npm run test:watch

Building the Project

# Type check without emitting files
npm run typecheck

# Compile TypeScript to dist/
npm run build

Continuous Integration

GitHub Actions automatically runs on pushes and pull requests to main:

• Typechecks with TypeScript tsc --noEmit
• Runs unit tests via Vitest
• Builds output files to dist/
• Executes a smoke test running the demo on social_ads.csv
• Runs across Ubuntu, macOS, and Windows on Node.js 18, 20, and 22