# Unsupervised Offline Changepoint Detection Ensembles
## 2 Materials and Methods
### Ensembles of Offline Changepoint Detection Procedures
#### 2.1.3 Changepoint Detection Procedure  
We call \(\Pi\) a changepoint detection (CPD) procedure if \(\Pi\) finds the \"best partition\" \(\hat{\mathcal{T}}\) by minimizing the quantitative criterion \(V(\mathcal{T},y)=\sum_{k=0}^{K}c(y_{t_{k}\cdot t_{k+1}})\), where \(c(\cdot)\) is a cost function which measures for each point of the partition \(t_{k}\) or for each subsequence \(y_{t_{k}\cdot t_{k+1}}\) a \"quality of partition\". To find the \"best partition\" \(\hat{\mathcal{T}}\), a discrete optimization problem of minimizing the criterion \(V(\mathcal{T},y)\) must be solved. If a number of changepoints \(K\) is known beforehand, an optimization problem is as follows:  
\[\min_{|\mathcal{T}|=K}V(\mathcal{T},y), \tag{1}\]  
where \(|\mathcal{T}|\) is a cardinality of a \(\mathcal{T}\).  
For an unknown \(K\), an optimization problem looks like:  
\[\min_{\mathcal{T}}V(\mathcal{T},y)+\text{pen}(\mathcal{T})=\min_{\mathcal{T} }\bar{V}(\mathcal{T},y), \tag{2}\]  
where \(\text{pen}(\mathcal{T})\) is a constraint to balance a number of found changepoints. Additional penalty allows to choose if a few most highly ranked points (or even none) or a lot of candidates of a changepoint will be selected as a final decision of a \"best partition\" \(\hat{\mathcal{T}}\).  
It is important to mention that in the case of a multivariate problem (\(D>1\)), we need to aggregate criteria for each of the \(D\) time series inside the \(\Pi\) (in this case, we can call \(\Pi\) an ensemble already according to the further definition of the ensemble procedure). To avoid dealing with ensembling of individual univariate time series, considered criterion \(V(\mathcal{T},y)\) is then defined in our case in a common way as a sum of the criteria calculated for each univariate time series and looks like:  
\[V(\mathcal{T},y)=\sum_{d=1}^{D}V_{d}(\mathcal{T},y_{d}) \tag{3}\]  
Though dealing with univariate time series and following aggregating looks like a simpler approach against using multivariate models from the first, the paper [21] clearly shows how aggregation of the univariate models outperforms multivariate models.  
A CPD procedure in a general way may consist of three main parts:  
1. _A cost function_\(c(\cdot)\), also called a model,
2. _A search method_ for finding \(\hat{\mathcal{T}}\), also called an optimization or detection algorithm,
3. _A constraint_ on the number of changepoints if the exact number of changepoints \(K\) is unknown.  
The scheme of the CPD procedure used in our work is shown in Figure 1.  
For a comprehensive review of cost functions and search methods, the theoretical foundation behind them as well as the intuition behind the selection of a constraint, an interested reader may refer to [22]. The number of changepoints \(K\) or a constraint are usually set in a problem statement or can be defined during the experiment process, and the search method only determines the way of changepoint finding. A cost function determines the particular function for minimizing. Therefore, it is vital to select the right cost function for each specific changepoint detection case since different cost functions  
Figure 1: Components of a typical non-ensemble changepoint detection (CPD) approach.  
usually represent different statistical properties of a signal. For example, changes in a mean can hardly be detected through standard deviation calculation. It also means that proper cost function selection can become a laborious and time-consuming process with an uncertain result.