Once we've identified the k nearest neighbors of a query point, a crucial question remains: How do we combine their labels into a single prediction?

This is the aggregation step of KNN—the moment when individual neighbor opinions become a collective verdict. The choice of aggregation scheme significantly impacts prediction quality, especially in challenging scenarios:

• When neighbors disagree
• When some neighbors are much closer than others
• When class frequencies are imbalanced
• When predicting continuous values (regression)

This page explores the full spectrum of voting and aggregation schemes, from the naive to the sophisticated.

The simplest aggregation scheme is majority voting: each of the k neighbors gets one vote, and the class with the most votes wins.

Formal Definition

For a query point $\mathbf{x}_q$ with k nearest neighbors having labels ${y_1, y_2, \ldots, y_k}$:

$$\hat{y}(\mathbf{x}q) = \arg\max_c \sum{i=1}^{k} \mathbf{1}[y_i = c]$$

where $\mathbf{1}[\cdot]$ is the indicator function, and $c$ ranges over all classes.

Properties:

• Each neighbor contributes equally regardless of distance
• The k-th nearest neighbor has as much influence as the 1st nearest neighbor
• Simple, fast, and often surprisingly effective
• Sensitive to the choice of k (discussed in previous page)

Distance-weighted voting addresses the equidistant illusion by giving closer neighbors more influence. The weight of each neighbor is inversely related to its distance from the query.

Formal Definition

For neighbor $i$ at distance $d_i$ from the query, assign weight:

$$w_i = \frac{1}{d_i}$$

or more generally:

$$w_i = \frac{1}{d_i^p}$$

where $p > 0$ controls how quickly influence decays with distance ($p = 1$ is most common, $p = 2$ gives quadratic decay).

The prediction becomes:

$$\hat{y}(\mathbf{x}q) = \arg\max_c \sum{i=1}^{k} w_i \cdot \mathbf{1}[y_i = c] = \arg\max_c \sum_{i: y_i = c} w_i$$

Kernel-weighted voting provides a principled framework for distance-based weighting using kernel functions from non-parametric statistics.

The Kernel Perspective

A kernel function $K: \mathbb{R}^+ \to \mathbb{R}^+$ maps distances to weights. Good kernels satisfy:

1. Non-negative: $K(d) \geq 0$
2. Monotonically decreasing: $K(d_1) \geq K(d_2)$ if $d_1 < d_2$
3. Maximum at zero: $K(0) = \max_d K(d)$
4. Often normalized: $\int K(d) dd = 1$ (for proper probability interpretation)

Bandwidth Parameter

Most kernels have a bandwidth (or scale) parameter $h$ that controls the effective range:

$$K_h(d) = \frac{1}{h} K\left(\frac{d}{h}\right)$$

Larger $h$ → smoother weighting, more neighbors contribute significantly Smaller $h$ → sharper weighting, nearest neighbors dominate

For regression tasks, we predict a continuous value by aggregating neighbor target values. The choice of aggregation function affects robustness and accuracy.

Common Aggregation Functions

Mean (Default): $$\hat{y}(\mathbf{x}q) = \frac{1}{k} \sum{i=1}^{k} y_i$$

Weighted Mean: $$\hat{y}(\mathbf{x}q) = \frac{\sum{i=1}^{k} w_i \cdot y_i}{\sum_{i=1}^{k} w_i}$$

Median (robust to outliers): $$\hat{y}(\mathbf{x}_q) = \text{median}(y_1, \ldots, y_k)$$

Weighted Median (robust + distance-aware): Find $m$ such that the sum of weights below $m$ and above $m$ are approximately equal.

Beyond point predictions (a single class or value), KNN can provide probabilistic predictions indicating confidence in the prediction.

Classification: Class Probabilities

Instead of just returning the majority class, return the distribution of neighbor labels:

$$P(y = c | \mathbf{x}q) = \frac{\sum{i=1}^{k} w_i \cdot \mathbf{1}[y_i = c]}{\sum_{i=1}^{k} w_i}$$

This gives:

• A probability for each class
• Natural confidence measure: high probability = high confidence
• Ability to set decision thresholds (e.g., "classify as positive only if P > 0.8")
• Proper inputs for metrics like log-loss, Brier score, ROC/AUC

Regression: Prediction Intervals

For regression, confidence can be expressed as prediction intervals:

$$[\hat{y} - z_{\alpha/2} \cdot s, \hat{y} + z_{\alpha/2} \cdot s]$$

where $s$ is the standard deviation of neighbor values, and $z_{\alpha/2}$ is the appropriate z-score for confidence level $1-\alpha$.

Robust KNN implementations must handle various edge cases that arise in practice.

KNN naturally extends beyond binary classification:

Multi-class Classification

KNN handles multi-class problems natively—no modification needed. The voting simply considers all classes:

$$\hat{y} = \arg\max_c \sum_{i=1}^k w_i \cdot \mathbf{1}[y_i = c]$$

where $c \in {1, 2, \ldots, C}$.

Key considerations:

• Ties are more likely with more classes
• Class imbalance affects results more strongly
• k should typically be larger than for binary classification

Multi-label Classification

When each instance can belong to multiple classes simultaneously (e.g., an image tagged as [outdoor, sunny, beach]):

ML-KNN Approach:

1. Find k nearest neighbors
2. For each possible label, compute the proportion of neighbors having that label
3. Predict label if proportion exceeds a threshold (possibly label-specific)

$$\hat{y}l = \mathbf{1}\left[\frac{\sum{i \in N_k} \mathbf{1}[l \in y_i]}{k} > \tau_l\right]$$

Multi-output Regression

When predicting multiple continuous targets simultaneously (e.g., predict both temperature and humidity):

$$\hat{\mathbf{y}} = \frac{\sum_{i=1}^k w_i \cdot \mathbf{y}i}{\sum{i=1}^k w_i}$$

where $\mathbf{y}_i$ is a vector of target values. Each output dimension is aggregated independently (or jointly if outputs are correlated).

Handling Output Correlations

If outputs are correlated, better approaches:

1. Use a joint distance metric that considers all outputs
2. Apply dimensionality reduction to outputs (PCA) before finding neighbors
3. Use multi-task learning formulations

The voting/aggregation scheme determines how neighbor information becomes a prediction. While majority voting is simple and often effective, distance-weighted and kernel-based methods usually perform better.

Coming Up Next: In Algorithm Pseudocode, we'll synthesize everything we've learned into complete, implementable KNN algorithms for both classification and regression, with all the details for a production-quality implementation.