NDLI: CID: an efficient complexity-invariant distance for time series

Content Provider	Springer Nature Link
Author	Batista, Gustavo E. A. P. A. Keogh, Eamonn J. Tataw, Oben Moses Souza, Vinícius M. A.
Copyright Year	2013
Abstract	The ubiquity of time series data across almost all human endeavors has produced a great interest in time series data mining in the last decade. While dozens of classification algorithms have been applied to time series, recent empirical evidence strongly suggests that simple nearest neighbor classification is exceptionally difficult to beat. The choice of distance measure used by the nearest neighbor algorithm is important, and depends on the invariances required by the domain. For example, motion capture data typically requires invariance to warping, and cardiology data requires invariance to the baseline (the mean value). Similarly, recent work suggests that for time series clustering, the choice of clustering algorithm is much less important than the choice of distance measure used.In this work we make a somewhat surprising claim. There is an invariance that the community seems to have missed, complexity invariance. Intuitively, the problem is that in many domains the different classes may have different complexities, and pairs of complex objects, even those which subjectively may seem very similar to the human eye, tend to be further apart under current distance measures than pairs of simple objects. This fact introduces errors in nearest neighbor classification, where some complex objects may be incorrectly assigned to a simpler class. Similarly, for clustering this effect can introduce errors by “suggesting” to the clustering algorithm that subjectively similar, but complex objects belong in a sparser and larger diameter cluster than is truly warranted.We introduce the first complexity-invariant distance measure for time series, and show that it generally produces significant improvements in classification and clustering accuracy. We further show that this improvement does not compromise efficiency, since we can lower bound the measure and use a modification of triangular inequality, thus making use of most existing indexing and data mining algorithms. We evaluate our ideas with the largest and most comprehensive set of time series mining experiments ever attempted in a single work, and show that complexity-invariant distance measures can produce improvements in classification and clustering in the vast majority of cases.
Starting Page	634
Ending Page	669
Page Count	36
File Format	PDF
ISSN	13845810
Journal	Data Mining and Knowledge Discovery
Volume Number	28
Issue Number	3
e-ISSN	1573756X
Language	English
Publisher	Springer US
Publisher Date	2013-04-12
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Time series Classification Clustering Similarity measures Complexity Data Mining and Knowledge Discovery Artificial Intelligence (incl. Robotics) Information Storage and Retrieval Statistics for Engineering, Physics, Computer Science, Chemistry and Earth Sciences
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Information Systems Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Time series classification with ensembles of elastic distance measures

The great time series classification bake off: a review and experimental evaluation of recent algorithmic advances

Invariant time-series factorization

Improving time series similarity measures by integrating preprocessing steps

A Bit Level Representation for Time Series Data Mining with Shape Based Similarity

Scalable time series classification

Efficient mining of understandable patterns from multivariate interval time series

Time series representation and similarity based on local autopatterns

Experimental comparison of representation methods and distance measures for time series data

CID: an efficient complexity-invariant distance for time series

Similar Documents

Time series classification with ensembles of elastic distance measures

The great time series classification bake off: a review and experimental evaluation of recent algorithmic advances

Invariant time-series factorization

Improving time series similarity measures by integrating preprocessing steps

A Bit Level Representation for Time Series Data Mining with Shape Based Similarity

Scalable time series classification

Efficient mining of understandable patterns from multivariate interval time series

Time series representation and similarity based on local autopatterns

Experimental comparison of representation methods and distance measures for time series data

CID: an efficient complexity-invariant distance for time series