Coresets for $k$-mean clustering of segments

Authors: David Denisov, Dan Feldman, Shlomi Dolev, Michael Segal
Primary area: optimization
Keywords: Clustering; $k$-means; Segment clustering; Non-convex optimisation; Coresets

Abstract:
The $k$-means of a given set $\mathcal{S}\subseteq \mathbb{R}^d$ of $n$ segments is a set $X\subseteq \mathbb{R}^d$ of $|X|=k$ centers which minimizes their sum of squared distances $D(\mathcal{S},X):=\sum_{S\in \mathcal{S}}\min_{x\in X}D(S,x)$.
Here, the distance $D(S,x)$ between a segment $S$ and a point $x$ is the integral of its distances $\int_{s\in S}\|p-x\|$ over each point on the segment.
More generally, the farthest $m$ input points (outliers) may be ignored, other distance functions may be used, such as M-estimator or non-squared, and each distance may be multiplied by a function that depends on the size of its cluster, say, to obtain balanced clustering.
For a given $\varepsilon>0$, an $\varepsilon$-coreset $C\subseteq S$ for all these problems is a weighted subset $C\subset S$, that approximates $D(S,X)$ up to $1\pm\varepsilon$ multiplicative factor for every set $X\subseteq\mathbb{R}^d$ of (possibly weighted) $k$ centers. Such a coreset enables handling streaming, big, distributed input in parallel using existing techniques.
We suggest the first coreset construction that, with high probability, returns an $\varepsilon$-coreset $C$ for \emph{any} input set $\mathcal{S}$ of segments.
For constant $k,\varepsilon$, the size of the coreset is $|C|\in O \big(\log^2(n)\big)$ and is computed in time $O(nd)$.
Experimental results and real-time video tracking application demonstrate the applicability of our algorithm, the latter demonstrates that our method supports vectorized segments.

Decision: reject
Reviewer scores: 1, 3, 5, 3

Reviews and discussion:
<thread>
creation date:
1730125261494

thread_type:
official_review

<thread_object>
creator: reviewer_npxv

<content>
summary:
This paper introduces a new clustering problem called segment clustering, and presents a reduction from the coreset construction for this problem to that of traditional (vanilla) clustering. For constant $k$ and $\varepsilon$, the coreset size achieved is $O(\log^2(n))$, where $n$ denotes the number of segments. The paper also extends the segment clustering problem to a more general setting by transforming the dataset of $n$ segments into $n$ well-bounded convex shapes and provides an algorithm to construct a coreset.

strengths:
The topic of constructing a coreset for clustering problems is relevant. It is good to provide an algorithm with theoretical guarantee.

weaknesses:
The motivation of the segment clustering problem is unclear. The paper does not provide applications or real-world scenarios for the studied problem.

The result is not very strong. The paper compares to the previous discrete result given by Har-Peled, but the size bound of $O(\log^2(n))$  does not improve over the previous bound of $O(\log n / \varepsilon^2)$ by Har-Peled.

The technique is not that interesting. To my understanding, it employs uniform sampling on each segment separately to obtain an intermediate set, which is then fed into Feldman's coreset construction method.

questions:
- What motivates your investigation of the segment clustering problem? Also, why consider this coreset definition for the segment clustering problem? There is other choice, e.g., selecting a set of segments.

- Why is the distance function between a segment and a point defined as an integral? Is there a practical reason for choosing this formulation?

- The notion of $k$-segmentation in your cited works (Jubran et al., 2021 and Rosman et al., 2014) appears to differ from the one used in this study. Could you clarify the distinctions?

Minor issues:
- **Line 58 to Line 64**: The reference to "the right figure" in the text actually corresponds to the left figure, and "the left figure" corresponds to the right figure.

- **Line 287 to Line 294**: The reference to "Top right" in the text actually corresponds to the top left figure, and "Top left" corresponds to the top right figure. The same issue occurs with "Bottom left" and "Bottom right," which are also swapped.

- **Line 828 to Line 908**: The proof of Lemma B.2 employs notations that are only defined later in Theorem B.3, making the proof difficult to follow.

- **Line 1009, Inequality (43)**: Since the function $h$ is non-decreasing, we have $\min_{x \in I\_{j-1}} h(i) - \min\_{x \in I_j} h(i) \leq 0$. Thus, the inequality as stated is incorrect.

- **Line 1047**: The expression $\text{lip}\_{p'}( D(p', \tilde{x}) + D(l(x), l(\tilde{x})))$ should be corrected to $\text{lip}_{p'}(D(p', l(\tilde{x})) + D(l(x), l(\tilde{x})))$.

- **Line 1060 to Line 1063**: Change $\text{lip}\_{p'}(D(p', l(x)))$ to $\text{lip}_{p'}(D(p', l(\tilde{x})))$.

- **Line 1163**: The function should be written as $f(x) = D(Q, l(x))$ instead of $f(i) = D(Q, l(x))$. 

These revisions would enhance the clarity and accuracy of the manuscript.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730434695733

thread_type:
official_review

<thread_object>
creator: reviewer_tnfn

<content>
summary:
This paper studies a coresets for a version of segment k-means. The input is a set of line segments in R^d, and the goal is to find a set of k center points in R^d, such that the sum of (squared) distance to the distance D is minimized, where for a segment s and center set C, D(s, C) := \int_0^1  \min_{c \in C} \|s(x) - c\| dx. This is different to the standard distance from a point to a segment, and it takes an integration.

The main result is a coreset of size roughly poly(1 / eps) k^k log^2 n, and a generalization to multi-dimensional shapes. The main idea is to do a uniform sample/discretization for each line segments and take the union of them, which yields a point set, then take a coreset for the point set that preserves the distance D. The first coresets for line segments are only of size poly(k), but the second step needs to use an existing algorithm from Feldman & Schulman (2012), which is of size k^k.

Experiments are conducted on both synthesized and real datasets, and compared with several baselines including a previous coreset for lines (instead of segments). The experiments indicate that the proposed algorithm outperforms the baselines.

strengths:
- The suggested clustering problem is well motivated and has fundamental difference to a similar line segment problem

- The framework seems to be general and not restricted to segment clustering

weaknesses:
- Both the coreset size and running time has a dependence on k^k

- One of the main technical step is a black-box use of Feldman & Schulman (2012), which limits the technical contribution

- The writing needs to be improved, especially the introduction. For instance, I find little discussion of the motivation of the problem, and the introduction for coresets seem to be very brief (and makes it hard to understand for non-experts)

questions:
- I think the title should say “k-means” instead of “k-mean”?

- Line 40, “union over every pair (C, W)” — this is not really a union, and probably you should say “the set/collection of all pairs (C, w)”

- Line 69, you said the coreset is a weighted subset of input points — It seems the input is a set of segments, so the sentence does not make perfect sense (and one needs to explain)

- Line 127, is t a function of r? Also, why do you say big-O of t? I think you should simply say the running time is t

- Line 138 - 139, shouldn’t it be {(S \cap \beta) \mid \beta \in B} (you missed the {})?

- Line 152 - 155, here you used D( (C, w’), p ), while in your Definition 2.3 the order of the arguments are different, which is D(p, (C, w))

- Definition 2.7, I suppose S is a subset in R^d? But this is not stated

- Line 1 of Algorithm 1, you said r is as in Definition 2.3. However, that r is with respect to a function and not a universal constant. So where is such a function in the context of Algorithm 1? In hindsight, I find this is stated in line 208 - 209, so I think you need to reorganize the description

- Line 3 of Algorithm 2, I’m not sure about the comment “see Definition 2.3” — Def 2.3 is about the distance function D, but here in the algorithm it is about the coreset

- General question: how do we set the value of d^*?

- General question: you said you focus on k-means, but where does the “square” of k-means objective appear in your definitions? I only see generic definition of D, and the sum of D is not squared?

- Line 369, you said you can skip Algorithm 2 and only use Algorithm 1 + known k-means algorithm — I don’t think this theoretically works, because your objective is not point k-means (and is a sophisticated k-means over segments, even if you reduce to a subset of points for the approximation)

- Line 379, I’m not sure the way you evaluate “OPT”, at least this is misleading — isn’t it still through your coreset? In my mind one needs to use a more direct brute-force for OPT

- FIg 3, middle row, I don’t understand the plot. Why there are both vertical and horizontal segments? Shouldn’t it be a line plot?

- FIg 3, what’s “Approx”? Is this a baseline? I don’t find where it was introduced
</content>
</thread_object>

</thread>
<thread>
creation date:
1730436694808

thread_type:
official_review

<thread_object>
creator: reviewer_wiuy

<content>
summary:
The paper discusses the k-means type clustering problem for line segments. The distance of a point x from a line segment S is defined as D(S, x) = \int_{s \in S} ||p-x||ds. Given this distance measure, the problem is finding k centers to minimize the sum of distances. Here, partial assignment of contiguous pieces of a line segment is allowed. The main contribution of the paper is to suggest breaking a line segment into small pieces, replacing them with weighted points, and then using the coreset construction of Feldman and Schulman to obtain a weighted set of points such that a good center set for these points will also be a good center set for the line segments. Experimental results are given with real data sets.

strengths:
Defines a new problem and extends the notion of coreset object to this problem.

weaknesses:
- The problem is not well-motivated before starting the technical section. Even the experimental section does not discuss why this problem is relevant in the context of the experiments performed. Why is this problem the right mathematical problem in the context of the experiments conducted?
- The results in the paper are not surprising and obtained using a straightforward application of Feldman and Schulman.

questions:
Question related to motivation is very important and has been mentioned above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730699023459

thread_type:
official_review

<thread_object>
creator: reviewer_uny9

<content>
summary:
Assume L as a set of n segments. The goal of k-mean clustering of segments is to find a weighted set (C, w) of size |C| = k that minimize \sum_{l \in L} loss(l, (C, w)), where loss(l, (C, w)) = \int_0^1 D( l(x), (C, w) ) dx. A coreset is a weighted set of small size that can approximate the loss function of any solution. For the k-mean clustering of segments, an (epsilon, k)-coreset for a segment l is a weighted set (S, w) such that for any weighted set (C, w'), we have | loss(l, Q) - \sum_{p \in S} w(p) D(p, Q) | <= epsilon loss (l, Q). Furthermore, (S, w) is an (epsilon, k)-coreset for a set L of n segments if it is an (epsilon, k)-coreset for all l in L.
In this paper, the author propose a deterministic algorithm SEG-CORESET that returns an (epsilon, k)-coreset for a segment l. In SEG-CORESET, the coreset (S, w) consists of all the epsilon' equally spaced points on l, where epsilon' = \ceil{ 4k (20k)^{r+1} / epsilon }. Then, they propose their second algorithm CORESET that generates an (epsilon, k)-coreset (P, w) for L. P has size k' log^2m / epsilon^2 * O(d* + log (1/delta)), where d* is the VC-dimension, m = 8nk (20k)^{r+1} / epsilon, and k' \in (k+1)^{O(k)}. In the CORESET algorithm, they first apply SEG-CORESET to generate an (epsilon, k)-coreset for every l in L, and then send them as the input of Feldman's coreset generation framework.
Furthermore, they generalize their result to convex shapes, and apply experiments to evaluate the quality of their approximation compared to the other methods.

strengths:
The authors introduce a new problem, k-mean clustering of segments, in this paper, which may have its own interest in the future. They also proposed novel algorithm that generate coreset of small size, which transfer the problem into a transitional weighted k-means problem, which makes the problem easier to solve. They provide both rigor proof and empirical evaluation for their algorithm.

weaknesses:
This paper has a poor presentation. It abuse the notation which makes it more confused. For example, it uses loss(l, (C, w)) as its loss function and D as the distance function in section 2, but uses D as the loss function in the abstract. There are also many typos in the paper. For instance, "right figure" should be "left figure" and "left figure" should be "right figure" in the notation of figure 1. Also, \sum_{s \in S} w(s) D( (C, w'), p) should rather be \sum_{s \in S} w(s) D( (C, w'), s) in the claim (i) in Theorem 2.5. Furthermore, it claims SEG-CORESET would output an (epsilon, k)-coreset with probability at least 1-delta, but SEG-CORESET is a deterministic algorithm and the returned set would always be an (epsilon, k)-coreset. The failure probability of their algorithm CORESET comes from Feldman's coreset generation framework rather than their SEG-CORESET algorithm.
It also seems that this paper has a low novelty. Since they use Feldman's coreset generation framework to generate a coreset of the union of coresets generated by SEG-CORESET, it seems that the novelty of this paper would focus on their novel algorithm SEG-CORESET. However, SEG-CORESET generates the coreset that consists of all the epsilon' equally spaced points on segment l. Using equally spaced points on a segment to approximate the segment itself does not seem to be very novel. If such technique is really very novel, the authors should present the novelty more clearly.
Furthermore, the experiments do not seems to be very persuasive. They compare their algorithm to the algorithm proposed by Feldman's paper. However, Feldman's paper studies about k-mean for lines problem, whose goal is to find k centers that minimize the distance be the lines and the centers, which is not the k-mean clustering of segments problem proposed by this paper. Since the algorithm from Feldman's paper focuses another problem, it is unfair to compare the performance of the authors' algorithm to Feldman's algorithm on k-mean clustering of segments problem. Therefore, the experiments are not very persuasive.
In addition, the k-mean clustering of segments problem is not the previous problem like k-mean for lines problem studied by Feldman. The authors do not mention whether this is a novel problem or has already been studied by other researchers before in the paper. The authors should present the importance of this problem if it is a new problem.

questions:
1. Is k-mean clustering of segments problem a new problem? If this problem has been studied before, please present the related research in the paper. If this problem is a new problem, please present its importance.
2. Why the idea of using equally spaced points on a segment to approximate the segment itself is novel in this paper?
3. Why do you compare your algorithm with Feldman's algorithm, which focus on another problem?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732536751595

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Response to the most notable questions/comments of the reviewers

comment:
We thank the reviewers for their review and detailed feedback.

We will fix the typos/mistakes the reviewers pointed out and review the manuscript to reduce such mistakes.
Additionally, we will work on the writing, especially the problem motivation/introduction as pointed out by the reviewers.

Below we state our comments on the most notable questions.

## The comparison with Marom et at. in the experimental results
Indeed we should have motivated better the comparison with Marom et at. in the experimental results.

A motivation for this was that Marom et at. used segments from "Open Street Map" and extended them to lines, thus it felt natural to compare the methods since both used the same data and returned the same output (while the objective function is different, as was mentioned in the paper).

An additional motivation was a discussion with the author (Yair Marom) where he mentioned segment clustering as a motivation for their problem (and specifically for their "Open Street Map" test). 

Moreover, we were not aware of many comparable methods, thus we "settled" on this comparison method.

## Comparison to Har-Peled's work on Discrete Integration.
We emphasize that in our work, for each segment, we take an infinite sum of distances (the integral), while Har-Peled’s work considers the case where the sum is over a finite number ($n\geq 1$) of elements, and the size of the coreset is dependent on the number of elements.

Thus applying the result of Har-Peled for a single segment would yield a coreset of size approaching infinity, while in our case we derive a constant size coreset (for constant $k,\varepsilon,$ and $r$).

Additionally Har-Peled supports a different family of functions, and this result does not trivially generalize to our problem.

## The use of Feldman & Schulman (2012)
While indeed after the reduction of the segments to points the application of Feldman & Schulman is rather straightforward, the main theoretical novelty is in the reduction of the points to segments, which takes most of the theoretical part.

Specifically, the proof of Theorem 2.9 (in Theorem E.1) follows straight after the proof of Lemma 2.8. (in Lemma D.4), and takes less than a page.

This is while all the prior part of the appendix (besides the table of contents) is dedicated to the proof of Lemma 2.8.

Moreover, we believe that the result is rather surprising since we obtained a constant size coreset for nonelementary continuous Integrals, while of a specific family.

Hopefully, it clarified why we believe that the results are not a straightforward application of Feldman and Schulman.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces a new problem: k-means clustering of line segments. The goal is to find a set of points that minimize the sum of distances to a set of segments, where distance is defined as the integrated l2 distance between the point and the line segment. Many reviewers felt the problem was not sufficiently motivated in the paper. To their credit, the authors have an appendix section on using line clustering for motion tracking in videos -- it might be helpful to move some of the motivation earlier in the paper. To solve the clustering problem more quickly, the authors propose a coreset algorithm. Essentially they show that the line segments can be discretized into O(1/eps) weighted points, which can then be passed to a black-box coreset construction method for point clustering. The reviewers felt that the novelty of this approach was somewhat low, given that the "heavy lifting" is done by the black-box coreset algorithm. To the authors' credit, while ultimately quite a simple result, the proof that discretizing the line segments works takes some non-trivial work. Finally, the authors implement and provide some experiments on their results. Overall, while this paper has merit, the novelty, presentation, and motivation are weaker than other papers submitted this year. We hope the feedback from reviewers will help the authors refine the work, and wish them the best of luck in a resubmission to another venue.