<commit_before># Introduction

This python class ([strangenss.py](./strangeness.py)) is an anomaly/change detector based on the concept of martingales. It is designed to work on unlabelled data (unsupervised anomaly detection). An example of unlabelled data set can be the dataset of number of steps taken by a user everyday. This anomaly detector can point out if the number of steps taken on a particular day are out of the ordinary.

I implemented one of the many possible implementation of the concept explained in this paper  [Detecting Changes in Unlabeled Data Streams using Martingale](http://ijcai.org/Proceedings/07/Papers/308.pdf) by <NAME> and <NAME>. The basic pretext is that given a list of values, the properties (joint probability) of set should not change if the elements in the list are permutated. I use cluster mean for cluster representation.



# Usage

The input to the code is a file with a header row and data in the following format

`<row Label/ID>,<value1>,<value2>,<value3>...,<valueN>`

The `row label` can be anything that represents the set of values. A timestamp can be a label. The 'value' fields represent the state at that particular label. For a heat rate monitor, the label represents the time of measurement and the values are the light intensity detected by the heart rate sensor. Check the sample data file in 'test-data' folder. I combined data from 4 different normal distributions to generate this dataset.

Also, order of the rows is important, please maintain the original order of records when generating an input dataset. 


## Concrete usage example

Once the data file is ready, the code can be run as follows:
```python usageExample.py <dataset> <threshold> <minQueueLen> <epsilon>```
 
With sample parameters:

```python usageExamples.py ./test-data/martingalesDataWithLabels.csv 10 50 0.92```
 
The 3 values after the input dataset are as follows:

* `threshold` -  This value decides the sensitivity of the algorithm. Lesser value causes more detections

* `minQueueLen` -  This value decides the minimum number of input values before starting the change detection. Lesser value causes more detections

* `epsilon` -  This value decides the sensitivity of the algorithm - randomised power martingales


The output consists of  ```<row Label/ID> <M Value>```. If this value is greater than `threshold`, the algorithm has detected an anomaly. 



## Adding in your python code 

1. Download the class file `strangeness.py` in your code folder  
2. Add the import statement `from strangeness import Strangness`
3. Create the class object - `strangeness = Strangeness(threshold, minQueueLen, epsilon)`
4. Next pass the tuple of values (no label) to get the M value - `strangeness.getMValue(valuesTuple)` 

5. Step 4 is to be repeated for each data point.
6. If the value returned by `getMValue()` is greater than the threshold then the algorithm has detected an anomaly.

# Performance

For the above parameters, the code takes around 6 secs to process 4000 points.
For each new point, the center mean and distance are recalculated for `minQueueLen` points, therefore keeping the queue length short will reduce runtime.

# Parameter Tuning

For each new problem we need to find optimum paramters(`threshold`, `minQueueLen`, and `epsilon`) that results in the lower number of false positive (false detection)  and false negatives (missed detection). I have put up an example of how parameter tuning (finding optimum values for `threshold`, `minQueueLen`, and `epsilon`) can be perfomed using an example dataset comprising of S&P500 opening day values for each day. The date serves as the `label` for this dataset. More details are here 

### Disclaimer

The code is my personal work and does not in any way represent my employer

<commit_msg>adding link to paramter tuning to the main readme<commit_after># Introduction

This python class ([strangenss.py](./strangeness.py)) is an anomaly/change detector based on the concept of martingales. It is designed to work on unlabelled data (unsupervised anomaly detection). An example of unlabelled data set can be the dataset of number of steps taken by a user everyday. This anomaly detector can point out if the number of steps taken on a particular day are out of the ordinary.

I implemented one of the many possible implementation of the concept explained in this paper  [Detecting Changes in Unlabeled Data Streams using Martingale](http://ijcai.org/Proceedings/07/Papers/308.pdf) by <NAME> and <NAME>. The basic pretext is that given a list of values, the properties (joint probability) of set should not change if the elements in the list are permutated. I use cluster mean for cluster representation.



# Usage

The input to the code is a file with a header row and data in the following format

`<row Label/ID>,<value1>,<value2>,<value3>...,<valueN>`

The `row label` can be anything that represents the set of values. A timestamp can be a label. The 'value' fields represent the state at that particular label. For a heat rate monitor, the label represents the time of measurement and the values are the light intensity detected by the heart rate sensor. Check the sample data file in 'test-data' folder. I combined data from 4 different normal distributions to generate this dataset.

Also, order of the rows is important, please maintain the original order of records when generating an input dataset. 


## Concrete usage example

Once the data file is ready, the code can be run as follows:
```python usageExample.py <dataset> <threshold> <minQueueLen> <epsilon>```
 
With sample parameters:

```python usageExamples.py ./test-data/martingalesDataWithLabels.csv 10 50 0.92```
 
The 3 values after the input dataset are as follows:

* `threshold` -  This value decides the sensitivity of the algorithm. Lesser value causes more detections

* `minQueueLen` -  This value decides the minimum number of input values before starting the change detection. Lesser value causes more detections

* `epsilon` -  This value decides the sensitivity of the algorithm - randomised power martingales


The output consists of  ```<row Label/ID> <M Value>```. If this value is greater than `threshold`, the algorithm has detected an anomaly. 



## Adding in your python code 

1. Download the class file `strangeness.py` in your code folder  
2. Add the import statement `from strangeness import Strangness`
3. Create the class object - `strangeness = Strangeness(threshold, minQueueLen, epsilon)`
4. Next pass the tuple of values (no label) to get the M value - `strangeness.getMValue(valuesTuple)` 

5. Step 4 is to be repeated for each data point.
6. If the value returned by `getMValue()` is greater than the threshold then the algorithm has detected an anomaly.

# Performance

For the above parameters, the code takes around 6 secs to process 4000 points.
For each new point, the center mean and distance are recalculated for `minQueueLen` points, therefore keeping the queue length short will reduce runtime.

# Parameter Tuning

For each new problem we need to find optimum paramters(`threshold`, `minQueueLen`, and `epsilon`) that results in the lower number of false positive (false detection)  and false negatives (missed detection). I have put up an example of how parameter tuning (finding optimum values for `threshold`, `minQueueLen`, and `epsilon`) can be perfomed using an example dataset comprising of S&P500 opening day values for each day. The date serves as the `label` for this dataset. More details are [here](https://github.com/udayankumar/anomaly-detection/tree/master/test-data/SP500) 

### Disclaimer

The code is my personal work and does not in any way represent my employer


{'fraction_non_alphanumeric': 0.06025974025974026, 'fraction_numerical': 0.008701298701298701, 'mean_word_length': 4.51647564469914, 'pattern_counts': {'":': 0, '<': 29, '<?xml version=': 0, '>': 29, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1388213', 'n_tokens_mistral': 2004, 'n_tokens_neox': 1866, 'n_words': 1126}