Pruned fuzzy K-nearest neighbor classifier for beat classification
Muhammad Arif, Muhammad Usman Akram, Fayyaz-ul-Afsar Amir Minhas
DOI: 10.4236/jbise.2010.34053   PDF   HTML     6,742 Downloads   13,530 Views   Citations


Arrhythmia beat classification is an active area of research in ECG based clinical decision support systems. In this paper, Pruned Fuzzy K-nearest neighbor (PFKNN) classifier is proposed to classify six types of beats present in the MIT-BIH Arrhythmia database. We have tested our classifier on ~ 103100 beats for six beat types present in the database. Fuzzy KNN (FKNN) can be implemented very easily but large number of training examples used for classification can be very time consuming and requires large storage space. Hence, we have proposed a time efficient Arif-Fayyaz pruning algorithm especially suitable for FKNN which can maintain good classification accuracy with appropriate retained ratio of training data. By using Arif-Fayyaz pruning algorithm with Fuzzy KNN, we have achieved a beat classification accuracy of 97% and geometric mean of sensitivity of 94.5% with only 19% of the total training examples. The accuracy and sensitivity is comparable to FKNN when all the training data is used. Principal Component Analysis is used to further reduce the dimension of feature space from eleven to six without compromising the accuracy and sensitivity. PFKNN was found to robust against noise present in the ECG data.

Share and Cite:

Arif, M. , Akram, M. and Minhas, F. (2010) Pruned fuzzy K-nearest neighbor classifier for beat classification. Journal of Biomedical Science and Engineering, 3, 380-389. doi: 10.4236/jbise.2010.34053.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] Garcia, T.B. and Miller, G.T. (2004) Arrhythmia recognition: The art of interpretation. Jones and Barlett Publishers, the United States of America.
[2] Kohler, B.U., Hennig, C. and Orglmeister, R. (2002) The principles of software QRS detection. IEEE Magazine of Engineering in Medicine and Biology, 21(1), 42-57.
[3] Martinez, J.P., Almeida, R., Olmos, S., Rocha, A.P. and La-guna, P. (2004) A wavelet-based ECG delineator: Eva- luation on standard databases. IEEE Transactions on Biomedical Engineering, 51(4), 570-581.
[4] Minami, K., Nakajima, H. and Toyoshima, T. (1999) Real-time discrimination of ventricular tachyarrhythmia with fourier-transform neural network. IEEE Transactions on Biomedical Engineering, 46(2), 179-185.
[5] Prasad, G.K. and Sahambi, J.S. (2003) Classification of ECG arrhythmias using multi-resolution analysis and neural networks. Conference on Convergent Technologies for Asia-Pacific region, 1, 227-231.
[6] Al-Fahoum, A.S. and Howitt, I. (1999) Combined wavelet transform and radial basis neural networks for the classifying life threatening cardiac arrhythmias. Medical & Biological Engineering & Computing, 37, 566-573.
[7] Addison, P.S., Watson, J.N., Clegg, G.R., Holzer, M., Sterz, F. and Robertson, C.E. (2000) A Novel wavelet based analysis reveals hidden structure in ventricular fibrillation. IEEE Engineering in Medicine and Biology, 19(4), 383-392.
[8] Chen,Y.-H. and Yu, S.N. (2007) Subband features based on higher order statistics for ECG beat classification. 29th Annual International Conference of IEEE Engineering in Medicine and Biology Society, Lyon, January 1, 2001.
[9] Afsar, F.A. and Arif, M. (2008) Robust electrocardiogram (ECG) beat classification using discrete wavelet transform. Physiological Measurement, 29, 555-570.
[10] Yu, S.N. and Chou, K.T. (2007) A switchable scheme for ECG beat classification based on independent component analysis. Expert System Applications, 33(4), 824-829.
[11] Bortolan, G., Bortolan, G., Jekova, I., Jekova, I. and Christov, I. (2005) Comparison of four methods for premature ventricular contraction and normal beat clustering. Computers in Cardiology, 2005, 921-924.
[12] Exarchos, T.P., Tsipouras, M.G., Exarchos, C.P., Papaloukas, C., Fotiadis, D.I. and Michalis, L.K. (2007) A methodology for the automated creation of fuzzy expert systems for ischemic and arrhythmic beat classification based on a set of rules obtained by a decision tree. Artificial Intelligence in Medicine, 40, 187-200.
[13] Christov, I., Jekova, I. and Bortolan, G. (2005) Premature ventricular contraction classification by the Kth nearest- neighbours rule. Physiological Measurement, 1, 123.
[14] Mark, R. and Moody, G. (1988) MIT-BIH arrhythmia database directory. Second Edition, MIT Press, Cambridge.
[15] Duda, R., Hart, P. and Stork, D. (2001) Pattern classification. Second Edition, John Wiley and Sons, Inc, New York.
[16] Keller, J.M., Gray, M.R. and Givens, J.A. (1985) A fuzzy k-nearest neighbor algorithm. IEEE Transactions on Systems, Man and Cybernetics, SMC-15(4), 580.
[17] Wilson, D.R. and Martinez, T.R. (2000) Reduttion techniques for instance based learning algorithms. Machine Learning, 38(3), 257-286.
[18] Merkwirth, C., Parlitz, U. and Lauterborn, W. (2000) Fast nearest-neighbor searching for nonlinear signal processing. Physical Review E, 62(2), 2089-2097.
[19] Hart, P.E. (1968) The condensed nearest neighbor rule. IEEE Transactions on Information Theory, 14, 515-516.
[20] Ritter, G.L., Woodruff, H.B., Lowry, S.R. and Isenhour, T.L. (1975) An algorithm for a selective nearest neighbor decision rule. IEEE Transactions on Information Theory, 21(6), 665-669.
[21] Aha, D.W., Kibler, D. and Albert, M.K. (1991) Instance- based learning algorithms. Machine Learning, 6, 37-66.
[22] Wilson, D.R. and Martinez, T.R. (1997) Improved hetero-geneous distance functions. Journal of Artificial Intelligence Research (JAIR), 6(1), 1-34.
[23] Wilson, D.L. (1972) Asymptotic properties of nearest neighbor rules using edited data. IEEE Transactions on Systems, Man, and Cybernetics, 2(3), 408-421.
[24] Tomek, I. (1976) An experiment with the edited nearest-neighbor rule. IEEE Transactions on Systems, Man, and Cybernetics, 6(6), 448-452.
[25] Cameron-Jones, R.M. (1995) Instance selection by encoding length heuristic with random mutation hill climbing. Proceedings of the Eighth Australian Joint Conference on Artificial Intelligence, 99-106.
[26] Osowski, S. and Tran, H.L. (2001) ECG beat recognition using fuzzy hybrid neural network. IEEE Transactions on Biomedical Engineering, 48(11), 1265-1271.
[27] Güler, İ. and Übeylı, E.D. (2005a) ECG beat classifier designed by combined neural network model. Pattern recognition, 38, 199-208.
[28] Güler, İ. and Übeylı, E.D. (2005b) A modified mixture of experts network structure for ECG beats classification with diverse features. Engineering Applied Artificial Intelligence, 18, 845-856.
[29] Dokur, Z., Olmez, T. and Yazgan, E. (1999) Comparison of discrete wavelet and fourier transforms for ECG beat classification. Electronics Letters, 35(18), 1502-1504.
[30] Yu, S.-N. and Chen, Y.-H. (2007) Electrocardiogram beat classification based on wavelet transformation and probabilistic neural network. Pattern Recognition Letters, 28(10), 1142-1150.
[31] Yu, S.-N. and Chou, K.-T. (2008) Selection of significant independent components for ECG beat classification. Expert Systems with Applications, 36(2), 2088-2096.

Copyright © 2021 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.