The effect of measurement error on clustering algorithms

• URL: http://arxiv.org/abs/2005.11743v1
• Date: Sun, 24 May 2020 13:36:30 GMT
• Title: The effect of measurement error on clustering algorithms
• Abstract summary: We investigate the sensitivity of two common clustering algorithms, GMMs with merging and DBSCAN, to random and systematic error. We find that measurement error is particularly problematic when it is systematic and when it affects all variables in the dataset. For the conditions considered here, we also find that the partition-based GMM with merged components is less sensitive to measurement error than the density-based DBSCAN procedure.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Clustering consists of a popular set of techniques used to separate data into interesting groups for further analysis. Many data sources on which clustering is performed are well-known to contain random and systematic measurement errors. Such errors may adversely affect clustering. While several techniques have been developed to deal with this problem, little is known about the effectiveness of these solutions. Moreover, no work to-date has examined the effect of systematic errors on clustering solutions. In this paper, we perform a Monte Carlo study to investigate the sensitivity of two common clustering algorithms, GMMs with merging and DBSCAN, to random and systematic error. We find that measurement error is particularly problematic when it is systematic and when it affects all variables in the dataset. For the conditions considered here, we also find that the partition-based GMM with merged components is less sensitive to measurement error than the density-based DBSCAN procedure.

Related papers

• An Observation on Lloyd's k-Means Algorithm in High Dimensions [2.186901738997927]
  Clustering and estimating cluster means are core problems in statistics and machine learning.<n>We provide a theoretical explanation for the failure of k-means in high-dimensional settings with high noise and limited sample sizes.
  arXiv  Detail & Related papers  (2025-06-17T20:06:41Z)
• A simulation study of cluster search algorithms in data set generated by Gaussian mixture models [0.0]
  This study examines centroid- and model-based cluster search algorithms in various cases that Gaussian mixture models (GMMs) can generate. The results show that some cluster-splitting criteria based on Euclidean distance make unreasonable decisions when clusters overlap.
  arXiv  Detail & Related papers  (2024-07-27T07:47:25Z)
• Cluster Quilting: Spectral Clustering for Patchwork Learning [8.500141848121782]
  We focus on the clustering problem in patchwork learning, aiming at discovering clusters amongst all samples even when some are never jointly observed for any feature. We propose a novel spectral clustering method called Cluster Quilting, consisting of (i) patch ordering that exploits the overlapping structure amongst all patches, (ii) patchwise SVD, (iii) sequential linear mapping of top singular vectors for patch overlaps, followed by (iv) k-means on the combined and weighted singular vectors. Under a sub-Gaussian mixture model, we establish theoretical guarantees via a non-asymptotic misclustering rate bound that reflects both
  arXiv  Detail & Related papers  (2024-06-19T20:52:47Z)
• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  We devise an efficient algorithm that recovers clusters using the observed labels. We present Instance-Adaptive Clustering (IAC), the first algorithm whose performance matches these lower bounds both in expectation and with high probability.
  arXiv  Detail & Related papers  (2023-06-18T08:46:06Z)
• Research on Efficient Fuzzy Clustering Method Based on Local Fuzzy Granular balls [67.33923111887933]
  In this paper, the data is fuzzy iterated using granular-balls, and the membership degree of data only considers the two granular-balls where it is located. The formed fuzzy granular-balls set can use more processing methods in the face of different data scenarios.
  arXiv  Detail & Related papers  (2023-03-07T01:52:55Z)
• Learning to Bound Counterfactual Inference in Structural Causal Models from Observational and Randomised Data [64.96984404868411]
  We derive a likelihood characterisation for the overall data that leads us to extend a previous EM-based algorithm. The new algorithm learns to approximate the (unidentifiability) region of model parameters from such mixed data sources. It delivers interval approximations to counterfactual results, which collapse to points in the identifiable case.
  arXiv  Detail & Related papers  (2022-12-06T12:42:11Z)
• Causality-Based Multivariate Time Series Anomaly Detection [63.799474860969156]
  We formulate the anomaly detection problem from a causal perspective and view anomalies as instances that do not follow the regular causal mechanism to generate the multivariate data. We then propose a causality-based anomaly detection approach, which first learns the causal structure from data and then infers whether an instance is an anomaly relative to the local causal mechanism. We evaluate our approach with both simulated and public datasets as well as a case study on real-world AIOps applications.
  arXiv  Detail & Related papers  (2022-06-30T06:00:13Z)
• Differentially-Private Clustering of Easy Instances [67.04951703461657]
  In differentially private clustering, the goal is to identify $k$ cluster centers without disclosing information on individual data points. We provide implementable differentially private clustering algorithms that provide utility when the data is "easy" We propose a framework that allows us to apply non-private clustering algorithms to the easy instances and privately combine the results.
  arXiv  Detail & Related papers  (2021-12-29T08:13:56Z)
• Anomaly Clustering: Grouping Images into Coherent Clusters of Anomaly Types [60.45942774425782]
  We introduce anomaly clustering, whose goal is to group data into coherent clusters of anomaly types. This is different from anomaly detection, whose goal is to divide anomalies from normal data. We present a simple yet effective clustering framework using a patch-based pretrained deep embeddings and off-the-shelf clustering methods.
  arXiv  Detail & Related papers  (2021-12-21T23:11:33Z)
• Clustered Hierarchical Anomaly and Outlier Detection Algorithms [0.0]
  We present CLAM, a fast hierarchical clustering technique that learns a manifold in a Banach space defined by a distance metric. On 24 publicly available datasets, we compare the performance of CHAODA to a variety of state-of-the-art unsupervised anomaly-detection algorithms.
  arXiv  Detail & Related papers  (2021-02-09T15:27:52Z)
• Decorrelated Clustering with Data Selection Bias [55.91842043124102]
  We propose a novel Decorrelation regularized K-Means algorithm (DCKM) for clustering with data selection bias. Our DCKM algorithm achieves significant performance gains, indicating the necessity of removing unexpected feature correlations induced by selection bias.
  arXiv  Detail & Related papers  (2020-06-29T08:55:50Z)
• Categorical anomaly detection in heterogeneous data using minimum description length clustering [3.871148938060281]
  We propose a meta-algorithm for enhancing any MDL-based anomaly detection model to deal with heterogeneous data. Our experimental results show that using a discrete mixture model provides competitive performance relative to two previous anomaly detection algorithms.
  arXiv  Detail & Related papers  (2020-06-14T14:48:37Z)
• Handling missing data in model-based clustering [0.0]
  We propose two methods to fit Gaussian mixtures in the presence of missing data. Both methods use a variant of the Monte Carlo Expectation-Maximisation algorithm for data augmentation. We show that the proposed methods outperform the multiple imputation approach, both in terms of clusters identification and density estimation.
  arXiv  Detail & Related papers  (2020-06-04T15:36:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.