Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Knowledge and Information Systems
Published in: Knowledge and Information Systems 2/2016

01-08-2016 | Regular Paper

Comparison of different weighting schemes for the kNN classifier on time-series data

Authors: Zoltan Geler, Vladimir Kurbalija, Miloš Radovanović, Mirjana Ivanović

Published in: Knowledge and Information Systems | Issue 2/2016

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Many well-known machine learning algorithms have been applied to the task of time-series classification, including decision trees, neural networks, support vector machines and others. However, it was shown that the simple 1-nearest neighbor (1NN) classifier, coupled with an elastic distance measure like Dynamic Time Warping (DTW), often produces better results than more complex classifiers on time-series data, including k-nearest neighbor (kNN) for values of \(k>1\). In this article, we revisit the kNN classifier on time-series data by considering ten classic distance-based vote weighting schemes in the context of Euclidean distance, as well as four commonly used elastic distance measures: DTW, Longest Common Subsequence, Edit Distance with Real Penalty and Edit Distance on Real sequence. Through experiments on the complete collection of UCR time-series datasets, we confirm the view that the 1NN classifier is very hard to beat. Overall, for all considered distance measures, we found that variants of the Dudani weighting scheme produced the best results.
previous article An entropy-based clustering ensemble method to support resource allocation in business process management
next article Word network topic model: a simple but general solution for short and imbalanced texts

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Literature
1.
Agrawal R, Faloutsos C, Swami A (1993) Efficient similarity search in sequence databases. In: Lomet David B (ed) Proceedings of the 4th international conference on foundations of data organization and algorithms (FODO’93). Springer, Berlin Heidelberg, pp 69–84
2.
Bache K, Lichman M (2013) UCI machine learning repository. University of California, School of Information and Computer Science, Irvine, CA
3.
Berndt D, Clifford J (1994) Using dynamic time warping to find patterns in time series. In: Usama M, Fayyad RU (ed) Knowledge discovery in databases: papers from the 1994 AAAI workshop. AAAI Press, Seattle, Washington, pp 359–370
4.
Bouckaert RR, Frank E (2004) Evaluating the replicability of significance tests for comparing learning algorithms. In: Dai H, Srikant R, Zhang C (eds) Advances in knowledge discovery and data mining. Springer, Berlin, Heidelberg, pp 3–12CrossRef
5.
Brockwell PJ, Davis RA (2002) Introduction to time series and forecasting. Springer, New YorkCrossRefMATH
6.
Chen L, Ng R (2004) On the marriage of lp-norms and edit distance. In: Nascimento MA, Özsu MT, Kossmann D, et al. (eds) Proceedings of the thirtieth international conference on very large data bases, Toronto, Canada, August 31–September 3, 2004. Morgan Kaufmann, pp 792–803
7.
Chen L, Özsu MT, Oria V (2005) Robust and fast similarity search for moving object trajectories. In: Proceedings of the 2005 ACM SIGMOD international conference on management of data—SIGMOD’05. ACM Press, New York, New York, USA, pp 491–502
8.
Cover T, Hart P (1967) Nearest neighbor pattern classification. IEEE Trans Inf Theory 13:21–27CrossRefMATH
9.
Das G, Gunopulos D (2003) Time series similarity and indexing. In: Ye N (ed) The handbook of data mining. Lawrence Erlbaum Associates, Mahwah, pp 279–304
10.
Ding H, Trajcevski G, Scheuermann P et al (2008) Querying and mining of time series data: experimental comparison of representations and distance measures. In: Proceedings of the VLDB endowment, vol 1. pp 1542–1552
11.
Dudani SA (1976) The distance-weighted k-nearest-neighbor rule. IEEE Trans Syst Man Cybern SMC 6:325–327CrossRef
12.
13.
Faloutsos C, Ranganathan M, Manolopoulos Y (1994) Fast subsequence matching in time-series databases. In: Proceedings of ACM SIGMOD record, vol 23. pp 419–429
14.
Fix E, Hodges JL (1989) Discriminatory analysis. Nonparametric discrimination: consistency properties. Int Stat Rev 57:238–247CrossRefMATH
15.
García S, Fernández A, Luengo J, Herrera F (2009) A study of statistical techniques and performance measures for genetics-based machine learning: accuracy and interpretability. Soft Comput 13:959–977CrossRef
16.
García S, Herrera F (2008) An extension on “statistical comparisons of classifiers over multiple data sets” for all pairwise comparisons. J Mach Learn Res 9:2677–2694MATH
17.
Goldin DQ, Kanellakis PC (1995) On similarity queries for time-series data: Constraint specification and implementation. In: Montanari U, Rossi F (eds) Proceedings of principles and practice of constraint programming—CP’95. Springer, Berlin Heidelberg, pp 137–153
18.
19.
Gou J, Du L, Zhang Y, Xiong T (2012) A new distance-weighted k-nearest neighbor classifier. J Inf Comput Sci 9:1429–1436
20.
Gou J, Xiong T, Kuang Y (2011) A novel weighted voting for k-nearest neighbor rule. J Comput 6:833–840CrossRef
21.
Han J, Kamber M (2006) Data mining: concepts and techniques, 2nd edn. Morgan Kaufmann Publishers Inc., San FranciscoMATH
22.
Hand DJ, Mannila H, Smyth P (2001) Principles of data mining. MIT Press, Cambridge
23.
Itakura F (1975) Minimum prediction residual principle applied to speech recognition. IEEE Trans Acoust Speech Signal Process 23:67–72CrossRef
24.
Jeong Y-S, Jeong MK, Omitaomu OA (2011) Weighted dynamic time warping for time series classification. Pattern Recogn 44:2231–2240CrossRef
25.
Keogh E, Ratanamahatana CA (2005) Exact indexing of dynamic time warping. Knowl Inf Syst 7:358–386CrossRef
26.
27.
Kotsiantis SB (2007) Supervised machine learning: a review of classification techniques. In: Proceedings of the 2007 conference on emerging artificial intelligence applications in computer engineering: real word AI systems with applications in eHealth, HCI. Information retrieval and pervasive technologies. IOS Press, Amsterdam, pp 3–24
28.
Kurbalija V, Ivanović M, Budimac Z (2009) Case-based curve behaviour prediction. Softw Pract Exp 39:81–103CrossRef
29.
Kurbalija V, Ivanović M, von Bernstorff C et al (2014a) Matching observed with empirical reality—what you see is what you get? Fundam Inform 129:133–147MathSciNet
30.
Kurbalija V, Radovanović M, Geler Z, Ivanović M (2010) A framework for time-series analysis. In: Dicheva D, Dochev D (eds) Artificial intelligence: methodology, systems, and applications SE-5. Springer, Berlin, Heidelberg, pp 42–51CrossRef
31.
Kurbalija V, Radovanović M, Geler Z, Ivanović M (2011) The Influence of Global Constraints on DTW and LCS Similarity Measures for Time-Series Databases. In: Dicheva D, Markov Z, Stefanova E (eds) Third international conference on software, services and semantic technologies S3T 2011 SE-10. Springer, Berlin, Heidelberg, pp 67–74
32.
Kurbalija V, Radovanović M, Geler Z, Ivanović M (2014b) The influence of global constraints on similarity measures for time-series databases. Knowl Based Syst 56:49–67CrossRef
33.
Kurbalija V, Radovanović M, Ivanović M et al (2014c) Time-series analysis in the medical domain: a study of Tacrolimus administration and influence on kidney graft function. Comput Biol Med 50:19–31CrossRef
34.
Kurbalija V, von Bernstorff C, Burkhard H-D et al (2012) Time-series mining in a psychological domain. In: Proceedings of the fifth Balkan conference in informatics on—BCI ’12. ACM Press, New York, New York, USA, pp 58–63
35.
Larose DT (2005) Discovering knowledge in data. Wiley, HobokenMATH
36.
37.
Macleod J, Luk A, Titterington D (1987) A re-examination of the distance-weighted k-nearest neighbor classification rule. IEEE Trans Syst Man Cybern 17:689–696CrossRef
38.
Marteau P-F (2009) Time warp edit distance with stiffness adjustment for time series matching. IEEE Trans Pattern Anal Mach Intell 31:306–318CrossRef
39.
Mitchell TM (1997) Mach Learn. McGraw-Hill Inc, New York
40.
Mitrović D, Geler Z, Ivanović M (2012) Distributed distance matrix generator based on agents. In: Proceedings of the 2nd international conference on web intelligence, mining and semantics—WIMS’12. ACM Press, New York, New York, USA, pp 40:1–40:6
41.
Mitrovic D, Ivanović M, Geler Z (2014) Agent-based distributed computing for dynamic networks. Inf Technol Control 43:88–97
42.
Morse MD, Patel JM (2007) An efficient and accurate method for evaluating time series similarity. In: Proceedings of the 2007 ACM SIGMOD international conference on management of data—SIGMOD’07. ACM Press, New York, New York, USA, pp 569–580
43.
Nanopoulos A, Alcock R, Manolopoulos Y (2001) Feature-based classification of time-series data. Int J Comput Res 10:49–61
44.
Pao T-L, Chen Y-T, Yeh J-H et al (2007) A comparative study of different weighting schemes on KNN-based emotion recognition in Mandarin speech. In: Huang D-S, Heutte L, Loog M (eds) Advanced intelligent computing theories and applications. With aspects of theoretical and methodological issues. Springer, Berlin, Heidelberg, pp 997–1005CrossRef
45.
Pao T-L, Chen Y-T, Yeh J-H, Chang Y-H (2005) Emotion recognition and evaluation of Mandarin speech using weighted D-KNN classification. In: Proceedings of the 17th conference on computational linguistics and speech processing, ROCLING 2005, Taiwan, ROC, 2005. Association for Computational Linguistics and Chinese Language Processing (ACLCLP), Taiwan, pp 203–212
46.
Pavlovic V, Frey BJ, Huang TS (1999) Time-series classification using mixed-state dynamic Bayesian networks. In: Proceedings of 1999 IEEE computer society conference on computer vision and pattern recognition (Cat. No PR00149). IEEE Computer Society, pp 609–615
47.
Radovanović M, Nanopoulos A, Ivanović M (2010) Time-series classification in many intrinsic dimensions. In: Proceedings of the 2010 SIAM international conference on data mining. Society for Industrial and Applied Mathematics, Philadelphia, PA, pp 677–688
48.
Radovanović M, Nanopoulos A, Ivanović M (2010b) Hubs in space: popular nearest neighbors in high-dimensional data. J Mach Learn Res 11:2487–2531MathSciNetMATH
49.
Ralanamahatana CA, Lin J, Gunopulos D et al (2005) Mining time series data. In: Maimon O, Rokach L (eds) Data mining and knowledge discovery handbook. Springer, New York, pp 1069–1103CrossRef
50.
Ratanamahatana CA, Keogh E (2005) Three myths about dynamic time warping data mining. In: Proceedings of the 2005 SIAM international conference on data mining. Society for Industrial and Applied Mathematics, Philadelphia, PA, pp 506–510
51.
Rodríguez JJ, Alonso CJ (2004) Interval and dynamic time warping-based decision trees. In: Proceedings of the 2004 ACM symposium on applied computing. ACM, New York, NY, USA, pp 548–552
52.
Rodríguez JJ, Alonso CJ, Boström H (2000) Learning first order logic time series classifiers: rules and boosting. In: Zighed D, Komorowski J, Żytkow J (eds) Principles of data mining and knowledge discovery SE-29. Springer, Berlin, Heidelberg, pp 299–308CrossRef
53.
Sakoe H, Chiba S (1978) Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans Acoust Speech Signal Process 26:43–49CrossRefMATH
54.
Shi T, Wang P, Wang J-S, Yue S (2012) Application of grid-based k-means clustering algorithm for optimal image processing. Comput Sci Inf Syst 9:1679–1696CrossRef
55.
Skopal T, Bustos B (2011) On nonmetric similarity search problems in complex domains. ACM Comput Surv 43:34:1–34:50CrossRefMATH
56.
Stojanović R, Knežević S, Karadaglić D, Devedžić G (2013) Optimization and implementation of the wavelet based algorithms for embedded biomedical signal processing. Comput Sci Inf Syst 10:503–523CrossRef
57.
Takigawa Y, Hott S, Kiyasu S, Miyahara S (2005) Pattern classification using weighted average patterns of categorical k-nearest neighbors. In: Proceedings of the 1th international workshop on camera-based document analysis and recognition. pp 111–118
58.
Tomašev N, Mladenić D (2012) Nearest neighbor voting in high dimensional data: learning from past occurrences. Comput Sci Inf Syst 9:691–712CrossRef
59.
Vlachos M, Kollios G, Gunopulos D (2002) Discovering similar multidimensional trajectories. In: Proceedings 18th international conference on data engineering. IEEE Computer Society, pp 673–684
60.
Wu X, Kumar V, Ross Quinlan J et al (2008) Top 10 algorithms in data mining. Knowl Inf Syst 14:1–37CrossRef
61.
Wu Y, Chang EY (2004) Distance-function design and fusion for sequence data. In: Proceedings of the thirteenth ACM conference on information and knowledge management—CIKM’04. ACM Press, New York, New York, USA, pp 324–333
62.
Wu Y-L, Agrawal D, El Abbadi A (2000) A comparison of DFT and DWT based similarity search in time-series databases. In: Proceedings of the ninth international conference on Information and knowledge management—CIKM ’00. ACM Press, New York, New York, USA, pp 488–495
63.
Xi X, Keogh E, Shelton C et al (2006) Fast time series classification using numerosity reduction. In: Proceedings of the 23rd international conference on machine learning—ICML’06. ACM Press, New York, New York, USA, pp 1033–1040
64.
Ye L, Keogh E (2009) Time series shapelets. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining—KDD’09. ACM Press, New York, New York, USA, pp 947–956
65.
Zavrel J (1997) An empirical re-examination of weighted voting for k-NN. In: Proceedings of the 7th Belgian–Dutch conference on machine learning. pp 139–148
66.
Zhang H, Ho TB, Lin MS (2004) A non-parametric wavelet feature extractor for time series classification. In: Dai H, Srikant R, Zhang C (eds) Advances in knowledge discovery and data mining SE-71. Springer, Berlin, Heidelberg, pp 595–603CrossRef
Metadata
Title
Comparison of different weighting schemes for the kNN classifier on time-series data
Authors
Zoltan Geler
Vladimir Kurbalija
Miloš Radovanović
Mirjana Ivanović
Publication date
01-08-2016
Publisher
Springer London
Published in
Knowledge and Information Systems / Issue 2/2016
Print ISSN: 0219-1377
Electronic ISSN: 0219-3116
DOI
https://doi.org/10.1007/s10115-015-0881-0

Other articles of this Issue 2/2016

Knowledge and Information Systems 2/2016 Go to the issue

Regular Paper

Word network topic model: a simple but general solution for short and imbalanced texts

Regular Paper

IRAFCA: an O(n) information retrieval algorithm based on formal concept analysis

Regular Paper

Performance evaluation of word-aligned compression methods for bitmap indices

Regular Paper

An entropy-based clustering ensemble method to support resource allocation in business process management

Regular Paper

Phoneme sequence recognition via DTW-based classification

Regular Paper

Inferring lockstep behavior from connectivity pattern in large graphs

Premium Partner

    Image Credits