Simple, Scalable and Effective Clustering via One-Dimensional Projections

Summary

$k$-means clustering is a classical and fundamental method in machine learning. This paper proposes a very simple method that projects the $n$ data points onto a one-dimensional space by generating a random Gaussian vector. Moreover, the one-dimensional projections can be used for coreset construction and the seeding in $k$-means++. The experimental results have proven the efficiency of the proposed algorithm.

Strengths

(1) The proposed method is very simple and easy to understand. (2) The idea of projecting the $n$ input points onto one-dimensional space is kind of novel. (3) This paper provides strict proofs for the running time and approximation ratio. (4) Experimental results show the efficiency for coreset construction and $k$-means++ implementation.

Weaknesses

(1) The essence of the proposed method is dimension reduction. To be specific, the pairwise distances of the $n$ data points are roughly preserved by projecting onto one-dimensional space. The projected distances are used to $k$-means++ seeding and an approximate clustering. By the sorted $n$ scalars, the seeding can be implemented in time $O(n \log{n})$ independent of $k$ but at the cost of $\widetilde{O}(k^4)$ approximation ratio. For me, I think the technique is straightforward and the idea's novelty is a little limited. (2) The colors of the curves in Figure 2 and Figure 3 are not easy to distinguish.

Questions

The approximation ratio $\widetilde{O}(k^4)$ can be improved to $O(\log{k})$ with running time $O(\text{nnz}(X) + n\log{n}) + \text{poly}(kd) \log{n}$. However, why does not this result show in the experiments?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

See the Weaknesses part.

Summary

The paper proposes a new clustering algorithm that seeks to have the accuracy of k-means++ while avoiding the time complexity of O(ndk). In particular, the paper focuses on settings where k is large and seeks a O(nd+nlogn) time complexity. This is a practically relevant problem. The main algorithm proposed in the paper is a simple algorithm based on projecting all data points onto a random one-dimensional subspace and performing the k-means++ seeding procedure on the dimensionality-reduced data. Interestingly, it is shown that this can be done in time O(nd+nlog(n)) and it has a poly(k) approximation guarantee with respect to the optimal k-means clustering. While the poly(k) guarantee is worse than the O(log k) guarantee of k-means++, a log(k) approximation guarantee can be obtained if we use the proposed algorithm to build a coreset of size poly(kd)*log(n), and then use k-means++ on the resulting coreset. While the techniques in [26] (based on approximate nearest neighbor search) achieve similar goals to those of the present paper (a fast alternative to k-means++ with a complexity that doesn’t depend on k), the algorithm in the present paper is attractive for its surprising simplicity.

Strengths

The proposed algorithm is natural and intuitive, but the theoretical analysis is quite involved. The fact that a one-dimensional projection can be shown to provide an approximation guarantee (although a poly(k) one) is interesting and nontrivial, since a Johnson-Lindenstrauss type approach typically requires a projection onto log(n) dimensions. After the one-dimensional projection, a standard implementation of k-means++ seeding does not avoid the O(nk) dependence. As such, the paper proposes a careful data structure to perform k-means seeding on a one-dimensional dataset. The proof that this approach runs in time O(n logn) is technically sophisticated and could be of independent interest. The potential function must be carefully defined, and its use to show that each point is only updated O(log n) times is elegant. The paper is well written and clear, and the results should be of interest to people working on the theory of clustering algorithms and to people looking for practical approaches for performing k-means clustering on large datasets with large k.

Weaknesses

The empirical results in the paper are generally positive, but perhaps a bit underwhelming, as the proposed approach doesn’t seem to have a strong advantage over the Lightweight coreset approach from [10]. In particular, the proposed algorithm is slower than the Lightweight approach, and the accuracy of the two approaches is similar (except on the Gaussian dataset case, which was designed to adversarially exploit a weakness of Lightweight). I found it a little confusing to distinguish between the different variants of the algorithm, and it may be helpful to give them clear names (rather than saying “Ours”). In particular, in Section 1, there is a brief discussion about how the approximation can be reduced from poly(k) to O(log k), by incurring an additional poly(nk)*log(n) time. Are the results in 3 and Table 1 for the variant with the O(log k) approximation? Also, in section 1, it says that this improvement is further discussed in the supplementary material, but it wasn’t very clear where. Is this just referring to the general discussion on coresets in Appendix A? It may be useful to have an explicit theorem about the algorithm that combines the proposed algorithm with k-means++ on a coreset (and that algorithm should have a name). I apologize if I missed this somewhere. It may be useful to discuss some of the literature on fast clustering algorithms beyond k-means. For instance, there are “fast” implementations of PAM for k-medoids (such as FastPAM, Clarans and BanditPAM) and of dbscan (such as dbscan++). It may be the case that all those incur the O(ndk) time that this paper tries to avoid, but a mention of that would be useful to the community (specially as it relates to the claim that there are no other clustering algorithms with O(n*log(n)) complexity). Some other minor comments/typos: - line 144: k-measn -> k-means - line 278: “compared a” -> “compared to a” - line 279: “entre dataset” -> “entire dataset” - line 344: “running independent” -> “running time independent”

Questions

A natural way to perform a one-dimensional reduction for clustering would be to take the first principal component of the dataset and then perform k-means++ on it. Would such a projection be expected to perform better than the random Gaussian projection used? I realize that computing the first PC would probably be slow, but it may be worth discussing. This may be connected with spectral clustering approaches as well, and with the “biased” versions of the proposed algorithm. A natural question that the proposed algorithm raises is whether one can use a constant number of random projections to improve the poly(k) approximation factor (maybe just reducing the polynomial degree). Could you comment on that?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

The limitations of the proposed approach are discussed in a fair manner.

Summary

The submitted paper focuses on the problem of unsupervised clustering and aims at improving the $\Omega(ndk)$ runtime of the ```kmeans++``` algorithm in the clustering of $n$ $d$-dimensional datapoints in $k$ clusters. The proposed algorithm relies on the intuition of running ```kmeans++``` on a one-dimensional projection of the dataset along a random direction $\boldsymbol v$: the authors prove that such strategy leads to a clustering in $O(nd+n\ln n)$ steps with an approximation ratio scaling as $\tilde O(k^4)$ (to be compared with the $O(\ln k)$ of ```kmeans++```). Numerical experiments compare the performance of the algorithm both with ```kmeans++``` and with other strategies for the production of coresets.

Strengths

The proposed algorithm is very simple to implement (reminiscent of sliced optimal transportation strategies, in which a low-dimensional projection is adopted to solve a high-dimensional problem with a subsequent polynomial gain in speed). The approach proposed by the authors is indeed compatible with a remarkable speed-up and, given its price in quality, suitable for adoption in a pipeline. One of the strengths of the paper is that the authors can provide theoretical guarantees on the performance obtained by this simple trick.

Weaknesses

The proposed algorithm pays the price of better performances producing clusterings of lower quality, as the authors themselves point out. This drawback can be mitigated by adopting the algorithm for the construction of coresets within a pipeline (as discussed in the paper). In the case in which the algorithm is adopted as a stand-alone solution, the (possibly deteriorating) effect of structure in the dataset is only partially investigated and addressed.

Questions

* If I understand correctly, the algorithm relies on a single low-dimensional projection along a random vector $\boldsymbol v\in\mathbb R^d$. I was wondering if the algorithm would benefit from the sampling of $m=O(1)$ vectors, or if instead, such strategy would lead to irrelevant benefits. * It is not very clear in which units the elements of Table 1 are given (from what I understand the table reports speed-up ratios). Please clarify the caption. Also, do the authors have an estimate of the error on the reported values? * Do the authors have an intuition about the fact that the biased and covariance version of the algorithm suffers a remarkable slowdown with respect to the unbiased version? * In section 3.2 it is commented that, when working on the Gaussian dataset, the algorithm *did not pick up one of the points close to the origin* so its output is associated with a particularly high cost. Could the author clarify what they mean with this sentence? Minor typos * Line 45: *in approximate* in place of *an approximate*. * Line 244: *measn* in place of *means*. * What does *with a few approaches in the literature* refer to in line 147? * Line 293: *Senstivity* in place of *Sensitivity*.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

Limitations of the contribution have been addressed, see also the *Weakness* section.

Summary

The paper presents a new technique for clustering data such that the running time of the method is independent of the number of clusters, and the approximation error is polynomial only in the number of clusters and not the number of data points. The paper experimentally tests the method and finds that it is a good balance of speed and quality of the result.

Strengths

There are many strengths. 1) The runtime being independent of $k$ is a significant speed up. Further, the constants seem to be better as well. Since the method is not iterative and only makes a single pass over the data 2) The experimental results on corsets are compelling. 3) The presentation of the method is easy to follow.

Weaknesses

The approximation of ratio of $O(k^4)$ is significantly worse than $O(\log k)$. I was hoping this was only theoretical and that we would see better results experimentally, but the experimental results are not clear. Specifically for Figure 3, I have no idea what the difference between the bottom and the top row is. This is partly due to the fact that the paper never actually writes down formally the problem or the metrics used. From my understanding, we have $n$ data points $x_1, \ldots, x_n$ in high dimensional space. We want to find $k$ clusters $C_1, \ldots, C_k$ where each $C_i$ is a subset of the $n$ data points such that if $c_i$ is the center of the mass of those points, then $$ \sum_{i=1}^k \sum_{j \in C_i} \|c_i - x_j\|^2 $$ is minimized. This is what I interpret to be the cost. Hence it is very unclear to me what Figure 3 is showing.

Questions

What is the time complexity for the third step?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Summary

This paper introduces a randomized clustering algorithm that provably runs in expected time O(nnz(X) + n log n) for arbitrary k. In theoretical analysis, the proposed algorithm achieves approximation ratio O(k^4 ) on any input dataset for the k-means objective. In the experiments, the quality of the clusters found by the proposed algorithm is usually much better than this worst-case bound. They use the algorithm for k-means clustering and coreset construction. This work shows that the approximation ratio achieved after a random one-dimensional projection can be lifted to the original points and that k-means++ seeding can be implemented in expected time O(n log n) in one dimension.

Strengths

This paper has the following contributions: It designs a simple, practical algorithm for k-means that runs in time roughly O(nd), independent of k, and produces high-quality clusters. In theoretical analysis, they give a randomized clustering algorithm with provable guarantees on its running time and approximation ratio without making any assumptions about the data. In experiments, they run two types of experiments, highlighting various aspects of the algorithm: Coreset Construction Comparison and Direct k-means++ comparison.

Weaknesses

1.Insufficient research on related work. There are many methods for accelerating clustering. This paper did not conduct comprehensive research. In the most relevant random projection clustering, this work is not the first random projection clustering work, such as paper [1]. It is not cited in this paper. The superiority of this work cannot be verified. Please compare it from the theoretical analysis, experimental results, algorithm complexity, etc. [1]Liu W, Shen X, Tsang I. Sparse Embedded $ k $-Means Clustering[J]. Advances in neural information processing systems, 2017. 2.The organization and presentation of this paper can be further improved. The second half of the abstract is logically chaotic. 3.The experiment is insufficient to verify the superiority of this work. The experimental results show that the performance of the proposed algorithm is not excellent, such as in Figure 2,3.

Questions

See “Weaknesses”.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

N/A

Thank you for the clarification

I will increase my score