Burst Similarity Measures

The burst similarity measure is the way of comparing two synchronous time sequences. This algorithm is described in paper [Michail Vlachos, Chris Meek and Zografoula Vagena Identifying Similarities, Periodicities and Bursts for Online Search Queries / In Proceedings of the ACM SIGMOD International Conference on Management of Data, – Paris, France, June 13-18, 2004. ACM 2004, – pp. 131-142].

The class BurstSimilarityMeasures implements the 6th part of this paper. As described in the paper, the burst similarity measure deals with preliminarily detected data. So, the preliminary data normalization and detection is required.

For the purpose of data normalization the standard score (Z-Score) algorithms implementation was added in library. The Z-Score algorithm (and corresponding class ZScore) performs data standardization, according with estimated sample mean and standard deviation values.

For the purpose of data detection the simple two state machine was added in library. This algorithm releases widely used approach of turn on machine if the incoming value becomes greater or equal to turn on threshold and machine turn off if the incoming value becomes less than turn off threshold. Obviously, the turn on threshold should be greater or equal to turn off threshold.

These auxiliary classes can be replaced with more appropriate ones for specified case.

The burst similarity computes as:

where BDSim 2

BDIntersect

and BDAbsB represents burst length in seconds and

BDAvg Value is the mean value of X in i-th burst.

Next figure shows the example.

As you can see, two observed variables (blue sine line and green sine line) convert to states (red line and magenta line) according their thresholds. The intersection regions are selected by grey rectangles.

Implementation

Thresholder class allows to create the state machine instances, which are passed for the burst similarity detection.

BurstSimilarityMeasures class implements the described functionality. It contains the following constructor:

Method	Description	Performance
constructor	The BurstSimilarityMeasures class constructor. BurstSimilarityMeasures(Int32)

Method

Description

Performance

constructor

The BurstSimilarityMeasures class constructor.

Static BurstSimilarityMeasures(Int32)

Use method Add to update the indicator value. Use property Value to get the current value.

Code Sample

Copy

  1using System;
  2using System.Collections.Generic;
  3using System.IO;
  4using System.Linq;
  5using System.Reflection;
  6using System.Text;
  7using FinAnalysis.BurstDetection;
  8using FinAnalysis.Base;
  9using FinAnalysis.Comparators;
 10using FinAnalysis.TA;
 11
 12namespace BurstSimilarityMeasuresSample
 13{
 14    class BurstSimilarityMeasuresSample
 15    {
 16        public interface IDataGenerator
 17        {
 18            void Generate(int i, out double x, out double y);
 19        }
 20
 21        public class SineGenerator : IDataGenerator
 22        {
 23            public void Generate(int i, out double x, out double y)
 24            {
 25                x = Math.Sin(i / 5.0) * Math.Sin(i / 20.0);
 26                y = Math.Sin(i / 6.0) * Math.Sin(i / 17.0);
 27            }
 28        }
 29
 30        public class RandomGenerator : IDataGenerator
 31        {
 32            private Random random = new Random(12345);
 33
 34            public void Generate(int i, out double x, out double y)
 35            {
 36                x = random.NextDouble();
 37                y = random.NextDouble();
 38            }
 39        }
 40
 41        public class FrequencyGenerator : IDataGenerator
 42        {
 43            private double frequency;
 44
 45            public FrequencyGenerator(double frequency)
 46            {
 47                this.frequency = frequency;
 48            }
 49
 50            public void Generate(int i, out double x, out double y)
 51            {
 52                x = Math.Cos(frequency*i);
 53                y = x;
 54            }
 55        }
 56
 57        public static void Main(string[] args)
 58        {
 59            SequenciesTest(new SineGenerator(), "Frequency modulation test");
 60
 61            SequenciesTest(new RandomGenerator(), "Random test");
 62
 63            SequenciesTest(new FrequencyGenerator(0.1), "Frequency 0.1 test");
 64            SequenciesTest(new FrequencyGenerator(2.0), "Frequency 2.0 test");
 65        }
 66
 67        public static void SequenciesTest(IDataGenerator generator, string testName)
 68        {
 69            int period = 200;
 70
 71            var z1 = new ZScore(40);
 72            var z2 = new ZScore(50);
 73
 74            BurstSimilarityMeasures bsm = new BurstSimilarityMeasures(period);
 75
 76            double x, y;
 77            for (int i = 0; i <= period; ++i)
 78            {
 79                // Generates two sine signals with little different frequencies and different scaling parameters.
 80                generator.Generate(i, out x, out y);
 81
 82                z1.Add(x);
 83                z2.Add(y);
 84
 85                // Calculates the similarity
 86                bsm.Add(z1.Value, z2.Value, new DateTime(i*10000000 + (long) 600000000000000000));
 87
 88                if (i < period && !Double.IsNaN(bsm.Value))
 89                    throw new Exception("Result[" + i + "] != NaN");
 90            }
 91
 92            if (Double.IsNaN(bsm.Value))
 93                throw new Exception("Result is NaN");
 94            else if (Double.IsInfinity(bsm.Value))
 95                throw new Exception("Result is Infinity");
 96
 97            Console.WriteLine($"{testName} similarity measure: {bsm.Value}");
 98        }
 99    }
100}

Other Resources

ShiftedWaveletTree