Mesh partitioning is an indispensable tool for efficient parallel numerical simulations. Its goal is to minimize communication between the processes of a simulation while achieving load balance. Established graph-based partitioning tools yield a high solution quality; however, their scalability is limited. Geometric approaches usually scale better, but their solution quality may be unsatisfactory for "non-trivial" mesh topologies. In this paper, we present a scalable version of k-means that is adapted to yield balanced clusters. Balanced k-means constitutes the core of our new partitioning algorithm Geographer. Bootstrapping of initial centers is performed with space-filling curves, leading to fast convergence of the subsequent balanced k-means algorithm. Our experiments with up to 16 384 MPI processes on numerous benchmark meshes show the following: (i) Geographer produces partitions with a lower communication volume than state-of-the-art geometric partitioners from the Zoltan package; (ii) Geographer scales well on large inputs; (iii) a Delaunay mesh with a few billion vertices and edges can be partitioned in a few seconds.
Lloyd's greedy algorithm @cite_22 for the @math -means problem consists of repeatedly alternating two steps: For every point @math : Assign @math to the cluster @math so that the distance between @math and @math is minimized. For every cluster @math : Set cluster center @math to the arithmetic mean of all points in @math . The algorithm stops when the maximum movement of cluster centers is below a user-defined threshold, at the latest if no cluster membership changes.
@cite_22
2204035083 2018165630 2199495299 2952769483
The Lloyd’s algorithm, also known as the k-means algorithm, is one of the most popular algorithms for solving the k-means clustering problem in practice. However, it does not give any performance guarantees. This means that there are datasets on which this algorithm can behave very badly. One reason for poor performance on certain datasets is bad initialization. The following simple sampling based seeding algorithm tends to fix this problem: pick the first center randomly from among the given points and then for i ≥ 2, pick a point to be the i th center with probability proportional to the squared distance of this point from the previously chosen centers. This algorithm is more popularly known as the k-means++ seeding algorithm and is known to exhibit some nice properties. These have been studied in a number of previous works [AV07, AJM09, ADK09, BR11]. The algorithm tends to perform well when the optimal clusters are separated in some sense. This is because the algorithm gives preference to further away points when picking centers. [ORSS06] discuss one such separation condition on the data. Jaiswal and Garg [JG12] show that if the dataset satisfies the separation condition of [ORSS06], then the sampling algorithm gives a constant approximation with probability Ω(1 k). Another separation condition that is strictly weaker than [ORSS06] is the approximation stability condition discussed by [BBG09]. In this work, we show that the sampling algorithm gives a constant approximation with probability Ω(1 k) if the dataset satisfies the separation condition of [BBG09] and the optimal clusters are not too small. We give a negative result for datasets that have small optimal clusters. We consider @math -median clustering in finite metric spaces and @math -means clustering in Euclidean spaces, in the setting where @math is part of the input (not a constant). For the @math -means problem, show that if the optimal @math -means clustering of the input is more expensive than the optimal @math -means clustering by a factor of @math , then one can achieve a @math -approximation to the @math -means optimal in time polynomial in @math and @math by using a variant of Lloyd's algorithm. In this work we substantially improve this approximation guarantee. We show that given only the condition that the @math -means optimal is more expensive than the @math -means optimal by a factor @math for some constant @math , we can obtain a PTAS. In particular, under this assumption, for any @math we achieve a @math -approximation to the @math -means optimal in time polynomial in @math and @math , and exponential in @math and @math . We thus decouple the strength of the assumption from the quality of the approximation ratio. We also give a PTAS for the @math -median problem in finite metrics under the analogous assumption as well. For @math -means, we in addition give a randomized algorithm with improved running time of @math . Our technique also obtains a PTAS under the assumption of that all @math approximations are @math -close to a desired target clustering, in the case that all target clusters have size greater than @math and @math is constant. Note that the motivation of is that for many clustering problems, the objective function is only a proxy for the true goal of getting close to the target. From this perspective, our improvement is that for @math -means in Euclidean spaces we reduce the distance of the clustering found to the target from @math to @math when all target clusters are large, and for @math -median we improve the largeness'' condition needed in the work of to get exactly @math -close from @math to @math . Our results are based on a new notion of clustering stability. In k-means clustering we are given a set of n data points in d-dimensional space Rd and an integer k, and the problem is to determine a set of k points in &#211C;d, called centers, to minimize the mean squared distance from each data point to its nearest center. No exact polynomial-time algorithms are known for this problem. Although asymptotically efficient approximation algorithms exist, these algorithms are not practical due to the extremely high constant factors involved. There are many heuristics that are used in practice, but we know of no bounds on their performance.We consider the question of whether there exists a simple and practical approximation algorithm for k-means clustering. We present a local improvement heuristic based on swapping centers in and out. We prove that this yields a (9+e)-approximation algorithm. We show that the approximation factor is almost tight, by giving an example for which the algorithm achieves an approximation factor of (9-e). To establish the practical value of the heuristic, we present an empirical study that shows that, when combined with Lloyd's algorithm, this heuristic performs quite well in practice. We study exact recovery conditions for convex relaxations of point cloud clustering problems, focusing on two of the most common optimization problems for unsupervised clustering: @math -means and @math -median clustering. Motivations for focusing on convex relaxations are: (a) they come with a certificate of optimality, and (b) they are generic tools which are relatively parameter-free, not tailored to specific assumptions over the input. More precisely, we consider the distributional setting where there are @math clusters in @math and data from each cluster consists of @math points sampled from a symmetric distribution within a ball of unit radius. We ask: what is the minimal separation distance between cluster centers needed for convex relaxations to exactly recover these @math clusters as the optimal integral solution? For the @math -median linear programming relaxation we show a tight bound: exact recovery is obtained given arbitrarily small pairwise separation @math between the balls. In other words, the pairwise center separation is @math . Under the same distributional model, the @math -means LP relaxation fails to recover such clusters at separation as large as @math . Yet, if we enforce PSD constraints on the @math -means LP, we get exact cluster recovery at center separation @math . In contrast, common heuristics such as Lloyd's algorithm (a.k.a. the @math -means algorithm) can fail to recover clusters in this setting; even with arbitrarily large cluster separation, k-means++ with overseeding by any constant factor fails with high probability at exact cluster recovery. To complement the theoretical analysis, we provide an experimental study of the recovery guarantees for these various methods, and discuss several open problems which these experiments suggest.