ODIN (outlier detection using in-degree number) detects unusual observations through reverse nearest-neighbor relationships. Instead of asking how far a record is from its nearest neighbors, it counts how many other records select it as a nearest neighbor. Records selected by few others receive higher outlier scores. section 7.7
A practical ODIN procedure follows these steps:
- Find each record’s k nearest neighbors. section 7.7
- Count how often each record appears in other records’ neighbor lists. section 7.7
- Weight incoming matches by rank, giving greater weight to closer-neighbor positions when calculating the ODIN score. section 7.7
- Treat records with few incoming selections as more suspicious, while interpreting scores alongside the chosen k and the data’s structure. section 7.7 section 8.1.1
Choosing k and reading the result
With k = 5, ODIN can flag dense-cluster records that are near other points but do not fall among the closest five neighbors of many records. A value near the smallest cluster size regarded as an inlier may provide more useful guidance, although the effect of k can be unintuitive, especially in high dimensions. On the test sets, ODIN produced results different from other detectors, scoring small-cluster points, global outliers, and some cluster-margin points. section 8.1.1 section 7.7
Listing 7.7 ODIN outlier detection
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
from sklearn.neighbors import BallTree
from collections import Counter
class ODINOutlierDetector:
def __init__(self):
pass
def fit_predict(self, df_in, k):
df = df_in.copy()
num_rows = len(df)
b = BallTree(df)
dist, ind = b.query(df, k=k) #1
df['ODIN Score'] = [0] * num_rows #2
for current_k in range(1, k): #3
current_ind = ind[:, current_k] #4
c = Counter(current_ind) #5
g = [(x, c[x]) if x in c else (x, 0) for x in range(num_rows)]
df['ODIN Score'] += \
(k - current_k) * np.array([x[1] for x in g]) #6
min_score = df['ODIN Score'].min()
max_score = df['ODIN Score'].max()
return (max_score - df['ODIN Score']) / (max_score - min_score)
np.random.seed(0)
df = create_four_clusters_test_data()
clf = ODINOutlierDetector()
df['ODIN Score'] = clf.fit_predict(df, k=20)
The listing provides a concise Python implementation using BallTree, neighbor indices, rank-weighted incoming counts, and an ODIN score column. section 7.7
