##
Bulanık (Fuzzy) sınıflayıcılarla EKG şekil bozukluklarının belirlenmesi

Bulanık (Fuzzy) sınıflayıcılarla EKG şekil bozukluklarının belirlenmesi

##### Dosyalar

##### Tarih

1995

##### Yazarlar

Dokur, Zümray

##### Süreli Yayın başlığı

##### Süreli Yayın ISSN

##### Cilt Başlığı

##### Yayınevi

Fen Bilimleri Enstitüsü

Institute of Science and Technology

Institute of Science and Technology

##### Özet

Kalple ilgili oluşabilecek rahatsızlıkları önceden tespit etmek insan sağlığı açısından son derece önemlidir. Oluşabilecek kalp rahatsızlıkları ile ilgili bilgiler EKG kayıtlarından iki tip inceleme ile elde edilir: EKG şekil bozukluğu, ritim bozukluğu. Ancak bu bilgilerin elde edilmesi için uzun EKG (bir günü aşan) kayıtlarına ihtiyaç vardır. EKG kayıtlarında bir program kontrolü olmadan şekil bozukluklarını aramak uzun zaman almaktadır. Tez içerisinde EKG işaretindeki şekil bozukluklarının^ hızlı ve otomatik olarak tespit edilmesi sağlanmıştır. Çalışma içerisinde, öncelikle EKG işaretinden QRS kompleksi tespit edilir, daha sonra bu kompleks içinde R tepesinin yeri bulunur. Çalışma içerisinde literatürde kullanılan 4 farklı tip özellik vektörü elde etme yöntemi incelenmiştir: 1) QRS şekil bilgisi kullanılarak özellik vektörünün elde edilmesi, 2) 0-30 Hz arasında frekans bandı kullanılarak özellik vektörünün elde edilmesi, 3) Lineer tahmin katsayıları (Lineer Prediction Coefficients, LPCs ) kullanılarak özellik vektörünün elde edilmesi, 4) R tepesi etrafındaki EKG genlikleri kullanılarak özellik vektörlerinin elde edilmesi. Birinci ve dördüncü tip özellik elde etme yöntemlerinin R tepesinin yerine çok bağlı olduğu gözlenmiştir. Ancak bu iki yöntem ile özellik vektörleri daha hızlı elde edilebilmektedir. Diğer özellik elde etme yöntemleri R tepesinin yerinin yanlış belirlenmesinden etkilenmez; ancak hesaplama yükü diğer yöntemlere göre daha uzundur..- Çalışma içerisinde, EKG kayıtlarını izleyen kişiye daha fazla bilgi verdiği için bulanık sınıf layıcılarm kullanılması tercih edilmiştir. iki farklı bulanık smıflayıcı incelenmiştir: Bulanık K-en yakın komşu sınıf layıcısı ve bulanık en yakın model sınıf layıcısı. Bulanık sınıf layıcılarm öz-vektörlerinin elde edilmesi için iki farklı öğrenme algoritması kullanılmıştır: Bulanık küme-ortalar (fuzzy c-means) algoritması ve bulanık Kohonen kümeleme algoritması.. öğrenme sırasında eğitim kümesi, üç değişik hastadan alman EKG kayıtları içerisinden, her sınıftan 15 vektör alınmak suretiyle, dört farklı sınıf için 4*15 vektörden meydana getirilmiştir.

As the ECG has considerable diagnostic significance, it is important to detect and display shape changes on the ECG recordings fast and automatically. In this study, shape detection was performed by fuzzy classifiers. A fuzzy classifier searches for the membership of each ECG recording to all of the classes and presents the information held by the membership degrees to the decision of the cardiologist to make diagnosis. The hard classifier searches for the unique class that the ECG recording belongs to. Two types of classifiers are used in this study: Fuzzy nearest prototype (fuzzy NP) classifier and fuzzy K nearest neighbour classifier (fuzzy K-NN). All the evaluations in this study are performed on the MIT-BIH Arrhythmia Database. The database consists of 48 half-hour recordings for a total of 24h of ECG data. It provides a standardized means of comparing the basic performances of the algorithms used in this thesis and in other studies. Before the classification, at the first step of the study, R peaks of the QRS complexes are detected. After the detection of R peaks, feature vectors are formed by 4 different methods: Linear Prediction Coefficients (LPCs) method, QRS shape information, amplitudes of the significant frequencies on the frequency spectrum, and directly using the amplitudes of the ECG signal. Feature vectors obtained by the preceding methods constituting the training sets of 4 different classes are used in the learning process. In this process, fuzzy c-means and fuzzy Kohonen clustering algorithms are used to obtain the cluster prototypes. Learning is completed after the formation of the prototypes. After these processes, fuzzy classification of the feature vectors belonging to the test set is performed. Successful results are obtained for the four different classes by the two fuzzy classifiers. QRS detection is the first stage of signal processing in which pattern recognition is important. Detection of the QRS is difficult, not only because of the physiological variability of the QRS complexes, but also because of the various types of noise that can be present in the ECG signal. Noise sources include muscle noise, artifacts due to electrode motion, power-line interference, baseline wander, and T waves with high frequency characteristics similar to QRS complexes. In our approach, digital filters reduce the influence of these noise sources, and thereby improve the signal-to-noise ratio. Software QRS detectors typically include one or more three types of processing steps: Linear digital filtering, nonlinear transformation, and decision rule algorithms. We use all three types, in order to enhance the QRS complexes while suppressing noise artifact, baseline wander and non- QRS portions of the ECG. Linear processes include a band pass filter (BPF), a high-pass filter (HPF), a low-pass filter (LPF), and a moving window integrator. The nonlinear information that we use is signal amplitude squaring. The linear and nonlinear units all form the preprocessing stage of QRS detection. The output of the preprocessor stage is presented to a decision rule that declares a QRS detection if the preprocessor output exceeds a threshold. The most common rule is a simple amplitude threshold, and in this study, the threshold level is started at some nominal level (based on past history), and then is lowered systematically. The QRS detector is illustrated in fig 1. JL HPF BPF SQR. LPF I1T, 12T DBLAr MDLT. Fig 1: The QRS detector. In this study, normalized analog filters are used to design the digital filters. A normalized analog filter is a low-pass filter with a cutoff frequency of 1 Hz. By. using this filter, other required filters can be designed. Bilinear transformation is used for the transformation from analog filters to digital ones. The bilinear transfer -vii- relation is as follows (T is the sampling period) 2 1-z"1 a - T l+z *i First, in order to restore the baseline, the signal passes through a digital high-pass filter with a cutoff frequency of 2 Hz. The transfer function for this high-pass filter is: T (z) »-Iİ5İ. = 0-976-1.952z-1 + 0.976z-2 H = u(z) " ı-ı^siz^ + cgsaz-2 The difference equation is: y(k) = 1.951y(k-l) - 0.952y(k-2) + 0.976u(k) - 1.952u(k-l) + 0.976u(k-2) The output of the high-pass filter is processed in two different branches, and the outputs of these branches are fed into a multiplier. On one of these branches, the output of the high-pass filter is given to a band-pass filter with a center frequency of 17 Hz which is the main frequency of the QRS complex. BPF reduces the influence of muscle noise, 50 Hz interference, and T-wave interference. The transfer function of the band-pass filter is: T (z) = Y(z) = 0.0337 - 0.0337Z-2 B " U(z) i - 1.849Z"1 + 0.933Z'2 The difference equation is: y(k) =1.849y(k-l) - 0.933y(k-2) + 0.0337u(k) - 0.0337u(k-2) The output of the BPF is processed in the squaring unit. The signal is squared point by point. The equation of this operation is: y(k) = x(k)2 This makes all data points positive and does nonlinear amplification of" the output of the band-pass filter emphasizing the higher frequencies (i.e., predominantly the ECG frequencies). The next process after squaring is moving window integration. The purpose of moving window integration is to obtain wave-form feature information in addition to the slope of the R wave. It is calculated from -viii- y(k) = (l/N). [x(k-(N-l)) + x(k-(N-2)) + + x(k)] where N is the number of samples in the width of the integration window. The width of the window is determined empirically. For our sample rate of 360 samples/s, the window is 30 sample wide. On the other branch; the output of the high-pass filter is given to a digital low-pass filter with a cutoff frequency of 36 Hz to reduce the high-frequency noise present in the ECG signal. This filter is designed directly in the z domain. Its transfer function is:,"(,) = ; (1 - z-1) x k = (sampling frequency) / (cutoff frequency) In this study k is 10 according to k=360/36=10. 1 is chosen as 2. Tt(z) - Y(z) = 1 - 2z-10 + z-20 U(z) " i - 2z-1 + z-2 The difference equation is: y(k) = 2y(k-l) - y(k-2) + u(k) - 2u(k-10) + u(k-20) The output of the low-pass filter is delayed by the total processing time of the detection algorithm. It is chosen empirically as 12T. y(k) = x(k-12) The outputs of the integration and delay units are multiplied and then presented to the decision rule (amplitude threshold) which declares a QRS detection if the output of the multiplier exceeds a threshold. After detecting the QRS complex, the maximum amplitude in this complex is taken as the R peak. This process, detection of R peak in the ECG signal is very important. After the detection of the QRS complex and the R peak, feature extraction process is started. A common question that arises in connection with clustering and classification concerns the constitution of data space. Features (or characteristics) of data item x^GX must be sufficiently representative of the physical -ix- process to enable us to construct realistic clusters or classifiers. By discarding, modifying, enriching and transforming some features of Xl, we need to construct the "right" data space. In feature selection, we search for internal structure in data items: the goal is to improve their usefulness as constituents of data sets for clustering and/or classification. In short, we hope to identify the "best" data space by looking for structure within its elements. In this thesis, feature selection is made by using four different methods: 1 ) Feature vectors are formed by using the shape information of the QRS complex. The features are: a) Duration, the width of the QRS complex in milliseconds. b) Height, the difference between the maximum and the minimum points of the QRS complex. c) The area above the baseline within the QS duration. d) I (Baseline) - (Height/2) I All these parameters highly depend on the position of the R peak in the QRS complex. 2) Amplitudes of the significant frequencies on the frequency spectrum are used to form the feature vectors. After the detection of the R peak in the QRS complex, a window of 256 samples is formed in the vicinity of the R peak. Frequency analysis is made by using the 0-30 Hz frequency band. Amplitude values are used on the frequency spectrum. The following equation is used for the frequency analysis : 255 -j2n-f -k x(f) = ]£x(k)e N The dimension of the feature vector is 30. Feature vectors obtained by this method are not affected by high frequency noises, and the frequency amplitude values are not dependant on the position of the R peak. Misdetection of the R peak is taken as a delay and does not affect the parameters of the feature vectors. -x- 3) Linear Prediction Coefficients (LPCs) method. Linear prediction coefficients (LPCs) computed for an average cardiac complex are used for feature vector construction. The choice of LPCs method was not accidental. LPCs are almost insensitive to high frequency noise. Also, each LPC depends from the whole signal, i.e., it carries some sort of information about the signal, not just a local one as conventional features do. Both facts justify an expectation of much higher robustness when classifying with LPCs. The position of the R peak does not affect the linear prediction coefficients, and the number of parameters representing the signal is small. In this study 6 coefficients are used as the parameters of the feature vectors 4) The amplitudes of the ECG signal are used directly for feature vector formation. A window containing only one QRS complex is formed by taking 24 points from the left side of the R peak, and 24 points from the right side of it. In this way a feature vector of 48 parameters is obtained. The parameters of the vector highly depend on the position of the R peak. As no preprocessing is required before feature selection, classification is performed in less t i-me. Feature vectors obtained by the preceding methods constituting the training sets of four different classes (ECG shape changes) are used in the learning process. There are 4*1.5 feature vectors in the training set, 15 feature vectors coming from each class. Class prototypes which will be given as inputs to the classifiers are formed during learning. In order to obtain the cluster prototypes during the learning process fuzzy c-means and fuzzy Kohonen clustering algorithms (FKCA) are used. Fuzzy c-means algorithm gives optimal results when the number of the clusters in a class is known a priori. But it is difficult to estimate the number of clusters, especially when one is studying in a multi-dimensional (>2) space. A second algorithm used in this thesis to obtain the cluster prototypes is the fuzzy Kohonen clustering algorithm. Kohonen clustering networks (KCNs) are used for clustering. -xi- Learning is completed after the formation of the cluster prototypes. In this study 4 prototypes are obtained by the fuzzy c-means algorithm and 8 prototypes (class number*k, k any positive number) by the fuzzy Kohonen clustering algorithm. After these processes, fuzzy classification of the feature vectors belonging to the test set is performed. Two types of classifiers are used in this study: Fuzzy nearest prototype classifier and fuzzy K nearest neighbour classifier. The nearest neighbour classifiers require no preprocessing of the labeled sample set prior to their use. The crisp nearest-neighbour classification rule assigns an input sample vector y, which is of unknown classification, to the class of its nearest neighbour. This idea can be extended to the K-nearest neighbours with the vector y being assigned to the class that is represented by a majority amongst the K-nearest neighbours. The sample vector is assigned to the class, for which the sum of distances from the sample to each neighbour in the class is a minimum. While the fuzzy K-nearest neighbour procedure is also a classification algorithm the form of its results differ from the crisp version. The fuzzy K-nearest neighbour algorithm assigns class membership to a sample vector rather than assigning the vector to a particular class. In addition, the vector's membership values should provide a level of assurance to accompany the resultant classification. For example, if a vector is assigned 0.9 membership in one class and 0.05 membership in two other classes we can be reasonably sure the class of 0.9 membership is the class to which the vector belongs. On the other hand, if a vector is assigned 0.55 membership in class one, 0.44 membership in class two, and 0.01 membership in class three, then we should be hesitant to assign the vector based on these results. However, we can feel confident that it does not belong to class three. In such a case the vector might be examined further to determine its classification, because the vector exhibits a high degree of membership in both classes one and two. Clearly the membership assignments produced by the algorithm can be useful in the classification process. The basis of the algorithm is to assign membership as a function of the vector's distance from its K-nearest neighbours and those neighbours' memberships in the possible classes. The fuzzy algorithm is similar to the crisp version in the sense that it must also search the labeled sample set for the K-nearest neighbour. The labeled samples can be assigned class memberships in several ways. First, they can be given complete -xii- membership in their known class and nonmembership in all other classes. Other alternatives are to assign the samples' membership based on distance from their class mean or based on the distance from labeled samples of their own class and those of the other class or classes, and then to use the resulting memberships in the classifier. An alternate scheme for assigning initial memberships based on a learning scheme is also considered in this thesis. Two different methods are used in order to form the prototypes of the fuzzy K-NN classifier. First, the training set is completely used as the class prototypes and their memberships are assigned by the fuzzy c-means algorithm. Second, class prototypes are formed by using fuzzy Kohonen clustering algorithm and crisp memberships (1, complete membership; 0, nonmembership) are assigned to these vectors. The second classifier used in this study is the fuzzy nearest prototype classifier. These nearest prototype classifiers bear a marked resemblance to the one-nearest neighbour classifier. Actually, the only difference is that for the nearest prototype classifier the labeled samples are a set of class prototypes, whereas in the nearest neighbour classifier we use a set of labeled samples that are not necessarily prototypical. In this study, fuzzy c-means algorithm is used for the formation of the class prototypes. In the fuzzy NP algorithm, membership in each class is assigned based only on the distance from the prototype of the class. The fuzzy K-nearest neighbour and fuzzy nearest prototype classifiers developed and investigated in this thesis show useful results. By using these classifiers, we obtain a measure of how "typical" the object is of each class. Memberships obtained by these classifiers do provide a useful level of confidence of classification. The nearest prototype classifier is the quickest and simplest of the classifiers considered. The reason is that in this algorithm, an unknown sample is compared to one prototype per class as opposed to the K-nearest neighbour algorithms, where an entire set of labeled samples representing each class must be compared before the K nearest are obtained. The two of the learning algorithms used in this study give successful results for the formation of the prototypes that represent the normal beat, left bundle branch block beat and the paced beat shape changes. As the PVC type shape change is represented by more than one cluster in the feature space, its prototypes can not be formed correctly by the fuzzy c-means algorithm. For this reason, fuzzy nearest prototype classifier which uses the prototypes -xiii- formed by the fuzzy c-means algorithm, classifies the PVC by a low success rate. As the fuzzy Kohonen algorithm represents the shape changes by more than one prototype, it gives better results compared to the fuzzy c-means algorithm, especially for the PVC type shape change. Fuzzy K-NN classifier gives better results compared to the fuzzy NP classifier for it uses more than one prototype for each class. The results presented in this thesis were produced by software implementation of the algorithms. The software was developed using C language on PC.

As the ECG has considerable diagnostic significance, it is important to detect and display shape changes on the ECG recordings fast and automatically. In this study, shape detection was performed by fuzzy classifiers. A fuzzy classifier searches for the membership of each ECG recording to all of the classes and presents the information held by the membership degrees to the decision of the cardiologist to make diagnosis. The hard classifier searches for the unique class that the ECG recording belongs to. Two types of classifiers are used in this study: Fuzzy nearest prototype (fuzzy NP) classifier and fuzzy K nearest neighbour classifier (fuzzy K-NN). All the evaluations in this study are performed on the MIT-BIH Arrhythmia Database. The database consists of 48 half-hour recordings for a total of 24h of ECG data. It provides a standardized means of comparing the basic performances of the algorithms used in this thesis and in other studies. Before the classification, at the first step of the study, R peaks of the QRS complexes are detected. After the detection of R peaks, feature vectors are formed by 4 different methods: Linear Prediction Coefficients (LPCs) method, QRS shape information, amplitudes of the significant frequencies on the frequency spectrum, and directly using the amplitudes of the ECG signal. Feature vectors obtained by the preceding methods constituting the training sets of 4 different classes are used in the learning process. In this process, fuzzy c-means and fuzzy Kohonen clustering algorithms are used to obtain the cluster prototypes. Learning is completed after the formation of the prototypes. After these processes, fuzzy classification of the feature vectors belonging to the test set is performed. Successful results are obtained for the four different classes by the two fuzzy classifiers. QRS detection is the first stage of signal processing in which pattern recognition is important. Detection of the QRS is difficult, not only because of the physiological variability of the QRS complexes, but also because of the various types of noise that can be present in the ECG signal. Noise sources include muscle noise, artifacts due to electrode motion, power-line interference, baseline wander, and T waves with high frequency characteristics similar to QRS complexes. In our approach, digital filters reduce the influence of these noise sources, and thereby improve the signal-to-noise ratio. Software QRS detectors typically include one or more three types of processing steps: Linear digital filtering, nonlinear transformation, and decision rule algorithms. We use all three types, in order to enhance the QRS complexes while suppressing noise artifact, baseline wander and non- QRS portions of the ECG. Linear processes include a band pass filter (BPF), a high-pass filter (HPF), a low-pass filter (LPF), and a moving window integrator. The nonlinear information that we use is signal amplitude squaring. The linear and nonlinear units all form the preprocessing stage of QRS detection. The output of the preprocessor stage is presented to a decision rule that declares a QRS detection if the preprocessor output exceeds a threshold. The most common rule is a simple amplitude threshold, and in this study, the threshold level is started at some nominal level (based on past history), and then is lowered systematically. The QRS detector is illustrated in fig 1. JL HPF BPF SQR. LPF I1T, 12T DBLAr MDLT. Fig 1: The QRS detector. In this study, normalized analog filters are used to design the digital filters. A normalized analog filter is a low-pass filter with a cutoff frequency of 1 Hz. By. using this filter, other required filters can be designed. Bilinear transformation is used for the transformation from analog filters to digital ones. The bilinear transfer -vii- relation is as follows (T is the sampling period) 2 1-z"1 a - T l+z *i First, in order to restore the baseline, the signal passes through a digital high-pass filter with a cutoff frequency of 2 Hz. The transfer function for this high-pass filter is: T (z) »-Iİ5İ. = 0-976-1.952z-1 + 0.976z-2 H = u(z) " ı-ı^siz^ + cgsaz-2 The difference equation is: y(k) = 1.951y(k-l) - 0.952y(k-2) + 0.976u(k) - 1.952u(k-l) + 0.976u(k-2) The output of the high-pass filter is processed in two different branches, and the outputs of these branches are fed into a multiplier. On one of these branches, the output of the high-pass filter is given to a band-pass filter with a center frequency of 17 Hz which is the main frequency of the QRS complex. BPF reduces the influence of muscle noise, 50 Hz interference, and T-wave interference. The transfer function of the band-pass filter is: T (z) = Y(z) = 0.0337 - 0.0337Z-2 B " U(z) i - 1.849Z"1 + 0.933Z'2 The difference equation is: y(k) =1.849y(k-l) - 0.933y(k-2) + 0.0337u(k) - 0.0337u(k-2) The output of the BPF is processed in the squaring unit. The signal is squared point by point. The equation of this operation is: y(k) = x(k)2 This makes all data points positive and does nonlinear amplification of" the output of the band-pass filter emphasizing the higher frequencies (i.e., predominantly the ECG frequencies). The next process after squaring is moving window integration. The purpose of moving window integration is to obtain wave-form feature information in addition to the slope of the R wave. It is calculated from -viii- y(k) = (l/N). [x(k-(N-l)) + x(k-(N-2)) + + x(k)] where N is the number of samples in the width of the integration window. The width of the window is determined empirically. For our sample rate of 360 samples/s, the window is 30 sample wide. On the other branch; the output of the high-pass filter is given to a digital low-pass filter with a cutoff frequency of 36 Hz to reduce the high-frequency noise present in the ECG signal. This filter is designed directly in the z domain. Its transfer function is:,"(,) = ; (1 - z-1) x k = (sampling frequency) / (cutoff frequency) In this study k is 10 according to k=360/36=10. 1 is chosen as 2. Tt(z) - Y(z) = 1 - 2z-10 + z-20 U(z) " i - 2z-1 + z-2 The difference equation is: y(k) = 2y(k-l) - y(k-2) + u(k) - 2u(k-10) + u(k-20) The output of the low-pass filter is delayed by the total processing time of the detection algorithm. It is chosen empirically as 12T. y(k) = x(k-12) The outputs of the integration and delay units are multiplied and then presented to the decision rule (amplitude threshold) which declares a QRS detection if the output of the multiplier exceeds a threshold. After detecting the QRS complex, the maximum amplitude in this complex is taken as the R peak. This process, detection of R peak in the ECG signal is very important. After the detection of the QRS complex and the R peak, feature extraction process is started. A common question that arises in connection with clustering and classification concerns the constitution of data space. Features (or characteristics) of data item x^GX must be sufficiently representative of the physical -ix- process to enable us to construct realistic clusters or classifiers. By discarding, modifying, enriching and transforming some features of Xl, we need to construct the "right" data space. In feature selection, we search for internal structure in data items: the goal is to improve their usefulness as constituents of data sets for clustering and/or classification. In short, we hope to identify the "best" data space by looking for structure within its elements. In this thesis, feature selection is made by using four different methods: 1 ) Feature vectors are formed by using the shape information of the QRS complex. The features are: a) Duration, the width of the QRS complex in milliseconds. b) Height, the difference between the maximum and the minimum points of the QRS complex. c) The area above the baseline within the QS duration. d) I (Baseline) - (Height/2) I All these parameters highly depend on the position of the R peak in the QRS complex. 2) Amplitudes of the significant frequencies on the frequency spectrum are used to form the feature vectors. After the detection of the R peak in the QRS complex, a window of 256 samples is formed in the vicinity of the R peak. Frequency analysis is made by using the 0-30 Hz frequency band. Amplitude values are used on the frequency spectrum. The following equation is used for the frequency analysis : 255 -j2n-f -k x(f) = ]£x(k)e N The dimension of the feature vector is 30. Feature vectors obtained by this method are not affected by high frequency noises, and the frequency amplitude values are not dependant on the position of the R peak. Misdetection of the R peak is taken as a delay and does not affect the parameters of the feature vectors. -x- 3) Linear Prediction Coefficients (LPCs) method. Linear prediction coefficients (LPCs) computed for an average cardiac complex are used for feature vector construction. The choice of LPCs method was not accidental. LPCs are almost insensitive to high frequency noise. Also, each LPC depends from the whole signal, i.e., it carries some sort of information about the signal, not just a local one as conventional features do. Both facts justify an expectation of much higher robustness when classifying with LPCs. The position of the R peak does not affect the linear prediction coefficients, and the number of parameters representing the signal is small. In this study 6 coefficients are used as the parameters of the feature vectors 4) The amplitudes of the ECG signal are used directly for feature vector formation. A window containing only one QRS complex is formed by taking 24 points from the left side of the R peak, and 24 points from the right side of it. In this way a feature vector of 48 parameters is obtained. The parameters of the vector highly depend on the position of the R peak. As no preprocessing is required before feature selection, classification is performed in less t i-me. Feature vectors obtained by the preceding methods constituting the training sets of four different classes (ECG shape changes) are used in the learning process. There are 4*1.5 feature vectors in the training set, 15 feature vectors coming from each class. Class prototypes which will be given as inputs to the classifiers are formed during learning. In order to obtain the cluster prototypes during the learning process fuzzy c-means and fuzzy Kohonen clustering algorithms (FKCA) are used. Fuzzy c-means algorithm gives optimal results when the number of the clusters in a class is known a priori. But it is difficult to estimate the number of clusters, especially when one is studying in a multi-dimensional (>2) space. A second algorithm used in this thesis to obtain the cluster prototypes is the fuzzy Kohonen clustering algorithm. Kohonen clustering networks (KCNs) are used for clustering. -xi- Learning is completed after the formation of the cluster prototypes. In this study 4 prototypes are obtained by the fuzzy c-means algorithm and 8 prototypes (class number*k, k any positive number) by the fuzzy Kohonen clustering algorithm. After these processes, fuzzy classification of the feature vectors belonging to the test set is performed. Two types of classifiers are used in this study: Fuzzy nearest prototype classifier and fuzzy K nearest neighbour classifier. The nearest neighbour classifiers require no preprocessing of the labeled sample set prior to their use. The crisp nearest-neighbour classification rule assigns an input sample vector y, which is of unknown classification, to the class of its nearest neighbour. This idea can be extended to the K-nearest neighbours with the vector y being assigned to the class that is represented by a majority amongst the K-nearest neighbours. The sample vector is assigned to the class, for which the sum of distances from the sample to each neighbour in the class is a minimum. While the fuzzy K-nearest neighbour procedure is also a classification algorithm the form of its results differ from the crisp version. The fuzzy K-nearest neighbour algorithm assigns class membership to a sample vector rather than assigning the vector to a particular class. In addition, the vector's membership values should provide a level of assurance to accompany the resultant classification. For example, if a vector is assigned 0.9 membership in one class and 0.05 membership in two other classes we can be reasonably sure the class of 0.9 membership is the class to which the vector belongs. On the other hand, if a vector is assigned 0.55 membership in class one, 0.44 membership in class two, and 0.01 membership in class three, then we should be hesitant to assign the vector based on these results. However, we can feel confident that it does not belong to class three. In such a case the vector might be examined further to determine its classification, because the vector exhibits a high degree of membership in both classes one and two. Clearly the membership assignments produced by the algorithm can be useful in the classification process. The basis of the algorithm is to assign membership as a function of the vector's distance from its K-nearest neighbours and those neighbours' memberships in the possible classes. The fuzzy algorithm is similar to the crisp version in the sense that it must also search the labeled sample set for the K-nearest neighbour. The labeled samples can be assigned class memberships in several ways. First, they can be given complete -xii- membership in their known class and nonmembership in all other classes. Other alternatives are to assign the samples' membership based on distance from their class mean or based on the distance from labeled samples of their own class and those of the other class or classes, and then to use the resulting memberships in the classifier. An alternate scheme for assigning initial memberships based on a learning scheme is also considered in this thesis. Two different methods are used in order to form the prototypes of the fuzzy K-NN classifier. First, the training set is completely used as the class prototypes and their memberships are assigned by the fuzzy c-means algorithm. Second, class prototypes are formed by using fuzzy Kohonen clustering algorithm and crisp memberships (1, complete membership; 0, nonmembership) are assigned to these vectors. The second classifier used in this study is the fuzzy nearest prototype classifier. These nearest prototype classifiers bear a marked resemblance to the one-nearest neighbour classifier. Actually, the only difference is that for the nearest prototype classifier the labeled samples are a set of class prototypes, whereas in the nearest neighbour classifier we use a set of labeled samples that are not necessarily prototypical. In this study, fuzzy c-means algorithm is used for the formation of the class prototypes. In the fuzzy NP algorithm, membership in each class is assigned based only on the distance from the prototype of the class. The fuzzy K-nearest neighbour and fuzzy nearest prototype classifiers developed and investigated in this thesis show useful results. By using these classifiers, we obtain a measure of how "typical" the object is of each class. Memberships obtained by these classifiers do provide a useful level of confidence of classification. The nearest prototype classifier is the quickest and simplest of the classifiers considered. The reason is that in this algorithm, an unknown sample is compared to one prototype per class as opposed to the K-nearest neighbour algorithms, where an entire set of labeled samples representing each class must be compared before the K nearest are obtained. The two of the learning algorithms used in this study give successful results for the formation of the prototypes that represent the normal beat, left bundle branch block beat and the paced beat shape changes. As the PVC type shape change is represented by more than one cluster in the feature space, its prototypes can not be formed correctly by the fuzzy c-means algorithm. For this reason, fuzzy nearest prototype classifier which uses the prototypes -xiii- formed by the fuzzy c-means algorithm, classifies the PVC by a low success rate. As the fuzzy Kohonen algorithm represents the shape changes by more than one prototype, it gives better results compared to the fuzzy c-means algorithm, especially for the PVC type shape change. Fuzzy K-NN classifier gives better results compared to the fuzzy NP classifier for it uses more than one prototype for each class. The results presented in this thesis were produced by software implementation of the algorithms. The software was developed using C language on PC.

##### Açıklama

Tez (Yüksek Lisans) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 1995

Thesis (M.Sc.) -- İstanbul Technical University, Institute of Science and Technology, 1995

Thesis (M.Sc.) -- İstanbul Technical University, Institute of Science and Technology, 1995

##### Anahtar kelimeler

Biyomühendislik,
Bulanık mantık,
Elektrokardiyografi,
Bioengineering,
Fuzzy logic,
Electrocardiography