A new algorithm for Electroencephalogram (EEG) signals classification is proposed in this paper. This classification is used for automatic detection of patients with epilepsy in a medical system for decision support. The classification algorithm is based on Ordered Fuzzy Decision Tree (OFDT) for EEG signals. The application of OFDT requires special transformation of EEG signal that is named as preliminary data transformation. This transformation extracts fundamental properties/features of EEG signals from every sample and reduces dimension of the samples. The accuracy of the proposed algorithm was evaluated and compared with other known algorithms used for EEG signal classification. This comparison showed that the algorithm proposed in this paper is comparable with existing ones and can produce better results than others.
Epilepsy is characterized by the seizures that are the result of a transient and unexpected electrical disturbance of the brain. These electrical discharges of neurons are evident in the electroencephalogram (EEG) signal, i.e. a signal that represents electrical activity of the brain [1]. EEG has been the most common used signal for brain state monitoring. It is used in medicine to reveal changes in the electrical activity of the brain to detect disorders that are indicated generally at seizure diseases, loss of consciousness after a stroke, inflammations, trauma, or concussion [2]. Measuring brain electrical activity by EEG is considered as one of the most important tools in neurology diagnostic [3, 4]. The specifics of this signal have been presented in details in [3]. The communication in the brain cells takes place through electrical impulses. EEG allows measuring these electrical impulses by placing the electrodes on the scalp [1, 2]. Captured signals are amplified by EEG and then converted to the graphic representation – curve [2]. The shape and character of the curves depend on the current activity of the brain. By extracting useful information from captured signal, we are able to predict or classify the brain state of investigated patient. However, the visual inspection of EEG signal does not provide much information and, therefore, the automatic analysis and classification of EEG signal is a current problem. Solution to this problem can permit developing decision support system for epilepsy diagnosis [1]– [3]. By extracting useful information from the captured signal, the brain state of a patient can be predicted or classified.
The specifics of EEG signal described in [1] imply special transformation of this
signal before application of classification procedure. This typical step of algorithms
for EEG classification is known as preliminary data transformation. The features
extraction and reduction of their dimension from the initial signal are fundamental
procedures that are necessary before the classification. Different algorithms for features
extraction can be used for EEG signal, e.g. Fourier transform [4], logistic regression
[3], wavelet transform [2], Welch's method [4]. In this paper, we use Welch's
method, whose result is a matrix of features that indicates specifics of the investigated
signal. However, this matrix has usually a large dimension for classification and,
therefore, a special procedure has to be used to reduce its dimension. The principal
component analysis (PCA) is used typically to achieve this goal in EEG signal
analysis. PCA is a statistical procedure [
After the preliminary data transformation, the EEG signal can be classified. The
classification is implemented based on such methods as neural networks [4],
evaluation methods [5], clustering analysis [
In this paper, a new algorithm for classification of EEG signal that is transformed
into fuzzy reduced features is developed. The classification itself is implemented by
an Ordered Fuzzy Decision Tree (OFDT). This type of decision trees has been
introduced in [
This paper consists of four sections. The first section describes the background of
the proposed algorithm for EEG signals classification. This section describes data
used in the algorithm and explains the principal steps of the algorithm. The second
section deals with the preliminary data transformation by Welch’s method, principal
component analysis, and fuzzification. The process of OFDT induction is explained in
the third section. This process is illustrated using the data obtained after the
preliminary data transformation of data from [
In case of epileptic activity, EEG signal has some special features that have to be
extracted automatically to allow classification. The development of new classification
algorithm requires application of data from real observations because they allow us to
evaluate the accuracy of the algorithm. The dataset of EEG signals used in this paper
was collected and published by R. G. Andrzejak in [
The visual inspection of EEG signals depicted in Fig.1 does not provide much information. Also, the classification of these signals by decision tree, OFDT in particular, is not possible because these signals cannot be interpreted in terms of OFDT attributes. This implies that some numerical features from these signals have to be extracted. Furthermore, if there are a lot of extracted features, then they should be reduced before the classification. This transformation of EEG signal is interpreted as preliminary data transformation.
The new algorithm for EEG signal classification has 2 principal steps (Fig. 2):
preliminary data transformation and classification based on OFDT. The first of these steps
consists of three procedures. The first of them is feature extraction. There are different
procedures for extraction of features of EEG signal. For example, Fourier Transform
is used in [4], and wavelet transform in [
The second procedure of the preliminary data transformation is a reduction of the
dimension. This procedure can be implemented based on the PCA, whose background
and principals are discussed in [
Finally, the third procedure is fuzzification of the obtained features of EEG signal.
This procedure is specific for our algorithm (it is not used in the existing ones), and its
addition results from application of classification algorithm based on OFDT. Several
algorithms can be implemented for this task. In this paper, we use algorithm of
fuzzification that was described in [
The second step of the developed algorithm is classification. A new classification
based on OFDT is elaborated in this paper. The OFDT for this classification is
inducted based on estimation of cumulative information introduced in [
The preliminary data transformation includes three procedures. The first of them is Welch’s method that is used for extraction of the features from raw EEG segments. The Welch’s method provides conversion from the time domain of the analyzed signal into its frequency domain. It is non-parametric power signal density estimator [4]. This transformation divides the time series of a signal into several overlapping segments of the same length, and then computes the periodogram of the each segment. The result of the Welch’s transformation is a matrix of features where every row corresponds with the periodogram of one signal. Every column is considered as input attribute. As a rule, the obtained matrix has usually a lot of columns, i.e. a lot of input attributes for the classification. To reduce the amount of input attributes PCA can be applied. 3.2
PCA is a statistical procedure, which converts a set of observations (possibly
correlated variables) into linearly uncorrelated variables called "principal components". The
number of principal components is less than or equal to the number of original
variables. Every resulting principal component can be considered as an input attribute for
arbitrary classification model. The goal of the PCA is to maximize the variance of
individual principal components, provided that their covariance is equal to zero. The
resulting principal components are linear combinations of original features. In the
feature space, the components are orthogonal to each other. The first component has
the biggest variance. Every next component has as big variance as possible keeping
constraints that it is uncorrelated and orthogonal to the components obtained before
and its variance is bigger than variance of components after them. The number of
selected components for next analysis has been estimated by Kaiser’s criterion [
Input data for OFDT induction is fuzzy. This implies the numerical data obtained
from PCA has to be fuzzified. The fuzzification is the transformation of continuous
numerical data into a set of fuzzy data. One of the possible algorithms of fuzzification
is arbitrary clustering algorithm described in [
The classification algorithm considered in this paper works with fuzzy attributes. Let us assume that we have fuzzy attributes denote as , for = 1,2, … , . Then fuzzy attribute is a linguistic attribute, which means that can take fuzzy ues , , = 1,2 … , . Every value , of fuzzy attribute can be considered as a fuzzy set. Fuzzy set , is defined as an ordered set of pairs {( , , ( )), ∈ }, where denotes the set containing all the entities belonged to the discourse (this set is known as the universe of discourse or the domain of discourse), and , ( ): → [0,1] is a membership function that defines for every entity from universe U its degree of membership to set , (a numeric value between 0 and 1). The membership of entity from universe to fuzzy set , is defined by function , ( ) in the following manner: 1. , ( ) = 0 2. 0 < , ( ) < 1 3. , ( ) = 1 if and only if is not a member of set , , if and only if is not a full member of set , , if and only if is a full member of set , .
In what follows, we will use some special terms from fuzzy set theory. The first of them is cardinality ( , ) of fuzzy set , , which is defined as follows: ( , ) = ∑ , ( ), ∈ and another one is the product of fuzzy sets ,̃ = ,1 × ,2 × … × , . This product results in new fuzzy set ,̃, which is defined as follows:
,̃ = {( , ,1( )∗ ,2( )∗ … ∗ , ( )) , ∈ }.
The fuzzy attributes necessary for the OFDT induction in case of EEG signal classification have to be obtained by fuzzification of principal components obtained after PCA transformation of data acquired by the Welch’s transformation of raw signals. For this purpose, we use the arbitrary clustering algorithm. This algorithm divides numerical values of the numerical attribute into clusters to obtain fuzzy attribute . The -th cluster, for = 1,2, … , , is described by center . Creation of membership functions is based on these centers. The usage of membership functions , ( )is explained in Table 1. The columns in Table 1 are separated into two subcolumns. The first sub-column contains membership functions, and the second contains obligations, which defines the function that will be used during the transformation. ,1( ) 1 0 2 − 2 − 1 ,1
If
≤ 1
1 < < 2
≥ 2
utes , for = 1,2, … , . The values of the output attribute represent class labels. The
repository table consists of + 1 columns that correlate with n input attributes and 1
output attribute B. Attribute is divided into
sub-columns that correspond to the
values of the input attribute. The example of a repository is shown in Table 2. The
cells of this table contain the membership function values for every value of
individual attributes. A row in the table represents one sample used for OFDT induction.
The preliminary data transformation described above was applied on the data
collected in [
According to [
Let us consider application of OFDT for classification of EEG signal that is
represented by reduced features with fuzzy values. The splitting criterion for OFDT
induction is the Cumulative Mutual Information (CMI) ( ; 1, 2, … , −1
[
( ). The splitting criterion also tries to reduce the number of branches in multi valued attributes. This can be achieved using the entropy ( ) of the investigated attribute. Therefore, the criterion for choosing the attribute that will be used for splitting has the following form: (1) (2) (3) = arg max ( ( ; 1, … , −1 ( ) ∗
, )), ( ) where the entropy of attribute is computed as ( ) = (log2 − log2 ( , )), where is the count of data samples and z is the investi∑ =1 ( , ) ∗ gated level of the OFDT.
The OFDT algorithm uses pruning technique for establishing leaf nodes. The goal of pruning is to remove a part of an OFDT, which provides a small power for classification of new instances. The used pruning method establishes the leaf nodes by stopping the tree expansion during the induction phase. The pruning procedure uses the threshold values and . Threshold reflects the minimal frequency of occurrences in a given branch. The frequency of a branch reflects percentage of instances belonging to the given branch. (Please realize that one instance can belong to more than one branch, which is caused by usage of fuzzy logic.) Threshold represents the maximal confidence level computed in a given node. Confidence level means the likelihood of the taken decision. Every internal node of the tree is declared as a leaf if at least one of the following conditions is satisfied: ≥ ( 1 1 × … × )
≤ 2− ( | 1 1,…, z )
where 1 1, … , is the sequence of specific values of attributes 1, … , z (this
sequence agrees with a path from the root 1 to node z), represents the j-th value
of output attribute B, where = 1,2, … , , and ( | 1 1, … , z ) is computed as:
( 1 1 × … × )⁄log2 ( 1 1 × … × × ). These threshold values have
big influence on tree level and the depth of branches (paths from the root to a specific
node). The branch depth is defined as the number of nodes of given branch.
Increasing value causes increasing in the depth of tree branches. The parameter also
affects the depth of the tree. In this case, bigger causes the smaller depth of
branches. The threshold values should be set to good values to perform accurate
classification. If = 0 and = 1, the classification is very accurate, but only for training
instances. Small frequencies of branches will lead in classification mistakes of new
instances [
Modification of threshold values and allows induction of OFDT with accuracy that agrees with problem conditions. OFDTs for different values of the threshold and can have different structure and accuracy. 4.2
In the next part of this section, the induction of the OFDT will be illustrated. The illustration is done for branch 1,1 2,3. At the beginning of the OFDT induction, we have set F of unused attributes. From set F we have to choose the attribute with maximal value of splitting criterion (1). We computed that the attribute with the maximal value of the splitting criterion is 1. Therefore, this attribute is established as the root of the tree. The frequency in the root calculated by (2) is always equal to 1. Attribute 1 has 2 fuzzy values 1,1 and 1,2. These values will be associated with outcomes from the root. Attribute 1 is removed from set F of unused attributes. The first level of the decision tree is displayed in Fig. 3.
Fig. 4. The first level of OFDT
At the second level, the attribute with a maximal value of (1) is selected from set F again. In this case, attribute 2 has the maximal value of (1). This attribute is associated with the nodes at the second level of the tree. Next, it is necessary to check if some node at the second level can be a leaf. The node is established as a leaf if at least one of conditions (2) or (3) is satisfied. In explained branch 1,1 2,3, branch 1,1, 2 has frequency equal to 0.543, which is greater than minimal frequency α, and confidence levels are 0.547 and 0.453. This implies that condition (3) is also not satisfied and, therefore, node 2 of branch 1,1, 2 cannot be a leaf.
At the third level, unused attribute 10 is chosen. This attribute is removed from set F of unused attributes. At the third level two nodes become leafs. A leaf is established in branch 1,1 2,3, because condition (2) for minimal frequency is satisfied.
In a similar way the full OFDT displayed in Fig. 7 can be inducted. Every level of this OFDT has exactly one attribute: the first level has one node with attribute A1, the second level includes 2 nodes with attribute A2 and the third level has nodes agreeing with attribute A10. The third level includes some nodes that are labeled as LEAF if the node is a leaf. Every node has the information about the frequencies and confidence in the second row and the last row accordantly. The confidence levels and frequencies are calculated by formulas (2) and (3).
It can be unclear for someone why attribute A10 has been chosen at the 3-rd level of the resulting OFDT since, after PCA transformation, the biggest amount of information should be in first attributes while last attributes should have small amount of information. This is caused by the splitting criterion because it takes into account the output attribute too.
Please note we did not use fuzzification of the best quality in the illustration of OFDT induction because we needed a tree of such sizes that can fit on the page (this also affected on the sequence of chosen attributes). For the illustration purpose, we also chose threshold for minimal frequency and threshold for maximal confidence as 0.1 and 0.65 respectively. Therefore, the OFDT depicted in Fig. 7 does not agree with one with the best reached accuracy. 5.1
The important characteristic of the classification procedure is the accuracy. The accuracy is estimated as the ratio between the count of correctly classified instances and the number of classified instances, which represents the percentage of properly classified instances: where is the number of classified instances, is the classified instance from dataset , = 1,2, … , and ( ) is given by: ( ) = { 1, if 0, otherwise ( ) = class of , where function classify returns the resulting class of OFDT classification.
The estimation of the accuracy of the classification can be done by two methods. In first, the training and testing samples are the same. Each sample from dataset is used to induct the OFDT. Then each sample ∈ is classified, and the accuracy is evaluated. The second estimation is provided with the divided set of instances . Firstly, the set of instances is split into two sets. The first set contains training samples and the second one testing samples. About 20% of samples of dataset are used for classification (testing samples) and about 80% for OFDT induction (training samples). The described process is shown in the Fig. 8.
The accuracy evaluation was implemented by several experiments. According to [
The goal of experiment 1 was to detect epileptic segments. Therefore, only two output classes were needed: (AB) and (CDE). The first class represents healthy persons and the second epileptics. The classification in experiment 2 estimated accuracy for the division into 5 separate subsets (A, B, C, D, E) according to dataset description in section 1.1. Experiment 3 focused on the seizure detection. This experiment represents also binary classification. One class represents segments with seizure activity (E), while the second without the activity (ABCD). Experiment 4 aimed at estimation of the subsets of the classified segments from the dataset. It was similar to experiment 2, but the subset with seizure activity (E) was not included. Experiment 5 was also binary classification. The subset with seizure activity (E) was removed and the target of the classification was to estimate healthy (AB) and epileptic (CD) segments.
Result of each experiment was evaluated by accuracy (Table 4). The experiments
were performed in two versions. These versions are named as "No split" and "Split"
in Table 4. "No split" version agrees with the first method for estimation of the
accuracy of the classification in section 4.1, i.e. the whole dataset was used for OFDT
induction. In "Split" version, the accuracy of the classification was computed using
two sets – training (80% of instances in the original dataset) and testing (the
remaining 20% of instances in the original dataset). According to data in Table 4, the
accuracy of EEG signal classification is better for "No split" versions than for "Split". Need
to note that evaluations in [
In future investigation, other methods for fuzzy data analysis and classification should be used. Also, preliminary data transformation can be realized in many ways. For example, feature extractor which takes into account the output attribute can be used instead of PCA. The Welch’s method transforms signal from time domain to the frequency domain, but methods that can analyze signals in both domain exist. Example of such method is the wavelet transform. The important goal of this investigation is to develop a classification of EEG signal with maximal accuracy that can be used in medical decision support systems.
This work is partly supported by grants VEGA 1/0038/16 and VEGA 1/0354/17.