Abstract
In this paper we consider thek-clustering problem for a set S of n points i=(xi) in thed-dimensional space with variance-based errors as clustering criteria, motivated from the color quantization problem of computing a color lookup table for frame buffer display. As the inter-cluster criterion to minimize, the sum on intra-cluster errors over every cluster is used, and as the intra-cluster criterion of a cluster Sj,
Keywords
Cluster analysisVoronoi diagramCluster (spacecraft)Computer scienceData miningVariance (accounting)Set (abstract data type)k-medians clusteringAlgorithmMathematicsFuzzy clusteringArtificial intelligenceCURE data clustering algorithmGeometry
Affiliated Institutions
Related Publications
Approximation schemes for clustering problems
Let k be a fixed integer. We consider the problem of partitioning an input set of points endowed with a distance function into k clusters. We give polynomial time approximation ...
On coresets for k-means and k-median clustering
In this paper, we show the existence of small coresets for the problems of computing k-median and k-means clustering for points in low dimension. In other words, we show that gi...
A local search approximation algorithm for k-means clustering
In k-means clustering we are given a set of n data points in d-dimensional space ℜd and an integer k, and the problem is to determine a set of k points in ℜd, called centers, to...
Better streaming algorithms for clustering problems
We study clustering problems in the streaming model, where the goal is to cluster a set of points by making one pass (or a few passes) over the data using a small amount of stor...
Robust Estimation of a Location Parameter
This paper contains a new approach toward a theory of robust estimation; it treats in detail the asymptotic theory of estimating a location parameter for contaminated normal dis...
Publication Info
- Year
- 1994
- Type
- article
- Pages
- 332-339
- Citations
- 321
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
321
OpenAlex
Cite This
Mary Inaba,
Naoki Katoh,
Hiroshi Imai
(1994).
Applications of weighted Voronoi diagrams and randomization to variance-based <i>k</i>-clustering.
, 332-339.
https://doi.org/10.1145/177424.178042
Identifiers
- DOI
- 10.1145/177424.178042