Generalized $k$-means (KM)

We also employed the well-known Euclidean $k$-means algorithm and three variations of it using non-metric distance measures. The $k$-means algorithm is an iterative algorithm to minimize the least squares error criterion [DH73]. A cluster $\mathcal{C}_{\ell}$ is represented by its center $\mu_{\ell}$, the mean of all samples in $\mathcal{C}_{\ell}$. The centers are initialized with a random selection of $k$ data objects. Each sample is then labeled with the index $\ell$ of the nearest or most similar center. In classical $k$-means, `nearest' means the point with the smallest Euclidean distance. However, $k$-means can be generalized by substituting nearness with any other notion of similarity. For our comparison, we will use all four definitions of the similarity $s(\mathbf{x}_a,\mathbf{x}_b)$ between two objects $\mathbf{x}_a$ and $\mathbf{x}_b$ as introduced in the previous section. Subsequent re-computing of the mean for each cluster and re-assigning the cluster labels is iterated until convergence to a fixed labeling after $m$ iterations. The complexity of this algorithm is $O(n \cdot d \cdot k \cdot m)$.