We consider the problem of partitioning a finite set of Euclidean points into two clusters minimizing the sum over both clusters the weighted sums of the squared intracluster distances from the elements of the clusters to their centers. The center of one of the clusters is unknown and determined as the average value over all points in the cluster, while the center of the other cluster is the origin. The weight factors for both intracluster sums are the cardinalities of the corresponding clusters. In this work, we present a short survey on the results for this problem and a new result: a 2-approximation algorithm.
|C| ∑ ∥y − y(C)∥2 + |Y \ C| ∑ ∥y − y(Y \ C)∥2 −→ min ; y2C
y2YnC where y(C) = jC1j ∑y2C y and y(Y \ C) = jC1j ∑y2YnC y are the geometric centers (centroids) of both clusters C and Y \ C.
The main difference between the problem under study and this problem is that in the considered problem the center of one of the clusters is fixed in the origin (without loss of generality). It is obvious, that the considered problem and the Weighted variance-based 2-clustering problem are not equivalent and so both of them need an individual study. The importance of the problem for applications motivates to continue researches, e.g. importance for geometric problems, approximation problems, statistical problems of joint evaluations and testing hypotheses by nonuniform samples, problems of Data clustering, Data mining, Machine learning, Big data, applied problems in technical and medical diagnostics, etc. 2
Cardinality-weighted Variance-based 2-clustering with Given Center Problem 1. Given a set Y = {y1; : : : ; yN } of points from Rq and a positive integer M . Find a partition of Y into two non-empty clusters C and Y \ C such that
F1(C) = |C| ∑ ∥y − y(C)∥2 + |Y \ C| ∑ ∥y∥2 −→ min ; y2C y2YnC where y(C) = 1 ∑y is the geometric center (centroid) of C and such that |C| = M .
jCj y2C
Problem 1 is strongly NP-hard [Kel’manov & Pyatkin, 2015, Kel’manov & Pyatkin, 2016]. Therefore, by [Garey & Johnson, 1979], there are neither exact polynomial-time nor exact pseudopolynomial-time algorithms for this problem, unless P=NP.
Despite of this, a pseudopolynomial algorithm for the special case of Problem 1 exists. It proposed in [Kel’manov & Motkova, 2016a] and finds an optimal solution in the case of integer components of the points in the input set and fixed space dimension.
Step 1. Construct G — a multidimensional cubic uniform in each coordinate grid of size 2D with the distance M1 between the nodes and the center at the origin, and D is the maximal modulus of the coordinates of input points.
gx(y) = (2M − N )∥y∥2 − 2M ⟨y; x⟩ ; y ∈ Y; subset BxA1 . Put CA1 = BxA1 .
Output: The set CA1 .
Theorem 1. Assume that the elements of Y have integer values from the interval [−D; D]. Then algorithm
In the case of fixed space dimension q the algorithm is pseudopolynomial.
In [Kel’manov & Pyatkin, 2015, Kel’manov & Pyatkin, 2016] it is also shown that for Problems 1 there does not exist any fully polynomial time approximation scheme (FPTAS), unless P=NP. In [Kel’manov & Motkova, 2016b] was proposed such approximation scheme for a special case of the Problem 1 when the space dimension q is fixed.
Step 1. Compute the values gy(z); z ∈ Y; using formula (2); find a subset By ⊆ Y with M smallest values gy(z), compute F (By) using formula (1).
Step 2. If F (By) = 0, then put CA3 = By; exit.
Step 3. Compute H = H(y) = M1 √F1(By) and h = h(y; ") = M1 √ 2q" F1(By).
Step 4. Construct the lattice G(y; h; H + h=2) using formula
G(y; h; H + h=2) = {d ∈ Rq| d = y + h · (i1; : : : ; iq); ik ∈ Z; |hik| ≤ H + h=2; k ∈ {1; : : : ; q}}: Step 5. For each node x of the lattice G(y; h; H + h=2) compute the values gx(y), y ∈ Y, using formula (2) and find a subset Bx ⊆ Y with M smallest values gx(y). Compute F1(Bx) using formula (1), remember this value and the set Bx.
Step 6. If F (Bx) = 0, then put CA2 = Bx; exit. (1) (2) qN 2 (√ 2"q + 2
time.
Step 7. In the family {Bx| x ∈ G(y; h; H + h=2); y ∈ Y} of candidate sets that have been constructed in Steps
Theorem 2. For any fixed " > 0 algorithm A2 finds a (1 + ")-approximate solution of Problem 1 in ( )q)
Corollary 1. In the case when the dimension q of space is bounded by a constant value, this algorithm is an FPTAS.
Later in [Kel’manov et al., 2017] was proposed the similar approximation scheme with the same time complexity for the generalization of Problem 1 in which the weight factors are given as input (positive real numbers). Also there was presented an improved algorithm that allows to find (1 + ")-approximate solution of generalized problem in O (√qN 2( 2e )q=2(√ 2" + 2)q) time. In the case when the dimension q of space is bounded by a constant value, this algorithm is also an FPTAS. In addition, improved algorithm remains polynomial even when the dimension q of the space is bounded by the value C log N , where C is the positive constant. It is clear that in this case algorithm implements a PTAS with time complexity N O(log 1" ).
The last proposed algorithm for Problem 1 until this moment is a 2-approximation algorithm. It was proposed in [Kel’manov & Motkova, 2017] and allows us to find an approximate solution in the polynomial time.
Step 1. Compute the values gy(z); z ∈ Y, using formula (2); find an M -elements subset By ⊆ Y with the smallest values gy(z), compute F1(By) using formula (1).
Step 2. If F1(By) = 0, then put CA2 = By; exit.
Step 3. In the family {By|; y ∈ Y} of candidate sets that have been constructed in Steps 1–2, choose as a solution CA3 the set Bx, for which F1(Bx) is minimal.
Two examples of an input set (of 1000 points) and admissible solutions (i.e. 300-elements subset By) found by Algorithm A3 at step 1 are presented at Fig.1 (a) and (b).
(a) Let us substuntiate this algorithm below. Lemma 3. Let
The following two lemmas are well known.
Lemma 1. For an arbitrary point x ∈ Rq, a finite set Z ⊂ Rq and z = jZ1 j ∑z2Z z (z is the centroid of Z), it is true that ∑ ∥z − x∥2 = ∑ ∥z − z∥2 + |Z| · ∥x − z∥2 : z2Z
z2Z
Lemma 2. For a finite set Z ⊂ Rq, if a point u ∈ Rq is closer (in terms of distance) to the centroid z of Z than any point in Z, then ∑ ∥z − u∥2 ≤ 2 ∑ ∥z − z∥2 : z2Z
z2Z S(C; x) = |C|∑ ∥y − x∥2 + |Y \ C| ∑ ∥y∥2; C ⊆ Y; x ∈ Rq : y2C y2YnC Then the next statements are true:
(1) for any nonempty fixed set C ⊆ Y the minimum of the function S(C; x) over x ∈ Rq is reached at the point y(C) = 1 ∑y;
jCj y2C (2) if |C| = M = const, then for any fixed point x ∈ Rq the minimum of function S(C; x) over C ⊆ Y is reached at the subset Bx that consists of M points of the set Y, at which the function (2) has the smallest values.
Proof. The first statement follows from Lemma 2 and the definition of the functions S and F . Since |Y| = N and |C| = M , the second statement follows from the next chain of equalities:
S(C; x) = M ∑ ∥y − x∥2 + (N − M ) ∑
∥y∥2 = M ∑ ∥y∥2 − 2M ∑ ⟨y; x⟩ + M 2∥x∥2+ y2C y2YnC y2C y2C (N − M ) (∑ ∥y∥2 − ∑ ∥y∥2) = ∑{(2M − N )∥y∥2 − 2M ⟨y; x⟩} + M 2∥x∥2 + (N − M )∑ ∥y∥2 : y2Y y2C y2C y2Y
Lemma is proved.
Theorem 3. An Algorithm A3 finds a 2-approximate solution of Problem 1 in time O (qN 2): Proof. Let C be an optimal subset and t = arg min ||y − y(C )||2 be a point from a subset C that is the y2C closest to its centroid.
Step-by-step, the algorithm goes through every points y of the set Y. Since t ∈ Y, a permissible solution also will be formed for the point t: the subset Bt, defined by Lemma 3 (if x = t).
Besides, a value F (Bt) of objective function for the Problem 1 will be calculated. For this value we have this inequalities from definitions of the functions F and S and Lemma 3 and a definition of the point t: (3) (5) Applying Lemma 2 to the set Z = C and the point u = t, we have
F (Bt) = Sy(Bt)(Bt) ≤ St(Bt) ≤ St(C ): ∑ ||y − t||2 ≤ 2 ∑ ||y − y(C )||2: y2C y2C Using this inequality and definition (2), we find an estimation for a right part of (3)
St(C ) = M ∑ ||y − t||2 + (N − M ) ∑ ||y||2 y2C
y2YnC Combining (3) and (4), we have
F (Bt) ≤ 2F (C ): y2C y2YnC From Step 3 we know that the algorithm finds a solution of Problem 1 in the next form:
Finally, (5) and (7) implies an estimate
Let us consider the case when at Step 2 of the algorithm the condition F (By) = 0 is executed for some input point y ∈ Y. For every subset C ⊆ Y inequality F (C) ≥ 0 is correct, so the subset CA = By ⊆ Y is an optimal solution of Problem 1. Inequality (8) is correct for this solution too. It means that a subset CA is a 2-approximation solution of Problem 1.
Let us estimate the time complexity of the algorithm. At Step 1 we need no more than O(qN ) operations to
calculate values gy(z). Searching of M the smallest elements in the set of N elements requires O(N ) operations
As Steps 1 and 2 are executed N times, total time complexity of this steps is O(qN 2). Time complexity of Step 3 is estimated by value O(N ). So, the time complexity of the algorithm is O(qN 2). Theorem 3 is proved.
Two examples of an input set (of 1000 points) and 2-approximate solutions found by Algorithm A3 are presented at Fig.2 (a) (i.e. 400-elements subset CA) and (b) (i.e. 600-elements subset CA).
CA = arg min F (By):
y2Y F (CA) ≤ F (Bt): F (CA) ≤ 2F (C ): (6) (7) (8) (a) (b) 3
In this work, we presented a short survey on the results for the problem of 2-partitioning of points in Euclidean space into two clusters. Also we presented the new result: a 2-approximation algorithm.
It seems important to continue studying and the issue of great interest is the substantiation of randomized algorithms for this problem with linear or sub-linear time complexity. The research for algorithms A1 and A2 was supported by the Russian Foundation for Basic Research, Projects 16-31-00186, 16-07-00168. Research for algorithm A3 was supported by the Russian Science Foundation, Project 16-11-10041.