Abstract
Time-series classification is the common denominator in many real-world pattern recognition tasks. In the last decade, the simple nearest neighbor classifier, in combination with dynamic time warping (DTW) as distance measure, has been shown to achieve surprisingly good overall results on time-series classification problems. On the other hand, the presence of hubs, i.e., instances that are similar to exceptionally large number of other instances, has been shown to be one of the crucial properties of time-series data sets. To achieve high performance, the presence of hubs should be taken into account for machine learning tasks related to time-series. In this chapter, we survey hubness-aware classification methods and instance selection, and we propose to use selected instances for feature construction. We provide detailed description of the algorithms using uniform terminology and notations. Many of the surveyed approaches were originally introduced for vector classification, and their application to time-series data is novel, therefore, we provide experimental results on large number of publicly available real-world time-series data sets.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
In this chapter, we only consider the case when each instance belongs to exactly one class. Note, however, that the presence of hubs may be relevant in the context of multilabel and fuzzy classification as well.
- 2.
Please note that the numbering of the columns and rows begins with zero, i.e., the very-first column/row of the matrix is called in this sense as the 0th column/row.
- 3.
In case of time series, consecutive values are strongly interdependent, thus instead of the length of time series, we have to consider the intrinsic dimensionality [43].
- 4.
References
Aha, D., Kibler, D., Albert, M.: Instance-based learning algorithms. Mach. Learn. 6(1), 37–66 (1991)
Altendorf, E., Restificar, A., Dietterich, T.: Learning from sparse data by exploiting monotonicity constraints. In: Proceedings of the 21st Annual Conference on Uncertainty in Artificial Intelligence, pp. 18–26. AUAI Press, Arlington, Virginia (2005)
Barabási, A.: Linked: How Everything Is Connected to Everything Else and What It Means for Business, Science, and Everyday Life. Plume, New York (2003)
Bellman, R.E.: Adaptive Control Processes—A Guided Tour. Princeton University Press, Princeton (1961)
Botsch, M.: Machine Learning Techniques for Time Series Classification. Cuvillier, Munchen (2009)
Brighton, H., Mellish, C.: Advances in instance selection for instance-based learning algorithms. Data Min. Knowl. Discov. 6(2), 153–172 (2002)
Burges, C.J.: A tutorial on support vector machines for pattern recognition. Data Min. Knowl. Discov. 2(2), 121–167 (1998)
Buza, K.A.: Fusion Methods for Time-Series Classification. Peter Lang Verlag, New York (2011)
Buza, K., Nanopoulos, A., Schmidt-Thieme, L.: Insight: efficient and effective instance selection for time-series classification. In: Proceedings of the 15th Pacific-Asia Conference on Knowledge Discovery and Data Mining. Lecture Notes in Computer Science, vol. 6635, pp. 149–160. Springer (2011)
Chen, G.H., Nikolov, S., Shah, D.: A latent source model for nonparametric time series classification. In: Advances in Neural Information Processing Systems, vol. 26, pp. 1088–1096. Springer (2013)
Cortes, C., Vapnik, V.: Support vector machine. Mach. Learn. 20(3), 273–297 (1995)
Devroye, L., Györfi, L., Lugosi, G.: A Probabilistic Theory of Pattern Recognition. Springer, New York (1996)
Duivesteijn, W., Feelders, A.: Nearest neighbour classification with monotonicity constraints. In: Machine Learning and Knowledge Discovery in Databases, pp. 301–316. Springer (2008)
Eads, D., Hill, D., Davis, S., Perkins, S., Ma, J., Porter, R., Theiler, J.: Genetic algorithms and support vector machines for time series classification. In: Applications and Science of Neural Networks, Fuzzy Systems, and Evolutionary Computation V, Proceedings of SPIE, vol. 4787, pp. 74–85 (2002)
Fix, E., Hodges, J.: Discriminatory analysis, nonparametric discrimination: consistency properties. Technical Report, USAF School of Aviation Medicine, Randolph Field (1951)
Garcia, V., Mollineda, R.A., Sanchez, J.S.: On the k-NN performance in a challenging scenario of imbalance and overlapping. Pattern Anal. Appl. 11, 269–280 (2008)
Geurts, P.: Pattern extraction for time series classification. In: Principles of Data Mining and Knowledge Discovery, pp. 115–127. Springer (2001)
Grabocka, J., Wistuba, M., Schmidt-Thieme, L.: Time-series classification through histograms of symbolic polynomials. Comput. Res. Repos.- arXiv abs/1307.6365 (2013)
Grochowski, M., Jankowski, N.: Comparison of instance selection algorithms II. Results and comments. In: International Conference on Artificial Intelligence and Soft Computing. Lecture Notes in Computer Science, vol. 3070, pp. 580–585. Springer, Berlin (2004)
Hand, D.J., Vinciotti, V.: Choosing k for two-class nearest neighbour classifiers with unbalanced classes. Pattern Recognit. Lett. 24, 1555–1562 (2003)
He, H., Garcia, E.A.: Learning from imbalanced data. IEEE Trans. Knowl. Data Eng. 21(9), 1263–1284 (2009)
He, X., Zhang, J.: Why do hubs tend to be essential in protein networks? PLoS Genet. 2(6) (2006)
Horváth, T., Vojtáš, P.: Ordinal classification with monotonicity constraints. In: Advances in Data Mining. Applications in Medicine, Web Mining, Marketing, Image and Signal Mining, pp. 217–225 (2006)
Jankowski, N., Grochowski, M.: Comparison of instance selection algorithms I. Algorithms survey. In: Proceedings of the International Conference on Artificial Intelligence and Soft Computing. Lecture Notes in Computer Science, vol. 3070, pp. 598–603. Springer, Berlin (2004)
Jolliffe, I.: Principal Component Analysis. Wiley Online Library, New York (2005)
Kehagias, A., Petridis, V.: Predictive modular neural networks for time series classification. Neural Netw. 10(1), 31–49 (1997)
Keller, J.E., Gray, M.R., Givens, J.A.: A fuzzy k-nearest-neighbor algorithm. IEEE Trans. Syst., Man Cybern. 15(4), 580–585 (1985)
Keogh, E., Shelton, C., Moerchen, F.: Workshop and challenge on time series classification. In: International Conference on Knowledge Discovery and Data Mining (KDD) (2007)
Kim, S., Smyth, P.: Segmental hidden Markov models with random effects for waveform modeling. J. Mach. Learn. Res. 7, 945–969 (2006)
Levenshtein, V.: Binary codes capable of correcting deletions, insertions, and reversals. Sov. Phys. Dokl. 10(8), 707–710 (1966)
Lin, W.J., Chen, J.J.: Class-imbalanced classifiers for high-dimensional data. Brief. Bioinform. 14(1), 13–26 (2013)
Liu, H., Motoda, H.: On issues of instance selection. Data Min. Knowl. Discov. 6(2), 115–130 (2002)
MacDonald, I., Zucchini, W.: Hidden Markov and Other Models for Discrete-Valued Time Series, vol. 1. Chapman & Hall, London (1997)
Marcel, S., Millan, J.: Person authentication using brainwaves (EEG) and maximum a posteriori model adaptation. IEEE Trans. Pattern Anal. Mach. Intell. 29, 743–752 (2007)
Martens, R., Claesen, L.: On-line signature verification by dynamic time-warping. In: Proceedings of the 13th International Conference on Pattern Recognition, vol. 3, pp. 38–42 (1996)
Marussy, K., Buza, K.: Success: a new approach for semi-supervised classification of time-series. In: Rutkowski, L., Korytkowski, M., Scherer, R., Tadeusiewicz, R., Zadeh, L., Zurada, J. (eds.) Artificial Intelligence and Soft Computing. Lecture Notes in Computer Science, vol. 7894, pp. 437–447. Springer, Berlin (2013)
Niels, R.: Dynamic time warping: an intuitive way of handwriting recognition? Master’s Thesis. Radboud University Nijmegen, The Netherlands (2004)
Petridis, V., Kehagias, A.: Predictive Modular Neural Networks: Applications to Time Series. The Springer International Series in Engineering and Computer Science, vol. 466. Springer, Netherlands (1998)
Rabiner, L., Juang, B.: An introduction to hidden Markov models. ASSP Mag. 3(1), 4–16 (1986)
Radovanović, M.: Representations and Metrics in High-Dimensional Data Mining. Izdavačka knjižarnica Zorana Stojanovića, Novi Sad, Serbia (2011)
Radovanović, M., Nanopoulos, A., Ivanović, M.: Nearest neighbors in high-dimensional data: the emergence and influence of hubs. In: Proceedings of the 26th International Conference on Machine Learning (ICML), pp. 865–872 (2009)
Radovanović, M., Nanopoulos, A., Ivanović, M.: Hubs in space: popular nearest neighbors in high-dimensional data. J. Mach. Learn. Res. (JMLR) 11, 2487–2531 (2010)
Radovanović, M., Nanopoulos, A., Ivanović, M.: Time-series classification in many intrinsic dimensions. In: Proceedings of the 10th SIAM International Conference on Data Mining (SDM), pp. 677–688 (2010)
Rish, I.: An empirical study of the naive Bayes classifier. In: Proceedings of the IJCAI Workshop on Empirical Methods in Artificial Intelligence (2001)
Sakoe, H., Chiba, S.: Dynamic programming algorithm optimization for spoken word recognition. Acoust. Speech Signal Process. 26(1), 43–49 (1978)
Schedl, M.F.A.: A Mirex meta-analysis of hubness in audio music similarity. In: Proceedings of the 13th International Society for Music Information Retrieval Conference (ISMIR 12) (2012)
Stańczyk, U.: Recognition of author gender for literary texts. In: Man-Machine Interactions 2, pp. 229–238. Springer (2011)
Sykacek, P., Roberts, S.: Bayesian time series classification. Adv. Neural Inf. Process. Syst. 2, 937–944 (2002)
Tomašev, N.: The Role of Hubness in High-Dimensional Data Analysis. Jožef Stefan International Postgraduate School (2013)
Tomašev, N., Mladenić, D.: Nearest neighbor voting in high dimensional data: learning from past occurrences. Comput. Sci. Inf. Syst. 9, 691–712 (2012)
Tomašev, N., Mladenić, D.: Class imbalance and the curse of minority hubs. Knowl. Based Syst. 53, 157–172 (2013)
Tomašev, N., Mladenić, D.: Hub co-occurrence modeling for robust high-dimensional kNN classification. In: Proceedings of the ECML/PKDD Conference. Springer (2013)
Tomašev, N., Radovanović, M., Mladenić, D., Ivanovicć, M.: A probabilistic approach to nearest neighbor classification: Naive hubness Bayesian k-nearest neighbor. In: Proceedings of the CIKM Conference (2011)
Tomašev, N., Radovanović, M., Mladenić, D., Ivanović, M.: Hubness-based fuzzy measures for high-dimensional k-nearest neighbor classification. Int. J. Mach. Learn. Cybern. 5(3), 445 (2013)
Tomašev, N., Radovanović, M., Mladenić, D., Ivanović, M.: The role of hubness in clustering high-dimensional data. IEEE Trans. Knowl. Data Eng. 99 (PrePrints), 1 (2013)
Wang, J., Neskovic, P., Cooper, L.N.: Improving nearest neighbor rule with a simple adaptive distance measure. Pattern Recognit. Lett. 28(2), 207–213 (2007)
Xi, X., Keogh, E., Shelton, C., Wei, L., Ratanamahatana, C.: Fast time series classification using numerosity reduction. In: Proceedings of the 23rd International Conference on Machine Learning (ICML), pp. 1033–1040 (2006)
Acknowledgments
Research partially performed within the framework of the grant of the Hungarian Scientific Research Fund (grant No. OTKA 108947). The position of Krisztian Buza is funded by the Warsaw Center of Mathematics and Computer Science (WCMCS).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Tomašev, N., Buza, K., Marussy, K., Kis, P.B. (2015). Hubness-Aware Classification, Instance Selection and Feature Construction: Survey and Extensions to Time-Series. In: Stańczyk, U., Jain, L. (eds) Feature Selection for Data and Pattern Recognition. Studies in Computational Intelligence, vol 584. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-45620-0_11
Download citation
DOI: https://doi.org/10.1007/978-3-662-45620-0_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-45619-4
Online ISBN: 978-3-662-45620-0
eBook Packages: EngineeringEngineering (R0)