dorsal/arxiv
View SchemaEfficient Uncertainty Minimization for Fuzzy Spectral Clustering
| Authors | Brian White, David Shalloway |
|---|---|
| Categories | |
| ArXiv ID | physics/0703238 |
| URL | https://arxiv.org/abs/physics/0703238 |
| DOI | 10.1103/PhysRevE.80.056705 |
| Journal | Phys. Rev. E 80 (2009) 056705 |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
Abstract
Spectral clustering uses the global information embedded in eigenvectors of an inter-item similarity matrix to correctly identify clusters of irregular shape, an ability lacking in commonly used approaches such as k-means and agglomerative clustering. However, traditional spectral clustering partitions items into hard clusters, and the ability to instead generate fuzzy item assignments would be advantageous for the growing class of domains in which cluster overlap and uncertainty are important. Korenblum and Shalloway [Phys. Rev. E 67, 056704 (2003)] extended spectral clustering to fuzzy clustering by introducing the principle of uncertainty minimization. However, this posed a challenging non-convex global optimization problem that they solved by a brute-force technique unlikely to scale to data sets having more than O(10^2) items. Here we develop a new method for solving the minimization problem, which can handle data sets at least two orders of magnitude larger. In doing so, we elucidate the underlying structure of uncertainty minimization using multiple geometric representations. This enables us to show how fuzzy spectral clustering using uncertainty minimization is related to and generalizes clustering motivated by perturbative analysis of almost-block-diagonal matrices. Uncertainty minimization can be applied to a wide variety of existing hard spectral clustering approaches, thus transforming them to fuzzy methods.
{
"annotation_id": "8a3e1b22-7a7a-4b26-93de-420eea8315db",
"date_created": "2026-03-02T18:01:18.445000Z",
"date_modified": "2026-03-02T18:01:18.445000Z",
"file_hash": "f4e1a354c541ad9901a456aab9dea800aeb0fffc4dd59096878b3e256aefa9e9",
"private": false,
"record": {
"abstract": "Spectral clustering uses the global information embedded in eigenvectors of\nan inter-item similarity matrix to correctly identify clusters of irregular\nshape, an ability lacking in commonly used approaches such as k-means and\nagglomerative clustering. However, traditional spectral clustering partitions\nitems into hard clusters, and the ability to instead generate fuzzy item\nassignments would be advantageous for the growing class of domains in which\ncluster overlap and uncertainty are important. Korenblum and Shalloway [Phys.\nRev. E 67, 056704 (2003)] extended spectral clustering to fuzzy clustering by\nintroducing the principle of uncertainty minimization. However, this posed a\nchallenging non-convex global optimization problem that they solved by a\nbrute-force technique unlikely to scale to data sets having more than O(10^2)\nitems. Here we develop a new method for solving the minimization problem, which\ncan handle data sets at least two orders of magnitude larger. In doing so, we\nelucidate the underlying structure of uncertainty minimization using multiple\ngeometric representations. This enables us to show how fuzzy spectral\nclustering using uncertainty minimization is related to and generalizes\nclustering motivated by perturbative analysis of almost-block-diagonal\nmatrices. Uncertainty minimization can be applied to a wide variety of existing\nhard spectral clustering approaches, thus transforming them to fuzzy methods.",
"arxiv_id": "physics/0703238",
"authors": [
"Brian White",
"David Shalloway"
],
"categories": [
"physics.data-an",
"physics.comp-ph"
],
"doi": "10.1103/PhysRevE.80.056705",
"journal_ref": "Phys. Rev. E 80 (2009) 056705",
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "Efficient Uncertainty Minimization for Fuzzy Spectral Clustering",
"url": "https://arxiv.org/abs/physics/0703238"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "a9fc3df0-0615-4c25-b54d-2ab5cdc429be",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}