Signal Processing Algorithms from MongoDB
Project description
Signal Processing Algorithms
A suite of algorithms implementing EDivisive with Means and Generalized ESD Test for Outliers in python.
Getting Started  Users
pip install signalprocessingalgorithms
Getting Started  Developers
Getting the code:
$ git clone git@github.com:mongodb/signalprocessingalgorithms.git
$ cd signalprocessingalgorithms
Making a virtual environment and installing the stuff you need into it:
$ virtualenv p python3 venv
$ source venv/bin/activate
$ pip install e .
$ pip install r requirements.txt
Testing stuff:
$ pytest
Running the slow tests:
$ pytest runslow
Some of the larger tests can take a significant amount of time (more than 2 hours).
The linters:
$ pytest src flake8 black pydocstyle mypy
Intro to EDivisive
Detecting distributional changes in a series of numerical values can be surprisingly difficult. Simple systems based on thresholds or mean values can be yield false positives due to outliers in the data, and will fail to detect changes in the noise profile of the series you are analyzing.
One robust way of detecting many of the changes missed by other approaches is to use EDivisive with Means, an energy statistic based approach that compares the expected distance (Euclidean norm) between samples of two portions of the series with the expected distance between samples within those portions.
That is to say, assuming that the two portions can each be modeled as i.i.d. samples drawn from distinct random variables (X for the first portion, Y for the second portion), you would expect the following to be nonzero if there is a sdifference between the two portions:
Where alpha is some fixed constant in (0, 2). This can be calculated empirically with samples from the portions corresponding to X, Y as follows:
Thus for a series Z of length L, we find the most likely change point by solving the following for argmax(τ) (with a scaling factor of mn/(m+n) and α=1 for simplicity):
Multiple Change Points
The algorithm for finding multiple change points is also simple.
Assuming you have some k known change points:
 Partition the series into segments between/around these change points.
 Find the maximum value of our divergence metric within each partition.
 Take the maximum of the maxima we have just found > this is our k+1th change point.
 Return to step 1 and continue until reaching your stopping criterion.
Stopping Criterion
In this package we have implemented a permutation based test as a stopping criterion:
After step 3 of the multiple change point procedure above, randomly permute all of the data within each cluster, and find the most likely change point for this permuted data using the procedure laid out above.
After performing this operation z times, count the number of permuted change points z' that have higher divergence metrics than the change point you calculated with unpermuted data. The significance level of your change point is thus z'/(z+1).
We allow users to configure a permutation tester with pvalue
and permutations
representing the significance cutoff for algorithm termination and permutations to perform for each
test, respectively.
Example
from signal_processing_algorithms.e_divisive import EDivisive
from signal_processing_algorithms.e_divisive.calculators import cext_calculator
from signal_processing_algorithms.e_divisive.significance_test import QHatPermutationsSignificanceTester
from some_module import series
// Use CExtension calculator for calculating divergence metrics
calculator = cext_calculator
// Permutation tester with 1% significance threshold performing 100 permutations for each change point candidate
tester = QHatPermutationsSignificanceTester(
calculator=calculator, pvalue=0.01, permutations=100
)
algo = EDivisive(calculator=calculator, significance_tester=tester)
change_points = algo.get_change_points(series)
Project details
Release history Release notifications
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Filename, size  File type  Python version  Upload date  Hashes 

Filename, size signal_processing_algorithms1.0.4cp37cp37mmacosx_10_14_x86_64.whl (21.4 kB)  File type Wheel  Python version cp37  Upload date  Hashes View 
Filename, size signal_processing_algorithms1.0.4.tar.gz (14.7 kB)  File type Source  Python version None  Upload date  Hashes View 
Hashes for signal_processing_algorithms1.0.4cp37cp37mmacosx_10_14_x86_64.whl
Algorithm  Hash digest  

SHA256  01a3557dbdb741e73d1e903cab099d76456baed3f3db143480234154cdd0d78c 

MD5  0fd500c6469337acfa6af3e33ac33184 

BLAKE2256  9eaac096194a90d511c3d9bedfc36d3481d9f497638eb9675114b6d2bf60a979 
Hashes for signal_processing_algorithms1.0.4.tar.gz
Algorithm  Hash digest  

SHA256  30c77b508f703228648cf760759b248bd6b834fb326ccd30988a9121818dab16 

MD5  52f183ca4e2eec9b2f1483d00c9ae649 

BLAKE2256  9071068a6b72ed76dd379a768e1ff48b624bda29458c9e91da21715569248698 