Research Article
General Science
Biomedical Engineering
We are sorry, but we are not currently accepting applications for postings.
In addition, you can continue to use the publications you have published until now.
We are sorry, but we are not currently accepting applications for postings.
In addition, you can continue to use the publications you have published until now.
The aim of this study is to present nonlinear symbolic gait time series analysis which helps to characterize the dynamic features of stride-to-stride variations of gait on a small time scale in aging and disease, identify relevant set of temporal features to detect gait abnormalities and thereby discriminate among healthy elderly, healthy young, and Parkinson disease gait signals. Besides computational efficiency, symbolic methods are also robust when noise is present. Since a mere binary partition cannot capture 2- and larger-variation ordinal patterns, we speculated that a higher number of partitions can better capture symbolic dynamics and performed symbolic time series analysis on elderly, young, and Parkinson disease gait signals. Six partitions in the data space showed significant differences in the histogram properties, symbol-sequence histogram statistics and complexity measures (modified Shannon entropy and forbidden words) of symbol sequences among the three groups. The symbolic measures were found to be significantly different from their surrogate counterparts implying that the fluctuations observed in the original time series may reflect nonlinear deterministic processes by the neuromuscular systems. Receiver operating characteristic plots demonstrate the high diagnostic ability of these complexity measures to discern elderly, young, and Parkinson disease subjects from each other. It is found that while complexity is increased and regularity is decreased a little in the aging process compared to healthy young state, complexity is decreased and regularity is increased considerably with the disorder in the diseased state. These findings could be of importance for clinical diagnostics, in algorithms for gait fall-risk stratification, and for therapeutic and fall-preventive tools of next generation.
Keywords:Coarse-graining, Complexity measures, Forbidden words, Gait analysis, Shannon entropy, Symbolic dynamics, Symbolic entropy, Symbolic time series analysis, Surrogate analysis, Word length
1） ShanthaNilaya, 107, Ananthnagar, Manipal-576104, India.
RecievedOct 7 2015 Acceptedfeb 16 2016 PublishedFeb 19 2016
Citation
Kamath C (2016) Symbolic time-series analysis to unravel gait dynamics in aging and disease. Science Postprint 1(2): e00057. doi:10.14340/spp.2016.02A0001.
Copyright©2016 The Authors. Science Postprint published by GH Inc. This is an open access article under the terms of the Creative Commons Attribution-NonCommercial-NoDerivs 2.1 Japan (CC BY-NC-ND 2.1 JP) License, which permits use and distribution in any medium, provided the original work is properly cited, the use is non-commercial and no modifications or adaptations are made.
FundingNot applicable.
Competing interestThere are no competing interests.
Ethics Not applicable
Corresponding authorChandrakar Kamath
AddressShanthaNilaya, 107, Ananthnagar, Manipal-576104, India.
E-mail chandrakar.kamath@gmail.com
Despite extensive preventive efforts falls are a major source of morbidity and mortality in the elderly and gait disordered patients. The results include significant injury, fractures, hospital admission, and may be even death [1, 2]. Fear of fall can give rise to lack of confidence which in turn may lead to restrictions in domestic and social activities. Though the causes of falls are multifactorial, impairments in gait and balance are found to be the most prevalent and sensitive risk factors [3].The wide-ranging effect of falls and the potentially high cost of these interventions demand an early detection of these impairments to facilitate appropriate therapeutic intervention as part of falls prevention strategy. Gait is a complex process with multiple inputs and multiple outputs. Gait stride interval is one of the outputs of this highly complex, integrated, and multilayered system. The temporal fluctuations in the stride interval provide a non-invasive means into the neural control of locomotion and its variation with aging and disease [4, 5]. Both, biological aging and neurodegenerative disorders are commonly associated with a degradation and/or breakdown in the complex dynamics of gait and motor activity. Physiological signals generated by nonlinear dynamic systems are nonstationary and more often demonstrate complex structures which cannot be interpreted easily [6]. Linear methods cannot fully describe the underlying complex dynamics and thus may miss potentially useful information while the conventional nonlinear methods suffer from the difficulty of dimensionality [6]. Further, many nonlinear methods require rather long time series to arrive at a reasonable estimate of the nonlinear measures and hence, are not suitable for very short data sets [6, 7]. From this perspective it is reasonable to resort to nonlinear methods like the symbolic time-series analysis, which can quantify system dynamics even for short time series [8]. Symbolic time series analysis is a powerful technique which can extract hidden features like the occurrence of frequent recurrent patterns [9, 10] or existence of missing/forbidden patterns in a time series [11]. However, it is to be noted that although this method is motivated by symbolic dynamics theory, it is not completely rigorous because the generating partitions are not defined in the presence of noise [9]. A generating partition is a partition in data space such that it provides a perfect symbolic description of the time series structure [10]. Even though some microscopic details of the dynamics may be lost on the symbolic level for non-generating partitions, most of the temporal correlations remain embedded in the structure of the symbol sequence distributions and most importantly, it yields meaningful results in the presence of observational and dynamical noise [12]. It has been clearly demonstrated that heuristically defined partitions which are not generating, symbolic analysis can provide powerful methods for characterizing and investigating a given time series [10]. The main rationale in choosing symbolic analysis is (1) gait involves cycles characterized by regularity in addition to balance components characterized by variability [13]. Unravelling the latter components from noise causing random error is a challenge. Symbolic analysis, being less sensitive to measurement noise, is definitely a better choice. (2) Unlike other nonlinear measures, symbolic measures are sensitive to time causality of the system dynamics i.e., the order in which measurements appear in the data. That is to say, these measures are explicitly concerned with the temporal evolution of structure of the data variability and hence, may unravel more meaningful information. (3) In general, time and frequency domain parameters are not able to distinguish between series with the same standard deviation and power spectrum, whereas symbolic analysis can readily distinguish between such series; for example, original time series and its surrogate [14]. Collet and Eckmann have shown that symbolic dynamics can provide almost a complete description of the dynamics of a time series under investigation [15]. Further, symbolic analysis provides new parameters independent of those derived from time domain or frequency domain. Other advantages of this analysis include increase in efficiency of numerical computations compared to what it would be for original data. Also, to apply symbolic analysis limited a priori knowledge of the disease states is sufficient and we do not have to make any assumptions about the structure of the underlying dynamical time series [16-18]. That is to say that the approach applies well to any type of (1-D) time series, be it linear or nonlinear, regular, deterministic or stochastic, chaotic, or noisy [17-19] and yields meaningful results in the presence of observational and dynamical noise [12]. Further, symbolic analysis has well defined measures of uncertainty and complexity which provide guidelines to fix an appropriate model for the given data. The approach of symbolic analysis of time series is recommended when the data is characterized by a low degree of precision, i.e., when the available information is essentially qualitative, where robustness to noise, speed, and/or cost are of highest priority [20]. A common practice in symbolic time series analysis is to apply threshold-crossing method in which one chooses an arbitrary partition or partitions, so that distinct symbols can be derived from the time series [21, 22]. This approach is popular for two reasons: (1) it is not possible to arrive at a generating partition in the presence of noise and (2) threshold-crossing is physically intuitive and natural idea [21, 22]. The number of possible symbols constitutes symbol-set size or alphabet size. Once the original time series is transformed into a symbol series, our objective is to look for characteristic temporal patterns through the analysis of the structure of the obtained symbolic-sequences. One useful approach is to select a specific number of sequential measurements as comprising a symbol-sequence/word and characterizing the resulting entire symbol series statistically by employing frequency distribution of symbol-sequences or words of different length [5], [23-26]. The number of partitions (uniform or non-uniform) and the frequency distribution of words of different length depend upon the trade-off between sufficient dynamical resolution and sufficient statistics to estimate the frequency/probability distribution [27]. The frequency distribution of symbol-sequences or words is, generally, termed symbol-sequence histogram. In this study, we use equiprobable partitioning with threshold-crossing method of symbolic time series analysis. Equiprobable partitioning allows distinction between stochastic and deterministic structures because recurrent patterns show up as peaks in the symbol-sequence histogram [28]. This implies that any significant deviation from equiprobable sequences is an indication of time correlation and determinism [18], [28].
Symbolic time series analysis has found profound application during the past few decades and opened new vistas for research in the field of complexity analysis, including multiphase flow [27] and combustion [28], astrophysics, geomagnetism, geophysics, classical mechanics, medicine and biology, plasma physics, robotics, communication, and linguistics [10], [29-30], economics [17], [31], encephalography [32], assessment of depth of anaesthesia [33], and cardiology (particularly, heart rate variability) [17], [34-39]. Symbolic time series analysis has been seldom tried to evaluate gait dynamics under different conditions. Aziz and Arif [40] employed threshold dependent symbolic entropy with binary-partition quantization (symbols 0 and 1) in the complexity analysis of stride interval time series and showed that the symbolic entropy can discern control from neurodegenerative disease subjects for a certain range of thresholds. Abbasi et al., [41] applied normalized corrected symbolic entropy on symbolic sequences and found that the voluntary output of human locomotors system is more complex during unconstrained normal walking as compared with slow, fast or metronomically paced walking. In a different study, Qumar et al. [42] compared multiscale entropy analysis and symbolic time series analysis and showed that the latter outperforms the former in discriminating normal and metronomically paced stressed walking. Many have proposed different approaches to unravel dynamics in gait time series of neuro-degenerative disease patients [43-46]. In this study, we show that because a commonly used binary partition is not sufficient to capture the gait dynamics (2-variation and higher-variation ordinal patterns) and hence, cannot discriminate properly healthy young, healthy elderly, and the PD groups, more partitions are necessary.
Biological aging is usually correlated with a degradation, degeneration, or breakdown in the intrinsic complex dynamics of the natural physiological fluctuations of the variability in gait and motor activity [47, 48]. It has been found that healthy dynamic stability is the outcome of a combination of specific feedback mechanisms and spontaneous properties of interconnected networks, and the weak connection between systems or within system is the reason for the degradation, degeneration, or disease, which is characterized by alterations in the stride dynamics. It is to be noted that gait disturbances need not inevitably accompany old age. A population based study has shown that 85% of 60-year-elders walk normally, while only 20% of 85-year-old subjects walk normally [49]. Another study has shown that gait disorders are prevalent in 35% of the population above age 70 years [4]. Thus, in general, aging population requires mobility related therapeutic and/or rehabilitative care that comprises a major concern in every healthcare system. With an aim to seek better markers of gait dynamics due to balance impairments, we employ symbolic time series analysis to capture these changes in intrinsic dynamics using symbolic entropy and forbidden words. We show that the results have implications for quantifying gait dynamics in healthy young, healthy elderly and pathological conditions, thus could be useful in the early diagnosis of subjects at risk of falls. Elderly subjects who had no history of falls and free from disease that might directly affect gait (including any neurological, musculoskeletal, cardiovascular, or respiratory disorders, or diabetes) have been chosen so that it is possible to find effect of aging on gait.
Linear stochastic processes can generate very complicated looking signals and that not all the structures that we observe in the time series are likely to be due to nonlinear dynamics of the system. To test the presence of nonlinear deterministic structures in the stride time series and thereby ascertain appropriateness of the application of our nonlinear approach, we carried out surrogate data analysis too.
The paper is organized as follows. The immediate following section discusses the database which is widely used in stride analysis. The next section discusses the pre-processing of the gait data used in this work. Thereafter, the next four sections explain the measures used to evaluate fluctuation magnitude and fluctuation dynamics of stride-to-stride variability, in detail. In particular, these sections deal with coefficient of variation (CV) and standard deviation of the detrended stride time series (SDdetrended), symbolic time series analysis and symbolic entropy and forbidden word features. This is followed by the sections related to statistical tests used and ROC analysis for decision making and binary classification and its significance in diagnosis. Next, we show the presence of nonlinear deterministic structures in the stride time series and appropriateness of the application of our nonlinear approach through surrogate data analysis. This is followed by a section in which we discuss the results and their implications.
The database used in this study can be downloaded from the public domain database at physionet.org (http://www.physionet.org/physiobank/database/gaitdb/) [50]. The database used in this study includes stride time series from two groups: Group-I and Group-II. Group-I includes 5 healthy young adults (23-29 years old), 5 elderly subjects (71-77 years old), and 5 Parkinson’s disease (PD) patients (60-77 years old). It was confirmed that the patients free from other pathologies which might lead to lower extremity weakness only participated. Over the duration of treatment the medication usage was not changed in the case of PD.
The healthy subjects (young and elderly) from the above classes were asked to walk continuously at their normal pace on an obstacle-free level ground along a long hallway for 15 minutes. The subjects from the PD class, however, were asked to walk at their normal pace up and down a long hallway for 6 minutes. This is because it is difficult to collect walking data for an extended period of time in clinical patients. The protocols differed slightly because of the use of two different locations. To measure the stride interval, ultra-thin force sensitive resistors were placed inside subject’s shoes. These sensors produce a measure proportional to the force applied to the ground during movement. The analog force signal was sampled at 300 Hz with a 12 bit A/D converter, using an ambulatory, ankle-worn microcomputer that also recorded the data. Subsequently, the time between foot-strikes was automatically computed. The method for determining the stride interval is a modification of a previously validated method that has been shown to agree with force-platform measures, a “gold” standard [4].
Group-II is also composed of stride time series from 5 healthy young adults (21-29 years old), 5 healthy elderly (71-77 years old), and 5 Parkinson disease patients (65-77 years old). Group-II is a subset of the database for neuro-degenerative diseases contributed by Hausdorff et al., (2000) [5] and Goldberger et al., (2000) [51] and can be downloaded from the same freely available public domain physionet.org mentioned above. The subjects from the different classes were asked to walk at their normal pace up and down a 77 m long hallway for 5 minutes. To measure the gait rhythm and the timing of the gait cycle, force sensitive insoles were place inside or under subject’s shoes. The output from the footswitches which corresponds to force signal is sampled at 300 Hz and digitized using an analog-to-digital converter and then stored in a recorder. The recorded data is then analyzed using a validated software that determined initial and end contact times (and also, stride and swing times) of each stride.
The protocols used differed a little in terms of total walking time. Thus, the database used in this study comprises stride time series from 10 healthy young adults, 10 healthy elderly subjects, and 10 PD patients.
Before the application of the method of analysis it is necessary to pre-process the gait data. To minimize the start-up effects the samples in the first 20 seconds of the recordings are removed [5]. Over the monitoring interval, each time the subject reached the deep curvature or end of the hall-way, the subject had to turn around and continue walking. The strides associated with these turning events are to be treated as outliers and should be removed from the rest of the time series. To remove the outliers we employed the three-sigma-rule [52], which states that 99.7% of the normally distributed probability values lie within the range of (mean ± 3.SD), where SD is the standard deviation. This implies that those samples which lie outside the range (median ± 3.SD) are outliers and hence, can be removed. In the removal process, median value and not mean value of the time series has been used because some outliers possessed large values and will affect the computation of the mean.
The linear measures are usually reported using the range, standard deviation, and coefficient of variation of the time series and these measures focus only on the magnitude of variation in a time series. These measures are concerned only with the distribution irrespective of the order in which the data points accumulate and thus potentially miss important inherent information [53].
In this study, two measures are used to assess the magnitude of stride-to-stride variability and gait unsteadiness: 1) CV, the coefficient of variation of the original stride time series and 2) SDdetrended, the standard deviation of the detrended stride time series [5]. It is important to note that both of these measures are not sensitive to changes in the ordering of the stride intervals or stride dynamics. That is to say, randomly ordering the time series will not affect these measures.
The CV expresses the standard deviation as a percentage of what is being measured relative to the sample or population mean. CV is a normalized measure of stride-to-stride variability. It is defined as the ratio of the standard deviation (SD) σ to mean µ as, CV = σ / µ. It shows the extent of variability in relation to mean of the population. The advantage is that it lets you compare the scatter of variables expressed in different units. CV may be preferred over SD as a measure of precision [5].
The standard deviation of a time series, in general, provides a measure of overall variations in the gait with respect to mean. It is a metric for absolute variability. This measure may be influenced by the trend in the data and may fail to differentiate between a walk with large changes from stride to next and one in which stride changes are small. To minimize effects of local changes in the mean the time series is detrended [5]. The detrended stride time series refers to time series from which the trend is removed. Detrending can be carried out by computing the first difference of the time series or removing the least-squares-fit straight line. In this study, the former method is used for detrending. SDdetrended is a measure of variability which minimizes the effects of the local changes in the mean. Hypothesizing that the stride interval variability would be altered by changes in neurological function associated with aging and certain disease states, first we investigate the linear statistics of stride time series of elderly, young, and PD subjects. Each gait record, in each group, is divided into segments, with 45 strides per segment. A thumb rule to select segment length is that it must be long enough to reliably estimate the measure of interest, while it must be short enough to accurately capture local activities. For each segment the variability measures of the stepping patterns, namely the coefficient of variation (CV) and standard deviation of the detrended stride time series (SDdetrended) are computed and the results of a particular class are averaged.
Fluctuation dynamics is about how the stride interval alters from one stride to the next, independent of the variance. Nonlinear methods provide information on the temporal sequential structure of the time series and allow explorations of the stride dynamics in aging and disease [47-49]. To quantify how the dynamics fluctuates over time during walk, we employed symbolic entropy, which is explained in detail below.
Symbolic analysis is an efficient approach to investigate the dynamic aspects of the signal of interest. The concept of symbolic analysis is based on a coarse-graining of the dynamics [54]. That is the range of original observations is partitioned into a finite number of regions and each region is associated with a specific symbolic value so that each observation is uniquely mapped to a particular symbol depending on the region into which it falls. Thus the original observations are transformed into a series of same length but the elements are only a few different symbols (letters from the same alphabet), the transformation being termed symbolization. The resulting symbol sequence may be characterized statistically by employing frequency distribution of words of different length [8], [11], [18, 19], [55, 56]. The number of quantization levels (uniform or non-uniform) and the frequency distribution of words of different length depend upon the trade-off between sufficient dynamical resolution and sufficient statistics to estimate the probability distribution [24].
If xi represents the time series and Si the corresponding symbolic time series that comprises the full range of dynamics of xi, the difference between the minimum and the maximum of xi is divided into a ξ quantization partitions each of size l = (max(xi) – min(xi)) / ξ. Hence, this transformation leads to an alphabet A = {0, 1, . . ., ξ-1} [56]. The transformation is as below.
In this work, the number of partitions is fixed to ξ = 6. The advantages of this kind of symbolization are (i) ease of computation and (ii) robustness against noise.
One general approach as suggested by Finney et al. [19] is that the partitions must be such that (i) the individual occurrence of each symbol is equiprobable with all other symbols or (ii) the measurement range covered by each region is equal [55, 56], [18, 19]. Such partitions permit distinction between stochastic and deterministic structure in the data and so can be a contribution to examine the stride interval time series. The transformations into symbols have to be selected context dependent. For this reason, we employ complexity measures on the basis of such context-dependent transformations, which have a close relationship to physiological phenomena and are relatively easy to interpret [7]. This way the study of dynamics simplifies to the description of symbol sequences. Some detailed information is lost in the process but the coarse, invariant, and robust dynamic behaviour is conserved and can be analyzed [7], [56]. After symbolization our objective is to look for characteristic temporal patterns by selecting a standard number of sequential measurements in the temporal order as comprising symbol sequences of specific length L. These symbol sequences are termed words and L is called the word length. We then observe the relative frequency of occurrence for all possible sequences as one indexes the symbol series through time. With the equiprobable partitioning convention, the relative frequency of each word/symbol-sequence derived for uniform distribution of patterns (truly random data, subject to availability of data) will be equal [28]. This implies that any significant deviation from equiprobable sequences is an indication of time correlation and determinism [27]. One approach that is useful for selecting an appropriate word length involves employing modified Shannon entropy/symbolic entropy. It is empirically found that as the word length is increased from 1 in steps of 1, the entropy value initially suddenly decreases, reaches a minimum and then gradually increases. The word length Lm corresponding to minimum entropy reflects the symbol sequence transformation that best distinguishes the data from a random sequence [28], [56]. Sequences that are too short (L < Lm) lose some deterministic information while those that are too long (L >> Lm) reflect noise and deplete data for reliable statistics. Thus a word length L equal to or a little greater than Lm (for which modified Shannon entropy is minimum), corresponds to almost an optimal length. We have empirically found that word lengths of three as well as four (L=3 and L=4) are suitable choices for unravelling the gait time series of the healthy (elderly and young) and PD groups for reasons explained in Results and discussion section.
The sequencing process involves definition of a template of finite length L that can be moved along the symbol series one symbol at a time, each step revealing a new word. If each possible new sequence is identified by a unique identifier the resulting series will be a new time series, termed word-sequence series. For example, symbolization with a number of partitions ξ = 6 and a word length L=4, there shall be a maximum of ξL (64=1296) words. This is a compromise of retaining important dynamical information, on one hand and of having a robust statistics to estimate probability distribution, on the other hand. The next step is to evaluate the relative frequency of occurrence of all possible words. A simple way to keep track word-sequence frequencies is to assign a unique value, called symbolic code, to each word by computing the corresponding base-10 value for each base-ξ word, where, ξ is the number of partitions. The observed symbol dynamics can be described in terms of symbol-sequence histogram, which is a plot of symbol-sequence frequencies as a function of symbolic codes/bins. This histogram provides a visualization of relative importance of all possible symbol dynamic patterns in the signal under investigation. Besides this visual representation, symbol-sequence histogram provides a basis for quantitative statistics. We employ three statistics in this study, two of which are measures of complexity namely, modified Shannon entropy, and forbidden words, and the third is Chi-square statistic (evaluated through Kruskal-Wallis test) used to compare relative frequencies of the individual symbol-sequences. Next, we evaluate the measures of complexity, i.e. Shannon entropy which we call symbolic entropy and forbidden words, explained in the following section. Because of the above rule of thumb for partitioning, for a truly random data the relative frequency of all possible symbolic codes will be equal (subject to availability of data) [27, 28]. This implies that any significant deviation from this equiprobable feature is an indication of time correlation and deterministic characteristic of the given data, the more the deviation the more is the data deterministic and time correlated.
Not to leave behind the dynamic information embedded in the symbol strings of word length L=3, we also investigated these words from a different perspective. There are several quantities that properly characterize such symbol strings of word length L=3. Next, from the above symbolization we compute ordinal patterns to describe relations within words of length L (3-consecutive time points, in our case) of a given time series. All possible patterns are grouped without loss into 3 major classes based on variability, referred to as (1) patterns with no or 0-variation, with all the three consecutive symbols being equal; these patterns signify regularity (2) patterns with 1-variation, with two consecutive symbols being equal and the remaining being different; these patterns usual/normal variations (3) patterns with 2-variations, with each symbol being different from the adjacent one; these patterns signify irregularity . We call these pattern classes by, respectively, (1) no-variation, (2) small-variation, and (3) large-variation pattern classes. Patterns with 1-variation are further divided into 4 subclasses, two subclasses with first two consecutive symbols being equal and the third symbol being different and remaining two subclasses with first symbol being different and the last two symbols being equal. Patterns with 2 variations are further divided into 4 subclasses, two subclasses with like variations and two subclasses with unlike variations. In all, we have 9 subclasses one for each ordinal pattern {0V, 1V1, 1V2, 1V3, 1V4, 2V1, 2V2, 2V3 and 2V4}. Representative illustrations in Fig. 1 show these ordinal patterns of consecutive three time-point data. Both x and y scales are arbitrary. Fig. 1(a) depicts 0-variation pattern, 1(b), 1(c), 1(d) and 1(e) depict 1-variation patterns and 1(f), 1(g), 1(h) and 1(i) depict 2-variation patterns. In this framework, we investigate the frequency distribution (relative frequencies) of each of the ordinal patterns from the alphabet {0V, 1V1, 1V2, 1V3, 1V4, 2V1, 2V2, 2V3 and 2V4}, tabulate the percentage of ordinal patterns and perform pattern classification.
Assuming that 3 patterns (3 major classes) from the alphabet {0V, 1V, and 2V} based on variability are sufficient for visual inspection to bring out better differences among the variability of groups we investigate the frequency distribution (relative frequencies) of each of the variability patterns from the alphabet {0V, 1V, and 2V}, plot the corresponding bar graph for the percentage of symbolic indices and perform pattern classification. On a percentage basis, the sum of normalized symbolic indices will be 100% (i.e., 0V% + 1V% + 2V% = 100%) and each can increase or decrease at the cost of others.
We employ two measures of complexity. (1) The Shannon entropy of the probability distribution of the symbol-sequence/words of length L, in this context usually called symbolic entropy (SE) and (2) the number/count of missing words in the probability distribution of the symbol-sequence/words of length L, usually called forbidden words (FW). Symbolic entropy is a measure of complexity of the time series. A larger value implies higher complexity and a smaller value implies a lower complexity. From the probabilities p(sk) of words sk of length k we evaluate kth order Shannon entropy (symbolic entropy) as given by [18, 19]
In this study, we have used modified/normalized symbolic entropy which is defined below [28], [56].
with 0.log(0)=0, N is the total number of observed sequences/words of length L, which correspond to non-zero frequency words. This choice of N instead of total number of all possible sequences is based on the fact that many of the words are not realized because of finite data-set length. The implication of this is to bias Hkn upwards when the number of possible sequences becomes large relative to the available data [28]. Clearly, Hkn is in its normalized form with 0 ≤ Hkn ≤ 1. This quantifier equals zero if the derived patterns are fully deterministic (i.e. the series is perfectly predictable from the past) and reaches its maximum value if and only if all values are independent and uniformly distributed.
Forbidden words (FWs) derived from symbolic word histogram provide a separate measure of system complexity [11]. The FWs refer to words in the distribution of words of length L which never or almost never occur [7], [10, 11], [14], [17]. A FW cannot appear in the distribution of words simply because it is not permitted by the dynamics of the time series. In practice however, these are defined as words which occur with a probability less than 0.001 [14]. A higher count of FW reflects a rather regular behaviour (presence of repetitive patterns) or reduced dynamics in the time series. If the time series is highly complex in Shannonian sense, only few FWs are found [14]. This method has been tried for the evaluation of heart rate and blood pressure variability in patients with dilated cardiomyopathy [55].
All linear and nonlinear measures are examined first for normality using Shapiro test. Since they are found to be skewed, Kruskal-Wallis tests are used to evaluate the statistical differences among the respective linear and nonlinear measures of the gait of healthy young, elderly, and PD groups. Next, multiple Wilcoxon rank-sum tests are performed to compare two groups at a time. The Wilcoxon rank-sum test is equivalent to a Mann-Whitney U-test. These non-parametric tests are used because they make no assumption about the underlying distribution of the data and also permit simultaneous testing of multiple groups. A p-value ≤ 0.05 is considered statistically significant. If significant differences between groups are found, then the ability of the nonlinear analysis method to discriminate gait of healthy young, elderly, and PD groups is evaluated using receiver operating characteristic (ROC) plots in terms of area under ROC curve (AUC) [57], one pair at a time. ROC curves are obtained by plotting sensitivity values (which represent that proportion of states identified as neurodegenerative disorder) along the y axis against the corresponding (1-specificity) values (which represent the proportion of the correctly identified healthy control states) for all the available cutoff points along the x axis. Accuracy is a related parameter that quantifies the total number of states (both healthy control and neurodegenerative disorder states) precisely classified. The AUC measures this discrimination, that is, the ability of the test to correctly classify stride of healthy control and neurodegenerative disorder groups and is regarded as an index of diagnostic accuracy. The optimum threshold is the cut-off point in which the highest accuracy (minimal false negative and false positive results) is obtained. This can be determined from the ROC curve as the closet value to the left top point (corresponding to 100% sensitivity and 100% specificity). An AUC value of 0.5 indicates that the test results are better than those obtained by chance, where as a value of 1.0 indicates a perfectly sensitive and specific test.
If the dynamics that generated the time series is not known or if the time series is noisy, in that case it is essential to investigate whether the amount of nonlinear deterministic dependencies is worth analyzing further or to treat the time series as stochastic. Hence, one of the first steps before applying the nonlinear technique to the data is to investigate if the application of such technique is justified. The main reason behind this rationale is that linear stochastic processes can generate very complicated looking signals and that not all the structures that we observe in the data are likely to be due to nonlinear dynamics of the system. The method of surrogate data test, introduced by Theiler et al. [58], has been a popular validating test to address this issue. This test facilitates to find out if the regularity of the data is most likely due to nonlinear deterministic structure or due to variations in system parameters or due to random inputs to the system.
This section presents a brief sketch of the idea in that connection. The starting point is to create an ensemble of random nondeterministic surrogate data sets that have the same mean, variance, and power spectrum as the original time series. The measured topological properties of the surrogate data sets are compared with those of the original time series. If, in case, the surrogate data sets and original data yield the same values for the topological properties (within the standard deviation of the surrogate data sets) then the null hypothesis that the original data is random noise cannot be ruled out. On the other hand, if the data under test is generated by a nonlinear process, the value for the topological property would be different from that of the surrogate data, and the null hypothesis that a linear method characterizes the data can be rejected.
The method of computing surrogate data sets with the same mean, variance, and power spectrum as the original time series, but otherwise random is as follows: First find the Fourier transform of the original time series, then randomize the phases, and find the inverse Fourier transform. The resulting time series is that of the surrogate data. More details can be found in [58]. However, Rapp et al. have shown that inappropriately constructed random phase surrogates can lead to false-positive rejections of the surrogate null hypothesis [59]. They found that numerical errors in the computation of Fourier transform was the cause for this problem and that Welch windowing the data can eliminate false-positive rejections of the surrogate null hypothesis. Hence, in this study, we made sure that Welch window was introduced before the computation of the Fourier transform of the stride interval segment whose surrogate needs to be found.
Before the application of the proposed method of analysis it is necessary to pre-process the gait data in all the three groups. To minimize the start-up effects the samples in the first 20 seconds of the recordings are removed [5]. Next, a median filter is applied to remove all the outliers. The outliers mostly are due to the turns at the end of the hallway and are filtered so that the intrinsic dynamics of the gait series can be studied. The stride time series before and after median filtering showed a strong correlation as indicated by the correlation coefficient in the Spearman test (ζ=1 and p=0). This also implies the effectiveness of the median filter in preserving the underlying dynamics while removing the extraneous data points associated with the changes in gait direction.
Representative examples of stride time series, over first 50 strides from continuous walk at their normal pace on an obstacle-free level ground, for the three groups are illustrated in Fig. 2. Least variability about the mean is found in the case of healthy young group and highest is found in the case of PD (between stride numbers 3 and 6) group. Healthy elderly group shows medium variability. After pre-processing the gait data as explained above, it is necessary to normalize the data by subtracting from each sample the mean of the time series and dividing the result by the standard deviation of the time series. Normalization removes most of the very large within and across-subject variability in the signal under consideration. Normalization also tends to produce values that are more exchangeable across different laboratories and research studies.
Unlike the above linear measures which focus on the magnitude of variation in a distribution irrespective of the order in which data points accumulate, the nonlinear measures that we used are explicitly concerned with the temporal evolution of structure of the data variability and hence, may unravel more meaningful information. In this study, first we investigate the linear statistics of stride time series of elderly, young, and PD groups. Each gait record in each group is divided into segments, with 45 strides per segment. A thumb rule to select segment length is that it must be long enough to reliably estimate the measure of interest, while it must be short enough to accurately capture local activities. For each segment the variability measures are computed and the results of a particular group are averaged. Table 1 shows the linear measures of fluctuation magnitude of stride-to-stride variability characteristic of elderly, young, and PD gait time series. All the variability measures are expressed as mean ± SD. The table shows differences among the three examined groups, possibly indicating differences in aging process and neuropathology. It is found that the average stride time is longer in the PD group compared to those of young and elderly groups. The two measures of fluctuation magnitude, CV and SDdetrend, are also considerably increased in the PD group compared to those of the young and elderly groups. The CV and SDdetrend of the young group are the lowest while those of PD are the highest. The elderly group showed intermediate values for both the parameters. These results indicate that the magnitude of stride-to-stride variability in elderly is increased by the aging process and in PD subjects is significantly increased by the neuro-degenerative disease. These significantly increased values suggest higher susceptibility for falls. These measures are based on the notion that a stable walking pattern has less variability and higher variability, as in elderly and PD subjects, is associated with higher vulnerability for falls. These results are in agreement with previous studies [60]. Kruskal-Wallis tests are performed to evaluate the statistical differences between the different measures of the three groups. The test detected significant group differences for all the measures. In the case of stride time CV, p=0 and chi-square =128.42. In the case of stride time SDdetrended, p=0 and chi-square =137.86. Also, it is observed that the influence of healthy aging on the magnitude of stride-to-stride fluctuations in stride interval is only a little as seen in healthy elderly, while the influence of healthy aging on the dynamics of gait is substantial as shown below. It is to be noted that the above linear statistical measures do not provide insight into how the motor system responds to disturbances that are present in the walking patterns over time. This implies that measures which can encapsulate time dependent changes in the walking patterns, like SE and FW may serve as better metrics for assessing balance. We speculate that the ability to typify short-term locomotor control might lie in the chosen pattern length and/or in the adopted procedure to group patterns into a small number of classes carefully to commensurate with the segment length of the time series.
With this, first we investigate dynamic features of particularly short stride-to-stride sequences by means of symbolic time series analysis. For this, each gait record is divided into segments each with 100 samples, in the case of healthy (elderly and young) and PD groups. We carefully avoided nonstationary segments of the gait records, since stationarity is a requirement for symbolic analysis. As mentioned above, we use equiprobable partitioning with threshold-crossing method of symbolic time series analysis for elderly, young, and PD group gait time series. Eq. (1) is applied on each segment to arrive at a symbol string with a range of ξ symbols. In order to arrive at a better choice for the number of partitions, we adopt an approximate method starting with two partitions, ξ=2 (two symbols: {0, 1}), refining into four ξ=4 (four symbols: {0, 1, 2, 3}), six ξ=6 (six symbols: {0, 1, 2, 3, 4, 5}), and eight partitions ξ=8 (eight symbols: {0, 1, 2, 3, 4, 5, 6, 7}) to arrive at a framework to capture the dynamics of the stride time series and highlight proper features and relevant patterns in the symbolic series. For each of the successive partitions, the resulting symbol series is characterized statistically by employing frequency distribution of words of lengths L=3 and L=4 and computing symbolic entropy (SE) and forbidden words (FW) for each segment of the three groups. The distribution of SE and FW for different partitions and word lengths for elderly, young, and PD groups is shown in Table 2. A detailed description of the computation of these nonlinear measures is given in one of the subsequent paragraphs for one case (ξ=6 and L=4).The results of Kruskal-Wallis test (p-value and chi-square) for each case, used to evaluate the statistical differences between the different measures of the three groups, is also listed in the last column of the Table 2. The following inferences can be made. (1) As the number of partitions increases the discrimination capability of the SE also increases as indicated by p-value and chi-square index. (2) For a given set of partitions as the word length increases the discrimination capability of the SE also increases as indicated by p-value and chi-square index. (3) Similar remarks can also be made with FW, except the case with ξ=2 and L=3. For this case no FWs are generated as can be seen from Table 2. (4) Though there are significant decreases in p-value and increases in chi-square index as the number of partitions increases from 2 to 6, the decrease in p-value and increase in chi-square index is not that significant for a change from 6 to 8. (5) Resorting to 8 partitions may unnecessarily increase the burden of numerical computations and memory requirements. (6) This indicates that a number of partitions equal to 6 and a word length equal to 4 are sufficient to discriminate healthy young, healthy elderly, and patients with PD from each other, in terms of SD and FW. Henceforth for all discussion we employ a number of partitions ξ=6. Though we found empirically that a sequence length L=4 is sufficient, to confirm an appropriate word/sequence length, however, we adopt the procedure described below.
Thus, the next step is to find an appropriate sequence length L ≥ Lm corresponding to minimum entropy for the symbolic time series analysis. As mentioned above, this involves plotting modified Shannon entropy vs. sequence length and observing the minimum which reflects the symbol sequence transformation that best distinguishes the data from a random sequence. Such plots of modified Shannon entropy vs. sequence length for ξ=6 partitions are shown in Fig. 3, for elderly, young, and PD groups. It is found that for elderly group Lm=2 and for young and PD groups Lm=3. We choose word lengths of three as well as four, i.e. L=3 and L=4, as suitable values for all the three groups. With this, first we discuss in detail dynamic features of particularly short stride-to-stride sequences in the order of 100 consecutive stride intervals by means of symbolic analysis with ξ=6 and L=4. Symbolic analysis is applied to each of these different segments to decide whether a particular segment belongs to elderly, young, or PD group. Eq. (1) is applied on each segment to arrive at a symbol string with a range of six possible symbols {0, 1, 2, 3, 4, 5}. From this symbolization we compute words/symbolic codes of length L=4. As mentioned above, with a number of symbols ξ=6 in the alphabet and a word length L=4, there shall be a maximum of ξL (64=1296) words/symbolic codes. The relative frequencies of each of the words/symbolic codes are computed for each segment and averaged over all the records of each group and the symbolic sequence histogram is plotted for each group. Figs. 4(a) through 4(c) compare these averaged symbolic-sequence histograms for the elderly, young, and PD subjects. The following observations can be made: (1) the relative frequency distribution of patterns for the three cases is found to be distinctly different. This indicates that there is a difference in the dynamics governing the gait time series of healthy elderly, healthy young, and PD subjects. (2) It is found from Fig. 4(b) for the young group that the dominant ten peaks in the descending order occur at the following symbolic codes/bins {778, 519, 562, 777, 772, 742, 526, 555, 771, 735}; from Fig. 4(a) for the elderly group it is found that the dominant ten peaks in the descending order occur at the following bins {778↓, 562↑, 777↓, 742↑, 772↓, 771↑, 519↓, 526↑, 561, 736}; and from Fig. 4(c) for the PD group it can be observed that the dominant ten peaks in the descending order occur at the following bins {778↑, 772↑, 777↑, 562↑, 742↑, 519↑, 736, 526↑, 561, 771↑}. The magnitudes of these peaks are different in each group. The arrow following the integer indicates an increase (↑) or decrease (↓) in magnitude relative to the corresponding magnitude in the healthy young group. Where the arrow is missing it implies that there is no corresponding peak in the young group. Among these eight peaks {778, 519, 562, 777, 772, 742, 526, 771} are common to all the three groups, with the peak at 778 being most dominant in that group. (3) However, the young group shows two dominant peaks at {555, 735}, which are not found in other two groups. These are possibly typical dominant peaks of the healthy young group. Likewise, both the elderly and PD groups show two dominant peaks at {561, 736}, which do not occur in the healthy young. These are possibly typical dominant peaks of the gait disorder groups. (4)
Also, for each segment the SE and FW values are computed and averaged over all the records of the respective group. The corresponding distribution of SE and FW are portrayed in Figs. 5(a) and 5(b), respectively, using Box-whisker plots and a comparison statistics (mean ± SD) are shown in Table 2. Intact values for SE are 0.561 ± 0.020 for healthy young, 0.575 ± 0.023 for healthy elderly, and 0.476 ± 0.045 for PD group. That is the SE is increased marginally in the elderly group while decreased significantly in the PD group compared to that of young group. This implies that locomotor system complexity is increased due to aging while decreased in disease condition. Intact values for FW are 1230.0 ± 6.213 for healthy young, 1226.0 ± 6.740 for healthy elderly, and 1250.0 ± 9.261 for PD group. That is the FW is decreased a little in the elderly group while increased considerably in the PD group compared to that of young group. This also, implies that locomotor system regularity is decreased due to aging while increased in disease condition (more of repetitive patterns). It is found that between FWs of young and elderly groups 608 FWs are common, between young and PD groups 753 FWs are common and between elderly and PD groups 607 FWs are common. The common FWs indicate that the symbolic analysis of both the groups do not support the patterns at these bins. Kruskal-Wallis tests are performed to evaluate the statistical differences among the SE and FW measures of the three groups. The test detected significant group differences (p=2.23 x10-05 and chi-square=21.42) for stride analysis of SE and (p=2.11x10-05 and chi-square=21.53) for stride analysis of FW. Healthy elderly showed comparatively higher entropy values, healthy young indicated medium entropy values, and Parkinson group showed lower values. This implies that healthy elderly and Parkinson groups exhibit high and low symbolic complexity respectively, while in the young states the subjects show intermediate values for symbolic complexity. Similarly, healthy elderly showed comparatively lower FW values, healthy young indicated medium FW values, and PD group showed higher values. This implies that healthy elderly and Parkinson groups exhibit low and high regularity respectively, while in the young states the subjects show intermediate values for regularity. Next, multiple Wilcoxon rank-sum tests are performed to compare two groups at a time. The Wilcoxon rank-sum test is equivalent to a Mann-Whitney U-test. Descriptive group results are shown in Table 3 for both SE and FW. The tests detected significant group differences as is evident from this table (p<0.05). This implies that both SE and FW of the stride dynamics are readily able to distinguish among elderly, young, and PD groups from each other.
To test the presence of deterministic structures in the stride time series and ascertain the aptness of our approach, we carried out surrogate data analysis. Fifteen surrogate series for each of the segmented original stride series are constructed as explained in the above section. The mean of surrogate SE and FW values for the fifteen surrogate series are computed and compared with those of the original series. Table 4 shows results of surrogate data analysis of symbolic measures, SE and FW, derived from stride interval series of healthy elderly, healthy young, and Parkinson groups. The values are expressed as mean±SD. In the elderly group, the SE and FW of the original series are 0.575±0.023 and 1226.0±6.740, respectively, and those of the surrogate series are 0.298±0.015 and 1272±2.347, respectively, while in the young group, SE and FW of the original series are 0.561±0.020 and 1230.0±6.213, respectively, those of the surrogate series are 0.289±0.012 and 1274±1.748, respectively. In the PD group, the SE and FW of the original series are 0.476±0.045 and 1250.0±9.261, respectively, and those of the surrogate series are 0.357±0.032 and 1264±3.024, respectively. The statistical significance of the differences between symbolic measures (SE and FW) of the original and surrogate series of elderly, young, and PD groups investigated using Wilcoxon rank-sum test is also specified in the Table 4. Interestingly, comparison between the respective SE and FW of the stride original and surrogate series, reveals highly significant differences (p-value < 0.0001) implying that the relevant patterns in the original time series cannot be considered present by chance. This indicates that the fluctuations observed in the original stride time series are not randomly derived, instead may reflect deterministic processes due to neuromuscular system. This substantiates the appropriateness of the application of the symbolic measures to the analysis of stride interval series.
Now, we evaluate the diagnostic capacity of SE and FW in different discriminations using ROC analysis. The corresponding ROC plots are shown in Figs. 6(a) and 6(b). The group results of evaluation of diagnostic parameters of the SE and FW in separating elderly, young, and PD group stride time series is summarized in Table 5. It is found that the SE and FW perform very well in its diagnostic ability, in separating elderly, young, and PD groups.
Next, we investigate the dynamic information embedded in the symbol strings of word length L=3 from a different perspective. The percentage frequency distribution of the nine ordinal patterns from the alphabet {0V, 1V1, 1V2, 1V3, 1V4, 2V1, 2V2, 2V3 and 2V4} for the elderly, young, and PD groups are shown in Fig. 7 and summarised in Table 6. Compared to the ordinal patterns in the healthy young the change in variability in the corresponding patterns of the healthy elderly and PD groups are indicated by upward (↑) or downward (↓) arrows representing respectively an increase or a decrease. The following inferences can be drawn. While the 0V% patterns predominate in the PD group, the 2V2% and 2V3% patterns predominate in the elderly group and in the healthy young group 1V1% and 1V4% predominate. An increase in 0V% signifies that gait variability becomes more periodic and predictable in the neurodegenerative disordered PD group. The changes in other patterns (increase or decrease) imply that the self adaptability of gait variability decreases or becomes disordered from that of the normal in elderly because of aging process and in PD patients because of neurological disorder. To arrive at a more comprehensive picture we investigate the frequency distribution of each of the variability patterns from the alphabet {0V, 1V, and 2V} and plot the percentage of ordinal patterns which provides a visual compact presentation to recognize the hidden patterns in the gait signal. The plots of the bar graph for the percentage of symbolic indices in the case of elderly, young, and PD groups are displayed in Figs. 8(a) through 8(c). The following conclusions can be drawn. The 0V% patterns are significantly increased in the PD group relative to those of healthy control group. The 1V% patterns predominate in the young group relative to those of elderly as well as PD groups. The 2V% patterns are increased in the elderly group. In the healthy control (elderly and young), 1V% (small-variation) and 2V% (large-variation) patterns dominate with roughly the same weight compared to 0V% (no-variation) patterns. This implies that the stride dynamics in the healthy control supports more variability patterns than no-variability patterns indicating an adaptation in stride variability. In the PD patients, 0V% increases at the cost of 2V% and 1V% so that 0V% patterns significantly dominate compared to both 1V% and 2V% patterns. This means that the stride dynamics in the disease group supports more no-variability patterns than small and large variability patterns indicating a loss of variability. From the above discussion it is clear that young subjects exhibit more of usual/normal patterns; elderly subjects show more of irregularity patterns; and PD patients exhibit more of regular patterns.
The important findings of this work can be summarised as below. The symbolic measures (SE and FW) were found to be significantly different from their surrogate counterparts implying that the fluctuations observed in the original time series may reflect nonlinear deterministic processes by the neuromuscular systems. This substantiates the appropriateness of the application of the symbolic time series analysis to analyse stride interval series. Symbolic dynamic analysis with 6 partitions and word length L=4 can discern healthy elderly, healthy young, and PD groups from each other with good accuracy. This implies clearly that a binary partition is definitely not sufficient for this analysis. This is because a binary partition cannot identify patterns with 2-variations. It is also found that complexity is increased and regularity is decreased a little in the aging process compared to healthy young state implying increased instability in gait. This finding is in agreement with [60]. On the other hand, complexity is decreased and regularity is increased considerably with the disorder in the Parkinson diseased state implying stereotyped walk and lower adaptability. This finding is in agreement with [43]. This means an optimal complexity and regularity are desirable for self adaptability as in healthy young group. The changes (increase or decrease) from the young patterns derived from 6 partitions and word length L=3 imply that the self adaptability of gait variability becomes disordered from that of the normal young, in elderly because of aging process and in PD patients because of neurological disorder. The plot of the percentage of ordinal patterns derived from the alphabet {0V, 1V, and 2V} (word length L=3) provides a visual compact presentation and a more comprehensive picture to recognize the hidden patterns in the gait signal. The healthy elderly exhibit 1V% (small-variation) and 2V% (large-variation) patterns dominance compared to 0V% (no-variation) patterns. Among the three classes of patterns the 2V% (large-variation) patterns show highest dominance. The healthy young also, exhibit 1V% (small-variation) and 2V% (large-variation) patterns dominance compared to 0V% (no-variation) patterns. In this case, however, the 1V% (small-variation) patterns show highest dominance. Thus, the healthy stride dynamics supports more variability patterns than no-variability patterns indicating an adaptation in stride variability. Unlike healthy subjects, 0V% patterns considerably increase at the cost of 2V% and 1V% in PD patients implying loss of large variability patterns in these patients. In this case, however, the 0V% (no-variation) patterns show highest dominance. The PD patients display least value for 2V% (large-variation) patterns. In all, irregularity is increased in the aging process while regularity is increased with the disorder in the diseased state. This new perspective might be useful in the evaluation of other neuropathological situations of the locomotor system as well.
A limitation of this study is the small sample size. Factors like high variance, age differences, and differing male-to-female ratios between groups will have an impact on the results when statistical analyses are carried out on small sample sizes. However, it has been shown that the effect of gender on usual gait patterns is considerably small [61, 62]. Though the effect of age on gait is complex, the effect of neurodegenerative disorders considerably predominates over the aging effects. This implies that the discrimination using this method stands irrespective of the above limitations.
The main objective of this study was to show that a symbolic dynamic analysis with six partitions and word length of four can capture stride dynamics and can discern healthy elderly, healthy young, and PD groups from each other with high accuracy. The increase or decrease from the young group patterns derived from six partitions and word length of three implies that the self adaptability of gait variability decreases or becomes disordered from that of the normal in elderly because of aging process and in PD patients because of neurological disorder. The plot of the percentage of ordinal patterns from the alphabet {0V, 1V, and 2V} provides a visual compact presentation and a more comprehensive picture to recognize the hidden variability patterns in the gait signals. The analysis reveals that irregularity is increased in the aging process while regularity is increased with the disorder in the diseased state. These findings could be of importance for clinical diagnostics, in algorithms for gait fall-risk stratification, and for therapeutic and fall-preventive tools of next generation. This new perspective might be useful in the evaluation of other neuropathological situations of the locomotor system as well.
 |
 |
 |
 |
 |
 |
 |
