Noncommutative Model Selection for Data Clustering and Dimension Reduction Using Relative von Neumann Entropy

• URL: http://arxiv.org/abs/2411.19902v1
• Date: Fri, 29 Nov 2024 18:04:11 GMT
• Title: Noncommutative Model Selection for Data Clustering and Dimension Reduction Using Relative von Neumann Entropy
• Authors: Araceli Guzmán-Tristán, Antonio Rieser,
• Abstract summary: We propose a pair of data-driven algorithms for unsupervised classification and dimension reduction. In our experiments, our clustering algorithm outperforms $k$-means clustering on data sets with non-trivial geometry and topology.
• Score: 0.0
• License:
• Abstract: We propose a pair of completely data-driven algorithms for unsupervised classification and dimension reduction, and we empirically study their performance on a number of data sets, both simulated data in three-dimensions and images from the COIL-20 data set. The algorithms take as input a set of points sampled from a uniform distribution supported on a metric space, the latter embedded in an ambient metric space, and they output a clustering or reduction of dimension of the data. They work by constructing a natural family of graphs from the data and selecting the graph which maximizes the relative von Neumann entropy of certain normalized heat operators constructed from the graphs. Once the appropriate graph is selected, the eigenvectors of the graph Laplacian may be used to reduce the dimension of the data, and clusters in the data may be identified with the kernel of the associated graph Laplacian. Notably, these algorithms do not require information about the size of a neighborhood or the desired number of clusters as input, in contrast to popular algorithms such as $k$-means, and even more modern spectral methods such as Laplacian eigenmaps, among others. In our computational experiments, our clustering algorithm outperforms $k$-means clustering on data sets with non-trivial geometry and topology, in particular data whose clusters are not concentrated around a specific point, and our dimension reduction algorithm is shown to work well in several simple examples.

Related papers

• Diffusion-based Semi-supervised Spectral Algorithm for Regression on Manifolds [2.0649432688817444]
  We introduce a novel diffusion-based spectral algorithm to tackle regression analysis on high-dimensional data. Our method uses the local estimation property of heat kernel, offering an adaptive, data-driven approach to overcome this obstacle. Our algorithm performs in an entirely data-driven manner, operating directly within the intrinsic manifold structure of the data.
  arXiv  Detail & Related papers  (2024-10-18T15:29:04Z)
• Resampling and averaging coordinates on data [1.660242118349614]
  We introduce algorithms for robustly computing intrinsic coordinates on point clouds. We identify a subset of representative embeddings by clustering the collection of candidate coordinates and using shape descriptors from topological data analysis. The final output is the embedding obtained as an average of the representative embeddings using generalized Procrustes analysis.
  arXiv  Detail & Related papers  (2024-08-02T16:37:33Z)
• Distributional Reduction: Unifying Dimensionality Reduction and Clustering with Gromov-Wasserstein [56.62376364594194]
  Unsupervised learning aims to capture the underlying structure of potentially large and high-dimensional datasets. In this work, we revisit these approaches under the lens of optimal transport and exhibit relationships with the Gromov-Wasserstein problem. This unveils a new general framework, called distributional reduction, that recovers DR and clustering as special cases and allows addressing them jointly within a single optimization problem.
  arXiv  Detail & Related papers  (2024-02-03T19:00:19Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure. We introduce a new class of manifold, named soft manifold, that can solve this situation. Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
  arXiv  Detail & Related papers  (2023-11-29T12:48:33Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• 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)
• Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs [5.301300942803395]
  Cut-based directed graph (digraph) clustering often focuses on finding dense within-cluster or sparse between-cluster connections. For flow-based clusterings the edges between clusters tend to be oriented in one direction and have been found in migration data, food webs, and trade data.
  arXiv  Detail & Related papers  (2022-03-02T20:07:04Z)
• Learning Low-Dimensional Nonlinear Structures from High-Dimensional Noisy Data: An Integral Operator Approach [5.975670441166475]
  We propose a kernel-spectral embedding algorithm for learning low-dimensional nonlinear structures from high-dimensional and noisy observations. The algorithm employs an adaptive bandwidth selection procedure which does not rely on prior knowledge of the underlying manifold. The obtained low-dimensional embeddings can be further utilized for downstream purposes such as data visualization, clustering and prediction.
  arXiv  Detail & Related papers  (2022-02-28T22:46:34Z)
• Riemannian classification of EEG signals with missing values [67.90148548467762]
  This paper proposes two strategies to handle missing data for the classification of electroencephalograms. The first approach estimates the covariance from imputed data with the $k$-nearest neighbors algorithm; the second relies on the observed data by leveraging the observed-data likelihood within an expectation-maximization algorithm. As results show, the proposed strategies perform better than the classification based on observed data and allow to keep a high accuracy even when the missing data ratio increases.
  arXiv  Detail & Related papers  (2021-10-19T14:24:50Z)
• Measuring inter-cluster similarities with Alpha Shape TRIangulation in loCal Subspaces (ASTRICS) facilitates visualization and clustering of high-dimensional data [0.0]
  Clustering and visualizing high-dimensional (HD) data are important tasks in a variety of fields. Some of the most effective algorithms for clustering HD data are based on representing the data by nodes in a graph. I propose a new method called ASTRICS to measure similarity between clusters of HD data points.
  arXiv  Detail & Related papers  (2021-07-15T20:51:06Z)
• Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminants [94.46276668068327]
  In [1], an ensemble of randomly projected linear discriminants is used to classify datasets. We develop a consistent estimator of the misclassification probability as an alternative to the computationally-costly cross-validation estimator. We also demonstrate the use of our estimator for tuning the projection dimension on both real and synthetic data.
  arXiv  Detail & Related papers  (2020-04-17T12:47:04Z)

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.