Variance-Based <I>k</I>-Clustering Algorithms by Voronoi Diagrams and Randomization

Mary INABA; Naoki KATOH; Hiroshi IMAI

Variance-Based k-Clustering Algorithms by Voronoi Diagrams and Randomization

Mary INABA, Naoki KATOH, Hiroshi IMAI

Full Text Views

0

Cite this

Summary :

In this paper we consider the k-clustering problem for a set S of n points p_i=(x_i) in the d-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 of intra-cluster errors over every cluster is used, and as the intra-cluster criterion of a cluster S_j, |S_j|^α-1 Σ_{p_i S_j} ||x_i - ^- x (S_j)||² is considered, where |||| is the L₂ norm and ^- x (S_j) is the centroid of points in S_j, i. e. , (1/|S_j|)Σ_{p_i S_j} x_i. The cases of α=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 α = 1,2 are treated in a unified manner by characterizing the optimum solution to the k-clustering 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 shatter function for the Voronoi diagrams. The primary shatter function is shown to be O(n^O(kd)), 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 in O(n(1/ε)^d) time, which is quite practical and may be used to real large-scale problems such as the color quantization problem.

Publication: IEICE TRANSACTIONS on Information Vol.E83-D No.6 pp.1199-1206

Publication Date: 2000/06/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Algorithms

Cite this

Copy

Mary INABA, Naoki KATOH, Hiroshi IMAI, "Variance-Based k-Clustering Algorithms by Voronoi Diagrams and Randomization" in IEICE TRANSACTIONS on Information, vol. E83-D, no. 6, pp. 1199-1206, June 2000, doi: .
Abstract: In this paper we consider the k-clustering problem for a set S of n points p_i=(x_i) in the d-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 of intra-cluster errors over every cluster is used, and as the intra-cluster criterion of a cluster S_j, |S_j|^α-1 Σ_{p_i S_j} ||x_i - ^- x (S_j)||² is considered, where |||| is the L₂ norm and ^- x (S_j) is the centroid of points in S_j, i. e. , (1/|S_j|)Σ_{p_i S_j} x_i. The cases of α=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 α = 1,2 are treated in a unified manner by characterizing the optimum solution to the k-clustering 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 shatter function for the Voronoi diagrams. The primary shatter function is shown to be O(n^O(kd)), 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 in O(n(1/ε)^d) time, which is quite practical and may be used to real large-scale problems such as the color quantization problem.
URL: https://global.ieice.org/en_transactions/information/10.1587/e83-d_6_1199/_p

Copy

@ARTICLE{e83-d_6_1199,
author={Mary INABA, Naoki KATOH, Hiroshi IMAI, },
journal={IEICE TRANSACTIONS on Information},
title={Variance-Based k-Clustering Algorithms by Voronoi Diagrams and Randomization},
year={2000},
volume={E83-D},
number={6},
pages={1199-1206},
abstract={In this paper we consider the k-clustering problem for a set S of n points p_i=(x_i) in the d-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 of intra-cluster errors over every cluster is used, and as the intra-cluster criterion of a cluster S_j, |S_j|^α-1 Σ_{p_i S_j} ||x_i - ^- x (S_j)||² is considered, where |||| is the L₂ norm and ^- x (S_j) is the centroid of points in S_j, i. e. , (1/|S_j|)Σ_{p_i S_j} x_i. The cases of α=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 α = 1,2 are treated in a unified manner by characterizing the optimum solution to the k-clustering 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 shatter function for the Voronoi diagrams. The primary shatter function is shown to be O(n^O(kd)), 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 in O(n(1/ε)^d) time, which is quite practical and may be used to real large-scale problems such as the color quantization problem.},
keywords={},
doi={},
ISSN={},
month={June},}

Copy

TY - JOUR
TI - Variance-Based k-Clustering Algorithms by Voronoi Diagrams and Randomization
T2 - IEICE TRANSACTIONS on Information
SP - 1199
EP - 1206
AU - Mary INABA
AU - Naoki KATOH
AU - Hiroshi IMAI
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E83-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 2000
AB - In this paper we consider the k-clustering problem for a set S of n points p_i=(x_i) in the d-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 of intra-cluster errors over every cluster is used, and as the intra-cluster criterion of a cluster S_j, |S_j|^α-1 Σ_{p_i S_j} ||x_i - ^- x (S_j)||² is considered, where |||| is the L₂ norm and ^- x (S_j) is the centroid of points in S_j, i. e. , (1/|S_j|)Σ_{p_i S_j} x_i. The cases of α=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 α = 1,2 are treated in a unified manner by characterizing the optimum solution to the k-clustering 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 shatter function for the Voronoi diagrams. The primary shatter function is shown to be O(n^O(kd)), 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 in O(n(1/ε)^d) time, which is quite practical and may be used to real large-scale problems such as the color quantization problem.
ER -