Introduction

This document (notebook) presents a computational approach to identifying outliers in a set of multidimensional (geometric) points. The method discussed and demonstrated is based on nearest-neighbor statistics. Related workflow extensions, such as visualization and classification, are also shown.

The Python package “GeometricNearestNeighborsProcessor”, [AAp1], is used (which, as the name indicates, was specifically developed for tackling these kinds of problems.)

Purpose and theoretical background

Consider the following computational tasks for a given set of n-dimensional (nD) points P:

1. Find the points of P that are outliers or anomalies
2. Find the points of another set P1 that can be seen as anomalies wrt to P
3. For a given nD point s find its Nearest Neighbors (NNs) in
   • The points of  can have labels
   • It might be desired to get the distances and labels of the NNs of s
4. Plot the points P with minimal setup or specification writing
5. Give the (sparse) proximity matrix of  for a specified number of neighbors

Let us define an anomalous point as one that is “too far” from the other points.
Which points are “too far” from the rest can be determined by examining statistics of distances between each point and nearest neighbors of it.

More concretely, point anomalies are found in the following way:

1. Input:
   • Points P as a data frame, list, or dictionary
   • Number of nearest neighbors n
   • Distance function d
   • Aggregation function a
2. For each point of P
   • Find its n nearest neighbors
   • Aggregate with a the corresponding n distances
3. Using the statistics from the previous step — a 1D array — find outlier identification parameters
   • Like, Hampel-, SPLUS-, or Quartile parameters
4. Identify anomalies using the parameters of the previous step

Setup

Here are imported (and aliased) the packages used below:

from GeometricNearestNeighborsProcessor import *
from RandomDataGenerators import *
from OutlierIdentifiers import *
import numpy
import random
import pandas as pd
import plotly.express as px
import plotly.graph_objects as go

Usage examples

Generate random points (using the package “RandomDataGenerators”, [AAp2]):

random.seed(23)
dfPoints = random_data_frame(
    n_rows=30, 
    columns_spec = ["X", "Y"], 
    generators= {"X": numpy.random.normal, "Y": numpy.random.normal}
)
print(dfPoints.shape)
print(dfPoints[1:6])

# (30, 2)
#           X         Y
# 1  0.033569  0.564870
# 2 -2.092372 -1.821958
# 3  0.414600  0.198779
# 4  1.425464 -1.009210
# 5 -1.451830  0.529209

Here is a summary of the point coordinates:

dfPoints.describe()

Here is a plot of the points:

fig = px.scatter(dfPoints, x="X", y="Y", template="plotly_dark")
fig.show()

Here is a typical pipeline of geometric nearest neighbors processing:

1. Initiate the Geometric Nearest Neighbors (GNNs) object with a set of points
2. Create the nearest-neighbor finder (a function or a function-like object)
3. Compute the outlier detection thresholds using:
   • 10 nearest neighbors
   • The mean of the radiuses as a statistic
   • The outlier detector “Quartile”
4. Find anomalies (among the points of the GNN object)
5. Echo the found anomalies

gnnObj = (GeometricNearestNeighborsProcessor(dfPoints)
   .make_nearest_function(distance_function = "EuclideanDistance")
   .compute_thresholds(number_of_nearest_neighbors = 10, aggregation_function = "mean", outlier_identifier = "QuartileIdentifierParameters")
   .find_anomalies()
   .echo_function_value("Anomaly points:")
)

# Anomaly points:
#           X         Y    Radius
# 0 -2.092372 -1.821958  1.867283
# 1  1.031366 -2.202532  1.740659
# 2 -2.420255  0.366653  1.433153

One way to plot the anomalies together with the data points using the package “plotly” is to merge into one data frame and add an indicator column:

# Assign data
df1 = gnnObj.take_data()
df2 = gnnObj.take_value()
# Mark points that are in df2
df1['highlight'] = df1.merge(df2.assign(flag=1), on=['X', 'Y'], how='left')['flag'].fillna(0)
# Convert to category for plotting
df1['highlight'] = df1['highlight'].map({0: 'data', 1: 'anomalies'})
# Plot
fig = px.scatter(df1, 
    title="Random data", 
    x='X', y='Y', color='highlight',
    color_discrete_map={'data': 'blue', 'anomalies': 'red'},
    template="plotly_dark")
fig.show()

Alternatively, the anomaly points can be shown as smaller, in red, and on top of the data points:

fig = go.Figure()
# All points (larger)
fig.add_trace(go.Scatter(
    x=df1['X'],
    y=df1['Y'],
    mode='markers',
    marker=dict(size=12, color='blue'),
    name='data'
))
# Anomaly points (smaller, on top)
fig.add_trace(go.Scatter(
    x=df2['X'],
    y=df2['Y'],
    mode='markers',
    marker=dict(size=6, color='red', line=dict(width=1, color='black')),
    name='anomalies'
))
fig.update_layout(
    title="Random data", 
    template="plotly_dark",
    xaxis_title="X Axis",
    yaxis_title="Y Axis"
)
fig.show()

The following data can be used :

aPoints = [(r["X"], r["Y"]) for r in dfPoints.to_dict(orient="records")]
aPoints = dict(zip(random_word(len(aPoints)), aPoints))

With that the plots above have to use the columns “x1” and “x2”. Or the attribute “data” of gnnObj have to be changed to have the columns “X” and “Y”.

Nearest neighbors

Here we generate another set of random points using the same random point generators:

dfPoints2 = random_data_frame(n_rows=40, columns_spec = ["X", "Y"], generators= {"X": numpy.random.normal, "Y": numpy.random.normal})
print(dfPoints2.shape)

# (40, 2)

For each point of the second set find its top-3 nearest neighbors in the first set:

dfNNs = pd.concat(
    [
        gnnObj.find_nearest(point=[row["X"], row["Y"]], n=3)
        .take_value()
        .assign(SearchIndex=i)
        for i, row in enumerate(dfPoints2.to_dict(orient="records"))
    ],
    ignore_index=True
)
dfNNs

120 rows × 4 columns

Classification

Here the points of second set are classified into being anomalous or not:

gnnObj.classify(dfPoints2).take_value()

Plot the original data points (in gray) and the new data points by marking the anomalous ones:

df0 = gnnObj.take_data()
dfClassified = gnnObj.classify(dfPoints2).take_value()
dfCombined = dfPoints2.join(dfClassified)
df1 = dfCombined[dfCombined["Label"] == True]
df2 = dfCombined[dfCombined["Label"] == False]
fig = go.Figure()
# Original data points
fig.add_trace(go.Scatter(
    x=df0['X'],
    y=df0['Y'],
    mode='markers',
    marker=dict(size=8, color='gray'),
    name='data'
))
# Non-anomaly points
fig.add_trace(go.Scatter(
    x=df1['X'],
    y=df1['Y'],
    mode='markers',
    marker=dict(size=10, color='blue', line=dict(width=1, color='black')),
    name='non-anomalies'
))
# Anomaly points
fig.add_trace(go.Scatter(
    x=df2['X'],
    y=df2['Y'],
    mode='markers',
    marker=dict(size=10, color='red', line=dict(width=1, color='black')),
    name='anomalies'
))
fig.update_layout(
    title = "Anomaly classification results",
    template="plotly_dark",
    xaxis_title="X Axis",
    yaxis_title="Y Axis"
)
fig.show()

Proximity matrix

For some of the algorithms for recommendations systems or search engines it is helpful to have a metrics of the distances from each point to its top-K nearest neighbors. We call that matrix “proximity matrix”. Here is the proximity matrix of the GNN object created (and trained) above:

mat=gnnObj.compute_proximity_matrix().take_value()
mat

# <Compressed Sparse Row sparse matrix of dtype 'float64'
 	with 330 stored elements and shape (30, 30)>

Here is a corresponding matrix plot:

rows, cols = mat.nonzero()
fig = go.Figure(data=go.Scattergl(
    x=cols,
    y=rows,
    mode='markers',
    marker=dict(size=3)
))
fig.update_layout(
    title="Proximity matrix",
    xaxis_title="Columns",
    yaxis_title="Rows",
    yaxis_autorange='reversed',
    xaxis=dict(scaleanchor='y', scaleratio=1),
    yaxis=dict(constrain='domain'),
    width=600,
    height=600,
    template="plotly_dark"
)
fig.show()

Additional comments

• The package “GeometricNearestNeighborsProcessor” provides the class GeometricNearestNeighborsProcessor that can be used to construct chainable, monadic pipeline-like behavior.
• Plotting of the data points is done via “plotly” — just a scatter plot of 2D points for now.
• The chainable behavior of the methods of the class GeometricNearestNeighborsProcessoris implemented
  by following the principle that all methods return self, except the so-called “takers”.
  • I.e., methods with names that start with “take_”.
• The core Nearest Neighbors (NNs) finding functionality is provided by the “scikit-learn” class NearestNeighbors.
• The NNs finding algorithms used by GeometricNearestNeighborsProcessor are “scan” and “kdtree”.
  • “scan” is implemented in the class GeometricNearestNeighborsProcessor instead of delegating to scikit-learn’s NearestNeighbors “brute” algorithm.
  • “kdtree” delegates to the “kd_tree” algorithm of NearestNeighbors.

References

Python

[AAp1] Anton Antonov, GeometricNearestNeighborsProcessor, Python package, (2026), GitHub/antononcube.(PIPy.org.)

[AAp2] Anton Antonov, RandomDataGenerators, Python package, (2021-2026), GitHub/antononcube. (PIPy.org.)

[AAp3] Anton Antonov, OutlierIdentifiers, Python package, (2024), GitHub/antononcube. (PIPy.org.)

R

[AAp4] Anton Antonov, OutlierIdentifiers, R package, (2019-2024), GitHub/antononcube.

[AAp5] Anton Antonov, GNNMon-R, R package, (2019-2025), GitHub/antononcube.

[AAp6] Anton Antonov, KDTreeAlgorithm, R package, (2025), GitHub/antononcube.

Wolfram Language

[AAp7] Anton Antonov, MonadicGeometricNearestNeighbors, Wolfram Language paclet, (2023-2025), Wolfram Language Paclet Repository.

[AAp8] Anton Antonov, OutlierIdentifiers, Wolfram Language paclet, (2023), Wolfram Language Paclet Repository.