Biomedical Signal Processing and Control 5 (2010) 114–123 Contents lists available at ScienceDirect Biomedical Signal Processing and Control journal homepage: www.elsevier.com/locate/bspc Local fractal dimension based ECG arrhythmia classification Amit K. Mishra *, Shantanu Raghav Department of Electronics and Communication Engineering, Indian Institute of Technology Guwahati, India A R T I C L E I N F O A B S T R A C T Article history: Received 13 August 2008 Received in revised form 30 December 2009 Accepted 5 January 2010 Available online 2 February 2010 We propose a local fractal dimension based nearest neighbor classifier for ECG based classification of arrhythmia. Local fractal dimension (LFD) at each sample point of the ECG waveform is taken as the feature. A nearest neighbor algorithm in the feature space is used to find the class of the test ECG beat. The nearest neighbor is found based on the RR-interval-information-biased Euclidean distance, proposed in the current work. Based on the two algorithms used for estimating the LFD, two classification algorithms are validated in the current work, viz. variance based fractal dimension estimation based nearest neighbor classifier and power spectral density based fractal dimension estimation based nearest neighbor classifier. Their performances are evaluated based on various figures of merit. MIT-BIH (Massachusetts Institute of Technology - Boston’s Beth Israel Hospital) Arrhythmia dataset has been used to validate the algorithms. Along with showing good performance against all the figures of merit, the proposed algorithms also proved to be patient independent in the sense that the performance is good even when the test ECG signal is from a patient whose ECG is not present in the training ECG dataset. ß 2010 Elsevier Ltd. All rights reserved. Keywords: ECG arrhythmia Beat classification Fractal dimension Patient-independent classifier 1. Introduction Cardiac arrhythmia is a term for any abnormal electrical activity in heart beats. Electrocardiogram (ECG) is one of the most important noninvasive tools for the diagnosis of cardiac arrhythmia. The classification of ECG signals into different disease categories is a complex pattern recognition problem. For the computer-aided diagnosis (CAD) of ECG signals, a wide range of signal processing techniques have been used, like spectral analysis, time frequency distribution and nonlinear signal processing techniques [1–5]. Researchers have also used wavelets [6], artificial neural networks (ANN) [7], fuzzy and neuro-fuzzy systems [8], hidden Markov modeling [9], principal component analysis (PCA) [10] and independent component analysis (ICA) [11]. There have also been works on the use of simple template matching based classifier for the detection and classification of arrhythmia using ECG signal [12,13]. However, most of the published algorithms are not validated regarding their performance in stringent conditions like the lack of enough training dataset. Secondly, most of these algorithms do not perform well if the training and test ECG signals are from different patients. The current work proposes algorithms based on local fractal dimension of ECG signal. The idea of self similar structures has * Corresponding author. E-mail addresses: amishra@iitg.ernet.in, akmishra@ieee.org (A.K. Mishra), s.raghav@iitg.ernet.in (S. Raghav). 1746-8094/$ – see front matter ß 2010 Elsevier Ltd. All rights reserved. doi:10.1016/j.bspc.2010.01.002 occurred in mathematical research for a long time. It was Mandelbrot who gave this idea a firm theoretical background and coined such structures as fractals [14]. Broadly speaking, a fractal structure has the same statistics under any scale of magnification [14–16]. Due to their ability to model nature more accurately, fractal modeling has proved to be an important tool in a wide spectrum of fields, starting from image analysis, texture modeling, market analysis to the study of genome sequences [17– 19]. Previous studies suggest that physiological signals generated by complex self-regulating systems under healthy conditions may have a fractal temporal structure [20]. Fractal geometry based methods have been a major success in cardiac signal analysis [21]. It has been reported that ECG signals are well modeled as selfaffined fractal sets and their classification is possible by using fractal dimension [22–24]. There has also been some reports on the use of multifractal model for cardiac signal analysis [25,26]. However, none of the works in the open literature has extensively tested and validated a fractal dimension based ECG signal classification algorithm. In one of the earlier works [27], the authors have tried using local fractal dimension based nearest neighbor classifier for ECG signal based arrhythmia classification, and results were encouraging. The current work is an expanded version of the earlier work and here we have done some addition to the base algorithm and have validated it extensively. In the current work, local fractal dimension (LFD) of neighboring sample points of ECG signal segments are used as the features on which the classifier is based. For estimating the LFD we have A.K. Mishra, S. Raghav / Biomedical Signal Processing and Control 5 (2010) 114–123 used two methods, viz. power spectral density based fractal dimension estimator (PSDFE) and variance based fractal dimension estimator (VFE). A modified Euclidean distance based nearest neighbor classifier is used as the final classification machine. This modified Euclidean distance takes into account the RR-interval information, and is a contribution of the authors. The proposed algorithms have many unique advantages. First of all the performance of the classifier in terms of sensitivity and specificity is comparable to the best in the open literature. Secondly, the classification results also have a good confidence level, as observed from the error-bar analysis and performance with reduction of training dataset. From these experiments, the VFE based classifier was found to be more suitable for ECG based arrhythmia classification. Another novelty of this algorithm is the performance of the classifier when it is presented with ECG of patients whose ECG signals were not present in the training dataset. The classifier is found to give good performance with different patients without any a priori information about the patient. It may be noted here that there are very few works in the open literature which have validated ECG classifiers using different sets of patients in the training and test phases [28,29], and many of these works use some amount of a priori information about the patient. On the other hand the proposed algorithm uses no such information. The rest of the paper is organized as follows. The next section gives a description about fractals and discusses two major algorithms for estimating the local fractal dimension, as used in this paper. Section 3 describes the database used in the classification exercise. After this the classification algorithm is described. Section 5 discusses the figures of merit based on which the validation of the classifiers has been done. After that we give the results and analyze them. Section 7 discusses some of the limitations of the current study and the implications of the same. The last section ends the paper with conclusive remarks. Fractal is a mathematical model to represent self similar structures and is used to describe scale invariant random processes. Fractals are often characterized by their fractional dimensions [30]. Many algorithms have been devised to estimate the fractal dimension of a time series, viz. power spectral analysis [31], range scaled analysis by the calculation of Hurst exponent[32], box-counting method [33], Higuchi method [34], analysis by wavelet packets [35], etc. The algorithms to estimate the fractal dimension can be grouped into two groups, viz. timedomain analysis based estimators, and transfer-domain analysis based estimators. To estimate the fractal dimension of ECG signals we have used two methods, one from each group. From transferdomain analysis based group of estimators, power spectral density based fractal dimension estimator (PSDFE) [31] is chosen. From time-domain analysis based group of estimators, variance based fractal dimension estimator (VFE) [36] is chosen. These estimators are chosen based on their reported performance and the ease of implementing them. 2.1. Power spectrum density based fractal dimension estimator PSDFE is a well-accepted method to estimate the fractal dimension of biological signals[31]. Let xðnÞ be a discrete sequence. Then the power spectrum of the discrete signal can be calculated by the square of its Fourier transform. The power spectrum (Sð f n Þ) of a fractal process in frequency domain follows a power law relationship with the frequency (f), according to the following relation. b Sð f n Þ  p fn Taking logarithm of both sides of the expression yields log Sð f n Þ  log p  blog f n : (1) (2) The spectral exponent b is estimated by the slope of the line fitting the log–log plot of the power spectrum by a least square method in the linear frequency range. Fractal dimension D can be expressed in terms of spectral index b by the following equation. D¼ 5b 2 (3) To find the fractal dimension of a curve, first an estimate of b is obtained from the PSD curve and then the fractal dimension D is found using the above expression. 2.2. Variance based fractal dimension estimator VFE [36] is a popular method for estimating the fractal dimension of a non chaotic time series. It is estimated by the spread of the increments in the signal amplitude. The variance s 2 , of the amplitude increments for a time series xðnÞ over a given time increment is proportional to the time increment according to the following power law varðxðn2 Þ  xðn1 ÞÞ  jn2  n1 j2H : (4) Here H is the Hurst exponent and var() function which determines the variance. By setting Dn ¼ jn2  n1 j and ðDxÞDn ¼ xðn2 Þ  xðn1 Þ, H can be estimated from a log–log plot of Dnm versus varðDxÞm . Dnm is the discrete time increment at the m th order scale. Similarly, varðDxÞm is the amplitude increment over that discrete time increment at the m th order scale. The slope s of the line fitting the log–log plot can be calculated by least square method and Hurst exponent is obtained from H¼ 2. Fractals and fractal dimension 115 s : 2 (5) Hurst exponent H is related to fractional dimension D as: D ¼ E þ 1  H: (6) where E is the Euclidean dimension [14]. For ECG signals E ¼ 1 and hence D ¼ 2  H: (7) 3. ECG signal database and preprocessing The data used in the present work is the ECG signal database from the MIT-BIH (Massachusetts Institute of Technology Boston’s Beth Israel Hospital) Arrhythmia Database [37] available on Physionet website. The MIT-BIH Arrhythmia Database contains 48 half-hour excerpts of two-channel ambulatory ECG recordings, obtained from 47 subjects studied by the BIH Arrhythmia Laboratory between 1975 and 1979. The recordings were digitized at 360 samples per second per channel with 11-bit resolution over a 10 mV range. The proposed algorithm uses small segments of the ECG records of modified limb lead II (MLII), each segment consisting of 200 samples. A fixed length window around the maximum peak of R wave, was applied to extract the heartbeat waveform. Not only QRS complex but also some parts of P and T waves were extracted by using a window starting 50 samples before the R-peak and ending 150 samples after the same point. Hence, the ECG waveform samples are aligned in time. It can be noted here that unlike most of the ECG arrhythmia classifier algorithms, for LFD based algorithms it is not required to normalize the ECG beats in the preprocessing stage. This is because of the fact that linear operations on a signal do not change its fractal 116 A.K. Mishra, S. Raghav / Biomedical Signal Processing and Control 5 (2010) 114–123 Table 1 The number and type of QRS complexes used in this study. Type MIT-BIH file number N 100, 105, 116, 201, 212, 222, 101, 106, 117, 202, 213, 223, 102, 104, 108, 112, 119, 121, 203, 205, 215, 217, 228, 230, No. of QRS complexes No. of QRS complexes for validation 74,952 49,983 113, 114, 115, 122, 123, 200, 208, 209, 210, 219, 220, 221, 231, 233, 234 L 109, 111, 207, 214 8066 5380 R 118, 124, 207, 212, 231, 232 7248 4833 PB 102, 104, 107, 217 7016 4678 V 100, 109, 123, 207, 217, 233, 102, 111, 124, 208, 219, 234, 104, 105, 106, 107, 108 114, 116, 118, 119, 121, 200, 201, 202, 203, 205, 209, 210, 213, 214, 215, 221, 223, 228, 230, 231, 7126 4764 A 100, 117, 205, 223, 101, 118, 207, 228, 103, 108, 112, 114, 116 121, 124, 200, 201, 202, 209, 213, 215, 220, 222, 231, 232, 233 2541 1701 106,949 71,334 Total dimension [15]. Hence, the estimated LFD is roughly independent of any scaling operation done on the signal. The database consists of ECG beats belonging to five types of arrhythmia and normal ECG (N). The arrhythmia types are left bundle branch block beat (L), right bundle branch block beat (R), atrial premature beat (A), premature ventricular contraction (V) and paced beat (PB). The ECG beats in the database are summarized in Table 1. Out of these, one third of the ECG beats are selected for training and the remaining for testing or validating the classifiers. 4. Fractal dimension based nearest neighbor classifier This section describes the proposed fractal dimension based nearest neighbor classifier (FDNN). The ECG signal is preprocessed as described in the above section. The next step is to extract the fractal dimensions of the ECG signal. For that, the local fractional dimension is calculated for each sample point in the signal by using the two algorithms described in Section 2, separately. In case of PSDFE algorithm, a Hamming window of size W is taken around each sample point of the ECG record, after which its fractional dimension is calculated by Eqs. (1)–(3). The reason to choose Hamming window is to reduce the side-lobes in the frequency domain. Fractional dimension at each point consists of fractal information about its neighboring sample points. Thus, this moving window of size W over each ECG signal waveform of 200 samples converts the signal into a time series of fractional dimensions of size ð200  WÞ. Similarly, in case of the VFE, a rectangular window of the same size W is taken around each sample point and fractional dimension is calculated by using Eqs. (4), (5) and (7). In the training phase, the above process is applied on each preprocessed ECG beat in the training set and the resulting fractal dimension series are used as features. In the test phase, each ECG beat in testing set is first converted into its fractal dimension series. Then its nearest neighbor is found from the ECG beats from the training set, in the fractal dimension feature dimension. For finding the nearest neighbor, a modified Euclidean distance incorporating the RR-interval information has been used. This measure is termed as the RR-biased Euclidean distance (RRED) and, for two fractal dimension sequences xi and yi , is defined as: vffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi u200W   u X RRdi f f 2 ðxi  yi Þ2 þ RRED ¼ t : (8) i¼1 k Here RRdi f f is the difference of RR-interval values (RRdi f f ) between the training and testing QRS complexes. To keep the contribution of RRdi f f at a desired level, it is scaled by factor k. The value of k was experimentally determined to be 10. The reason for biasing Euclidean distance with RRdi f f is the observation that ECG beats for certain arrhythmia such as atrial fibrillation, are difficult to detect on the basis of the information from the QRS complex only. For example, the heart rate varying features in arrhythmia of type A are the prominent factors in their detection and the RR-interval information may help in recognizing these beats. A switchable scheme has been implemented for ECG classification by Yu et al. [11] which decides the length of the sample for classifier on the basis of the RR-interval value. The proposed RRED has been inspired by such works. After finding the nearest neighbor in the fractal dimension feature space, the class of the ECG beat giving the minimum RRED is declared as the class of the test signal. In our work we have used two different algorithms to estimate the local fractal dimension. Based on the algorithm used, we developed two classification algorithms, viz. PSDFE based nearest neighbor classifier (PSDFENNC) and VFE based nearest neighbor classifier (VFENNC). 5. Figures of merit for comparison Comparison and validation of classification algorithms have always been tough. Due to the high mortality rate among the patients with heart diseases and high risk involved in arrhythmia diseases, the ECG classification task becomes more crucial and sensitive. Rigorous validation of the algorithm is to be done before the implementation of an ECG beat classifier in real-time heart diagnosis. Thus, the correct classification rate or sensitivity should not be the only figure of merit, in evaluating the performance of the classifier. Considering all the features affecting the performance of 117 A.K. Mishra, S. Raghav / Biomedical Signal Processing and Control 5 (2010) 114–123 an ECG classifier algorithm, the comparison between the two above mentioned algorithm PSDFENNC and VFENNC and the validation of the same is done on the basis of the following figures of merit. 5.1. Confusion matrix Confusion matrix is by far the most comprehensive form of representing the results from a classification exercise. The entries in the confusion matrix give the number of QRS complexes of a given class, classified as different classes. For example, the (i, j)th entry in the confusion matrix represents the number of QRS complexes from the test dataset belonging to class i recognized as the class j. Following are some of the information that can be extracted from the confusion matrix. – Sensitivity Se for a given class i is calculated using the (i, i)th element of the confusion matrix, i.e. Sei ¼ CMði; iÞ ; Ni (9) where CM(i, i)th is the (i, i)th element of the confusion matrix and N i is the total no. of QRS complexes for class i. The sensitivity of a classifier measures the proportion of actual positives which are correctly identified. – Average sensitivity for a given classification algorithm is given by the expression Average sensiti ðSe Þ ¼ M 1X Se M i¼1 i (10) where M is the number of classes of ECG beats in the dataset. – Specificity S p of a classifier measures the proportion of negatives which are correctly identified, i.e. the fraction of correctly identified QRS complexes that does not belong to a certain class. Hence, the specificity for a given class i is calculated as S pi ¼ 1  M X CMð j; iÞ  CMði; iÞ j¼1 0 1 M X @ N j A  Ni (11) : j¼1 5.2. Performance with reduced training dataset ECG measurements involve human subjects in clinical environment. This makes the collection of extensive amount of real-life data, both time consuming and costly. Hence, a practical ECG signal based arrhythmia classifier is expected to perform with limited amount of training dataset. The trend of how a classifier behaves with reduced training data is the next ground on which the current algorithms have been evaluated. The less the deviation observed in the percentage of correct classification with reduced training dataset, the more efficient is the classifier. 5.3. Receiver operating characteristics (ROC) curves In a detection problem, the ROC curve is plotted between the 1  s peci ficity and average sensitivity. The present way of looking at ROC curves has been adopted to examine the performance of the algorithms to see how efficient it is in classifying a particular class. This was analyzed by assigning a threshold of classification to each arrhythmia class. For a template matching type algorithm atst 2 arg min ðkatst ; atrði; jÞ k  g i Þ: (12) i Here g i is the risk factor assigned to the ith class, atst is the test QRS complex and atrði; jÞ is the jth ECG template of the ith class. The higher the threshold g i for a class, the more difficult it is to miss that class. At the same time, the easier it is to mis-classify another arrhythmia as belonging to this class. For a given value of g i and a given ECG class, the confusion matrix was calculated. From that, the values of average sensitivity and specificity were found. This procedure was repeated for all the classes. By varying the value of g i , the ROC curve of a particular type of target is determined for a given FDNN algorithm. 5.4. Patient independence of the classifier The ECG waveforms of different patients and patient groups vary wildly in their morphologies, which make their automatic real-time classification a tough task. The performance of an ECG beat classifier often deteriorates when presented with ECG waveform of a different patient than those whose ECG waveforms have been used in the training phase. To overcome this problem, we may use a training dataset containing ECG signal from all the possible patient types. However it is not practically feasible to cover every ECG waveform of all potential patients. Also, it will be a costly and time consuming approach as it is difficult to develop and maintain such a large training database in practice. Hence, a good classifier must perform well with a training database collected from a limited number of patients. This is an important figure of merit and unfortunately not much stressed in many of the works on ECG arrhythmia classification. Some previous studies have developed algorithms to solve this problem by monitoring the patient for some time before using their ECG signals for classification [28,29]. To validate an ECG classifier for its patient-independent nature, we have devised the following scheme. The performance of a classifier is tested under six different cases. In each case, the ECG signals in the test dataset are from patients different from the patients whose ECG beats are used in the training phase. For this set of experiments, we have used the recordings from 25 patients as described in Table 2. Recordings from rest of the subjects have not been used. This is because in the rest of the subjects, there are some with more than one type of arrhythmia. Hence they cannot be used to represent a single type of arrhythmia. Secondly, the 25 Table 2 QRS complexes used for patient-independent study of different classifiers. Experiment number MIT-BIH file number used in test phase (each file number corresponds to a different patient) No. of QRS complexes I II III IV V VI 209, 222, 232, 209, 222, 232, 17,241 15,570 16,234 16,606 17,752 17,646 109, 111, 207, 109, 109, 111, 111, 207, 214, 214, 207, 214, 103, 113, 115, 123, 220, 103, 113, 115, 123, 220, 234, 234, 102, 104, 107, 102, 102, 104, 104, 107, 217, 217, 107, 217, 118, 124, 212, 118, 118, 124, 124, 212, 231, 231, 212, 231, 119, 200, 221, 119, 119, 200, 200 221 233 233 221 233 118 A.K. Mishra, S. Raghav / Biomedical Signal Processing and Control 5 (2010) 114–123 patients under consideration contribute towards the maximum amount of recordings in the dataset. Rest of the patients contribute mostly towards normal type of ECG or have very little amount of data. Hence if included, these will increase the amount of normal ECG disproportionately which in turn will give rise to biased classification. ECG waveforms from 11 patients out of the total 25 patients are used for testing and ECG waveform from the rest 14 patients are used for training. The patients are selected such that training set and test set both contain at least one patient from each class of arrhythmia. Table 2 describes the MIT files used for testing and training. 5.5. ECG fractal clustering analysis The fractal features of ECG signals are obtained by converting the original QRS signals into a fractal dimension time series. The effectiveness of these features for separating the different morphological classes is demonstrated by using statistical measures such as cluster dispersion and cluster-to-cluster distance. Such measures can be effectively used as quantitative ways of predicting the classifiability of classes [38]. In the current study, we have used two measures for testing the classifiability of arrhythmia in the domain of fractal dimension time series of ECG signal. Geometrical separability index (GSI): Thornton’s separability index or geometrical separability index [39] is a measure of the separability of the classes assuming a nearest neighbor type of classifier. GSI has been used to design optimal support vector machines and in other machine learning exercises [40,41]. GSI gives an idea about if two classes are separable in a nearest neighbor sense or not. For two data-clusters, GSI is given as: GSI ¼ N X ð f ðxi Þ þ f ðxiNN Þ þ 1Þmod2 i¼1 N (13) Here, xi is a data point and xiNN is its nearest neighbor. f represents the binary decision classification function giving the class number of the data point. N is the total number of data points. GSI finds the number of data points for which its nearest neighbor is from the same class as itself. Bhattacharya distance: Bhattacharya distance (BD) is a measure of difference or separability between two Gaussian distributed data-clusters. This is given by [42,43].   S1 þS2   1  2  1 1 T S1 þ S2 BD ¼ ðM 1  M 2 Þ ðM 1  M 2 Þ þ ln qffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi (14) 2 8 2 jS1 jjS2 j Here, S1 and S2 are the covariance matrices of clusters 1 and 2, respectively. M 1 and M 2 are mean vectors of clusters 1 and 2, respectively. BD as expressed in the above expression has two terms. The first term gives the difference between the means of the two clusters, normalized by the sum of their spreads as given by the covariance of the clusters. The second term shows the difference between the spread of the two clusters. Based on these measures the cluster-to-cluster distance and cluster dispersion of the arrhythmia classes were analyzed in the current work. 6. Results and discussion This section presents the results from the present work and discusses the implications of the same. All ECG signal beats of 200 sample points each, as mentioned in Table 1 are processed using the two algorithms, PSDFE and VFE, for estimating their local fractal dimension series. To achieve good classification performance the sliding window (W) should be chosen judiciously for the algorithms. The window size affects the quality of the LFD features obtained. A very small window introduces noise into the estimated fractal dimension and a very large window may cause loss of information. An optimal sliding window of size 30 is chosen experimentally by inspecting the local fractal series of the ECG samples. After the calculation of LFD, the samples reduce to a length of 170 sample points, resulting in higher processing speed and less use of hardware memory. One third of the total QRS complexes (i.e. 35,615 QRS complexes) are kept for training and rest of them (i.e. 71,334 QRS complexes) are used in the test phase. The performance of the two classifiers is compared on the basis of the figures of merit as discussed in the last section. Before we proceed with the results a note on the fractal dimension of ECG signals is in order. Fig. A1 in Appendix A displays the QRS complexes for class V and class A arrhythmia and the fractal dimension of corresponding QRS complexes by VFENNC and PSDFENNC algorithm. It can be interpreted from the figure that the three different QRS complexes of a normal ECG beat give almost similar fractal dimension series by VFENNC algorithm however a considerate difference can be seen in QRS complexes of these three normal beats. Also from the same figure it can be seen that the fractal dimension by PSDFENNC algorithm are almost similar for three completely different QRS complexes of class V arrhythmia. Fig. A2 in Appendix A displays the fractal dimension series for all six classes of arrhythmia and their QRS complexes. It can be noted here that VFE is a time-domain fractal dimension estimator, whereas PSDFE is a transform domain estimator. Hence the local fractal dimensions as estimated using these two algorithms are not exactly equal. Local small perturbations affect the VFE estimated dimension severely and hence the fractal dimension estimated by VFE is more varying than that estimated using PSDFE. 6.1. Absolute performance and confusion matrix There are six different classes of arrhythmia taken into consideration in this work. Correspondingly there will be six sensitivity indices. Tables 3 and 4 give the confusion matrices of the VFENNC and PSDFENNC, respectively. The rows represent the ECG database classes and columns represent the ECG classes classified by the algorithm. Thus as previously explained the (i, j)th element of a confusion matrix represent the number of QRS complexes which belong to class i and classified as class j. The diagonal elements of the confusion matrices show the number of correctly classified QRS complexes. Table 5 gives the average specificity and average sensitivity information for different classes. The average sensitivity for PSDFENNC is 92.8%, while the same for VFENNC is 95.6%. The average specificity performance in percentage for all ECG arrhythmia using VFENNC is found to be 99.4% and the same using PSDFENNC is found to be 98.8%. These figures are comparable to those of some of the best ECG arrhythmia classifiers reported in the open literature [11,44,45]. It may also be observed that VFENNC performs better than PSDFENNC. Table 3 Confusion matrix for VFENNC (the rows represent database classification and the columns represent algorithm classification). N L R PB V A N L R PB V A 49,441 124 80 32 229 208 129 5238 8 6 25 3 64 6 4732 2 6 9 1 2 0 4630 7 0 136 6 5 7 4481 11 212 4 8 1 16 1470 A.K. Mishra, S. Raghav / Biomedical Signal Processing and Control 5 (2010) 114–123 119 Table 4 Confusion matrix for PSDFENNC (the rows represent database classification and the columns represent algorithm classification). N L R PB V A N L R PB V A 48,908 238 185 56 379 314 343 5109 8 1 28 4 170 8 4629 3 13 12 12 3 0 4611 3 0 193 18 3 6 4286 16 357 4 8 1 55 1355 Table 5 Different figures of merit for VFENNC and PSDFENNC. Type of Average sensitivity Average specificity ECG beat VFENNC PSDFENNC VFENNC PSDFENNC N L R PB V A Avg. 98.92 97.36 97.91 98.97 94.06 86.42 95.6 97.86 94.96 95.78 98.57 89.96 79.65 92.8 97.49 99.78 99.85 99.93 99.57 99.67 99.4 94.99 99.59 99.69 99.90 99.28 99.50 98.8 Fig. 2. Receiver operating characteristics (ROC) curves for VFENNC and PSDFENNC for ventricular contraction. 6.3. ROC curves 6.2. Performance with reduced training set This section gives the results regarding the performance of the FDNN algorithm with reduced amount of training data. Fig. 1 describes the trend of how the two FDNN classifiers behave with reduced amount of training data for PSDFE and VFE, respectively. The indices on X-axis represent the reduction factor (p) defined by the following equation and indices on Y-axis represent the classification performance in terms of average sensitivity for all the six arrhythmia classes. pðreduction factorÞ ¼ no: of test QRS complexes no: of training QRS complexes (15) It can be observed that the performance of both the classifiers are sufficiently high even when the training dataset is half the original size. It is also observed that on reducing the size of training dataset the degradation of classification performance for VFENNC is less in comparison to that for PSDFENNC. Thus VFENNC is less dependent on the size of training dataset than PSDFENNC. Even with one tenth of the original training dataset, average sensitivity for VFENNC is around 95%. ROC curves can be studied for any particular class of arrhythmia or for all the classes of arrhythmia. In the present work we studied the ROC performance for premature ventricular contraction (V) type of arrhythmia. Premature ventricular contraction (V) is the most common and frequent among all the arrhythmia and can occur in both, individuals with and without heart diseases. Ventricular contraction can sometimes be potentially life-threatening and it may require immediate medical attention. Hence, we analyze the performance of the two classifiers for the detection of ventricular contraction. Fig. 2 describes the ROC curves for both VFENNC and PSDFENNC for ECG beats of class ventricular contraction (V). From the ROC curves it can be observed that the VFENNC is more efficient than PSDFENNC. 6.4. Error-bar calculation Classification performance of a classifier expressed in terms of percentage of correct classification or sensitivity can many times be misleading. Because classifiers are sensitive to the training and test datasets used. With a small change in the training and test datasets, the performance of the classifier can alter. An efficient classifier’s performance is not only expected to be high but also to change as little as possible with a change in training and test datasets. Error-bar study gives information about how reliable is the classifier’s performance. For this, the classification exercise is run repeatedly with different choices of training and test datasets. However, the amount of data in training and test datasets is kept constant. Let Sei represents the sensitivity (in percentage) for a certain class of arrhythmia for the ith iteration. Then the estimated mean value of the sensitivity Sem for that class is given by Sem ¼ N 1X Se : N i¼1 i (16) Here N is the total number of iterations. The estimated standard deviation of the sensitivity Sesd is given by vffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi u N u1 X (17) ðSe  Sem Þ2 : Sesd ¼ t N i¼1 i Fig. 1. Classification performance for VFENNC and PSDFENNC for different reduction factor. In comparing the results, the mean value of performance Sem was plotted along with an error bar of width equal to the standard deviation Sesd . 120 A.K. Mishra, S. Raghav / Biomedical Signal Processing and Control 5 (2010) 114–123 Fig. 3. Error-bar of the classification performance for VFENNC and PSDFENNC. The error-bar plots of VFENNC and PSDFENNC are presented in Fig. 3. Both in terms of the absolute performance and the deviation from the mean value observed from the error-bar plots, VFENNC is better than PSDFENNC. 6.5. Patient-independent classifier performance In the current study, we have observed that the fractal features for a particular ECG arrhythmia beat across different patients do not vary much and classifier may perform well without being provided with any patient-specific information before classification. Hence, the FDNN classifier has been tested under conditions where the training dataset contains no signal from the patients being tested for arrhythmia classification. As it has been observed from the above results and discussions that the performance of VFENNC is better than PSDFENNC, in this section we only use VFENNC. These results have been compared to those of the simple template matching classifier. In simple template matching classifier (STMC) the ECG samples are considered without finding their local fractional dimensions and the testing is done by finding the minimum Euclidean distance. It may be noted here that when tested with ECG from same set of patients in the training and test phase, the performance of STMC is comparable to that of VFENNC. Tables 6 and 7 give the performance of VFENNC and STMC, respectively in percentage of correct classification for each class of ECG beats. It can be observed from the tables that the sensitivity of each arrhythmia in all six cases for VFENNC is better than that for STMC. The average sensitivity of all arrhythmia types (i.e. P cc ) is given in Tables 6 and 7. The mean value of Pcc for all the six cases in case of VFENNC is found to be 88.64% and the same for STMC is found to be 38.21%. From Table 7, we also observe that sensitivity by STMC varies through a fairly large range, in the six classification exercises. Thus, we can say that the classification performance of STMC strongly depends upon the training dataset used in the classification test. However for VFENNC, sensitivity deviates little from the mean value. Hence, VFENNC proves to be a better patientindependent classifier than STMC. This indicates that for a particular arrhythmia there are some fractal features which are prominent among all the patients. 6.6. Clustering analysis In the current study we have used GSI to analyze the cluster-tocluster separability between different classes of arrhythmia. The matrix described in Table 8 gives the GSI between each pair of arrhythmia classes for FDNN classifier. The higher the GSI value, the more separable are the classes in the fractal domain. As most of the entries in the table are close to 1, it shows that all the different classes of arrhythmia under consideration in this study are separable in the fractal dimension domain. In order to study the interpatient cluster dispersion for the two classifiers, viz. FDNN and STMC, we have used BD. Bhattacharya distance between each pair of the patient in the same class is evaluated for both FDNN and STMC and these BDs are averaged for each class and shown in Fig. 4. The figure shows that BDs between patients in a certain class of arrhythmia for FDNN is smaller than that for STMC. From the clustering analysis it is observed that the FDNN classifier is capable of classifying the different arrhythmias from ECG signal and the classifier is fairly patient independent. Table 6 Performance of VFENNC (sensitivity in percentage) for patient-independent study. Exp. no. N L R PB V A Sensitivity I II III IV V VI Avg. 94.67 94.12 96.45 97.87 86.97 88.85 93.15 97.29 91.76 72.90 86.24 94.85 81.19 87.37 79.54 83.42 82.36 81.81 79.13 88.35 82.44 85.70 92.39 88.37 95.76 95.74 93.25 91.87 84.60 86.53 94.41 96.39 96.65 87.86 91.07 87.79 85.78 84.34 88.31 85.37 84.20 85.96 88.27 89.00 86.47 91.06 89.79 87.28 88.64 Table 7 Performance of STMC (sensitivity in percentage) for patient-independent study. Exp. no. N L R PB V A Sensitivity I II III IV V VI Avg. 67.19 74.70 99.01 99.97 94.96 40.47 79.38 22.28 01.09 02.22 00.55 02.17 02.06 05.66 01.11 00.35 02.04 30.45 02.43 21..51 09.65 00.02 84.18 03.62 15.17 82.80 61.28 41.18 61.54 60.60 91.51 65.07 13.09 35.64 54.58 58.48 15.38 01.23 51.43 21.15 88.76 39.41 35.10 39.38 33.27 43.77 36.10 41.62 38.21 A.K. Mishra, S. Raghav / Biomedical Signal Processing and Control 5 (2010) 114–123 Table 8 The GSI index between each arrhythmia class for FDNN classifier. 121 7. Limitations of the current study ECG classes N L R PB V A N L R PB V A 0 0.9915 0.9920 0.9912 0.9902 0.9845 0.9912 0 0.9858 0.9905 0.9825 0.9928 0.9908 0.9878 0 0.9928 0.9862 0.9922 0.9925 0.9915 0.9958 0 0.9920 0.9912 0.9894 0.9810 0.9850 0.9925 0 0.9905 0.9755 0.9915 0.9832 0.9902 0.9895 0 Table 9 Performance of VFENNC (sensitivity in percentage) for different level of white noise added in clean ECG. SNR (dB) N L R PB V A Sensitivity 24 18 12 6 0 98.92 98.29 90.09 64.14 42.12 97.36 96.53 84.44 54.49 32.67 97.91 96.29 83.46 57.23 36.00 98.97 98.34 91.25 70.01 54.09 94.06 93.50 90.42 77.23 65.16 84.42 83.60 69.81 35.46 16.87 95.27 94.42 84.91 59.76 41.15 6.7. Noise analysis A classifier or an arrhythmia analysis program, which usually performs well with clean ECG signal, may give errors while performing on a noisy real-time ECG database. Noise is usually one of the main causes of false beat classification for most of the realtime algorithms. A practical ECG signal classifier is expected to perform well even under noisy situations. For the validation of performance of the proposed FDNN classifier over noisy ECG database, we added white Gaussian noise with different signal to portions of clean ECG records from the MIT-BIH database. The white noise is added to the test database of the classifier with different signal to noise ratio (SNRs) values one by one and the performance of the classifier is tested for each value of SNR. Table 9 presents the performance of FDNN classifier for each class under six different values of SNR in dB. It shows that the sensitivity for each class is fairly good even for low values of SNR (i.e., when noise power is relatively larger than signal power). Also the classifier gives 62.8% average percentage of classification at 6 dB SNR (i.e., noise power is one-fourth of the power of the signal). The results show that the FDNN classifier works well given noisy ECG signals. Implementing filters and after processing of real-time ECG signals, FDNN classifier will give better results even under considerate level of noise. Fig. 4. Average Bhattacharya distances among patients belonging to same class for VFENNC and STMC. In this section we discuss some of the limitations of the current study and implications of the same. The first limitation of the study is the dependence on MIT-BIH dataset. All the algorithms in the current work have been validated using the MIT-BIH ECG dataset. The ECG signals in this dataset are preprocessed. Hence, the algorithm as such cannot be ported to a real-life system or Holter. However, the current work is the study of a new classifier for ECG based arrhythmia classification. Practical implementation of the same will need some more fine-tuning and testing with different datasets. In the current study we have chosen the beat size so as not to include P-wave in the analysis. Because, P-wave being feeble in nature will be difficult to be captured by fractal analysis. By this limitation, P-wave based detection of left bundle branch block (LBBB) is not possible using the current classifier. However, this can be implemented by a preprocessing block. The proposed classifiers in this study use Euclidean distance biased by the RR-interval. However to keep the complexity low, the RR-interval used is not patient-specific. This is the second limitation of the work. However, even with this limitation the classifier gives good performance and the performance is better than using simple Euclidean distance. Lastly, the complexity of the complete classification algorithm, based on local fractal dimension based nearest neighbor approach, is high. However, with current generation of computing devices, this is not a major limitation, given the good performance of the classification algorithm against all the figures of merit. For example using a Pentium 3 machine it takes around 10 s to classify 1 min of ECG beats. 8. Conclusions We have developed a local fractal dimension based nearest neighbor algorithm for the classification of ECG arrhythmia. The algorithm estimates the local fractal dimensions of ECG signals and uses them as features. The final classification is done based on a nearest neighbor approach. To find the nearest neighbor the algorithm uses a modified Euclidean distance taking into account the RR-interval information, termed as RR-biased Euclidean distance. By this, a substantial increase in performance is observed for arrhythmia like atrial fibrillation and premature ventricular contraction. We have considered five different arrhythmia and normal ECG beats, with a total database of 10,6949 ECG sample beats. Thus, the database includes a wide class of ECG waveforms of different potential patients. Two algorithms have been used for estimating the local fractal dimension, viz. PSDFE and VFE. It was observed that the FDNN classifier’s performance is optimal when the LFD is estimated using a sliding window of size 30 samples. The classifier avoids complicated computations by applying estimations over the samples around the QRS waves rather than comparing all P–QRS–T waves. FDNN classifier does not need to normalize the ECG beats before using them for classification purpose. Because, linear operations on a signal does not change its fractal dimension [15]. Based on how the LFD is estimated, two FDNN classifiers have been proposed, viz. PSDFENNC and VFENNC. The performance of these two classifiers was analyzed on the basis of different figures of merit. The performance of VFENNC for individual arrhythmia came quite high with sensitivity of 98.92% for normal beats, 97.36% for L and 97.91%, 98.97%, 94.06%, and 86.42% for R, PB, V, and A, respectively. The false positive cases were also very low with an average specificity of 99.4%. These figures are comparable to some of the best performances found in the open literature [11], and is better than the results presented in many other works [44,45]. 122 A.K. Mishra, S. Raghav / Biomedical Signal Processing and Control 5 (2010) 114–123 An important advantage of this work is the high performance of the algorithms when tested with ECG waveforms of different patients. For this, six cases were considered where the patients whose ECG recordings were there in the test database were different from the patients whose ECG recordings were there in the training database. The proposed classifier gave 88.64% of average sensitivity for those six cases with the individual performance of 93.15% for normal beats and 91.07% for V arrhythmia. The results obtained were much better than those using simple template matching classifier which gave an overall average sensitivity of 38.21%. The overall good recognition results, optimistic error-bar characteristics, immunity to reduction in training dataset, and a good performance independent and invariant to the patient shows the potentialities of LFDNN classification algorithms. Acknowledgement The authors acknowledge the extensive amount of helpful comments given by one of the anonymous reviewers. Appendix A See Figs. A.1 and A.2. Fig. A.1. The QRS complexes for normal and PVC class and their corresponding fractal dimension series calculated by VFENNC and PSDFENNC algorithms. Fig. A.2. The QRS complexes for each class of arrhythmia and their corresponding fractal dimension series calculated by VFENNC algorithm. A.K. Mishra, S. Raghav / Biomedical Signal Processing and Control 5 (2010) 114–123 References [1] R. Archarya, N. Kannathal, S. Krishnan, Comprehensive analysis of cardiac health using heart rate signals, Physiological Measurement (25) (2004) 1139– 1151. [2] R. Povinelli, F. Roberts, R.K. Pella, Identification of ECG arrhythmias using phase space reconstruction, PKDD01, Freiburg, Germany, 2001, pp. 411–423. [3] L. Khadra, A. Al-Fahoum, S. Binajjaj, A quantitative analysis approach for cardiac arrhythmia classification using higher order spectral techniques, IEEE Transactions on Biomedical Engineering (45) (2005) 1878–1885. [4] P.S. Addison, J.N. Watson, G.R. Clegg, M. Holzer, F. Sterz, C.E. Roberstson, Evaluating arrhythmias in ECG signals using wavelet transforms, IEEE Engineering in Medicine and Biology (2000) 104–109. [5] V. Afonso, W. Tompkins, Detecting ventricular fibrillation, IEEE Engineering in Medicine and Biology (14) (1995) 152–159. [6] L. Khadra, A.S. Al-Fahoum, H. Al-Nashash, Detection of life-threatening cardiac arrhythmias using the wavelet transformation, Medical & Biological Engineering & Computing 35 (1997) 626–632. [7] I. Guler, E.D. Übeyli, ECG beat classifier designed by combined neural network, Pattern Recognition 38 (2) (2005) 199–208. [8] M. Engin, ECG beat classification using neuro-fuzzy network, Pattern Recognition Letters 25 (15) (2004) 1715–1722. [9] D.A. Coast, R.M. Stern, G.G. Cano, S.A. Briller, An approach to cardiac arrhythmia analysis using hidden Markov models, IEEE Transactions on Biomedical Engineering 37 (1990) 826–836. [10] J. Nadal, R.B. Panerai, Classification of cardiac arrhythmias using principal component analysis of the ECG, in: Annual International Conference of IEEE Eng. in Med. and Biology Society, vol. 13 (2), 1991, 580–581. [11] S.N. Yu, K.T. Chou, A switchable scheme for ECG beat classification based on independent component analysis, Expert Systems with Application 33 (2007) 824–829. [12] R.D. Throne, J.M. Jenkins, S.A. Winston, L.A. DiCarlo, A comparison of four new time-domain techniques for discriminating nonmorphic ventricular tachycardia from sinus rhythm using ventricular waveform morphology, IEEE Transactions on Biomedical Engineering 38 (1991) 561–570. [13] V. Krasteva, I. Jekova, QRS template matching for recognition of ventricular ectopic beats, Annals of Biomedical Engineering 35 (12) (2007) 2065– 2076. [14] B.B. Mandelbrot, The Fractal Geometry of Nature, Freeman, CA, 1983. [15] A.P. Pentland, Fractal based description of natural scenes, IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-6 6 (1984) 661–674. [16] E. Bayraktar, V. Poor, R. Sircar, Estimating the fractal dimension of the sp 500 index using wavelet analysis, International Journal of Theoretical and Applied Finance 7 (5) (2004) 615–643. [17] L.M. Kaplan, Extended fractal analysis of texture classification and segmentation, IEEE Transactions on Image Processing 8 (11) (1999) 1572–1585. [18] E.E. Peters, Fractal Market Analysis, John Wiley and Sons, 1994. [19] Y.X. Tian, C. Chen, X.Y. Zou, P.X. Cai, J.Y. Mo, Study on fractal characteristics of the coding sequence in DNA, Chinese Journal of Chemistry 24 (3) (2006) 423–429. [20] J.B. Bassingthwaighte, L.S. Liebovitch, B.J. West, Fractal Physiology, Oxford University Press, New York, 1994. [21] B.J. West, R. Zhang, A.W. Sanders, S. Miniyar, J.H. Zuckerman, B.D. Levine, Fractal fluctuations in cardiac time series, Physica A 270 (1999) 309–324. [22] P.Y. Muller, N. Contento, H. Rix, Fractal dimension on ECG, Engineering in Medicine and Biology Society 14 (3) (1992) 977–978. 123 [23] K.T. Lai, K.L. Chan, Real-time classification of electrocardiogram based on fractal and correlation analyses, Engineering in Medicine and Biology Society 20 (1) (1998) 119–122. [24] A.N. Esgiar, P.K. Chakravorty, Electrocardiogram signal classification based on fractal features, Computers in Cardiology 31 (2004) 661–664. [25] P.C. Ivanov, L.A.N. Amaral, A.L. Goldberger, S. Havlin, M.G. Rosenblum, Z.R. Struzik, Multifractality in human heart beat dynamics, Nature 5 (1999) 399–461. [26] G. Wang, H. Huang, H. Xie, Z. Wang, X. Hu, Multifractal analysis of ventricular fibrillation and ventricular tachycardia, Medical Engineering and Physics 29 (2007) 375–379. [27] S. Raghav, A.K. Mishra, Fractal feature based ECG arrhythmia classification, in: Proceedings of IEEE TENCON 2008. [28] Y.H. Hu, S. Palreddy, W.J. Tompkins, A patient-adaptable ECG beat classifier using a mixture of experts approach, IEEE Transactions on Biomedical Engineering (9) (1997) 891–900. [29] R. Watrous, G. Towell, A patient adaptive neural network ECG patient monitoring algorithm, Computers in Cardiology (1995) 229–232. [30] J. Theiler, Estimating fractal dimension, Journal of the Optical Society of America A 7 (6) (1990) 1055–1073. [31] S. Spasic, Spectral and fractal analysis of biosignals and coloured noise, in: International Symposium on Intelligent systems and Informatics, 2007, 147–149. [32] B. James, G.M. Raymond, Evaluating rescaled range analysis for time series, Annals of Biomedical Engineering 22 (4) (1994) 432–444. [33] A. Block, W. Von Bloh, H.J. Schellnhuber, Efficient box-counting determination of generalized fractal dimensions, Physical Review A 42 (4) (1990) 1869–1874. [34] T. Higuchi, Approach to an irregular time series on the basis of the fractal theory, Physics D31 (1988) 277–283. [35] Z. Wang, D. Guo, X. Li, Y. Fei, Estimating Hurst exponent with wavelet packet, Computer-Aided Industrial Design and Conceptual Design, 2006. CAIDCD’06. 7th International Conference on (2006) 1–4 [36] W. Kinsner, Batch and real-time computation of a fractal dimension based on variance of a time series, Technical Report, DEL 94-6. [37] MIT-BIH Arrhythmia Database, http://www.physionet.ph.biu.ac.il/physiobank/ database/mitdb/. [38] A.K. Mishra, Separability indices and their use in radar signal based target recognition, IEICE Electronics Express 6 (14) (2009) 1000–1005. [39] C. Thornton, Separability is a learner’s best friend, in: Proceedings of the Fourth Neural Computation and Psychology Workshop: Connectionist Representations, 2008, pp. 40–47. [40] C. Scheler, R. Pfelfer, Y. Kunyloshi, Embedded neural networks: exploiting constraints, Neural Networks 11 (7–8) (1998) 1551–1569. [41] G. Anthony, H. Ruther, Comparison of feature selection techniques for SVM classification, in: International Symposium on Physical Measurement and Signature in Remote sensing, ISPMSRS, 2007. [42] K. Fukunaga, Introduction to Statistical Pattern Recognition, Academic Press, 1990. [43] M. Rahman, P. Bhattacharya, B. Desai, Similarity searching in image retrieval with statistical distance measures and supervised learning, Lecture Notes in Computer Science 3686/2005 (2005) 315–324. [44] G.K. Prasad, J.S. Sahambi, Classification of ECG arrhythmias using multi-resolution analysis and neural networks, TENCON 2003. Conference on Convergent Technologies for Asia-Pacific Region 1. [45] K. Minami, H. Nakajima, T. Toyoshima, Real-time discrimination of ventricular tachyarrhythmia with Fourier-transform neural network, IEEE Transactions on Biomedical Engineering 46 (2) (1999) 179–185.