A nearest-neighbor measurement scores an observation by how far it is from nearby observations. The kth-nearest-neighbor (kthNN) score uses the distance to its kth closest other observation. A large score indicates that the observation lacks a sufficiently large group of close neighbors. The same idea works for a single numeric feature or for records in multiple dimensions. section 2.1.6 section 3.2.1
To calculate and interpret the score:
- Find each observation’s neighbor distances, excluding its zero distance to itself. In the single-feature example, a BallTree query requests 26 results to obtain distances to 25 other observations; the maximum returned distance is the kthNN score. section 2.1.6
- Choose k with the size of groups you want to detect in mind. With 25 other neighbors required, even a point close to 24 others scores highly if its next neighbor is far away. This can expose small isolated clusters, while larger clusters can receive low scores. section 2.1.6
- Inspect the score distribution before choosing a cutoff. Scores can rank unusual observations without supplying an obvious boundary between outliers and inliers. section 2.1.6
Single-feature outlier search
For the numeric hue-mean feature, reshape the values as one-column observations, query a scikit-learn BallTree for neighbor distances, and score each value by its farthest returned distance. Examining the high-score tail suggests a cutoff around 0.2 in this example; the cutoff is a judgment about these scores, not a universal threshold. section 2.1.6
Listing 2.5 Using k nearest neighbors to identify outliers
import pandas as pd
from sklearn.datasets import fetch_openml
from sklearn.neighbors import BallTree
data = fetch_openml('segment', version=1, parser='auto')
data = pd.DataFrame(data.data, columns=data.feature_names)
X = data['hue-mean'].values.reshape(-1, 1)
tree = BallTree(X, leaf_size=2) #1
dist, ind = tree.query(X, k=26) #2
max_dist_arr = pd.Series([max(x) for x in dist]) #3
The Python listing shows the one-feature BallTree query and maximum-distance score. section 2.1.6
For multidimensional records, kthNN remains a distance-based outlier score. Averaging distances to the nearest neighbors is an alternative that can be more robust. A single well-chosen k may produce a stronger detector, but without labeled data it is often difficult to tune; averaging results across a reasonable range of k values is another practical approach. BallTree avoids relying on an explicit distance calculation for every pair of observations. section 3.2.1
