M2-050M2: Classical Machine LearningK-Nearest Neighbors & Metric LearningMedium
⚡Flashcard Drill➔Mastery:

Detail How K-Nearest Neighbors Extends to Continuous Regression and Unsupervised Anomaly Detection

🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
Next: M2-051 →
📐 Mathematical Definition
y^=1K∑i∈kNNyi,LOF(x)=local density of neighborslocal density of x\hat y=\frac1K\sum_{i\in\mathrm{kNN}}y_i,\qquad \text{LOF}(x)=\frac{\text{local density of neighbors}}{\text{local density of }x}
⚡ One-Sentence Core Answer
In regression, KNN averages the continuous target values of the KK closest neighbors; in anomaly detection, instances with unusually large average distance to their KK nearest neighbors are flagged as outliers (Local Outlier Factor).

📌 Key Takeaways

  • •
    KNN Regression: y^(x)=∑i∈NK(x)wiyi∑i∈NK(x)wi\hat{y}(x) = \frac{\sum_{i \in \mathcal{N}_K(x)} w_i y_i}{\sum_{i \in \mathcal{N}_K(x)} w_i}; non-parametric local constant or local linear regression.
  • •
    Distance-Based Anomaly Detection: Anomaly score is the average distance to KK nearest neighbors: S(x)=1K∑i∈NK(x)d(x,xi)S(x) = \frac{1}{K}\sum_{i \in \mathcal{N}_K(x)} d(x, x_i); anomalies reside in low-density sparse regions with large S(x)S(x).
  • •
    Local Outlier Factor (LOF, Breiman et al., 2000): Compares local density of sample xx to the local densities of its neighbors, detecting anomalies across varying cluster densities.

📐 Mathematical Derivations

Local Outlier Factor (LOF) formulation: Define reachability distance of point pp from oo: reach-distk(p,o)=max⁡(k-distance(o),d(p,o))\text{reach-dist}_k(p, o) = \max(k\text{-distance}(o), d(p, o)). The local reachability density (lrd) is the inverse average reachability distance: lrdk(p)=[∑o∈Nk(p)reach-distk(p,o)∣Nk(p)∣]−1\text{lrd}_k(p) = \left[ \frac{\sum_{o \in \mathcal{N}_k(p)} \text{reach-dist}_k(p, o)}{|\mathcal{N}_k(p)|} \right]^{-1}. The LOF score is the average ratio of neighbor densities to point density: LOFk(p)=∑o∈Nk(p)lrdk(o)lrdk(p)∣Nk(p)∣\text{LOF}_k(p) = \frac{\sum_{o \in \mathcal{N}_k(p)} \frac{\text{lrd}_k(o)}{\text{lrd}_k(p)}}{|\mathcal{N}_k(p)|}. If LOF≈1\text{LOF} \approx 1, density matches neighbors (normal cluster). If LOF≫1\text{LOF} \gg 1, the point's density is substantially lower than its neighbors, identifying it as an anomaly.

🏭 Production Trade-offs

Strengths and weaknesses in anomaly detection: (1) Strengths: Completely unsupervised, requires zero label data, makes no parametric distribution assumptions (unlike Gaussian mixture anomaly detection). (2) Weaknesses: O(N2)O(N^2) distance computation makes inference slow for high-throughput streaming fraud detection; often replaced in production by Isolation Forest (O(Nlog⁡N)O(N \log N)).
⚠️ Common Interview Pitfalls
  • ✕
    Using global distance thresholds for anomaly detection in datasets with clusters of varying densities (LOF is strictly required).
  • ✕
    Using KNN regression for extrapolation (KNN can NEVER predict values outside the range [min⁡(y),max⁡(y)][\min(y), \max(y)] of historical training labels).
🎯 Interviewer Follow-up Inquiries
  • ?
    Why is KNN regression fundamentally incapable of extrapolating beyond training target boundaries?
  • ?
    How does Isolation Forest achieve O(Nlog⁡N)O(N \log N) anomaly detection compared to O(N2)O(N^2) KNN LOF?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM2-049: Explain Why KNN Strictly Requires Feature Scaling and Contrast Common Distance Metrics📋 Back to BankNext →M2-051: Explain the Curse of Dimensionality and Its Pathological Consequences on Distance-Based Models