New algorithm for EEG signals classification is proposed in this paper. The typical algorithm for signal classification includes two steps: preliminary transformation and classification. The preliminary transformation modifies investigated signals by the procedures of feature extraction and dimension reduction into data set accepted for the classification. This transformation causes the loss of some information that can improve the classification accuracy. New procedure of fuzzification is added in the preliminary transformation for the proposed algorithm. This procedure allows using the fuzzy classifier at the second step. The Fuzzy Random Forest is used for the classification of EEG signals in the proposed algorithm. The new procedure (fuzzification) in the preliminary transformation and new fuzzy classifier (Fuzzy Random Forest) allows increase the classification accuracy of the EEG signals. The efficiency of new algorithm is evaluated by two investigations. The first one focuses on epilepsy diagnostics and the second one aims at epileptics' seizure detection. The comparison with other studies and shows the increasing of the classification accuracy of EEG signals by the proposed algorithm.
Epilepsy is considered as one of the most common chronic neurological disorders. Statistics of World Health Organization shows that approximately 50 million people worldwide suffer from epilepsy [1]. The most notable epileptic symptom are recurrent unprovoked seizures which usually occurs without warning, and they can affect each part of the body [2]. Seizures are caused by the electrical activity of the brain, concretely by the unexpected electrical disturbance of brain and excessive neuronal discharge. These brain activities can be monitored by the Electroencephalogram (EEG) [3]. Ability to measure brain electrical activity makes EEG as one of the most important tools in neurology diagnostics [5, 6]. EEG measures electrical brain activity by the electrodes placed on the scalp [1, 2]. Captured measurement are signals. These signals are converted into the graphic form represented by curves [4]. The shape and character of captured curve is strongly affected by current brain activity. Curves of signals obtained from EEG can be evaluated visually by specialized doctors who are able to use them in neural disorder diagnostic. However, such evaluation might not provide enough information for doctors to provide reliable neurological diagnostics. Diagnostic based on EEG can be significantly improved by development of algorithms for automatic analysis of EEG signals. Such algorithms must involve automatic extraction and analysis of information from the captured signal. According to extracted information, the brain state can be predicted or classified. In this paper, the algorithm for EEG signal analysis is proposed. This algorithm is demonstrated by the detection of epileptic seizures and the diagnostics of epilepsy.
To develop reliable and credible algorithms for automatic EEG signal analysis can be developed based on the real data. There is well-known dataset of EEG signals collected and published by R. G. Andrzejak [6]. This dataset consists of 500 samples of EEG signal evenly divided into five disjoint subsets A, B, C, D, and E. Therefore, each subset contains 100 samples of EEG signals. Each of these samples represents an EEG signal captured during 23.6 seconds of EEG recording. Subset A and B contain measurement recorded from persons who do not suffer from epilepsy. In case of subset A, patients had eyes opened during recording while patients in subset B had eyes closed. Whether the eyes are open or closed affects the electrical activity of the brain according to [6]. Samples in subsets C, D, E was recorded from persons suffered from epilepsy. While patients in subsets C and D were investigated during seizure-free intervals, subset E contains samples measured during seizure activity only. Subset C consists of the vectors, were obtained from the hippocampal formation of the opposite hemisphere of the brain. Data vectors in the subset D were recorded from within the epileptogenic zone. Examples of samples from these subsets are shown in Fig. 1.
From Fig. 1 is observable that signals in A and E are different from signals in B, C, and D. Nevertheless, only visual inspection can be insufficient to recognize healthy (A, B) and epileptics EEG segments (C, D, E). The most significant similarity between this group is oblivious in case of samples from B, C, and D. The samples are very similar to each other and the use only of visual inspection can lead to failure in diagnostic (patient suffering from epilepsy diagnosed as healthy). This example was used to shows that development of algorithms for automatic EEG signals analysis can be instrumental in diagnostics. It allows deciding whether a person has epilepsy without information if they have had an epileptic seizure or have not. Another task can be focused on detection of seizure activities. Also, development and analysis of these algorithms can enable the growth of decision support systems for early diagnosis of epilepsy [3–5].
Algorithms for automatized EEG signals analysis has been considered in several works. Different classification methods are used in these investigations, for example, K-nearest neighbor classifier [7], neural networks [5, 8, 9], support vector classifier [10, 11], decision trees [12]. The classification accuracy of EEG signals can be increased by the application of evolution methods [7] and clustering analysis [13]. Analysis of these investigations shows that one of effective classification methods of EEG signal for identification of persons with epilepsy is based on the application of decision tree [12] and Fuzzy Decision Tree (FDT) [14, 15]. The approach of EEG signal classification by FDT is developed in this paper and ordered FDT (oFDT) introduced in [16] are used. This tree has a regular structure that contains exactly one attribute at each level of the tree [17]. This ability allows parallelization of classification. The evaluation of the EEG signals classification in [17] has possible and quite accurate. However, there can be possibility for increasing of the classification accuracy that is considered in this paper. In particular, the application of Fuzzy Random Forest (FRF) is considered.
Typical algorithms for EEG signals classification in addition to the classification procedure include the signal preliminary transformation into numerical attributes [18, 19]. For this reason, analyzed signal must be preprocessed to extract useful information necessary for creating classification models. Nowadays, we can find many preprocessing schemes in the literature. Basically, most of them consist of two steps: feature extraction and dimensional reduction. Feature extraction usually includes wavelet or spectral transformation. In [12] discrete wavelet and Discrete Fourier Transformation (DFT) was compared. Result of this paper shows better performance of DFT in combination with method C4.5 for decision tree induction. In [20] and [9] the Welch’s method was used. These studies indicate that power spectrum density estimation by Welch’s method provides strong attributes which represent EEG signals well. The second typical step of preprocessing is dimensional reduction. This step is required when feature extraction produce data matrix of large dimension. Dimensional reduction usually transforms data matrix to matrix of significantly smaller dimension. In [10] three techniques was compared: Principal Components Analysis (PCA), linear discriminant analysis, and independent component analysis. The used in this paper PCA is recomended especially in cases when the number of training samples per class is small [21].
In comparison with preprocessing of EEG signals mentioned above, the algorithm presented by us in [14] and [15] involve fuzzy logic to preliminary data transformation as additional step. This step is fuzzification which can significantly reduce possible uncertainty in data. This paper shows a detailed investigation of this step with combination of different fuzzy classifiers: FDTs and FRF. This analysis allows developing of accurate method for EEG signals analysis.
The proposed algorithm for epileptics’ seizure detection from EEG signals includes two steps (Fig.2): the preliminary transformation of EEG signal and the classification. The differences between traditional algorithms of signal classification and algorithm proposed in this paper are (a) the additional procedure of fuzzification at step of preliminary transformation and (b) the fuzzy classifier at step of classification. The addition of the fuzzification permits to use fuzzy classification and consider the ambiguity of the transformed and reduced initial EEG signal.
In papers [22–24], it has been shown that fuzzy data are useful for representation of ambiguous and imprecise data with higher accuracy and the application of fuzzy data instead of numerical data allows increasing of the accuracy of classification. The principal steps of the proposed algorithm for EEG signal classification are shown in the figure bellow.
(oFDT, uFDT, FRF)
Signal preprocessing and the preliminary signal transformation of EEG signals causes the loss of some information of initial signal. This fact implies the classification of ambiguous data. Fuzzy classifiers can be used for effective classification in this case [25]. The application of these classifiers is possible if the input data for the classification is fuzzy. However, data in standard algorithms of EEG signal classification after the preliminary transformation is not fuzzy even if procedures of attribute extraction and dimension reduction include fuzzy transformation. For example, in paper [26] propose the algorithm for EEG signal classification with the application of adaptive neurofuzzy inference system. Other fuzzy techniques are described in [27]. At same time classifications in these algorithms are not implemented based on fuzzy classifier. Classification can be improved by application of a fuzzy classifier that causes the representation of data for classification after the preliminary transformation as the fuzzy data.
Moreover, we lose some amount of information during EEG signal preprocessing during preliminary data transformation. Therefore, the ambiguity and uncertainty of initial data can occur. By applying fuzzification, we can reduce possible ambiguity. Moreover, fuzzy logic is tolerant to imprecise data and deviations during data measurement. Fuzzy logic can also model nonlinear functions of arbitrary complexity [28]. These facts allow reducing ambiguity and uncertainty of transformed data. According to obtained data after preliminary data transformation, we obtain data which was used to create three fuzzy classifiers. In the next sections, the steps of preliminary data transformation are described in detail. 3
The preliminary data transformation developed in [14] and [15] was evaluated by classification of EEG signals from dataset gathered in [6] (Fig. 1). Description of recording in [6] tells that during the recording of each EEG signal was used the same 128-channels amplifier system. Recorded data were converted to digital form by 12 bit analogto-digital conversion, and then the data were written continuously onto disk of data acquisition computer system at a sampling rate of 173.61 Hz. The frequency of Bandpass filter was 0.53-40 Hz. Aa was mention in previous section, signal obtained by this recording is function of time. Therefore, the preliminary data transformation is necessary to extract useful information, which can be used to build classifiers and classify new EEG records. 3.1
The signal preprocessing which preliminary data transformation do, consist of three steps (Fig. 2). At first, feature extraction by Welch method is applied [29]. The method is based on the concept of periodogram spectrum estimates, which is the result of signal conversion from its time to frequency domain. Periodogram is commonly used for examining the amplitude vs frequency characteristics of analyzed signal. Time series of a signal is split into overlapping segments (Fig. 3) of the predefined length which is equal for each preiodogram. Then the periodgram of each segment is computed and used to find important periodic components in the time series. At last step, periodograms are averaged. The result of averaged periodograms is known as power spectral density estimation of analyzed signal [29]. − | = 0, where is the unit matrix. The principal components are com= T × T, = ( 1, … , ). This transformation forms orthogonal principal After transformation, it is necessary to choose only several important principal components. Nowadays, many criterions exist to solve this problem. One of the most commonly used criteria to determine appropriate number of principal components is the eigenvalue-one criterion, also known as the Kaiser criterion [31]. This criterion selects a principal component as significant if its variance is higher than 1.00.
As a result of PCA, we obtained 8 principal components, which describe the reduced feature matrix of origin EEG signals. Therefore, each signal is described by 8 principal components. In text bellow, these principal components are noted as numerical input attributes ( = 1, … ,8)of EEG signals. 3.3
We propose to use fuzzification process as part of preliminary data transformation. This process transforms each numeric attribute Xi obtained after dimensionality reduction into fuzzy attribute ( = 1, … , ). After this transformation, each fuzzy attribute will be composed of mi (mi ≥ 2) linguistic terms. A -th linguistic term of attribute is defined by fuzzy set , ( = 1, … , ). Fuzzy set , with respect to a universe Xi is defined by a membership function ,
( ): → 〈0,1〉. This function defines a membership degree ,
( ) for each element ( ∈ ), which define how strongly element is the member of fuzzy set , . Formally, fuzzy set , is defined as an ordered set of pairs , = {( , , ( )), ∈ }, where: (a) , ( )= 0, if and only if is not the member of set , ; (b) 0 < ,
( )< 1, if and only if is not the full member of set , ; and (c) ,
( )= 1, if and only if is the full member of set , .
To perform fuzzification of analyzed data, we used the algorithm proposed in [32]. This algorithm is based on the computation of the fuzzy entropy of fuzzy sets. The algorithm divides values
∈ into intervals. Intervals are defined by points 1… . We find this borders by K-Means algorithm as in [32]. Number of intervals is determined automatically. This number agrees with the number of linguistic terms mi of fuzzy attribute . The algorithm is initially performed with two linguistic terms, then the algorithm adds linguistic term to attribute. Adding of linguistics term is repeated until the fuzzy entropy of attribute does not raise. The definition of Fuzzy entropy, which with the aforementioned algorithm works, is following. fine, that belongs to class . Than, ,
is defined as follow: where is the number of classes defined by output attribute . Notation ∈ deFor each attribute must hold following constrain where ∑ , = 1. Then the =1 fuzzy entropy of attribute defined as:
Then the fuzzification process assigns membership degree ,1 ( )to each of numeric attribute . This membership degree is obtained by triangular membership function. The definition of used membership function for first linguistic term ,1 of attribute is following.
,1( )= { 1 0 2 − 2 − 1 ≤ 1 ≥ 2 1 < < 2
Each non-first and non-last linguistics term of has a membership function , ( = 2,3, … , − 1) defined as follow: ≤ −1 −1 < ≤ < ≤ +1 ≥ +1 ≤ −1 −1 < ≤ ≥ , ( )= , ( )=
Finally, the last term , of has the membership function with following mathematical form:
Fuzzification is the last step of preliminary data transformation. After fuzzification of reduced data matrix, we obtained data represented by 8 fuzzy attributes. This data was used to induct fuzzy classifiers and evaluate the performance of proposed algorithm for EEG signals analysis. 4
After fuzzification, we obtained data described by 8 fuzzy input attributes ( = 1, … ,8)and one output attribute . According to this data, we induct three fuzzy classifiers to evaluate new algorithm for EEG signal analysis. We use oFDT which combines into the FRF. 4.1
Nodes and leaves are the main parts of the Decision trees. Each node is associated with one input attribute (splitting attribute). Domain of this input attribute determines outcoming edges of the node. The domain of attribute defines all its possible values. The classification's task solving begins at the root of the tree. If a node is associated with an input attribute, then the outcome edge for the classified instance is determined according to splitting attribute, and the classification continues using the appropriate sub-tree. When classified instance encounters a leaf, encountered leaf give the predicted class as classification result. In case of fuzzy decision trees, classified instance usually traverses by multiple branches during classification. Therefore, the decision is based on several leaves.
In this paper, we use two type of fuzzy decision trees based on CMI. The first is oFDT. This type of tree has nodes on the same level associated with one input attribute. This fact allows to performing classification as parallel process. The second type is uFDT. uFDT do not require the same splitting attribute on each level of the tree. In Table 1 are shown splitting criteria for these FDTs.
( ; −1, )) (
( | −1) = = oFDT
( ; − , )) (
( | − , )
In the Table 1 argmax returns attribute index with maximal value of CMI, −1 = { 1, 1 × … × −1, −1} is the fuzzy set defined by the sequence of fuzzy terms 1, 1, … , −1, −1 of selected attributes 1, … , −1 from the root to the -th node. − is the sequence of selected attributes { 1 , … , −1}. The CMI in output attribute B about the attribute and the sequence of values −1 been introduced in [33] and calculated as:
( ; −1, ) = ∑
∑ ( × −1 × , )× =1 =1 × (log2 ( × −1 × , ) + log2 ( −1) − log2 ( × −1) − log2 ( −1 × , )), where , ; The conditional cumulative entropy between fuzzy attribute quence of selected attribute terms −1 is defined as: ( × −1 × , ) is measurement of cardinality of fuzzy set × −1 × and the se ( | −1) = ∑ ( , , −1)× (log2 ( ( −1))− log2 ( , × −1)).
=1
Implemented FDTs solve overfitting problem by pruning technique. Overfitting occur leaves covers insuficient number of instances in ratio with input data. To avoid overfitting, we use threshold parameters alpha and beta to determine leaf nodes during FDT induction. These parameters are described in detail in [15]. 4.2
Random forest is classifier, which combines set of individual decision trees into one classifier system. Advantage of random forests against individual decision trees is stability. Decision trees are sensitive to variations in data. Generally, random forests are not sensitive to overfitting while decision trees tend to overfit input data [34]. Overfitting occurs when leaves contain a small number of instances in ratio with number of input data. Nevertheless, pruning techniques can solve this problem. On the other hand, decision trees are well interpretable classifier. In case of random forest, it is hard to figure out what hundreds of trees tell. Next advantage of decision trees is classification performance. Provided classification by many trees is significantly slower then classify by one individual decision tree. Nevertheless, many papers shows bigger classification accuracy of random forests over individual decision trees, eq. in [35].
Random forests are type of ensemble methods. Ensemble methods combines
multiple classifiers to obtain better classification accuracy than can acquire any of the
constituent classifiers alone [36]. Many methods of ensemble learning based on different
base of classifiers was developed. One of the first is bagging [37]. Bagging creates new
dataset from origin dataset for each classifier by sampling with replacement. It means,
one instance from origin dataset can occur in sampled dataset multiple times. This
approach helps to avoid overfitting. Bagging is often combined with decision trees. In
[
FRF consists of defined number of individual FDTs. Each of these FDT provide some decision (classification result). To obtain decision of forest, results of individual trees must be combined (Fig. 3). The combining of these results was achieved by the summation of membership degrees of belonging to each class divided by the number of trees. The strategy of classification, which we use, is shown in figure below.
In case of implemented random forest, the number of decision trees must be specified as input parameter. It is important to find ideal value of this parameter because small number of decision trees can lead to small classification power. In case of big number of decision trees, the algorithm can suffer from slow computation performance caused by thousands of trees. Therefore, we implemented simple iterative procedure to find the smaller value of this parameter in combination with the biggest classification accuracy. This procedure builds initial FRF consists of 3 FDTs. On the start of each iteration, one decision tree is added to FRF and accuracy is evaluated. This procedure finishes when classification accuracy stops growing.
After preliminary data transformation we obtained data described by 8 fuzzy input attributes and one output attribute. According to this data, we create fuzzy classifiers. In this section is described, how classification performance of used classifiers was evaluated. To evaluate classification performance of implemented classifiers, we used three metrics: accuracy, sensitivity, and specificity. Sensitivity and specificity are important in case, when data is not evenly distributed into classes. The definition of used metrics is showed in the table below.
Sensitivity
Specificity where TP stands for true positive, TN is true negative, FP is false positive, and FN is false negative. True positive and true negative results are obtained after correct classification while false negative and false positive stands for misclassification results. To evaluate classifiers, we divide data into training and testing set in ratio 70:30. Training set was used to create classifier and testing set was used to evaluate it. We repeated this for 10 000 times for each training set.
FRF needs to have defined an exact number of trees. Therefore, we analyzed how number of trees can affect classification accuracy of FRF. In this analysis, the forest from 3 trees was created and its accuracy was evaluated. Then, the number of trees was increased by one, and performance was re-evaluated. Adding of trees was repeated while the accuracy of the forest was raising. 5.1
Evaluation of used classifiers was performed by two experiments. In the first experiment, the classification was aimed to recognize patients who suffer from epilepsy. The goal of the second experiment was to find patients during epileptic’s seizure. To solve this task, the database was divided into two classes. In case of the first experiment, healthy persons and persons suffering from epilepsy (AB, CDE). In the second experiment, we were aimed to separate persons during seizure activity and persons in seizurefree interval (ABCD, E). For each experiment, the analysis of number of trees necessary for accurate prediction of FRF classifier was performed. Results obtained by proposed algorithm are shown in Table 3.
0,996 0,994 0,992 0,99 0,988 0,986 0,984
Classifier uFDT oFDT FRF uFDT oFDT FRF
Predicated
Implemented FRF requires to have a specified number of trees as input parameter. This parameter affects computational complexity of aforementioned FRF. In case of large number of trees, total time necessary for FRT induction can be large. Also, classification by thousands of trees can be complex. Therefore, the setting of this parameter to proper value is necessary. To find proper value of this parameter, the FRF from 3 trees was inducted and its accuracy was estimated. Then, the number of trees was increased by one, and performance was evaluated again. Adding of trees was repeated while the accuracy of forest was raising. The results obtained by this analysis are shown on plots bellow. There are shown four plots. The plots show classification accuracy of FRF depending on the number of inducted FDT. The x axes of these plots stand for number of trees. The y axes sands for classification accuracy. Plots on the left side show accuracy for FRF consisted of 3 to 100 trees. Plots on the right side are plots created from the same data, but these plots show the accuracy of FRF consisted from 82 to 100 trees. 82 84 86 88 90 92 94 96 98 0,885 0,88 0,9003 0,90025 0,9002 0,90015 0,9001 0,90005 3 9 15 21 27 33 39 45 51 57 63 69 75 81 87 93 99 828384858687888990919293949596979899 Fig. 4. Plots show accuracy (y axis) of FRF depending on the number of inducted FDT (y axis) for epileptics’ detection.
To compare results of our investigation with similar studies, we created the comparison showed in Table 4. These tables include only studies which used the same data as we used. The classification of selected studies was targeted on prediction of occurrences of the epileptic’s seizures. Differences between selected studies are in its preliminary data transformation and classification methods, eq. attribute extraction, dimensional reduction or classification algorithm. The comparison is shown in Table 4, where the first column contains first authors of studies and the reference to the paper, the second describes used methods in preliminary data transformation, third columns tells which classifier was used and the last column shows acquired classification accuracy. In this paper, the algorithm for EEG signal classification based on fuzzy logic was proposed. Previously, we solve task of EEG signals FDTs in [14] and [15], where the analysis of different fuzzification techniques was performed in detail. In this paper, the algorithm based on fuzzy entropy according to [32] was used. Involving of fuzzy logic permits to take into account the ambiguity of data that can arise in step of preliminary transformation (the feature extraction and the dimension reduction). The modification resulted in adding of fuzzification as new step in the preliminary data transformation. According to data obtained after preliminary data transformation, we compare three type of fuzzy classifiers: oFDT, uFDT, and FRF. These classifiers were inducted based on estimation of the cumulative mutual information [33]. In case of FRF, the impact of number of trees to classification accuracy has been analyzed. Results shows, that usage of proposed preliminary transformation can improve the classification accuracy of the EEG signals. Therefore, involving of fuzzy logic can be considered as recommended step for future development in EEG classification.
In future development of proposed classification algorithm, the impact of another classifier can be evaluated. Also, the modification of preliminary data transformation is possible. There are numerous ways to provide spectral transformation, dimensional reduction or fuzzification. The crucial goal of this development is increasing the classification accuracy of EEG signals.
This paper has been supported by grant VEGA 1/0354/17. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 36. 37. 38. 39. 41.