Training Data

Neural Comput & Applic (****) **: *** ***

DOI **.1007/s00521-005-0466-z

O R I GI N A L A R T IC L E

Nurettin Ac r

Classi cation of ECG beats by using a fast least square support vector

machines with a dynamic programming feature selection algorithm

Received: 14 February 2005 / Accepted: 4 March 2005 / Published online: 14 May 2005

Springer-Verlag London Limited 2005

Abstract In this paper, we present a new system for the evaluation of ECG patterns and heart-rate variability

classi cation of electrocardiogram (ECG) beats by using signal may take several hours. In this procedure, the vol-

a fast least square support vector machine (LSSVM). ume of the data is too large, and the evaluation is tedious

Five feature extraction methods are comparatively and very time consuming. So, the possibility of the expert

examined in the 15-dimensional feature space. The missing vital information is naturally high . Therefore,

dimension of the each feature set is reduced by using several computer-based diagnostic systems are needed

dynamic programming based on divergence analysis. and proposed for contributing the clinical applications [4

After the preprocessing of ECG data, six types of ECG 6]. Recently, most of these computer-based systems are

beats obtained from the MIT-BIH database are classi- designed by using arti cial neural network (ANN) tech-

ed with an accuracy of 95.2% by the proposed fast niques [7, 8]. In this study, we have also proposed a new

LSSVM algorithm together with discrete cosine trans- system based on ANNs.

form. Experimental results show that not only the fast Feature extraction techniques for ECG beat classi -

LSSVM is faster than the standard LSSVM algorithm, cation are generally grouped into three subgroups in the

but also it gives better classi cation performance than literature [9]: direct techniques, transformation tech-

the standard backpropagation multilayer perceptron niques, parameter estimation techniques.

network. In direct techniques, the amplitudes of the raw sam-

ples are used as input vectors to perform the classi ca-

tion procedure [10, 11]. In this technique, the feature

Keywords LSSVM ECG beat classi cation

vector s dimension should be kept at a high value pro-

Feature selection Dynamic programming

viding enough information about P, Q, R, S and T

Backpropagation MLP

characteristic points. In most of these studies, dimension

reduction methods are used to simply the classi cation

structure and increase the computational performance

[12, 13]. As feature vectors are only formed by the

1 Introduction

amplitudes of the ECG signals, computational cost is

low. If R peak position is not correctly detected, the

Electrocardiogram (ECG) signal carrying valuable

amplitudes of the ECG signals in the feature space will

information about the functional aspects of the heart and

shift and vectors will scatter in the feature space and

cardiovascular system is one of the most important tools

feature vectors will be a ected. Noise also directly

in clinical applications. The recognition of the ECG beats

a ects the elements of the feature vectors.

is the main process for the diagnosis, and it is very

In transformation techniques, the samples are trans-

important task in the coronary intensive unit. Recently,

formed from original domain to another domain, and

many methods and algorithms have been proposed for the

the classi cation is performed in the transformed

classi cation of ECG signal [1, 2]. The ECG waveforms

domain. Transformation techniques are applied to the

may di er for the same patient to such an extent that they

signals to extract further information from the signal

are unlike each other and at the same time alike for dif-

that is not readily available in the raw signal. Trans-

ferent types of beats [3]. For a perfect diagnosis, the

formation methods prevent the scattering of vectors in

the feature space.

N. Ac r

The ECG signals, consisting of many data points, can

Electrical and Electronics Engineering Department,

be represented by a few features by using the transform

Nigde University, 51200 Nigde, Turkey

techniques such as Fourier transforms and wavelet

E-mail: *****@*****.***.**

300

transforms. Using a small number of features to represent motion artifacts from the subject and electrodes. After

the ECG signals is particularly important for recognition receiving signals from MIT-BIH database [17], the ECG

and diagnostic purposes [9, 14, 15]. Fourier transform, signals are ltered with bandpass of 1 100 Hz [18]. In

wavelet transform and cosine transform are the three order to detect R wave, peak detection process is em-

widely used promising techniques in feature extraction ployed on ECG data [19].

techniques in recognition/classi cation problems. A rectangular window (256 data points) is formed by

In parameter estimation techniques, after the char- centering the R peak in the QRS complex for a single

acteristic points P, Q, R, S and T are determined by ECG beat pattern. Peak-to-peak amplitudes of the ECG

using some methods [16], feature vectors are formed by signal are normalized to a value of 1 mV. Thus, it is

time intervals of the characteristic points and signal noted that classi cation decision does not depend on the

amplitudes at these points. maximum amplitude of the ECG records. Mean value of

In the present study, the ECG signals obtained from ECG signal in the window is xed to zero value by

the MIT-BIH database [17] were classi ed using a fast subtracting mean value from original signal. Thus, o set

least square support vector machine (LSSVM) with the e ect is cancelled out.

dynamic programming (DP) feature selection algorithm.

Five feature vectors from each type of ECG beat are

extracted and comparatively examined by performing 2.2 Feature extraction and selection

LSSVM and standard backpropagation multilayer per-

ceptron (MLP) networks. The dimension of each feature A window, which is formed by 256 data points, is

vectors is reduced by using DP based on divergence selected for a single ECG beat pattern. For six classes,

analysis. In this study we used six types of ECG beats training set is formed by choosing 1,440 vectors (240

(normal beat, left bundle branch block beat, congestive vectors for each class) of 256 dimensions from the MIT-

heart failure beat, premature ventricular contraction BIH database [17]. Seven hundred and twenty vectors

beat, non-conducted P-wave, ventricular escape beat) (120 vectors from each class) are used for testing pro-

obtained from the MIT-BIH database. cedure. We have also created a cross validation set for a

The outline of the paper is as follows: In Sect. 2, we better generalization. It is composed of 288 vectors (48

present methods including preprocessing, feature vectors from each class, about 20% of training set)

extraction and selection procedures. In Sect. 3, the chosen from training set randomly. In addition, in order

LSSVM with a fast algorithm and MLP with back- to have a better generalization ability of the proposed

propagation algorithm are presented, respectively, as system, the training and testing sets are formed from

nonlinear classi ers. The experimental results are also di erent subjects records. Vectors in the training set are

presented in Sect. 3. Results and discussions are normalized and then features for each normalized vector

presented in Sect. 4. Finally, conclusion is presented in are extracted. After the feature vectors are selected by

Sect. 5. using DP, they are fed to the ANN as input vectors for

training and testing procedures.

In this study, the best ECG features among all the

extracted ones are searched by DP according to the

2 Methods

divergence values. The problem of selecting the subset of

best d features from a given set of n features (d

Decision making is performed in three stages: prepro-

straightforward solution, which is of an exhaustive

cessing, feature extraction/selection and ANN as a

search. One can form all possible di erent combinations

classi er. Figure 1 shows the block diagram of the

of d out of n features; for each one the measure of sep-

classi cation system.

arability can be calculated and best set selected.

Unfortunately, such an exhaustive search method is

impossible for large n and d because of the amount of

2.1 Preprocessing

calculations required. Therefore a dynamic program-

ming algorithm [20] with divergence analysis is used in

The ECG waveforms contain 60 Hz artifacts owing to

this study. Divergence analysis gives information about

power-line interferences, EMG artifacts from muscles,

Fig. 1 Block diagram

of the classi cation system.

DFT discrete Fourier

transform, DCT discrete cosine

transform, DWT discrete

wavelet transform, AAR

adaptive autoregressive

301

the distribution of the class vectors in the feature space. coe cients containing the most energy, a subset of the

As the class vectors arbitrarily scatter, the divergence best 15 coe cients is searched by using DP according to

value decreases. Divergence value is computed as fol- the divergence values. The frequency-based elements of

lows [20]. First, within class scatter matrix is de ned as: each feature vector are ordered as follows:

k1 k2 k3 k4 k5 k6 k7 k8 k9 k10 k11 k12 k13 k14 k15

c2 c7 c35 c12 c1 c5 c10 c14 c37 c4 c16 c32 c41 c22 c43

k=[k1, k2, k15] is the 15-dimensional new feature

X

F nj lj F nj lj T ;

Wi j j 1; . . . ; C 1

^i ^i vector. c=[c1, c2, c256] is a vector representing the

i i

DFT coe cients.

n

The feature extraction of the third feature set involves

where C (C=6 in this study) is the number classes, F j isi

the discrete cosine transform (DCT) coe cients of ECG

the i-th dimensional feature vector of the j-th class (i=15

data. From calculated DCT coe cients, the 15 DCT

in this study), lj is the mean vector of the feature vectors

^i

coe cients are selected by using dynamic programming.

of the j-th class, and the summation is performed over

The ordering of the elements in terms of signi cance

all training samples available for the j-th class.

level for DCT coe cients is as follows:

Then, let us de ne between class scatter matrix;

k1 k2 k3 k4 k5 k6 k7 k8 k9 k10 k11 k12 k13 k14 k15

c1 c23 c3 c6 c16 c11 c14 c2 c7 c26 c9 c31 c28 c13 c32

k=[k1, k2, k15] is the 15-dimensional new feature

X

C

vector. c=[c1, c2, c256] is a vector that represents

l k T ;

Bj l j lk lj

j 1; . . . ; C 2

^i ^i ^i ^i the DCT coe cients.

i

k 1

The feature extraction of fourth feature set involves

the DWT of ECG data. Feature vectors are formed

For each j-th class, the divergence is

using Daubechies-2 wavelet [21]. For each feature vec-

1

Dj tr Wij Bj tor, wavelet approximation coe cients at the second,

3

i i

third and fourth levels (66+34+18=118) are calcu-

where Dj is the i-th divergence value for j-th class. lated. Among 118 DWT approximation coe cients, a

i

subset of 15 DWT coe cients are determined. Dynamic

Divergence analysis determines the best features,

programming search in this feature set showed the

which increases the classi cation performance and also

fourth level DWT approximation coe cients to be more

it gives information to determine the dimension of the

signi cant than the others.

feature vectors.

k1 k2 k3 k4 k5 k6 k7 k8 k9 k10 k11 k12 k13 k14 k15

3 10 9 5

a44 a24 14

a14 6 16 7 8 15 13

a114

a a a a a a a a a a a

4 4 4 4 4 4 4 4 4 4 4

k=[k1, k2,, k15] and a a1 ; a2 ; . . . ; a66 ; a1 ; a2 ; . . . ;

The feature extraction of the rst feature set involves 22 33

2

a34 ; a1 ; a2 ; . . . ; a18 where a is a vector representing the

the amplitude values of data. In this direct method 44

3 4

procedure, the number of samples is reduced to 16 as DWT approximation coe cients at second, third and

follows: fourth levels and k represents 15-dimensional new fea-

ture vector. We also repeated the same procedure for

1X 16

di erent wavelet types such as Symmlet of order 2,

sj x i j 1 16 ; j 1; 2; . . . ; 16 4

Coi et of order 2, Daubechies of order 1 and 6. But the

16 i 1

best result is obtained for Daubechies-2.

x(1), x(2), x(256) are the samples of the original Fifth feature set is created by using AAR estimation

ECG pattern, and sj is the j-th element of the new feature method [22]. Conventional autoregressive methods are

vector formed by taking the average of every 16 samples appropriate if the signal does not change with time, but

of the original ECG signal. Computation time is also in real situations, the ECG signal is under the in uence of

decreased by reducing the number of samples for rst several factors that is impossible to control. Therefore,

feature set. block AR methods may not track the slow change in the

The second feature extraction method involving the spectrum of non-stationary signal, as is the case of ECG

discrete Fourier transform (DFT) of a window of data signals. Here, the limitation of AR methods is overcome

length 256 data points around the R-peak is applied for by estimating the AR parameters adaptively by using

creating the second feature set. From calculated DFT least mean square method [23] for each sample (Fig. 2).

302

Here, AAR coe cients are calculated for each raw support vectors. The architecture of the SVM is shown

feature vectors (256 data points length). The optimal in Fig. 3.

order of AAR model is obtained as 15 by using Akaike For a linearly separable binary classi cation problem,

the construction of a hyperplane is wT x+b=0 so that

criterion [22]. Thus, the input dimension of each feature

vector is automatically reduced to 15. Although the the margin between the hyperplane and the nearest point

dimension of feature vector is equal to 15, we search the is maximized and can be posed as the following qua-

signi cance of coe cients by using DP algorithm. The dratic optimization problem [24]:

ordering of the elements for each feature vector is as

follows:

k1 k2 k3 k4 k5 k6 k7 k8 k9 k10 k11 k12 k13 k14 k15

c2 c4 c6 c15 c8 c11 c1 c12 c3 c5 c7 c13 c14 c9 c10

k=[k1, k2, k15] is the 15-dimensional new feature

1

vector in a signi cance order. c=[c1, c2, c15] is a min wT w 5

w2

vector that represents AAR coe cients. Here, AAR

coe cients can also be evaluated as nite impulse re- subject to

sponse lter coe cients.

d i wT xi b ! 1

Consequently, the best features for ve di erent with i 1; . . . ; N 6

feature sets are determined by using DP based on

where d 2{ 1, 1 } stands for the i th desired output, xi

i

divergence analysis. Thus, not only the system is opti-

2RP stands for the i th input sample of the training data

mized for having the best performance but also the input N

set fxi ; d i gi 1 : Equation 6 forces a rescaling on (w,b) so

dimension is reduced. So, computing time is drastically

that the point closest to the hyperplane has a distance of

reduced and the network has become simple.

1=kwk [24]. Maximizing the margin corresponds to

minimizing the Euclidean norm of the weight vector.

Often in practice, a separating hyperplane does not exist.

3 Classi cation

Hence the constraint (6) is relaxed by introducing slack

variables ni ! 0; i 1; . . . ; N : The optimization prob-

In this study, a fast LSSVM is proposed for ECG beat

lem now becomes as follows (for a user-de ned positive

classi cation. We also present standard backpropaga-

nite constant C):

tion MLP network for a comparison between the per-

formance of LSSVM with a fast algorithm and MLP XN

1

min wT w C

network with standard backpropagation algorithm. So, 7

ni

w ;n 2

they are comparatively examined for ECG beat classi- i 1

cation.

subject to

d i wT xi b ! 1 ni ; 8

3.1 Matrix representation of LSSVM

for a fast algorithm ni ! 0 with i 1; . . . ; N 9

Support vector machine (SVM) is a powerful technique The C controls the tradeo between the complexity of

for solving supervised classi cation problems and is very the machine and the number of non-separable points; it

useful due to its generalization ability. In essence, such may therefore be viewed as a form of a regularization

an approach maximizes the margin between the training parameter.

data and the decision boundary, which can be cast as a By introducing Lagrange multipliers a i and using the

quadratic optimization problem. The subsets of patterns Karush-Kuhn-Tucker theorem of optimization theory

that are closest to the decision boundary are called [25], the solution is given by;

Fig. 2 Block diagram of the

adaptive linear estimator

303

Fig. 3 Architecture of the

SVM. Here, K is a kernel

function, M is the number of

support vectors and p is the

input dimension

X

N The corresponding Lagrangian for Eq. 13 is,

d i ai xi

w 10

cX 2N

1

i 1

L w; b; e; a wT w e

2 i 1 i

2

The non-zero a i s correspond to the so-called sup-

X

port vectors xi that help to de ne the boundary between N

a i d i wT x i b 1 e i

15

the two classes. All other training examples with corre-

i 1

sponding zero a i values are now rendered irrelevant and

automatically satisfy constraint (8) with n i=0. The As shown in [26], the optimality condition leads to

hyperplane decision function can be written, for the the following (N+1) (N+1) linear system:

vector x, as follows: ! !

DT 0

b

0

! 16

D ZZT c 1 I a

X 1

N

d i a i x T x i b

f x sgn 11

where ZT = [ d1 x1, d2 x2, dN xN ], DT = [ d1, d2,

i 1

dN ], 1T = [ 1, 1, 1 ] and aT a1 ; a2 ; . . . ; aN :

To allow for more general decision surfaces, the inner We now observe that it is in fact only necessary to

product = xT xi can simply be replaced by a invert the N N matrix

suitable kernel function K . The decision function, for

the vector x, then becomes: A c 1 I ZZT 17

XN

and

d i ai K x; xi b

f x sgn 12

bD Aa 1 18

i 1

By replacing the inner products with kernel functions, Then we can write;

the input data are mapped to a higher dimensional

a A 1 1 bD 19

space. It is then in this higher dimensional space that a

separating hyperplane is constructed to maximize the 1

T

DA 1

where b DT A 1 D

margin. In the lower dimensional data space, this

Solving Eq. 19 still requires the inversion of an N N

hyperplane becomes a non-linear separating function.

matrix which is prohibitive when N is large and indeed

Up till now, we formulated standard SVM classi er

the large matrix A is not even easily stored for really

algorithm. Recently, Suykens and Vandewalle [26] have

large N. We now observe that the matrix (17) is of a

modi ed standard SVM classi er into the following

special form and when the number of features k is much

LSSVM formulation:

less than the number of data points N, k

Contact this candidate