J. Biomedical Science and Engineering, 2010, 3, 380-389  JBiSE
doi:10.4236/jbise.2010.34053 Published Online April 2010 (http://www.SciRP.org/journal/jbise/).
Pruned fuzzy K-nearest neighbor classifier for beat
classification
Muhammad Arif , Muhammad Usman Akram , Fayyaz-ul-Afsar Amir Minhas
1 2 3
1
Department of Computer Science and Engineering, Air University, Islamabad, Pakistan;
2
Software Engineer, Elixir technologies Pakistan (Pvt) Ltd, Islamabad, Pakistan;
3
Department of Computer and Information Sciences, Pakistan Institute of Engineering and Applied Sciences, Islamabad, Pakistan.
Email: arif@mail.au.edu.pk; usman.akram232@gmail.com; fayyazafsar@gmail.com
Received 18 January 2010; revised 30 January 2010; accepted 7 February 2010.
ABSTRACT  cardiograph (ECG) can be used as a non-invasive di-
agnostic tool for the detection of these disorders. With
the development in computing and sensor technology,
standalone automated ECG based decision support sys-
tems are an active area of research. A clinical decision
support system includes ECG acquisition, pre-proc-
essing and noise removal (baseline variation, electronic
and electromyographic noise etc.), ECG Delineation (for
detection and delineation of P, QRS and T waves of
ECG), feature extraction and beat classification.
A variety of methods exist in the literature for QRS
delineation [2] which rely upon derivative based meth-
ods, use of digital filters and filter-banks etc. One of the
most promising approaches for QRS detection and
delineation has been proposed by Martínez et al. [3]
as it offers very high detection and delineation accu-
racy. It uses wavelet domain analysis for performing
QRS detection and delineation which is particularly
suited to the ECG signal due to the non-stationary
nature of the signal.
ECG beat classification, being an integral part of any
ECG based automatic decision support system, has
been studied by a number of researchers. Different
feature extraction methods for beat classification in-
clude use of Fourier Transform [4], multi-resolution
analysis [5], wavelet transform [6-9], independent
component analysis [10], morphological analysis [11]
etc. For the purpose of beat classification, literature re-
ports a variety of classifiers such as Backpropagation
Neural Networks [8], Learning Vector Quantization and
Probabilistic Neural Networks [6], Fuzzy Inference Sys-
tems [12], Nearest Neighbor classifiers [13] etc.
Arrhythmia beat classification is an active area of
research in ECG based clinical decision support sys-
tems. 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 stor-
age 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 train-
ing data. By using Arif-Fayyaz pruning algorithm
with Fuzzy KNN, we have achieved a beat classifi-
cation accuracy of 97% and geometric mean of sensi-
tivity 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.
Keywords: Arrhythmia; ECG; K-Nearest Neighbor;
Pruning; Fuzzy; Classification
1. INTRODUCTION
In our previous work [9], we have used features ex-
tracted from two-level wavelet decomposition of an
ECG signal. The wavelet decomposition was performed
through algorithm a’ trous using the wavelet proposed by
Martínez et al. [3] for QRS delineation. This wavelet
offers inherent noise suppression and eliminates the need
of re-evaluation of wavelet coefficients for beat classifi-
Arrhythmias result due to improper pacing of the car-
diac muscle or any discrepancy in the electrical con-
duction network of the heart [1]. Detection of these
pathologically significant arrhythmias is an impera-
tive task in the diagnosis of cardiac diseases. Electro-
Published Online April 201 0 in SciRes. http://www.scirp.org/journal/jbise