In this paper, one-dimensional k-medians clustering problem is considered in the context of zero-sum game between players choosing a sample and partitioning it into clusters, respectively. For any sample size n and k > 1, an attainable guaranteed value of the clustering accuracy 0:5n=(2k − 1) (the low value of an appropriate game) is provided for samples taken from the segment [0; 1].
Introduction In data analysis, k-medians clustering problem is regarded as one of the famous center-based metric clustering problems, whose instance can be defined as follows. For a given number k ≥ 1 and a finite sample = (x1; : : : ; xn) taken from a metric space (X; ), it is required to find a partition of Nn = {1; : : : ; n} onto k clusters C1; : : : ; Ck and, for any j-th cluster, to point out an appropriate center cj such that k ∑ ∑ j=1 i∈Cj
n (xi; cj ) = ∑ min{ (xi; c1); : : : ; (xi; ck)} → min : i=1 (1) Equation (1) evidently implies that, for any j, the point cj ∈ Arg min{∑i∈Cj (xi; c) : c ∈ X}; i.e. cj is a median are known numerous approximation results. For instance, in [Kumar et al., 2010], for any fixed k, randomized LTAS with time complexity of O(2(k=")O(1) · dn) is proposed. On the basis of the famous coresets technique, in [Har-Peled and Mazumdar, 2004], RPTAS with polynomially depending on the number of clusters k time complexity bound O(n + (k log n)O(1)), where = exp(O((1 − log ")=")d−1) is proposed. For d = 1, k-medians problem is polynomially (and very efficiently) solvable. To date, the most efficient exact algorithm with time complexity O(n log n + kn) is proposed in [Grønlund et al., 2017].
Among others, the setting, where it is required to obtain a guaranteed accuracy of clustering for a fixed
number of clusters k and an arbitrary sample, is valuable
Problem Statement and the Main Result We consider the following two-player zero-sum game induced by k-medians clustering. There are two players placing points in the unit segment of the real line. Strategies of the first player are samples = (x1; : : : ; xn), xi ∈ [0; 1] of some given size n. Strategies of the second one are k-tuples = (c1; : : : ; ck), ci ∈ [0; 1]. The payoff function F ( ; ) = ∑in=1 min{|xi − c1|; : : : ; |xi − ck|}. Goals of the first and the second players are to find the lower and the higher v∗(n; k) = v∗(n; k) = sup ∈[0;1]n inf ∈[0;1]k inf ∈[0;1]k
F ( ; ) sup F ( ; ) ∈[0;1]n values of the game, respectively.
It is easy to verify that, for any k > 1 and n > 0, the game has no value, i.e. v∗(n; k) < v∗(n; k). For many reasons arising from applications in data analysis, combinatorial optimization, and computational geometry, it is important to have an upper bound for v∗(n), which means the guaranteed accuracy of k-medians clustering of an appropriate n-points sample. Although, v∗(n; k) can obviously be taken as an upper bound, for large values of n it is imprecise and should be replaced with more accurate one.
In this paper, we propose an attainable upper bound B(n; k) for v∗(n; k). Actually, to any n > 0, k > 1, and ∈ [0; 1]n, we show how to assign an appropriate k-tuple = (c1; : : : ; ck), i.e. how to construct a clustering C1; : : : ; Ck with medians c1; : : : ; ck, such that inf ∈[0;1]k
F ( ; ) ≤ F ( ; ) ≤ B(n; k):
(i) For any k > 1, n > 0, and sample (c1; : : : ; ck), cj ∈ [0; 1], j ∈ Nk, such that = (x1; : : : ; xn), xi ∈ [0; 1], i ∈ Nn, there exists the k-tuple
F ( ;
n ) ≤ 2(2k − 1) : = (2) (ii) For any k > 1, there is n˜ = n˜(k) such that, for all n > n˜, bound (2) is attained at some sample = (k; n).
Postponing the rigorous proof to the forthcoming paper, we restrict ourselves to some suggestive thoughts. To put it simple, we consider the case of k = 2. 3
Proof Sketch for k = 2 We start with the following simple upper bound 3.1
It can be assumed that the second player always adheres to the following strategy. He splits the segment [0; 1] onto two equal parts and put c1 and c2 at the centers of each part as it is shown in Fig. 1 Obviously, in this case, for any x ∈ [0; 1], min{|x − c1|; |x − c2|} ≤ 1=4. Therefore, regardless of the choice = (x1; : : : ; xn) of the first player, ∑n
i=1 min{|xi − c1|; |xi − c2|} ≤ n=4, i.e. B(n; 2) ≤ n=4. Since, to complete the first point of the proof (for the considered case k = 2), we need to show that B(n; 2) ≤ n=6, we need further improvements. Φ( ) = min ∑ |xi − c1| + ∑ |xi − c2| : C1 ∪ C2 = Nn
= min − i∈C2 ⌊m1=2⌋ ∑ i=1 xi + m1 ∑ i=⌈m1=2⌉+1
xi − Hereinafter, without loss of generality, we assume that any sample = (x1; : : : ; xn) contains points xi in ascending order. Moreover, we assume that any cluster C = {i1; : : : ; im} ⊂ Nn inherites this property, i.e. xi1 ≤ : : : ≤ xim . Then, for the median c of the cluster C we have m ∑ |xil − c| = ⌊m=2⌋ ∑ (c − xil ) + l=1 l=1 m ∑ l=⌈m=2⌉+1
⌊m=2⌋ (xil − c) = − ∑ xil + l=1 m ∑ l=⌈m=2⌉+1 xil : Therefore, for a given sample , Φ( ) = inf =(c1;c2) F ( ; ) depends on choice of partitions C1 ∪ C2 = Nn ultimately and obeys the equation Thus, v∗(n; 2) = sup ∈[0;1]n Φ( ) is an optimum value of linear program (4) v∗(n; 2) = max u s:t: } ⌊m2=2⌋ ∑ i=1 m2 ∑ i=⌈m2=2⌉+1 xi+m1 + xi+m1 : m1 + m2 = n
(3) : ⌊m1=2⌋ − ∑ xi + i=1 m1 ∑ i=⌈m1=2⌉+1 0 ≤ x1 ≤ : : : ≤ xn ≤ 1: xi − ⌊m2=2⌋ ∑ xi+m1 + i=1 m2 ∑ i=⌈m2=2⌉+1 xi+m1 ≥ u; (m1 + m2 = n); (4) Further, guided by the symmetry argument, we can reduce the number of variables (and also, the number of constraints) in problem (4) by half. Indeed, suppose, ′ = (x′1; : : : ; x′n) is an optimal solution of (4). Then, by symmetry, ′′ = (1 − x′n; : : : ; 1 − x′1) is an optimal solution of (4) as well. Convexity of the optimal set2 of (4) implies that = ( ′ + ′′)=2, each whose entry is defined by the formula xi = (1 + x′i − x′n+1−i)=2 is also an optimal solution. Since xi + xn+1−i = 1, hereinafter, we reduce the number of variables to ⌊n=2⌋. Moreover, for odd n, x⌈n=2⌉ = 1=2.
To show that B(n; 2) ≤ n=6, we study all cases for (n mod 6).
Case n = 6t: Consider the constraint of (4) defined by m1 = 2t and m2 = 4t.
t 2t − ∑ xi + ∑ i=1 i=t+1 3t ∑ i=2t+1 xi − xi − 3t ∑ (1 − xi) + i=2t+1 2t ∑(1 − xi) ≥ u; i=1 which is equivalent to u + 2 ∑t
i=1 xi ≤ t. Since all xi ≥ 0, u ≤ t = n=6, and we are done.
Case n = 6t + 1: Here, we consider two constraints of (4), defined by m1 = 2t, m2 = 4t + 1 and m1 = 2t + 1, m2 = 4t, respectively. They are
t 2t − ∑ xi + ∑ i=1 i=t+1 xi − 3t ∑ 2t ∑(1 − xi) ≥ u i=1 2The set of optimal solutions and which implies In case n = 6t + 2 we take constraints defined by m1 = 2t + 1; m2 = 4t + 1 and m1 = 2t; m2 = 4t + 2: Transformed they imply
t 2t+1 − ∑ xi + ∑ xi − i=1 i=t+2 t 2t − ∑ xi + ∑ xi − i=1 i=t+1 3t+1 ∑ xi − i=2t+2 3t+1 ∑ xi − i=2t+1 3t+1 2t ∑ (1 − xi) + ∑(1 − xi) ≥ u i=2t+2 i=1 3t+1 2t+1 ∑ (1 − xi) + ∑ (1 − xi) ≥ u: i=2t+2 i=1 t u + 2 ∑xi − x2t+1 ≤ t i=1
t u + 2 ∑xi + 2x2t+1 ≤ t + 1; i=1
t 3u + 6 ∑ xi ≤ 3t + 1 i.e. u ≤ t + 1=3 = n=6:
i=1 Case n = 6t + 3 is similar to the case n = 6t. Here, to obtain the desired bound, it is enough to consider the single constraint defined by m1 = 2t + 1 and m2 = 4t + 2
t 2t+1 − ∑ xi + ∑ xi − i=1 i=t+2 3t+1 ∑ i=2t+2
1 xi − 2 − i=2t+2 3t+1 2t+1 ∑ (1 − xi) + ∑ (1 − xi) ≥ u: i=1 (5) Being transformed, (5) becomes which implies u ≤ t + 1=2 = n=6.
t u + 2 ∑ xi + xt+1 ≤ t + 1=2;
i=1 In case n = 6t + 4 we convolve again two appropriate constraints defined by m1 = 2t + 1; m2 = 4t + 3 and m1 = 2t + 2; m2 = 4t + 2 t 2t+1 − ∑ xi + ∑ xi − i=1 i=t+2 t+1 2t+2 − ∑ xi + ∑ xi − i=1 i=l+2 3t+2 ∑ xi − i=2t+2 3t+2 ∑ xi − which, after the equivalent transformation give the subsystem which, being convolved, gives us Now, we show that for any n ≥ 12 inequality (2) is tight. Consider the following configuration given by locations p1; : : : ; p5 Place n = 4⌊ n4 ⌋ + { 4 } points at the locations p1; : : : ; p5 with multiplicities presented at Fig. 3 n
Since n ≥ 12, the multiplicities of points located at p1; p2; p4; and p5 are at least 3 and at most 3 points are located at p3. By the symmetry of the sample obtained, there are two best options to partition it into two clusters C1 = {1; : : : ; ⌊n=4⌋}, C2 = {⌊n=4⌋ + 1; : : : ; n} and C1 = {1; : : : ; 2⌊n=4⌋}, C2 = {2⌊n=4⌋ + 1; : : : ; n} (see Fig.4). Let us calculate the cost F ( ; ) for each option. In the first case
F ( ; ) = ∑
|xi − c2|; i∈C2 where c2 = p4 (since n > 12). Therefore,
F ( ; ) = : Consider the second case. Here, again c2 = p4. Therefore,
F ( ; ) = ; i.e. Theorem is completely proved so as point (ii).