Recovering the Zipfian Distribution in Unsupervised Term Discovery

• URL: http://arxiv.org/abs/2606.10781v1
• Date: Tue, 09 Jun 2026 12:33:59 GMT
• Title: Recovering the Zipfian Distribution in Unsupervised Term Discovery
• Abstract summary: Unsupervised term discovery involves segmenting unlabelled speech into word- or syllable-like units and clustering these into a lexicon of candidate types.<n>True lexicons follow a Zipfian distribution, yet the dominant centre-based clustering approach -- K-means -- produces a more uniform distribution.<n>We revisit graph-based clustering as a bottom-up alternative, where segment embeddings are connected by pairwise similarity.
• Score: 15.386356718833555
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Unsupervised term discovery involves segmenting unlabelled speech into word- or syllable-like units and clustering these into a lexicon of candidate types. True lexicons follow a Zipfian distribution, yet the dominant centre-based clustering approach -- K-means -- produces a more uniform distribution due to an inductive bias toward spherical clusters. In this paper we revisit graph-based clustering as a bottom-up alternative, where segment embeddings are connected by pairwise similarity and partitioned using the Leiden algorithm. We show that graph clustering substantially outperforms centre-based approaches (K-means, GMM, BIRCH) in both word- and syllable-level lexicon discovery across three languages, producing more Zipf-like distributions. Another bottom-up approach, agglomerative clustering with average linkage, also performs well, although it is computationally less efficient and allows for less control over the resulting distribution. Our work calls into question the dominance of centre-based clustering for term discovery, and promotes graph clustering as an attractive alternative.

Related papers

• Why does Greedy Search produce Optimal Clustering Outcomes? A Fixed-Core Assignment Theory [12.631764566188407]
  Clustering performance can deteriorate badly when cluster shapes are irregular, and densities or sizes vary between clusters.<n>Recent Cluster-as-Distribution' (CaD) clustering has been shown to discover these generic types of clusters.<n>This is the first analysis that explains why CaD clustering via greedy search can discover clusters of arbitrary shapes, densities and sizes.
  arXiv  Detail & Related papers  (2026-07-27T10:15:08Z)
• Distributionally Robust K-Means Clustering [18.037323759791658]
  K-means clustering is notoriously brittle to outliers, distribution shifts, and limited sample sizes.<n>We develop a distributionally robust variant that protects against such pathologies.<n>A tractable dual yields a soft-clustering scheme that replaces hard assignments with smoothly weighted ones.
  arXiv  Detail & Related papers  (2026-04-13T07:32:36Z)
• Rethinking Divisive Hierarchical Clustering from a Distributional Perspective [7.023830532843621]
  Divisive Hierarchical Clustering (DHC) methods produce a dendrogram that does not have three desired properties.<n>We show that this shortcoming can be addressed by using a distributional kernel, instead of the set-oriented criterion.<n>Our proposed method successfully creates a dendrogram that is consistent with the biological regions in a Spatial Transcriptomics dataset.
  arXiv  Detail & Related papers  (2026-01-27T15:41:56Z)
• 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)
• Learning Uniform Clusters on Hypersphere for Deep Graph-level Clustering [25.350054742471816]
  We propose a novel deep graph-level clustering method called Uniform Deep Graph Clustering (UDGC) UDGC assigns instances evenly to different clusters and then scatters those clusters on unit hypersphere, leading to a more uniform cluster-level distribution and a slighter cluster collapse. Our empirical study on eight well-known datasets demonstrates that UDGC significantly outperforms the state-of-the-art models.
  arXiv  Detail & Related papers  (2023-11-23T12:08:20Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  We propose a new deep graph clustering method termed Reinforcement Graph Clustering. In our proposed method, cluster number determination and unsupervised representation learning are unified into a uniform framework. In order to conduct feedback actions, the clustering-oriented reward function is proposed to enhance the cohesion of the same clusters and separate the different clusters.
  arXiv  Detail & Related papers  (2023-08-13T18:12:28Z)
• A Computational Theory and Semi-Supervised Algorithm for Clustering [0.0]
  Clustering is the obtainment of groupings of data with no anomalies.<n>The kernel of the clustering method is the perception anomaly detection algorithm.<n>A semi-supervised clustering algorithm is presented.
  arXiv  Detail & Related papers  (2023-06-12T09:15:58Z)
• 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)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  Clustering is a fundamental primitive in unsupervised learning. Recent work has established lower bounds against the class of low-degree methods. We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
  arXiv  Detail & Related papers  (2021-12-07T18:50:17Z)
• Self-supervised Contrastive Attributed Graph Clustering [110.52694943592974]
  We propose a novel attributed graph clustering network, namely Self-supervised Contrastive Attributed Graph Clustering (SCAGC) In SCAGC, by leveraging inaccurate clustering labels, a self-supervised contrastive loss, are designed for node representation learning. For the OOS nodes, SCAGC can directly calculate their clustering labels.
  arXiv  Detail & Related papers  (2021-10-15T03:25:28Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  Existing scalable hierarchical clustering methods sacrifice quality for speed. We present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points.
  arXiv  Detail & Related papers  (2020-10-22T15:58:35Z)
• Revisiting Agglomerative Clustering [4.291340656866855]
  A model of clusters was also adopted, involving a higher density nucleus surrounded by a transition, followed by outliers. The obtained results include the verification that many methods detect two clusters in unimodal data. The single-linkage method was found to be more resilient to false positives.
  arXiv  Detail & Related papers  (2020-05-16T14:07:25Z)

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.