Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering: (extended abstract)

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 clusterSj , a -1pi∈Sjxi-x Sj ² is considered, where ˙ is the L2 norm and xSj is the centroid of points in Sj, i.e., 1/Sjpi∈Sjxi. The cases of a=1,2 correspond to the sum of squared errors and the all-pairs sum of squared errors, respectively. The k-clustering problem under the criterion with a=1,2 are treated in a unified manner by characterizing the optimum solution to the kclustering problem by the ordinary Euclidean Voronoi diagram and the weighted Voronoi diagram with both multiplicative and additive weights. With this framework, the problem is related to the generalized primary shutter function for the Voronoi diagrams. The primary shutter function is shown to be On^Okd, which implies that, for fixed k, this clustering problem can be solved in a polynomial time. For the problem with the most typical intra-cluster criterion of the sum of squared errors, we also present an efficient randomized algorithm which, roughly speaking, finds an ∈–approximate 2–clustering inOn1/∈^d time, which is quite practical and may be used to real large-scale problems such as the color quantization problem.

REFERENCES

• 1: T. Asano , B. Bhattacharya , M. Keil , F. Yao, Clustering algorithms based on minimum and maximum spanning trees, Proceedings of the fourth annual symposium on Computational geometry, p.252-257, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73419]
• 2: E. Boros , P. L. Hammer, On clustering problems with connected optima in Euclidean spaces, Discrete Mathematics, v.75 n.1-3, p.81-88, 1989 [doi>10.1016/0012-365X(89)90080-0]
• 3: Vasilis Capoyleas , Günter Rote , Gerhard Woeginger, Geometric clusterings, Journal of Algorithms, v.12 n.2, p.341-356, June 1991 [doi>10.1016/0196-6774(91)90007-L]
• 4: Tomás Feder , Daniel Greene, Optimal algorithms for approximate clustering, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.434-444, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62255]
• 5: Johann Hagauer , Günter Rote, Three-Clustering of Points in the Plane, Proceedings of the First Annual European Symposium on Algorithms, p.192-199, September 30-October 02, 1993
• 6: S. Hasegawa: A study on e-net and ~-approzimation. Master's Thesis, Department of Information Science, University of Tokyo, 1993.
• 7: S. Hasegawa, H. imai, M. Inaba, N. Katoh and J. Nakano: Efficient algorithms for variance-based k-clustering. Proceedings o/the First Pacific Conference on Computer Graphics and Applications, World Scientific, 1993, pp.75-89.
• 8: Susumu Hasegawa , Hiroshi Imai , Masaki Ishiguro, Epsilon-Approximations of k-label Spaces, Proceedings of the 4th International Workshop on Algorithmic Learning Theory, p.288-299, November 08-10, 1993
• 9: Paul Heckbert, Color image quantization for frame buffer display, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.297-307, July 1982
• 10: John Hershberger, Minimizing the sum of diameters efficiently, Computational Geometry: Theory and Applications, v.2 n.2, p.111-118, Oct. 1992 [doi>10.1016/0925-7721(92)90028-Q]
• 11: M. Ishiguro: Evaluation o/combinatorial complezity /or hypothesis spaces in learning theory with applications. Master's Thesis, Department of Information Science, University of Tokyo, 1994.
• 12: N. Katoh , T. Ibaraki, A parametric characterization and an &egr;-approximating scheme for the minimization of a quasiconcave program, Discrete Applied Mathematics, v.17 n.1-2, p.39-66, May 1987 [doi>10.1016/0166-218X(87)90006-0]
• 13: B. W. Kernighan and S. Lin: An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, Vol.49, No.2 (1970), pp.291- 307.
• 14: N. Megiddo and K. J. Supowit: On the complexity of some common geometric location problems. SIAM Journal on Computing, Vol.13 (1984), pp. 182-196.
• 15: S. J. Wan , S. K. M. Wong , P. Prusinkiewicz, An algorithm for multidimensional data clustering, ACM Transactions on Mathematical Software (TOMS), v.14 n.2, p.153-162, June 1988 [doi>10.1145/45054.45056]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

General Terms:
Algorithms, Theory, Verification