Skip to main content

Tensor-based outlier detection. A general GPU-accelerated framework.

Project description

Background: Outlier detection (OD) is a key data mining task for identifying abnormal objects from general samples with numerous high-stake applications including fraud detection and intrusion detection.

To scale outlier detection (OD) to large-scale, high-dimensional datasets, we propose TOD, a novel system that abstracts OD algorithms into basic tensor operations for efficient GPU acceleration.

The corresponding paper. The code is being cleaned up and released. Please watch and star!

One Reason to Use It:

On average, TOD is 11 times faster than PyOD!

If you need another reason: it can handle much larger datasets:more than a million sample OD within an hour!

TOD is featured for:

  • Unified APIs, detailed documentation, and examples for the easy use (under construction)

  • Supports more than 10 different OD algorithms and more are being added

  • TOD supports multi-GPU acceleration

  • Advanced techniques like provable quantization

A Motivating Example PyOD vs. PyTOD!

kNN example shows that how fast and how easy PyTOD is. Take the famous kNN outlier detection as an example:

  1. Initialize a kNN detector, fit the model, and make the prediction.

    from pytod.models.knn import KNN   # kNN detector
    
    # train kNN detector
    clf_name = 'KNN'
    clf = KNN()
    clf.fit(X_train)
    # if GPU is not available, use CPU instead
    clf = KNN(device='cpu')
    clf.fit(X_train)
  2. Get the prediction results

    # get the prediction label and outlier scores of the training data
    y_train_pred = clf.labels_  # binary labels (0: inliers, 1: outliers)
    y_train_scores = clf.decision_scores_  # raw outlier scores
  3. On a simple laptop, let us see how fast it is in comparison to PyOD for 30,000 samples with 20 features

    KNN-PyOD ROC:1.0, precision @ rank n:1.0
    Execution time 11.26 seconds
    KNN-PyTOD-GPU ROC:1.0, precision @ rank n:1.0
    Execution time 2.82 seconds
    KNN-PyTOD-CPU ROC:1.0, precision @ rank n:1.0
    Execution time 3.36 seconds

It is easy to see, PyTOD shows both better efficiency than PyOD.

Programming Model Interface

Complex OD algorithms can be abstracted into common tensor operators.

https://raw.githubusercontent.com/yzhao062/pytod/master/figs/abstraction.png

For instance, ABOD and COPOD can be assembled by the basic tensor operators.

https://raw.githubusercontent.com/yzhao062/pytod/master/figs/abstraction_example.png

End-to-end Performance Comparison with PyOD

Overall, it is much (on avg. 11 times) faster than PyOD takes way less run time.

https://raw.githubusercontent.com/yzhao062/pytod/master/figs/run_time.png

Implemented Algorithms

PyTOD toolkit consists of three major functional groups (to be cleaned up):

(i) Individual Detection Algorithms :

Type

Abbr

Algorithm

Year

Ref

Linear Model

PCA

Principal Component Analysis (the sum of weighted projected distances to the eigenvector hyperplanes)

2003

[29]

Proximity-Based

LOF

Local Outlier Factor

2000

[7]

Proximity-Based

COF

Connectivity-Based Outlier Factor

2002

[30]

Proximity-Based

HBOS

Histogram-based Outlier Score

2012

[9]

Proximity-Based

kNN

k Nearest Neighbors (use the distance to the kth nearest neighbor as the outlier score)

2000

[25]

Proximity-Based

AvgKNN

Average kNN (use the average distance to k nearest neighbors as the outlier score)

2002

[5]

Proximity-Based

MedKNN

Median kNN (use the median distance to k nearest neighbors as the outlier score)

2002

[5]

Probabilistic

ABOD

Angle-Based Outlier Detection

2008

[16]

Probabilistic

COPOD

COPOD: Copula-Based Outlier Detection

2020

[20]

Probabilistic

FastABOD

Fast Angle-Based Outlier Detection using approximation

2008

[16]

Code is being released. Watch and star for the latest news!


Reference

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

pytod-0.0.0.tar.gz (27.0 kB view hashes)

Uploaded Source

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page