PaperlayerView exact revision on arXiv

Source-linked AI summary

Poisson Subspace Clustering: Focusing on the Essentials in Count Data

Collin Leiber, Kai Puolamäki, Heikki Mannila

arXiv:2608.23287v1cs.LG

TL;DR

Count-data clustering requires methods that respect specialized distributional properties while remaining interpretable through relevant-column selection. The paper introduces 3CPO, a Poisson-based algorithm that jointly clusters rows and selects columns, and reports strong performance across diverse count-data settings.

  • Problem

    Generic clustering and transformations may be unreliable for count data because they do not adequately account for its distributional properties, while high dimensionality complicates relevant-column identification.

  • Method

    3CPO uses a Poisson-based model and iterative posterior-probability optimization to cluster rows, select relevant columns, and optionally model outliers with background parameters.

  • Results

    3CPO outperforms compared methods in many scenarios, often selects fewer columns, and shows superior performance in noisy settings.

  • Takeaways & Limitations

    The method provides hard row clusters together with a relevant-column subset, simplifying interpretation across count-data applications.

  • Takeaways & Limitations

    The Poisson structure may be sub-optimal for substantial overdispersion or zero-inflation, and column-selection penalties and outlier encoding involve heuristic choices.

Abstract

from arXiv · show

Count data represented as a matrix of non-negative integer values, such as contingency tables, are prevalent across diverse domains. When clustering such data sets, specific methods are required, as generic algorithms often fail to consider their unique distributional properties, leading to unreliable outputs. An effective strategy is to use well-established statistical models such as the Poisson and negative binomial distributions. We present 3CPO, a clustering algorithm based on statistically solid modeling of count data. In addition to the cluster labels, it identifies a subset of relevant columns, enhancing the interpretability of the results. We propose a simple iterative algorithm that maximizes the posterior probability to find good clustering solutions and discuss its properties. Extensive experiments demonstrate its ability to define high-quality clusters within associated subspaces for various data domains, ranging from gene expressions and texts to economics. Our findings suggest that 3CPO is a robust solution for clustering count data in a statistically sound and interpretable manner. Our code is available at https://github.com/collinleiber/3CPO.

1 Introduction

Count data have distributional properties that make generic clustering and preprocessing unreliable, motivating specialized statistical approaches. 3CPO addresses this need by jointly clustering rows and selecting relevant columns for interpretable common-subspace results.

  • Count data are non-negative integer observations used across fields including biology, ecology, mobility, environmental studies, publications, and economics.
  • Traditional clustering can perform unreliably on count data because transformations may underperform Poisson- and negative-binomial-based models.
  • High dimensionality makes automatic selection of clustering-relevant columns beneficial for simplifying subsequent analysis and reducing domain-expert effort.
  • 3CPO uses Poisson-based optimization to cluster matrix rows while simultaneously selecting the columns most relevant to the clustering result.
  • The method significantly reduces relevant columns, simplifying interpretation in real-world unsupervised scenarios.
  • The paper presents a statistically sound Poisson model, an iterative posterior-probability optimization algorithm, and experiments across diverse data domains.

2 Related Work

Prior work includes count-data clustering, preprocessing and distributional models, co-clustering, and common-subspace feature selection. 3CPO is positioned among these approaches as a method combining count-data modeling with common column selection.

  • The related-work landscape covers clustering of count data and column selection for clustering.
  • Count-data baselines preprocess rows using relative frequencies or revealed comparative advantage, while prior work questions whether transformations preserve suitable structure.
  • Dirichlet-based methods, including LDA and EDCM, provide alternative distributional approaches often associated with topic modeling and burstiness.
  • Existing combinations of count-data clustering and column selection have primarily focused on co-clustering rows and columns simultaneously.
  • Common-subspace algorithms identify a single relevant subspace using transformations such as SVD, QR decomposition, LDA, rotations, eigenvalue decompositions, or projection pursuit.
  • The motivating example distinguishes clustering-relevant columns C1, equally contributing columns C0, and uniformly distributed noise columns C−.

3 Definitions, Theory, and Algorithms

3CPO models count matrices with Poisson parameters that combine row scale, cluster-specific proportions, and three column classes. An EM-type optimization alternates expected-value, clustering, and column-partition updates, with outlier handling and convergence properties built into the framework.

  • Definitions: The model partitions matrix rows into K disjoint clusters and represents count entries using a Poisson distribution.
  • Poisson model: Expected counts use row-specific scale factors and cluster-specific column proportions, which act like cluster centroids.
  • Column partitions: Columns are divided into C1 for clustering-relevant scale-dependent features, C0 for similarly behaving clusters, and C− for uninformative columns.
  • Objective: The log-loss combines Poisson log-likelihood terms with an MDL-motivated penalty for column selection and is scale invariant when the penalty is zero.
  • Algorithm: 3CPO alternates expected-value, cluster-assignment, and column-partition updates in an EM-type procedure until convergence.
  • Column selection: The method assigns columns by maximizing their partition-specific likelihood contributions, with BIC offered as an alternative penalty.
  • Outliers: Outliers are modeled with data-set-wide background column parameters rather than cluster-specific values.
  • Convergence and complexity: 3CPO converges to a local optimum, and its worst-case complexity is O(InmK), linear in iterations, rows, columns, and clusters.

4 Experiments

Experiments across synthetic and real-world count data evaluate 3CPO against clustering and co-clustering baselines, including robustness, outlier detection, column selection, and cluster-number estimation. 3CPO often achieves leading clustering performance while selecting fewer informative columns, although performance varies across data types.

  • Comparison to traditional Clustering Algorithms: 3CPO is the top performer in eight of twelve experiments and ranks among the top three across all data sets.
  • A detailed look at text data sets: 3CPO performs best in four of five text-data scenarios and substantially outperforms BM25+SKM on BBCSports and Reuters.
  • Performance with Outlier Detection: Outlier detection improves clustering scores on every data set except Synth, while identifying uncertain samples that are difficult to assign to a specific cluster.
  • Analysis of the Column Partitions: 3CPO reduces selected columns on high-dimensional data, using approximately 32% for GeneExp and 40% for BBCSports while retaining strong clustering performance.
  • Analysis of the Column Partitions: Column selection reflects structural patterns rather than simply filtering zero-heavy columns, because zero-entry distributions remain similar across column partitions.
  • Robustness with respect to noise columns: On synthetic noise experiments, 3CPO is unaffected by added uniformly distributed noise columns, maintaining an ARI of 1.0.
  • Ablation Study: The penalty term is needed to identify columns behaving similarly across clusters; removing it increases selected columns without improving clustering.
  • Estimating the Number of Clusters: 3CPO identifies the ground-truth cluster number for Synth and BBCSports and is off by one for GeneExp, but struggles with certain tabular data.

5 Limitations

3CPO has limitations involving its Poisson-based assumptions, heuristic penalty and outlier choices, local optima, and the need to know the cluster count in advance.

  • 3CPO assumes a Poisson-based structure, which may be sub-optimal for data with substantial overdispersion or zero-inflation.The authors suggest extending the method to distributions such as the negative binomial.
  • The column-selection penalty and outlier encoding rely on heuristic choices that may lead to undesired local optima in some high-dimensional settings.
  • 3CPO currently requires the number of clusters to be known a priori, although the paper proposes a heuristic for estimating it.The authors identify more cohesive integration, such as iterative splitting, as future work.

6 Discussion and Conclusions

The paper develops Poisson-based clustering and subspace selection for count matrices, using iterative optimization to identify clusters and relevant columns. Its modeling assumptions support interpretable clustering by excluding noisy or unsuitable columns.

  • The Poisson model represents count-data entries and provides the statistical foundation for clustering and Poisson-based standardization.The model treats entries as independently drawn counts with expected values determined by row- and column-specific factors.
  • PoissonL and PoissonC provide related Poisson-based clustering procedures, with PoissonC assigning rows using the cluster that minimizes a Chi-squared value.
  • 3CPO iteratively updates expected values, row clusters, and the column partition while maximizing the likelihood until convergence.The column partition separates relevant, neutral, and noisy columns under the model.
  • The algorithm automatically discovers noisy columns when model assumptions are violated, rather than using all columns in the clustering subspace.
  • 3CPO outputs hard row clusters and a subset of columns relevant for clustering, improving interpretability by limiting the columns requiring analysis.

A.3 Scale Invariance

The clustering and column partition are invariant to multiplying the data matrix by a positive constant when the column-selection penalty is zero. A nonzero bias term can slightly favor solutions with fewer selected columns after scaling.

  • If b(X·j|K) = 0 for every column, multiplying X by any positive constant leaves the clustering and column partition unchanged.
  • The invariance follows because scaling preserves the ordering used for cluster assignments and column-partition decisions, while added terms are common across alternatives.
  • A nonzero bias term breaks exact scale invariance and slightly favors solutions with fewer columns in C1 when the scaling factor exceeds one.
  • The general-purpose distance function compares log-losses for rows treated as separate clusters versus a shared cluster.
  • When outliers are included, the clustering objective contains an outlier set, while maximum-likelihood updates retain the cluster-specific column-value rules with adaptations for shared parameters.

Appendix B Data sets

The appendix describes synthetic and real-world count-data sets spanning economics, images, texts, and biology, with characteristics including dimensions, sparsity, imbalance, and domains.

  • The benchmark comprises one synthetic and 11 real-world count data sets from economics, biology, images, and texts.
  • The collection includes monetary counts, handwritten-digit pixel counts, sports and news text data, university websites, and categorized news articles.
  • The data-set table reports rows n, columns m, clusters K, data range, sparsity, imbalance, and domain.A dagger marks data sets whose original feature count was modified.
  • GeneExp contains five tumor-related clusters, while HDendritic and MouseAtlas contain single-cell RNA-sequencing data involving human or mouse cell types.
  • The synthetic data set contains three clusters whose first four columns follow cluster-specific ratios, including (2, 3, 4, 1), (4, 1, 4, 1), and (3, 2, 4, 1).The base value v4 ranges from 1 to 30.

Appendix C Implementations

The implementation appendix identifies the software sources used for 3CPO and comparison methods and notes that supplementary experimental results are provided separately.

  • The authors implement 3CPO, PoissonL, PoissonC, and Spherical k-Means, using scikit-learn for k-Means-based approaches.
  • CROINFO, CoclustMod, and CoclustSpecMod use implementations from the coclust package, while EBML, SEBML, and TauCC use repositories referenced by their publications.
  • Complementary experimental results that did not fit into the main paper are presented in the following sections.

D.1 ACC and NMI Results

The appendix evaluates clustering with ACC and NMI alongside ARI, finding broadly similar metric trends but important differences for highly unbalanced clusters.

  • ACC and NMI supplement the ARI evaluations through additional tables covering traditional algorithms, co-clustering, and text-data analyses.
  • The different metrics generally show similar trends and rarely diverge.
  • For highly unbalanced clusters such as WebKB, ACC can be disproportionately higher because smaller clusters have less influence on the score.NMI and ARI more accurately reflect the difficulty of capturing smaller groups in this setting.

D.2 Initialization Strategies for Rk

The initialization study compares several strategies for cluster assignments Rk, finding broadly similar performance across many settings and favoring Poisson-k-Means++ in selected cases.

  • The study compares random labels, random centers, Euclidean k-Means++ seeding, full k-Means, and the proposed Poisson-k-Means++ initialization.
  • All initialization versions perform similarly on Synth, Wholesales, and GeneExp, with no clear overall winner in the other scenarios.
  • Poisson-k-Means++, random labels, and random centers all provide good solutions across the benchmark.
  • Poisson-k-Means++ is considered a reasonable choice because of better results on BBCSports and HDendritic.

D.3 Evaluation of the Runtime

3CPO has linear runtime in the number of rows and columns, with column selection making it faster than competing Poisson methods for large column counts. Its Optdigits outlier analysis also identifies unusual examples, while revealing a class-related sensitivity.

  • Runtime scaling: 3CPO is slightly slower than PoissonL and PoissonC as the number of rows increases because it updates column partitions and recalculates λR_i each iteration.PoissonL and PoissonC compute λR_i only once.
  • Runtime scaling: For large m, 3CPO becomes faster than PoissonL and PoissonC because additional columns are assigned to C0 and omitted from cluster-assignment updates.It is initially slightly slower than both Poisson baselines.
  • Runtime scaling: Co-clustering methods including CoclustMod, CROINFO, ELBM, and TauCC show exponential runtime increases as the number of columns grows.The runtime increases exponentially with m for these approaches.
  • Runtime scaling: 3CPO has linear complexity with respect to both the number of rows n and columns m.The runtime summary confirms the complexity described in Section 3.7.
  • Detected outliers: More than half of the Optdigits outliers belong to ground-truth cluster eight, although most visually examined outliers show genuinely unusual characteristics.A common unusual trait is a gap within the structure of the eight.
  • Detected outliers: Because outlier detection uses a distribution shared across clusters and row scaling by λR_i, rows with similarly valued pixels are especially prone to outlier assignment.Digit eight is particularly exposed because it requires the most active pixels.

Appendix E Estimating the Number of Clusters for k-Means-based Approaches

The appendix evaluates elbow, Silhouette, and BIC strategies for estimating k-Means cluster counts across several data sets. These standard criteria often misestimate K, whereas 3CPO provides reasonable estimates across the three highlighted cases but remains weaker on many tabular data sets.

  • Evaluation setup: Elbow, Silhouette, and BIC strategies are evaluated across K values from 2 to 30 using inertia, Silhouette, and BIC criteria.Each clustering method is run 20 times per K, and the run with the best inertia is evaluated.
  • Results by data set: On Synth, elbow suggests K ≈7, Silhouette suggests K = 2, and BIC suggests K = 30, despite the ground-truth cluster count.All standard K-estimation techniques struggle on this data set.
  • Results by data set: For GeneExp, elbow and Silhouette usually indicate K ≈6, while BIC recommends K = 12 or K = 13.The elbow and Silhouette estimates are more consistent than on Synth.
  • Results by data set: For BBCSports, elbow and Silhouette perform poorly, whereas BIC returns K within [3, 8] for every algorithm except standard k-Means.No standard strategy is a clear winner across all scenarios.
  • Results by data set: 3CPO provides a reasonable number of clusters in all three highlighted cases.These cases are Synth, GeneExp, and BBCSports.
  • Overall comparison: Across data sets, Silhouette returns K = 2 in 56 of 62 outcomes, while BIC returns K ∈{29, 30} in 44 cases.Silhouette therefore tends to underestimate K, whereas BIC often overestimates it; high Purity from BIC can coincide with lower ARI.
  • Overall comparison: 3CPO struggles to match ground-truth K on most tabular data sets but performs notably better than competitors on high-dimensional text data.It estimates the correct K for Synth and BBCSports, is off by one for BBCNews and GeneExp, and is close for 20NewsG and WebKB.
  • Overall comparison: TauCC correctly estimates K = 3.0 for Synth but averages K = 3.0 for both GeneExp and BBCSports, indicating underestimation there.It also underestimates on several other data sets, including Optdigits and MouseAtlas.
Loading 2608.23287v1…