[Exploration] Test Bregman Clustering for ShapeCART Classifier Leaf to bin assignment

[upadhyan]

ShapeCART’s induction algorithm currently uses standard K-means to assign leaves to bins. While fast, K-means relies on squared Euclidean distance ($L_2$ norm). For the ShapeCART classifier, the leaves contain probability distributions. Minimizing $L_2$ distance between distributions might be misaligned with their underlying geometry.

As a result, we might want to add Bregman clustering as an alternative to K-means. While this departs from the original ShapeCART paper, it allows us to use distance metrics that actually respect the probability simplex.

Instead of minimizing standard K-means:

$$\arg\min_{\mu} \sum_{i=1}^{n} |p_i - \mu_k|^2_2$$

We can minimize a chosen Bregman divergence $D_\phi$:

$$\arg\min_{\mu} \sum_{i=1}^{n} D_\phi(p_i, \mu_k)$$

By setting the generator function to negative entropy, we recover Kullback-Leibler (KL) divergence—the mathematically principled metric for these distributions.

Tasks

• Implement a Bregman clustering utility supporting KL-divergence.
• Add a clustering_method hyperparameter ('kmeans' vs 'bregman') to the ShapeCART class.
• Integrate the assignment step (the cluster update step remains a simple arithmetic mean, as it is the exact minimizer for Bregman divergences).
• Benchmark classification performance and runtime between 'bregman' and 'kmeans'.

this needs to be on a seperate branch and might be added to v0.2.0 if it works well.