Iranian Journal of Biomedical Engineering (IJBME)
نشریه علمی مهندسی پزشکی زیستی

Dimensionality Reduction for Motor Imagery BCI System using Kron Reduction, Graph Fourier Transform and Differential Evolution

Document Type : Full Research Paper

Authors

Mohammad Davood Khalili 1
Vahid Abootalebi 2
Hamid Saeedi-Sourck 2

1 M.Sc. Student, Department of Electrical Engineering, Yazd University, Yazd, Iran

2 Associate Professor, Department of Electrical Engineering, Yazd University, Yazd, Iran

https://doi.org/10.22041/ijbme.2022.551240.1761
Abstract
The human brain is one of the most complex and heterogeneous networks, and brain signals contain a lot of information, so researchers in this field are always looking for proper solutions to select meaningful features and reduce the dimension of this information appropriately to lead to better classification. Two of the new tools for brain signal processing are Graph Signal Processing (GSP) and Meta-heuristic and Evolutionary methods. In this paper, a geometric structure and a mixed structure are considered for the brain graph and the weights of the edges in the mixed structure are calculated by a combination of two measures: geometric distance and correlation. To reduce the graph dimension, the weighted degree metric and a combination of the Kron reduction method and Graph Fourier Transform (KG) are used to properly preserve the information of all vertices of the graph into the selected vertices. Feature extraction is performed by Ledoit-Wolf shrinkage estimation and Tangent Space Mapping (TSM) method. For dimension reduction of extracted features, Principal Component Analysis (PCA) method and feature selection based on Differential Evolution (DE) are used. The selected features are given to several well-known machine learning classifiers. To evaluate the performance of the proposed method, dataset IVa from BCI Competition III has been used. The results show that the average classification accuracy of the proposed KG-PCA method with SVM-RBF and DT classifiers, in the structural graph and the functional-structural graph, is higher than the TSM-GFT method expressed in previous studies, and the DT classifier has achieved an average accuracy of  91.15±1.17. Also, according to the obtained results, the performance of the proposed KG-DE method has been better compared to KG-PCA and in the best case, the average accuracy of the SVM-RBF classifier is equal to 95.50±1.27.

Keywords

Electroencephalogram (EEG)
Brain-Computer Interface (BCI)
Graph Signal Processing (GSP)
Kron Reduction
Differential Evolution (DE)
Subjects
  1. L. Nunez, and R. Srinivasan, "The Physics-EEG Interface" in Electric fields of the brain: The neurophysics of EEG, 2nd ed. New York, USA: Oxford University Press, 2006.
  2. R. Wolpaw, N. Birbaumer, D. J. McFarland, G. Pfurtscheller, and T. M. Vaughan, "Brain–computer interfaces for communication and control," Clinical Neurophysiology, vol. 113, no. 6, pp. 767-791, 2002.
  3. Ortega, P. Frossard, J. Kovačević, J. M. Moura and P. Vandergheynst, "Graph signal processing: Overview, challenges, and applications," Proceedings of the IEEE, vol. 106, no. 5, pp. 808-828, 2018.
  4. I. Shuman, S. K. Narang, P. Frossard, A. Ortega and P. Vandergheynst, "The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains," IEEE Signal Processing Magazine, vol. 30, no. 3, pp. 83-98, 2013.
  5. Sandryhaila and J. M. Moura, "Big data analysis with signal processing on graphs," IEEE Signal Processing Magazine, vol. 31, no. 5, pp. 80-90, 2014.
  6. Stam and J. C. Reijneveld, "Graph theoretical analysis of complex networks in the brain," Nonlinear Biomedical Physics, vol. 1, no. 3, 2007.
  7. DelEtoile and H. Adeli, "Graph theory and brain connectivity in Alzheimer’s disease," The Neuroscientist, vol. 23, no. 6, pp. 616-626, 2017.
  8. Tanaka, T. Uehara and Y. Tanaka, "Dimensionality reduction of sample covariance matrices by graph Fourier transform for motor imagery brain-machine interface," in 2016 IEEE Statistical Signal Processing Workshop (SSP), Palma de Mallorca, Spain, pp. 1-5, 2016.
  9. Kalantar, H. Sadreazami, A. Mohammadi and A. Asif, "Adaptive dimensionality reduction method using graph-based spectral decomposition for motor imagery-based brain-computer interfaces," in proc. 2017 IEEE Global Conference on Signal and Information Processing (GlobalSIP), Monreal, Canada, pp. 990-994, 2017.
  10. Huang, L. Goldsberry, N. F. Wymbs, S. T. Grafton, D. S. Bassett and A. Ribeiro, "Graph frequency analysis of brain signals," IEEE Journal of Selected Topics in Signal Processing, vol. 10, no. 7, pp. 1189-1203, 2016.
  11. Website of Berlin Institute of Technology, Charité-University Medicine Berlin, Available: https:// bbci.de/competition/iii/desc_IVa.html
  12. Blankertz, K. R. Muller, D. J. Krusienski, G. Schalk, J. R. Wolpaw, A. Schlogl, et al., "The BCI competition III: validating alternative approaches to actual BCI problems," in IEEE Transactions on Neural Systems and Rehabilitation Engineering, vol. 14, no. 2, pp. 153-159, June 2006, doi: 10.1109/TNSRE.2006.875642.
  13. K. Narang, and A. Ortega, "Perfect reconstruction two-channel wavelet filter banks for graph structured data," IEEE Transactions on Signal Processing, vol. 60, no. 6, pp. 2786-2799, 2012.
  14. D. Medaglia, W. Huang, E. A. Karuza, A. Kelkar, S. L. Thompson-Schill, A. Ribeiro, and D. S. Bassett, "Functional alignment with anatomical networks is associated with cognitive flexibility," Nature Human Behaviour, vol. 2, no. 2, pp. 156-164, 2018.
  15. K. Hammond, P. Vandergheynst and R. Gribonval, "Wavelets on graphs via spectral graph theory," Applied and Computational Harmonic Analysis, vol. 30, no. 2, pp. 129-150, 2011.
  16. Leonardi and D. Van De Ville, "Tight wavelet frames on multislice graphs," IEEE Transactions on Signal Processing, vol. 61, no. 13, pp. 3357-3367, 2013.
  17. Rui, H. Nejati and N.-M. Cheung, "Dimensionality reduction of brain imaging data using graph signal processing," in 2016 IEEE International Conference on Image Processing (ICIP), Phoenix, USA, pp. 1329-1333, 2016.
  18. Mateos, S. Segarra, A. G. Marques and A. Ribeiro, "Connecting the dots: Identifying network structure via graph signal processing," IEEE Signal Processing Magazine, vol. 36, no. 3, pp. 16-43, 2019.
  19. Behjat, N. Leonardi, L. Sörnmo and D. Van De Ville, "Anatomically-adapted graph wavelets for improved group-level fMRI activation mapping," NeuroImage, vol. 123, pp. 185-199, 2015.
  20. Yu, Y. Du, J. Chen, J. Sui, T. Adalē, G. D. Pearlson and V. D. Calhoun, "Application of graph theory to assess static and dynamic brain connectivity: Approaches for building brain graphs," Proceedings of the IEEE, vol. 106, no. 5, pp. 886-906, 2018.
  21. P. Moran, E. M. Bernat, S. Aviyente, H. S. Schroder and J. S. Moser, "Sending mixed signals: worry is associated with enhanced initial error processing but reduced call for subsequent cognitive control," Social Cognitive and Affective Neuroscience, vol. 10, no. 11, pp. 1548-1556, 2015.
  22. Faber, P. C. Antoneli, G. Via, N. S. Araújo, D. J. Pinheiro and E. Cavalheiro, "Critical elements for connectivity analysis of brain networks," in V. Yamamoto and N. Zhong (Eds.), "Functional Brain Mapping: Methods and Aims," University of Illinois at Chicago, Chicago, USA: Springer, pp. 67-106, 2020.
  23. Ramoser, J. Muller-Gerking, and G. Pfurtscheller, "Optimal spatial filtering of single trial EEG during imagined hand movement," IEEE Transactions on Rehabilitation Engineering, vol. 8, no. 4, pp. 441-446, 2000.
  24. Pfurtscheller, C. Neuper, D. Flotzinger, and M. Pregenzer, "EEG-based discrimination between imagination of right and left hand movement," Electroencephalography and Clinical Neurophysiology, vol. 103, no. 6, pp. 642-651, 1997.
  25. Blankertz, G. Curio, and K. R. Müller, "Classifying single trial EEG: Towards brain computer interfacing," Advances in Neural Information Processing Systems 14‏ (NIPS), Vancouver, Canada, pp. 157-164, 2001.
  26. A. Spielman, and S. H. Teng, "Spectral sparsification of graphs," SIAM Journal on Computing, vol. 40, no. 4, pp. 981-1025, 2011.
  27. Koutis, L. Miller, and R. Peng, "A nearly-m log n time solver for sdd linear systems," in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, USA, pp. 590-598, October, 2011.
  28. Loukas, "Graph Reduction with Spectral and Cut Guarantees," Journal of Machine. Learning Research, vol. 20, no. 116, pp. 1-42, 2019.
  29. Jin, A. Loukas, and J. JaJa, "Graph coarsening with preserved spectral properties," in International Conference on Artificial Intelligence and Statistics (PMLR), Palermo, Italy, pp. 4452-4462, June, 2020.
  30. Dorfler, and F. Bullo, "Kron reduction of graphs with applications to electrical networks," IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 60, no. 1, pp. 150-163, 2012.
  31. I. Shuman, M. J. Faraji, and P. Vandergheynst, "A multiscale pyramid transform for graph signals," IEEE Transactions on Signal Processing, vol. 64, no. 8, pp. 2119-2134, 2015.
  32. P. Van Den Heuvel, and O. Sporns, "Network hubs in the human brain," Trends in Cognitive Sciences, vol. 17, no. 12, pp. 683-696, 2013.
  33. Y. Caliskan, and P. Tabuada, "Towards Kron reduction of generalized electrical networks," Automatica, vol. 50, no. 10, pp. 2586-2590, 2014.
  34. Zhang, "Basic Properties of the Schur Complement," in The Schur complement and its applications (Vol. 4), ed. New York, USA: Springer Science & Business Media.,‏ 2006.
  35. Barachant, S. Bonnet, M. Congedo, and C. Jutten, "Multiclass brain–computer interface classification by Riemannian geometry," IEEE Transactions on Biomedical Engineering, vol. 59, no. 4, pp. 920-928, 2011.
  36. Bartz, and K. R. Müller, "Covariance shrinkage for autocorrelated data," Advances in Neural Information Processing Systems, vol. 27, pp. 1592-1600, 2014.‏
  37. Ledoit, and M. Wolf, "A well-conditioned estimator for large-dimensional covariance matrices," Journal of Multivariate Analysis, vol. 88, no. 2, pp. 365-411, 2004.
  38. Ledoit, and M. Wolf, "Nonlinear shrinkage estimation of large-dimensional covariance matrices," The Annals of Statistics, vol. 40, no. 2, pp. 1024-1060, 2012.
  39. Z. Baig, N. Aslam, H. P. Shum, and L. Zhang, "Differential evolution algorithm as a tool for optimal feature subset selection in motor imagery EEG," Expert Systems with Applications, vol. 90, pp. 184-195, 2017.
  40. N. Khushaba, A. Al-Ani, and A. Al-Jumaily, "Feature subset selection using differential evolution and a statistical repair mechanism," Expert Systems with Applications, vol. 38, no. 9, pp. 11515-11526, 2011.
  41. Liu, K. Chen, Q. Liu, Q. Ai, Y. Xie, and A. Chen, "Feature selection for motor imagery EEG classification based on firefly algorithm and learning automata," Sensors‏, vol. 17, no. 11, November, 2017.
  42. Padfield, J. Zabalza, H. Zhao, V. Masero, and J. Ren, "EEG-based brain-computer interfaces using motor-imagery: Techniques and challenges," Sensors, vol. 19, no. 6, March, 2019.
  43. Qin, V. L. Huang, and P. N. Suganthan, "Differential evolution algorithm with strategy adaptation for global numerical optimization," IEEE transactions on Evolutionary Computation, vol. 13, no. 2, pp. 398-417, 2008.
Iranian Journal of Biomedical Engineering (IJBME)
Volume 16, Issue 1
Spring 2022
Pages 75-94

  • Receive Date 02 April 2022
  • Revise Date 12 May 2022
  • Accept Date 14 May 2022

Home

Contact Us