Nystr\"om Approximation with Nonnegative Matrix Factorization

• URL: http://arxiv.org/abs/2008.03399v1
• Date: Fri, 7 Aug 2020 23:52:59 GMT
• Title: Nystr\"om Approximation with Nonnegative Matrix Factorization
• Authors: Yongquan Fu
• Abstract summary: We show that the proximity clustering problem can be effectively formulated as the Nystr"om approximation problem. We implement the Nystr"om approximation based on a landmark based Nonnegative Matrix Factorization (NMF) process.
• Score: 4.990119940008071
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by the needs of estimating the proximity clustering with partial distance measurements from vantage points or landmarks for remote networked systems, we show that the proximity clustering problem can be effectively formulated as the Nystr\"om approximation problem, which solves the kernel K-means clustering problem in the complex space. We implement the Nystr\"om approximation based on a landmark based Nonnegative Matrix Factorization (NMF) process. Evaluation results show that the proposed method finds nearly optimal clustering quality on both synthetic and real-world data sets as we vary the range of parameter choices and network conditions.

Related papers

• K*-Means: A Parameter-free Clustering Algorithm [55.20132267309382]
  k*-means is a novel clustering algorithm that eliminates the need to set k or any other parameters.<n>It uses the minimum description length principle to automatically determine the optimal number of clusters, k*, by splitting and merging clusters.<n>We prove that k*-means is guaranteed to converge and demonstrate experimentally that it significantly outperforms existing methods in scenarios where k is unknown.
  arXiv  Detail & Related papers  (2025-05-17T08:41:07Z)
• Clustering by Nonparametric Smoothing [6.635604919499181]
  A novel formulation of the clustering problem is introduced in which the task is expressed as an estimation problem. The proposed approach bypasses any explicit modelling assumptions and exploits the flexible estimation potential of nonparametric smoothing. Experiments on a large collection of publicly available data sets are used to document the strong performance of the proposed approach.
  arXiv  Detail & Related papers  (2025-03-12T07:44:11Z)
• Counterfactual Explanations for k-means and Gaussian Clustering [1.8561812622368767]
  We present a general definition for counterfactuals for model-based clustering that includes plausibility and feasibility constraints. Our approach takes as input the factual, the target cluster, a binary mask indicating actionable or immutable features and a plausibility factor specifying how far from the cluster boundary the counterfactual should be placed.
  arXiv  Detail & Related papers  (2025-01-17T14:56:20Z)
• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means one-step dimensionality reduction clustering method has made some progress in addressing the curse of dimensionality in clustering tasks. We propose a unified framework that integrates manifold learning with K-means, resulting in the self-supervised graph embedding framework.
  arXiv  Detail & Related papers  (2024-09-24T08:59:51Z)
• Fuzzy K-Means Clustering without Cluster Centroids [21.256564324236333]
  Fuzzy K-Means clustering is a critical technique in unsupervised data analysis. This paper proposes a novel Fuzzy textitK-Means clustering algorithm that entirely eliminates the reliance on cluster centroids.
  arXiv  Detail & Related papers  (2024-04-07T12:25:03Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  We present a new clustering algorithm which directly detects clusters of data without mean estimation. Specifically, we construct distance matrix between data points by Butterworth filter. To well exploit the complementary information embedded in different views, we leverage the tensor Schatten p-norm regularization.
  arXiv  Detail & Related papers  (2023-05-12T03:01:41Z)
• Sketch-and-solve approaches to k-means clustering by semidefinite programming [14.930208990741132]
  We introduce a sketch-and-solve approach to speed up the Peng-Wei semidefinite relaxation of k-means clustering. If the data is appropriately separated we identify the k-means optimal clustering. Otherwise, our approach provides a high-confidence lower bound on the optimal k-means value.
  arXiv  Detail & Related papers  (2022-11-28T19:51:30Z)
• A One-shot Framework for Distributed Clustered Learning in Heterogeneous Environments [54.172993875654015]
  The paper proposes a family of communication efficient methods for distributed learning in heterogeneous environments. One-shot approach, based on local computations at the users and a clustering based aggregation step at the server is shown to provide strong learning guarantees. For strongly convex problems it is shown that, as long as the number of data points per user is above a threshold, the proposed approach achieves order-optimal mean-squared error rates in terms of the sample size.
  arXiv  Detail & Related papers  (2022-09-22T09:04:10Z)
• Gradient Based Clustering [72.15857783681658]
  We propose a general approach for distance based clustering, using the gradient of the cost function that measures clustering quality. The approach is an iterative two step procedure (alternating between cluster assignment and cluster center updates) and is applicable to a wide range of functions.
  arXiv  Detail & Related papers  (2022-02-01T19:31:15Z)
• Improving k-Means Clustering Performance with Disentangled Internal Representations [0.0]
  We propose a simpler approach of optimizing the entanglement of the learned latent code representation of an autoencoder. Using our proposed approach, the test clustering accuracy was 96.2% on the MNIST dataset, 85.6% on the Fashion-MNIST dataset, and 79.2% on the EMNIST Balanced dataset, outperforming our baseline models.
  arXiv  Detail & Related papers  (2020-06-05T11:32:34Z)
• A New Validity Index for Fuzzy-Possibilistic C-Means Clustering [6.174448419090291]
  Fuzzy-Possibilistic (FP) index works well in the presence of clusters that vary in shape and density. FPCM requires a priori selection of the degree of fuzziness and the degree of typicality.
  arXiv  Detail & Related papers  (2020-05-19T01:48:13Z)
• Stable and consistent density-based clustering via multiparameter persistence [77.34726150561087]
  We consider the degree-Rips construction from topological data analysis. We analyze its stability to perturbations of the input data using the correspondence-interleaving distance. We integrate these methods into a pipeline for density-based clustering, which we call Persistable.
  arXiv  Detail & Related papers  (2020-05-18T19:45:04Z)
• Local Graph Clustering with Network Lasso [90.66817876491052]
  We study the statistical and computational properties of a network Lasso method for local graph clustering. The clusters delivered by nLasso can be characterized elegantly via network flows between cluster boundary and seed nodes.
  arXiv  Detail & Related papers  (2020-04-25T17:52:05Z)

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.