ðX
t
3 ; y
t
3 Þ; . . .; ðX
t
n ; y
t
n Þg, X
t
n ’s corresponding distribution is P t ðX; yÞ, if P t ðX; yÞ 6 ¼
P tÀ1 ðX; yÞ then concept drift occurs.
Definition 2 Independent increment process: As the name suggests, it means that the
increments are independent of each other. Strictly defined as follows: set fXðjÞ; j ! 0g
be a random process. For 0 s j, the random variable XðjÞ À XðsÞ is increment of the
random process in the interval ½s; j, if any positive integer n ! 2 and any
0 j 0 \j 1 \j 2 \j 3 \ Á Á Á \j n , n increments are independent of each other, and
fXðjÞ; j ! 0g is autocephalous increment process.
Definition 3 Wiener process: given the process fWðjÞ; j ! 0g, if it satisfies a stationary
independent increment, Wð0Þ ¼ 0, and for any 0 s\j, fWðjÞ À WðsÞg
$ Nð0; r
2
ðj À sÞÞ.
Definition 4 Brown Bridge: a special Wiener process, is strictly defined as follows:
BðtÞ :¼ ðWðtÞjWðTÞ ¼ 0Þ; t 2 ½0; T.
Definition 5 Kolmogorov distribution is defined as
K ¼ sup
t2½0;1
jBðtÞj
ð1Þ
sup is the smallest upper bound of a set, by finding the distribution of random variables
that are bounded by the Brownian motion, its cumulative distribution function can be
written as:
PðK xÞ ¼ 1 À 2
P 1
k¼1
ðÀ1Þ
ðkÀ1Þ e
À2k
2 x
2 ¼
ffiffiffiffi
2p
p
x
P 1
k¼1
e
Àð2kÀ1Þ 2 p 2
8x 2
ð2Þ
2.2 Kolmogorov–Smirnov Test
In statistical test, K–S test is used to test whether an empirical distribution conforms to
a theoretical distribution or whether there is a significant difference between data
distributions. Because it is sensitive to parameters of the data distribution function
between both samples, K–S test is used to compare two samples. Kolmogorov–
Smirnov test finds the upper bound of the difference between the cumulative probability of experience and the cumulative probability of target distribution at each data
point, and lists the following formulas:
D n ¼ sup
x
fjF 0 ðxÞ À F n ðxÞjg
ð3Þ
sup is the supremum of distance, which is minimum upper bound of absolute value of
[F n x À F 0 ðxÞ] under the original assumption [F n ðxÞ ¼ F 0 ðxÞ] that the conditions are
true, and the cumulative distribution function of the observed values of random samples is represented by F n ðxÞ, and the cumulative probability distribution function of the
theoretical distribution is represented by F 0 ðxÞ.
Concept Drift Detection Based on Kolmogorov–Smirnov Test
275
t
3 ; y
t
3 Þ; . . .; ðX
t
n ; y
t
n Þg, X
t
n ’s corresponding distribution is P t ðX; yÞ, if P t ðX; yÞ 6 ¼
P tÀ1 ðX; yÞ then concept drift occurs.
Definition 2 Independent increment process: As the name suggests, it means that the
increments are independent of each other. Strictly defined as follows: set fXðjÞ; j ! 0g
be a random process. For 0 s j, the random variable XðjÞ À XðsÞ is increment of the
random process in the interval ½s; j, if any positive integer n ! 2 and any
0 j 0 \j 1 \j 2 \j 3 \ Á Á Á \j n , n increments are independent of each other, and
fXðjÞ; j ! 0g is autocephalous increment process.
Definition 3 Wiener process: given the process fWðjÞ; j ! 0g, if it satisfies a stationary
independent increment, Wð0Þ ¼ 0, and for any 0 s\j, fWðjÞ À WðsÞg
$ Nð0; r
2
ðj À sÞÞ.
Definition 4 Brown Bridge: a special Wiener process, is strictly defined as follows:
BðtÞ :¼ ðWðtÞjWðTÞ ¼ 0Þ; t 2 ½0; T.
Definition 5 Kolmogorov distribution is defined as
K ¼ sup
t2½0;1
jBðtÞj
ð1Þ
sup is the smallest upper bound of a set, by finding the distribution of random variables
that are bounded by the Brownian motion, its cumulative distribution function can be
written as:
PðK xÞ ¼ 1 À 2
P 1
k¼1
ðÀ1Þ
ðkÀ1Þ e
À2k
2 x
2 ¼
ffiffiffiffi
2p
p
x
P 1
k¼1
e
Àð2kÀ1Þ 2 p 2
8x 2
ð2Þ
2.2 Kolmogorov–Smirnov Test
In statistical test, K–S test is used to test whether an empirical distribution conforms to
a theoretical distribution or whether there is a significant difference between data
distributions. Because it is sensitive to parameters of the data distribution function
between both samples, K–S test is used to compare two samples. Kolmogorov–
Smirnov test finds the upper bound of the difference between the cumulative probability of experience and the cumulative probability of target distribution at each data
point, and lists the following formulas:
D n ¼ sup
x
fjF 0 ðxÞ À F n ðxÞjg
ð3Þ
sup is the supremum of distance, which is minimum upper bound of absolute value of
[F n x À F 0 ðxÞ] under the original assumption [F n ðxÞ ¼ F 0 ðxÞ] that the conditions are
true, and the cumulative distribution function of the observed values of random samples is represented by F n ðxÞ, and the cumulative probability distribution function of the
theoretical distribution is represented by F 0 ðxÞ.
Concept Drift Detection Based on Kolmogorov–Smirnov Test
275