Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.18555 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915617150337024 |
|---|---|
| author | Khaniha, Sayeh Baccelli, François |
| author_facet | Khaniha, Sayeh Baccelli, François |
| contents | This paper introduces a hierarchical clustering algorithm, the Clustroid Hierarchical Nearest Neighbor ($\mathrm{CHN}^2$), designed for datasets with a countably infinite number of points. The method builds clusters across successive levels by linking nearest-neighbor points or clusters using the clustroid distance. The properties of this algorithm make it suitable for very large datasets.
To evaluate its properties, we first apply the algorithm to the homogeneous Poisson point process, which serves as a natural null-hypothesis model with no intrinsic aggregation. In this setting, the algorithm generates a random forest that is a factor of the Poisson point process and hence unimodular. We prove that at every level, the level-$k$ graph has only finite connected components (a.s.) and derive bounds on their mean size. We also establish the existence of a limiting graph as the number of levels tends to infinity. In this limit, clusters are infinite and one-ended, which induces a natural order within each component and supports a tree-like phylogenetic interpretation.
Beyond the Poisson case, we extend the analysis to a class of Cox and more general stationary point processes without second-order descending chains (introduced here), for which analogous results hold. Simulations show that comparing these cases with the Poisson baseline allows an efficient detection of aggregation, thereby linking the stochastic-geometric analysis to practical clustering tasks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_18555 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hierarchical Clustering Algorithms on Poisson and Cox Point Processes Khaniha, Sayeh Baccelli, François Probability This paper introduces a hierarchical clustering algorithm, the Clustroid Hierarchical Nearest Neighbor ($\mathrm{CHN}^2$), designed for datasets with a countably infinite number of points. The method builds clusters across successive levels by linking nearest-neighbor points or clusters using the clustroid distance. The properties of this algorithm make it suitable for very large datasets. To evaluate its properties, we first apply the algorithm to the homogeneous Poisson point process, which serves as a natural null-hypothesis model with no intrinsic aggregation. In this setting, the algorithm generates a random forest that is a factor of the Poisson point process and hence unimodular. We prove that at every level, the level-$k$ graph has only finite connected components (a.s.) and derive bounds on their mean size. We also establish the existence of a limiting graph as the number of levels tends to infinity. In this limit, clusters are infinite and one-ended, which induces a natural order within each component and supports a tree-like phylogenetic interpretation. Beyond the Poisson case, we extend the analysis to a class of Cox and more general stationary point processes without second-order descending chains (introduced here), for which analogous results hold. Simulations show that comparing these cases with the Poisson baseline allows an efficient detection of aggregation, thereby linking the stochastic-geometric analysis to practical clustering tasks. |
| title | Hierarchical Clustering Algorithms on Poisson and Cox Point Processes |
| topic | Probability |
| url | https://arxiv.org/abs/2503.18555 |