More Like this

1. Fast Optimal Circular Clustering and Applications on Round Genomes

   https://doi.org/10.1109/TCBB.2021.3077573  

   Debnath, Tathagata; Song, Mingzhou (June 2021, IEEE/ACM Transactions on Computational Biology and Bioinformatics)

   null (Ed.)

   Round genomes are found in bacteria, plant chloroplasts, and mitochondria. Genetic or epigenetic marks can present biologically interesting clusters along a circular genome. The circular data clustering problem groups N points on a circle into K clusters to minimize the within-cluster sum of squared distances. Repeatedly applying the K-means algorithm takes quadratic time, impractical for large circular datasets. To overcome this issue, we developed a fast, reproducible, and optimal circular clustering (FOCC) algorithm of worst-case O(KN log^2 N) time. The core is a fast optimal framed clustering algorithm, which we designed by integrating two divide-and-conquer and one bracket dynamic programming strategies. The algorithm is optimal based on a property of monotonic increasing cluster borders over frames on linearized data. On clustering 50,000 circular data points, FOCC outruns brute-force or heuristic circular clustering by three orders of magnitude. We produced clusters of CpG sites and genes along three round genomes, exhibiting higher quality than heuristic clustering. More broadly, the presented subquadratic-time algorithms offer the fastest known solution to not only framed and circular clustering, but also angular, periodical, and looped clustering. We implemented these algorithms in the R package OptCirClust (https://CRAN.R-project.org/package=OptCirClust) 

   more » « less
2. Area-Optimized UAV Swarm Network for Search and Rescue Operations

   https://doi.org/10.1109/CCWC47524.2020.9031197  

   Ruetten, Laik; Regis, Paulo Alexandre; Feil-Seifer, David; Sengupta, Shamik (January 2020, Computing and Communication Workshop and Conference (CCWC))

   null (Ed.)

   Intelligent robot swarms are increasingly being explored as tools for search and rescue missions. Efficient path planning and robust communication networks are critical elements of completing missions. The focus of this research is to give unmanned aerial vehicles (UAVs) the ability to self-organize a mesh network that is optimized for area coverage. The UAVs will be able to read the communication strength between themselves and all the UAVs it is connected to using RSSI. The UAVs should be able to adjust their positioning closer to other UAVs if RSSI is below a threshold, and they should also maintain communication as a group if they move together along a search path. Our approach was to use Genetic Algorithms in a simulated environment to achieve multi-node exploration with emphasis on connectivity and swarm spread. 

   more » « less
3. Sketch-and-Lift: Scalable Subsampled Semidefinite Program for K-means Clustering

   Zhuang, Yubo; Chen, Xiaohui; Yang, Yun (March 2022, International Conference on Artificial Intelligence and Statistics)

   Semidefinite programming (SDP) is a powerful tool for tackling a wide range of computationally hard problems such as clustering. Despite the high accuracy, semidefinite programs are often too slow in practice with poor scalability on large (or even moderate) datasets. In this paper, we introduce a linear time complexity algorithm for approximating an SDP relaxed K-means clustering. The proposed sketch-and-lift (SL) approach solves an SDP on a subsampled dataset and then propagates the solution to all data points by a nearest-centroid rounding procedure. It is shown that the SL approach enjoys a similar exact recovery threshold as the K-means SDP on the full dataset, which is known to be information-theoretically tight under the Gaussian mixture model. The SL method can be made adaptive with enhanced theoretic properties when the cluster sizes are unbalanced. Our simulation experiments demonstrate that the statistical accuracy of the proposed method outperforms state-of-the-art fast clustering algorithms without sacrificing too much computational efficiency, and is comparable to the original K-means SDP with substantially reduced runtime. 

   more » « less
4. Explainable k-means: don’t be greedy, plant bigger trees!

   https://doi.org/10.1145/3519935.3520056  

   Makarychev, Konstantin; Shan, Liren (June 2022, STOC 2022)

   We provide a new bi-criteria O(log2k) competitive algorithm for explainable k-means clustering. Explainable k-means was recently introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020). It is described by an easy to interpret and understand (threshold) decision tree or diagram. The cost of the explainable k-means clustering equals to the sum of costs of its clusters; and the cost of each cluster equals the sum of squared distances from the points in the cluster to the center of that cluster. The best non bi-criteria algorithm for explainable clustering O(k) competitive, and this bound is tight. Our randomized bi-criteria algorithm constructs a threshold decision tree that partitions the data set into (1+δ)k clusters (where δ∈(0,1) is a parameter of the algorithm). The cost of this clustering is at most O(1/δ⋅log2k) times the cost of the optimal unconstrained k-means clustering. We show that this bound is almost optimal. 

   more » « less
5. Convergence Rate of Stochastic k-means

   Tang, Cheng; Monteleoni, Claire (January 2017, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics)

   We analyze online (Bottou & Bengio, 1994) and mini-batch (Sculley, 2010) k-means variants. Both scale up the widely used Lloyd’s algorithm via stochastic approximation, and have become popular for large-scale clustering and unsupervised feature learning. We show, for the first time, that they have global convergence towards “local optima” at rate O(1/t) under general conditions. In addition, we show that if the dataset is clusterable, stochastic k-means with suitable initialization converges to an optimal k-means solution at rate O(1/t) with high probability. The k-means objective is non-convex and non-differentiable; we exploit ideas from non-convex gradient-based optimization by providing a novel characterization of the trajectory of the k-means algorithm on its solution space, and circumvent its non-differentiability via geometric insights about the k-means update. 

   more » « less