## 2 Methods
### General Prototype-Based Clustering and Its Convergence  
As described above, prototype-based conditional clustering algorithms comprise two main phases. First, they start with an initial partition of the data, and second, the quality of this partition is improved by a local search algorithm during the search phase. The initial partition can be obtained based on many different principles [4; 8], but a common strategy is to use distinct prototypes [9]. Most typically, the globalization of the whole algorithm is based on random initialization with several regenerations [10]. Then, the best solution with the smallest clustering error is chosen as the final result. The iterative relocation algorithm skeleton for prototype-based partitional clustering is presented in Algorithm 1[12; 16]. ```
Input: Dataset and the number of clusters \(K\). Output: Partition of dataset into \(K\) disjoint groups. Select \(K\) points as the initial prototypes; repeat  1. Assign individual observation to the closest prototype;  2. Recompute the prototype with the assigned observations; until the partition does not change;
```  
**Algorithm 1**Prototype-based partitional clustering algorithm. As stated in [17] (see also [19]), the different location estimates for a cluster prototype arise from different \(l_{p}\)-norms to the \(q\)-th power as the distance measure and the corresponding clustering error function; mean refers to \(\|\cdot\|_{2}^{2}\) (\(p=q=2\)), median is characterized by \(\|\cdot\|_{1}^{1}\) (\(p=q=1\)), and the spatial median is given by \(\|\cdot\|_{2}^{1}\) (\(p=2,q=1\)). Hence, generally the repetition of Steps 1 and 2 from the search phase of Algorithm 1 locally minimize the following clustering error criterion:  
\[\mathcal{J}(\{\mathbf{b}_{k}\})=\sum_{k=1}^{K}\sum_{\mathbf{x}_{i}\in\mathbf{ c}_{k}}\|\mathbf{x}_{i}-\mathbf{b}_{k}\|_{p}^{q}. \tag{1}\]  
Here \(\{\mathbf{b}_{k}\},\ k=1,\ldots,K\) denote the prototype vectors to be determined and \(\{\mathbf{x}_{i}\}_{i=1}^{N},\mathbf{x}_{i}\in\mathbb{R}^{n}\) refers to the given set of \(n\)-dimensional observations. The interpretation of (1) is that each observation \(\mathbf{x}_{i}\) is assigned to cluster \(k\) with the closest prototype on the \(l_{p}\)-norm:  
\[\mathbf{C}_{k}=\{1\leq k\leq K\mid\|\mathbf{x}_{i}-\mathbf{b}_{k}\|_{p}\leq\| \mathbf{x}_{i}-\mathbf{b}_{k^{\prime}}\|_{p}\quad\forall k\
eq k^{\prime}\}.\]  
Hence, as noted in [40], another more compact way of formalizing the clustering error criterion reads as  
\[\mathcal{J}(\{\mathbf{b}_{k}\})=\sum_{i=1}^{N}\min_{k=1,\ldots,K}\|\mathbf{x}_ {i}-\mathbf{b}_{k}\|_{p}^{q}, \tag{2}\]  
which more clearly shows the _nonsmoothness_ of the clustering problem, because the min-operator is not classically differentiable (see [17] and references therein). This observation gives rise to a different set of clustering algorithms that are based on nonsmooth optimization solvers [41]. However, despite the nonsmoothness of the error function, it can be shown that the search phase of Algorithm 1 decreases the clustering error, ensuring local convergence of the algorithm in finite many steps. We formalize this in the next proposition. The proof here is a slight modification and simplification of the more general treatment in [19], Theorem 5.3.1, along the lines of the convergence analyses in different problem domains, as given in [42; 43; 44]. **Proposition 1**. : _The repeated Steps 1 and 2 of Algorithm 1 decrease the clustering error function (2). This guarantees convergence of the algorithm in finite many steps._  
Proof. : Let us denote by superscript \(t\) the current iterates of the prototypes \(\{\mathbf{b}_{k}^{i}\}\) with the initial candidates for \(t=0\).