dbsod 0.2.0

DBSOD: Density-Based Spatial Outlier Detection

DBSOD: Density-Based Spatial Outlier Detection

Official implementation of "DBSOD: Density-Based Spatial Outlier Detection". Paper preprint is coming soon.

Algorithm

While DBSCAN is a widely used clustering algorithm, it only provides a binary label for outliers and does not assign a continuous outlierness score. To address this limitation, we propose DBSOD, a density-based spatial outlier detection method inspired by DBSCAN. The algorithm estimates the consistency with which a data point is identified as an outlier across a range of neighborhood sizes:

The algorithm systematically varies the neighborhood size parameter $\epsilon$, evaluating outlierness across multiple density assumptions. By aggregating binary outlier classifications across these scales, it produces a normalized outlierness score for each point, reflecting how consistently the point is identified as an outlier.

It is also possible to estimate outlierness score for unseen data (novelty detection). Here, each new data point is treated as a non-core candidate for expansion of a cluster obtained from training data. The algorithm then estimates the consistency with which a data point does not expand the cluster.

Installation

Note: the package was developed for Linux (manylinux, x86_64) machines.

You can install package using pip:

pip install dbsod

Alternatively (for instance if you want to contribute) you may clone this repository, build dbsod and install it in .venv in editable mode:

git clone https://github.com/Kowd-PauUh/dbsod.git
cd dbsod
make install_g++
make venv

Usage

Take as an example this dataset:

import numpy as np

DATA = np.array([
    [0.35, 0.18],
    [0.60, 0.16],
    [0.40, 0.18],
    [0.40, 0.30],
    [0.30, 0.70],
])

We can use DBSOD to calculate outlierness score for each point:

from dbsod import dbsod, DBSOD

EPS_SPACE = [0.15, 0.22]  # `eps` parameters used for calculating normalized outlierness score
MIN_PTS = 2               # minimum number of neighbors for the data point to become "core" point

# Initialize model
model = DBSOD(
    eps_space=EPS_SPACE,
    min_pts=MIN_PTS,
)

# Fit model and get outlierness scores of the training data points
# This can be also achieved using:
#     `model.fit_predict(X=DATA)` or `dbsod(X=DATA, eps_space=EPS_SPACE, min_pts=MIN_PTS)`
outlierness_scores = model.fit(X=DATA).outlierness_score
print(outlierness_scores)

The output will be: array([0. , 0.5, 0. , 0. , 1. ]).

Below is the visualization of this example:

Having fitted the DBSOD, we can estimate outlierness scores for the new data points:

# prepare a 3x3 grid of points
x, y = np.meshgrid(np.linspace(0.2, 0.5, 3), np.linspace(0.2, 0.5, 3))
points = np.column_stack([x.ravel(), y.ravel()])

# estimate outlierness score for each new point
predictions = model.predict(points)
print(predictions)

The output of this is: array([0.5, 0. , 0. , 0.5, 0. , 0. , 1. , 0.5, 1. ]).

Notice how we can use DBSOD to estimate outlierness of the points in a grid with an arbitrary resolution. This effectively allows us to create outlierness heatmaps.

On the real-world data (check out this and this examples) result of applying DBSOD would look like this:

Time and space complexity

Method	Time complexity (worst case)	Space complexity (worst case)
.fit	$O(N^2 \cdot (d + logN))$	$O(N^2)$
.predict	$O(N \cdot M \cdot d)$	$O(N + M)$

Given that len(eps_space) $\ll N$, where:
  $N$ – number of points used to fit the algorithm;
  $M$ – number of points used to predict scores for;
  $d$ – point dimensionality.

Citation

@software{danylenko2025dbsod, 
  author = {Danylenko, Ivan},
  doi = {10.5281/zenodo.19557644},
  month = apr,
  title = {{DBSOD: Density-Based Spatial Outlier Detection}},
  url = {https://github.com/Kowd-PauUh/dbsod},
  version = {0.1.0},
  year = {2026}
}