In this paper we present generalizations of the k-means clustering algorithm, with guaranteed monotonic convergence, which do not require that data points be localized in a vector space. Instead, only a dissimilarity matrix between data points is needed. This generalization allows k-means-like clustering to be applied to data-sets that cannot be embedded exactly in an Euclidean space, such as road networks, and data-sets with categorical data. If the data points have localizations in an Euclidean space and the dissimilarity matrix is the matrix of mutual squared Euclidean distances between points, one of our algorithms perfectly mirrors the classical k-means. If the dissimilarity matrix does not correspond to an Euclidean scenario, our experimental results using both real-world and synthetic data sets show that our proposed generalizations of k-means generally lead to more compact clusters than k-medoids clustering.