gordonlesti / dynamic-time-warping Goto Github PK

Dynamic time warping for JavaScript

License: MIT License

JavaScript 94.24% HTML 5.76%

dynamic-time-warping's Introduction

dynamic-time-warping

Dynamic time warping for JavaScript. A simple usecase would be Touch signature identification with JavaScript for example.

Install

Several quick start options are available:

Download the latest release.
Clone the repo: git clone https://github.com/GordonLesti/dynamic-time-warping.git.
Install with npm: npm install dynamic-time-warping.
Install with Bower: bower install dynamic-time-warping.

Include script (unless you are packaging scripts somehow else):

<script src="/path/to/dynamic-time-warping.js"></script>

The plugin can also be loaded as AMD or Node module.

Usage

Initialization

DynamicTimeWarping needs two arrays containing objects of the the same type and function that calculates the distance between two objects and returns a float.

var ser1 = [ 9, 93, 15, 19, 24 ];
var ser2 = [ 31, 97, 81, 82, 39 ];
var distFunc = function( a, b ) {
    return Math.abs( a - b );
};

var dtw = new DynamicTimeWarping(ser1, ser2, distFunc);

getDistance

Will return the distance of the dynamic time warping as float.

// 108
var dist = dtw.getDistance();

getPath

Will return the path of the dynamic time warping as array of arrays with two integers.

// [ [ 0, 0 ], [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 2, 4 ], [ 3, 4 ], [ 4, 4 ] ]
var dist = dtw.getPath();

Change log

Please see CHANGELOG for more information what has changed recently.

Testing

$ grunt

Contributing

Please see CONTRIBUTING and CONDUCT for details.

Security

If you discover any security related issues, please email [email protected] instead of using the issue tracker.

Credits

License

The MIT License (MIT). Please see License File for more information.

dynamic-time-warping's People

Contributors

Stargazers

Watchers

Forkers

koraxos vodelerk atherfawaz sandy4321 fjteam pdkyll fheyen gsrivera mtrucc vitaly-z

dynamic-time-warping's Issues

It can't run

TypeError [Error]: DynamicTimeWarping is not a constructor

Does not work for me, rewrote it to the newer class syntax

export default class DynamicTimeWarping {
    constructor(ts1, ts2, distanceFunction) {
        this.ser1 = ts1;
        this.ser2 = ts2;
        this.distFunc = distanceFunction;
        this.distance = null;
        this.matrix = null;
        this.path = null;
    }

    getDistance() {
        if (this.distance !== null) {
            return this.distance;
        }
        this.matrix = [];
        for (var i = 0; i < this.ser1.length; i++) {
            this.matrix[i] = [];
            for (var j = 0; j < this.ser2.length; j++) {
                var cost = Infinity;
                if (i > 0) {
                    cost = Math.min(cost, this.matrix[i - 1][j]);
                    if (j > 0) {
                        cost = Math.min(cost, this.matrix[i - 1][j - 1]);
                        cost = Math.min(cost, this.matrix[i][j - 1]);
                    }
                } else {
                    if (j > 0) {
                        cost = Math.min(cost, this.matrix[i][j - 1]);
                    } else {
                        cost = 0;
                    }
                }
                this.matrix[i][j] = cost + this.distFunc(this.ser1[i], this.ser2[j]);
            }
        }
        return this.matrix[this.ser1.length - 1][this.ser2.length - 1];
    };

    getPath() {
        if (this.path !== null) {
            return this.path;
        }
        if (this.matrix === null) {
            this.getDistance();
        }
        var i = this.ser1.length - 1;
        var j = this.ser2.length - 1;
        this.path = [[i, j]];
        while (i > 0 || j > 0) {
            if (i > 0) {
                if (j > 0) {
                    if (this.matrix[i - 1][j] < this.matrix[i - 1][j - 1]) {
                        if (this.matrix[i - 1][j] < this.matrix[i][j - 1]) {
                            this.path.push([i - 1, j]);
                            i--;
                        } else {
                            this.path.push([i, j - 1]);
                            j--;
                        }
                    } else {
                        if (this.matrix[i - 1][j - 1] < this.matrix[i][j - 1]) {
                            this.path.push([i - 1, j - 1]);
                            i--;
                            j--;
                        } else {
                            this.path.push([i, j - 1]);
                            j--;
                        }
                    }
                } else {
                    this.path.push([i - 1, j]);
                    i--;
                }
            } else {
                this.path.push([i, j - 1]);
                j--;
            }
        }
        this.path = this.path.reverse();
        return this.path;
    };
}

You create it via let dtw = new DynamicTimeWarping(...).

Can you think about integrating this and running your tests on it?

Breaking out prematurely if a maximum distance is met?

Thanks for this great little library.

For my purposes I am not interested in a result if a distance is going to be greater than a certain boundary (a maxDistance). For performance reasons I would therefore like to return prematurely if we know that the distance will be greater than this boundary.

I tried to change:

          matrix[ i ][ j ] = cost + distFunc( ser1[ i ], ser2[ j ] );

to:

          matrix[ i ][ j ] = cost + distFunc( ser1[ i ], ser2[ j ] );

          if (matrix[ i ][ j ] > maxDistance) {
            return matrix[ i ][ j ];
          }

But this did not have the desired effect. I'm probably not fully understanding the algorithm. Do you have any pointers that could help?

getDistance only returns the distance of the last cell in the distance matrix?

At line https://github.com/GordonLesti/dynamic-time-warping/blob/master/src/dynamic-time-warping.js#L37 it seems as though only a subpart of the actual DTW distance is returned.

In DTW the distance is the sum of the optimal path in the distance matrix (greedy search). So, shouldn't you iterate over the distance matrix and return a sum instead? @GordonLesti

mailtivarite time series classification for example mixture of categorical and continues data

will it work for
mailtivarite time series classification for example mixture of categorical and continues data
for example at time t1 we have observation: red, 2.4 , 5, 12.456 and time t2: green, 3.5, 2, 45.78; time t3: black, 5.6, 7, 23.56; t4: red, 2.1, 5, 12.6 ?