wenmin-wu/ds-skills/haversine-knn-candidate-generation

Haversine KNN Candidate Generation

Overview

Entity matching at scale requires a candidate generation step — comparing all N^2 pairs is infeasible. For location-based entities (POIs, stores, addresses), KNN with haversine distance finds the K geographically closest candidates per record. Partitioning by country/region reduces the search space further and prevents cross-continent false matches. The resulting candidate pairs are then scored by a downstream classifier.

Quick Start

import numpy as np
from sklearn.neighbors import NearestNeighbors
def generate_geo_candidates(df, n_neighbors=20, partition_col="country"):
    """Generate candidate pairs using haversine KNN per partition."""
    all_candidates = []
    for group, group_df in df.groupby(partition_col):
        group_df = group_df.reset_index(drop=True)
        coords = np.deg2rad(group_df[["latitude", "longitude"]].values)
        knn = NearestNeighbors(
            n_neighbors=min(len(group_df), n_neighbors),
            metric="haversine", n_jobs=-1
        )
        knn.fit(coords)
        dists, indices = knn.kneighbors(coords)
        for i in range(len(group_df)):
            for j in range(1, len(indices[i])):  # skip self-match
                all_candidates.append({
                    "id": group_df.iloc[i]["id"],
                    "match_id": group_df.iloc[indices[i][j]]["id"],
                    "geo_dist": dists[i][j] * 6371,  # km
                    "neighbor_rank": j,
                })
    return pd.DataFrame(all_candidates)
candidates = generate_geo_candidates(df, n_neighbors=20)

Workflow

1. Convert lat/lon to radians (required by haversine metric)
2. Partition data by country or region to reduce search space
3. Fit KNN with haversine metric per partition
4. Extract K nearest neighbors and distances for each record
5. Build candidate pair DataFrame with distance and rank features

Key Decisions

• n_neighbors: 10-50 typical; higher recall but more pairs to classify
• Partitioning: By country prevents cross-region false matches; skip for global matching
• Distance unit: Haversine returns radians; multiply by 6371 for kilometers
• Dual index: Combine geo KNN with text-based KNN for higher recall

References

• Foursquare - LightGBM Baseline
• Public: 0.861 | PyKakasi & Radian Coordinates