Preprocessing Method for Improving Ecg Signal Classification and Compression Validation

PHYSCON 2009, Catania, Italy, September, 1–September, 4 2009 PREPROCESSING METHOD FOR IMPROVING ECG SIGNAL CLASSIFICATION AND COMPRESSION VALIDATION Liviu Goras Monica Fira 1. Faculty of Electronics, Telecommunications and Information Technology Institute for Computer Science Gh. Asachi Technical University of Iasi Romanian Academy, Iasi Branch 2. Institute for Computer Science Romania Romanian Academy, Iasi Branch [email protected] Romania [email protected] Abstract ing long-term recording waves, improvements of au- A method for improving electrocardiogram (ECG) tomated classification results are of significant interest signal classification in time domain is presented. The [Nyongesa, 2004; Graja, Boucher 2005; Jekova, 2000; main idea is to preprocess the segmented waveforms in Christov, Jekova, Bortolan, 2005]. order to obtain an alignment of the ECG with respect After data segmentation, ECG heartbeat classification to the maximum value of the R beat while keeping the consists in using a comparison method to decide the information on its initial position as a feature. class in which a heartbeat most probably belongs. No We propose two simple preprocessing methods basi- matter if artificial neural networks (ANN’s), support cally consisting in the alignment of the R-waves either vector machines (SVM), distance based methods etc. by translation or by a slight nonlinear time scaling. It is are used, either in the time domain or in the feature shown that the methods significantly improve the clas- space, it is obviously important that similar waveform sification rates obtained with two independent meth- be classified in the same class. In all cases classifica- ods, one using a MLP artificial neural network and the tion is related more or less to the concept of distance; other one based on the k-nearest neighbor (k-NN). distances between signals belonging to the same class These techniques are also used to improve the valida- are generally smaller than distances between signals tion of ECG compression by comparing the classifica- belonging to different classes. (This statement is dis- tion results obtained with original patterns and with re- cussible for signals belonging to different classes but constructed ones, a higher classification rate in the for- close to the delimitation zone between classes.) mer case reflecting better compression results. The simplest way to segment ECG signals consists in taking samples between the middles of two successive RR periods so that the R wave will be placed some- Key words where about the middle of the signal support. The ECG, alignment, compression validation waveforms obtained in this way can be normalized to a constant number of samples (through interpolation, filtering and down sampling) to eliminate the influence 1 Introduction of heart rate variability and to be easily compared using ECG signal classification is an important issue in for instance the L2 norm, neural networks, etc. Such a clinical monitoring and has been thoroughly studied technique has been used in [Fira, Goras, 2008] to vali- [Wei Jiang Kong, Peterson, 2005; AS Al-Fahoum, Qa- date the efficiency of a new compression method. saimeh, 2006; Addison et all, 2002; Povinelli et all, In this paper we propose two simple preprocessing 2006; Roberts,Povinelli,Ropella, 2003]. The process methods basically consisting in the alignment of the involves extraction of attributes from ECG waveforms R-waves either by translation or by a slight nonlinear and subsequent comparisons with patterns characteris- time scaling. It is shown that the methods significantly tic to known diseases. improve the classification rates obtained with two in- Even though much progress has been achieved in this dependent methods, one using a MLP artificial neural area, it is unanimously agreed that the ultimate ver- network and the other one based on the k-nearest neigh- dict concerning the correctness of the results falls bor (k-NN). The above mentioned techniques are also under de competence of the cardiologist physician. used to improve the validation of ECG compression by However, since recognizing of deviation in the ECG comparing the classification results obtained with orig- trace is tedious and time-consuming when investigat- inal patterns and with reconstructed ones, a higher clas- sification rate in the former case reflecting better com- pression results. 2 Materials and methods We start from the simple observation that, even after normalization to the same number of samples, the posi- tion of the R wave peaks for various frames containing normal or pathological beats generally does coincide neither as position nor as amplitude. In a standard nor- mal beat the R wave has a peak about three times higher than any other maxima in the heart-beat. Even though Figure 2. Stylized R-beats with different amplitudes and positions the duration of the R beat is about 5% of the waveform with details at another temporal scale support, due to its high amplitude the weight in the dis- tance of the R wave contribution is significantly impor- tant. Thus, even though two or more waveforms are visually similar (figure 1), the distances between waves which corresponds to the case when the sup- them might be high due to the un-alignment of the R port of the triangles bases are disjoint (which happens waves. for values of a higher √ than 0.55 or less than 0.45) is where 1.825 = 1.291 2, a significant value, is the norm (”length”) of each triangle. We have studied two R wave alignment techniques. 2.1 First method (R-wave centering through shift- ing) The first and the simplest one consist in shifting the patterns to the left or to the right so that the R waves are placed just in the middle of the waveform inter- val. After shifting, the samples that leave out the in- terval at one end are discarded and the missing sam- ples at the other end are replaced with the (same) right- most/leftmost known value. Figure 1. Superposed segmented and time normalized similar To make an image on the contribution in the dis- waveforms showing R-waves un-alignment tance between two waveforms coming only from the un-alignment of the R waves we will consider first the ”stylized” R-waves described above. The distance be- tween the two waves shown in figure 3.a varies Thus the un-alignment of the R waves is a factor that with a and A1 for A = 1 and constant d = 2.5 as shown might somehow artificially increase the distance be- in figure 3.b. Obviously, the distance between the tween similar segmented waveforms when compared two functions vanishes for A1 = A and a = 1/2. Note in the time domain by using the Euclidian distance, √ that the previously mentioned value 1.825 = 1.291 2 ANN’s or other techniques. The main idea of this paper for the distance between two non-overlapping equal tri- is based on the finally fully confirmed conjecture that angles can be found in (figure 3.b) for A1 = A = aligning ECG waveforms with respect to the R wave 1 and a>0.55 or a<0.45. will increase the time domain techniques classification Coming back to real heartbeats, the distance between rate. the two real R-waves selected between the two dot- To make an image on the contribution in the distance ted lines in figure 1 is 1.676 while the distance be- between two beats coming from the un-alignment of tween the whole waves is 1.737. A typical value for the R waves we have considered as a ”toy” example two the distance between two beats with completely non- (highly) ”stylized” R beats assimilated for simplicity overlapping R waves is 2. with two isosceles triangles with the same basis width 2d and different heights A, A1 placed at different ab- scissas T/2 and aT respectively (a>T/2) as shown in 2.2 Second method (R-wave centering through figure 2. shrinking/stretching) Considering a value of d (figure 2) equal to 2.5 for The second method consists in using a nonlinear time a waveform with a normalized duration of 100 units scaling to make the R waves coincide. An intuitive way (such that 2d represents 5% of the wave duration) and to describe the method is the following. Imagine that a maximum amplitude equal to unity for both triangles the waveform already normalized to a specified dura- (A=A1=1), the maximum L2 distance between the two tion T = 100 is drawn on an elastic sheet with width T  Figure 4. Dependence on a and A1 of the distance between trian- gles after alignment The above consideration show that the un-alignment of the R waves is a significant factor that affects the dis- tance between ECG signals - a fact that has been fully confirmed through simulations with real waveforms as shown below. 2.3 ECG preprocessing Figure 3. A. Alignment of triangle A1 with A (centered) B. Dis- The ECG signals used to illustrate the proposed tance between the two triangles as a function of A1 and a (A=1, method were taken from the MIT-BIH Arrhythmia d=2.5) database and consisted in ECG signals digitized through sampling at 360 samples/s, quantized and en- coded with 11 bits. The segmentation was done by and fastened lateral margins. Suppose that the wave- taking as heartbeats the waveforms between the mid- form has the R peak placed to the right of T/2. Let dles of adjacent RR intervals. Since the segmented out- us further imagine a rigid vertical line passing through put patterns had different dimensions, each pattern was the R wave peak fastened with the sheet. Now move the resampled to 100 samples by introducing extra sam- line to the left until its abscissa reaches T/2 thus slightly ples through linear interpolation, filtering with a low- shrinking/stretching the left/right part of the waveform. pass FIR filter with 90Hz cutoff frequency followed by In this way any waveform can be processed such that decimation to 100 samples per pattern - a value which the peak has an abscissa of T/2. Moreover, the wave- proved high enough to preserve the initial waveform. forms can be vertically (linearly) scaled as well to a The simulations used three classes of waveforms. The normalized value of the peak equal to unity. first class, denoted by I (initial) consisted of the above To make an image on how close the two ”stylized” described resampled patterns which were used for clas- R-waves can get using the above procedure we have sification with no extra processing. The second class, suggested in figure 3.a the aligning mechanism denoted by S (shifted) was obtained from the first one and sketched in figure 4 the dependence of the dis- by shifting the pattern until the R wave reached T/2, tance between the two triangles on a and A1. We only discarding samples that left out the interval at one end mention that if the A1 triangle is translated and de- and replacing the missing samples at the other end with formed until the abscissa of its peak reaches the value the last known value. The last category, denoted by T/2, the abscissas of its bases become T/2-d/(2a) and S/S (stretch/shrink) was obtained from the first one T/d+d(2(1-a)). Let us note that, in this case, the A1 through resampling the patterns with 50 samples on triangle is no more isosceles: in our example its left each side of the R wave which is equivalent to a lin- part has been slightly shrunk while it left part slightly ear stretching/shrinking of the two sides of the pattern stretched. This is why the distance between the two tri- when the R wave was not in the middle of the interval. angles vanishes only in the trivial case when A1 = A = Since the information about the period variability is 1 and a = 1/2. For any other value of a, even with a ver- surely a non-negligible aspect and should not be dis- tical scaling, the distance between the triangles will be carded, it can always be displayed in association to the not exactly zero. However, as it will be shown next, this processed waveforms. Moreover, it has been used as a very second technique proved to be the most efficient in feature in the classification scheme using ANN’s as it preprocessing for improving classification. will be further shown. To make an image regarding the effect of the methods number of neighbors used to classify the new example used for centering the R wave, we show in figure 5, [Dasarathy, Belur, 1990]. several superposed patterns from the class ”right bun- Usually the metric is the Euclidean distance but other dle branch block beat”. options as the overlap metric (or Hamming distance) can be used as well [Shakhnarovish, Darrell, and Indyk, 2001]. The number of neighbors, k, should be enough large to minimize the probability of wrong classifica- tion and enough small so that the k neighbors are really within the class to provide a correct estimation. In our case the best results were obtained with k=1. 3 Results In order to verify the advantages of the proposed methods and to compare results, the two methods men- tioned above have been used. Basically, the aim was to show the classification improvements for the above two methods. It is expected that the method would im- prove the results of other classification techniques as well, with even better recognition rates. For the first method an ANN with a hidden layer con- taining 50 neurons has been trained with heartbeats from 8 classes (atrial premature beat, left bundle branch block beat, right bundle branch block beat, premature ventricular contraction, fusion of ventricular and nor- mal beat, paced beat, fusion of paced and normal beat) taken from 23 records of the MIT-BIH Arrhythmia database. For training the MLP network a back-propagation al- gorithm with gradient descent and cross-validation was used. From a total of 7500 patterns, 60% have been used for training, 20% for validation and 20% for test- ing. The patterns used in the three sets above were distinct. Figure 5. Patterns for the class right bundle branch block beat A. The records no. 100, 101, 103, 104, 106, 118, 119, type I, B. type S, C. type S/S 200, 201, 207, 210, 213, 214, 217, 219 were used for training and records no. 102, 105, 202, 203, 208, 209, 212, 215 for testing and validation. From these An ANN consists of an interconnected group of artifi- last records, the validation and testing sets have been cial neurons that processes information using a connec- obtained through a random selection mechanism, each tionist approach to computation. In most cases an ANN pattern being selected either in the testing set or in the is an adaptive system that changes its weights based on validation set but never in both of them. The error func- external or internal information that flows through the tion used was the mean square error and the stop crite- network during the learning phase [Haykin, 1998]. rion was the least error for the validation set. Compared to other methods, the MLP exhibits im- The ANN was trained with the patterns alone from the proved performances thus being widely used in car- classes I, S and S/S but also with patterns and features diac pattern classification for its ability to learn from (which were either the initial length of the heartbeat for examples and for its very good generalization capabil- class I or the initial lengths of the left and right sides of ity based on complex separation surfaces [Duda, 2001]. the heartbeat for classes S and S/S). Additional results The k-NN is another method for classifying objects in were obtained with patterns vertically scaled such that the feature space being one of the simplest machine they have the same peak value of the R waves. learning algorithms - an object is classified by a ma- Table 1 contains the results obtained with the MLP jority vote of its neighbors. The k-NN algorithm has without and with features for the three classes of pat- the advantage of not requiring information on the class terns (I, S and S/S) without and with vertical scaling. It statistics, it can be easily implemented and has a small can be observed that the classification results are bet- probability of error. ter for the S and S/S classes and further improve when The performances of the k-NN algorithm are influ- using features and vertical normalization. enced by tree main factors: type of metric used for lo- It is also apparent that using features for comparing calization of the nearest neighbors, decision rule and initial waveforms i.e., without centering and vertical  MLP without MLP with fication. However, we mention here De Chazal [De Chazal, O’Dwayer, Reilly, 2004] who reports a clas- features features sification accuracy of 97.4% for 5 classes (with a to- No vertical No vertical tal of 15 pathologies) while Prasad [Krishna Prasad, Sahambi, Reilly, 2003] and Osowski [Osowski, Hoai, scaling scaling scaling scaling Markiewicz, 2004] using wavelets and SVM’s respec- (I) 90.9 91.4 90.4* 90.7* tively for 13 classes, report 96%. (S) 91.7 92 93.23** 94.41** 3.1 Compression validation (S / S) 92.8 93.1 94.9** 95.3** In the following we make several comments regarding the possibility of using the classification rate for recon- Table 1. Results obtained with the MLP for the three classes of structed signals to validate the quality of ECG com- patterns (I, S and S/S) derived from original records of MIT BIH pressed signals. Arrhythmia database. Features: * initial length of the pattern, ** Indeed, the definition of the error criterion to appre- initial lengths of the left and right sides of the pattern. ciate the distortion of the reconstructed and original signal is of paramount importance for lossy compres- sion techniques. For biomedical signals like the elec- scaling gives worse results. Thus the extra informa- trocardiogram (ECG), a slight loss or modification of tion contained in the initial length of the pattern is ir- information can lead to wrong diagnostics. Therefore, relevant for comparing waveforms if no other process- the measurement of these distortions is a very sensi- ing has been used. On the other side, the classification tive problem only partially solved for biomedical sig- rate increased in the S/S case with vertical scaling with nals. In most ECG compression algorithms, the per- 4.4% compared to the un-processed situation (with or centage root-mean-square difference (PRD) measure or without features but with no vertical scaling). normalization PRD, the root mean square error (RMS) Besides the ANN based classification, we have also and the signal to noise ratio (SNR) are used. In order to used the k-NN algorithm for patterns, this time with- evaluate the relative preservation of the diagnostic in- out features since the principle of the method is based formation in the reconstructed signal compared to the solely on the concept of distance. The best results original one, Zigel [Zigel, Cohen, Katz, 2000] intro- were obtained considering only the first neighbor and duced a new measure, not always easy to use, called are presented in table 2. Since we have used the Weighted Diagnostic Distortion (WDD), which con- same database for both classification techniques, the sists in comparing the P and T wave, and QRS com- results can be relevantly compared, both showing sig- plexes features of the ECG signals. nificant improvements when the preprocessing method Taking into account the need for relevant errors mea- has been used. sures for the biomedical signal compression, but also that these measures should be easily calculated, we suggest that the classification error of reconstructed k-NN signals can be used as a distortion measure of the com- No vertical scaling vertical scaling pression method, i.e., a higher classification rate of the reconstructed signals reflects a higher quality compres- (I) 93.36 93.84 sion. (S) 94.48 93.68 Based on the above considerations on preprocess- ing, we have tested the validation of the compression (S/S) 95.60 95.76 method proposed in [Fira, Goras, 2008] by comparing the classification results of a MLP trained with original Table 2. Results obtained with the K-NN algorithm for the three waveforms and then with reconstructed ones. Using the classes of patterns (I, S and S/S) derived from original records of procedures presented above the following results have MIT BIH Arrhythmia database been obtained. The results in table 3 show that using features al- ways improve the classification rate while vertical scal- It is apparent that in case of k-NN classification using ing comes with little improvement (with an exception patterns with vertical scaling the results are better than for class S when using features plus vertical scaling those obtained using ANN, reaching 95.76% accuracy gives slightly weaker results). These results show that for the (S/S) segmentation method. the suggested method for compression validation can Since the number of papers dealing with classification be improved using the proposed preprocessing tech- of many classes is, to our knowledge, relatively small, nique. The classification results using k-NN methods it is rather difficult to make a comparison with other having the original waveforms as known patterns and results (most authors classify only 2-3 types of car- the reconstructed ones as patterns to be classified are diac pathologies) - the aim of the results presented here presented in table 4. being that of showing the improvement of the classi- We remark that, in most cases the results are better  MLP without MLP with Al-Fahoum, A.S. and Qasaimeh, A.M., (2002) ECG Arrhythmia Classification Using Simple Recon- features features structed Phase Space Approach. Comp. Cardio, 33, No vertical No vertical pp.757 Addison P.S., Watson J.N., Clegg G.R., Holzer M., scaling scaling scaling scaling Sterz F., Robertson C.E. (2000) Evaluating arrhyth- (I) 78.2 81 83.5* 85.6* mias in ECG signals using wavelet transforms. EMB Magazine 2000, September/October, pp.104. (S) 84.7 86.5 89.89** 89.29** Povinelli R., Johnson M., Lindgren A., Roberts (S/S) 86.4 88.9 90.05** 90.54** F. and Ye J. (2006) Statistical Models of Re- constructed Phase Space for signal classification. Table 3. Results obtained with the MLP for the three classes of IEEE Trans. Signal. Proc., 54, pp.2178. reconstructed patterns (I, S and S/S) Roberts F., Povinelli R. and Ropella K. (2003) Rhythm classification using reconstructed phase space of sig- nal frequency sub-bands. Comp. Cardio., 30, pp.61. k-NN Nyongesa, H., (2004) Classification Of ECG By Auto-Regressive Modelling And Neural Networks. No vertical scaling vertical scaling IEEE AFRICON 2004,pp. 841. (I) 77.71 79.30 Graja S. and Boucher J. M. (2004) SVM Classification of patients prone to atrial fibrillation. WISP 2005. (S) 90.80 90.39 Jekova, I., (2000) Comparison of five algorithms for the (S/S) 93.16 93.98 detection of ventricular fibrillation from the surface ECG. Physiol. Measur., 21, pp. 429–439. Table 4. Results obtained with the KNN algorithm for the three Christov I., Jekova I. and Bortolan G., (2005) Pre- classes of reconstructed patterns (I, S and S/S) mature ventricular contraction classification by the Kth nearest-neighbours rule. Physiol. Measur., 26, pp. 123-130. than those obtained with ANN, reaching a maximum Fira, M. ,Goras, L., (2008) An ECG signals com- of 93.98% for the (S/S) segmentation method. pression method and its validation using NN’s. IEEE Trans. Biomed. Eng., 45, pp. 1319-1326. Haykin, S., (1998). Neural Networks: A Comprehen- 4 Conclusion sive Foundation. Prentice-Hall. New York. We have presented an improved method for electro- Duda, R.O., Hart, P.E., Stork, D.G., (2001). Pattern cardiogram (ECG) signal classification in time domain classification (2nd edition). Wiley. New York. which takes into consideration the heart rate variability. Dasarathy, Belur V., (1990). Nearest neighbor (NN) By preprocessing the waveforms in order to obtain an norms: NN pattern classification techniques. IEEE ”alignment” of the R beats it has been shown that the Computer Society Press. Los Alamitos. classification results have been significantly improved Shakhnarovish, Darrell, and Indyk, (2001). Nearest- for both tested methods (ANN and k-NN) and are ex- Neighbor Methods in Learning and Vision. The MIT pected to improve for other classification techniques as Press. well. P. De Chazal, M. O’Dwayer, R. B. Reilly, (2004) A major advantage of the proposed method based on Automatic Classification of Heartbeats Using cardiac beat alignment consists in a reduced computa- ECG Morphology and Heartbeat Interval Features. tional complexity and robustness. Last but not least, IEEE Trans. Biomed. Eng., 51, pp. 1196- 1206. considering the results obtained for reconstructed sig- G. Krishna Prasad, J. S. Sahambi,, (2003) Classifi- nals after compression, the method can be used for cation of ECG Arrhythmias using Multi Resolution compression validation as well. Analysis and Neural Network. Proc. TENCON. S. Osowski, L. T. Hoai, T. Markiewicz, (2004) Sup- port Vector Machine based expert system for reliable Acknowledgements heartbeat recognition. IEEE Trans. Biomed. Eng., 51, This paper was supported by the National University pp.582. Research Council under Grant PN2 - 648/19.01.2009, Zigel Y., Cohen A., Katz A., (2000) The Weighted PNCDI II - PC - no.12115/01.10.2008 and PNCDI II - Diagnostic Distortion (WDD) Measure for ECG Bilateral project no. 117/10.10.2008 Signal Compression. IEEE Trans. Biomed. Eng., 47, pp.1422. References Wei Jiang Kong, S.G., Peterson,G.D., (2005) ECG sig- nal classification using block-based neural networks. Proc. IJCNN, pp. 326