Messrs This is to certify that the thesis entitled ECGONLINE: A DISTRIBUTED ECG ANALYZER WITH JAVA IMPLEMENTATION presented by Zhiwen Zou has been accepted towards fulfillment of the requirements for Master's degree in Computer Science & Engineering Major professor Date W42]; 2009‘ 0-7639 MS U is an Affirmative Action/Equal Opportunity Institution "G Q '- 4! a a 5: . ‘T‘Q ‘ 5 , i. t} t" ,i ii 5 “ 5-“ ~ . l. m ‘. {1, H K LlBRARY Michigan State University PLACE IN RETURN Box to remove this checkout from your record. To AVOID FINES return on or before date due. MAY BE RECALLED with earlier due date if requested. DATE DUE DATE DUE DATE DUE 6/01 c-JCIRC/DateDuepSS-pJS ECGOnline: A DISTRIBUTED ECG ANALYZER WITH JAVA IMPLEMENTATION By Zhiwen Zou A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of MASTER OF SCIENCE Department of Computer Science and Engineering 2002 ABSTRACT ECGOnline: A DISTRIBUTED ECG ANALYZER WITH JAVA IMPLEMENTATION By Zhiwen Zou This study designs and implements a distributed electrocardiogram (ECG) analyzer (“ECGOnline”) for academic use. The analyzer consists of the client and server programs. The client, with a graphic user interface, performs I/O operations, filters ECG signals, extracts ECG features, and displays ECG diagrams, features, and classification results. Four groups of ECG features - amplitudes, durations, slopes, and areas - are extracted. The server runs an adaptive weighted k nearest neighbors (AWKNN) algorithm, which was modified from the k nearest neighbors (KNN) algorithm by this study, to classify an unknown ECG by comparing its features to those of the stored training samples, and reports the results to the client. The analyzer is designed to read the II-lead ECG signals and classify them as normal or abnormal. It is implemented using the Java programming language. The test results show that the AWKNN classifier improves the traditional KNN classifier for ECG interpretation from 72.7% to 76.5% in accuracy. The addition of the slope and area features to the classic amplitude and duration features improves the performance of the analyzer from 72.5% to 76.5%. It was found that the normal ECG’s are more clustered than the abnormal ECG’s in the 34D feature space defined in this study. ACKNOWLEDGENIENTS I am grateful to all the people who helped me complete this thesis. I would particularly like to thank Professor Min Pei for his significant help, from conceptualization, literature review, to algorithm design. He was always happy to answer my questions. I could reach him from office to home. I also want to thank my advisor, Professor Erik Goodman, for his invaluable advice on writing this thesis. He read every word I wrote in this thesis and made very helpful comments, which at times made me embarrassed for my sloppy work. I would like to thank my fellow student, Zhijian Huang, for his generous help. He shared his research with me and patiently answered my questions. He also helped me get the ECG records for testing. My thanks also go to Linda Moore, who helped with the administration of my thesis research. iii TABLE OF CONTENTS LIST OF TABLES ............................................................................ vi LIST OF FIGURES .......................................................................... vii 1. INTRODUCTION ........................................................................... l 2. LITERATURE REVIEW .................................................................. 3 2.1 QRS Detection ......................................................................... 3 2.2 Computerized ECG Interpretation ................................................... 4 2.3 The K Nearest Neighbors Algorithm ............................................... 10 3. ALGORITHM DESIGN .................................................................. 12 3.1 ECG Feature Extraction ........................................................... 13 3.2 ECG Classification: Adaptive Weighted KNN ............................... 20 4. IMPLEMENTATION OF ECGOnline ................................................ 26 4.1 A Distributed Application ........................................................ 26 4.2 The Client .......................................................................... 27 4.3 The Server .......................................................................... 31 5. TRAINING, TESTING, AND RESULTS ............................................ 33 5.1 Training and Testing ............................................................. 33 5.2 Performance and Limitations of the Classifiers .............................. 36 5.3 Effects of Feature Parameters .................................................. 39 5.4 Conclusions and Future Directions ........................................... 41 BIBLIOGRAPHY ............................................................................ 43 iv TABLE OF CONTENTS ATTACHIVIENT A floppy disk containing the program code in Java LIST OF TABLES Table l. AWKNN Training Results for Five Different Training Sets .............. 34 Table 2. Comparison of the performance of two classifiers in five tests. . . . . . . 36 Table 3. Distributions of the distances between ECG’s ................................ 37 Table 4. Performance of AWKNN using a single group of parameters. ............. 40 Table 5. Performance of AWKNN using combined groups of feature parameters .................................................................................... 41 vi LIST OF FIGURES Figure 1. Stages in the statistical pattern recognition approach ........................ 5 Figure 2. Stages in the syntactic approach ................................................. 7 Figure 3. An ECG signal and its parameters ........................................... 12 Figure 4. An example of QRS detection using the Okada algorithm................. 14 Figure 5. The left diagram shows an ECG that changes the sign of its slope at the Q point. The right diagram shows one in which the slope does not change sign at Q. .................................................................................... 16 Figure 6. Area of an ECG wave .......................................................... 20 Figure 7. Java RM] mechanism ........................................................... 26 Figure 8. The MVC architecture .......................................................... 27 Figure 9. The graphic user interface of ECGOnline .................................. 29 Figure 10. K values vs. performance ..................................................... 35 Figure 11. Distribution of normal and abnormal ECG’s in the feature space...... 37 vii 1. INTRODUCTION Computerized electrocardiogram (ECG) interpretation techniques were initially developed and used on mainframe computers in the early 19603 [T om95]. In those days, mainframe computers centrally located in computer centers performed the ECG analysis. The ECG’s were transmitted to the computer from remote hospital sites. As technology evolved, minicomputers located within hospitals took over the role of the remote mainframes. Nowadays the automated ECG analyzers are run on stand-alone microprocessor-based machines. The complete process of signal acquisition and analysis can be done at the patient’s bedside. The commercial automated ECG analysis systems are designed for hospital use. They are expensive and may not be suitable for academic and research purposes. The objective of this thesis project is to develop a research tool for ECG analysis. The emergence of the Internet has opened new possibilities for computerized ECG analysis. The Internet provides an excellent communication channel for computer systems. Taking advantage of the Internet, the ECG analyzer for this project is designed as a distributed client/server application, called ECGOnline. It is designed to read and analyze only the II-lead signal. It classifies an ECG signal as normal or abnormal. The client and the server programs share the work of ECG analysis. The client program runs the feature extraction process, whereas the server program does the ECG classification task. This system has two main advantages: 1) It is fairly scalable. More functions can be added to the server without significantly increasing the complexity of the client. For example, a library of digital filters can be implemented in the server program as remote methods. The clients can call these methods any time they want. 2) Multiple users can access the server simultaneously. There are, however, also some tradeoffs to be made. The users need to access the Internet to run the classification algorithms and other operations that are implemented in the server program. There is also the network overhead associated with these remote operations because the data are passed back and forth between the client and the server programs. ECGOnline is implemented using the Java programming language. Several characteristics make Java a better choice for this project than other programming languages such as C. First, Java is platform independent. This means that applications written in Java can run in all machines. Second, Java is object oriented. In Java almost everything is an object. Many objects (classes) and methods are already built and available for use. The programmer does not need to develop everything from scratch. Third, Java Remote Method Invocation (RMI) technology, specifically devel0ped for distributed programs, is available for this project. Thus in ECGOnline, the communication between the client and the server is implemented with RMI. This thesis contains four more chapters. Chapter 2 reviews the literature in computerized interpretation of ECG’s. Chapter 3 discusses the algorithm design for ECG feature extraction and classification in ECGOnline. Chapter 4 discusses the implementation issues. Chapter 5 reports and discusses the test results of running ECGOnline. 2. LITERATURE REVIEW This chapter provides a brief but critical review of the most common approaches to the automated analysis of ECG signals, and sets the context for the algorithms implemented in ECGOnline. 2.1 QRS Detection The first step in automated ECG analysis is to detect the ECG waveforms, including QRS complexes and P and T waves. While the detection of P and T waves (i.e., onsets and offsets) is still an open problem, the research on QRS detection has been quite successful. First of all, the accurate detection of QRS complexes is critically important. If QRS complexes are not correctly detected, the subsequent detection of P waves and T waves will also be misled and the feature parameters extracted from the signal will be meaningless. Many good QRS detection algorithms have been developed. Some are based on first and second derivatives [e.g., Bal77, AT83]; some are based on digital filters [e.g., Oka79, E279, and PT85]; some use template-matching techniques [e.g., FT82]; and others are based on wavelet transforms [e.g., LZT 95, MOLOO]. The QRS detectors based only on derivatives usually have poorer performance. Those using template matching are difficult to implement. The ones based on digital filters and wavelet transforms have good performance and are most popular. Some of the wavelet-based detectors were reported to achieve more than 99% QRS detection rate [LZT95, MOLOO]. A disadvantage of the wavelet-based QRS detectors is that they require very complicated and intensive computations, which would slow the responsiveness of a system designed for “on-line” use, such as ECGOnline, or require additional storage of multiple forms of each ECG signal, which was also deemed undesirable. Bceause QRS detectors based on digital filters require less computation but still provide very good performance, they were chosen as most appropriate for this study. The two QRS detectors implemented in ECGOnline are adapted from Okada’s [Oka79] and Engelse and Zeelenberg’s [EZ79] QRS detection algorithms, both of which are based on digital filters. These two algorithms were reported to be the best algorithms in a study of comparing the noise sensitivity of nine QRS detection algorithms [Fri90]. The study tested a H-lead normal ECG with 37 cycles, corrupted with such noise as powerline interference, respiration, baseline shift, and composite noise. The study showed that when the ECG signal was corrupted at a 50% level of noise, both algorithms had 100% QRS detection rate for all types of noise corruption, except that the performance of Okada’s algorithm dropped to 78% for electromyographic (EMG) noise corruption. Okada’s algorithm is set as the default QRS detector in ECGOnline (please see 3.1 for the implementation details). For the test cases randomly selected in this project for inspection, Okada’s algorithm had a 100% QRS detection rate for both normal and abnormal ECG’s. 2.2 Computerized ECG Interpretation Five basic approaches to computerized interpretation of ECG’s have been widely reported: decision logic, multivariate statistical pattern recognition, syntactic approach, fuzzy logic, and neural networks. The decision logic approach is most popular in the commercial automated ECG analyzers [Tom95, WuOO]. In this approach, the ECG analyzer mimics the cardiologist’s decision process using a rule-based expert system. The patterns of the input ECG are represented by a measurement matrix derived from the extracted ECG wave features. The rules are developed based on the experts’ cardiological knowledge and stored in a computer program as a set of IF-THEN statements. The parameter values in the measurement matrix are tested by this set of rules. A decision about the interpretation of the input ECG can be made based on the propositions (true or false) of the rule statements. An advantage of this approach is that it follows closely the cardiologist’s interpretation process and thus can be easily understood by human experts [Tom95]. Another advantage of this approach is that its interpretation decision can be made at a very low level based on one or more ECG feature parameters. In other words, its decision making can be based on either global or local patterns of the ECG. However, since the rules are based on the experts’ knowledge, such a system may never outperform human experts. Also, a limitation of implementing such a rule-based system is its requirement of the cardiological expertise. Nevertheless, the commercial ECG analyzers using this approach represent the state of the art. This approach, however, is also rendered impractical for application here because the experts’ rule sets are treated as proprietary information by the manufacturers of the commercial ECG analyzers. The second approach to ECG interpretation is based on statistical pattern recognition techniques. It usually consists of the following three stages (Figure 1): . Waveform , Feature ’ Interpretation ‘ . detection measurement lclassification Figure 1. Stages in the statistical pattern recognition approach The first two stages actually perform the task of feature extraction. The outcome of the feature extraction is a feature vector consisting of the measured values of the feature parameters. Its major difference from the decision logic approach lies in the interpretation stage. While the decision logic approach is knowledge based, the statistical approach is data driven. Its interpretation of the input ECG is based on a set of training samples and the statistical pattern classification algorithm that was implemented, such as Bayes or the K nearest neighbors (KNN) algorithm. Meanwhile, various techniques, from Principal Component Analysis, linear or nonlinear transforms, to Genetic Algorithms, can be applied to the selection and optirrrization of the feature parameters [e.g., PGP, Hua02]. An advantage of this approach is that it is not necessary to have extensive expert knowledge to implement such a system. Since this approach is data based instead of knowledge based, it is theoretically possible to develop an ECG interpretation system that outperforms the best physician [Tom95]. However, that is only in theory for now. One of the limitations of this approach is that it is difficult to know how well a given set of samples represents the ECG population. If the training samples poorly represent the population, using the statistical approach is fundamentally flawed. Another limitation of this approach is that it may be insensitive to small but diagnostically important changes in the shape of the ECG waves that cause little or no changes of the feature parameters [Pie9l]. This is where the syntactic approach comes in. The syntactic approach to ECG interpretation examines the ECG shape as well as its measured parameters [Pie9l]. This approach consists of three stages (Figure 2). Waveform . Primitive . Syntax . detection selection analvsis Tl Grammar inference Figure 2. Stages in the syntactic approach The first stage detects the ECG waveforms as in the statistical approach. The second stage transforms the waveform pattern into a string representation. The third stage classifies the ECG by testing whether the string is correct according to the rules defined by the inferred grammar. Using this approach, Pietka [Pie9l] reported a classification rate of 85% or better for tested ECG signals consisting of normal and five abnormal patterns. However, Skordalakis [Sk086] points out, referring to the general syntactic methods of ECG processing, that the syntactic approach only addresses specific sub-problems of ECG pattern recognition. The complete recognition of ECG patterns by the syntactic method has not yet been achieved. Since the ECG patterns have context-sensitive characteristics as well as time varying size and shape, it is difficult to devise a grammar for the description of these patterns. Another limitation of the syntactic approach is that it is very time-consuming to undertake the grammar inference for each class of patterns. In recent years, the application of fuzzy logic to automatic ECG interpretation has gained increasing attention. Fuzzy logic is based on the concept of fuzzy sets, where the membership of objects to classes is a matter of degree [Zad65]. The approach based on fuzzy logic uses fuzzy sets and fuzzy logic, rather than the conventional Boolean logic, to tolerate imprecision and noise in the data, which are prevailing in ECG signals. With the fuzzy logic approach, linguistic variables are used to describe the ECG features, and fuzzy conditional statements to represent the reasoning knowledge and rules. An advantage of a fuzzy logic system is that it is robust and cost-effective in the implementation of existing knowledge [Wie96]. Using a fuzzy classifier for a three-class arrhythmia classification, Silipo et al [SZB99] reported a classification rate of 92% for normal beats, 80% for PVBs and 56% for SVPBs. In another study, Wieben’s [Wie96] fuzzy-rule-based system correctly recognized premature ventricular contractions (PVCs) 81% of the time (out of two classes). The pattern recognition method based on fuzzy logic has serious limitations [J aiOO]. The fuzzy method is not useful for high dimensions or complex problems. A pure fuzzy method contributes little or nothing to problems with dozens of features. It also does not make use of the training data. When such a method has poor performance, it is often grafted to adaptive methods such as artificial neural networks (ANN 5). Artificial neural networks have emerged as a promising approach to automatic ECG analysis in recent years. Information in ANN s is encoded in the connection weights and learning is achieved by suitably adjusting the strengths of connections between neurons. The features of an ANN that, make it attractive for ECG interpretation are its adaptivity to frequently changing scenario, robustness to imprecision and uncertainty, massive parallelism and high degree of interconnection, and fault tolerant capability [KNBOO]. As discussed earlier, a fuzzy rule-based system is effective in dealing with the imprecision and uncertainty of ECG patterns. However, it requires quite intensive computation. This can be well handled by an ANN using its parallel processing. A major task for neural networks is to learn a model of the world (environment) [Hay99]. Unlike the rule-based system that relies on expert’s input, an ANN model for ECG interpretation can develop its knowledge base by learning from the set of training samples. Such systems with generalization capability are adaptive to variations of the input ECG’s and once trained, are capable of providing diagnosis rapidly [KNBOO]. Many ANN models have been successfully applied to the field of ECG analysis. Chazal and Celler [CC98] built a feedforward network, Softmax, modeling the Bayesian posterior probabilities for classifying seven classes of ECG’s such as normal, ventricular hypertrophy, and anterior myocardial infarction. Their model achieved a classification accuracy of 69.8%, which was claimed to be comparable to the performance expected of a panel of cardiologists. Some ANN models have been developed for the QRS complex classification and have achieved the good results. Among the best of these models are Associative ANN [SGM93], Linear Prediction and Fuzzy ARTMAP [HI-I96], and Kohonen Layer ANN [MCNOO]. Some adaptive resonance theory (ART) networks have been applied to ECG feature extraction with encouraging results [Suz95]. A major limitation of the ANN -based system for ECG interpretation is its complexity of implementation and the time-consuming training of the classifier. The five approaches discussed above are by no means exhaustive of the approaches to computerized ECG interpretation. Meanwhile, these approaches are not necessarily restricted to being used separately. In fact, many programs combined two or more of these approaches or other methods for better performance [e.g., Boz96]. There seems to be a new trend in combining neural networks and other techniques such as fuzzy logic for ECG analysis. It is also important to note that it is difficult to compare the performances of different algorithms due to their difference in one or more of the following factors: the ECG records selected for study, the sizes of the training and test sets, and the number and nature of the patterns (classes) for classification. 2.3 The K Nearest Neighbors Algorithm This project adopted the statistical pattern recognition approach, as it was easier to implement compared to other approaches. Usually KNN has pretty good performance among the statistical pattern recognition methods [JDMOO]. This study modified the KNN algorithm for ECG classification using weights and two thresholds (see 3.2 for details). This new algorithm is called adaptive weighted KNN (AWKNN). However, the focus of this project was on the architectural design and implementation of ECGOnline rather than on a specific classifier, although the latter is important for the project. The objective of this project was to develop a working ECG analyzer as a research tool with reasonable performance. When ECGOnline is up and running, more classifiers can be added in the future. Initially choosing the KNN algorithm for ECGOnline was influenced by IBM’s successful implementation of KNN in VeggieVision, a produce recognition system [B0196]. In this acclaimed system, four produce features — color, texture, shape, and size were extracted from a color image that was taken as the produce passed through the checkout point. The histograms of these features were normalized and concatenated to form the feature vector. There were 350 produce classes with 10 training samples of each. The classifier was implemented using the KNN algorithm and weighted Manhattan distance. VeggieVision had a classification rate of 82.6% when the training and testing 10 were in the same store. However, its performance decreased dramatically to 33.6% when the training and testing were in different stores. Recently Huang [Hua02] did a study comparing three statistical pattern recognition classifiers that were based on the KNN, Bayes, and Linear Regression algorithms respectively, for two-class (normal/abnormal) ECG recognition. In his study, principal component analysis and linear discriminant analysis were used to transform the ECG features, and a genetic algorithm (GA) was used to optimize the feature selection and extraction. When the GA was used, the KNN classifier performed slightly better than the other two classifiers (KNN 78.91%, Linear Regression 77.41%, Bayes 75.21%). However, when the GA was not used, the KNN classifier performed worse than the Linear Regression classifier but better than the Bayes classifier (KNN 73.4%, Linear Regression 77.59%, Bayes 71.94%). The detailed discussion of the implementation and testing of the AWKNN classifier is in 3.2, 5.1 and 5.2. 11 3. ALGORITHM DESIGN Feature extraction and signal classification are the two stages in computerized ECG analysis. This chapter discusses the algorithm design issues related to these two stages of ECG analysis. To facilitate the discussion, an ECG diagram and the related terminology are provided below (Figure 3). R ; PR interval QT interval . EP wave T wave 3 i A / \ i i Q s 1 PR segment ST segment QRS Figure 3. An ECG signal and its parameters A typical cycle of an ECG signal consists of P wave, QRS complex, T wave, and the segments between the waveforms. The P wave is a relatively small, rounded, and symmetrical waveform. The starting and ending points of a waveform are often called the onset and offset of the waveform respectively. The QRS complex is a sharp triangular waveform and is normally much taller than the P wave. The T wave occurs after the QRS complex. The T wave has a rounded gentle curve, is usually taller than the P wave and 12 has a longer duration than the QRS complex. The baseline is the straight line on the ECG. It represents the absence of electrical activity. The beginning of a waveform is marked by a departure from the baseline. The ending of a waveform is marked by a return to the baseline. An interval is the duration or length of time in which a waveform occurs. A segment is the period of time that begins when a waveform returns to the baseline and lasts until the next waveform begins. 3.1 ECG Feature Extraction The feature extraction algorithm in ECGOnline includes the following basic steps: 1) Use a QRS detector to detect the QRS complex and detemrine the number of beats in the ECG. 2) Detect P waves and T waves. 3) Correct the baseline of the original signal. 4) Extract ECG features for each beat (cycle). 5) Construct average cycle. 6) Generate feature vector for classification. QRS Detection As discussed in the literature review, the Okada’s [Oka79] QRS detection algorithm was implemented in ECGOnline. This algorithm has excellent performance. The following figure shows an example of QRS detection using Okada’s algorithm in ECGOnline. l3 .0 , 100 . 200, ,300. 41.19 H... 500... "£90-. ZOQWLBQU. ...4990 , 1000; An ECG Signal 'o 100 “200” 309 two ”sue - ape _ mo 7 poo I19,90.”firmsj QRS’s Detected by the Okada Algorithm (values are sealed for display) Figure 4. An example of QRS detection using the Okada algorithm There are four basic steps in Okada’s algorithm. Let X(n), n=1, 2, ..., N, be the ECG signal. The first step smoothes the signal using a three-point moving average filter: Y0(n) = [X(n-l) + 2X(n) + X(n+l)]/4, 1< n < N-l The output of the moving averaging filter is passed through a low-pass filter: Yl(n) = [l/(2m+l)] 2km". to n+mY0(k) m< n < N-m l4 where m is the Okada parameter (discussed later). The difference between the input and output of the low-pass filter is squared: Y2(n) = [Y0(n) — Y1(n)]2 m < n < N-m The squared difference is filtered: Y3(n) = Y2(n) mm", ,,,,mY2(k) )2 m < n < N-m The output is used to construct another array Y4(n) : if [Y0(n) — Y0(n-m)][YO(n) - Y0(n+m)] > 0 Y4(n) = Y3(n); else Y4(n) = 0; Then the maximum value of this array is determined and the threshold is set as follows: Threshold = 0.125 max{Y4(n)} m < n < N-m If Y4(n) > Threshold, a QRS is detected in the segment of 160 ms duration with n being the starting point. Parameter m is important for this algorithm. Friesen et al.’s study reported that as m increased, the performance increased along with computational demands. The improvement in performance began to fall off at values greater than 4, while computational demand continued to increase. Okada suggested setting m to 3 for best results. In the test cases in this project, there was no observable difference in performance for m = 3 and m = 4. When m > 4, the performance deteriorated. The default value of m for ECGOnline is set to 3. Engelse and Zeelenberg’s QRS detection algorithm [EZ79], recommended by a comparison study of QRS detectors, is also implemented in ECGOnline as an option. 15 After pinning down the location of QRS, the next step is to detect R-peak and Q and S points. R-peak is detected by searching for the maximum value of X[n] in the interval of 80ms (or 40 points for ECG with 500Hz sample rate) after the QRS detection mark. The Q wave is the first inflection point prior to the R wave. This inflection point is recognized by a change in the sign of slope, zero slope, or a significant change in the slope [Tom95]. Some QRSs usually satisfy the first and third conditions (see Figure 5, the QRS on the left). Some QRSs, however, only satisfy the third condition (see Figure 5, the QRS on the right). The implementation in ECGOnline first searches in the 80ms interval prior to the R peak for a point at which the ECG changes the sign of its slope or has zero slope, by checking the first derivative of the signal. If this search fails, ECGOnline searches for a point with the maximum change of slope by finding the maximum value of the second derivative of the signal in the interval. The S point is located as the first inflection point after R wave using the same strategy as for Q point. Figure 5. The left diagram shows an ECG that changes the sign of its slope at the Q point. The right diagram shows one in which the slope does not change sign at Q. After the Q point is located, the onset of QRS is determined by searching for the minimum value of second derivative of the ECG signal in the 60ms (30 points) interval prior to the Q point. This approach is based on the assumption that in this interval the 16 ECG slope decreases most dramatically at the QRS onset. Similarly, the QRS offset is determined by searching for the maximum value of the second derivative in the 60ms interval after the S point, assuming the slope increases most significantly at the offset point. T and P Wave Detection The T peak is established by searching for the maximum value of the signal in the 300 ms (150 points) interval after the QRS offset. Then the T onset is located by searching for the maximum value of the second derivative of the signal in the interval between the mid-point of the S-T interval and the T point. The T offset is located by searching for the maximum value of the second derivative in the interval of the same length after the T point. The same approach is used to find the P peak, P onset and P offset points. After the previous steps, the eleven feature points in the beat are located. These steps are repeated for the next beat. After the end of the signal is reached, the number of heartbeats in the signal and the feature points in each beat are determined. Baseline Correction Baseline correction is a tricky issue. Four different ways were tested in this work before one was chosen. The tricky part is how to determine the baseline. In the literature, the baseline is defined as the line between two consecutive P-Q intervals. But there are different ways to determine the baseline, depending on reference points chosen. N orrnally the reference points would be the P onset and /or Q onset. But in this project it was found 17 that the onset points are not as accurately identified as the peak (P, R, T) points. As such, if the baseline is determined by the onsets (or offsets) and is off a few points, the amplitude of every point after the baseline correction will be incorrect. Thus, in this project, the “baseline” was defined as the line passing through the two consecutive P points, because the P points are more accurately located than the P onsets or Q onsets. In this way, the baseline is actually translated upward. This translated baseline is seen as a reference line rather than the baseline. The point here is to use this reference line to remove the baseline wander. The baseline-corrected amplitudes obtained from this method will be decreased by a constant, in theory, compared to those obtained from the traditional method, but that will not affect the ECG classification results in ECGOnline. This is because ECGOnline uses a statistical pattern recognition algorithm that is based on the morphology of the signal rather than the absolute values of the parameters. Parameter Computation In ECGOnline, four groups of parameters are obtained from each beat for analysis: amplitudes, durations, slopes, and areas. The amplitudes of the feature points for each beat are obtained by subtracting the baseline from the original amplitudes of the signal. There are total eleven amplitudes that correspond to the eleven feature points of each beat. There are ten duration parameters: P wave duration (P offset - P onset) P-R segment (QRS offset — P offset) QRS duration (QRS offset — QRS onset) 18 PR interval (QRS onset — P onset) S-T segment (T onset — QRS offset) T wave duration (T offset - T onset) QT interval (T offset — QRS onset) T-P segment (P onset of next beat — T offset of current beat) R-R rate (heart rate) Standard deviation of R-R rates of all the beats These time domain parameters have long been used for ECG analysis. The third group of parameters measured is the slopes of the signal. Slopes reflect to some degree the shapes of the ECG waves. If we only measure the amplitudes and durations of the feature points, we may miss a lot of information on what is going on between the feature points. There will be no difference between a line and a curve that connect the feature points. In this project, each beat of the signal is divided into ten intervals with the eleven feature points as the end points. The average slope in each interval for each beat is computed by summing the first derivative of the signal and dividing by the duration of the interval (which is the number of points in the interval). The areas of P, R, and T waves are computed as the fourth group of parameters. The area of a wave is defined as the area enclosed by the wave and the segment connecting the starting and ending points (onset and offset) of the wave (see Figure 6). Areas of ECG waves are considered to be important parameters of computerized ECG analysis [WuOO]. The area of a wave is approximated by summing the offsets of the signal from the base segment. The following is the brief reasoning: l9 y(t) t0 t tn Figure 6. Area of an ECG wave Let y(t) t =0, 1, n be the offsets of the amplitudes from the segment tO-tl and y(0) = you = 0. Area E integration of y(t) from t0 to tn = 2t=0 to ..-, [y(t)* 1] = 2.=o to “-1 y(t) After the above four groups of parameters are obtained from each beat of the ECG signal, the trimmed mean [Afo96] of each parameter across all the beats is calculated by discarding the two highest and the two lowest values and averaging the rest of the values. Trimming the highest and lowest values is to reduce the parameters’ sensitivity to noise. The trimmed mean of each parameter value is used to represent the parameter for the average ECG cycle. Feature Vector Generation Each group of mean parameters is then separately normalized. Then these four groups of 34 normalized parameters are concatenated to generate a feature vector. This feature vector is to be fed into the ECG classification program. 3.2 ECG Classification: Adaptive Weighted KNN Two classifiers have been implemented in ECGOnline. One is based on the K nearest neighbors (KNN) algorithm, and the other is based on the adaptive weighted 20 KNN (AWKNN), a modified KNN algorithm by this study. The KNN assigns the unknown member to the majority class in the K nearest neighbors. It is over simplistic in that it treats the K nearest neighbors equally in making the classification decision. Ideally, the closer a neighbor is to the unknown member, the more weight it should has in the classification decision. From this perspective, this study modified the traditional KNN using weights. Furthermore, two thresholds are introduced to fine-tune the decision boundary and thus make the classifier more adaptive to the training data. The following explains how AWKNN works. Let x be the unknown ECG to be classified, and vi (i=1, 2, ..., k) be the k nearest neighbors of x and d; (i=1, 2, ..., k) be their corresponding distances sorted in ascending order. 80 v; is the nearest neighbor and so on. Let C1 and C2 represent the normal and abnormal ECG classes, and S; and 82 their training sets, respectively. Function d(x, y) represents the Euclidean distance between x and y. Each neighbor V, has a weight w. The decision rules of AWKNN are defined as follows 1) A lower threshold t is set for the distance between the input ECG signal and the nearest sample. If this distance is below the threshold, the ECG is classified as being in the same class as the nearest sample, regardless of the class status of its K-l remaining nearest neighbors. The reasoning for this modification is that if the input ECG closely matches a training sample, it is considered as being in the same class as the sample. This can prevent the classification mistakes that the input ECG is identical to a training sample but is assigned to a class different from that of the sample. In this study, the lower threshold t is set to the following value: t0=min{d(x1,x2)|xle SI .X26 32} 21 to is the minimum distance between any two ECG’s from different classes in the training sets. So if the distance between two ECG’s in the training samples is less than to, they must be in the same class. Of course, this may not be true for ECG’s outside the training sets. to is used as a trained parameter for t (see 5.1, Training and Testing, for more discussion). 2) An upper threshold T is set for the distance between the input ECG and its nearest normal ECG sample. If this distance is greater than T, the input ECG is classified as abnormal. The underlying assumption for this rule is that if the distance is greater than the threshold T, the input ECG is too far away from the normal ECG samples and therefore is considered as abnormal, even though it has no nearest abnormal ECG neighbors. Based on the experiments in this study, the following value is a good candidate for T: To: mean{D(Sl, 81)} — std{D(Sl, 81)} where D(SL 81): { d(xl, x2 ) l xl, X26 81 } D(S1, $1) is actually the set of distances between the normal ECG’s in the training set S]. The mean and std are the mean and standard deviation of D. In this study, a systematic search is used to find the best value of T based on the training samples (see 5.1 and 5.2 for details). 3) If conditions 1) and 2) are not satisfied, then (1, > 0 (i=1, 2, ..., k). The weights are defined as follows w, = (1/d, )IZ ...,-..., (1/dj) (i=1, 2, k) (a) 22 Obviously, 0 <= w, <= 1, and 21cm}. w, = 1. When d, -> 0, w, -> 1. When (1, -> 00, w, -> 0. The probabilities of x belonging to C. (normal) and C2 (abnormal) are defined as follows Pi = Z 1<=j<=k [Wj * P(Vj 6 Ci )1 (b) = 2 VjeCi Wj (i = 1, 2) (0) Where P(E) is the probability of E. Clearly, P1+ P2 = l. The class of x is decided by the maximum Pi. If P1> P2 (or P1 > 1/2), then x is assigned to class C1. If P1< P2, then x is in assigned to class C2. If P1 = P2, x is assigned to the class of its closest neighbor’. Actually, I) and 2) can be seen as special cases of this probability model. In case 1), If (11 = d(x, v1) < t (note: v1 is x’s closest neighbor), then x is classified as being in the same class as v]. Condition “ (11 < t ” can be seen as d1—> 0. So W1: 1, and w, = 0 (l< i <=k) according to equation (a). By equation (b), the probability that x belongs to class C, is Pi = W1 * P(VrE Ci ) = P(VIE Ci ) This means that x and V] are in the same class. In case 2), if the minimum distance between x and the normal ECG’s (C1) exceeds the upper threshold T, x is classified as abnormal (C2). The “if” condition means that the distance d, (1<= i <=k) for those nearest normal neighbors v, if any, go to infinity (exceed the threshold). Thus, their corresponding weights w, go to 0. Since the sum of all the weights is always 1, the weights are transferred to the nearest abnormal ECG’s. It follows that P] -> 0 and P2 -> 1 by equation (c). Therefore, x is assigned to C2 (abnormal). 23 In equation (a), the scale factor 21 T, x is assigned to the class of vl’s. But finding good values for these two thresholds could be very difficult if the number of the classes and the size of the training sets are big. Let D be the set of distances between any pair of members from different classes in the training sets. Then the minimum and maximum values of D can be used as estimates for t and T respectively. For any members x and y, if d(x, y) < t = min(D) or d(x,y) > T = max(D), then x and y must be in the same class. The above rule 1) and 2) are based on this property of the training samples. However, min(D) could be too small and max(D) too big to be useful if the range [min(D), max(D)] covers almost the whole distance space. The equations (a) ~ (c) in rule 3) for the 2-class AWKNN can be directly used for the n-class situation by expanding the class index i from 2 to n. The class of the unknown member x is decided by comparing 24 the probabilities P, = P(xe C, ) (i = l, 2, n). If Pj = max{P,}, then x is assigned to class Cj. In ECGOnline, there are 792 ECG training samples, of which half are normal and half are abnormal. The feature vectors of the training samples are generated and stored in a binary file. The training and testing of the KNN and AWKNN classifiers will be discussed in Chapter 5. 25 4. IMPLEMENTATION OF ECGOnline This chapter discusses the architectural design and programming of ECGOnline. 4.1 A Distributed Application ECGOnline is a distributed application. The communication between the client and the server is implemented with Java Remote Method Invocation (RMI). The RMI architecture allows the code that defines the methods and the code that implements the methods to remain separate and to run on separate Java Virtual Machines (JVM’s). In RMI, the definition of a remote method or service is coded using a Java interface. The implementation of the remote method is coded in a class. The following diagram illustrates this working mechanism: Client Program Server Program Interface Implementation T RMI T Figure 7. Java RMI mechanism In ECGOnline, the signal transformation and ECG classification algorithms are implemented in the server program as remote methods that can be called by the client program. The RMI component in ECGOnline includes the following: 0 Interface definitions for the remote methods (file: Waveletjava) o Implementations of the remote methods (file: WaveletImpl.java) 0 Stub and Skeleton files (files generated by Waveletlmpl.class) 26 0 The server to host the remote methods (file: Server.java) 0 The client program (file: WaveletMethod.java) 4.2 The Client The design of the client is based on the Model-View-Controller (MVC) architecture [Hor99]. MVC is an idealized way of modeling a component as three separate parts: 0 The model that stores the data which defines the component 0 The view that creates the visual representation of the component from the data in the model 0 The controller that deals with user interaction with the component and modifies the model and /or the view in response to a user action, as necessary The actually implementation of ECGOnline, however, is very complicated and not as neat as the above definition. Nevertheless, it follows the basic principle of MVC model. In ECGOnline, the data “model” is defined in the ECG class (ECG.java) , the “view” is defined in the view class (view.java), and the “controller” is defined in the GUI class (GUI.java). The following diagram shows the relationship between these components (Figure 8): ECG Object Model ECG Diagram GUI View fi Controller Figure 8. The MVC architecture 27 The ECG class models the ECG signal. The data members of the ECG class are defined as follows: String name; // ECG file name byte type; // ECG types: 0 = normal, 1 = abnormal, 2 float[] signal; // ECG signal array Vector feature // Vector of ECG feature points boolean flag; // flag for painting feature points Three ECG constructors are defined to accommodate different application situations. The use of a vector rather an array to hold the feature points is because the number of heart- beats of the ECG signal needs to be dynamically determined at run time. The following methods are implemented in the ECG class for changing the values of individual data members or the whole ECG object: public void setName(String ecgName) public void setType(byte echype) public void setSignal(float[] A) public void setFeature(Vector F) public void setECG(float[] A, Vector F, String ecgName, byte echype, boolean 602F133) After changing the data value, each method notifies the corresponding view class object to update the graphic representation of the ECG object. The ECG class also has get() methods to make the data members accessible to other classes. The view class defines the methods to draw the ECG diagram and feature points. The ECG is scaled down to drawn in a 500x200-pixel rectangle. The important model/view relationship between the ECG class objects and the view class objects is 28 established through the implementation of observable and observer objects defined in Java. When an observable object changes, it notifies its observer to update the view. In ECGOnline, The ECG signals are implemented as observable objects while the view objects are observers. In Java, observable is a class and observer is an interface to be implemented. So in ECGOnline, the ECG class inherits the Java observable class and the view class implements the observer interface. When an ECG object changes, it calls the notifyObserversO method to notify the view observer. In turn, the view observer calls the update() method to update the display. The Gui class implements the graphic user interface for ECGOnline, as shown in the following figure (Figure 9). Figure 9. The graphic user interface of ECGOnline 29 The GUI window consists of a menu bar, text area, and two graphic display areas. Users access the operations through the menus. The text area is used to display useful text information such as ECG feature parameters and classification results from the server. The two graphic areas are used to display ECG’s and filtered signals. The seven menus in the menu bar provide seven groups of operations: File, Filters, Detectors, Transform, Features, View, and Classify. The File menu provides I/O operations, which include read ECG signal from a local disk or a remote URL and save operations. When an ECG signal is read in, ECGOnline displays part of the ECG in the upper graphic area in a zoom-in mode and the whole ECG in the lower graphic area. It automatically locates the ECG feature points and displays them. Meanwhile, it computes the thirty-four feature parameters and generates the feature vector for classification analysis. The client runs these feature extraction processes. The Filters menu provides some common digital filters such as first and second derivative, moving average, Chebyshev, windowed-sine, etc. The user can select one of these filters and see the filtered signal displayed in the lower graphic area. These filters are implemented in the client side in file Filters.java. More filters can be easily added later. However, if there are two many filters, it is better to implement them in the server program to keep the client program simple. The View menu is used to control the display of the ECG. The ECG is divided into five sections with 2-second durations (1000 points for 500 Hz sample rate). The user can select any section of the ECG to display in a zoom-in mode or display the whole ECG in a zoom-out mode in any of the two graphic areas. 30 The Detectors menu provides some QRS detectors for the user to use. Currently two QRS detectors are implemented: the Okada QRS detector and En gelese and Zeelenberg QRS detector. The former is implemented as the default QRS detector called by the feature extraction algorithm in ECGOnline. These detectors are implemented in the client side. The Transform menu is designed to provide transform operations such as FFT. Because the transforms usually require intensive computation, their implementations are to be in the server side. Currently only four simulated transforms are implemented. When the user selects one of these transforms, the client program will send the signal to the server. The server will do the computation and return the transformed signal, which will be displayed in the lower graphic area. If we want to replace these simulated transforms later, we only need to replace their names and implementations. The Features menu is used for displaying ECG feature points or parameters in the text area. The Classify menu is used to run the ECG classification algorithms. Only KNN algorithm has been implemented in this work. When the user selects the KNN algorithm, the client program sends the ECG feature vector to the server. Upon receiving the feature vector, the server runs the KNN algorithm to classify the ECG signal and sends the result to the client. The client then displays the result in the text area. 4.3 The Server There are two major tasks in implementing the server: setting up the RMI framework and implementing the methods defined in the client interface file. When the 31 RMI system is up and running, implementing the methods is straightforward. RMI will take care of marshaling the parameters and communicating with the client. The sample ECG feature vectors for the AWKNN algorithm are stored in a binary file named samples.bin. When the server starts up, it automatically reads the ECG sample vectors into a two-dimensional array, and then is ready to run the classification algorithm. 32 5. TRAINING, TESTING, AND RESULTS This chapter reports and discusses the test results of running the AWKNN and KNN classifiers. The focus is on the AWKNN classifier. The ECG records used in the tests were from the data bank collected by Shanghai Zhongshan Hospital. The ECG’s were 10 seconds long with a 500 Hz sample rate. A total of 996 ECG’s were selected for this study, of which 500 are normal and 496 are abnormal. The 500 normal ECG’s were randomly divided into five lOO-ECG groups. Sirrrilarly, the 496 abnormal ECG’s were also organized into five groups of 100 abnormal ECG’s, with the final group copying 4 records from another group to make it 100 in size. Five tests were conducted. In each test, a group of 100 normal ECG’s and a group of 100 abnormal ECG’s were selected for testing. The remaining 396 normal (after discarding 4 records) and 396 abnormal ECG’s were used as training samples. 5.1 Training and Testing The training and testing were conducted offline rather than in ECGOnline, for a large number of ECG’s can be tested offline continuously and fast. However, the same feature extraction and KNN classification algorithms were used. The feature vectors of the training and test sets were generated in advanced using the feature extraction algorithm. Then these sample feature vectors were fed into the KNN and AWKNN classifiers for training and testing. The major task of training the AWKNN classifier was to find the optimal values for K, the lower threshold t, and the upper threshold T based on the training samples. The 33 basic steps in each training are as follows: 1) Find the minimum distance between pair of ECG’s of different classes in the training set; let this minimum value be min{D(S., 82)}. 2) Randomly select 100 normal and 100 abnormal ECG’s from the training set as test data, the remaining ECG’s in the training set as samples. 3) Set t = min{D(S., 82)} (see 3.2 for more discussion of t) and run the classifier with different values of K (1, 3, ..., 37) and T (0.2, 0.25, 0.30, ..., 0.95). 4) Find the (K, T) values that gave the best performance; if multiple (K, T) values are found, take the one with the best clustering. The following table shows the results from the training (Table 1). Table 1. AWKNN Training Results for Five Different Training Sets Training Set Set 1 Set 2 Set 3 Set 4 Set 5 mean { D(Sr. 30} 0.6566334 0.67080927 0.67665064 0.6814681 0.6687712 std {1)(51‘ 31) } 0.2864994 0.2943812 0.3042346 0.3043928 0.29898244 min{ ms], 32)} 0. 10426351 0.10426351 0.10469978 0.10801367 0.10426351 Trained t=0.10426351 t =0.1042635 1 t =0.10469978 t $.10801367 t =0.10426351 Parameters T = 0.4 T = 0.4 T = 0.45 T = 0.25 T = 0.4 K=3] K=19 K=35 K=7 K=25 Performance on Test Set 70% 84% 75% 77% 76.5% Optimal T = 0.25 T = 0.4 ~ 0.95 T = 0.4 T = 0.3 T = 0.4, 0.45, (T, K) for K=3 K=7,1l,19, K: 11 K=25 0.65.0.7 Test Set 21 K = 35 (22 points) Optimal Performance 73 % 84% 78% 79.5% 77.5% S, = {normal ECG’s in the training set}, S2 = {abnormal ECG’s in the training set}. D(Sr. Sz) '-' { d(Xr. X2 ) I X16 31. X26 52 l The last two rows show the real optimal parameter values and performance for the test sets for comparison. The results show that the optimal T values are clustered at 0.4, which is roughly the difference between the mean and standard deviation of the normal ECG’s in the training set, or represented as mean{D(S,, 81)} — std{D(S,, S,)}. This is consistent across all training and test sets. Although T = 0.4 always gives very good performance, more detailed training and testing information shows that there is a second 34 best clustering of the optimal T values at 0.6~0.7, which is roughly the mean of the the distances between pairs of normal ECG’s in the training set. However, the generalizability of these observations needs to be tested on other databases. The optimal K value varies greatly from training set to training set. For given t and T values, normally the performance of AWKNN increases as K increases. The performance peaks at a certain point and then decreases slowly as K gets large. Sometimes there are multiple peaks of performance corresponding to multiple optimal K i {T'Yf‘ff .1: values. Usually the performance is quite good for K values between 27 and 37. Figure 10 shows an example of K values vs. the performance of the AWKNN classifier for the first training set. Classification Rat—o tor Dtflonm K Vow“ Figure 10. K values vs. performance (T = 0.4, t = 0.10426351) The training for KNN was simple - it only needs to find the optimal K value. The trained K values for the previous five training sets were (27, 19, 3, 3, 3). 35 In each test, the trained parameters were fed into the corresponding classifier. The following section discusses the test results. 5.2 Performance and Limitations of the Classifiers The following table shows the percentages of the ECG’s that were correctly classified in five tests by the two classifiers (Table 2): Table 2. Comparison of the performance of two classifiers in five tests Test Sets Classifiers Test 1 Test 2 Test 3 Test 4 Test 5 Average 100 AWKNN 88% 92% 91% 75% 86% 86.4% Normal KNN 89% 92% 81% 83% 76% 84.2% 100 AWKNN 52% 76% 59% 79% 67% 66.6% Abnormal KNN 46% 72% 60% 59% 69% 61.2% 200 AWKNN 70% 84% 75% 77% 76.5% 76.5% Mixed KNN 67.5% 82% 70.5% 71% 72.5% 72.7% Notes: 1) The test sets are different for different tests. 2) The percentages in the last row were computed from the results in the second and third rows. Overall, the AWKNN classifier improved KNN’s performance from 72.7% to 76.5%. The major improvement came from the abnormal ECG sets, from 61.2% to 66.6%. For the normal sets, it improved only two percentage points, from 84.2% to 86.4%. From the table we see that the classification performance of both classifiers on the normal ECG’s was consistently much better than on the abnormal ECG’s across the five tests. For both classifiers, the performance differences between these two data sets were about 20%. 36 Why were the abnormal ECG’s more difficult to recognize than the normal ECG’s? To explore this question, this study investigated the distributions of the Euclidean distances between the ECG’s in or between different classes. The results are summarized in Table 3. Table 3. Distributions of the distances between ECG’s Statistics Normal ECG’s Abnormal ECG’s Between Normal & Abnormal Mean 0.671305 1.002745 0.889289 Standard deviation 0.297952 0.510704 0.428833 Range 0 ~ 2.061144 0 ~ 2.916923 0.104264 ~ 2.613042 These results were computed from all the 500 normal and 496 abnormal ECG samples that were used in this study. There are nearly half million distances between pairs of these ECG’s. The mean distance between the normal ECG’s (0.671305) is much smaller than that between the abnormal ECG’s (1.002745). The standard deviation of the distances between the normal ECG’s (0.297952) is also much smaller than that of the distances between the abnormal ECG’s (0.510704). This suggests that the normal ECG’s are more clustered than the abnormal ECG’s in the feature space. Another interesting finding is that the mean distance between the normal and the abnormal ECG’s (0.889289) is less than that between the abnormal ECG’s. The following hypothetical figure illustrates these findings (Figure 11). A A O : fiiihreshold T 0 normal ECG A abnormal ECG n.336fl A 00 $0 0: AOQA 2 A Figure 11. Distribution of normal and abnormal ECG’s in the feature space 37 In the feature space, the normal ECG’s are clustered in a certain region, whereas the abnormal ECG’s are scattered around. This also makes sense when we think of ECG classes from a cardiologist’s perspective. According to the literature [Lu00], the parameters of a normal ECG usually fall into certain ranges. For instance, the amplitude of a normal P wave is usually between OmV and 0.25mV and the duration between Os and 0.113. When the feature parameters are out of the defined ranges, the ECG is considered abnormal. From a mathematical perspective, the out-of-range parameter values are more discrete and dispersed. As such, the in-range normal ECG’s are more ‘-" clustered than the out-of-range abnormal ECG’s. The difference in the distance distributions between the normal and abnormal ECG samples presents a serious problem for the KNN classifier. In the feature space, the abnormal ECG’s might have more nearby normal neighbors than nearby abnormal neighbors. It is no surprise that many abnormal ECG’s are mistakenly classified as normal by their nearest normal neighbors using the KNN algorithm. To deal with this problem, an upper threshold is used in AWKNN for the minimum distance between the normal and the abnormal ECG’s, as discussed in section 3.2. If the distance between an unknown ECG and the nearest normal ECG sample is greater than the threshold, the unknown ECG is classified as abnormal. The reasoning for this is that if the unknown ECG is far away from all normal ECG’s, which means the distance exceeds the threshold, it is considered as abnormal regardless of its nearest neighbors. For example, in Figure 8, x is an unknown ECG, and the threshold is marked by the circle. Thus, x has more nearby normal neighbors than abnormal neighbors. But it is classified as abnormal because all the nearest normal ECG neighbors are outside the 38 circle — farther way than the threshold permits. This method, used in AWKNN, improves the performance of the KNN classifier. As the threshold decreases, more abnormal ECG’s are picked up by the AWKNN classifier. But meanwhile, more normal ECG’s are mistakenly classified as abnormal, because the distances between the normal ECG’s may easily exceed the small threshold. This phenomenon was very consistent across the test cases in this study. Therefore, there is a tradeoff to be made. It is difficult to use the threshold to separate those abnormal ECG’s that are very close to the normal ECG’s. The threshold remedy does not completely solve the problem of low performance in recognizing the abnormal ECG’s. Another way of dealing with this problem is to increase the number of training samples in the abnormal ECG set. Because the abnormal ECG’s are more dispersed and have a “larger” abnormal feature region, more training samples of abnormal ECG’s seem necessary. As Jain and Chandrasekaran [JC82] point out, the ratio of sample size to dimensionality is a crucial factor in the design of a recognition system, and there is danger in having too many measurements in the classifier design when the number of samples is small. Yet it is unclear how many samples are needed for the AWKNN classifier. This would be a good issue for future study. Currently we have a very limited number of abnormal ECG records, and no information about the types of different abnormalities each may represent. 5.3 Effects of Feature Parameters This study has also examined the effects of the individual groups of feature parameters on the performance of the AWKNN classifier. As introduced in section 3.1, 39 an ECG feature vector consists of four groups of parameters: the amplitudes of feature points, the durations of intervals, the averaged slopes of intervals, and the areas of ECG waves. Table 4 summarizes the results of five tests using only a single group of parameters. The tests were identical to the previous tests except that the thirty-four feature parameters were replaced with one of the four groups of parameters. Table 4. Performance of AWKNN using a single group of parameters Feature Parameters Normal ECG’s Abnormal ECG’s Average All 34 Parameters 86.4% 66.6% 76.5 % Amplitudes 77.2% 64.6% 70.89% Durations 70% 61.8% 65.9% Slopes 79.4% 57.2% 63.3% Areas 64.4% 60.8% 62.6% The results from previous tests are also presented in the table for comparison. The most effective group of parameters is amplitudes. Using this group of parameters alone can correctly classify 70.89% of the ECG’s. The performance is degraded by 5.6 percentage points compared with using all four groups of parameters. The less effective groups of feature parameters are in the following order: durations, slopes, and areas. However, the effectiveness of single groups of feature parameters does not tell the whole story. It is more important how the different groups of parameters work together. Table 5 shows the mean results of five tests using combined groups of feature parameters: 40 Table 5. Performance of AWKNN using combined groups of feature parameters Feature Vector Normal ECG’s Abnormal ECG’s Average All 34 Parameters 86.4% 66.6% 76.5 % Areas removed 87.2% 64% 75.6% Slopes removed 84% 62.4% 73.2% Amplitudes removed 83% 62% 72.5 % Duration removed 82.8% 66.8% 74.8% Areas & slopes removed 82.2% 62.8% 72.5% Amplitudes & duration removed 74.2% 60% 67.1 % When the area parameters were removed from the feature vectors, the average rate for classifying mixed ECG’s dropped 0.9 percentage points. This suggests the addition of the area parameters to other three groups of features can improve the classification performance by about 1 percentage point. When the slope parameters were removed from the feature vectors, the performance decreased by 2.3 percentage points. This indicates that the addition of the slope parameters can improve the performance of ECGOnline by about 2 percentage points. When both the area and lepe parameters were removed from the feature vectors, the performance degraded from 76.5% to 72.5%. This means that adding the area and slope parameters can contribute a 4-percentage point improvement to the performance of the AWKNN classifier. 5.4 Conclusions and Future Directions The following are the major conclusions regarding 2-class ECG interpretation from this study: 1) The AWKNN classifier improves the traditional KNN classifier for ECG interpretation from 72.7% to 76.5%. 41 2) The addition of the slope and area features to the classic amplitude and duration features improves the performance of the AWKNN classifier from 72.5% to 76.5%. 3) The normal ECG’s are more clustered than the abnormal ECG’s in the 34- feature space defined in this study. 4) The abnormal ECG’s are more difficult to recognize than the normal ECG’s using the KNN and AWKNN classifiers. 5) The lower and upper thresholds in AWKNN can be estimated as t = min{D(S., 82)} and T = mean{D(S., 5.)} - std{D(S.. S,)}, where S. and S2 are the training sets for the normal and abnormal ECG’s respectively, and D(S., 82) ={d(x1, x2) I X16 S], X26 8] }. The following directions are worthy of future exploration to continue this study: 1) Apply statistical and other techniques such as genetic algorithms to ECG feature selection and optimization. 2) Develop and compare classifiers that are based on the emerging techniques such as neural networks and fuzzy logic. As discussed in the literature review, these techniques have shown potential for ECG interpretation. 42 BIBLIOGRAPHY [Afo96] Afonso, V. X. et al. “Comparing stress ECG enhancement algorithms: with introduction to a filter bank based approach,” IEEE Engineering in Medicine and Biology, May/June 1996. [AT83] Ahlstrom, M. L. and Tompkins, W. J. “Automated high-speed analysis of holter tapes with microcomputers,” IEEE Transactions on Biomedical Engineering, Vol. BME- 30, pp. 651-657, Oct. 1983. [Bal77] Balda, R. A., et al. “The HP ECG analysis program,” Trends in Computer- Processed Electrocardiograms, vanBemnel, J. H. and Willems, J. L. Eds. North Holland, pp. 197-205, 1977. [B0196] Bolle, R. M., at al. VeggieVision: A Produce Recognition System. www.research.ibm.com/ecvg[pubslihc-wacv.mf, 1996. [B0296] Bozzola, P., et al. “A hybrid neuro-fuzzy system for ECG classification of myocardial infarction,” IEEE Computers in Cardiology, pp. 241-244, 1996. [CC98] Chazal, P. and Celler, B. G. “Selecting a neural network structure for ECG diagnosis,” Proceedings of the 20” Annual International Conference of the IEEE Engineering in Medicine and Biology Society, Vol. 20, N0. 3, 1998. [EZ79] Engelse, W.A.H. and Zeelenberg, C. “A single scan algorithm for QRS-detection and feature extraction,” IEEE Computers in Cardiology, pp.37-42. Long Beach: IEEE Computer Society, 1979. [Fri90] Friesen, et al. “A comparison of the noise sensitivity of nine QRS detection algorithms,” IEEE Transactions on Biomedical Engineering, Vol.37, No.1, Jan. 1990. [FT82] Fumo, G. S., and Tompkins, W. J. “QRS detection using automata theory in a battery-powered microprocessor system,” IEEE Frontiers of Engineering in Health Care, 4: 155-58, 1982. [Hay99] Haykin, S. Neural Networks: A Comprehensive Foundation. New Jersey: Prentice Hall, 1999. [HH96] Han, F. and Han, S. “Classification of cardiac arrhythmia using fuzzy ARTMAP,” IEEE Transactions on Biomedical Engineering, 43: 425-430, 1996. [H0r99] Horton, 1. Beginning Java 2, pp. 526-527. Birmingham, UK: Wrox Press, 1999. 43 [Hua02] Huang, Z. Genetic Algorithms Optimized Feature Extraction and Selection for ECG Pattern Classification. Master’s Thesis, Michigan State University, Department of Electrical and Computer Engineering, 2002. [Jai00] Jain, A. K. Pattern Recognition and Analysis, Course pack for CSE 802, Michigan State University, Department of Computer Science and Engineering, 2000. [JC82] J ain, A. K. and Chandrasekaran, B. “Dimensionality and sample size considerations in pattern recognition practice,” Krishnaiah, PR. and Kanal, L. N. Ed., Handbook of Statistics, Vol. 2, pp. 835-855. North-Holland Publishing, 1982. [JDMOO] Jain, A. K., Duin, R.P.W., and Mao, J. “Statistical pattern recognition: a review,” IEEE Transactions on Pattern Analysis and machine Intelligence, Vol. 22, No. 1, Jan. 2000. [KNBOO] Kundu, M., N asipuri, M., and Basu, D. K. “Knowledge-based ECG interpretation: a critical review,” Pattern Recognition, 33: 351-373, 2000. [Lu00] Lu, S. Interpreting Electrocardiogram. Beijing: Scientific and Technical Documents Publishing House, 2000. [LTZ95] Li, C., Zheng, C., and Tai, C. “Detection of ECG characteristic points using wavelet transforms.” IEEE Transactions on Biomedical Engineering, Vol. 42, No. 1, Jan. 1995. [MCNOO] Melo, S. L., Caloba, L. P., and Nada], J. “Arrhythrrria analysis using artificial neural network and decimated electrocardiographic data,” IEEE Computers in Cardiology, 27: 73-76, 2000. [MOLOO] Martinez, J. P., Olmos, S., and Laguna, P. “Evaluation of a wavelet-based ECG waveform detection on the QT database,” IEEE Computers in Cardiology, 27: 81-84, 2000. [Oka79] Okada, M. “A digital filter for QRS complex detection,” IEEE Trans. Biome. Eng. V01. BME-26, pp. 700-703, Dec. 1979. [PGP98] Pei, M., Goodman, E. D., and Punch, W. F. “Feature extraction using genetic algorithms”, Proceedings of International Symposium on Intelligent Data Engineering and Learning ’98, Hong Kong, Oct. 1998. [Pie91] Pietka, E. “Feature extraction in computerized approach to the ECG analysis,” Pattern Recognition, Vol. 24, No. 2, pp. 139-146, 1991. [PT85] Pan, J. and Tompkins, W. J. “A real-time QRS detection algorithm,” IEEE Transactions on Biomedical Engineering, BME-32: 230-36, 1985. [Sk086] Skordalakis, E. “Syntactic ECG processing: a review,” Pattern Recognition, Vol. 19, N0. 4, pp. 305-313, 1996. [Smi97] Smith, S. W. The Scientist and Engineer’s Guide to Digital Signal Processing, California Technical Publishing, 1997. [SGM93] Silipo, R., Gori, M, and Marquesi, C. “ Autoassociator structured neural network for rhythm classification of long term electrocardiogram, ” IEEE Computers in Cardiology, 1993: 349-352. [Suz95] Suzuki, “Self-organizing QRS wave recognition in ECG using neural networks,” IEEE Trans. Neural Networks, 6(6): 1469-1477, 1995. [SZB99] Silipo, R., Zong, W., and Berthod, M. “ECG feature relevance in a fuzzy arrhythmia classifier,” IEEE Computers in Cardiology, 26: 679-682, 1999. [T0m95] Tompkins, W.J. “ECG analysis systems,” Tompkins, W. J. Ed. Biomedical Digital Signal Processing, pp. 265-282. New Jersey: Prentice Hall, 1995. [Wie96] Wieben, O. The Classification of PVCs using Filter bank Features, Induction of Decision Trees and a F uzzy-Rule-Based System, Master’s Thesis, University of Wisconsin-Madison, Department of Electrical and Computer Engineering, 1996. [WuOO] Wu, J. “ Computer analysis of the electrocardiogram,” Zhang, K., Liu, H. and Wu, J. Ed. Electrocardiographic Informatics, pp. 547-568. Beijing: Scientific and Technical Documents Publishing House, 2000. [Zad65] Zadeh, L. “Fuzzy sets,” Information and Control, 8:338-353, 1965. 45