## 4 Applications to Center-Based Clustering  
Clustering is a class of unsupervised learning algorithms which partitions a given \(d\)-dimensional point set \(\mathcal{P}=\{p_{1},\ldots,p_{n}\}\) into clusters such that data points falling into a same cluster tend to be more similar to data points belonging to different clusters. The celebrated \(k\)-means clustering [69] is a center-based method for clustering \(\mathcal{P}\) into \(k\) clusters \(\mathcal{C}_{1},\ldots,\mathcal{C}_{k}\) (with \(\mathcal{P}=\cup_{i=1}^{k}\mathcal{C}_{i}\)), by minimizing the following \(k\)-means objective function  
\[L(\mathcal{P},\mathcal{C})=\frac{1}{n}\sum_{i=1}^{n}\min_{j\in\{1,\ldots,k\}} \|p_{i}-c_{j}\|^{2}, \tag{107}\]where the \(c_{j}\)'s denote the cluster representatives. Let \(\mathcal{C}=\{c_{1},\ldots,c_{k}\}\) denote the set of cluster centers. The cluster \(\mathcal{C}_{j}\) is defined as the points of \(\mathcal{P}\) closer to cluster representative \(c_{j}\) than any other \(c_{i}\) for \(i\
eq j\):  
\[\mathcal{C}_{j}=\{p\in\mathcal{P}\ :\ \|p-c_{j}\|^{2}\leq\|p-c_{i}\|^{2}, \forall l\in\{1,\ldots,k\}\}.\]  
When \(k=1\), it can be shown that the centroid of the point set \(\mathcal{P}\) is the unique best cluster representative:  
\[\arg\min_{c_{1}}L(\mathcal{P},\{c_{1}\})\Rightarrow c_{1}=\frac{1}{n}\sum_{i =1}^{n}p_{i}.\]  
When \(d>1\) and \(k>1\), finding a best partition \(\mathcal{P}=\cup_{j=1}^{k}\mathcal{C}_{j}\) which minimizes the objective function of Equation (107) is NP-hard [70]. When \(d=1\), \(k\)-means clustering can be solved efficiently using dynamic programming [71] in subcubic \(O(n^{3})\) time.  
The \(k\)-means objective function can be generalized to any arbitrary (potentially asymmetric) divergence \(D(\cdot:\cdot)\) by considering the following objective function:  
\[L_{D}(\mathcal{P},\mathcal{C}):=\frac{1}{n}\,\sum_{i=1}^{n}\min_{j\in\{1, \ldots,k\}}D(p_{i}:c_{j}). \tag{108}\]  
Thus, when \(D(p:q)=\|p-q\|^{2}\), one recovers the ordinary \(k\)-means clustering [69]. When \(D(p:q)=B_{F}(p:q)\) is chosen as a Bregman divergence, one gets the right-sided Bregman \(k\)-means clustering [72] as the minimization of the cluster centers are defined on the right-sided arguments of \(D\) in Equation (108). When \(F(x)=\|x\|_{2}^{2}\), Bregman \(k\)-means clustering (i.e., \(D(p:q)=B_{F}(p:q)\) in Equation (108)) amounts to the ordinary \(k\)-means clustering. The right-sided Bregman centroid for \(k=1\) coincides with the center of mass and is independent of the Bregman generator \(F\):  
\[\arg\min_{c_{1}}L_{B_{F}}(\mathcal{P},\{c_{1}\})\Rightarrow c_{1}=\frac{1}{n} \sum_{i=1}^{n}p_{i}.\]  
The left-sided Bregman \(k\)-means clustering is obtained by considering the right-sided Bregman centroid for the reverse Bregman divergence \((B_{F})^{*}(p:q)=B_{F}(q:p)\), and the left-sided Bregman centroid [73] can be expressed as a multivariate generalization of the quasi-arithmetic mean:  
\[c_{1}=(\
abla F)^{-1}\Bigg{(}\frac{1}{n}\sum_{i=1}^{n}\
abla F(p_{i})\Bigg{)}.\]  
In order to study the robustness of \(k\)-means clustering with respect to our novel family of divergences \(I_{\alpha}^{f,\mathcal{S}}\), we first study the robustness of the left-sided Bregman centroids to outliers.