Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://brain.bio.msu.ru/papers/Kaplan_Roeschke_Darkhovsky_Fell_2001_JNSciMeth_MacrostructChangePointSleep.pdf Äàòà èçìåíåíèÿ: Wed Jan 31 21:51:06 2001 Äàòà èíäåêñèðîâàíèÿ: Mon Oct 1 20:23:02 2012 Êîäèðîâêà:

/typeset1:/sco3/jobs1/ELSEVIER/nsm/week.02/Pnsm2979z.0011001on Jan 29 12:17:41 2001

Page

Mon

Journal of Neuroscience Methods 00 (2001) 000 ­ 000 www.elsevier.com/locate/jneumeth

Macrostructural EEG characterization based on nonparametric change point segmentation: application to sleep analysis
A. Kaplan a, J. Roschke c,*, B. Darkhovsky b, J. Fell ¨
a b c

c

Department of Human Physiology, Moscow State Uni6ersity, Moscow, 119899, Russian Federation Institute for Systems Analysis, Prosp. 60 Let Oktyabrya 9, Moscow, 117312, Russian Federation Department of Psychiatry, Uni6ersity of Mainz, Untere Zahlbacher Str. 8, 55131 Mainz, Germany Received 30 October 2000; received in revised form 6 January 2001; accepted 8 January 2001

Abstract

Keywords: Sleep EEG; Macrostructure; Nonstationarity; Nonparametric change-point segmentation; Sleep stage classification

UNCORRECTED

In the present investigation a new methodology for macrostructural analysis EEG characterization based on automatic segmentation has been applied to sleep analysis. A nonparametric statistical approach for EEG segmentation was chosen, because it minimizes the need for a priori information about a signal. The method provides the detection of change-points i.e. boundaries between quasi-stationary EEG segments based on the EEG characteristics within four fundamental frequency bands (delta, theta, alpha and beta). Polysomnographic data of 18 healthy subjects were analyzed. Our findings show that nonparametric change-point segmentation in combination with cluster analysis enables us to obtain a clear picture of the hierarchical macrostructural organization of sleep, which is impossible to deduce from the unsegmented EEG data. Analysis of correlations between classically defined sleep stages and piecewise stationary power step functions reveals that three basic patterns can be distinguished: SWS (stage III/stage IV), stage II and stage I/REM. In accordance with correlation analyses, cluster detection shows that the cyclic sleep patterns during the course of the night becomes clearly observable by implementation of only three classes. Since the described methodology is based on a minimum of a priori assumptions, it may be useful for the development of a new sleep classification standard, which goes beyond the established Rechtschaffen and Kales scheme. © 2001 Elsevier Science B.V. All rights reserved.

1. Introduction

The Rechtschaffen and Kales (1968) (R&K) system was the first universally accepted platform for sleep classification and thus enabled significant advances in sleep research during the past 30 years. Today, it is obvious that the R&K criteria implicate several limitations and shortcomings. One of the limitations is the fixed temporal resolution of 30 or 20 s. If a state transition occurs in the middle of an epoch the rater has nevertheless to choose one specific stage. The macrostructure of sleep is divided into the more or less heuristically motivated number of six discrete states (stage I ­ IV, REM, awake) according to R&K criteria.
* Corresponding author. Tel.: + 49-6131-177011; fax: + 49-6131176690. E -mail address: roeschke@mail.uni-mainz.de (J. Roschke). ¨

Different numbers or different groupings of sleep stages would be justified. The slow wave stages for example are only distinguishable by a quantitative criterion (amount of delta waves), so that the need for a differentiation into stage III and IV is questionable. On the other hand, evidence for a functional difference between consecutive REM episodes has been reported (Roschke et al., 1995). Since the R&K system was ¨ developed with respect to sleep data from young and healthy subjects, it often fails to adequately describe the sleep of elderly or sleep disturbed subjects. Furthermore, stage classification according to R&K leaves much room for subjective interpretation, so the interrater reliability ranges only at 80 ­ 90%. Therefore, many investigators today are searching for a new sleep classification standard which relies on objective computerized analysis (Hirshkowitz and Moore, 1994; Hasan, 1996). In order to obtain a char-

0165-0270/01/$ - see front matter © 2001 Elsevier Science B.V. All rights reserved. PII: S0165-0270(01)00331-4

PROOF


/typeset1:/sco3/jobs1/ELSEVIER/nsm/week.02/Pnsm2979z.0011001on Jan 29 12:17:41 2001
2 A. Kaplan et al. / Journal of Neuroscience Methods 000 (2001) 000 ­ 000

Page

Mon

acterization of the sleep process being independent of R&K terminology it is desirable to use as little a priori information as possible. The analyses presented in this pilot study was therefore only based on the knowledge that there are four fundamental EEG frequency bands (delta, theta, alpha, beta) determining the functionality of mental states during sleep. Since a nonparametric method was used for EEG segmentation, no additional a priori information was incorporated into the macrostructural characterization of sleep. Our hypothesis is that EEG variations during sleep can be described by a limited set of quasi-stationary segments determined by the four main frequency bands. The analysis of the EEG as a quasi-stationary process demands a special approach, which will be discussed in brief in the following.

1.1. EEG as a nonstationary process
Some years ago it was thought that the main laws of EEG dynamics could be studied on the basis of its probability-statistical estimations irrespective of the biophysical origin of cortical electrical processes (Lopes da Silva, 1981). As a result, a considerable body of work appeared concerning the stochastic properties of the EEG signal. The main conclusion was that the EEG may actually be described by the basic stochastic concepts (in other words, by probability distributions), but only at rather short realizations (usually not longer than 10 ­ 20 s), since the EEG turned out to be an extremely nonstationary process. The variability of power of the main spectral EEG components, e.g., for successive short-term (5 ­ 10 s) segments, ranged up to

1.2. The approaches to EEG segmentation
Assuming a minimal duration of stationary intervals the procedure of EEG segmentation into stationary fragments would consist of four stages. At the first stage, an EEG recording is divided preliminary into equal minimal (`elementary') segment lengths. Then, each segment is characterized by a certain set of features, e.g., spectral estimations or autoregression coefficients. At the third stage, using one of the multivariate statistical procedures, the elementary EEG segments are assigned to one of a number of classes accordingly to their characteristics. Finally, the boundaries between the segments belonging to a same class are erased. Thus, the EEG recording is transformed into a series of segments within which the EEG parameters remain relatively constant. Each of these stationary segments is characterized by its specific duration and typological features. This `fixed-interval' approach to the EEG segmentation was used in early works concerned with EEG segmentation (for a review see Barlow, 1985). With this approach the number of typical EEG segments really turned out to be restricted, not more than 15 ­ 35 for different EEGs, and the duration of the majority of segments did not exceed 4 s, which provided evidence for a piecewise EEG organization. However, a shortcoming of this segmentation method was that some of the initially defined intervals would necessarily fall on boundaries between the real stationary EEG segments. This led to the appearance of a variety of EEG frag-

Fig. 1. Occurrence of change-points (vertical lines) in an example sleep EEG (derivation C4-A1), which was filtered within the two spectral bands delta (l ) and theta (q ).

UNCORRECTED

PROOF

50 ­ 100% (Oken and Chiappa, 1988). It became clear that the routine statistical characteristics could be computed for the EEG only after its prior segmentation into relatively stationary intervals. This, in turn, required the development of techniques for the detection of the boundaries between the stationary segments in the EEG signal. The first positive findings in this line have not only directed the way for more correct estimation of the statistical EEG properties but, more importantly, provided the initial foundation for a novel understanding of the temporal EEG structure as a piecewise stationary process (Bodenstein and Praetorius, 1977). Nonstationary phenomena are present in EEG usually in form of transient events, such as sharp waves, spikes or spike-wave discharges which are characteristic for the epileptic EEG, or as alternation of relatively homogenous intervals (segments) with different statistical features (e.g., with different amplitude or variance) (Lopes da Silva, 1978). The transient phenomena have specific patterns, which makes it easily possible to identify them by visual inspection in most cases, whereas the identification of the homogenous segments of the EEG requires a certain theoretical basis.


/typeset1:/sco3/jobs1/ELSEVIER/nsm/week.02/Pnsm2979z.0011001on Jan 29 12:17:41 2001
A. Kaplan et al. / Journal of Neuroscience Methods 000 (2001) 000 ­ 000

Page
3

Mon

Fig. 2. Example of automatically segmented 8 h sleep EEG: The top trace shows the visual R&K scoring (based on 30 s epochs), where S1 ­ S4 and REM denote the classical sleep stages, 0 means awake and M are movement epochs. The following four traces are the averaged power values (mV2) within the four different spectral bands (delta; 1 ­ 3.5 Hz; theta: 4 ­ 7.5 Hz; alpha: 8 ­ 12.5 Hz; beta: 13 ­ 17 Hz) for the quasi-stationary segments as determined by change-point analysis. Table 1 Correlation coefficients between R&K scoring (indicator trace) and segmental indicator sequence in four spectral bands for one example EEG Variable S1 S2 S3 S4 S34 REM D­H -.12 -.34b .42b .82b .95b -.27 D­L -.28b .61b .16 .28b .34b -.72b T­H -.13 -.22 .27 .76b .81b -.29b T­L -.28b .54b .15 .27 .32b -.63b A -.17 .54b .16 .28b .33b -.73b B -.14 .59b .14 -.20b -.10 -.47b

UNCORRECTED

PROOF

a

a Marked correlations (b) are significant at PB0.05. Notation: S1­S4 and REM ­ classical sleep stages in according to R&K visual staging. D, T, A and B ­ the change-point hypnograms in delta, theta, alpha and beta frequency bands. The index H and L indicate the `High' and `Low' power threshold during preparation of the indicator sequences.


/typeset1:/sco3/jobs1/ELSEVIER/nsm/week.02/Pnsm2979z.0011001on Jan 29 12:17:41 2001
4 A. Kaplan et al. / Journal of Neuroscience Methods 000 (2001) 000 ­ 000

Page

Mon

ments, which contained transition processes and, hence, were not strictly stationary. In addition, the boundaries between stationary segments were defined rather roughly, with an accuracy not better than the duration of the fixed interval. To overcome these disadvantages, it was necessary to develop a segmentation procedure including adaptation of the segment boundaries to the real positions of the transitions between stationary intervals. The majority of procedures for the automatic detection of stationary EEG segments are based on this methodology, called adaptive segmentation (Bodenstein and Praetorius, 1977). In brief, the procedure of adaptive segmentation can be based on the estimation of the extent of similarity of an initially fixed EEG interval with an EEG interval of the same duration specified by a time window running along the EEG recording. The similarity index will drop sharply when the window runs over a segment boundary, giving a formal indication of the transition to the

following segment. The assumption is therefore that autoregressive methods, which predict the EEG amplitude at a given moment by analyzing a series of amplitudes at prior moments, are adequate for this task. The discordance between predicted and real EEG amplitude can be used as an indicator of a local nonstationarity. Methods of predicting time series are based on the assumption that their stochastic nature is substantially confined by certain dynamic rules. If mathematical models can be fitted to these regularities, the EEG amplitude will be predicted with a certain accuracy for a number of successive samples. Beyond the stationary segment to which the model parameters were fitted the prediction error will sharply increase, thus signaling the termination of the foregoing segment and the beginning of the next one. For the initial portion of this next segment, new model parameters can be computed, and then the search for the next boundary can be continued. Thus, the parameters of the mathematical EEG model

Fig. 3. Example of automatical clustering of 8 h sleep EEG: The top trace shows the visual R&K scoring, where St1 ­ St4 and REM denote the classical sleep stages, AWK means awake, and M are movements. The following four traces demonstrate the results of a cluster analysis of the 4-dimensional power vectors (number of classes: 2 ­ 5) for the original (unsegmented) sleep EEG.

UNCORRECTED

PROOF


/typeset1:/sco3/jobs1/ELSEVIER/nsm/week.02/Pnsm2979z.0011001on Jan 29 12:17:41 2001
A. Kaplan et al. / Journal of Neuroscience Methods 000 (2001) 000 ­ 000

Page
5

Mon

Fig. 4. Example of automatical clustering of 8 h sleep EEG: The top trace shows the visual R&K scoring, where St1 ­ St4 and REM denote the classical sleep stages, AWK means awake, and M are movements. The following four traces demonstrate the results of a cluster analysis of the 4-dimensional power vectors (number of classes: 2 ­ 5) for the change-point segmented sleep EEG. Table 2 Correlation coefficients between R&K scoring (indicator) trace and segmental indicator sequence in four spectral bands Variable S1 S2 S3 S4 S34 REM
a

UNCORRECTED

PROOF
a

D ­H -0.08 (0.03) -0.22 (0.04) 0.37b (0.03) 0.60b (0.04) 0.77b (0.03) -0.15 (0.03)

D­L -0.18 (0.05) 0.50b (0.04) 0.11 (0.03) 0.21 (0.02) 0.25 (0.02) -0.58b (0.02)

T­H -0.07 (0.03) -0.20 (0.03) 0.20 (0.03) 0.63b (0.03) 0.71b (0.02) -0.17 (0.02)

T­L -0.23b (0.04) 0.54b (0.04) 0.12 (0.02) 0.21 (0.02) 0.22 (0.02) -0.52b (0.02)

A -0.15 (0.03) 0.37b (0.03) 0.13 (0.02) 0.21 (0.02) 0.18 (0.02) -0.53b (0.03)

B -0.1 (0.03) 0.38b (0.03) 0.11 (0.02) -0.09 (0.02) -0.02 (0.03) -0.29 (0.03)

Cumulative data for sleep EEGs of 18 subjects (mean 9 S.E.M.). Marked correlations (b) are significant at PB0.05.

become the key element segment-to-segment transitions.

in

search

for

1.3. Inherent contradiction of parametric segmentation
In principle, parametric methods of adaptive segmen-

tation allow to describe adequately the piecewise stationary structure of the EEG signal. However, all these methods designed for the analysis of nonstationary processes are based on a procedure which may be applied only to stationary processes, namely on fitting a mathematical model for the EEG (usually an autorr-


/typeset1:/sco3/jobs1/ELSEVIER/nsm/week.02/Pnsm2979z.0011001on Jan 29 12:17:41 2001
6 A. Kaplan et al. / Journal of Neuroscience Methods 000 (2001) 000 ­ 000

Page

Mon

1.4. Nonparametric approach to EEG segmentation
Unlike parametric methods, nonparametric ones require no a priori information about probability distributions of random sequences. The problem of extracting such fragments from a signal recording which can be sufficiently well described by unique probabilistic mechanism is one of the main problems of a relatively new branch of mathematical statistics called statistical diagnosis. The first works in this direction were done by Page (1954) and during the last 20 ­ 30 years much progress occurred in this field. An overview on recent advances in this area can be found in (Basseville and Nikiforov, 1993). Nonparametric methods for the detection of the time of change for a sequence of independent random variables were first proposed by Bhattacharya and Johnson (1968). Their ideas were further elaborated in a number of works in the 1970s and 1980s. In the middle of the 1970s Darkhovsky and Brodsky proposed nonparametric change-point detection methods for a sequence of dependent random variables (results are summarized in (Brodsky and Darkhovsky, 1993). The basic idea of the statistics proposed by Darkhovsky and Brodsky was used in a subsequent work by Deshayes and Picard (1981) for the detection of change-points in the spectrum of a Gaussian random sequence. In the present pilot study, we investigated whether nonparametric

UNCORRECTED

2.2. Preprocessing of sleep EEG
In a first step, we extracted the spectral bands 1 ­ 3.5 Hz (delta), 4 ­ 7.5 Hz (theta), 8 ­ 12.5 Hz (alpha) and 13 ­ 17 Hz (beta, sleep spindle range; in sleep literature the spindle frequency range is often called sigma) from the EEG signals of channel C4 by application of a second order Butterworth filter. The filtered EEG signals were then transformed into a diagnostic sequence by calculating the autocorrelation values (see below). Since the present pilot study was devoted to the macrostructure of sleep EEG we did not analyze EEG changes on time intervals shorter than 5 s. We used a moving average with a window length of 5 s for the transformation of the filtered EEG into the diagnostic time series. Intervals corresponding to artifacts as identified by visual inspection were excluded from analysis.

2.3. Algorithm of change -point analysis
The methodology of nonparametric change point

PROOF

gressive one). It is evident that accurate fitting of a model can be achieved only for a stationary interval. The longer the interval, the finer the characteristics of the process that can be represented by the model. But the longer the analyzed EEG interval, the more probable the incidence of heterogeneities within it (McEwen and Anderson, 1975). If the model is constructed on a very short interval, it will be very rough and the results of segmentation based on the parameters of this model cannot be expected to be of high accuracy. Thus, parametric EEG segmentation methods carry a rather strong contradiction: segmentation into stationary fragments is impossible without construction of an adequate mathematical model, but such a model cannot be constructed without previous segmentation. Moreover, since the EEG is a highly composite and substantially nonlinear process (Steriade et al., 1990; Nunez, 1995; Fell et al., 2000), the development of a rigorous linear mathematical model adequately representing the intrinsic nature of the EEG is questionable. The parameters even of locally well-fitted models are in general not able to follow the time course of EEG signals (Wright and Liley, 1995; Kaipio and Karjalainen, 1997). Not only the parameters, but also the model structure would have to be modified in order to adequately describe the long time evolution of the EEG (Lopes da Silva, 1981; Jansen, 1991). Therefore, a need for the development of nonparametric EEG segmentation methods exists.

change point analysis is able to provide new insights into the macrostructural organization of the human sleep EEG. 2. Material and methods

2.1. EEG registration
Eighteen healthy volunteers (nine male, nine female) aged 24 ­ 71 years (mean: 48.5 9 15.3) recruited from the general public participated in the investigation. All reported to be in good health with regular sleep-wake patterns. There was no evidence of hypnotic drug abuse or more than moderate alcohol, caffeine or nicotine consumption. None of the participants had a past history or current symptoms of psychopathology or a medical condition known to influence sleep. Following an adaptation night to sleep laboratory conditions, polysomnographic data were recorded from 23:00 PM to 7:00 AM next day. Surface electrodes were placed on the skull (FP1, FP2, C3, C4, O1 and O2; 10 ­ 20 system) and mastoid to record electroencephalic activity, and at the outer canthi on the left and right eye to record eye movements. Furthermore, electromyographic activity was registered with electrodes fixed at the chin (submental EMG) and to the left leg (tibialis muscle). Interelectrode impedances were all below 5 kV. The EEG was digitized by a 12 Bit analog ­ digital-converter with a sampling frequency of fs = 200 Hz for further computer analysis. Visual analysis of the sleep EEG based on 30 s epochs was performed according to R&K (1968) by one experienced rater. Automatized nonparametric changepoint analysis was applied to the EEG derivation C4-A1 from sleep onset to final awakening.


/typeset1:/sco3/jobs1/ELSEVIER/nsm/week.02/Pnsm2979z.0011001on Jan 29 12:17:41 2001
A. Kaplan et al. / Journal of Neuroscience Methods 000 (2001) 000 ­ 000

Page
7

Mon

analysis is based on two main ideas. (1) It can be proven (Brodsky and Darkhovsky, 1993), that the detection of changes in any distribution function or some other probabilistic characteristic can be reduced (with any degree of accuracy) to the detection of changes in the mathematical expectation of some other random sequence formed by the initial one. This circumstance enables us to limit ourselves to the development of only one basic algorithm for detection of changes in the mathematical expectation, and not to create an infinite family of algorithms for detection of changes in arbitrary statistical characteristics. A new sequence constructed from the initial one, in which a change in expectation occurs, will be called a diagnostic sequence. For example, if the autocorrelation function of a sequence changes, then considering new sequences Vt (~ ) = xtx
t+~

, ~ = 0,1,2,...,

YN (n,l ) =

UNCORRECTED

n
1- nn NN
l

1n 1 %x- n k=1 k N - n

%
k=n+1

N

x

k

n

,

where 0 0 l 0 1, 1 0 n 0 N - 1, {xk }N= 1 is the realizak tion of the diagnostic sequence under investigation. N is the sample size of the diagnostic sequence (in our case corresponding to the whole night EEG). This family of statistics is a generalized variant of the Kolmogorov ­ Smirnov statistic, which is used for testing coincidence or difference of distribution functions of two samples (with fixed n ). In simple words, we calculate the difference between an arithmetic mean of the first n samples and an arithmetic mean of the last N ­ n samples times a factor depending on l. This calculation has to be done for all n, 1 0 n 0 N. Then, we compare the maximum of the differences over n (1 0 n 0 N ) with a special threshold. The threshold is calculated on the base of the limit (under N tends to infinity) characteristics of the statistic. We make a decision about stationarity of the EEG realization, if this threshold is not exceeded, whereas in the opposite case we detect a change-point. Any change-point estimation method can be characterized by the false alarm probability (i.e., the probability for a decision about the presence of change-points, when no change occurred), by the probability of false tranquility (i.e., the probability for the absence of change-points,

2.3.1. Calculation of the diagnostic sequence The diagnostic sequence Vt is constructed from the autocorrelation values (for ~ = 0) derived from the original EEG data:
Vt = xt â xt = x 2. t

2.3.2. Checking the homogeneity hypothesis Compute the value max{YN (n,l = 1):1 0 n 0 N - 1} pN and the threshold C (note that l = 1, i.e. the probability of false tranquility is minimal). If pN 0 C, then the homogeneity hypothesis is accepted (i.e., the absence of disorders) and the procedure is completed; in the other case, we go to the next step. The threshold is computed on the basis of the limit theorem in dependence on the given false alarm probability, which is set rather high at this stage. In brief, it can be shown that under weak conditions, for example, for stationary sequences P {max1 0 n 0 N-1

PROOF

we will reduce the problem to detection of changes in one of the sequences Vt (~ ). The sequences Vt (~ ) hereby consists of the autocorrelation values Vt for a specific delay ~. Changes in autocorrelation values correspond to variations in power spectra, since the power spectrum is equal to the Fourier transform of the autocorrelation function. In particular, the mean of Vt (0) is identical with the total power (Parseval's theorem). The time resolution of change-point analysis hereby is given by the time base of the diagnostic sequence. (2) The second idea of our approach is to detect change-points using the following family of statistics:

when there actually was a change) and by the estimation error (in time) for a change-point. For the above defined class of statistics these values are functions of the parameter l (this is true for any given threshold). It can be shown, that the above defined family of statistics gives asymptotically (as N tends to infinity) optimum estimates for the change-points under weak mathematical assumptions (Brodsky and Darkhovsky, 1993). An important property of these statistics is that the choice of l = 0 provides the minimum for the false alarm probability (i.e., the probability for a decision about the presence of change-points, when no change occurred). On the other hand, l = 1 corresponds to the minimum probability of false tranquility (i.e., the probability for the absence of change-points, when there actually was a change) and the choice l = 0.5 guarantees a minimal estimation error (in time) for a change-point. The basic parameter, which has to be specified by the user for the threshold calculation, is the false alarm probability under the statistic YN (n, l = 0). The lower the false alarm probability, the larger is the threshold for change point detection, and the larger are the changes in the characteristic under consideration, that will be detected. By adjusting the false alarm probability it is therefore possible to either focus on the analysis of macrostructural changes (high threshold analysis) or to investigate the microstructural organization of EEG (low threshold analysis). For the present study we applied a rather low false alarm level corresponding to a high change point threshold. We set the false alarm probability to 0.05 for step (c) of the algorithm (see below). On step (d) where superfluous change-points are eliminated, the false alarm level was decreased to 0.02. The main processing steps of the nonparametric change-point method adapted for EEG analysis (Brodsky et al., 1999) are listed in the following.


/typeset1:/sco3/jobs1/ELSEVIER/nsm/week.02/Pnsm2979z.0011001on Jan 29 12:17:41 2001
8 A. Kaplan et al. / Journal of Neuroscience Methods 000 (2001) 000 ­ 000

Page

Mon


N YN (n,0) \ C } tends to the value f (C ) 2  1 k= ( - 1)k + 1 exp ( - 2k 2(C /| )2) as N , where is the variance of the sequence (Brodsky and Darkhovsky, 1993). From this relation the theoretical threshold Cth for a given false alarm probability can be calculated. To adjust for the finite sample size the theoretical threshold is being multiplied by a correction value depending on size and correlation function of the sample. Correction values were experimentally determined by Monte Carlo modeling.

3. Results

3.1. Quasi -stationary macrostructure of sleep EEG
A typical example of the sleep EEG segmentation for the frequency bands delta and theta is shown in Fig. 1. Only a small fraction of the change points within delta and theta band occur at identical time points. High threshold change-point analysis usually revealed for each of the four frequency bands about 25 ­ 40 quasi-stationary macrosegments per night. The EEG segments between two change-points are homogeneous or quasi-stationary with respect to the applied threshold. Thus, it is statistically justified to characterize each quasi-stationary segment by the average EEG power within its time frame. In this way, a step function of EEG power values can be constructed for each frequency band. An example of the EEG power step functions during the course of the night is displayed in Fig. 2 (same sleep EEG as in Fig. 1). Compared with the classical hypnogram as classified according to R&K rules (upper trace) the step curves show a similar time course. The sleep cycles as characterized by classical evaluation are reflected by parallel variations of EEG power. The correspondence between the occurrence of a certain sleep stage (according to R&K rules) with the course of the EEG power step functions was further examined by a quantitative analysis.

2.3.3. The call it found
Z1:

Preliminary estimation of change -points global maximum of the statistic YN (n,l = 1), n1, is assumed to be the estimate of the first change-point. Now, two new samples: n1 + [mN ] 0 n 0 N

1 0 n 0 n1 - [mN ] and Z2:

UNCORRECTED

2.3.4. Rejecting of doubtful change -points The following subsamples are formed (s = 2,...,k - 1):
1 X1:1 0 n 0 n1 + (n2 - n1), 2 Xs :ns
-1

3.2. Quantitati6e comparison between 6isual and automatic segmental analysis
The R&K scorings were transformed into indicator sequences defined as a vector containing the symbols 1 and 0. Hereby, 1 corresponds to the occurrence of the specified sleep stage, 0 to the absence. For example, the indicator sequence for REM sleep consists of symbol 1 in case of EEG epochs where stage REM was identified; the other epochs are marked by symbol 0. In a similar way, the power step functions were transformed into binary sequences. Those epochs, where the power in the given frequency band exceeds a certain threshold P were marked with the symbol 1, the other epochs were marked with 0. Now, the degree of similarity between both indicator sequences can be estimated via Pearson correlation coefficients. The threshold P for the power sequences were chosen such that the absolute value of the correlation coefficient attained its maximum. In case of the delta and theta frequency band, two optimal thresholds (high and low) for different comparisons were found (Table 1). Correlation coefficients between R&K stages and change-point power sequences for one sleep EEG (same example as in Figs. 1 ­ 4) are shown in Table 1.

1 + (ns - ns 2 1 + (nk - n 2

-1

1 ) 0 n 0 ns + (n 2 )0n0N

s+1

- ns ),

Xk :nk

-1

k-1

Thus, inside each subsample Xi there is a single preliminary change-point estimate ni. Each sample is analyzed in analogy to stage (c), but with a lower false alarm probability. If the homogeneity hypothesis is accepted for a sample, then the corresponding change-point is rejected.

2.3.5. Final estimation of change -points For each sample Xi (of the volume Ni ) remaining after step (d) the statistic YNi (n,l = 0) is computed. The maximum point of the module for this statistic is assumed to be the final estimate of the i -th changepoint. Then the confidence interval is computed from the statistic YNi (n,l = 1/2).

PROOF

are formed. Here m is a number, which is computed by the size of the sample and the steepness of the statistics' maximum and gives the preliminary estimate of a confidence interval for the change-point. Then each of the new samples Z1 and Z2 is checked for homogeneity (step (b)), and if not the case, we go again to step (c). The procedure is repeated until we obtain statistically homogenous segments. As a result of step (c) we obtain a set of preliminary estimates of (ordered) change-points, where k is the preliminary estimate of the number of change-points.


/typeset1:/sco3/jobs1/ELSEVIER/nsm/week.02/Pnsm2979z.0011001on Jan 29 12:17:41 2001
A. Kaplan et al. / Journal of Neuroscience Methods 000 (2001) 000 ­ 000

Page
9

Mon

Correlations with a corresponding P -value smaller than 0.05 are marked as statistically significant. The cumulative data for the sleep EEGs of all 18 subjects are shown in Table 2. Significant differences of the averaged correlation coefficients from zero were estimated by Wilcoxon tests. Three basic patterns of correlation coefficients are distinguishable: S1/REM, S2, and S3/S4. Both, S1 and REM sleep appear to be inversely correlated to all frequency bands, especially to delta and theta power (low threshold) and to alpha power. Nevertheless, the inverse correlations between REM occurrence and delta, theta and alpha power are clearly larger than it is the case for S1. That means, a relative minimum of delta, theta and alpha power seems to be especially an indication for REM sleep. S2 is characterized by a positive correlation to delta and theta under a low threshold and to alpha and beta power. On the other hand, the slow wave stages S3 and S4 are mainly correlated to delta and theta power, when implementing a high power threshold.

course of sleep cycles during the night. When increasing the number of classes to 4 and 5, stage II and REM sleep as determined according to R&K rules are subdivided into separate stages in case of the example EEG.

4. Discussion In the present pilot study we investigated whether nonparametric change-point segmentation is a useful tool for EEG-characterization. In particular we applied the change-point methodology to the analysis of the macrostructural organization of sleep. Our approach was restricted to the analysis of the four fundamental EEG bands delta, theta, alpha and beta, without including other polygraphic signals like EOG or EMG. Since we implemented a nonparametric segmentation method, the only assumption on which our automatic analysis was based is, that the macrostructural organization of sleep can be grasped by monitoring the four fundamental EEG frequency bands. Thus, we followed a kind of ontologically minimalistic approach in order to obtain information, which is objective and independent from the established R&K criteria. The main result of this pilot study is that nonparametric change-point segmentation in combination with cluster analysis enables us to obtain a clear picture of the macrostructural organization of sleep, which is impossible to deduce from the unsegmented EEG data. By increasing the number of classes entering the cluster analysis, a hierarchical classification of functional states based on EEG dynamics can be achieved. Our findings show that the first differentiation occurs between SWS and the other stages (stage I, II and REM sleep) as defined by the R&K scheme. When implementing three classes, in most cases SWS, stage II and stage I/REM are being separated. Thus, the cyclic sleep pattern during the course of the night becomes clearly observable with three classes. Since we wanted to investigate the basic reliability of the change-point approach to macrostructural sleep analysis, we chose a low false alarm probability resulting in a rather coarse segmentation. In order to reveal a better temporal resolution, i.e. a more fine grained picture, a higher false alarm probability should be implemented. The results of the cluster analyses are corroborated by the outcome of the analysis of correlations between the frequency band specific power step functions and the indicator functions for the sleep stages as defined by R&K rules. Three different patterns of correlations can be clearly distinguished: SWS (stage III/stage IV), stage II and stage I/REM. SWS is significantly correlated to the delta and theta band, when the analysis is based on a high power indicator threshold. On the other hand, for a low power indicator threshold significant correla-

3.3. Cluster analysis of the segmental spectral structure of sleep EEG
In order to investigate whether the segmentation analysis reveals indications for separate sleep stages we performed cluster analyses on the power values within the four selected frequency bands. For this purpose, four dimensional vectors were constructed, where each vector component corresponds to the power values within one of the frequency bands. For each sleep EEG the collection of power vectors was classified into different clusters by k -means clustering (program package Statistica 5.0). This was done for the unsegmented sleep EEG data (5 s time window), as well as for the change-point segmented data. For the segmented data the power vectors were constructed from the averaged power values within the quasi-stationary segments. Figs. 3 and 4 show an example of the clustering of power values for an unsegmented sleep EEG (Fig. 3) compared with the same EEG after change-point segmentation (Fig. 4). Clustering of the unsegmented sleep EEG reveals frequent changes between classes and it appears almost impossible to deduce a macrostructure of sleep from the distribution of classes. On the other hand, clustering of the segmented EEG yields a clear macrostructural organization, which on first sight corresponds to the time course of sleep cycles as determined by classical R&K evaluation. The more classes are implemented, the more detailed is the macrostructural picture. In case of two classes, obviously a separation between slow wave sleep (SWS = stage III + stage IV) and the other stages ­ which in this example is mainly REM sleep ­ occurs. When shifting to three classes a differentiation between SWS, stage II and the other stages can be observed. Implementation of three classes appears to be sufficient to reveal a rough picture of the

UNCORRECTED

PROOF


/typeset1:/sco3/jobs1/ELSEVIER/nsm/week.02/Pnsm2979z.0011001on Jan 29 12:17:41 2001
10 A. Kaplan et al. / Journal of Neuroscience Methods 000 (2001) 000 ­ 000

Page

Mon

Acknowledgements This study was financially supported by the DFG (grant Ro 809/19-1). We thank Dipl. Ing. C. Schaeffner and Dr S. Shishkin for their valuable technical support and advice.

UNCORRECTED

tions between sleep stage II and delta and theta band are found. These correlations reflect the appearance of k -complexes, i.e. transient, low-frequent graphoelements during sleep stage II. The onset of sleep spindles during stage II corresponds to a significant correlation with the step function for the beta band. Relative minima for all four frequency bands as reflected by inverse correlations are characteristic for the occurrence of sleep stage I or REM sleep. Hereby, a minimum of delta, theta and alpha activity as expressed by pronounced negative correlation coefficients seems to be especially an indicator for REM sleep. This quantitative difference between stage I and REM sleep is probably caused by the intrusion of small body movements and the occurrence of residual alpha activity during stage I. In conclusion the present pilot study indicates that nonparametric change-point segmentation represents a helpful tool to obtain objective information about the macrostructural organization of sleep. The described methodology enables to grasp the cyclic macrostructure of sleep being based only on the assumption, that at least four fundamental EEG frequency bands are essential for brain functioning. The inclusion of other frequency bands probably will be necessary to obtain a more detailed picture. For example, muscle activity accompanying movements may be monitored by processing the gamma band. Analysis of additional nonEEG signals in order to catch the NREM-REM duality remains a crucial point for further consideration. Since the outlined approach is based on a minimum of a priori information, it may be useful for the development of a new sleep classification standard, which improves the established R&K scheme or goes beyond it. However, our results suggest that the same methodology should also be suitable for a robust analysis of functional shifts during waking state.

References
Barlow JS. Methods of analysis of nonstationary EEGs, with emphasis on segmentation techniques: a comparative review. J Clin Neurophysiol 1985;2:267 ­ 304. Basseville M, Nikiforov IV. Detection of abrupt changes: Theory and Application. Prentice Hall: Englewood Cliffs NY, 1993. Bhattacharya GK, Johnson R. Nonparametric tests for shifts at an unknown time point. Ann Math Statist 1968;23:183 ­ 208. Bodenstein G, Praetorius HM. Feature extraction from the electroencephalogram by adaptive segmentation. Proc IEEE 1977;65:642 ­ 52. Brodsky BE, Darkhovsky BS. Nonparametric Methods in ChangePoint Problems. Kluver Acad. Publ.: Dordrecht, 1993. Brodsky BS, Darkhovsky BE, Kaplan AY, Shishkin SL. Nonparametric Method for the Segmentation of the EEG. Comput Meth Prog Bio 1999;60:93 ­ 106. Deshayes J, Picard D. Testing for a change-point in a statistical model: rapport technique. Orsay: Universite de Paris-Sud, 1981. Fell J, Kaplan A, Darkhovsky B, Roschke J. Classification of mental ¨ states with nonlinear deterministic and stochastic EEG measures: a combined strategy. Acta Neurobiol Exp 2000;60:87 ­ 109. Hasan J. Past and future of computer-assisted sleep analysis and drowsiness assessment. J Clin Neurophysiol 1996;13:295 ­ 313. Hirshkowitz M, Moore CA. Issues in computerized polysomnography. Sleep 1994;17:105 ­ 12. Jansen BH. Quantitative analysis of the electroecephalograms: is there chaos in the future. Int J Biomed Comput 1991;27:95 ­ 123. Kaipio JP, Karjalainen PA. Simulation of nonstationary EEG. Biol Cybern 1997;76:349 ­ 56. Lopes da Silva FH. Analysis of EEG non-stationarities. Electroencephalogr Clin Neurophysiol 1978;34(suppl.):165 ­ 79. Lopes da Silva FH. Recent Advances in EEG and EMG Data Processing. Elsevier: Amsterdam, 1981, p. 95 ­ 115. McEwen JA, Anderson GB. Modeling the stationary and gaussianity of spontaneous electroencephalographic activity. IEEE Trans Biomed Eng 1975;22:361 ­ 9. Nunez P. Neocortical Dynamics and Human EEG Rhythms. Oxford Univ. Press. Oxford, 1995. Oken BS, Chiappa KH. Short-term variability in EEG frequency analysis. Electroencephalogr Clin Neurophysiol 1988;69:191 ­ 8. Page ES. Continuous inspection schemes. Biometrica 1954;1:100 ­ 15. Rechtschaffen A, Kales A. A manual standardized terminology, techniques and scoring system for sleep stages of human subjects. Public Health Service, NIH Publication No. 204, US Government Printing Office: Washington, DC, 1968. Roschke J, Mann K, Riemann D, Frank C, Fell J. Sequential ¨ analysis of the brain's transfer properties during consecutive REM episodes. Electroencephalogr Clin Neurophysiol 1995;96:390 ­ 7. Steriade M, Gloor P, Llinas RR, Lopes da Silva FH, Mesulam MM. Basic mechanisms of cerebral rhythmic activities. Electroencephalogr Clin Neurophysiol 1990;76:481 ­ 508. Wright JJ, Liley DTJ. Simulation of electrocortical waves. Biol Cybern 1995;72:347 ­ 56.

.

PROOF