High-Level Synthetic Data Generation with Data Set Archetypes (2024)

1 Introduction

The goal of clustering is to separate data points into groups such that points within a group a more similar to each other than to those outside the group (Cormack, (1971)). In practice, it is often not clear what constitutes a cluster (Hennig, (2015)). As a result, many practitioners evaluate cluster analysis algorithms on synthetic data (Milligan, (1980), Milligan etal., (1983), Tibshirani etal., (2001), Steinley and Brusco, (2008), Steinley and Brusco, (2011), VanMechelen etal., (2023)).

Synthetic data is valuable for two reasons. First, it clearly stipulates which data points belong to which cluster, allowing objective evaluation. Second, it allows independently manipulating different aspects of the data (such as the overlap between clusters or the variability of cluster shapes), which is critical for drawing scientific conclusions about the relative merits of different cluster analysis techniques (Milligan, (1996)).

Unfortunately, setting up benchmarks with synthetic data can be laborious. The process typically involves creating data sets for a number of different scenarios. For example, on benchmarks with convex clusters drawn from probabilistic mixture models, the scenarios may involve “clusters of very different shapes and sizes”, “highly overlapping oblong clusters”, “high-dimensional spherical clusters”, etc. (Tibshirani etal., (2001)).

Existing data generators do not cater directly to such high-level scenarios. Instead, the user must carefully tune simulation parameters to arrive at the desired scenarios (Steinley and Henson, (2005), Schubert and Zimek, (2019), Iglesias etal., (2019)). While some generators make it easy to control the overlaps between clusters, such high-level control typically does not extend to other aspects like the desired diversity of cluster shapes and sizes (Qiu and Joe, (2006), Shand etal., (2019)).

In this paper, we explore generating synthetic data directly from high level descriptions. Our Python package, repliclust, accomplishes this goal by summarizing the overall geometry of probabilistic mixture models with a few high-level parameters. We use a large language model to map a user’s verbal description of a scenario onto these parameters. Although our approach is based on ellipsoidal clusters, we have implemented two post-processing functions for generating more irregular cluster shapes. The first makes clusters non-convex by passing them through a randomly initialized neural network. The second makes a $p$-dimensional data set directional by wrapping it around the $(p+1)$-dimensional sphere through an inverse stereographic projection.

2 Generating Data from High-Level Archetypes

Our data generator repliclust is based on data set archetypes. A data set archetype is a high-level description of the overall geometry of a data set with clusters. For example, the class of all data sets with “three oblong and slightly overlapping clusters in two dimensions with some class imbalance” is a data set archetype.

We implement archetype-based generation by summarizing the overall geometry of probabilistic mixture models in terms of a few high-level parameters, as listed in Table 1. To create an archetype, users can either specify these parameters directly or verbally describe the archetype in English. To map an English description to a precise parameter setting, we use few-shot prompting of a large language model (Brown etal., (2020), OpenAI etal., (2024)).

Most of the high-level geometric parameters describing an archetype are based on what we call “max-min sampling.” In this approach, the user controls a geometric attribute by specifying a reference value and max-min ratio. In addition, a constraint ensures that the reference value and is indeed typical for every data set. For example, the aspect ratio of a cluster measures how elongated it is. The reference value aspect_ref sets the typical aspect ratio among all clusters in a data set, while aspect_maxmin sets the ratio of the highest to the lowest aspect ratio. To make sure that aspect_ref is indeed the typical aspect ratio, max-min sampling enforces the location constraint $(\prod_{j=1}^{k}\alpha_{j})^{\frac{1}{k}}=\texttt{aspect\_ref}$. Appendix A gives more details on how we manage different geometric attributes using max-min sampling.

Once an archetype has been defined, sampling concrete data sets proceeds in two steps. First, the algorithm samples a new probabilistic mixture model whose geometric structure matches the archetype. Second, we draw i.i.d. samples from this mixture model to generate a data set. Figure 1 illustrates this flow.

To accommodate use cases in which variation of an archetype’s hyperparameters (n_clusters, dim, n_samples) is desired , we have implemented a function Archetype.sample_hyperparams for generating a list of archetypes with hyperparameters sampled from Poisson distributions centered on the original values (subject to rejection sampling based on user-specified minimum and maximum values).

3 Sampling Probabilistic Mixture Models

Generating a synthetic dataset with repliclust starts with sampling a probabilistic mixture model that matches the desired archetype.

In the following sections, we give more details on each step involved in data generation.

3.1 Defining Clusters and Mixture Models

In the first four steps of data generation, repliclust models clusters as ellipsoidal probability distributions characterized by a central point. Specifically, each cluster $\mathcal{C}$ is defined by a cluster center $\mathbf{x}_{\mathcal{C}}\in\mathbb{R}^{p}$, orthogonal principal axes $\hat{\boldsymbol{u}}^{(1)}_{\mathcal{C}},\hat{\boldsymbol{u}}^{(2)}_{\mathcal{$ pointing in arbitrary directions, the lengths $\sigma^{(1)}_{\mathcal{C}},\sigma^{(2)}_{\mathcal{C}},...,\sigma^{(p)}_{$ of the principal axes, and a univariate probability distribution $f_{\mathcal{C}}(\cdot)$.

To generate an i.i.d. sample from a cluster, we 1) sample the direction $\hat{\mathbf{x}}$ from the ellipsoid defined by the cluster’s principal axes, and 2) sample the length $||\mathbf{x}||_{2}$ according to the cluster’s univariate distribution $f_{\mathcal{C}}$ (which can be one of many supported distributions including normal, lognormal, exponential, Student’s t, gamma, chi-square, Weibull, Gumbel, F, Pareto, beta, and uniform). To make the spread of each cluster depend only on the lengths of the principal axes, we normalize each univariate distribution so that the $68.2\%$ quantiles of its absolute value is unity. For example, if the univariate distribution is exponential with rate $\lambda$, we would actually sample from a re-scaled random variable $\text{Exp}(\lambda)/q_{0.682}$, where the quantile $q_{0.682}$ satisfies $\mathbb{P}(|\text{Exp}(\lambda)|\leq q_{0.682})=0.682$.²²2This rescaling puts all distributions on the same scale as the multivariate normal distribution, which natively satisfies $\mathbb{P}(|\mathcal{N}(0,1)|\leq 1)\approx 0.682$.

Figure 2(a) visualizes clusters with different base distributions. Note that using heavy-tailed distributions can lead to far outliers (not shown). By contrast, univariate distributions with bounded support give rise to clusters with crisply defined boundaries. Stretches where a probability density function vanishes give rise to concentric holes.

A mixture model (repliclust.MixtureModel) represents several clusters. Figure 2(b) shows a two-dimensional mixture model with four clusters, and a data set sampled from it. Note that our mixture models do not model class probabilities. Instead, the number of data points per cluster are drawn using max-min sampling, based on the archetype’s imbalance ratio (desired ratio between the number of data points in the most and least populous clusters). Appendix B lists the formal attributes of a mixture model.

3.2 Managing Cluster Overlaps

Managing the degree of overlaps between clusters is one of the most important tasks of a cluster generator. In repliclust, we quantify pairwise overlap between two clusters as the irreducible error rate when classifying a new data point as belonging to one of the two clusters (assuming equal class probabilities). On the level of entire datasets, the user controls overlap by specifying the maximum and minimum pairwise overlap.

The maximum overlap max_overlap states that no pair of clusters may overlap more than a certain amount. By contrast, the minimum overlap min_overlap prevents isolated clusters by enforcing that each cluster has some neighbor with which it overlaps at least min_overlap.We construct a loss function that enforces the minimum and maximum overlap conditions and optimize it using stochastic gradient descent (SGD).

In this section, we first describe our notion of pairwise overlap. Second, we explain the loss function we use to enforce the maximum and minimum overlap for an entire dataset.

3.2.1 Measuring Pairwise Overlap

Viewing clusters as probability distributions, we formally define the overlap between two clusters as twice the minimax error rate when classifying new data points using a linear decision boundary between the two clusters. Figure 3 illustrates this definition. To explain what we mean by “minimax” in this context, observe that any linear classifier $\hat{y}:\mathbb{R}^{p}\mapsto\{1,2\}$ depends on an axis $\boldsymbol{a}\in\mathbb{R}^{p}$ and threshold $c\in\mathbb{R}$ such that

$$\hat{y}(\mathbf{x})=\begin{cases}1,&\text{if $\boldsymbol{a}^{\top}\mathbf{x}$$

(1)

By definition, the minimax classifier $\hat{y}^{*}$ minimizes the worst-case loss. In symbols,

$$\max_{y}~{}\mathbb{P}(y\neq\hat{y}^{*}(\mathbf{x})|y)=\min_{\hat{y}}\max_{y}~{$$

(2)

where $y\in\{1,2\}$ is the true cluster label corresponding to a new data point $\mathbf{x}\in\mathbb{R}^{p}$. The outer minimum on the right hand side ranges over all linear classifiers $\hat{y}$, including $\hat{y}^{*}$. Rewriting (2) in terms of the classification axes $\boldsymbol{a}$ and thresholds $c$ yields

$$\boldsymbol{a}^{*},~{}c^{*}=\operatorname*{arg\,min}_{\boldsymbol{a}\in\mathbb$$

(3)

It is not hard to see that the minimax condition requires the cluster-specific error rates $\mathbb{P}(\boldsymbol{a^{*}}^{\top}\mathbf{x}>c^{*}~{}|~{}y=1)$ and $\mathbb{P}(\boldsymbol{a^{*}}^{\top}\mathbf{x}\leq c^{*}~{}|~{}y=2)$ to be equal. Consequently, the cluster overlap $\alpha$ becomes

$$\alpha=2~{}\mathbb{P}(\boldsymbol{a^{*}}^{\top}\mathbf{x}>c^{*}~{}|~{}y=1).$$

(4)

Geometrically, our definition means that two clusters overlap at level $\alpha$ if their marginal distributions along the minimax classification axis $\boldsymbol{a}^{*}$ intersect at the $1-\alpha/2$ and $\alpha/2$ quantiles. The left panel of Figure 3 highlights the probability mass bounded by these quantiles in gray.

Note that our formulation of minimax classification error explicitly does not take into account class probabilities for the clusters. Equation (2) depends only on the class-conditional probabilities.Our reasoning is that the underlying reality of each cluster depends on its class-conditional probability distribution, not the class probability.

Steinley and Henson, (2005) quantify cluster overlap by computing the full distributional overlap in $p$ dimensions. We prefer our one-dimensional notion in terms of minimax classification error, since high-dimensional Euclidean geometry exhibits a number of counterintuitive phenomena. Specifically, as $p\rightarrow\infty$, the majority of a sphere’s volume becomes concentrated in a thin shell from its surface, and so $p$-dimensional overlap goes to zero unless the marginal overlaps in each dimension approach 100% (Blum etal., (2020), Steinley and Henson, (2005)).

Computing our cluster overlap $\alpha$ requires finding the minimax classification axis $\boldsymbol{a}^{*}$. Anderson and Bahadur, (1962) describe an algorithm for computing $\boldsymbol{a}^{*}$ exactly, in the case of multivariate normal distributions. Unfortunately, their method requires computing the matrix inverse $(t\boldsymbol{\Sigma}_{1}+(1-t)\boldsymbol{\Sigma}_{2})^{-1}$ for $\text{O}(\log(1/\epsilon)$ values of $t$, where $\boldsymbol{\Sigma}_{1},\boldsymbol{\Sigma}_{2}$ are the clusters’ covariance matrices and $\epsilon$ is a numerical tolerance. To avoid these matrix inversions, we propose an approximation of the minimax classification axis based on linear discriminant analysis (LDA).

For a pair of multivariate normal clusters with means $\boldsymbol{\mu}_{1}\neq\boldsymbol{\mu}_{2}$ and the same covariance matrix $\boldsymbol{\Sigma}$, the axis $\boldsymbol{a}_{\text{\tiny{LDA}}}=\boldsymbol{\Sigma}^{-1}(\boldsymbol{\mu}_{$ minimizes the overall misclassification rate, assuming equal class probabilities (see Hastie etal., (2009)). Unfortunately, the result does not hold for unequal covariance matrices $\boldsymbol{\Sigma}_{1}\neq\boldsymbol{\Sigma}_{2}$. Thus, we propose the approximation $\boldsymbol{a}_{\text{\tiny{LDA}}}=(\frac{\boldsymbol{\Sigma}_{1}+\boldsymbol{$. Figure 4 verifies that this LDA-based approximation closely matches the exact overlap, as compared with a cruder “center-to-center" (C2C) approximation that uses the difference between the cluster centers as the classification axis (i.e., $\mathbf{a}_{\tiny{C2C}}=\boldsymbol{\mu}_{2}-\boldsymbol{\mu}_{1}$).

Theorem 1 gives a formula for computing the LDA-approximate cluster overlap. The proof is in Appendix C.

Theorem 1 (LDA-Based Cluster Overlap)

For two multivariate normal clusters with means $\boldsymbol{\mu}_{1}\neq\boldsymbol{\mu}_{2}$ and covariance matrices $\boldsymbol{\Sigma}_{1},\boldsymbol{\Sigma}_{2}$, the approximate cluster overlap $\alpha_{\text{\tiny{LDA}}}$ based on the linear separator $\boldsymbol{a}_{\text{\tiny{LDA}}}=(\frac{\boldsymbol{\Sigma}_{1}+\boldsymbol{$ is

$$\alpha_{\text{\tiny{LDA}}}=2\big{(}1-\Phi\Big{(}\frac{\boldsymbol{a}_{\text{$$

(5)

where $\Phi(z)$ is the cumulative distribution function of the standard normal distribution.Moreover, if $\boldsymbol{\Sigma}_{1}=\lambda\boldsymbol{\Sigma}_{2}$ for some $\lambda$ then $\alpha_{\text{\tiny{LDA}}}$ equals the exact cluster overlap $\alpha$.

Theorem 1 shows that cluster overlap depends on quantiles $q$ of the form

$\displaystyle q(\boldsymbol{\mu}_{1},\boldsymbol{\mu}_{2};\boldsymbol{\Sigma}_$

$\displaystyle=\frac{\boldsymbol{a}^{\top}(\boldsymbol{\mu}_{2}-\boldsymbol{\mu$

(6)

where $\boldsymbol{a}$ is a classification axis. Since these quantiles are inversely related to cluster overlap, they quantify cluster separation.

When generating synthetic data, repliclust uses Theorem 1 even when cluster distributions are non-normal. Figure 12 in Appendix D suggests that controlling overlap between non-normal distributions works well, except for distributions with bounded support (such as beta).

3.4 Making Cluster Shapes More Irregular

In many application domains, ellipsoidal center-based clusters are good models for the data. This is often the case when clusters can be characterized by a “typical” element. For example, in single-cell RNA sequencing, Chen etal., (2020) represent the differences in transcriptional activity across cell types using Gaussian mixture models. In this case, the cluster centers correspond to each cell type’s typical gene expression profile. Similarly, in deep learning, a large language model’s hidden states often form compact clusters that can effectively classify text (Howard and Ruder, (2018)), assess the truthfulness of a response (Azaria and Mitchell, (2023)), and help detect out-of-distribution inputs (Ren etal., (2023)).

However, convex clusters can be inappropriate. For example, Ester etal., (1996) developed the density-based DBSCAN algorithm specifically to handle spatial (GPS) data. Characterized by thin loops and irregular shapes, such data does not fit a center-based clustering paradigm at all. Another example is directional data lying on a sphere (Banerjee etal., (2005), Salah and Nadif, (2019)). In this case, the clusters have centers but are not convex.

To accommodate use cases where ellipsoidal clusters are inappropriate, repliclust provides two post-processing functions for creating non-convex clusters. The first,
repliclust.distort, passes a data set through a randomly initialized neural network, as shown in Figure 5. The second, repliclust.wrap_around_sphere, wraps a $p$-dimensional data set around the $(p+1)$-dimensional sphere by applying an inverse stereographic projection, as shown in Figure 6. Appendix D describes the default architecture of the neural network used in repliclust.distort.

4 Results

In this section, we first illustrate the convenience of archetype-based data generation by conducting a mock benchmark between several clustering algorithms. Second, we verify that our notion of clustering overlap effectively captures clustering difficulty (even in higher dimensions), and study the distribution of pairwise overlaps in data sets with multiple clusters.

4.2 Minimax Classification Error Captures Clustering Difficulty

In Section 3.2, we defined the overlap between two clusters in terms of the error rate of the best minimax linear classifier. We verify that this notion of overlap conveys clustering difficulty by measuring clustering performance on data sets with different degrees of overlap. For this simulation, we consider data sets with two clusters drawn from an archetype we described as “two clusters with very different shapes in $p$D”⁵⁵5This verbal description yields an archetype with parameters
{ ‘name’: ‘two_very_different_shapes_$p$d’, ‘n_clusters’: 2, ‘dim’: $p$, ‘n_samples’: 200, ‘aspect_ref’: 1.5, ‘aspect_maxmin’: 3.0, ‘radius_maxmin’: 3, ‘imbalance_ratio’: 2, ‘max_overlap’: 0.05, ’min_overlap’: 0.001, ‘distributions’: [‘normal’, ‘exponential’] } , where the dimensionality $p$ ranges across $[2,10,30,100]$. We vary max_overlap from $10^{-7}$ to 0.5, while setting min_overlap = max_overlap/10. For each overlap setting, we generate 100 distinct data sets and evaluate the average clustering performance of hierarchical clustering, quantified in terms of adjusted mutual information (AMI) and adjusted Rand index (ARI), as in the benchmark of Section 4.1. We choose hierarchical clustering because it is computationally efficient and performed well in the benchmark. We repeat this process twice, where in the second run we make clusters non-convex by applying the distort function.

Figure 9 confirms that clustering difficulty rises with increasing overlap. Figure 10 shows the same in the case of non-convex clusters, suggesting that applying distort maintains the desired relationship between overlap and clustering difficulty. Additionally, both figures show how our cluster overlap relates to the silhouette score, a popular metric for quantifying clustering difficulty (Rousseeuw, (1987), Shand etal., (2019)). At a fixed value of max_overlap, the silhouette score decreases markedly with a rise in dimensionality. This is not an artifact of our overlap measure, since plotting clustering performance vs silhouette score shows a similar dependence on dimensionality (not shown). This makes sense since the silhouette score is based on the difference of Euclidean distances, and distances between points tend to become more similar in high dimensions (Aggarwal etal., (2001)).

4.2.1 Examining the Distribution of Pairwise Overlaps

Since repliclust controls cluster overlap on the level of entire data sets by setting two global parameters (max_overlap and min_overlap), it is worthwhile to investigate the distributions of pairwise overlaps on datasets with multiple clusters. Figure 11 shows the distribution of pairwise overlaps for six data set archetypes, confirming that setting max_overlap and min_overlap effectively controls the pairwise overlaps between clusters.

5 Related Work

Simulations on synthetic data play an important role in cluster analysis. Accordingly, many synthetic data generators for cluster analysis have been proposed. However, the key idea in this paper is to specify the overall geometric characteristics of synthetic data in a high-level manner via data set archetypes. By contrast, previous data generators have put the onus on the user to design the overall geometric structure by carefully tuning lower-level properties of individual clusters.

In the following overview, we mainly focus on general-purpose generators. However, the literature has also proposed more specialized solutions to fill specific needs in the community. For example, Beer etal., (2019) present a data generator for subspace clustering, Gan and Tao, (2015) evaluates density-based clustering using a data generation process based on random walks, and Handl and Knowles, (2005) focus on creating long and thin ellipsoidal clusters in higher dimensions. None of these contributions focus on giving high-level control over the overall geometry of the data sets.

Milligan and Cooper, (1985) implements a generator for generating several clusters in up to 8 dimensions. The method enforces an upper bound on cluster overlap by limiting overlap in the first dimension, but does not otherwise provide control over high-level geometric structure.

Pei and Zaïane, (2006) present a compelling software system for generating two-dimensional clusters, which creates data sets with specified clustering difficulty “easy”, “medium” or “hard”; “easy” data consists only of spherical/convex clusters, whereas “medium” and “hard” data include curve segments and special shapes like letters of the alphabet. The generator does not offer high-level control over data set geometry except for the difficulty scale and the density of noise points to add to the data. The software comes with an appealing graphical user interface.

The popular scikit-learn library for machine learning (Pedregosa etal., (2011)) offers several functions for creating synthetic clusters. Among these, some are aimed at reproducing canonical 2D toy data sets like concentric circles and nested moons (make_moons, make_circles), while others focus on sampling multivariate normal clusters. These functions offer some valuable features, such as the ability to create datasets with informative and redundant features, as in the make_classification function. However, they do not control overall geometric characteristics of the data.

The data mining framework ELKI (Schubert and Zimek, (2019)) provides a synthetic data generator based on specifying probabilistic models in XML files. This XML-based approach makes it easy to reproduce benchmarks by sharing the underlying XML files. Drawing inspiration from this work, we have implemented an Archetype.describe function allowing users to easily share collections of data set archetypes as JSONL files.

The generators OCLUS (Steinley and Henson, (2005)) and GenRandomClust (Qiu and Joe, (2006)) focus on providing more sophisticated overlap control compared to previous generators. GenRandomClust extends the generator of Milligan and Cooper, (1985) by managing overlaps between clusters with different ellipsoidal shapes and arbitrary spatial orientations. Similar to our classification error-based notion of cluster overlap, their method finds an optimal separation direction between two clusters. To enforce the desired degree of overlap, the algorithm initially places cluster centers on a scaffold, then scales individual edges of the scaffold up or down to meet the overlap constraint. The method supports making all cluster shapes more or less elongated, but does not otherwise provide high-level control over data set geometry. Moreover, the scaling operations undertaken to manage cluster overlaps implicitly sacrifice control over cluster volumes (which, in repliclust, can be managed independently).

OCLUS (Steinley and Henson, (2005)) quantifies cluster overlap in terms of the shared density between two clusters. The generator uses analytical formulas for integrals of several interesting probability distributions (including exponential, gamma, and chi-square), thereby effectively managing overlaps between non-normal clusters. As a result, the method is limited to treating all dimensions independently, so that cluster distributions simplify as the products of marginals. The paper contains a valuable discussion of the distinction between marginal and joint cluster overlaps (of which their software supports both).

Like other existing generators, OCLUS does not aspire to helping the user establish the overall geometric characteristics of synthetic data sets. To generate a data set, the user must provide a covariance matrix for each cluster, the desired overlaps between all pairs of clusters, and a design matrix specifying which clusters overlap at all. In sum, generating 10 clusters in 10D requires supplying over 500 numbers, compared to only a handful in repliclust (or none if the user chooses to describe the archetype in English).

MDCGen (Iglesias etal., (2019) is a feature-rich generator that supports many desiderata in cluster analysis, such as overlap control, different probability distributions, subspace clusters, and the ability to add noise points. In particular, it is nice to be able to place noise points away from the clusters, which is made possible by the grid-based strategy for placing cluster centers. MDCGen does not target the overall geometric characteristics of synthetic data sets, instead giving users low-level control enabling extensive configurability. For example, managing the overlap between clusters involves setting compactness coefficients, grid granularity, and overall scale, compared to only tweaking max_overlap in repliclust.⁶⁶6max_overlap may also have to be tweaked but it can usually stay at max_overlap/10 or a similar value. In the words of the authors, “to enable covering a broad range of dataset possibilities, the parameters are multiple and some training for tuning the tool is required.”

Finally, the HAWKS generator (Shand etal., (2019)) controls cluster overlaps using an evolutionary algorithm that evolves the means and covariance matrices of multivariate normal distributions. The paper applies this framework to create data sets with a user-specified silhouette score representing clustering difficulty (Rousseeuw, (1987)). In principle, the evolutionary framework can be extended to attain desired high-level geometric characteristics. Of these, the authors consider two examples, cluster overlaps and elongations (the latter relating to our notion of cluster aspect ratio, as listed in Table 1). An interesting aspect of HAWKS is the ability to generate data sets that maximize the performance difference between two clustering algorithms. This feature is especially useful in two dimensions, since we can then visually examine the data sets to better understand when each algorithm succeeds or fails.

6 Conclusion

In this paper, we have presented an archetype-based approach to synthetic data generation for cluster analysis. Our method works by summarizing the overall geometric characteristics of a probabilistic mixture model with a few high-level parameters, and sampling mixture models subject to these constraints. To convey the convenience and informativeness of such an archetype-based approach, we have implemented a natural language interface allowing users to create archetypes purely from verbal descriptions in English. Thus, our software repliclust makes it possible to run an entire benchmark by describing the desired evaluation scenarios in English.

Although our data generator relies on creating a skeleton of convex, ellipsoidal clusters, we have implemented ways to make the cluster shapes more irregular and complex. The first method passes convex clusters through a randomly initialized neural network, making their shapes non-convex and irregular. The second method creates directional datasets by wrapping $p$-dimensional convex clusters around the $(p+1)$-dimensional sphere.

In future work, we are most interested in learning data set archetypes that mimic the geometric characteristics of real data. In application domains where multivariate Gaussians provide a good model for the data, it would suffice to fit a Gaussian mixture model, empirically measure its high-level geometric parameters (as listed in Table 1), then create a synthetic data set archetype with these parameters. For application domains with non-convex clusters, it would be interesting to implement a generalized version of this approach. We can imagine training an auto-encoder type neural network that maps non-convex clusters into a hidden space where they become multivariate Gaussian, then undoes the transformation. Defining an archetype based on the high-level geometric characteristics in the hidden space would presumably allow us to sample irregularly shaped clusters that look similar to those found in real data.

Acknowledgements

MJZ would like to acknowledge support from Matt Thomson and members of the Thomson Lab at Caltech. In addition, MJZ thanks Dante Roy Calapate for providing his computer monitor during the early stages of this project.

References

• Aggarwal etal., (2001)Aggarwal, C.C., Hinneburg, A., and Keim, D.A. (2001).On the surprising behavior of distance metrics in high dimensional space.In Vanden Bussche, J. and Vianu, V., editors, Database Theory — ICDT 2001, pages 420–434, Berlin, Heidelberg. Springer Berlin Heidelberg.
• Anderson and Bahadur, (1962)Anderson, T.W. and Bahadur, R.R. (1962).Classification into two multivariate normal distributions with different covariance matrices.The Annals of Mathematical Statistics, 33(2):420–431.
• Azaria and Mitchell, (2023)Azaria, A. and Mitchell, T. (2023).The internal state of an LLM knows when it’s lying.In Bouamor, H., Pino, J., and Bali, K., editors, Findings of the Association for Computational Linguistics: EMNLP 2023, pages 967–976, Singapore. Association for Computational Linguistics.
• Ba etal., (2016)Ba, J.L., Kiros, J.R., and Hinton, G.E. (2016).Layer normalization.arXiv preprint arXiv:1607.06450.
• Ball, (1992)Ball, K. (1992).A lower bound for the optimal density of lattice packings.International Mathematics Research Notices, 1992(10):217–221.
• Banerjee etal., (2005)Banerjee, A., Dhillon, I.S., Ghosh, J., and Sra, S. (2005).Clustering on the unit hypersphere using von mises-fisher distributions.Journal of Machine Learning Research, 6(46):1345–1382.
• Beer etal., (2019)Beer, A., Schüler, N.-S., and Seidl, T. (2019).A generator for subspace clusters.
• Blum etal., (2020)Blum, A., Hopcroft, J., and Kannan, R. (2020).Foundations of Data Science.Cambridge University Press.
• Brown etal., (2020)Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J.D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D. (2020).Language models are few-shot learners.In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H., editors, Advances in Neural Information Processing Systems, volume33, pages 1877–1901. Curran Associates, Inc.
• Chen etal., (2020)Chen, S., Rivaud, P., Park, J.H., Tsou, T., Charles, E., Haliburton, J.R., Pichiorri, F., and Thomson, M. (2020).Dissecting heterogeneous cell populations across drug and disease conditions with popalign.Proceedings of the National Academy of Sciences, 117(46):28784–28794.
• Cormack, (1971)Cormack, R.M. (1971).A review of classification.Journal of the Royal Statistical Society. Series A (General), 134(3):321–367.
• Dempster etal., (1977)Dempster, A.P., Laird, N.M., and Rubin, D.B. (1977).Maximum likelihood from incomplete data via the em algorithm.Journal of the Royal Statistical Society: Series B (Methodological), 39(1):1–22.
• Ester etal., (1996)Ester, M., Kriegel, H.-P., Sander, J., and Xu, X. (1996).A density-based algorithm for discovering clusters in large spatial databases with noise.In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, KDD’96, page 226–231. AAAI Press.
• Gan and Tao, (2015)Gan, J. and Tao, Y. (2015).Dbscan revisited: Mis-claim, un-fixability, and approximation.In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, SIGMOD ’15, page 519–530, New York, NY, USA. Association for Computing Machinery.
• Handl and Knowles, (2005)Handl, J. and Knowles, J. (2005).Improvements to the scalability of multiobjective clustering.In Proceedings of the IEEE Congress on Evolutionary Computation, CEC ’05, pages 2372–2379. IEEE.
• Harris etal., (2020)Harris, C.R., Millman, K.J., vander Walt, S.J., Gommers, R., Virtanen, P., Cournapeau, D., Wieser, E., Taylor, J., Berg, S., Smith, N.J., Kern, R., Picus, M., Hoyer, S., van Kerkwijk, M.H., Brett, M., Haldane, A., del Río, J.F., Wiebe, M., Peterson, P., Gérard-Marchant, P., Sheppard, K., Reddy, T., Weckesser, W., Abbasi, H., Gohlke, C., and Oliphant, T.E. (2020).Array programming with NumPy.Nature, 585(7825):357–362.
• Hastie etal., (2009)Hastie, T., Tibshirani, R., and Friedman, J. (2009).The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Second Edition.Springer Series in Statistics. Springer New York.
• Hennig, (2015)Hennig, C. (2015).What are the true clusters?Pattern Recognition Letters, 64:53–62.Philosophical Aspects of Pattern Recognition.
• Howard and Ruder, (2018)Howard, J. and Ruder, S. (2018).Universal language model fine-tuning for text classification.In Gurevych, I. and Miyao, Y., editors, Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 328–339, Melbourne, Australia. Association for Computational Linguistics.
• Hubert and Arabie, (1985)Hubert, L. and Arabie, P. (1985).Comparing partitions.Journal of Classification, 2(1):193–218.
• Hunter, (2007)Hunter, J.D. (2007).Matplotlib: A 2D graphics environment.Computing in Science & Engineering, 9(3):90–95.
• Iglesias etal., (2019)Iglesias, F., Zseby, T., and Ferreira, D. (2019).MDCGen: Multidimensional dataset generator for clustering.Journal of Classification, 36:599–618.
• Inan etal., (2017)Inan, H., Khosravi, K., and Socher, R. (2017).Tying word vectors and word classifiers: A loss framework for language modeling.In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net.
• LeCun etal., (2012)LeCun, Y.A., Bottou, L., Orr, G.B., and Müller, K.-R. (2012).Efficient BackProp, pages 9–48.Springer Berlin Heidelberg, Berlin, Heidelberg.
• MacQueen, (1967)MacQueen, J. (1967).Some methods for classification and analysis of multivariate observations.In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, University of California, Berkeley, pages 281–297.
• McInnes etal., (2017)McInnes, L., Healy, J., and Astels, S. (2017).hdbscan: Hierarchical density based clustering.Journal of Open Source Software, 2(11):205.
• Milligan, (1980)Milligan, G.W. (1980).An examination of the effect of six types of error perturbation on fifteen clustering algorithms.Psychometrika, 45(3):325–342.
• Milligan, (1996)Milligan, G.W. (1996).Clustering validation: Results and implications for applied analyses.In Clustering and Classification, pages 341–375.
• Milligan and Cooper, (1985)Milligan, G.W. and Cooper, M.C. (1985).An examination of procedures for determining the number of clusters in a data set.Psychometrika, 50(2):159–179.
• Milligan etal., (1983)Milligan, G.W., Soon, S.C., and Sokol, L.M. (1983).The effect of cluster size, dimensionality, and the number of clusters on recovery of true cluster structure.IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-5(1):40–47.
• Ng etal., (2001)Ng, A., Jordan, M., and Weiss, Y. (2001).On spectral clustering: Analysis and an algorithm.In Dietterich, T., Becker, S., and Ghahramani, Z., editors, Advances in Neural Information Processing Systems, volume14. MIT Press.
• OpenAI, (2023)OpenAI (2023).Openai api.https://platform.openai.com/.Accessed: 2024-09-18.
• OpenAI etal., (2024)OpenAI, Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F.L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., Avila, R., Babuschkin, I., Balaji, S., Balcom, V., Baltescu, P., Bao, H., Bavarian, M., Belgum, J., Bello, I., Berdine, J., Bernadett-Shapiro, G., Berner, C., Bogdonoff, L., Boiko, O., Boyd, M., Brakman, A.-L., Brockman, G., Brooks, T., Brundage, M., Button, K., Cai, T., Campbell, R., Cann, A., Carey, B., Carlson, C., Carmichael, R., Chan, B., Chang, C., Chantzis, F., Chen, D., Chen, S., Chen, R., Chen, J., Chen, M., Chess, B., Cho, C., Chu, C., Chung, H.W., Cummings, D., Currier, J., Dai, Y., Decareaux, C., Degry, T., Deutsch, N., Deville, D., Dhar, A., Dohan, D., Dowling, S., Dunning, S., Ecoffet, A., Eleti, A., Eloundou, T., Farhi, D., Fedus, L., Felix, N., Fishman, S.P., Forte, J., Fulford, I., Gao, L., Georges, E., Gibson, C., Goel, V., Gogineni, T., Goh, G., Gontijo-Lopes, R., Gordon, J., Grafstein, M., Gray, S., Greene, R., Gross, J., Gu, S.S., Guo, Y., Hallacy,C., Han, J., Harris, J., He, Y., Heaton, M., Heidecke, J., Hesse, C., Hickey, A., Hickey, W., Hoeschele, P., Houghton, B., Hsu, K., Hu, S., Hu, X., Huizinga, J., Jain, S., Jain, S., Jang, J., Jiang, A., Jiang, R., Jin, H., Jin, D., Jomoto, S., Jonn, B., Jun, H., Kaftan, T., Łukasz Kaiser, Kamali, A., Kanitscheider, I., Keskar, N.S., Khan, T., Kilpatrick, L., Kim, J.W., Kim, C., Kim, Y., Kirchner, J.H., Kiros, J., Knight, M., Kokotajlo, D., Łukasz Kondraciuk, Kondrich, A., Konstantinidis, A., Kosic, K., Krueger, G., Kuo, V., Lampe, M., Lan, I., Lee, T., Leike, J., Leung, J., Levy, D., Li, C.M., Lim, R., Lin, M., Lin, S., Litwin, M., Lopez, T., Lowe, R., Lue, P., Makanju, A., Malfacini, K., Manning, S., Markov, T., Markovski, Y., Martin, B., Mayer, K., Mayne, A., McGrew, B., McKinney, S.M., McLeavey, C., McMillan, P., McNeil, J., Medina, D., Mehta, A., Menick, J., Metz, L., Mishchenko, A., Mishkin, P., Monaco, V., Morikawa, E., Mossing, D., Mu, T., Murati, M., Murk, O., Mély, D., Nair, A., Nakano, R.,Nayak, R., Neelakantan, A., Ngo, R., Noh, H., Ouyang, L., O’Keefe, C., Pachocki, J., Paino, A., Palermo, J., Pantuliano, A., Parascandolo, G., Parish, J., Parparita, E., Passos, A., Pavlov, M., Peng, A., Perelman, A., deAvila BelbutePeres, F., Petrov, M., deOliveiraPinto, H.P., Michael, Pokorny, Pokrass, M., Pong, V.H., Powell, T., Power, A., Power, B., Proehl, E., Puri, R., Radford, A., Rae, J., Ramesh, A., Raymond, C., Real, F., Rimbach, K., Ross, C., Rotsted, B., Roussez, H., Ryder, N., Saltarelli, M., Sanders, T., Santurkar, S., Sastry, G., Schmidt, H., Schnurr, D., Schulman, J., Selsam, D., Sheppard, K., Sherbakov, T., Shieh, J., Shoker, S., Shyam, P., Sidor, S., Sigler, E., Simens, M., Sitkin, J., Slama, K., Sohl, I., Sokolowsky, B., Song, Y., Staudacher, N., Such, F.P., Summers, N., Sutskever, I., Tang, J., Tezak, N., Thompson, M.B., Tillet, P., Tootoonchian, A., Tseng, E., Tuggle, P., Turley, N., Tworek, J., Uribe, J. F.C., Vallone, A., Vijayvergiya, A., Voss, C., Wainwright, C., Wang,J.J., Wang, A., Wang, B., Ward, J., Wei, J., Weinmann, C., Welihinda, A., Welinder, P., Weng, J., Weng, L., Wiethoff, M., Willner, D., Winter, C., Wolrich, S., Wong, H., Workman, L., Wu, S., Wu, J., Wu, M., Xiao, K., Xu, T., Yoo, S., Yu, K., Yuan, Q., Zaremba, W., Zellers, R., Zhang, C., Zhang, M., Zhao, S., Zheng, T., Zhuang, J., Zhuk, W., and Zoph, B. (2024).Gpt-4 technical report.
• Pedregosa etal., (2011)Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E. (2011).Scikit-learn: Machine learning in Python.Journal of Machine Learning Research, 12:2825–2830.
• Pei and Zaïane, (2006)Pei, Y. and Zaïane, O. (2006).A synthetic data generator for clustering and outlier analysis.Technical report, University of Alberta, Edmonton.
• Qiu and Joe, (2006)Qiu, W. and Joe, H. (2006).Generation of random clusters with specified degree of separation.Journal of Classification, 23:315–334.
• Ren etal., (2023)Ren, J., Luo, J., Zhao, Y., Krishna, K., Saleh, M., Lakshminarayanan, B., and Liu, P.J. (2023).Out-of-distribution detection and selective generation for conditional language models.
• Rousseeuw, (1987)Rousseeuw, P. (1987).Silhouettes: a graphical aid to the interpretation and validation of cluster analysis.Journal of Computational and Applied Mathematics, 20:53–65.
• Salah and Nadif, (2019)Salah, A. and Nadif, M. (2019).Directional co-clustering.Advances in Data Analysis and Classification, 13(3):591–620.
• Sander etal., (1998)Sander, J., Ester, M., Kriegel, H.-P., and Xu, X. (1998).Density-based clustering in spatial databases: The algorithm gdbscan and its applications.Data Mining and Knowledge Discovery, 2(2):169–194.
• Schubert etal., (2017)Schubert, E., Sander, J., Ester, M., Kriegel, H.P., and Xu, X. (2017).Dbscan revisited, revisited: Why and how you should (still) use dbscan.ACM Trans. Database Syst., 42(3).
• Schubert and Zimek, (2019)Schubert, E. and Zimek, A. (2019).ELKI: A large open-source library for data analysis - ELKI release 0.7.5 “Heidelberg”.CoRR, abs/1902.03616.
• Shand etal., (2019)Shand, C., Allmendinger, R., Handl, J., Webb, A., and Keane, J. (2019).Evolving controllably difficult datasets for clustering.In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’19, pages 463–471. ACM.
• Shi and Malik, (1997)Shi, J. and Malik, J. (1997).Normalized cuts and image segmentation.Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 731–737.
• Steinley and Brusco, (2008)Steinley, D. and Brusco, M.J. (2008).Selection of variables in cluster analysis: An empirical comparison of eight procedures.Psychometrika, 73(1):125–144.
• Steinley and Brusco, (2011)Steinley, D. and Brusco, M.J. (2011).Evaluating mixture modeling for clustering: recommendations and cautions.Psychological Methods, 16(1):63–79.
• Steinley and Henson, (2005)Steinley, D.L. and Henson, R. (2005).Oclus: An analytic method for generating clusters with known overlap.Journal of Classification, 22:221–250.
• Tibshirani etal., (2001)Tibshirani, R., Walther, G., and Hastie, T. (2001).Estimating the number of clusters in a data set via the gap statistic.Journal of the Royal Statistical Society: Series B (Statistical Methodology), 63(2):411–423.
• vander Maaten and Hinton, (2008)vander Maaten, L. and Hinton, G. (2008).Visualizing data using t-sne.Journal of Machine Learning Research, 9(86):2579–2605.
• VanMechelen etal., (2023)VanMechelen, I., Boulesteix, A.-L., Dangl, R., Dean, N., Hennig, C., Leisch, F., Steinley, D., and Warrens, M.J. (2023).A white paper on good research practices in benchmarking: The case of cluster analysis.WIREs Data Mining and Knowledge Discovery, 13(6):e1511.
• Vinh etal., (2010)Vinh, N.X., Epps, J., and Bailey, J. (2010).Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance.Journal of Machine Learning Research, 11(95):2837–2854.
• Virtanen etal., (2020)Virtanen, P., Gommers, R., Oliphant, T.E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., van der Walt, S.J., Brett, M., Wilson, J., Millman, K.J., Mayorov, N., Nelson, A. R.J., Jones, E., Kern, R., Larson, E., Carey, C.J., Polat, I., Feng, Y., Moore, E.W., VanderPlas, J., Laxalde, D., Perktold, J., Cimrman, R., Henriksen, I., Quintero, E.A., Harris, C.R., Archibald, A.M., Ribeiro, A.H., Pedregosa, F., van Mulbregt, P., and SciPy 1.0 Contributors (2020).SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python.Nature Methods, 17:261–272.

Appendix A

We give more detail on how repliclust manages various geometric attributes using max-min parameters. Table 4 lists all geometric attributes managed with max-min sampling and names the corresponding parameters in repliclust. The reference value for each geometric parameter serves as a location constraint, while the max-min ratio determines the spread. A constraint ensures that the distribution of geometric parameters within a data set is similar across data sets drawn from the same archetype.

To enforce the attribute-specific constraints, repliclust samples new values of a geometric parameter in pairs. The first value is randomly drawn from a triangular distribution whose mode and endpoints are determined from the typical value and max-min ratio. The second value is then deterministically computed to maintain the constraint. For reference, see the sample_with_maxmin function in the maxmin.utils module (Version 1.0.0 of repliclust).

Appendix B

Table 5 lists the formal attributes of a mixture model in repliclust. A data set archetype provides a way to randomly sample mixture models with similar overall geometric characteristics. Thus, an archetype implicitly defines a probability distribution over the attributes in Table 5.

Appendix C

We prove Theorem 1 of Section 3.2. Additionally, we provide an analogous result for the cruder “center-to-center” approximation of cluster overlap.

Next, suppose that $\boldsymbol{\Sigma}_{1}=\lambda\boldsymbol{\Sigma}_{2}$ for some $\lambda$. In this case, maximum likelihood classification results in a linear decision boundary that coincides with the LDA solution. Hence, the minimax-optimal linear classifier uses the LDA-based classification axis $\boldsymbol{a}_{\text{\tiny{LDA}}}$.

Proof. The proof proceeds along the same lines as the proof of Theorem 1, except that the classification axis is $\boldsymbol{\mu}_{2}-\boldsymbol{\mu}_{1}$. If both covariance matrices are multiples of the identity matrix, $\boldsymbol{\mu}_{2}-\boldsymbol{\mu}_{1}$ is a scalar multiple of the LDA-based classification axis $\boldsymbol{a}_{\text{\tiny{LDA}}}$. Hence, the second part of Theorem 1 kicks in to establish equality between $\alpha_{\text{\tiny{C2C}}}$ and the exact overlap.

Appendix D

Figure 12 visualizes two-dimensional data sets created from the same archetype but with different radial probability distributions. The results suggest that pegging the 68.15% quantile of the radial distribution at unity leads to satisfactory overlap control for distributions with infinite support. However, for distributions with bounded support (such as the beta distribution), this approach leads to greater separation between the clusters, as shown in the rightmost column of Figure 12.

Appendix E

The default architecture for the neural network used in the distort function of Section 3.4 is a feed-forward network consisting (in order) of a linear embedding, 16 repeated feed-forward blocks (each consisting of a fully connected linear layer followed by layer normalization and Tanh activation), and a linear projection. Importantly, we tie the weights of the embedding and projection layers, so that the projection weights are the transpose of the embedding weights (Inan etal., (2017)). The default hidden dimensionality is 128, so that the embedding layer maps a data set archetype’s dimension to 128. The internal feed-forward blocks preserve this hidden dimension, and the final projection layer maps it back to the archetype’s dimension.

Appendix F

Below we list the prompt templates (including few-shot examples) used in Version 1.0.0 of repliclust. Up-to-date versions are available in the code base (see repliclust.org).

1. Prompt template mapping archetype description to high-level geometric parameters: