KNN Variants

K-Nearest Neighbors belongs to the family of instance-based learning algorithms—methods that store the entire training dataset and use it directly at prediction time. While this approach offers remarkable simplicity and the ability to model arbitrarily complex decision boundaries, it carries a fundamental computational burden: every prediction requires distance computations to all stored training instances.

Consider the implications at scale. A training set of 1 million instances with 100 features means every prediction involves 1 million distance calculations in 100-dimensional space. Even with efficient data structures like KD-trees or ball trees (which degrade to brute-force performance in high dimensions), this computational overhead becomes prohibitive for real-time applications.

But here's the critical insight: not all training instances contribute equally to the decision boundary. Points deep within the interior of a class region provide no discriminative value—removing them would leave the decision boundary unchanged. It's only the points near class boundaries that truly matter for classification.

Condensed Nearest Neighbors (CNN) exploits this observation to dramatically reduce the training set while preserving classification accuracy. It answers a deceptively simple question: What is the smallest subset of training data that correctly classifies all original training instances using 1-NN?

The mathematical foundation of CNN rests on the concept of a consistent subset. Before diving into the algorithm, we must precisely define what we're seeking.

Formal Definition of Consistency

Let $S = {(\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \ldots, (\mathbf{x}_n, y_n)}$ be our original training set, where $\mathbf{x}_i \in \mathbb{R}^d$ are feature vectors and $y_i \in {1, 2, \ldots, K}$ are class labels.

Definition (Consistent Subset): A subset $T \subseteq S$ is said to be consistent with respect to $S$ if every point in $S$ is correctly classified by the 1-nearest-neighbor rule using only the points in $T$.

Formally, $T$ is consistent if:

$$\forall (\mathbf{x}_i, y_i) \in S: \text{1-NN}(\mathbf{x}_i, T) = y_i$$

where $\text{1-NN}(\mathbf{x}, T)$ returns the label of the nearest neighbor to $\mathbf{x}$ within $T$.

The Minimum Consistent Subset Problem

The ideal goal would be to find the minimum consistent subset—the smallest $T$ that correctly classifies all of $S$. Unfortunately, this minimum consistent subset problem is NP-hard. The reduction can be shown from the minimum set cover problem, which is a well-known NP-complete problem.

Why Consistency Alone Isn't Enough

A consistent subset guarantees correct classification on the training data, but says nothing about generalization. In fact, there's a subtle but important relationship between subset size and generalization:

1. Too Large (Full Dataset): All training points retained; no storage benefit.
2. Too Small (Aggressive Reduction): May lose critical boundary information; generalization degrades.
3. Optimal: Retains boundary-defining points while removing redundant interior points.

The key insight is that points near class boundaries are geometrically necessary for maintaining the decision surface, while interior points are redundant because their contribution is dominated by closer boundary points.

Geometric Interpretation

Consider a two-class problem in 2D. The training data forms two clusters. The decision boundary of 1-NN is the Voronoi tessellation where each cell is assigned the label of its generating point.

Now observe:

• An interior point $\mathbf{x}_i$ whose Voronoi cell is entirely surrounded by cells of the same class contributes nothing to the inter-class boundary.
• Removing such interior points doesn't change where the decision boundary lies between classes.
• Only points whose Voronoi cells touch cells of a different class—the border points—define the decision boundary.

This geometric understanding motivates the CNN algorithm: iteratively identify and retain only those points that are necessary for correct classification.

The original CNN algorithm was introduced by Peter Hart in 1968. It operates through an incremental, greedy approach: start with a minimal subset and iteratively add points that are misclassified by the current subset.

Hart's Original Algorithm

The algorithm maintains two sets:

• STORE: The condensed subset we're building (initially nearly empty)
• GRABBAG: Remaining points from the original training set

Algorithm (CNN - Hart, 1968):

Step-by-Step Execution Trace

Let's trace through a simple example to build intuition. Consider 8 training points in 2D from two classes (+ and -):

Iteration 0 (Initialization):

• STORE = {A, E} (one point per class)
• GRABBAG = {B, C, D, F, G, H}

Iteration 1:

• Check B: Nearest in STORE = A (same class +). Correctly classified. Stays in GRABBAG.
• Check C: Nearest in STORE = A (same class +). Correctly classified. Stays in GRABBAG.
• Check D: Nearest in STORE = A (same class +). Correctly classified. Stays in GRABBAG.
• Check F: Nearest in STORE = E (same class -). Correctly classified. Stays in GRABBAG.
• Check G: Nearest in STORE = E (same class -). Correctly classified. Stays in GRABBAG.
• Check H: Nearest in STORE = E (same class -). Correctly classified. Stays in GRABBAG.

If all GRABBAG points are correctly classified, the algorithm terminates with STORE = {A, E}.

This example illustrates why CNN achieves dramatic reduction: two well-separated clusters need only one representative each.

Understanding CNN's computational behavior is critical for determining its applicability to large-scale problems. Let's analyze both time and space complexity rigorously.

Time Complexity

Let $n$ be the number of training instances, $d$ the dimensionality, and $k$ the number of iterations until convergence.

Per-Iteration Cost: In each iteration, we compute distances between all GRABBAG points and all STORE points. If GRABBAG has $g$ points and STORE has $s$ points:

$$\text{Distance computation: } O(g \cdot s \cdot d)$$

Number of Iterations: The algorithm terminates when no point moves from GRABBAG to STORE. In the worst case, exactly one point is added per iteration, requiring $O(n)$ iterations.

Worst-Case Total Complexity:

$$O(n^3 \cdot d)$$

This occurs when:

1. Points are added one at a time
2. STORE grows linearly while GRABBAG shrinks linearly

Average-Case Behavior: In practice, many points are often added in early iterations, and the algorithm converges much faster. Empirically, for well-separated clusters, the number of iterations is typically $O(\log n)$ to $O(\sqrt{n})$.

Space Complexity

CNN requires:

1. Input storage: $O(n \cdot d)$ for the original training set
2. Index sets: $O(n)$ for STORE and GRABBAG indices
3. Distance matrix: $O(|\text{GRABBAG}| \cdot |\text{STORE}|)$ per iteration

The distance matrix is the dominant factor. A memory-efficient implementation computes distances row-by-row rather than materializing the full matrix.

Reduction Ratio Analysis

The reduction ratio is the key practical metric:

$$\text{Reduction Ratio} = 1 - \frac{|\text{STORE}|}{n}$$

Factors Affecting Reduction:

1. Class Separation: Well-separated classes → Higher reduction (fewer border points needed)
2. Cluster Compactness: Tight clusters → Higher reduction (fewer representatives needed per cluster)
3. Label Noise: Noisy labels → Lower reduction (noise points become "necessary" borders)
4. Dimensionality: Higher dimensions → Generally lower reduction (curse of dimensionality spreads points)
5. Number of Classes: More classes → Lower reduction (more borders between class pairs)

The CNN algorithm enjoys important theoretical guarantees, though with notable limitations. Understanding these properties is essential for principled application.

Convergence Guarantee

Theorem (CNN Convergence): The CNN algorithm terminates in finite time.

Proof Sketch:

1. The STORE set is monotonically non-decreasing: once a point enters STORE, it never leaves.
2. GRABBAG is finite and monotonically non-increasing.
3. In each iteration where the algorithm doesn't terminate, at least one point moves from GRABBAG to STORE.
4. Since GRABBAG is finite and strictly decreases when non-empty after an iteration, the algorithm must terminate within $n$ iterations. ∎

Consistency Guarantee

Theorem (CNN Consistency): Upon termination, STORE is a consistent subset of the original training set.

Proof: By the termination condition, the algorithm stops only when every point in GRABBAG (and trivially, every point in STORE) is correctly classified by 1-NN using STORE.

Combined with the fact that STORE ∪ GRABBAG always equals the original training set, this means every original training point is correctly classified by the final STORE. Thus STORE is consistent. ∎

What CNN Does NOT Guarantee

Relationship to Nearest Neighbor Covering

CNN can be understood through covering theory. A covering of a set is a collection of subsets whose union contains the original set. CNN finds a covering such that each training point is "covered" by a consistent neighbor in STORE.

The fundamental combinatorial object is the consistent covering:

• Each point $\mathbf{x}_i$ with label $y_i$ must have its nearest neighbor in STORE also labeled $y_i$
• The covering must use only elements from $S$ (not arbitrary prototypes)

This perspective connects CNN to other prototype selection methods in computational geometry, particularly the minimum dominating set problem on the mutual k-nearest-neighbor graph.

Convergence Rate Characterization

While worst-case convergence is $O(n)$ iterations, the actual convergence rate depends on data geometry:

Fast Convergence (Few Iterations):

• Well-separated, compact clusters
• Low label noise
• Balanced class sizes

Slow Convergence (Many Iterations):

• Highly overlapping class distributions
• Complex, interleaved decision boundaries
• High label noise
• Severe class imbalance (rare class points each become border points)

The original CNN algorithm has inspired numerous improvements addressing its limitations. These variants offer different tradeoffs between reduction rate, accuracy, and computational cost.

Reduced Nearest Neighbors (RNN)

RNN is a post-processing step applied after CNN. It attempts to further shrink the condensed set by removing points that are no longer necessary for consistency.

RNN Algorithm:

1. Apply CNN to get initial STORE
2. For each point $\mathbf{x}$ in STORE (in some order):
   • Temporarily remove $\mathbf{x}$ from STORE
   • Check if all original training points are still correctly classified
   • If yes: permanently remove $\mathbf{x}$
   • If no: restore $\mathbf{x}$ to STORE

Generalized Condensed Nearest Neighbors (GCNN)

GCNN extends CNN to work with k-NN for k > 1 rather than just 1-NN. The consistency criterion becomes: all original points must be correctly classified by k-NN using STORE.

This is more challenging because:

• Need at least $k$ points of each class in STORE
• Consistency checking requires k-nearest-neighbor computation, not just 1-NN
• More points are typically retained to ensure k-NN consistency

Modification Condensed Nearest Neighbors (MCNN)

MCNN modifies the iteration strategy to process points in a specific order based on distance to the decision boundary:

1. Sort training points by their "boundary proximity" score
2. Process points starting from those closest to estimated decision boundary
3. This tends to find smaller consistent subsets by prioritizing true border points

Implementing CNN effectively in production systems requires attention to several practical details that aren't evident from the theoretical algorithm.

Initialization Strategy

The choice of which points to initially add to STORE significantly affects the final result. Several strategies exist:

Random per Class: Select one random point from each class. Simple but may require multiple runs.

Centroid Seeding: Select the point closest to each class centroid. Tends to start with "typical" representatives.

Boundary Seeding: Use a quick heuristic to estimate boundary points and start with those. Often produces smaller final sets.

Batch vs. Incremental Processing

The original CNN processes the entire GRABBAG in each iteration. For very large datasets, this becomes inefficient. Incremental CNN processes points one at a time:

Handling Feature Scaling

Like all distance-based methods, CNN is sensitive to feature scales. Features with larger numeric ranges dominate the distance computation.

Best Practice: Standardize or normalize features before applying CNN:

• Standardization (z-score): Centers features at 0, scales to unit variance
• Min-max normalization: Scales all features to [0, 1]

The choice should match whatever preprocessing you'll use at prediction time. The same transformation must be applied to test data.

Memory-Efficient Distance Computation

For large datasets, materializing an $n \times n$ distance matrix is impractical. Use chunked distance computation:

CNN is a powerful tool, but it's not universally applicable. Understanding its ideal use cases—and its limitations—helps you make informed decisions.

Ideal Conditions for CNN

Decision Framework

Use this framework to decide whether CNN fits your problem:

1. Estimate class separability: Plot or compute inter-class vs. intra-class distance ratios. High separation → CNN effective.

2. Assess label quality: Quantify noise rate if possible. > 5% noise → Consider Edited Nearest Neighbors first (covered in next page).

3. Measure dimensionality impact: For $d > 20$, test CNN on a sample first. If reduction < 50%, alternative methods may be better.

4. Compute ROI: Estimate $\text{(Prediction volume)} \times \text{(Speedup per prediction)} - \text{(CNN training time)}$. Positive ROI = use CNN.

5. Validate rigorously: Always evaluate CNN performance on held-out test data, not just training set consistency.

We've conducted a deep exploration of Condensed Nearest Neighbors—from its theoretical foundations to practical implementation. Let's consolidate the essential knowledge:

Connection to Next Topics

CNN focuses on retaining necessary instances—but what about removing harmful instances? Noisy labels and outliers can degrade KNN performance even after CNN condensation.

The next page explores Edited Nearest Neighbors (ENN), which takes the opposite approach: instead of selecting points to keep, it identifies points to remove based on neighborhood consistency. Together, CNN and ENN form a powerful data cleaning pipeline for instance-based learning.