Change-Point Detection in Homogeneous Segments of COVID-19 Daily Infection

Abstract

Modeling the number of individuals in different states is a principal tool in the event of an epidemic. The natural transition of individuals between possible states often includes deliberate interference such as isolation or vaccination. Thus, the mathematical model may need to be re-calibrated due to various factors. The model considered in this paper is the SIRD epidemic model. An additional parameter is the moment of changing the description of the phenomenon when the parameters of the model change and the change is not pre-specified. Detecting and estimating the moment of change in real time is the subject of statistical research. A sequential (online) approach was applied using the Bayesian shift point detection algorithm and trimmed exact linear time. We show how methods of analysis behave in different instances. These methods are verified on simulated data and applied to pandemic data of a selected European country. The simulation is performed with a social network graph to obtain a practical representation ability. The epidemiological data used come from the territory of Poland and concern the COVID-19 epidemic in Poland. The results show satisfactory detection of the moments where the applied model needs to be verified and re-calibrated. These show the effectiveness of the proposed combination of methods.

1. Introduction

In probabilistic models, we try to adjust the description in the simplest possible form. This method works well in the case of static phenomena that exhibit some stationarity, defined as a phenomenon whose source remains constant over time. In observations of such a phenomenon, randomness appears as a result of imperfect measurement methods or slight fluctuations in factors illustrating the state of the environment. We expect similar observations by dividing the phenomenon into areas (in time or space) with a homogeneous environment. Violation of homogeneity is a signal that the observed phenomenon has changed significantly. Thus, we would like to know how to detect these invisible changes by observing visible effects. It is an important research aspect that has its methodology. An adequate model of the phenomenon allows for a better short-term and long-term forecast. A correct model in the short term usually needs to be improved for long-term analysis, especially when the change in the phenomenon is sudden. We introduce the concept of change point to standardize such mathematical models.

From the perspective of time, the use of epidemic models (v. [1,2,3,4]) allows the forecasting of the number of daily cases (the intensity of epidemic development) in a short time (v. [5]). The detailed models may be different at a time when immunity in the population emerges only as a result of infection and the lack of a contact restriction policy. A change in the process is also possible due to new mutations (v. [6]). The introduction of contact restrictions and effective vaccination is another example where the appropriate model will be different. Applying a different model may deviate from information about the environment while the change or signal is present in the observed data. This signal may be the deteriorating compliance of the observations with the forecasts as measured by various criteria. The methods of change-point analysis, based on the data, allow the determination of rational criteria for determining the disorder moments.

In Figure 1, for example, with an approximate monthly segmentation, the sequence of infection changes is observed from January 2020 to February 2020, February 2020 to May 2020, May 2020 to August 2020, and August 2020 to early 2021 and then begins to decline. At all these points of trend changes, not predicted by the SIRC model, there are factors that are not properly accounted for in the basic model, and the model used should be changed. Those factors that are not taken into account may include actions taken that are noteworthy and documented for the investigation and control of an epidemic or the emergence of a mutation in the virus. The continuum of pandemic phases Figure 2 can be correlated with Figure 1. Figure 2 presents the four phases of a pandemic. The phases are the inter-pandemic, alert, pandemic and transition. The peak which started from the alert phase to the pandemic phase is caused by the great increase in the average daily cases. In line with the phases are the risk assessments which includes preparing for the subdue of worsening cases, responding and its result, recovery.

The term change point comes from studying detailed manufacturing processes in systems that routinely duplicate certain activities. We know that a correctly implemented production procedure results in high-quality products. The observed quality confirms the correctness of the process; an increase in defectiveness is a signal that the production process has been disordered. Thus, we have the intuition that the change point is a moment where the nature of the process changes. In a sequence of observations, such changes may be due to the abrupt deviation of the probability distribution at some point from what it initially follows. The method of change-point analysis originated in Page [7] by (v. [7,8]). The first approach was proposed to identify a single change point with a known model before and after the disorder. It is more difficult to detect a change point when the model after the change point is unknown (see [9]). The study has progressively been improved by presenting algorithms that can be used to detect several change points in data. These algorithms can be classified into two major groups, offline change point detection algorithms and online change point detection algorithms. The online change point detection algorithms are also known as sequential change-point detection algorithms, which use the cumulative sum method (CUSUM), generalized likelihood ratio, or Shiryayev–Roberts (SR) procedure (v. the monograph of the topic [10]).

To summarize, the subject of this research is to detect and estimate the moment of change in real time. We used the sequential (online) approach. The concept of sequential algorithms is desirable because our data are the daily numbers of infected people. Thus, there is a need to raise some alarms following an observed change. We used algorithms constructed based on Bayesian and purity methods. We demonstrated how to use the algorithms. We tested the algorithms on simulated data before the real-life data. The simulation was performed with a social network graph to obtain a practical representation ability. We used Poland’s COVID-19 data for our real-life test (We use the data on the daily number of COVID-19 infections in the period from January 2020 to early 2021 year in Poland (v. worldometers.info site (https://www.worldometers.info/coronavirus/country/poland/, accessed on 3 April 2021), Figure 1)). Additionally, we make remarks on the correlation of the change-point result with COVID-19 events in Poland.

The rest of the study is structured as follows: Section 2 presents the concept of change-point detection and its paradigms considered in this study. Section 3 presents the selected change-point algorithm that will be used for change-point detection. Section 4 presents the epidemic model for the study, and its parameter estimation. Section 5 presents the simulation procedure and describes the real data. Section 6 presents the results obtained from the application of the algorithms, which includes the simulation results and the real data result.

2. Concept of Change-Point Detection

The incidence of the subject change-point detection has led to the development of novel algorithms in several studies. This has further led to the application of some of these algorithms to data that are defined within their scope of composition. Detecting change points involves searching for the beginning of a new pattern within a given dataset. The method of change-point detection has been widely used for time series modeling [11,12,13] and has been applied to different areas, such as quality control [14], finance [15,16], climate monitoring [17,18], genetics [19,20] and so on. A very simple illustration of change-point detection is the case where we have a piece-wise function plotted as given in Figure 3. The function, $f\left(x\right)$ can be said to be composed of three different functions—linear function, $a\left(x\right)$; constant function, $b\left(x\right)$ and linear function, $c\left(x\right)$. These functions are defined at the change points A and B, respectively, i.e., $a\left(x\right)=$ Line OA, $b\left(x\right)=$ Line AB and $c\left(x\right)=$ Line BC.

Suppose that we have a sequence of random variables, $x_t$, with probability distribution function, $f_t$, $t=1,2,...,n$. The change point detection problem is to determine the point at which there are significant changes in the properties of the dataset. The location of these change points can be denoted by $\tau =({\tau }_0=0,{\tau }_1,{\tau }_2,...,{\tau }_t,{\tau }_{m+1}=n)$.

The hypothesis tested by the change-point detection problem is presented as follows:

$$\begin{array}{cc}{H}_0:& f_1=f_2=...=f_n\hfill \\ H_1:& f_1=f_{{\tau }_1}\ne f_{{\tau }_1+1}=...=f_{{\tau }_2}\ne f_{{\tau }_2+1}=...=f_{{\tau }_m}\ne f_{{\tau }_m+1}=...=f_n\hfill \end{array}$$

(1)

where

• $1={\tau }_0<{\tau }_1<{\tau }_2<...<{\tau }_m<{\tau }_t=n$;
• m is the unknown number of change points;
• ${\tau }_1,{\tau }_2,...,{\tau }_m$ are the change-point locations.

The objectives of the change-point problem can be seen in light of the following points:

• Quantity Objective: This involves the estimation of the possible number of change points, m, within the data.
• Location Objective: This involves the identification of the locations of the t change points in the data. This objective was further improved into quantifying the uncertainty in the locations within a confidence interval.
• Modeling Objective: This is the final objective of the method and it seeks to determine a befitting model for each of the $m+1$ segments, i.e., fitting observations lying within the splits that result from each change point.

In past literature, change-point problems have been solved using some basic and defined approaches of statistical and mathematical methods. These approaches include the likelihood ratio (LR) testing, the Cumulative Sum (CUSUM) methods, the Bayesian approach, the Hidden Markov Model (HMM) and the dynamic programming-based methods. The change-point algorithms used in this study are based on the Bayesian approach and the dynamic programming. Thus, the following subsections will discuss these paradigms, including the corresponding algorithm used.

2.1. Bayesian Method of Change-Point Detection

The idea of the Bayesian approach can be easily understood from the concept of Bayesian statistics (cf. Press [21], DeGroot [22]). Bayesian statistics is a theory that is based on the Bayesian interpretation of probability, which expresses the degree of belief in an occurrence based on prior knowledge. The prior knowledge of such an occurrence can greatly influence the degree of belief. The theory is in contrast to the frequentist approach that considers probability to be the relative frequency of the occurrence after a large number of trials. Bayesian statistics generally employs the Bayes theorem (cf. Martz and Waller [23]). The Bayes theorem expresses the conditional probability of an event, A, given that event B is true as (2). A is more similar to a proposition, while B is the evidence. $P\left(A\right|B)$ is the conditional probability after incorporating news that event B is true.

$$P\left(A\right|B)=\frac{P\left(B\right|A\left)P\right(A)}{P\left(B\right)}$$

(2)

In change-point detection, the Bayesian approach involves placing a prior on the number of change points, m, and their corresponding location. Although this method of specifying priors may appear logical, the priors for the quantity and locations of change points can be jointly defined indirectly by specifying a prior on the length of a segment, and this technique offers computational advantages over specifying two distinct priors [24]. Suppose that we have a series, X, with k segments, and ${\theta }_k$ represents the parameter vector for the $k^{th}$ segment of the series; then, the posterior probability of the set of m change points at locations $\tau$ is presented in Equation (3).

$$\begin{array}{c}P(m,\tau ,{\theta }_1,{\theta }_2,...,{\theta }_{m+1}|X,\lambda ,{\nu }_1,{\nu }_2,...,{\nu }_{k+1})\hfill \\ P\left(m\right|\lambda )P\left(\tau \right|m)P({\theta }_1,{\theta }_2,...,{\theta }_{m+1}|{\nu }_1,{\nu }_2,...,{\nu }_{m+1})P\left(X\right|m,\tau ,{\theta }_1,{\theta }_2,...,{\theta }_{m+1})=\hfill \\ P\left(m\right|\lambda )\left\{\prod _{k=1}^{m}P\left({\tau }_k\right)\right\}P({\theta }_1,{\theta }_2,...,{\theta }_{m+1}|{\nu }_1,{\nu }_2,...,{\nu }_{m+1})\left\{\prod _{k=1}^{m+1}\prod _{t={\tau }_{k-1}+1}^{{\tau }_k}P\left(X_t\right|{\theta }_k)\right\}\hfill \end{array}$$

(3)

where

• $k=1,...,m+1$
• $\tau =({\tau }_0=0,{\tau }_1,{\tau }_2,...,{\tau }_m,{\tau }_{m+1}=n)$
• $P({\theta }_1,{\theta }_2,...,{\theta }_{m+1}|{\nu }_1,{\nu }_2,...,{\nu }_{m+1})$ is the joint prior of the parameter vectors
• $P\left(X\right|m,\tau ,{\theta }_1,{\theta }_2,...,{\theta }_{m+1})$ is the likelihood of the given time series and given by Equation (4)

  $$P\left(X\right|m,\tau ,{\theta }_1,{\theta }_2,...,{\theta }_{m+1})=\prod _{k=1}^{m+1}\prod _{t={\tau }_{k-1}+1}^{{\tau }_k}P\left(X_t\right|{\theta }_k)$$

  (4)

A typical change-point model which employs this approach is the online change point detection [25], which is one of the main algorithms used in this study. In addition to change-point models, Bayesian approaches based on Markov Chain Monte Carlo (MCMC) have been applied [26,27,28]. When the number of changes is unknown, reversible jump MCMC [29] becomes a useful and typical strategy. It explores the joint space of the model and parameters for a collection of models with varying numbers of change points. The Bayesian approach, as one of the paradigms of change-point detection, with the introduction of Markov chains, led to another paradigm known as the Hidden Markov Models (HMMs) [30]. HMM is comparable in certain aspects to the Bayesian approach. For instance, let the series X be assumed to have a first-order Markov property and hidden segment labels $\Xi ={\Xi }_1,{\Xi }_2,...,{\Xi }_n$; the likelihood of X modeled as a HMM is formulated as:

$$\sum _{\Xi }P(X,\Xi )=\sum _{\Xi }\prod _{i=1}^{n}P(X_i,{\Xi }_i|{\Xi }_{i-1},X_1)$$

(5)

In the HMM, work has also been done on calculating the number of hidden states. Further discussion on the online Bayesian change-point detection is presented in Section 3.1.

2.2. Dynamic Programming Method

The dynamic programming method (DPM) was introduced using the concept of log-likelihood. A penalized cost technique can be used to extend the log-likelihood approach to change-point detection to the multiple change-point case. The dynamic programming approach is then used on the penalized cost function to detect changes. Dynamic programming is formulated through an optimization problem such that the likelihood of the series, $X_i$$i=1,2,...,n$, is used as the cost function, which is minimized. To improve the optimization, a penalized approach can be used. Suppose that we have a change point at $\tau$; then, the optimization approach is presented in Equation (6)

$$\underset{1\le \tau <n}{min}\{C\left(x_{1:\tau }\right)+C\left(x_{\tau +1:n}\right)+\varrho \}$$

(6)

$$C\left(x_{1:\tau }\right)+C\left(x_{\tau +1:n}\right)+\varrho <C\left(x_{1:n}\right)$$

(7)

It is important to note that Equation (6) follows from Equation (7). The penalty, $\varrho$, is re-defined from the threshold of the likelihood approach [10]. This can be generalized for multiple change-point detection (say m change points) as in Equation (8).

$$\underset{m,{\tau }_{1:m}}{min}\{\sum _{i=1}^{m+1}\left[C\left(x_{{\tau }_{i-1}+1:{\tau }_i}\right)\right]+\varrho \}$$

(8)

Equation (8) is unconstrained; it can, however, be solved in a constrained manner as Equation (9) subjected to Equation (10)

$$Z=\underset{{\tau }_{1:m}}{min}\left\{\sum _{i=1}^{m+1}\left[C\left(x_{{\tau }_{i-1}+1:{\tau }_i}\right)\right]\right\}$$

(9)

subject to

$$\underset{mϵ1:M}{min}\{Z+f\left(m\right)\}$$

(10)

where $f\left(m\right)$ is a chosen penalty term that increases as m increases and can also be a linear function in a form that is similar in a certain respect to the penalized unconstrained minimization approach. Although it might be difficult to know, nevertheless, M is present as the maximum change points in the series.

In Auger and Lawrence [31], the Segment Neighborhood (SN) search method was introduced, directed towards solving the constrained problem (9). The method uses a recursive procedure (13) which links $Z_m\left(x_{1:t}\right)$ to $Z_{m-1}\left(x_{1:s}\right)$ for $s<t$ to find the optimal segmentation in a series by specifying a maximum number of changes, M.

$$\begin{array}{ccc}\hfill Z_m\left(x_{1:t}\right)& =& \underset{\tau }{min}\left\{\sum _{i=0}^{m}C\left(x_{({\tau }_i+1):{\tau }_{i+1}}\right)\right\}\hfill \end{array}$$

(11)

$$\begin{array}{ccc}& =& \underset{{\tau }_m}{min}\{\underset{{\tau }_{1:(m-1)}}{min}\sum _{i=0}^{m-1}C\left(x_{({\tau }_i+1):{\tau }_{i+1}}\right)+C\left(x_{({\tau }_m+1):{\tau }_{m+1}}\right)\}\hfill \end{array}$$

(12)

$$\begin{array}{ccc}& =& \underset{{\tau }_{m-1}}{min}\{Z_m\left(x_{1:s}\right)+C\left(x_{({\tau }_m+1):{\tau }_{m+1}}\right)\}\hfill \end{array}$$

(13)

Similarly, Jackson et al. [32] presented a solution to the penalized optimization problem in (8) by proposing the optimal partitioning (OP) method. The OP method recursively solves Equation (15).

$$\begin{array}{ccc}\hfill Z\left(t\right)& =& \underset{\tau ϵ{\tau }^{*}}{min}\{\sum _{i=1}^{m+1}\left[C\left(x_{{\tau }_{i-1}+1:{\tau }_i}\right)\right]+\varrho \}\hfill \end{array}$$

(14)

$$\begin{array}{ccc}& =& \underset{sϵ0,...,t-1}{min}\{Z\left(s\right)+C(x_{(s+1)}:t)+\varrho \}\hfill \end{array}$$

(15)

where ${\tau }^{*}$ is the set of all possible change-point numbers and positions for data segmentation up to time t. The computation cost of the OP method is $O\left(n^2\right)$, and the method is much faster than the SN method, having a computational cost of $O\left(M{n}^2\right)$. The advantage of the SN is that it can find multiple change points within a range with 1:M changes. Additionally, recent algorithms that use pruning approaches to decrease computations have been developed to address the computational cost of executing dynamic programming algorithms. There are two types of these pruning techniques as used in studies: the inequality-based pruning used for the Pruned Exact Linear Time (PELT) [33] algorithm and the functional pruning used in the Function Pruning Optimal Partitioning (FPOP) algorithm [34]. The aim of pruning is to remove the points that can never be change points during the recursion procedure. The dynamic procedure will be discussed in light of the PELT algorithm later in the study.

3. Change-Point Algorithm

The two main change-point algorithms used in this study are discussed in this section.

3.1. Bayesian Online Change-Point Detection

The study reverts to the Bayesian Online Change-Point Detection (BOCPD) approach presented by Adams and MacKay [25]. The detection algorithm of the BOCPD (Algorithm 1) assumes that the sequence of observation consists of segments resulting from some partition. Thus, the algorithm identifies a change point when the underlying generative model of the observation changes and a new segment surfaces. The approach basically makes use of run length, $r_t$. Suppose that $r_t$ is a non-negative discrete variable which represents the length of time until the next change point. This implies that $r_t=0$ at every change point. The BOCPD algorithm is based on estimating the posterior probability of the current run length, $P\left(r_t\right|x_{1:t})$, and integrates the underlying predictive model, $P\left(x_{t+1}\right|r_t,x_t^{\left(r\right)})$, over it. The resulting joint distribution over the observed data and the run length from the posterior probability of the current run length follows the below recursion:

$$\begin{array}{ccc}\hfill P(r_t,x_{1:t})& =& \sum _{r_{t-1}}P(r_t,r_{t-1},x_{1:t})\hfill \end{array}$$

(16)

$$\begin{array}{ccc}& =& \sum _{r_{t-1}}P\left(x_t\right|r_{t-1},x_r^{\left(r\right)})P\left(r_t\right|r_{t-1})P(r_{t-1},x_{1:t-1})\hfill \end{array}$$

(17)

Now, it becomes possible to compute the joint distribution by computing the predictive distribution over the newly observed data, $P\left(x_t\right|r_{t-1},x_r^{\left(r\right)})$, and the prior over $r_t$ given $r_{t-1}$. $P\left(x_t\right|r_{t-1},x_r^{\left(r\right)})$ can be calculated since the new observation only depends on the recent data $x_t^{\left(r\right)}$. However, the prior over $r_t$ given $r_{t-1}$, i.e., $P\left(r_t\right|r_{t-1})$, is computed through a hazard function $H\left(r_{t-1}\right)\in [0,1]$ that allows two possible outcomes for $r_t$.

$$P\left(r_t\right|r_{t-1})=\left\{\begin{array}{cc}H(r_{t-1}+1)\hfill & \mathrm{if}{r}_t=0\hfill \\ 1-H(r_{t-1}+1)\hfill & \mathrm{if}{r}_t=r_{t-1}+1\hfill \\ 0\hfill & \mathrm{otherwise}\hfill \end{array}\right.$$

(18)

This implies that the hazard function implicitly induces a distribution over the period of the segments included in an observation sequence. In the long run, the joint probability will not only help to detect change points but also help to predict future observations. In essence, the marginal predictive distribution is obtained as:

$$P\left(x_{t+1}\right|x_{1:t})=\sum _{r_t}P\left(x_{t+1}\right|x_t^{\left(r\right)},r_t)P\left(r_t\right|x_{1:t})$$

(19)

Algorithm 1: BOCPD Algorithm.
Input: $H(.)$ (Hazard function) and ${\Theta }_{prior}$ (Prior hyper-parameters for the observation model)
1: for each new datum, $x_t$ do
2:     for $r_t\leftarrow 0$ to n do	▹ Estimate using sufficient statistics
3:         ${\pi }_t^{\left(r\right)}=P\left(x_t\right|{\nu }_t^{\left(r\right)},{\kappa }_t^{\left(r\right))}$
4:     end for
5:     for $r_t\leftarrow 1$ to n do	▹ Compute the growth probabilities
6:         $P(r_t=r_{t-1}+1,x_{1:t})={\sum }_{r_{t-1}}(1-H\left(r_{t-1}\right))P(r_{t-1},x_{1:t-1}){\pi }_t^{\left(r\right)}$
7:     end for
8:     for $r_t\leftarrow 0$ to n do	▹ Compute the change-point probabilities
9:         $P(r_t=0,x_{1:t})=P(r_{t-1},x_{1:t-1}){\pi }_t^{\left(r\right)}H\left(r_{t-1}\right)$
10:     end for
11:     $P\left(r_t\right|x_{1:t})=P(r_t,x_{1:t})/P\left(x_{1:t}\right)$	▹ Compute the run length distribution
12:     ${\Theta }_t^0={\Theta }_{prior}$	▹ Update sufficient statistics
13:     for $r_t\leftarrow 1$ to R do
14:         Update ${\Theta }_t^{r_t}$ from ${\Theta }_{t-1}^{r_{t-1}}$ and $x_{t+1}$
15:     end for
16:     $P\left(x_{t+1}\right|x_{1:t})={\sum }_{r_t}P\left(x_{t+1}\right|x_t^{\left(r\right)},r_t)P\left(r_t\right|x_{1:t})$	▹ Output prediction
17: end for

3.2. Pruned Exact Linear Time Algorithm

The Pruned Exact Linear Time (PELT) Algorithm [33] was proposed with the intent of searching how the computational efficiency of the optimal partition (OP) method [32] can be improved through pruning. The pruning is done while ensuring that the global minimum of the cost function is still found. Whilst some methods use the likelihood functions as their cost function, the arguably most used cost function minimization approach for estimating change points is:

$$\underset{\tau ϵ{\tau }_{*}}{min}\{\sum _{i=1}^{m+1}\left[C\left(x_{{\tau }_{i-1}+1:{\tau }_i}\right)\right]+\varrho f\left(m\right)\}$$

(20)

where:

• $C(.)$ is a cost function for a segment;
• $\varrho f\left(m\right)$ is a penalty to guard against overfitting.

The OP method was obtained from the equation. For the modification of the OP method to include pruning, the PELT algorithm (Algorithm 2) was proposed through the following theorem:

Theorem 1.

When introducing a change point into a sequence of observations, the cost, C, of the sequence reduces. Mathematically, assume that there is a constant K such that $\forall s<t<T$,

$$C\left(x_{(s+1):t}\right)+C\left(x(t+1):T\right)+K\le C\left(x_{(s+1):T}\right)$$

(21)

Then, if

$$F\left(s\right)+C\left(x_{(s+1):t}\right)+K\ge F\left(t\right)$$

(22)

holds, at a future time $T>t$, s can never be the optimal last change point prior to T.

It is important to note that ϱ has no relationship with the change points, $cp\left(0\right)$ is null at the start and K also relies on Theorem 1.

Algorithm 2: PELT Algorithm.

Input: (a) Set of data, $y_iϵ\mathbb{R}$, $i=1,...,n$, (b) a measure of $C(.)$ dependent on $y_i$, (c) a penalty constant, $\beta$, independent of the change points and (d) a constant K satisfying theorem 1

Output: Change points in $cp\left(n\right)$

1: Initialize: $F\left(0\right)=-\beta ,cp\left(0\right),R_1=0$

2: for ${\tau }^{*}\leftarrow 1$ to n do

3:     Calculate $F\left({\tau }^{*}\right)=mi{n}_{\tau ϵR_{{\tau }^{*}}}[F\left(\tau \right)+C\left(y_{(\tau +1)+{\tau }^{*}}\right)+\beta ]$

4:     Let ${\tau }^1=argF\left({\tau }^{*}\right)$

5:     Set $cp\left({\tau }^{*}\right)=[cp\left({\tau }^1\right),{\tau }^1]$

6:     And $R_{{\tau }^{*}+1}=\tau ϵR_{{\tau }^{*}}\cup {\tau }^{*}:F\left(\tau \right)+C\left(y_{(\tau +1)+{\tau }^{*}}\right)+K\le F\left({\tau }^{*}\right)$

7: end for

The cost function we used for the PELT algorithm is discussed in Section 3.3.

3.3. Cost Function and Penalties

The cost function, also known as the loss function or error function, is a function that maps an event or the values of one or more variables into a real number that intuitively represents any “cost” associated with the event in mathematical optimization. In most cases, they are functions that are desired to be minimized. They are a measure of homogeneity and can be classified into either parametric [35] or non-parametric [36]. The concept of cost functions in change-point detection is such that its value is low in segments with no change points and high in segments with change points. Although there are many ways to define costs, they are mostly equal to a loss based on an acceptable likelihood model.

With respect to the PELT algorithm, the method uses a penalized cost function based on the introduction of $\varrho f\left(m\right)$. Suppose that a datum is modeled from a normal distribution independently and identical with mean $\mu$ and variance ${\sigma }^2$; the log-likelihood of the data $x_{(s+1):t}$ is

$$l(x_{(s+1):t};\mu ,\sigma )=-\frac{t-s}{2}log\left({\sigma }^2\right)-\frac{1}{2{\sigma }^2}\sum _{j=s+1}^t{(y_j-\mu )}^2$$

(23)

The log-likelihood function (23) is used to formulate the cost associated with a segment with respect to the known or unknown case of the mean and the variance.

• The cost function of a segment specific mean, $\mu$, assuming that the variance, ${\sigma }^2$, is known and common to all observations, is given by (24).

  $$C_1\left(x_{(s+1):t}\right)=(t-s)log\left({\sigma }^2\right)+\frac{1}{{\sigma }^2}\sum _{j=s+1}^t{(y_j-\frac{1}{t-s}\sum _{i=s+1}^t{y}_i)}^2$$

  (24)
  The cost function associated with the segment is obtained by performing a minus twice the log-likelihood (23).
• Similarly, the cost function of a segment specific variance ${\sigma }^2$, assuming that the mean $\mu$ is known and constant for the observation, is given by

  $$C_2\left(x_{(s+1):t}\right)=(t-s)\{log\left(\frac{1}{t-s}\sum _{j=s+1}^t{(y_j-\mu )}^2\right)+1\}$$

  (25)
• The cost function of a segment specific mean $\mu$ and variance ${\sigma }^2$ is obtained by using minus twice the log-likelihood (23) after maximizing over both $\mu$ and $\sigma$. The resulting function is given by (26)

  $$C_3\left(x_{(s+1):t}\right)=(t-s)\{log\left(\frac{1}{t-s}\sum _{j=s+1}^t{(y_j-\frac{1}{t-s}\sum _{i=s+1}^t{y}_i)}^2\right)+1\}$$

  (26)

As discussed earlier for the penalized nature of the cost function used in the PELT algorithm, it important to note that the performance of the penalized optimization approach depends on the penalty value, $\beta$. Simply put, the choice of the penalty value has a significant effect on the detected changes. Suppose that introducing a change point leads to certain number parameters, denoted by p; most of the literature has considered a penalty based on different criteria for model selection. One of the most used is the Akaike Information Criterion (AIC) [37]. This is an estimator of prediction error; thus, it measures the goodness of fit of an estimated statistical model.

$$AIC=2p-2ln\left(\widehat{L}\right)$$

(27)

$$BIC=pln\left(n\right)-2ln\left(\widehat{L}\right)$$

(28)

In addition to p defined as the estimated parameters in the model, let $\widehat{L}$ denote the maximum value of the likelihood function for the model, and the AIC is given in Equation (27). The Bayesian Information Criterion (BIC) [38], also known as the Schwarz Information Criterion (SIC), is another closely used approach to the AIC. The BIC presented in Equation (28) and the AIC both attempt to resolve the problem of overfitting (that is, the problem of increased likelihood while fitting a model due to additional parameters). However, the penalty term is larger in BIC than in AIC. There is a modification of the BIC, MBIC, proposed by Zhang and Siegmund [39]. The MBIC accounts for the length of the segments; although it works well for simulated data, the study by Hocking et al. [40] has shown it to be limited with real-life datasets. The elbow plot approach, which is an adaptive penalty choice, was proposed by Lavielle and Moulines [41]. The method involves sequentially running the optimization problem for different numbers of change points and plotting it against the unpenalized cost; the traditional elbow plot approach is used to select the best segmentation point. This method is similar to that used by Hocking et al. [40], which reported the best segmentation with various numbers of change points, and then used the annotated training data to figure out the best penalty.

4. Secretion of Homogeneous Segments in the Number of Daily Infections

Modeling of infectious diseases is a subject having no depreciating interest in research across its concerned fields, such as mathematics, public health, epidemiology, etc. This results from the ubiquitous prevalence of various diseases occurring among the human race. A prominent example is the current pandemic at the time of writing—the COVID-19 virus. We will discuss the various models for infectious diseases with a focus on the infection rate in this section. We will also discuss two change-point detection algorithms that we will be using with the models.

4.1. Epidemic Model

Epidemic models are a well-known tool for simulating the mechanism by which infectious diseases spread. Several studies have used these models to predict future disease outbreaks, propose methods or strategies to prevent disease outbreaks and assess the efficacy of these methods. The epidemic model can exist in two types, which are stochastic and deterministic. The stochastic model is a model type which allows for random variance in one or more inputs over time to estimate the probability distributions of possible outcomes. On the other hand, the deterministic models involve assigning the population to different groups or sub-groups or compartments. Each compartment represents a specific phase of the epidemic. In addition, the stochastic models are based on chance variations in exposure risk, disease dynamics and other illness dynamics. The transition rates in the deterministic models are expressed mathematically as derivatives. Three common common epidemic models are presented below:

(i)

The SIS Model—the model has two compartments—the susceptible and the infectious. The model flow is presented below:

$$Susceptible\left(S\right)⟶Infectious\left(I\right)⟶Susceptible\left(S\right)$$

The model compartments result from infections that do not confer any long-lasting immunity—infections such as influenza and the common cold. The differential form of the model is presented as follows:

$$\begin{array}{c}\hfill S^{\prime }\left(t\right)=\frac{-\beta \left(t\right)S\left(t\right)I\left(t\right)}{N}+\gamma I\left(t\right)\\ \hfill I^{\prime }\left(t\right)=\frac{\beta \left(t\right)S\left(t\right)I\left(t\right)}{N}-\gamma I\left(t\right)\end{array}$$

where

• $S\left(t_1\right)=S_1>0,I\left(t_1\right)=I_1>0$
• $\beta$ is the average number of contacts per person per time, t.
• $\gamma$ is the rate at which people in the infectious compartment become susceptible again.
• N is assumed to be fixed in this case; thus, $N\equiv N\left(t\right)=S\left(t\right)+I\left(t\right)$

(ii)

The SIR Model—the model has three compartments—the susceptible, the infectious and the removed. The model flow is presented below:

$$Susceptible\left(S\right)⟶Infectious\left(I\right)⟶Removed\left(R\right)$$

The “removed” compartment of the model accounts for any individual that recovers or dies from the disease. The differential form of the model is presented as follows:

$$\begin{array}{cc}\hfill S^{\prime }\left(t\right)& =\frac{-\beta \left(t\right)S\left(t\right)I\left(t\right)}{N}\hfill \\ \hfill I^{\prime }\left(t\right)& =\frac{\beta \left(t\right)S\left(t\right)I\left(t\right)}{N}-\gamma I\left(t\right)\hfill \\ \hfill R^{\prime }\left(t\right)& =\gamma I\left(t\right)\hfill \end{array}$$

where

• $S\left(t_1\right)=S_1>0,I\left(t_1\right)=I_1>0,R\left(t_1\right)$
• $\beta$ is the average number of contacts per person per time, t.
• $\gamma$ is the rate at which people in the infectious compartment are removed.
• N is assumed to be fixed in this case; thus, $N\equiv N\left(t\right)=S\left(t\right)+I\left(t\right)+R\left(t\right)$.

(iii)

The SIRD Model—the model is a modification of the SIR model, in which the recovered and the removed (which implies the dead) are separated. Thus, it has four compartments, and the model flow is presented presented below:

$$Susceptible\left(S\right)⟶Infectious\left(I\right)⟶Recovered\left(R\right)⟶Death or Removed\left(D\right)$$

The differential form of the model is presented as follows:

$$\begin{array}{c}\hfill S^{\prime }\left(t\right)=\frac{-\beta \left(t\right)S\left(t\right)I\left(t\right)}{N}\\ \hfill I^{\prime }\left(t\right)=\frac{\beta \left(t\right)S\left(t\right)I\left(t\right)}{N}-\gamma I\left(t\right)\psi I\left(t\right)\\ \hfill R^{\prime }\left(t\right)=\gamma I\left(t\right)\\ \hfill D^{\prime }\left(t\right)=\psi I\left(t\right)\end{array}$$

where

• $S\left(t_1\right)=S_1>0,I\left(t_1\right)=I_1>0,R\left(t_1\right)\ge 0$
• $\beta$ is the average number of contacts per person per time, t.
• $\gamma$ is the rate at which people in the infectious compartment recover.
• $\psi$ is the rate at which people in the infectious compartment are removed (that is, die).
• N is assumed to be fixed in this case; thus, $N\equiv N\left(t\right)=S\left(t\right)+I\left(t\right)+R\left(t\right)+D\left(t\right)$.

4.2. Parameter Estimation

An important parameter that draws the attention of researchers more in the epidemic model lies within the infection compartment from the susceptible compartments. The first basic parameter is the infection rate itself, which is more convenient to be estimated with a time constant population assumption using the method adopted in the study by Wacker and Schluter Wacker and Schlüter [42]. For the purpose of this study, we focus more on the SIRD model. The time discrete formulation of the SIRD model was derived using the finite difference approach such that the approximation

$$f^{\prime }(t_i+1)\approx \frac{f_{i+1}-f_i}{\Delta t}=f_{i+1}-f_i$$

(29)

holds for all $i\in 1,\dots ,n$ since $\Delta t=1$. The implication of this is the following equations:

$$S_{i+1}-S_i=\frac{-{\beta }_{i+1}{S}_{i+1}{I}_{i+1}}{N}$$

(30)

$$I_{i+1}-I_i=\frac{{\beta }_{i+1}{S}_{i+1}{I}_{i+1}}{N}-{\gamma }_{i+1}{I}_{i+1}-{\psi }_{i+1}{I}_{i+1}$$

(31)

$$R_{i+1}-R_i={\gamma }_{i+1}{I}_{i+1}$$

(32)

$$D_{i+1}-D_i={\psi }_{i+1}{I}_{i+1}$$

(33)

The time varying coefficients sequence is obtained as with the following conditions:

• if $I_{i+1}\ne 0$, set ${\gamma }_{i+1}=\frac{R_{i+1}-R_i}{I_{i+1}}$ and ${\tau }_{i+1}=\frac{D_{i+1}-D_i}{I_{i+1}}$

  –

  if $S_{i+1}\ne 0$, set ${\beta }_{i+1}=\frac{N(S_i-S_{i+1})}{S_{i+1}{I}_{i+1}}$

  –

  if $S_{i+1}=0$, set ${\beta }_{i+1}=0$

• if $I_{i+1}=0$, set ${\beta }_{i+1}=0,{\gamma }_{i+1}=0 \mathrm{and} {\tau }_{i+1}=0$

The coefficients, $\gamma$ and $\tau$, are usually assumed to be constant in time; thus, they can be represented with their mean ($\overline{\gamma }$ and $\overline{\tau }$) or median ($\widehat{\gamma }$ and $\widehat{\tau }$). That is,

$$\overline{\zeta }=\sum _{i=2}^n{\zeta }_i$$

(34)

$$\widehat{\zeta }=\left\{\begin{array}{cc}\zeta \left[\frac{n}{2}\right]\hfill & \mathrm{if}\mathrm{n}\mathrm{is}\mathrm{odd}\hfill \\ \frac{\zeta \left[\frac{n-1}{2}\right]+\zeta \left[\frac{n+1}{2}\right]}{2}\hfill & \mathrm{if}\mathrm{n}\mathrm{is}\mathrm{even}\hfill \end{array}\right.$$

(35)

where $\zeta \in \{\gamma ,\beta \}$.

Another parameter of interest is the time count of the number of people with the disease, i.e., the infectious compartment. This can be modeled using several approaches, such as the ARIMA time series approach.

5. Simulation Procedure and Real Data Description

The real data for the study will be such that it follows an SIRD epidemic model. Thus, we perform the simulation for the SIRD epidemic model proposed in Section 4. This is because the source of the real-life data contains only the details relating to the infectious, recovered and removed (death) compartment. Using a fixed population figure is a particular limitation of our study. We adopt a network-based simulation to model an epidemic that allows for phase-type transmissibility in a SIRD model; see Figure 4. The network approach allows the real-life explanation of connectivity, which, in this case, allows the contact rate effect, i.e., the average number of contacts per person per time. The network also allows the simulation to be done randomly.

The network algorithm is constructed in a manner such that:

• The average number of contacts per person per time, $\beta$, is random and phase-based.
• The beta is chosen such that $\beta \sim Exp\left(\lambda \right)$ and $\lambda$ varies within time intervals. Six different $\lambda$s were chosen for $\lambda$; this implies six phases and five known change points in the transmission rate of the decease.
• Other parameters of the model ($\gamma$ and $\tau$) are fixed based on the assumption in Section 4.2. The choice of these parameters for the simulation is $\gamma =0.3$ and $\tau =0.15$
• The network starts with the whole population as susceptible with a single infection (N = 1000).
• The disease is only transferable within neighbors of the node with the probability ${\beta }_t$ at time t.

According to the simulation assumptions, the epidemic model was simulated on a random graph (Figure 5)—$G(N=1000,p=0.02)$, where N is the number of nodes (that is, N is the population) and p is the probability of an edge connecting to another (that is, it shows the connectivity in society). Algorithm 3 describes how the SIRD simulation was carried out.

Algorithm 3: Network algorithm for the SIRD model.
1: $S_1=N-I_1,I_1=1,R_1=0,D_1=0$	▹ Initialize nodes in the compartments
2: $i=0$
3: while $i<T$ do
4:     for node in $I_{t-1}$ do
5:        Infect neighbor nodes at rate ${\beta }_t$ to obtain $I_t$
6:     for in $I_{t-1}$ do
7:        Simultaneously,
8:         Recover nodes at rate $\gamma$ to obtain $R_t$
9:         Remove (death) nodes at rate $\gamma$ to obtain $D_t$
10:     Check $I_t\cap R_t\cap D_t=0$
11:     for node in graph do
12:        if node not in $D_t$:
13:           if node not in $R_t$:
14:             if node not in $I_t$:
15:                put node in $S_t$
16: next i

We used the daily COVID-19 data for Poland from 15th February 2020 to 2nd April 2021. We extracted the data from worldometers.info site (https://www.worldometers.info/coronavirus/country/poland/ (accessed on 3 April 2021)), including a fixed population of Poland since the time discrete approach considered in the estimation of the transmission rate uses a fixed population size. The compartmental plot of Poland’s COVID-19 data is presented in Figure 6. We ignored the susceptible compartment in Figure 6 to improve the visibility of other compartments. The model simulation and parameter estimation were done on Python, while the change-point detection algorithm was implemented using the packages [43] presented by their authors in R. Five different penalties were considered for the PELT algorithm: AIC, BIC/SIC, MBIC, Manual and None. None means no penalty was introduced in the optimization procedure of the algorithm. We use the elbow method for the manual penalty, with the penalty value obtained at $3.5$ for both simulated and real data. The result of the simulation and application are discussed in the next section. The change points detected are presented in Appendix A (see

Table A1. PELT Algorithm Result for Simulated Transmissibility Rate.

n	Penalty	PELT(Mean)		PELT(Variance)		PELT(Mean, Variance)
		m	τ	m	τ	m	τ
20	None	19	1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,12, 13, 14,15, 16, 17, 18, 19	8	2, 5, 7, 9, 11, 14, 16, 18	8	2, 5, 7, 9, 11, 13, 15, 18
	SIC, BIC	1	20	1	18	5	2, 5, 7, 9, 18
	MBIC	1	20	1	18	2	2, 18
	AIC	1	20	1	18	6	2, 5, 7, 11, 14, 18
	Manual	1	20	1	18	8	2, 5, 7, 9, 11, 13, 15, 18
30	None	29	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	12	2, 5, 7, 9, 11, 14, 16, 18, 20, 23, 25, 27	13	2, 5, 7, 9, 11, 13, 15, 18, 20, 22, 24, 26, 28
	SIC, BIC	1	30	2	18, 20	4	2, 5, 18, 20
	MBIC	1	30	2	18, 20	3	2, 18, 20
	AIC	1	30	2	18, 20	7	2, 5, 7, 11, 14, 18, 20
	Manual	1	30	2	18, 20	10	2, 5, 7, 9, 11, 13, 15, 18, 21, 24

* means each time point was detected as a change point; *** means change points detected are more than 40.

,

Table A2. PELT Algorithm Result for Simulated Transmissibility Rate.

n	Penalty	PELT(Mean)		PELT(Variance)		PELT(Mean, Variance)
		m	τ	m	τ	m	τ
50	None	49	***	22	2, 5, 7, 9, 11, 14, 16, 18, 20, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 44, 46, 48	22	2, 5, 7, 9, 11, 13, 15, 18, 20, 22, 24, 26, 28, 30, 32, 35, 37, 39, 41, 43, 45, 47
	SIC, BIC	1	50	2	18, 20	3	2, 18, 20
	MBIC	1	50	2	18, 20	3	2, 18, 20
	AIC	1	50	2	18, 20	10	2, 5, 7, 11, 14, 18, 20, 32, 35, 37
	Manual	1	50	2	18, 20	17	2, 5, 7, 9, 11, 13, 15, 18, 21, 24, 32, 35, 37, 39, 41, 45, 47
100	None	99	***	43	***	44	***
	SIC, BIC	1	100	1	71	4	2, 18, 20, 57
	MBIC	1	100	1	71	3	18, 20, 57
	AIC	1	100	6	19, 21, 24, 58, 74, 77	20	2, 5, 7, 11, 14, 18, 20, 32, 35, 37, 39, 52, 54, 56, 72, 75, 77, 79, 93, 95
	Manual	1	100	8	19, 21, 24, 58, 74, 77, 79, 84	36	2, 5, 7, 9, 11, 13, 15, 18, 21, 24, 32, 35, 37, 39, 41, 45, 47, 51, 54, 56, 59, 62, 66, 68, 70, 72, 75, 77, 79, 81, 84, 88, 91, 93, 95, 98
201	None	200	***	86	***	88	***
	SIC, BIC	1	201	4	18, 20, 56, 99	6	2, 18, 20, 57, 99, 111
	BIC	1	201	4	18, 20, 56, 99	6	2, 18, 20, 57, 99, 111
	MBIC	1	201	4	18, 20, 56, 99	4	18, 20, 57, 99
	AIC	1	201	11	18, 20, 56, 72, 75, 77, 80, 84, 93, 95, 99	51	***
	Manual	1	201	13	18, 20, 56, 72, 75, 77, 80, 84, 93, 95, 99, 111, 114	70	***

* means each time point was detected as a change point; *** means change points detected are more than 40.

,

Table A3. PELT Algorithm Result for Simulated Infection.

n	Penalty	PELT(Mean)		PELT(Variance)		PELT(Mean, Variance)
		m	τ	m	τ	m	τ
20	None	19	*	8	2, 4, 6, 8, 10, 13, 15, 17	8	2, 4, 6, 9, 11, 13, 16, 18
	SIC, BIC	17	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19	1	20	2	2, 9
	MBIC	17	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19	1	20	1	2
	AIC	17	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,19	4	4, 10, 13, 17	5	2, 4, 10, 13, 17
	Manual	17	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19	4	4, 10, 13, 17	6	2, 4, 10, 13, 16, 18
30	None	29	*	13	2, 4, 6, 9, 11, 13, 16, 18, 20, 22, 24, 26, 28	13	2, 4, 6, 9, 11, 13, 15, 17, 19, 21, 24, 26, 28
	SIC, BIC	27	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29	2	20, 25	4	2, 9, 20, 25
	MBIC	27	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29	1	20	3	2, 20, 25
	AIC	27	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29	2	20, 25	8	2, 4, 10, 13, 17, 19, 25, 28
	Manual	27	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29	2	20, 25	10	2, 4, 10, 13, 17, 19, 21, 24, 26, 28

* means each time point was detected as a change point; *** means change points detected are more than 40.

,

Table A4. PELT Algorithm Result for Simulated Infection.

n	Penalty	PELT(Mean)		PELT(Variance)		PELT(Mean, Variance)
		m	τ	m	τ	m	τ
50	None	34	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	17	2, 4, 6, 9, 12, 14, 16, 18, 20, 23, 25, 27, 29, 31, 33, 35, 42	21	2, 4, 6, 9, 11, 13, 15, 17, 19, 21, 24, 26, 28, 30, 32, 34, 36, 38, 40, 45, 47
	SIC, BIC	30	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 33	2	20, 25	5	2, 20, 25, 30, 34
	MBIC	30	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 33	2	20, 25	4	20, 25, 30, 34
	AIC	31	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33	2	20, 25	10	2, 4, 10, 13, 17, 19, 25, 28, 31, 34
	Manual	31	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33	2	20, 25	13	2, 4, 10, 13, 17, 19, 21, 24, 26, 28, 30, 32, 34

* means each time point was detected as a change point; *** means change points detected are more than 40.

,

Table A5. PELT Algorithm Result for Simulated Infection.

n	Penalty	PELT(Mean)		PELT(Variance)		PELT(Mean, Variance)
		m	τ	m	τ	m	τ
100	None	34	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	34	2, 4, 6, 8, 10, 13, 15, 17, 20, 22, 24, 26, 28, 30, 32, 34, 38, 42, 46, 52, 54, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95	39	2, 4, 6, 9, 11, 13, 15, 17, 19, 21, 24, 26, 28, 30, 32, 34, 36, 38, 40, 45, 47, 49, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 90, 92, 94, 96, 98
	SIC, BIC	30	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 33	2	20, 27	5	2, 20, 25, 30, 34
	MBIC	29	2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 33	2	20, 27	3	20, 27, 34
	AIC	31	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33	2	20, 27	10	2, 4, 10, 13, 17, 19, 25, 28, 31, 34
	Manual	31	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33	6	4, 10, 13, 17, 20, 27	13	2, 4, 10, 13, 17, 19, 21, 24, 26, 28, 30, 32, 34
201	None	34	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	19	2, 4, 6, 9, 11, 13, 15, 17, 19, 21, 24, 26, 28, 30, 32, 34, 37, 72, 74	72	***

* means each time point was detected as a change point; *** means change points detected are more than 40.

,

Table A6. PELT Algorithm Result for Simulated Infection.

n	Penalty	PELT(Mean)		PELT(Variance)		PELT(Mean, Variance)
		m	τ	m	τ	m	τ
201	SIC, BIC	30	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 33	2	20, 28	4	20, 25, 30, 34
	MBIC	29	2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 33	2	20, 28	3	20, 27, 34
	AIC	31	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33	5	9, 16, 19, 26, 29	10	2, 4, 10, 13, 17, 19, 25, 28, 31, 34
	Manual	31	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33	5	9, 16, 19, 26, 29	13	2, 4, 10, 13, 17, 19, 21, 24, 26, 28, 30, 32, 34

* means each time point was detected as a change point; *** means change points detected are more than 40.

,

Table A7. BOCPD Algorithm Result for Simulated Transmissibility Rate and Infection.

n	$\mathit{\beta }$		$\mathit{I}\left(\mathit{t}\right)$
	$\mathit{m}$	$\mathit{\tau }$	$\mathit{m}$	$\mathit{\tau }$
20	1	19	1	*
30	1	21	1	21
50	1	21	3	21,28,35
100	2	21, 58, 100	100	21,28,36
201	3	21, 58, 101	3	21,28,37

* means each time point was detected as a change point; *** means change points detected are more than 40.

,

Table A8. BOCPD Algorithm Result for Poland’s COVID-19 Transmissibility Rate and Infection.

n	$\mathit{\beta }$		$\mathit{I}\left(\mathit{t}\right)$
	$\mathit{m}$	$\mathit{\tau }$	$\mathit{m}$	$\mathit{\tau }$
20	1	19	1	19
30	1	19	2	19, 21
50	2	19, 33	4	19, 21, 31, 41
100	4	19, 33, 52, 66	7	19, 21, 31, 41, 53, 65, 81
200	6	19, 33, 52, 66, 116, 153	13	19, 21, 31, 41, 53, 65, 81, 97, 114, 134, 146, 171, 188
413	10	19, 33, 52, 66, 116, 153, 223, 269, 284, 383	24	19, 21, 31, 41, 53, 65, 81, 97, 114, 134, 146, 171, 188, 205, 224, 237, 246, 258, 272, 292, 304, 339, 376, 398

* means each time point was detected as a change point; *** means change points detected are more than 40.

,

Table A9. PELT Algorithm Result for Poland’s COVID-19 Transmissibility Rate.

n	Penalty	PELT(Mean)		PELT(Variance)		PELT(Mean, Variance)
		m	τ	m	τ	m	τ
20	None	2	18, 19	4	2, 6, 12, 18	4	2, 9, 13, 18
	SIC, BIC	1	20	1	18	1	18
	MBIC	1	20	1	18	1	18
	AIC	1	20	1	18	1	18
	Manual	1	20	1	18	1	18
30	None	12	18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29	8	10, 12, 14, 18, 21, 24, 26, 28	9	2, 9, 13, 18, 20, 22, 24, 26, 28
	SIC, BIC	1	30	2	18, 21	2	18, 21
	MBIC	1	30	1	30	2	18, 21
	AIC	1	30	2	18, 21	2	18, 21
	Manual	1	30	2	18, 21	2	18, 21
50	None	32	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, 44, 45, 46, 47, 48, 49	17	2, 5, 7, 12, 18, 21, 24, 26, 29, 32, 34, 36, 38, 41, 44, 46, 48	17	2, 9, 13, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 39, 41, 44, 47
	SIC, BIC	1	50	3	18, 21, 32	4	18, 21, 32, 39
	MBIC	1	50	1	32	4	18, 21, 32, 39
	AIC	1	50	5	18, 21, 32, 36, 41	6	18, 21, 32, 36, 38, 43
	Manual	1	50	5	18, 21, 32, 36, 41	9	18, 21, 30, 32, 36, 39, 41, 44, 47
100	None	82	***	41	3, 5, 7, 9, 13, 15, 18, 21, 24, 26, 29, 32, 34, 36, 39, 41, 44, 47, 49, 51, 53, 55, 57, 60, 62, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 86, 88, 91, 93, 95, 98	41	2, 9, 13, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 39, 41, 44, 47, 49, 51, 53, 55, 57, 60, 62, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 98
	SIC, BIC	1	100	2	18, 32	8	18, 21, 32, 39, 53, 55, 57, 65
	MBIC	1	100	2	18, 32	5	18, 21, 36, 53, 65

* means each time point was detected as a change point; *** means change points detected are more than 40.

,

Table A10. PELT Algorithm Result for Poland’s COVID-19 Transmissibility Rate.

n	Penalty	PELT(Mean)		PELT(Variance)		PELT(Mean, Variance)
		m	τ	m	τ	m	τ
100	AIC	1	100	5	18, 21, 32, 43, 57	22	18, 21, 32, 36, 38, 44, 47, 49, 53, 55, 57, 65, 69, 71, 75,77, 81, 83, 87, 89, 91, 93
	Manual	1	100	5	18, 21, 32, 43, 57	27	18, 21, 30, 32, 36, 39, 41, 44, 47, 49, 53, 55, 57, 60, 65, 69, 71, 75, 77, 81, 83, 87, 89, 91, 93, 95, 98
200	None	182	***	81	***	86	***
	SIC, BIC	1	200	4	18, 32, 43, 153	12	18, 21, 32, 39, 53, 57, 65, 124, 133, 147, 157, 183
	MBIC	1	200	2	18, 40	7	18, 32, 51, 65, 124, 133, 152
	AIC	1	200	10	18, 21, 32, 43, 53, 55, 57, 65, 159, 176	53	18, 21, 32, 36, 38, 44, 47, 49, 53, 55, 57, 65, 69, 71, 75, 77, 81, 83, 87, 89, 91, 93, 95, 98, 106, 110, 112, 115, 124, 129, 131, 135, 137, 139, 144, 147, 150, 152, 156, 164, 166, 169, 171, 174, 176, 180, 182, 184, 186, 188, 190, 192, 197
	Manual	1	200	11	18, 21, 32, 43, 53, 55, 57, 65, 157, 166, 176	65	***
413	None	395	***	171	***	182	***
	SIC, BIC	1	413	8	18, 32, 49, 164, 176, 235, 267, 281	17	18, 21, 32, 39, 53, 65, 124, 133, 147, 157, 183, 215, 236, 239, 267, 283, 382

* means each time point was detected as a change point; *** means change points detected are more than 40.

,

Table A11. PELT Algorithm Result for Poland’s COVID-19 Transmissibility Rate.

n	Penalty	PELT(Mean)		PELT(Variance)		PELT(Mean, Variance)
		m	τ	m	τ	m	τ
413	MBIC	1	413	3	18, 32, 49	12	18, 32, 51, 65, 124, 133, 152, 183, 215, 268, 283, 382
	AIC	1	413	15	18, 21, 32, 43, 53, 65, 157, 164, 176, 213, 223, 267, 281, 382, 386	128	***
	Manual	1	413	19	18, 21, 32, 43, 53, 65, 157, 164, 176, 213, 222, 235, 260, 268, 281, 319, 321, 382, 386	151	***

* means each time point was detected as a change point; *** means change points detected are more than 40.

,

Table A12. PELT Algorithm Result for Poland’s COVID-19 Daily Infection.

n	Penalty	PELT(Mean)		PELT(Variance)		PELT(Mean, Variance)
		m	τ	m	τ	m	τ
20	None	1	18	7	5, 7, 9, 11, 13, 15, 18	4	2, 9, 13, 18
	SIC, BIC	1	20	1	18	1	1, 17
	MBIC	1	20	1	18	1	18
	AIC	1	20	1	18	1	18
	Manual	1	20	1	18	1	18
30	None	11	18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29	9	3, 10, 12, 18, 20, 22, 24, 26, 28	9	2, 9, 13, 18, 20, 22, 24, 26, 28
	SIC, BIC	9	20, 22, 23, 24, 25, 26, 27, 28, 29	1	26	4	18, 20, 22, 26
	MBIC	9	20, 22, 23, 24, 25, 26, 27, 28, 29	1	26	3	18, 20, 26
	AIC	9	20, 22, 23, 24, 25, 26, 27, 28, 29	1	26	5	18, 20, 22, 26, 28
	Manual	9	20, 22, 23, 24, 25, 26, 27, 28, 29	1	26	6	18, 20, 22, 24, 26, 28

* means each time point was detected as a change point; *** means change points detected are more than 40.

,

Table A13. PELT Algorithm Result for Poland’s COVID-19 Daily Infection.

n	Penalty	PELT(Mean)		PELT(Variance)		PELT(Mean, Variance)
		m	τ	m	τ	m	τ
50	None	31	18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49	18	2, 7, 11, 18, 20, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47	19	2, 9, 13, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48
	SIC, BIC	29	20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49	1	42	8	18, 20, 22, 26, 30, 35, 42, 48
	MBIC	29	20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49	1	42	6	18, 20, 26, 30, 35, 42
	AIC	29	20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49	3	33, 38, 42	13	18, 20, 22, 26, 28, 30, 33, 35, 38, 40, 42, 45, 48
	Manual	29	20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49	3	33, 38, 42	16	18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48
100	None	81	***	38	18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 69, 71, 73, 76, 78, 80, 82, 85, 87, 90, 93, 95, 97	43	2, 9, 13, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 85, 87, 89, 91, 93, 95, 97

* means each time point was detected as a change point; *** means change points detected are more than 40.

,

Table A14. PELT Algorithm Result for Poland’s COVID-19 Daily Infection.

n	Penalty	PELT(Mean)		PELT(Variance)		PELT(Mean, Variance)
		m	τ	m	τ	m	τ
100	SIC, BIC	79	***	2	47, 60	14	18, 20, 26, 30, 35, 42, 48, 55, 64, 71, 80, 86, 90, 93
	MBIC	78	***	1	100	12	18, 20, 26, 30, 38, 47, 55, 64, 71, 80, 86, 95
	AIC	79	***	4	43, 50, 55, 63	32	18, 20, 22, 26, 28, 30, 33, 35, 38, 40, 42, 45, 48, 50, 52, 55, 58, 60, 62, 64, 66, 69, 71, 73, 78, 80, 85, 87, 90, 93, 95, 97
	Manual	79	***	4	43, 50, 55, 63	39	18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 69, 71, 73, 76, 78, 80, 82, 85, 87, 89, 91, 93, 95, 97
200	None	181	***	90	***	92	***
	SIC, BIC	178	***	8	52, 64, 79, 96, 145, 151, 164, 173	24	18, 20, 26, 30, 38, 47, 55, 64, 71, 80, 86, 95, 104, 112, 134, 141, 144, 153, 157, 161, 171, 180, 187, 192
	MBIC	177	***	4	62, 87, 148, 165	19	18, 20, 30, 40, 52, 64, 71, 80, 86, 97, 112, 134, 141, 144, 151, 163, 171, 181, 192
	AIC	178	***	11	52, 64, 79, 93, 112, 134, 146, 151, 164, 170, 180	69	***
	Manual	178	***	11	52, 64, 79, 93, 112, 134, 146, 151, 164, 170, 180	83	***

* means each time point was detected as a change point; *** means change points detected are more than 40.

and

Table A15. PELT Algorithm Result for Poland’s COVID-19 Daily Infection.

n	Penalty	PELT(Mean)		PELT(Variance)		PELT(Mean, Variance)
		m	τ	m	τ	m	τ
413	None	394	***	189	***	192	***
	SIC, BIC	391	***	4	243, 258, 301, 389	48	18, 20, 26, 30, 38, 47, 55, 64, 71, 80, 86, 95, 104, 112, 134, 141, 144, 153, 157, 161, 171, 181, 192, 202, 208, 218, 223, 230, 236, 243, 250, 257, 265, 273, 290, 298, 304, 309, 316, 338, 345, 369, 375, 382, 390, 396, 404, 411
	MBIC	390	***	3	264, 300, 389	33	18, 20, 30, 40, 52, 64, 71, 80, 86, 97, 112, 134, 141, 144, 170, 181, 192, 203, 224, 236, 245, 257, 271, 291, 303, 316, 339, 369, 375, 382, 390, 396, 404
	AIC	391	***	5	245, 256, 264, 301, 389	148	***
	Manual	391	***	5	245, 256, 264, 301, 389	177	***

* means each time point was detected as a change point; *** means change points detected are more than 40.

).

6. Results and Discussion

6.1. Simulation Result

Here, the result of the change-point detection algorithm is presented for the simulated data. To illustrate an online approach, both change-point algorithms (PELT and BOCPD) were tested in bits of 20, 30, 50, 100 and 201. It was possible to trace the change-point process of the transmission rate since the rate was self-introduced at time-points 35, 65, 100, 137 and 174.

The two algorithms (BOCPD and PELT) explored were able to properly detect some changes between the transmissibility data after time-point 20. We also discovered that the use of no penalty value results in the discovery of too many change points in the data. This was especially too many for the case of the specific mean penalty function (Function (24)); we detected change points at every time point. The manual approach, i.e., the use of the traditional elbow plot, had the second lowest performance. The AIC and the MBIC penalty function used on either of the specific variance (Function (25)) or specific mean and variance (Function (26)) are preferred for change-point detection in the simulated transmission rate and the infection. Based on the accuracy of the detection algorithm and the number of change points detected, the MBIC penalty function is preferred. Thus, we report the plot for only the MBIC penalty value. Furthermore, a larger sample improves the detection. We can see this in the BOCPD result.

Figure 7 shows the detection location of the BOCPD, specific variance PELT, and specific mean and variance PELT algorithm. The two PELT algorithms have three change points where they coincide (CP at 18, 20 and 99) and the last change point with a difference of one time-point—CP located at time-point 56 for specific variance and 57 for specific mean and variance PELT. These change points are one to two time-points away from the BOCPD change points; BOCPD change points are located at time points 21, 58 and 101. The change points discovered in the transmissible rate by the algorithms are related to the induced change-point locations. For instance, the real change point fixed at the time-point is in the domain of the change point located at time-point 20 for the two PELT algorithms and 21 for the BOCPD. The change point fixed at 65 can be linked with the change point at 56 in the specific variance PELT algorithm, point 57 in the specific mean and variance PELT algorithm and point 58 of the BOCPD. The change point fixed at 100 is detected at 99 for the PELT algorithms and 101 for the BOCPD. Thus, we can conclude that it is difficult to detect the last two fixed change points, i.e., 137 and 174. The reason may be due to a low variation in the segment of the observation containing the change points. It is possible to understand this from the change-point detection involving only the mean with constant variation.

We compare the result from the transmission rate to the daily infection. We discover that the points of detection do not necessarily agree. This effect can be understood from the simulation algorithm of the SIRD model. The disease flows at a specific rate per time but an infected person does not become “double-infected”. A general observation that shows the PELT algorithm detecting changes at a point behind the BOCPD can also be noticed. For instance, the BOCPD detects changes at time-points 21, 28 and 35, while the specific mean and variance PELT algorithm detect changes at time-points 20, 27 and 34. Specific variance PELT has change points located at time-points 20 and 28. The three methods were sensitive enough to detect the end segment of the disease (Figure 8). The issue of variance detection from the transmission rate and the difference in its change-point locations from the daily infection implies that change-point detection that takes variations into account is most needed for a phase-type model such as this.

6.2. Change-Point Detection on Real-Life Data

Following the same procedure used to detect change points in the simulated data, we observe similar effects of the change-point algorithms on the transmission rate and daily infection. These include the fact that the specific variance and the specific mean and variance PELT algorithm are preferred based on observations from Figure 9. Specific variance PELT was very sensitive to high variation. In this case, the specific mean and variance PELT appears to be better than other PELT approaches. This is because it could detect abrupt changes in segments with small variations (Figure 9). The plotted algorithms detect almost similar changes till the same time-point (CPs at time-points 18–19, 32–33 and 49–52). After these time-points, the specific variance PELT algorithm could not detect any other changes.

Figure 10 presents the pattern of detecting high and low variation changes as in the transmission rate, which was also observed for the daily infection. However, it is more obvious from Figure 11 that the specific variance PELT detects fewer change points than the other algorithms. It is important to note that choosing highly optimized (specific variance PELT with MBIC) change points does not imply that the other change points detected by other means are not significant. Critically checking these points, we can observe change events surrounding the COVID-19 pandemic. The specific variance PELT with MBIC was selected based on the simulation result. We detect change points at points 264, 300 and 389. These points fall on 4 November 2020, 10 December 2020 and 9 March 2021. The events surrounding these dates are highlighted below:

• Change point at time-point 264 (4 November 2020): Stricter coronavirus disease (COVID-19) restrictions were announced for Saturday (7 November 2020) by the Polish Prime Minister Mateusz Morawiecki, who also warned that if cases did not become stable, a full lockdown might be introduced in a week to ten days. As a result of the new laws, most retail malls, theaters, museums, galleries and cinemas would close. Students who had not previously worked remotely would be required to do so. Hotel rooms would be available only to business guests. Previously, bars and restaurants had been ordered to close, and the elderly had been advised to remain at home. This was due to the increase in the daily cases.
• Change point at time-point 298 (10 December 2020): Due to increased disease activity in Poland, authorities planned to strengthen current coronavirus disease (COVID-19) restrictions from 28 December 2020 to at least 17 January 2021. International arrivals were expected to isolate for 10 days, unless they traveled through private means. Additionally, theaters, museums, etc., were closed and hotels were only opened for business purposes. Looking at Figure 10, we observe that a decrease in daily infections was observed around this period; however, the purpose of this declaration can either be traced to the total current infections and/or cumulative infections. The period was also the festive season and the beginning of a new year, which could lead to a high contact rate between people, especially during new year’s eve. The news also indicated that the second wave of COVID-19 started around late December.
• Change point at time-point 389 (9 March 2021): Another rise in daily COVID-19 infections in Poland; news spread tagged sometime around early March the third wave of COVID-19 in Poland. Health officials tightened COVID-19 entry restrictions for certain travelers on 27 February 2021, while domestic limitations would be extended until at least 14 March 2021. On 20 March 2021, a total lockdown was announced for the whole country of Poland. The new restriction required pupils within the age of 1–3 years to return back to online learning.

7. Conclusions

This work investigates change-point detection algorithms in phase-type signals. The subject of consideration was the epidemic model, which suited the data that we used for the analysis. We used the Suspected, Infected, Recovered and Death (SIRD) model for the study. The main parameter that we were interested in was the mean and the variance of the transmissibility rate and daily infection. The two algorithms used for our analysis were the Bayesian Online Change Point Detection (BOCPD) algorithm and Pruned Exact Linear Time (PELT) algorithm. BOCPD employs the Bayes theorem depending on run length. PELT is an optimization approach to change points with pruning. Since it is possible to run the optimization in the PELT algorithm with different penalty values, we considered five different statistical penalty functions. These included the AIC, BIC/SIC, MBIC, a Manual approach using the elbow method and a null penalty value. The PELT algorithm also permits change-point detection for two parameters of interest: the mean, the variance and the variance and the mean together. We tested the algorithms on simulated data before the real-life data. The simulation was performed with a social network graph to obtain a practical representation ability. We used Poland’s COVID-19 data for our real-life test. Estimating the change points in the simulated transmissibility rate and the daily infection, we discovered that (a) the BOCPD and the PELT algorithm will most likely detect the same change points, probably with a unit time difference; (b) mean detection in the PELT algorithm has poor performance; this implies that the variance or a combination of both parameters for detection is better; (c) the penalty value that optimizes the model parameters well is the MBIC; (d) the change-point location of the transmissibility rate and daily infection is not necessarily the same. As illustrated, we observed the events surrounding the moment of change in the variance PELT algorithm with the MBIC as the penalty value. The three dates detected by this algorithm were 11 November 2020, 10 December 2020 and 9 March 2021. We discovered that the last two dates were the period when the second and third waves of COVID-19 were said to have started in Poland. There was a strict lockdown policy announcement during these periods.