نوع مقاله : مقاله کامل پژوهشی

نویسندگان

1 دانشجوی کارشناسی ارشد، بخش مخابرات، دانشکده‌ی مهندسی برق، دانشگاه یزد، یزد، ایران

2 دانشیار، بخش مخابرات، دانشکده‌ی مهندسی برق، دانشگاه یزد، یزد، ایران

10.22041/ijbme.2022.551240.1761

چکیده

مغز انسان جزو شبکه‌های پیچیده و ناهمگن محسوب می‌شود و سیگنال‌های مغز حاوی اطلاعات زیادی هستند، از این رو محققان این حوزه همواره در صدد یافتن راه حل‌هایی مناسب برای انتخاب ویژگی‌های معنادار و کاهش بعد مناسب این اطلاعات بوده تا به طبقه‌بندی بهتری دست یابند. دو مورد از ابزارهای نوین برای پردازش سیگنال‌های مغزی، پردازش سیگنال روی گراف (GSP) و روش‌های فراابتکاری و تکاملی هستند. در روش پیشنهادی این مقاله، دو ساختار هندسی و ترکیبی برای گراف مغز در نظر گرفته شده که در ساختار ترکیبی، وزن یال‌ها، ترکیب وزن‌دار دو معیار فاصله‌ی هندسی و همبستگی است. به منظور کاهش بعد گرافی، از معیار درجه‌ی وزن‌دار و ترکیب روش کاهش کرون با تبدیل فوریه‌ روی گراف (KG) استفاده شده است تا به نحو مناسبی اطلاعات تمام راس‌های گراف در رئوس منتخب حفظ شود. استخراج ویژگی توسط تخمین لدویت-وولف و روش نگاشت فضای مماسی انجام شده و برای کاهش بعد ویژگی‌های مستخرج، از روش تحلیل مولفه‌های اصلی (PCA) و انتخاب ویژگی بر اساس تکامل تفاضلی (DE) استفاده شده است. ویژگی‌های منتخب به چندین طبقه‌بند معروف حوزه‌ی یادگیری ماشین داده شده است. برای ارزیابی عمل‌کرد روش پیشنهادی از دادگان IV-a مسابقات BCI-III بهره گرفته شده است. نتایج نشان می‌دهد که میانگین صحت طبقه‌بندی روش پیشنهادی KG-PCA با طبقه‌بندهای ماشین بردار پشتیبان با تابع پایه‌ی شعاعی (SVM-RBF) و درخت تصمیم (DT) در گراف ساختاری و گراف ساختاری-عمل‌کردی نسبت به روش TSM-GFT در مطالعات پیشین بالاتر بوده و طبقه‌بند DT به میانگین درصد صحت 17/1±15/91 دست یافته است. هم‌چنین طبق نتایج به‌ دست آمده، عمل‌کرد روش پیشنهادی KG-DE در مقایسه با KG-PCA نیز بهتر بوده و در بهترین حالت، متوسط درصد صحت طبقه‌بند SVM-RBF برابر با 27/1±50/95 به دست آمده است. 

کلیدواژه‌ها

موضوعات

عنوان مقاله [English]

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

نویسندگان [English]

  • 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

چکیده [English]

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.

کلیدواژه‌ها [English]

  • Electroencephalogram (EEG)
  • Brain-Computer Interface (BCI)
  • Graph Signal Processing (GSP)
  • Kron Reduction
  • Differential Evolution (DE)
  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.