K-Means Clustering With Incomplete Data with the Use of Mahalanobis Distances

Lovis Kwasi Armah, Igor Melnykov · 2024

Read K-Means Clustering With Incomplete Data with the Use of Mahalanobis Distances by Lovis Kwasi Armah, Igor Melnykov (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-00870.txt.

Description

Abstract Effectively applying the K-means algorithm to clustering tasks with incomplete features remains an important research area due to its impact on real-world applications. Recent work has shown that unifying K-means clustering and imputation into one single objective function and solving the resultant optimization yield superior results compared to handling imputation and clustering separately.

Catalog record

CREATORLovis Kwasi Armah, Igor Melnykov
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2411-00870

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

K-Means Clustering With Incomplete Data with the Use of Mahalanobis Distances Lovis Kwasi Armah, Igor Melnykov Abstract Effectively applying the K-means algorithm to clustering tasks with incomplete features remains an important research area due to its impact on real-world applications. Recent work has shown that unifying K-means clustering and imputation into one single objective function and solving the resultant optimization yield superior results compared to handling imputation and clustering separately. In this work, we extend this approach by developing a unified K-means algorithm that incorporates Mahalanobis distances, instead of the traditional Euclidean distances, which previous research has shown to perform better for clusters with elliptical shapes. We conducted extensive experiments on synthetic datasets containing up to ten elliptical clusters, as well as the IRIS dataset. Using the Adjusted Rand Index (ARI) and Normalized Mutual Information (NMI), we demonstrate that our algorithm consistently outperforms both standalone imputation followed by K-means (using either Mahalanobis or Euclidean distance) and K-Means with Incomplete Data, the recent K-means algorithms that integrate imputation and clustering for handling incomplete data. These results hold across both the IRIS dataset and randomly generated data with elliptical clusters. August 24, 2026 K eywords K-means clustering \cdot Incomplete data, \cdot Imputation method 1 Introduction Clustering algorithms devise a systematic process to group data into similar categories using some measure. There are several different types of clustering algorithms based on how subgroups are found in data. Common types are Hierarchical Clustering, Partition Clustering, Grid based Clustering, Density based Clustering, and Soft clustering. Grid based clustering carries out clustering of high dimensional data using group of cells that form a grid structure. Common examples are Statistical information grid-based (STING) algorithm and Optimal grid (OPTIGRID) [ 18 , 6 ] . Density based clustering separates low data concentration points from highly concentrated ones. Notable examples are DBSCAN [ 4 ] and DENCUE [ 13 ] . Soft clustering allows data points to belong to more than one cluster with a graduating degree of membership. Examples of soft clustering algorithms are fuzzy C-Means, [ 2 ] and Fuzzy clustering by Local Approximation of Membership (FLAME). Partitioning clustering, unlike other clustering types discovers subgroups using some objective function which improves the quality of the clustering. K-means is an example of a Hierarchical clustering that assigns data points into one of K-subgroups based on a distance closest to the center of the centroid. K-Means is very easy to implement and as a result widely used in various fields, including computer vision, computer security, health, social sciences, and natural language processing. In computer vision, it is employed for object detection and image processing as well as algorithms in computer security helping detect Distributed Denial of Service (DDoS) attacks In health, and social sciences, it is used for data summarization and segmentation, among other applications [ 1 , 12 ] . Despite the popularity of K-means,it is often applied to data with incomplete features. However, Data must be made complete so K-means algorithm can be applied. To address the problem of incompleteness, various heuristics and statistical methods are employed. Heuristics might involve dropping incomplete data coordinates, while statistical methods utilize available data properties to fill in the incomplete data. Common imputation techniques include zero-filling, conditional mean, median, mode, regression imputation, and K-nearest neighbors (KNN) [ 17 ] . Other methods such as Expectation-Maximization (EM) algorithm, estimate the most likely values for the missing data. However, the problem is that these imputation methods are often applied separately from the K-means algorithm, which has been shown by [ 17 ] , to be less effective compared to unifying the imputation and clustering into one objective function. Furthermore, K-means is well suited for spherical clusters, but it is often applied to real-world data where interactions between features distort the spherical or compact shape. To overcome the challenge of lack of spherical shapes associated with real-world data, [ 10 ] demonstrated that employing the Mahalanobis distance rather than Euclidean distance typically used in K-means works well for non-spherical datasets. i. We extend existing K-means Clustering with Incomplete data algorithm to work with all clusters irrespective of the shape. We demonstrate that our extension performs better using extensive experiments done that we did using synthetic datasets with non-spherical shapes and one UCI benchmark dataset. ii. Extensive simulation study to determine how the level of incompleteness distribution impacts the performance of the proposed algorithm and suggest areas of improvement. 2 Related Works In this section, we review the literature on clustering algorithms, particularly on K-Means, We also discuss a variant of K-Means algorithm that uses Mahalanobis distances, We discuss imputation methods employed to deal with incomplete data and cover K-Means clustering with incomplete data. We provide a brief summary of relevant work and refer readers to their findings for detailed summaries. 2.1 K-Means Algorithm K-means is an example of Partition Clustering that assigns data points into one of K groups, Each group has a center called centroid and points are assigned to the closest centroid after calculating the distance to each centroid. The algorithm requires the use of some measure to determine the closest distance to a cluster centroid. Furthermore, the algorithm requires the number of clusters K to be known and seeded with K values. Knowing the number of clusters helps to partition a set of n p -dimensional data points \mathbf{X}=\{\mathbf{x}_{i}\}_{i=1}^{n} into K clusters. After the initial seeding of values, it continuously changes the cluster configuration until the algorithm converges to a stable solution by reassigning points to clusters that minimize the objective function below. \text{obj}=\sum_{i=1}^{n}\sum_{j=1}^{k}h_{ij}d(\mathbf{x}_{i},\boldsymbol{\mu}_{j})), (1) where h_{ij} is an indicator variable that is 1 if data point \mathbf{x}_{i} belongs to cluster j and 0 otherwise, \boldsymbol{\mu}_{j} is the centroid of cluster j , and d(\mathbf{x}_{i},\boldsymbol{\mu}_{j}) is the distance metric used, The most commonly used distance metric is the Euclidean distance, although other metrics, such as the Mahalanobis distance, can also be employed. The simplicity and ease of computation make the Euclidean distance a very popular choice for the K-means algorithm. However, because the Euclidean distance does not account for the shape of the clusters in its distance calculation, it may incorrectly assign points to the closest clusters, which might differ from the assignments obtained when the cluster shape is taken into consideration. 2.2 K-Means with Mahalanobis distances K-Means with Mahalanobis distance is similar to K-means except that it replaces the distance metric with Mahalanobis distance. It deals with the problem of assigning points to wrong clusters by replacing Euclidean distance, which does not factor the shape of the clusters in the distance metric, with Mahalanobis distance. The Mahalanobis distance takes the shape of the cluster, which is determined by the covariance matrix {\boldsymbol{\Sigma}} . It is defined as: d_{M}(\mathbf{x}_{i},\boldsymbol{\mu}_{k})=\sqrt{(\mathbf{x}_{i}-\boldsymbol{\mu}_{k})^{T}{\boldsymbol{\Sigma}}_{k}^{-1}(\mathbf{x}_{i}-\boldsymbol{\mu}_{k})} where \boldsymbol{\mu}_{k} and {\boldsymbol{\Sigma}_{k}} are the mean vector and covariance matrix of the k^{th} cluster, The use of the covariance matrix makes it less popular as it must be properly initialized to work properly. Melnykov et al [ 10 ] , demonstrated that the K-Means with Mahalanobis distances algorithm consistently outperforms the traditional K-Means algorithm in clustering data with non-spherical covariance structures and that it is particularly effective in scenarios where the clusters have different sizes and orientations, which are poorly handled

Read the complete text