Article
Computer Science, Information Systems
Zhenfeng He
Summary: Weighted K-Means (WKM) algorithms are increasingly important but have been largely ignored in terms of initialization. This paper proposes a semi-supervised algorithm to address the initialization problem by studying Feature weight self-adjustment K-Means (FWSA K-Means).
Article
Computer Science, Artificial Intelligence
Carlo Baldassi
Summary: We introduce an evolutionary algorithm called recombinator-k-means for optimizing the highly nonconvex kmeans problem. Its defining feature is that its crossover step involves all the members of the current generation, stochastically recombining them with a repurposed variant of the k-means++ seeding algorithm. The recombination also uses a reweighting mechanism that realizes a progressively sharper stochastic selection policy and ensures that the population eventually coalesces into a single solution. We compare this scheme with a state-of-the-art alternative, a more standard genetic algorithm with deterministic pairwise-nearest-neighbor crossover and an elitist selection policy, of which we also provide an augmented and efficient implementation. Extensive tests on large and challenging datasets (both synthetic and real word) show that for fixed population sizes recombinator-k-means is generally superior in terms of the optimization objective, at the cost of a more expensive crossover step. When adjusting the population sizes of the two algorithms to match their running times, we find that for short times the (augmented) pairwise-nearest-neighbor method is always superior, while at longer times recombinator-k-means will match it and, on the most difficult examples, take over. We conclude that the reweighted whole-population recombination is more costly but generally better at escaping local minima Moreover, it is algorithmically simpler and more general (it could be applied even to k-medians or k-medoids, for example).
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION
(2022)
Article
Computer Science, Artificial Intelligence
Yi-Cheng Chen, Yen-Liang Chen, Jyun-Yun Lu
Summary: K-Means algorithm is one of the most famous and popular clustering algorithms in the world, known for its simple structure, easy implementation, high efficiency, and fast convergence speed. This article introduces an improvement to past variants of K-Means used in evolutionary clustering, considering both past and future clustering results, and extending K-Means to multiple cycles, resulting in more consistent, stable, and smooth clustering results.
EXPERT SYSTEMS WITH APPLICATIONS
(2021)
Article
Engineering, Chemical
T. A. Sipkens, S. N. Rogak
Summary: This note presents a new approach to identifying soot aggregates in transmission electron microscopy images using k-means clustering, which requires image pre- and post-processing methods. Three pre-processed versions of the image are compiled into feature layers prior to segmentation using k-means.
JOURNAL OF AEROSOL SCIENCE
(2021)
Article
Automation & Control Systems
Uri Stemmer
Summary: This research presents a new algorithm operating in the local model of differential privacy for solving the Euclidean k-means problem, significantly reducing additive error while maintaining multiplicative error. The study shows that the obtained additive error in handling the k-means objective is almost optimal in terms of its dependency on the database size.
JOURNAL OF MACHINE LEARNING RESEARCH
(2021)
Article
Computer Science, Interdisciplinary Applications
Ahmed Fahim
Summary: The k-means method divides N objects into k clusters based on mean values, with linear time complexity and dependence on knowing the number of clusters and initial centers. This research introduces a method able to detect near-optimal values for k and initial centers without prior knowledge, resulting in improved final result quality. The proposed method combines DBSCAN and k-means to converge to global minima and has a time complexity of o(n log n).
JOURNAL OF COMPUTATIONAL SCIENCE
(2021)
Article
Computer Science, Information Systems
Jing Liu, Fuyuan Cao, Jiye Liang
Summary: In this paper, a centroids-guided deep multi-view k-means clustering method is proposed, which incorporates deep representation learning into the multi-view k-means objective. The method produces more k-means-friendly representations by reducing the loss between each representation and its assigned cluster centroid.
INFORMATION SCIENCES
(2022)
Article
Computer Science, Artificial Intelligence
Hongfu Liu, Junxiang Chen, Jennifer Dy, Yun Fu
Summary: K-means is a widely used clustering algorithm known for its simplicity and efficiency. This review paper focuses on generalizing K-means to solve challenging and complex problems. It unifies the available approaches in terms of data representation, distance measure, label assignment, and centroid updating. Concrete applications of modified K-means formulations are reviewed, including iterative subspace projection and clustering, consensus clustering, constrained clustering, domain adaptation, and outlier detection.
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE
(2023)
Article
Geochemistry & Geophysics
Han Zhai, Hongyan Zhang, Liangpei Zhang, Pingxiang Li
Summary: This article introduces a novel scalable nonlocal means regularized sketched reweighted sparse and low-rank (NL-SSLR) SC algorithm for large HSIs, which explores both local and global structural information of HSIs and fully utilizes spatial correlation information to enhance clustering performance.
IEEE TRANSACTIONS ON GEOSCIENCE AND REMOTE SENSING
(2021)
Article
Computer Science, Artificial Intelligence
Avgoustinos Vouros, Stephen Langdell, Mike Croucher, Eleni Vasilaki
Summary: K-Means is a widely used algorithm for data clustering, but it has limitations such as only finding local minima and being sensitive to initial centroid positions. Various K-Means variations and initialization techniques have been proposed, with more sophisticated techniques reducing the need for complex clustering methods. Deterministic methods generally outperform stochastic methods, but there is a trade-off where simpler stochastic methods run multiple times can result in better clustering.
Article
Computer Science, Artificial Intelligence
Luc Giffon, Valentin Emiya, Hachem Kadri, Liva Ralaivola
Summary: K-means algorithm and Lloyd's algorithm have expanded beyond their original clustering purposes to play pivotal roles in various machine learning and data analysis techniques. QuicK-means is an efficient extension of K-means that reduces computational complexity through sparse matrix products, demonstrating benefits through experimental results.
Article
Computer Science, Artificial Intelligence
Peter Olukanmi, Fulufhelo Nelwamondo, Tshilidzi Marwala
Summary: A key drawback of k-means algorithm is its susceptibility to local minima. The authors propose a technique for comparing initializations directly and selecting the best one based on the maximum minimum inter-center distance. The experiments and mathematical analysis show significant efficiency gains and improved accuracy compared to repeated k-means.
NEURAL COMPUTING & APPLICATIONS
(2022)
Article
Computer Science, Information Systems
Wojciech Kwedlo, Michal Lubowicz
Summary: This paper investigates exact accelerated algorithms for K-means clustering of low-dimensional data on modern multi-core systems, proposing a parallelized filtering algorithm using OpenMP standard. Computational experiments show that the algorithm has high parallel efficiency, but its advantage decreases rapidly as data dimension increases.
Article
Computer Science, Artificial Intelligence
Marco Capo, Aritz Perez, Jose A. Antonio
Summary: The K-means algorithm is a popular clustering method, but its performance depends heavily on the initialization phase. Researchers have developed various initialization techniques to address this issue. This article introduces a cost-effective Split-Merge step that can restart the K-means algorithm after reaching a fixed point, reducing error and computing fewer distances.
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
(2022)
Article
Multidisciplinary Sciences
K. Harinadha Reddy
Summary: This paper proposes a clustering machine learning approach to enhance the performance and safety of integrated networks under disturbances and improper operations, and uses continuous changes in fuzzy variables to estimate the network state.
ARABIAN JOURNAL FOR SCIENCE AND ENGINEERING
(2023)