Abstract
A new data mining technique used to classify normal and pre-seizure electroencephalograms is proposed. The technique is based on a dynamic time warping kernel combined with support vector machines (SVMs). The experimental results show that the technique is superior to the standard SVM and improves the brain activity classification.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
A. Babloyantz and A. Destexhe, “Low dimensional chaos in an instance of epilepsy,” Proc. Nat. Acad. Sci. USA, 83, 3513–3517 (1986).
D. Berndt and J. Clifford, “Using dynamic time warping to find patterns in time series,” in: Proc. of the AAAI-94 Workshop on Knowledge Discovery in Databases (KDD-94) (1994).
D. Bertsimas, C. R. Darnell, and R. Soucy, “Portfolio construction through mixed-integer programming at Grantham, Mayo, Van Otterloo and Company,” Interfaces, 29, No. 1, 49–66 (1999).
M. K. Borgwardt, S. V. N. Vishwanathan, and H-P. Kriegel, “Class prediction from time series gene expression profiles using dynamical systems kernels,” in: Pacific Symp. on Biocomput (2006), pp. 547–558.
P. S. Bradley, U. Fayyad, and O. L. Mangasarian, “Mathematical programming for data mining: Formulations and challenges,” INFORMS J. Computing, 11, 217–238 (1999).
P. S. Bradley, O. L. Mangasarian, and W. N. Street, “Clustering via concave minimization,” in: M. C. Mozer, M. I. Jordan, and T. Petsche (eds.), Adv. in Neural Inform. Proces. Systems, MIT Press, Cambridge (1997), pp. 368–374.
L. Breiman, J. Friedman, R. Olsen, and C. Stone, Classification and Regression Tree, Wadsworth Inc., Belmont (1993).
E. G. Caiani, A. Porta, G. Baselli, et al., “Warped-average template technique to track on a cycle-by-cycle basis the cardiac filling phases on left ventricular volume,” IEEE Comput. in Cardiology, 25, No. 98, CH36292 (1998).
W. A. Chaovalitwongse, P. M. Pardalos, L. D. Iasemidis, et al., “Applications of global optimization and dynamical systems to prediction of epileptic seizures,” in: P.M. Pardalos, J.C. Sackellares, L. D. Iasemidis, and P. R. Carney (eds.), Quantitative Neuroscience, Kluwer, Dordrecht (2003), pp. 1–36.
W. A. Chaovalitwongse, P. M. Pardalos, and O. A. Prokoyev, “Reduction of multi-quadratic 0-1 programming problems to linear mixed 0-1 programming problems,” Oper. Res. Letters, 32, No. 6, 517–522 (2004).
W. A. Chaovalitwongse, P. M. Pardalos, and O. A. Prokoyev, “Electroencephalogram (EEG) time series classification: Applications in epilepsy,” Ann. Oper. Res., 148, No. 1, 227–250 (2006).
D. Dasgupta and S. Forrest, “Novelty detection in time series data using ideas from immunology,” Intern. Conf. on Intell. Systems (1999).
J. J. R. Diez and C. A. Gonzalez, “Applying boosting to similarity literals for time series classification,” in: Intern. Workshop on Multiple Classifier Systems (2000), pp. 210–219.
C. E. Elger and K. Lehnertz, “Seizure prediction by non-linear time series analysis of brain electrical activity,” Eur. J. Neurosci., 10, 786–789 (1998).
G. M. Fung and O. L. Mangasarian, “Proximal support vector machines,” in: 7th ACM SIGKDD Intern. Conf. on Knowledge Discovery and Data Mining (2001).
D. M. Gavrila and L. S. Davis, “Towards 3-d model-based tracking and recognition of human movement: A multi-view approach,” in: Proc. Intern. Workshop on Autom. Face-and Gesture-Recognition (1995).
P. Geurts, “Pattern extraction for time series classification,” in: 5th Eur. Conf. on Principles of Data Mining and Knowledge Discovery (2001), pp. 115–127.
R. L. Grossman, C. Kamath, P. Kegelmeyer, et al., Data Mining for Scientific and Engineering Applications, Kluwer, Dordrecht (2001).
D. J. Hand, H. Mannila, and P. Smyth, Principle of Data Mining, Bradford Books, Concord (2001).
C.-W. Hsu and C.-J. Lin, “A comparison of methods multi-class support vector machines,” IEEE Trans. on Neural Networks, 13, 415–425 (2002).
A. S. Hurn, K. A. Lindsay, and C. A. Michie, “Modelling the lifespan of human t-lymphocite subsets,” Math. Biosciences, 143, 91–102 (1997).
F. J. Iannatilli and P. A. Rubin, “Feature selection for multiclass discrimination via mixed-integer linear programming,” IEEE Trans. on Pattern Analysis and Machine Learning, 25, 779–783 (2003).
L. D. Iasemidis, “On the dynamics of the human brain in temporal lobe epilepsy,” PhD Thesis, Univ. of Michigan, Ann Arbor (1991).
L. D. Iasemidis, P. M. Pardalos, J. C. Sackellares, and D.-S. Shiau, “Quadratic binary programming and dynamical system approach to determine the predictability of epileptic seizures,” J. Comb. Optimiz., 5, 9–26 (2001).
L. D. Iasemidis, D.-S. Shiau, W. A. Chaovalitwongse, et al., “Adaptive epileptic seizure prediction system,” IEEE Trans. Biomed. Eng., 5, No. 5, 616–627 (2003).
L. D. Iasemidis, H. P. Zaveri, J. C. Sackellares, and W. J. Williams, “Phase space analysis of eeg in temporal lobe epilepsy,” in: 10th Ann. Intern. Conf. “IEEE Eng. in Medicine and Biology Soc.” (1988), pp. 1201–1203.
E. Keogh, K. Chakrabarti, M. Pazzani, and S. Mehrotra, “Dimensionality reduction for fast similarity search in large time series databases,” Knowledge and Inform. Systems, 3, No. 3, 263–286 (2000).
E. Keogh and S. Kasetty, “On the need for time series data mining benchmarks: A survey and empirical demonstration,” in: 8th ACM SIGKDD Intern. Conf. on Knowledge Discovery and Data Mining (2002), pp. 102–111.
E. Keogh and M. Pazzani, “An enhanced representation of time series which allows fast and accurate classification, clustering and relevance feedback,” in: 4th Intern. Conf. on Knowledge Discovery and Data Mining (1998), pp. 239–241.
E. Keogh and M. Pazzani, “Scaling up dynamic time warping for datamining applications,” in: Proc. 6th ACM SIGKDD Intern. Conf. on Knowledge Discovery and Data Mining (2000), pp. 285–289.
U. Krebel, “Pairwise classification and support vector machines,” in: Adv. in Kernel Methods-Support Vector Learning, MIT Press, Cambridge (1999), pp. 255–268.
K. Lehnertz and C. E. Elger, “Can epileptic seizures be predicted? Evidence from nonlinear time series analysis of brain electrical activity,” Phys. Rev. Lett., 80, 5019–5022 (1998).
B. Litt, R. Esteller, J. Echauz, et al., “Epileptic seizures may begin hours in advance of clinical onset: A report of five patients,” Neuron, 30, 51–64 (2001).
O. L. Mangasarian, “Linear and nonlinear separation of pattern by linear programming,” Oper. Res., 31, 445–453 (1965).
O. L. Mangasarian, W. N. Street, and W. H. Wolberg, “Breast cancer diagnosis and prognosis via linear programming,” Oper. Res., 43, No. 4, 570–577 (1995).
J. Martinerie, C. Van Adam, and M. L. Van Quyen, “Epileptic seizures can be anticipated by non-linear analysis,” Nature Medicine, 4, 1173–1176 (1998).
N. H. Packard, J. P. Crutchfield, and J. D. Farmer, “Geometry from time series,” Phys. Rev. Lett., 45, 712–716 (1980).
P. M. Pardalos, W. A. Chaovalitwongse, L. D. Iasemidis, et al., “Seizure warning algorithm based on spatiotemporal dynamics of intracranial EEG,” Math. Program., 101, No. 2, 365–385 (2004).
J. R. Quinlan, C4.5: Programs for Machine Learning, Morgan Kaufmann, Orlando (1993).
M. L. Van Quyen, J. Martinerie, M. Baulac, and F. Varela, “Anticipating epileptic seizures in real time by non-linear analysis of similarity between eeg recordings,” Neuro Rep., 10, 2149–2155 (1999).
L. Rabiner and B. Juang, Fundamentals of Speech Recognition, Prentice Hall, Upper Saddle River (1993).
P. E. Rapp, I. D. Zimmerman, and A. M. Albano, “Experimental studies of chaotic neural behavior: Cellular activity and electroencephalographic signals,” in: H. G. Othmer (ed.), Nonlinear Oscillations in Biology and Chemistry, Springer, New York (1986), pp. 175–205.
S. Rüping, “SVM kernels for time series analysis,” in: R. Klinkenberg, S. Rüping, A. Fick, N. Henze, C. Herzog, R. Molitor, and O. Schröder (ed.), LLWA 01-Tagungsband der GI-Workshop-Woche Lernen-Lehren-Wissen-Adaptivitet (2001), pp. 43–50.
M. Schmill, T. Oates, and P. Cohen, “Learned models for continuous planning,” in: Proc. 7th Intern. Workshop on Artif. Intell. and Statist. (1999), pp. 278–282.
B. Scholkopf, C. Burges, and V. Vapnik, “Extracting support data for a given task,” in: Proc. 1st Intern. Conf. on Knowledge Discovery and Data Mining, AAAI Press, Menlo Park (1995).
B. Schölkopf, “The kernel trick for distances,” in: Techn. Rep., Microsoft Research (2000).
H. Shimodaira, K. Noma, M. Naka, and S. Sagayama, “Support vector machine with dynamic time-alignment kernel for speech recognition,” in: Proc. of Eurospeech (2001), pp. 1841–1844.
F. Takens, “Detecting strange attractors in turbulence,” D. A. Rand and L. S. Young (eds.), Dynamical Systems and Turbulence, Lecture Notes in Mathematics, Springer-Verlag, Berlin (1981).
V. N. Vapnik, The Nature of Statistical Learning, Springer, Berlin (1995).
V. Wan and J. Carmichael, “Polynomial dynamic time warping kernel support vector machines for dysarthric speech recognition with sparse training data,” in: Proc. of Interspeech (2005), pp. 3321–3324.
A. Wolf, J. B. Swift, H. L. Swinney, and J. A. Vastano, “Determining Lyapunov exponents from a time series,” Physica D, 16, 285–317 (1985).
K. Yang and C. Shahabi, “A pca-based kernel for kernel pca on multivariate time series,” in: Proc. of ICDM 2005 Workshop on Temporal Data Mining: Algorithms, Theory and Applications held in conjunction with the 5th IEEE Intern. Conf. on Data Mining (ICDM’05) (2005).
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was partially supported by Rutgers Research Council grant 202018, NSF grants CCF-0546574, DBI-980821, EIA-9872509, and CCF 0546574, and NIH grant R01-NS-39687-01A1.
__________
Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 159–173, January–February 2008.
Rights and permissions
About this article
Cite this article
Chaovalitwongse, W.A., Pardalos, P.M. On the time series support vector machine using dynamic time warping kernel for brain activity classification. Cybern Syst Anal 44, 125–138 (2008). https://doi.org/10.1007/s10559-008-0012-y
Received:
Issue Date:
DOI: https://doi.org/10.1007/s10559-008-0012-y