How to Convert a Time Series to a Supervised Learning Problem in Python
Machine learning methods like deep learning can be used for time series forecasting.
Before machine learning can be used, time series forecasting problems must be re-framed as supervised learning problems. From a sequence to pairs of input and output sequences.
In this tutorial, you will discover how to transform univariate and multivariate time series forecasting problems into supervised learning problems for use with machine learning algorithms.
After completing this tutorial, you will know:
- How to develop a function to transform a time series dataset into a supervised learning dataset.
- How to transform univariate time series data for machine learning.
- How to transform multivariate time series data for machine learning.
Let’s get started.
Time Series vs Supervised Learning
Before we get started, let’s take a moment to better understand the form of time series and supervised learning data.
A time series is a sequence of numbers that are ordered by a time index. This can be thought of as a list or column of ordered values.
For example:
A supervised learning problem is comprised of input patterns (X) and output patterns (y), such that an algorithm can learn how to predict the output patterns from the input patterns.
For example:
|
|
X, y
1 2
2, 3
3, 4
4, 5
5, 6
6, 7
7, 8
8, 9
|
For more on this topic, see the post:
Pandas shift() Function
A key function to help transform time series data into a supervised learning problem is the Pandas shift() function.
Given a DataFrame, the shift() function can be used to create copies of columns that are pushed forward (rows of NaN values added to the front) or pulled back (rows of NaN values added to the end).
This is the behavior required to create columns of lag observations as well as columns of forecast observations for a time series dataset in a supervised learning format.
Let’s look at some examples of the shift function in action.
We can define a mock time series dataset as a sequence of 10 numbers, in this case a single column in a DataFrame as follows:
|
|
from pandas import DataFrame
df = DataFrame()
df[‘t’] = [x for x in range(10)]
print(df)
|
Running the example prints the time series data with the row indices for each observation.
|
|
t
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
|
We can shift all the observations down by one time step by inserting one new row at the top. Because the new row has no data, we can use NaN to represent “no data”.
The shift function can do this for us and we can insert this shifted column next to our original series.
|
|
from pandas import DataFrame
df = DataFrame()
df[‘t’] = [x for x in range(10)]
df[‘t-1’] = df[‘t’].shift(1)
print(df)
|
Running the example gives us two columns in the dataset. The first with the original observations and a new shifted column.
We can see that shifting the series forward one time step gives us a primitive supervised learning problem, although with X and y in the wrong order. Ignore the column of row labels. The first row would have to be discarded because of the NaN value. The second row shows the input value of 0.0 in the second column (input or X) and the value of 1 in the first column (output or y).
|
|
t t-1
0 0 NaN
1 1 0.0
2 2 1.0
3 3 2.0
4 4 3.0
5 5 4.0
6 6 5.0
7 7 6.0
8 8 7.0
9 9 8.0
|
We can see that if we can repeat this process with shifts of 2, 3, and more, how we could create long input sequences (X) that can be used to forecast an output value (y).
The shift operator can also accept a negative integer value. This has the effect of pulling the observations up by inserting new rows at the end. Below is an example:
|
|
from pandas import DataFrame
df = DataFrame()
df[‘t’] = [x for x in range(10)]
df[‘t+1’] = df[‘t’].shift(–1)
print(df)
|
Running the example shows a new column with a NaN value as the last value.
We can see that the forecast column can be taken as an input (X) and the second as an output value (y). That is the input value of 0 can be used to forecast the output value of 1.
|
|
t t+1
0 0 1.0
1 1 2.0
2 2 3.0
3 3 4.0
4 4 5.0
5 5 6.0
6 6 7.0
7 7 8.0
8 8 9.0
9 9 NaN
|
Technically, in time series forecasting terminology the current time (t) and future times (t+1, t+n) are forecast times and past observations (t-1, t-n) are used to make forecasts.
We can see how positive and negative shifts can be used to create a new DataFrame from a time series with sequences of input and output patterns for a supervised learning problem.
This permits not only classical X -> y prediction, but also X -> Y where both input and output can be sequences.
Further, the shift function also works on so-called multivariate time series problems. That is where instead of having one set of observations for a time series, we have multiple (e.g. temperature and pressure). All variates in the time series can be shifted forward or backward to create multivariate input and output sequences. We will explore this more later in the tutorial.
The series_to_supervised() Function
We can use the shift() function in Pandas to automatically create new framings of time series problems given the desired length of input and output sequences.
This would be a useful tool as it would allow us to explore different framings of a time series problem with machine learning algorithms to see which might result in better performing models.
In this section, we will define a new Python function named series_to_supervised() that takes a univariate or multivariate time series and frames it as a supervised learning dataset.
The function takes four arguments:
- data: Sequence of observations as a list or 2D NumPy array. Required.
- n_in: Number of lag observations as input (X). Values may be between [1..len(data)] Optional. Defaults to 1.
- n_out: Number of observations as output (y). Values may be between [0..len(data)-1]. Optional. Defaults to 1.
- dropnan: Boolean whether or not to drop rows with NaN values. Optional. Defaults to True.
The function returns a single value:
- return: Pandas DataFrame of series framed for supervised learning.
The new dataset is constructed as a DataFrame, with each column suitably named both by variable number and time step. This allows you to design a variety of different time step sequence type forecasting problems from a given univariate or multivariate time series.
Once the DataFrame is returned, you can decide how to split the rows of the returned DataFrame into X and y components for supervised learning any way you wish.
The function is defined with default parameters so that if you call it with just your data, it will construct a DataFrame with t-1 as X and t as y.
The function is confirmed to be compatible with Python 2 and Python 3.
The complete function is listed below, including function comments.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
from pandas import DataFrame
from pandas import concat
def series_to_supervised(data, n_in=1, n_out=1, dropnan=True):
“”“
Frame a time series as a supervised learning dataset.
Arguments:
data: Sequence of observations as a list or NumPy array.
n_in: Number of lag observations as input (X).
n_out: Number of observations as output (y).
dropnan: Boolean whether or not to drop rows with NaN values.
Returns:
Pandas DataFrame of series framed for supervised learning.
““”
n_vars = 1 if type(data) is list else data.shape[1]
df = DataFrame(data)
cols, names = list(), list()
# input sequence (t-n, … t-1)
for i in range(n_in, 0, –1):
cols.append(df.shift(i))
names += [(‘var%d(t-%d)’ % (j+1, i)) for j in range(n_vars)]
# forecast sequence (t, t+1, … t+n)
for i in range(0, n_out):
cols.append(df.shift(–i))
if i == 0:
names += [(‘var%d(t)’ % (j+1)) for j in range(n_vars)]
else:
names += [(‘var%d(t+%d)’ % (j+1, i)) for j in range(n_vars)]
# put it all together
agg = concat(cols, axis=1)
agg.columns = names
# drop rows with NaN values
if dropnan:
agg.dropna(inplace=True)
return agg
|
Can you see obvious ways to make the function more robust or more readable?
Please let me know in the comments below.
Now that we have the whole function, we can explore how it may be used.
One-Step Univariate Forecasting
It is standard practice in time series forecasting to use lagged observations (e.g. t-1) as input variables to forecast the current time step (t).
This is called one-step forecasting.
The example below demonstrates a one lag time step (t-1) to predict the current time step (t).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
from pandas import DataFrame
from pandas import concat
def series_to_supervised(data, n_in=1, n_out=1, dropnan=True):
“”“
Frame a time series as a supervised learning dataset.
Arguments:
data: Sequence of observations as a list or NumPy array.
n_in: Number of lag observations as input (X).
n_out: Number of observations as output (y).
dropnan: Boolean whether or not to drop rows with NaN values.
Returns:
Pandas DataFrame of series framed for supervised learning.
““”
n_vars = 1 if type(data) is list else data.shape[1]
df = DataFrame(data)
cols, names = list(), list()
# input sequence (t-n, … t-1)
for i in range(n_in, 0, –1):
cols.append(df.shift(i))
names += [(‘var%d(t-%d)’ % (j+1, i)) for j in range(n_vars)]
# forecast sequence (t, t+1, … t+n)
for i in range(0, n_out):
cols.append(df.shift(–i))
if i == 0:
names += [(‘var%d(t)’ % (j+1)) for j in range(n_vars)]
else:
names += [(‘var%d(t+%d)’ % (j+1, i)) for j in range(n_vars)]
# put it all together
agg = concat(cols, axis=1)
agg.columns = names
# drop rows with NaN values
if dropnan:
agg.dropna(inplace=True)
return agg
values = [x for x in range(10)]
data = series_to_supervised(values)
print(data)
|
Running the example prints the output of the reframed time series.
|
|
var1(t-1) var1(t)
1 0.0 1
2 1.0 2
3 2.0 3
4 3.0 4
5 4.0 5
6 5.0 6
7 6.0 7
8 7.0 8
9 8.0 9
|
We can see that the observations are named “var1” and that the input observation is suitably named (t-1) and the output time step is named (t).
We can also see that rows with NaN values have been automatically removed from the DataFrame.
We can repeat this example with an arbitrary number length input sequence, such as 3. This can be done by specifying the length of the input sequence as an argument; for example:
|
|
data = series_to_supervised(values, 3)
|
The complete example is listed below.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
from pandas import DataFrame
from pandas import concat
def series_to_supervised(data, n_in=1, n_out=1, dropnan=True):
“”“
Frame a time series as a supervised learning dataset.
Arguments:
data: Sequence of observations as a list or NumPy array.
n_in: Number of lag observations as input (X).
n_out: Number of observations as output (y).
dropnan: Boolean whether or not to drop rows with NaN values.
Returns:
Pandas DataFrame of series framed for supervised learning.
““”
n_vars = 1 if type(data) is list else data.shape[1]
df = DataFrame(data)
cols, names = list(), list()
# input sequence (t-n, … t-1)
for i in range(n_in, 0, –1):
cols.append(df.shift(i))
names += [(‘var%d(t-%d)’ % (j+1, i)) for j in range(n_vars)]
# forecast sequence (t, t+1, … t+n)
for i in range(0, n_out):
cols.append(df.shift(–i))
if i == 0:
names += [(‘var%d(t)’ % (j+1)) for j in range(n_vars)]
else:
names += [(‘var%d(t+%d)’ % (j+1, i)) for j in range(n_vars)]
# put it all together
agg = concat(cols, axis=1)
agg.columns = names
# drop rows with NaN values
if dropnan:
agg.dropna(inplace=True)
return agg
values = [x for x in range(10)]
data = series_to_supervised(values, 3)
print(data)
|
Again, running the example prints the reframed series. We can see that the input sequence is in the correct left-to-right order with the output variable to be predicted on the far right.
|
|
var1(t-3) var1(t-2) var1(t-1) var1(t)
3 0.0 1.0 2.0 3
4 1.0 2.0 3.0 4
5 2.0 3.0 4.0 5
6 3.0 4.0 5.0 6
7 4.0 5.0 6.0 7
8 5.0 6.0 7.0 8
9 6.0 7.0 8.0 9
|
Multi-Step or Sequence Forecasting
A different type of forecasting problem is using past observations to forecast a sequence of future observations.
This may be called sequence forecasting or multi-step forecasting.
We can frame a time series for sequence forecasting by specifying another argument. For example, we could frame a forecast problem with an input sequence of 2 past observations to forecast 2 future observations as follows:
|
|
data = series_to_supervised(values, 2, 2)
|
The complete example is listed below:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
from pandas import DataFrame
from pandas import concat
def series_to_supervised(data, n_in=1, n_out=1, dropnan=True):
“”“
Frame a time series as a supervised learning dataset.
Arguments:
data: Sequence of observations as a list or NumPy array.
n_in: Number of lag observations as input (X).
n_out: Number of observations as output (y).
dropnan: Boolean whether or not to drop rows with NaN values.
Returns:
Pandas DataFrame of series framed for supervised learning.
““”
n_vars = 1 if type(data) is list else data.shape[1]
df = DataFrame(data)
cols, names = list(), list()
# input sequence (t-n, … t-1)
for i in range(n_in, 0, –1):
cols.append(df.shift(i))
names += [(‘var%d(t-%d)’ % (j+1, i)) for j in range(n_vars)]
# forecast sequence (t, t+1, … t+n)
for i in range(0, n_out):
cols.append(df.shift(–i))
if i == 0:
names += [(‘var%d(t)’ % (j+1)) for j in range(n_vars)]
else:
names += [(‘var%d(t+%d)’ % (j+1, i)) for j in range(n_vars)]
# put it all together
agg = concat(cols, axis=1)
agg.columns = names
# drop rows with NaN values
if dropnan:
agg.dropna(inplace=True)
return agg
values = [x for x in range(10)]
data = series_to_supervised(values, 2, 2)
print(data)
|
Running the example shows the differentiation of input (t-n) and output (t+n) variables with the current observation (t) considered an output.
|
|
var1(t-2) var1(t-1) var1(t) var1(t+1)
2 0.0 1.0 2 3.0
3 1.0 2.0 3 4.0
4 2.0 3.0 4 5.0
5 3.0 4.0 5 6.0
6 4.0 5.0 6 7.0
7 5.0 6.0 7 8.0
8 6.0 7.0 8 9.0
|
Multivariate Forecasting
Another important type of time series is called multivariate time series.
This is where we may have observations of multiple different measures and an interest in forecasting one or more of them.
For example, we may have two sets of time series observations obs1 and obs2 and we wish to forecast one or both of these.
We can call series_to_supervised() in exactly the same way.
For example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
from pandas import DataFrame
from pandas import concat
def series_to_supervised(data, n_in=1, n_out=1, dropnan=True):
“”“
Frame a time series as a supervised learning dataset.
Arguments:
data: Sequence of observations as a list or NumPy array.
n_in: Number of lag observations as input (X).
n_out: Number of observations as output (y).
dropnan: Boolean whether or not to drop rows with NaN values.
Returns:
Pandas DataFrame of series framed for supervised learning.
““”
n_vars = 1 if type(data) is list else data.shape[1]
df = DataFrame(data)
cols, names = list(), list()
# input sequence (t-n, … t-1)
for i in range(n_in, 0, –1):
cols.append(df.shift(i))
names += [(‘var%d(t-%d)’ % (j+1, i)) for j in range(n_vars)]
# forecast sequence (t, t+1, … t+n)
for i in range(0, n_out):
cols.append(df.shift(–i))
if i == 0:
names += [(‘var%d(t)’ % (j+1)) for j in range(n_vars)]
else:
names += [(‘var%d(t+%d)’ % (j+1, i)) for j in range(n_vars)]
# put it all together
agg = concat(cols, axis=1)
agg.columns = names
# drop rows with NaN values
if dropnan:
agg.dropna(inplace=True)
return agg
raw = DataFrame()
raw[‘ob1’] = [x for x in range(10)]
raw[‘ob2’] = [x for x in range(50, 60)]
values = raw.values
data = series_to_supervised(values)
print(data)
|
Running the example prints the new framing of the data, showing an input pattern with one time step for both variables and an output pattern of one time step for both variables.
Again, depending on the specifics of the problem, the division of columns into X and Y components can be chosen arbitrarily, such as if the current observation of var1 was also provided as input and only var2 was to be predicted.
|
|
var1(t-1) var2(t-1) var1(t) var2(t)
1 0.0 50.0 1 51
2 1.0 51.0 2 52
3 2.0 52.0 3 53
4 3.0 53.0 4 54
5 4.0 54.0 5 55
6 5.0 55.0 6 56
7 6.0 56.0 7 57
8 7.0 57.0 8 58
9 8.0 58.0 9 59
|
You can see how this may be easily used for sequence forecasting with multivariate time series by specifying the length of the input and output sequences as above.
For example, below is an example of a reframing with 1 time step as input and 2 time steps as forecast sequence.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
from pandas import DataFrame
from pandas import concat
def series_to_supervised(data, n_in=1, n_out=1, dropnan=True):
“”“
Frame a time series as a supervised learning dataset.
Arguments:
data: Sequence of observations as a list or NumPy array.
n_in: Number of lag observations as input (X).
n_out: Number of observations as output (y).
dropnan: Boolean whether or not to drop rows with NaN values.
Returns:
Pandas DataFrame of series framed for supervised learning.
““”
n_vars = 1 if type(data) is list else data.shape[1]
df = DataFrame(data)
cols, names = list(), list()
# input sequence (t-n, … t-1)
for i in range(n_in, 0, –1):
cols.append(df.shift(i))
names += [(‘var%d(t-%d)’ % (j+1, i)) for j in range(n_vars)]
# forecast sequence (t, t+1, … t+n)
for i in range(0, n_out):
cols.append(df.shift(–i))
if i == 0:
names += [(‘var%d(t)’ % (j+1)) for j in range(n_vars)]
else:
names += [(‘var%d(t+%d)’ % (j+1, i)) for j in range(n_vars)]
# put it all together
agg = concat(cols, axis=1)
agg.columns = names
# drop rows with NaN values
if dropnan:
agg.dropna(inplace=True)
return agg
raw = DataFrame()
raw[‘ob1’] = [x for x in range(10)]
raw[‘ob2’] = [x for x in range(50, 60)]
values = raw.values
data = series_to_supervised(values, 1, 2)
print(data)
|
Running the example shows the large reframed DataFrame.
|
|
var1(t-1) var2(t-1) var1(t) var2(t) var1(t+1) var2(t+1)
1 0.0 50.0 1 51 2.0 52.0
2 1.0 51.0 2 52 3.0 53.0
3 2.0 52.0 3 53 4.0 54.0
4 3.0 53.0 4 54 5.0 55.0
5 4.0 54.0 5 55 6.0 56.0
6 5.0 55.0 6 56 7.0 57.0
7 6.0 56.0 7 57 8.0 58.0
8 7.0 57.0 8 58 9.0 59.0
|
Experiment with your own dataset and try multiple different framings to see what works best.
Summary
In this tutorial, you discovered how to reframe time series datasets as supervised learning problems with Python.
Specifically, you learned:
- About the Pandas shift() function and how it can be used to automatically define supervised learning datasets from time series data.
- How to reframe a univariate time series into one-step and multi-step supervised learning problems.
- How to reframe multivariate time series into one-step and multi-step supervised learning problems.
Do you have any questions?
Ask your questions in the comments below and I will do my best to answer.
![[x_{1},x_{2}, \cdots, x_{n}]](https://s0.wp.com/latex.php?latex=%5Bx_%7B1%7D%2Cx_%7B2%7D%2C+%5Ccdots%2C+x_%7Bn%7D%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
表示原始的时间序列的话，标准化指的是 
，其中 
和 
分别表示均值和标准差。最大最小值归一化指的是 
，其中 
分别表示这段时间内的最大值与最小值。![[x_{1},x_{2},\cdots,x_{n}]](https://s0.wp.com/latex.php?latex=%5Bx_%7B1%7D%2Cx_%7B2%7D%2C%5Ccdots%2Cx_%7Bn%7D%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
，基线提取就是：
分别指的是 
的基线和剩余项。
来提取基线。假设时间序列是 ![[x_{1},\cdots,x_{n}]](https://s0.wp.com/latex.php?latex=%5Bx_%7B1%7D%2C%5Ccdots%2Cx_%7Bn%7D%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
，
，
。也就是说 
。![X = [x_{1},\cdots,x_{m}]](https://s0.wp.com/latex.php?latex=X+%3D+%5Bx_%7B1%7D%2C%5Ccdots%2Cx_%7Bm%7D%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
和 ![Y = [y_{1},\cdots,y_{m}]](https://s0.wp.com/latex.php?latex=Y+%3D+%5By_%7B1%7D%2C%5Ccdots%2Cy_%7Bm%7D%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
而言，为了解决左右平移的问题，需要考虑一个偏移量 
，然后计算它们之间的内积。
![NCC \in [-1,1]](https://s0.wp.com/latex.php?latex=NCC+%5Cin+%5B-1%2C1%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
指的是 Normalized version of Cross-Correlation，![SBD \in [0,2]](https://s0.wp.com/latex.php?latex=SBD+%5Cin+%5B0%2C2%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
指的是 Shape-based distance。
![X=[x_{1},\cdots, x_{n}]](https://s0.wp.com/latex.php?latex=X%3D%5Bx_%7B1%7D%2C%5Ccdots%2C+x_%7Bn%7D%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
和 ![Y = [y_{1},\cdots, y_{n}]](https://s0.wp.com/latex.php?latex=Y+%3D+%5By_%7B1%7D%2C%5Ccdots%2C+y_%7Bn%7D%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
，那么以下陈述是等价的。
使得二维点集 
能够被很好的拟合好，也就是说此刻的方差较小。![[y_{1},\cdots,y_{n}]](https://s0.wp.com/latex.php?latex=%5By_%7B1%7D%2C%5Ccdots%2Cy_%7Bn%7D%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
的 Pearson 系数很高；
使得 ![[x_{1}/\mu_{1},\cdots,x_{n}/\mu_{1}]](https://s0.wp.com/latex.php?latex=%5Bx_%7B1%7D%2F%5Cmu_%7B1%7D%2C%5Ccdots%2Cx_%7Bn%7D%2F%5Cmu_%7B1%7D%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
与 ![[y_{1}/\mu_{2},\cdots,y_{n}/\mu_{2}]](https://s0.wp.com/latex.php?latex=%5By_%7B1%7D%2F%5Cmu_%7B2%7D%2C%5Ccdots%2Cy_%7Bn%7D%2F%5Cmu_%7B2%7D%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
几乎一致。
和 
来表示，也就是说：
，并且编码器和解码器都是前馈神经网络，也就是说：
其中 
和 
分别是编码层和解码层的激活函数，
和 
分别是编码层和解码层的矩阵和相应的向量。具体来说它们的矩阵大小分别是 
一定是要小于输入层的维度 
的。
，那么令 
就可以得到一个自编码器，而这个自编码器对于提取特征没有任何的意义。同理，当 
时，
是一个 
矩阵，
是一个 
矩阵。从线性代数的角度来看，有无数个矩阵 
满足 
。这种情况下对于提取特征也是没有意义的。而当 
时，其实无法找到矩阵 
使得 
如果存在 
那么
和 
等都是白盒函数。
而言，我们都可以研究该函数的以下性质：
和 
而言，多项式的根指的是使得 
的 
的解。特别的，对于二次多项式而言，也就是 
它的根可以表示为：
这个集合。下面我们来介绍一下如何计算一个函数的根。![[a,b],](https://s0.wp.com/latex.php?latex=%5Ba%2Cb%5D%2C&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
而且通过 
与 
两点，它也必定通过区间 ![[a,b]](https://s0.wp.com/latex.php?latex=%5Ba%2Cb%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
内的任意一点 
其中 
和 
那么必定存在 
使得 
。根据这个定理，我们可以提出二分法来计算函数的根。
的解，其一般步骤是：
并求出 
的取值；
那么 
就选择 ![[m,b]](https://s0.wp.com/latex.php?latex=%5Bm%2Cb%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
为新的区间，否则选择 ![[a,m]](https://s0.wp.com/latex.php?latex=%5Ba%2Cm%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
为新的区间；
计算这个点相应的函数取值 
与导数值 
然后写出通过点 
的切线方程，并且计算出该切线与横轴的交点 
i.e.
随着 
的解。
的时候，可以用右侧的式子来估计导数值，i.e.
并且它们距离函数 
然后令 
就可以得到函数的临界点（critical point），再根据周围的点导数的性质即可判断这个点是否是局部最大值或者局部最小值。
这 
个样本。根据 Weierstrass 逼近定理可以知道：
的连续函数可以用三角函数级数一致逼近。
，存在一个多项式 
使得对于任意的 ![x\in[a,b],](https://s0.wp.com/latex.php?latex=x%5Cin%5Ba%2Cb%5D%2C&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
有
那么我们可以找到一个多项式 
对每一个 
都成立。根据计算，可以得到该多项式是：
，每一个粒子 
都是 
。在每一轮迭代中，需要更新两个最值，分别是每一个粒子在历史上的最优值和所有粒子在历史上的最优值，分别记为 
（
）和 
。在第 
次迭代的时候，![\bold{v}_{i}(t+1) = \bold{v}_{i}(t) + c r_{1}[\bold{x}_{i}^{*}(t) - \bold{x}_{i}(t)] + c r_{2}[\bold{x}^{g}(t) - \bold{x}_{i}(t)],](https://s0.wp.com/latex.php?latex=%5Cbold%7Bv%7D_%7Bi%7D%28t%2B1%29+%3D+%5Cbold%7Bv%7D_%7Bi%7D%28t%29+%2B+c+r_%7B1%7D%5B%5Cbold%7Bx%7D_%7Bi%7D%5E%7B%2A%7D%28t%29+-+%5Cbold%7Bx%7D_%7Bi%7D%28t%29%5D+%2B+c+r_%7B2%7D%5B%5Cbold%7Bx%7D%5E%7Bg%7D%28t%29+-+%5Cbold%7Bx%7D_%7Bi%7D%28t%29%5D%2C&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
，并且 
是 ![[0,1]](https://s0.wp.com/latex.php?latex=%5B0%2C1%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
中间的随机数。
这个维度，当温度 
。假设目标函数是 
需要寻找 
，然后执行以下的程序：
；
，
，也就是 
，选择 
；
的概率来接受 
。
。
其中的 
，
不一定需要是显式的（所谓显式指的是能够精确写出 
或者最小值 
。
并且每一个 
的值域都在 
的定义域内都相差得不多，也就是这 
或者 
。
一般都是连续的特征，而不是那种类别特征。如果是类别的特征，并不是所有的启发式优化算法都适用，但是遗传算法之类的算法在这种情况下有着一定的用武之地。
![\bold{x}\in[-5.12,5.12]^{n}.](https://s0.wp.com/latex.php?latex=%5Cbold%7Bx%7D%5Cin%5B-5.12%2C5.12%5D%5E%7Bn%7D.&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
或者 Easom 函数（Chapter 2，Example 2.1，Search and Optimization by Metaheuristics）
![\bold{x} \in [-100,100]^{2}.](https://s0.wp.com/latex.php?latex=%5Cbold%7Bx%7D+%5Cin+%5B-100%2C100%5D%5E%7B2%7D.&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
份，其中 
计算每一个交点的函数取值，然后统计出其最大值或者最小值就可以了。实际中不适用，因为当 
的时候，这个是指数级别的计算复杂度。
的时间。
，需要寻找 
，可以选择 Gaussian 正态分布，并且可以同时修改 
的时候，都会以极大概率接受 
，因为此时 
。然后一开始都在四处游荡；
和 
，那么子代（children）的交叉可以定义为：
，使用 Gaussian 正态分布可以构造出一个后代如下：
是基于具体问题的，很难给出一个通用的值。
和 
两种策略。这里的 
表示从人口中产生的后代的数量。
策略中，
中选择出来的。
的方案，它整体来说其实只有一个人口。从当前的点 
。计算它们的函数取值 
。那么估算的梯度就可以计算出来：
新的个体定义为: 
如果 
那么 
如果 
那么 
，
。按照其递归公式来计算，我们可以详细写出前面的几项，那就是：
的矩阵 A 能够对角化，那就是存在可逆矩阵 P 使得
表示一个 
。如果把矩阵 P 写成列向量的形式，i.e. 
，那么以上的矩阵方程就可以转换为 
, 
。进一步来说，如果要计算矩阵 A 的幂，就可以得到：
,
和 
，它们所对应的特征向量分别是：
.
.
具有弱平稳性（Weak Stationary）指的是：
对于所有的 
都是恒定的；
对于所有的 
与 
的协方差对于所有的 
，可以定义 ACF 为
.
.
时刻的取值 
时刻的取值 
相关，其公式就是：
，
，并且 
满足 iid 条件。其中 
表示 Gauss 正态分布，它的均值是0，方差是 
。
是弱平稳的，i.e. 必须满足 
。
，则可以得到一些 AR(1) 模型的例子如下图所示：
.
.
.
,
,
.
. 从 
.
对于所有的 
都成立。也就是可以写成一个一维函数的迭代公式：
的收敛性，这里的 
表示函数 
,
，可以得到 
。这与 
，可以从公式上得到 
当 
.
，我们可以得到 
. i.e. 
.
.
as 
并且忽略误差项，因此可以得到简化版的模型形如：
.
，求解可以得到 
，i.e. 
。当 
都在单位圆内部的时候，也就是该模型 
满足稳定性的条件。
，该 p 阶差分方程
和余弦函数 
，只是平移了 
个长度而已。本文将会介绍一些基于形状的时间序列的距离算法，并且介绍如何在给定时间序列的情况下，在时间序列数据库中寻找相似的时间序列。
和 
。首先我们可以建立一个 
的矩阵，
位置的元素是 
，这里的 dist 可以使用 
范数。其次，我们想找到一条路径，使得这个矩阵的累积距离最小，而这条路则是两条时间序列之间的最佳匹配。在这里，我们可以假设这条路径是 
，其中 
的每个元素表示时间序列 Q 中的第 i 个元素和时间序列 C 中的第 j 个元素之间的距离. i.e. 
。
.
，有
最终的取值 
就是我们需要的解，也就是两条时间序列的 DTW 距离。按照上面的算法，DTW 算法的时间复杂度是 
。特别地，
时，则 
表示最后的距离；
时，则 
时，则 
表示最后的距离。
，则
![q[i]](https://s0.wp.com/latex.php?latex=q%5Bi%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
与 ![c[j]](https://s0.wp.com/latex.php?latex=c%5Bj%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
的话，i 与 j 需要满足 
，这里的 w 表示窗口长度。因此算法的描述如下：
取值范围是：对每一个 
，需要 
。
和一个时间序列的数据库 
。通过某种相似度或者距离计算方法，计算出给定的时间序列 
中最相似的时间序列。
。从数据库 
.
，给定一个窗口的取值 r，得到 
，
。
，有不等式 
成立。
.
在 [0,1] 区间上与 X 坐标轴所夹的图形面积，就使用了 Riemann 积分的思想。 他把 [0,1] 区间等长地切割成 n 段，每一段使用一个长方形去逼近 
，
表示这些区间长度的最大值，在这里 
。在每一个子区间上![[x_{i},x_{i+1}]](https://s0.wp.com/latex.php?latex=%5Bx_%7Bi%7D%2Cx_%7Bi%2B1%7D%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
上取出一个点 ![t_{i}\in[x_{i},x_{i+1}]](https://s0.wp.com/latex.php?latex=t_%7Bi%7D%5Cin%5Bx_%7Bi%7D%2Cx_%7Bi%2B1%7D%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
。而函数 
的意思是：
使得对于任意取样分割，当 
时，就有
.
，这里的 
是系数，
是可测集合，
表示指示函数。当 
上的 Lebesgue 积分是：
,
表示零函数，这里的大小关系表示对定义域内的每个点都要成立。
，而这里的 
和 
都是非负可测函数。所以可以定义任意可测函数的 Lebesgue 积分如下：
.![(R)\int_{a}^{b}f(x)dx = (L)\int_{[a,b]}f(x)dx](https://s0.wp.com/latex.php?latex=%28R%29%5Cint_%7Ba%7D%5E%7Bb%7Df%28x%29dx+%3D+%28L%29%5Cint_%7B%5Ba%2Cb%5D%7Df%28x%29dx&bg=ffffff&fg=2b2b2b&s=1&c=20201002)
.
；
.
，无法画出函数图像，它不是 Riemann 可积的，但是它 Lebesgue 可积。
这样的定义域而已。所以，之前所讨论的很多连续函数的想法都可以应用在时间序列上。
用 
来表示，其中 
。那么后者就是原始序列的一种表示（representation）。
，定义 PAA 的序列是：
，
.
。用图像来表示那就是：
的定义上稍作修改即可。
个符号来表示时间序列，那么我们其实可以考虑正态分布 
，用
来表示 Gauss 曲线下方的一些点，而这些点把 Gauss 曲线下方的面积等分成了 
表示 
。
，那么 
；如果 
，那么 
，在这里 
；如果 
，那么 
。
.
表示时间序列 X 的取值落在第 k 个桶的比例（概率），maxbin 表示桶的个数，len(X) 表示时间序列 X 的长度。
上的距离函数定义为 
，其中 
表示实数集合，并且函数 
满足以下几个条件：
，并且 
当且仅当 
;
，也就是满足对称性；
，也就是三角不等式。
（其中 
或者 
）上的向量空间 
与一个内积（映射）所构成，
，它满足以下设定：
，有 
的映射：
是同构映射。
和 
，于是可以使用欧几里德空间里面的 
, 
。
，则 
表是它们是完全一致的，如果两条时间序列 
，则 
表示它们之间是负相关的。
.
.
的性质：
表示两条时间序列持有类似的趋势， 它们会同时上涨或者下跌，并且涨幅或者跌幅也是类似的。
表示两条时间序列的上涨和下跌趋势恰好相反。
表示两条时间序列在单调性方面没有相关性。![d_{CORT}(X_{T},Y_{T}) = \phi_{k}[CORT(X_{T},Y_{T})]\cdot d(X_{T},Y_{T}),](https://s0.wp.com/latex.php?latex=d_%7BCORT%7D%28X_%7BT%7D%2CY_%7BT%7D%29+%3D+%5Cphi_%7Bk%7D%5BCORT%28X_%7BT%7D%2CY_%7BT%7D%29%5D%5Ccdot+d%28X_%7BT%7D%2CY_%7BT%7D%29%2C&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
可以用 
来计算，而
，可以定义自相关系数为：
,
分别表示该时间序列的均值和方差。该公式相当于是比较整个时间序列 
的两个子序列的相似度（Pearson 系数），这两个子序列分别是 
和 
。
，可以对每一个时间序列得到一组自相关系数的向量，用公式描述如下：
的情况，可以假定 
和 
。于是，可以定义时间序列之间的距离如下：
.
表示一个 
的矩阵。它有着很多种选择，例如：
表示单位矩阵。用公式表示就是
.
表示一个 
。此时相当于一个带权重的求和公式。
.
和 
两个距离公式。
,
.
，
，![n=[(T-1)/2]](https://s0.wp.com/latex.php?latex=n%3D%5B%28T-1%29%2F2%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
。这里的 ![[\cdot]](https://s0.wp.com/latex.php?latex=%5B%5Ccdot%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
表示 Gauss 取整函数。
.
,
，
，
和 
表示 
的标准差（sample variance）。
.
模型有自己的 AR 表示，因此可以得到相应的一组参数 
，所以，对于每一条时间序列，都可以用一组最优的参数去逼近。如果
和 
对于时间序列 
和 
的参数估计，则 Piccolo 距离如下：
,
，
当 
，并且 
当 
。
当 
，并且 
当 
。
和 
表示 
模型对于 
，
和 
表示时间序列的方差，
和 
表示时间序列的 sample covariance 矩阵。
的结构，i.e. 
，这里的 
表示 AR 模型的参数，
表示白噪声（均值为 0，方差为 1 的 Gauss 正态分布）。于是可以从这些参数定义 LPC 系数如下：
，
当 
，
当 
。
.
范数的距离，基于相关性的距离，基于周期图表的计算方法，基于模型的计算方法。
![\text{skewness}(X) = E[(\frac{X-\mu}{\sigma})^{3}]=\frac{1}{T}\sum_{i=1}^{T}\frac{(x_{i}-\mu)^{3}}{\sigma^{3}},](https://s0.wp.com/latex.php?latex=%5Ctext%7Bskewness%7D%28X%29+%3D+E%5B%28%5Cfrac%7BX-%5Cmu%7D%7B%5Csigma%7D%29%5E%7B3%7D%5D%3D%5Cfrac%7B1%7D%7BT%7D%5Csum_%7Bi%3D1%7D%5E%7BT%7D%5Cfrac%7B%28x_%7Bi%7D-%5Cmu%29%5E%7B3%7D%7D%7B%5Csigma%5E%7B3%7D%7D%2C&bg=ffffff&fg=2b2b2b&s=1&c=20201002)
![\text{kurtosis}(X) = E[(\frac{X-\mu}{\sigma})^{4}]=\frac{1}{T}\sum_{i=1}^{T}\frac{(x_{i}-\mu)^{4}}{\sigma^{4}} .](https://s0.wp.com/latex.php?latex=%5Ctext%7Bkurtosis%7D%28X%29+%3D+E%5B%28%5Cfrac%7BX-%5Cmu%7D%7B%5Csigma%7D%29%5E%7B4%7D%5D%3D%5Cfrac%7B1%7D%7BT%7D%5Csum_%7Bi%3D1%7D%5E%7BT%7D%5Cfrac%7B%28x_%7Bi%7D-%5Cmu%29%5E%7B4%7D%7D%7B%5Csigma%5E%7B4%7D%7D+.&bg=ffffff&fg=2b2b2b&s=1&c=20201002)
![[\min(X_{T}), \max(X_{T})]](https://s0.wp.com/latex.php?latex=%5B%5Cmin%28X_%7BT%7D%29%2C+%5Cmax%28X_%7BT%7D%29%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
这个区间等分为十个小区间，那么时间序列的取值就会分散在这十个桶中。根据这个等距分桶的情况，就可以计算出这个概率分布的熵（entropy）。i.e. Binned Entropy 就可以定义为：
个桶的比例（概率），
表示桶的个数，
表示时间序列 
的长度是 
，同时 Approximate Entropy 函数拥有两个参数，
，下面来详细介绍 Approximate Entropy 的算法细节。
，可以计算出哪些向量与 
较为相似。i.e.
范数。
会基于具体的时间序列具体调整；
表示集合的元素个数。根据度量 
）的定义可以知道
，因此 Sample Entropy 总是非负数，i.e.
.
，这里n表示有n个事件发生。时间序列（S）表示为
，这里的m表示时间序列的长度。时间序列的时间戳可以选择一个等差序列，等差用
来表示，并且
，and 
+
来表示某个事件，
表示序列S在事件
表示序列S在事件
和
应该是不一样的。
，当且仅当
，当且仅当
(or 
)。如果
(or 
)。
来做例子，
是随机选择的，
，可以标记为
，其中
+
。
when 
when 
。可以使用记号
，其中
，
是随机选择的。
而言，
表示
中距离x最近的第r个元素，对于两个不相交的集合
和 
，可以定义方程：
when 
,
when otherwise.
表示x与x的第r个最近的邻居是否在同一个子集内。
,
小，则说明两类samples 
混合得非常好，表示无异常情况；如果
遵循标准Gauss分布，其参数是
+
, 
+
,
+
, 
+
有显著的不同，当
，在这里，参数可以按照以下标准设置：
for 
，
for 
。
并且它与
。
。
的概念。
而言，其中n是E中的事件个数。
.
，可以得到 
或者 
，可以得到 
或者 
是 True 表示 
是 True 表示 
，其中p是样本的总个数。
，而不是
，因为 
是递增排列的，并且 best-so-far > 0.
to obtain 5 typical features from EWMA; Holt-Winters has three [0,1] valued parameters 
. To choose 
, we have 
features; In ARIMA, we can estimate their “best” parameters from the data, and generate only one set of parameters, or one configuration for each detector.
, then 
5-fold prediction
, then 
+
, where 
is the best cThld of the (i-1)-th week. 
is the predicted cThld of the i-th week, and also the one used for detecting the i-th week data. ![\alpha\in [0,1]](https://s0.wp.com/latex.php?latex=%5Calpha%5Cin+%5B0%2C1%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
is the smoothing constant.
. As 
in this paper.
is when a query is submitted; 
is when the result HTML file has been downloaded; 
is when a brower finishes parsing the HTML; 
is when the page is completely rendered. SRT is measured by 
, the user-received search response time.
is the server response time of the HTML file, which is recorded by servers; 
is the network transmission time of the HTML file; 
is the browser parsing time of the HTML; 
is the remaining time spent before the page is rendered, e.g. download time of images from image servers.
,
affects SRT.
? What SRT components (e.g. 
and 
to get a variant condition type 
. In the past days, we have the number of HSRT events in total, the number of HSRT events in condition 
. As a result, we believe the historical data based comparison can provide a reasonable estimate of the attribute effects. The comparison between 
(row 7)?
(row 5, 10, 11, 12)?
来表示，其中 
。同时假设在语料库中出现的所有词语的集合是 
。
在该文件中出现的频率。词频通常定义为：
指的是词语 
则是文件 
，其中 
是指示函数，
+ 
+ 
，其中 
，或者 K 直接取值为 0.5 即可。
表示的是在语料库中包含词语 
的文件个数。
+ 
，
+ 
，
，
，
。原因是 “this” 这个词语在两个文件中都出现了，是一个常见的词语。
，
, 
，
，
。原因是 “example” 这个词语在第一份文件中没有出现，第二份文件中出现了。
。
。
![A[0],A[1],\cdot\cdot\cdot,A[n-1]](https://s0.wp.com/latex.php?latex=A%5B0%5D%2CA%5B1%5D%2C%5Ccdot%5Ccdot%5Ccdot%2CA%5Bn-1%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
，那么质心就是 ![\sum_{i=0}^{n-1}A[i]/n](https://s0.wp.com/latex.php?latex=%5Csum_%7Bi%3D0%7D%5E%7Bn-1%7DA%5Bi%5D%2Fn&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
；![num[j]](https://s0.wp.com/latex.php?latex=num%5Bj%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
表示。![dataMat[0]](https://s0.wp.com/latex.php?latex=dataMat%5B0%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
而言，自成一类。i.e. 质心就是它本身 ![C[0]=dataMat[0]](https://s0.wp.com/latex.php?latex=C%5B0%5D%3DdataMat%5B0%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
，该聚簇的元素个数就是 ![num[0]=1](https://s0.wp.com/latex.php?latex=num%5B0%5D%3D1&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
，当前所有簇的个数是 
。
，进行如下的循环操作：
个簇，第 j 个簇的质心是 ![C[j]](https://s0.wp.com/latex.php?latex=C%5Bj%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
，第 j 个簇的元素个数是 
。![d= \min_{0\leq j\leq K^{'}-1}Distance(dataMat[i],C[j])](https://s0.wp.com/latex.php?latex=d%3D+%5Cmin_%7B0%5Cleq+j%5Cleq+K%5E%7B%27%7D-1%7DDistance%28dataMat%5Bi%5D%2CC%5Bj%5D%29&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
，其中的 Distance 可以是欧几里德空间的 
范数，对应的下标是 
。i.e. ![j'=argmin_{0\leq j\leq K'-1}Distance(dataMat[i],C[j])](https://s0.wp.com/latex.php?latex=j%27%3Dargmin_%7B0%5Cleq+j%5Cleq+K%27-1%7DDistance%28dataMat%5Bi%5D%2CC%5Bj%5D%29&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
。
或者 
，则把 ![dataMat[i]](https://s0.wp.com/latex.php?latex=dataMat%5Bi%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
加入到第 ![C[j'] \leftarrow (C[j']*num[j]](https://s0.wp.com/latex.php?latex=C%5Bj%27%5D+%5Cleftarrow+%28C%5Bj%27%5D%2Anum%5Bj%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
+ ![dataMat[i])/(num[j]](https://s0.wp.com/latex.php?latex=dataMat%5Bi%5D%29%2F%28num%5Bj%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
+ 
，![num[j'] \leftarrow num[j']](https://s0.wp.com/latex.php?latex=num%5Bj%27%5D+%5Cleftarrow+num%5Bj%27%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
+ 
+ ![num[K'-1]=1](https://s0.wp.com/latex.php?latex=num%5BK%27-1%5D%3D1&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
，![C[K'-1]=dataMat[i]](https://s0.wp.com/latex.php?latex=C%5BK%27-1%5D%3DdataMat%5Bi%5D&bg=ffffff&fg=2b2b2b&s=0&c=20201002)
。
ZHANG RONG 