# Generative Histogram-Based Model Using Unsupervised Learning

Parisa Rastin, Guénaël Cabanes, Rosanna Verde, Younès Bennani, Thierry Couronne

► To cite this version:

Parisa Rastin, Guénaël Cabanes, Rosanna Verde, Younès Bennani, Thierry Couronne. Generative Histogram-Based Model Using Unsupervised Learning. ICONIP 2019, Dec 2019, Sydney (Australia), Australia. pp.634-646, 10.1007/978-3-030-36718-3_53. hal-02994819

HAL Id: hal-02994819

https://hal.science/hal-02994819v1

Submitted on 22 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Generative Histogram-based Model using
Unsupervised Learning

Parisa Rastin<fnref n="1" />, Guénaël Cabanes<fnref n="2" />, Rosanna Verde<fnref n="3" />, Younès Bennani<fnref n="2" />, and
Thierry Couronne

**Abstract.** This paper presents a new generative unsupervised learning algorithm based on a representation of the clusters distribution by histograms. The main idea is to reduce the model complexity through cluster-defined projections of the data on independent axes. The results show that the proposed approach performs efficiently compared with other algorithms. In addition, it is more efficient to generate new instances with the same distribution than the training data.

**Keywords:** Unsupervised learning · Clustering · Generative model · Histogram distribution.

## 1 Introduction

Unsupervised learning is a branch of machine learning able to compute a model of the data distribution without any external information. Unsupervised learning is a very important tool for data analysis and popular application have been proposed in various field such as marketing [13], bioinformatic [1] or fraud detection [4]. One of the most common family of unsupervised learning approaches are clustering algorithms. Their task is to detect groups (clusters) of objects (instances) having similar features, compared to objects belonging to different groups. Some clustering algorithms compute a model representing the distribution of each cluster. The simplest models compute only the mean vector of each cluster: the most cited being the K-means family [9]. Others propose a more complex model, for example the Gaussian Mixture Model (GMM) [12] which assumes a mixture of Gaussian functions, usually one for each cluster, as model of the data distribution. Other clustering algorithms do not propose an explicit model of the data distribution: they perform the clustering of the training data, but in order to classify new objects, they require a comparison with all the objects of the training data-set. These algorithms are, for example, density-based algorithms such as BDSCAN [7], or hierarchical clustering approaches such as the Hierarchical Agglomerative Clustering [11].

<footnote n="1">¹ LORIA, UMR-CNRS 7503
University of Lorraine, Nancy, France</footnote>

<footnote n="2">² LIPN, UMR-CNRS 7030
UP13, Sorbonne Paris Cité, Villetaneuse, France</footnote>

<footnote n="3">³ Dip. Matematica e Fisica
Università della Campania Luigi Vanvitelli, Naples, Italy</footnote>
Among the wide panel of family of clustering algorithms, we are interested in probabilistic approaches. The main idea is to be able to predict, given a set of observations, a probability distribution over a set of classes, instead of only delivering the most similar class that the observation should belong to. Probabilistic approaches can be divided into two families. Generative approaches compute, given the data $X$ and the clusters labels $C$, a statistical model of the joint probability distribution on $X \times C$, $P(X, C)$, the probabilities to observe an object $x$ in a cluster $c$ [10]. These models are called generative because the join probability distribution can be used to generate new samples following the same distribution as the training data. On the contrary, discriminative models compute the conditional probability of the cluster label $C$, given an object $x$: $P(C|X=x)$ [10]. Such approaches can compute membership probabilities, but are not suited to estimate the generative functions. Most of the time, the Expectation-Maximization (EM) algorithm [5] is used to estimate the parameter of the models.

A popular algorithm for discriminative clustering is Fuzzy C-Mean (FCM) [3]. FCM is similar to K-Means algorithm [9], except for the assignment of the objects to the clusters according to a membership value. First, the number of clusters must be chosen by the user and the membership values are initialized randomly, then the centroid of each cluster is computed based on the memberships' values (maximization step) and new memberships are computed based on the centroids (expectation step). These two steps are repeated until convergence. In Fuzzy C-Mean, the centroid of a cluster is the mean of all data points, weighted by their degree of membership to the cluster. When a generative approach is preferable, one of the most used algorithm is the abovementioned Gaussian Mixture Model (GMM) [12]. Again, the number of clusters is given as input and the model's parameters (the weight, the center and the covariance matrix of each Gaussian) are computed by alternating expectation and maximization steps.

GMM can produce very good results when the clusters' distributions are not too different from Gaussian distributions. When it is not the case, however, the data distribution cannot be modelled with a small number of Gaussian. Few approaches have been proposed to try to compute more general models. The algorithm presented in [2] is based on a (usually Gaussian) kernel density estimation made under a couple of constraints. In [16], the authors propose approaches based on different family of distributions (e.g. mixed logit model). As far as we are aware, there is no work using histograms as a true non-parametric representation of the data distribution. Histograms are a simple way of describing the empirical distribution as observed from the data. We propose here a non-parametric generative approach based on the EM algorithm, able to compute a histogram mixture model, allowing to deal with a much wider range of distributions than in previous algorithms.

The remainder of this paper is organized as follows. Section 2 describes the proposed approach and a complexity analysis is given in Section 3. The experimental protocol and the obtained results are detailed in Section 4. Finally, Section 5 concludes the paper and introduces future works.
## 2 General Framework

In this section, we introduce a new histogram-based clustering algorithm. The principle is to represent each cluster k with a set $H_k$ of d histograms where d is the number of dimensions of the data-set X. $H_k$ is a distribution represented with d histograms: $H_k = (h_{k,1}, ..., h_{k,d})$. Each $h_{k,l}$ is an empirical distribution and it is represented by a sequence of B continuous and no-overlapped intervals (or bins) $I_{k,l}^j$ with an associated weight (or relative frequency) $\pi_{k,l}^j$, for $j = 1, ..., B$, such that $\sum_{j=1}^B \pi_{k,l}^j = 1$:

$$h_{k,l} = [(I_{k,l}^1, \pi_{k,l}^1, ..., (I_{k,l}^B, \pi_{k,l}^B))]. \quad (1)$$

Let $X = (x_1, x_2, ..., x_n)$ be a data-set of N independent observations from a mixture of K distributions of dimension d, each represented by a set $H_k$ of d histograms, and let $Z = (z_1, z_2, ..., z_n)$ be the latent variables that determine the component (i.e. the cluster) from which the observation originates.

The aim is to estimate the unknown parameters of the histograms:

$$\theta = (\theta_1, ..., \theta_K) \quad (2)$$

with

$$\theta_k = (\tau_k, h_{k,1}, ..., h_{k,B}). \quad (3)$$

The expected values of $\theta$ minimize the following likelihood function :

$$L(\theta; X, Z) = p(X, Z | \theta). \quad (4)$$

This minimization can be done via an Expectation - Maximization (EM) algorithm.

### 2.1 Maximization step

In the Maximization step of the algorithm, the parameters of the histogram distribution are updated in order to maximize the expected value of the likelihood function of the model based on the current membership matrix of the data X, as computed is the Expectation step. To compute the membership matrix, however, we expect the histograms ($h_{k,1}, ..., h_{k,d}$) in $H_k$, for each cluster (component) k, to be independents from each other.

As each histogram $h_{k,l}$ represents a distribution along one dimension, we compute a set of d new independent axes and project the data belonging in cluster k in this new space. The projection is performed via Weighted Principal Component Analysis (WPCA [19]) to compute the eigenvectors of the covariance matrix of the data, weighed by their membership values for cluster k. We obtain d new independent axes representing the principal components of the data in cluster k, according to their membership values.

The data are then projected on each of the d new axes and d histogram are computed. To compute the parameters of an histogram $h_{k,l}$, the range between
the minimal and the maximal value of the data projected on axis $l$ is divided into $B$ equal intervals (bins) $I_{k,l}^j, j \in (1, \dots, B)$. For each of these interval, the relative frequency $\pi_{k,l}^j$ is computed as the normalized sum of the membership for cluster $k$ of the objects projected in this interval:

$$ \pi_{k,l}^j = \frac{\sum_{i/x_i^l \in I_{k,l}^j} T_{k,i}}{\sum_{j=1}^B \sum_{i/x_i^l \in I_{k,l}^j} T_{k,i}} \qquad (5) $$

with $x_i^l$ the value on the $i^{st}$ data point projected on axis $l$ and $T_{k,i} := P(Z_i = k | X_i = x_i; \theta)$ is the membership for cluster $k$ of an observation $x_i$, according the current parameters $\theta$, as computed in the Expectation step.

The mixing parameters $\tau_k$ for each cluster $k$ are simply computed as the sum of the membership values for this cluster:

$$ \tau_k = \sum_{i=1}^{N} T_{k,i}. \qquad (6) $$

This process is repeated for each cluster $k$, in order to obtain the values of all the parameters in $\theta$.

## 2.2 Expectation step

The expectation step computes the $K \times N$ membership matrix $T = [T_{k,i}]$, such as $T_{k,i} := P(Z_i = k | X_i = x_i; \theta)$, with $K$ the number of clusters (components) and $N$ the number of observations in the training data-set.

The probability $P_k(x_i^l) := P(X_i^l = x_i^l | Z_i = k; \theta)$ of an unique value $x_i^l$ for a distribution represented by a histogram $h_{k,l}$ is simply the weight $\pi_{k,l}^j$ (we recall that $\sum_{j=1}^B \pi_{k,l}^j = 1$ and $\pi_{k,l}^j \in [0, 1]$) so that $x_i^l$ is in the corresponding interval $I_{k,l}^j$:

$$ P_k(x_i^l) = \pi_{k,l}^j \text{ with } j | x_i^l \in I_{k,l}^j \qquad (7) $$

As the representation space of each cluster have been redefined such as the new axes are independents, the multivariate probability of an observation $x_i$ for the full distribution $H_k$ associated to cluster $k$ is proportional to the product of the individual probabilities and can be computed with the Bayesian formalism:

$$ T_{k,i} = \frac{\tau_k \prod_{l=1}^{d} P_k(x_i^l)}{\sum_{k=1}^{K} \tau_k \prod_{l=1}^{d} P_k(x_i^l)} \qquad (8) $$

Note that this equation is only valid because of the WPCA projections computed for each cluster in the Maximization step. Without this trick, we would have needed to compute the full multivariate histogram, with a weight $\pi$ associated to each combination of intervals in all dimensions. The number of parameters to learn would have been in $O(B^d)$, instead of $O(B.d)$ in the proposed approach.
## 2.3 Proposed algorithm

The approach is described in Algorithm 1. It takes as input the data X, the expected number of components (clusters) K and the number of intervals (bins) B for the histograms.

**Algorithm 1** Histogram-based generative clustering

**Input:** X, K and B.

**Output:** Adapted parameters θ.

1: Initialize $T = [T_{k,i}]$ and $\tau_k$ for each component $k$.

2: **repeat**

**MAXIMIZATION STEP**

3: **for each** component $k$ **do**

4: Compute a WPCA projection of X weighted by $T_{k,\cdot}$.

5: Compute the histogram distributions on each WPCA axes $l$:

$$ \pi_{k,l}^j = \frac{\sum_{i/x_i^l \in I_{k,l}^j} T_{k,i}}{\sum_{j=1}^B \sum_{i/x_i^l \in I_{k,l}^j} T_{k,i}} $$

6: Compute the mixing parameter $\tau_k$:

$$ \tau_k = \sum_{i=1}^{N} T_{k,i} $$

**EXPECTATION STEP**

7: **for each** component $k$ and instance $x_i \in X$ **do**

8: Compute the membership $T_{k,i}$:

$$ T_{k,i} = \frac{\tau_k \prod_{l=1}^{d} P_k(x_i^l)}{\sum_{k=1}^{K} \tau_k \prod_{l=1}^{d} P_k(x_i^l)} $$

with $P_k(x_i^l) = \pi_{k,l}^j$ for $j | x_i^j \in I_{k,l}^j$.

9: **until** convergence.

The mixing parameters are initialized such that $\tau_k = N/K$ for $k = 1, \dots, K$, with N the number of instances in the training data-set. The membership matrix $T = [T_{k,i}]$ can be initialized randomly, but we choose to optimize the initialization using a Fuzzy C-means algorithm [3] trained on the data with a number of cluster equal to K. Fuzzy C-means computes a membership matrix $T_{init}$ based on the distances between data points and clusters' centers. After normalization, it is a good starting point for the proposed model.
## 3 Complexity

In this section we analyze the complexity of the proposed approach in comparison to a classical Gaussian Mixture Model (GMM).

In term of time complexity, the maximization step of the proposed algorithm requires, for each cluster, the computation of the covariance matrix ($O(K.N.d^2)$), with *K* the number of clusters, *N* the data size and *d* the number of dimensions) and the computation of the eigenvectors of the covariance matrix, usually around $O(d^3)$, though some decomposition approaches are known to have a lower complexity. The projection is in $O(N.d)$, and the histograms computation have a complexity of $O(B.N.d)$, with *B* the number of chosen bins. The expectation step requires the computation of a probability for each histogram in each cluster, for each data point, leading to a complexity of $O(K.B.N.d)$. The number of bins *B* being a constant user-chosen parameter, the overall complexity is $O(K.N.d^3)$. It is the same complexity as the classical EM algorithm used to compute a full GMM [5]. Non-generative approaches, such as K-means, have a lower complexity regarding the number of dimension ($O(K.N.d)$), because of the simplicity of the produced model.

In term of model complexity, the proposed approach is actually at least as parsimonious as a full GMM. Indeed, thanks to the projections, for each cluster only *d* histograms (size *B*) are computed, leading to global model size in $O(B.K.d)$. A full GMM is composed of *K* mean vectors (size *d*) and *K* covariance matrices (size $d^2$), for a model complexity of $O(K.d^2)$. If we chose a number of bins $B < d$, the histograms model is at the same time smaller than the GMM and not limited to a family of distributions. In addition, in most cases, *B* does not need to be large, values between 5 to 20 have shown very good results in our preliminaries experiments. Note that a GMM computing only the diagonal covariance (i.e. the variance in each dimension) results in a more compact model ($O(K.d)$), at the expense of ignoring all possible correlations between features.

The proposed approach is therefore no more complex than a GMM, both in term of computation and model complexity. However, the histograms model should be a better representation of the data distribution than a GMM, because it can model a much larger range of distributions.

## 4 Experimental Validation

In this section, we compare experimentally the proposed approach with several classical algorithms. We compared it with two well-known "discriminative" approaches, K-means [9] and Fuzzy C-means (FCM) [3]. As the proposed approach initializes its membership matrix using FCM, it is important to check that the obtained clustering improves from the initial partition. We also compared with two generative approaches, a Gaussian Mixture Model learning only the diagonal covariance (GMM diag) and Gaussian Mixture Model learning the full covariance matrix (GMM full). In order to validate the proposed algorithm, we tested two criteria in particular: the quality of the algorithm for the clustering task and
its ability to generate new samples with the same distribution as the training data.

In order to evaluate these criteria, the algorithms are applied on sixteen data-sets. Eight of them are artificial data-set generated from various distributions (Section 4.1). Knowing the distributions allows an easier interpretation of the experimental results. In real data-sets, however, the range of possible distributions are usually more diverse, thus we also tested the algorithms on eight real data-sets with various sizes, dimensions and expected number of clusters.

To test the clustering quality of the proposed algorithm in comparison to its competitors, we chose two external quality indexes (see Section 4.2) able to compare the obtained clustering to an expected partition of the data. Internal quality indexes, which estimate the compactness and the separability of the clusters, are usually biased toward hyper-spherical distributions and are, therefore, not well adapted to the type of approaches proposed in this paper.

To test the quality of the generated samples, we compare the dissimilarity between the distribution of the original training data and the distribution of the generated data (Section 4.3). The computation of the dissimilarity measures between each pair of empirical distributions is based on the Wasserstein metric [14], seen as a solution of an optimal transport problem.

In all experiments, we chose a value of K matching the expected number of clusters and we fixed the number of bins to $B = 20$. All experiments have been done using Python 3.7, with the *scikit-learn* package for the classical algorithms and the quality indexes and the *Python Optimal Transport* package for the computation of the Wasserstein distance.

## 4.1 Data-sets

Sixteen data-sets have been used for the experiments. They were chosen to propose a high diversity of challenges in order to validate the proposed approach in comparison to classical algorithms. Table 1 summarizes the data-sets characteristics.

Eight of them are artificial data. “Gauss 1” and “Gauss 2” data-sets are structured with several Gaussian clusters, in respectively 3 and 50 dimensions. “Rect 1” and “Rect 2” have rectangular clusters in two dimensions, with some overlap between clusters. Clusters in “Comets” and “Gradients” are drawn from gamma distributions, resulting in non-symmetrical shapes. Finally, two data-sets with non-linearly separable clusters in three dimensions, “Atom” and “Chainlink” were chosen from the Fundamental Clustering Problems Suite (FCPS) [17].

The eight real data-sets come from the Open Machine Learning (OpenML) data base [18]. The data-sets were chosen for their variety of shapes, size, dimensions and number of expected clusters. We selected four data-sets with a small number of objects, under 500, as it is usually more difficult to compute the empirical distribution in such case. We also tested the approaches on bigger data-sets, from 5000 to 20000 objects, with a number of dimensions going up to 40 and a number of expected clusters ranging from 5 to 26.
<table><caption>**Table 1.** Data-sets description</caption><thead><tr><th>Name</th><th>Size</th><th>Dimension</th><th>#Clusters</th><th>Type</th></tr></thead><tbody><tr><td>Gauss 1</td><td>10000</td><td>3</td><td>3</td><td>Artificial</td></tr><tr><td>Gauss 2</td><td>10000</td><td>50</td><td>10</td><td>Artificial</td></tr><tr><td>Rect 1</td><td>3000</td><td>2</td><td>3</td><td>Artificial</td></tr><tr><td>Rect 2</td><td>3000</td><td>2</td><td>3</td><td>Artificial</td></tr><tr><td>Comets</td><td>3000</td><td>2</td><td>3</td><td>Artificial</td></tr><tr><td>Gradients</td><td>3000</td><td>2</td><td>3</td><td>Artificial</td></tr><tr><td>Atom</td><td>800</td><td>3</td><td>2</td><td>Artificial</td></tr><tr><td>Chainlink</td><td>1000</td><td>3</td><td>2</td><td>Artificial</td></tr><tr><td>Ecoli</td><td>336</td><td>7</td><td>2</td><td>Real</td></tr><tr><td>Letter</td><td>20000</td><td>16</td><td>26</td><td>Real</td></tr><tr><td>Page-blocks</td><td>5473</td><td>10</td><td>5</td><td>Real</td></tr><tr><td>Satimage</td><td>6430</td><td>36</td><td>6</td><td>Real</td></tr><tr><td>Seeds</td><td>210</td><td>7</td><td>3</td><td>Real</td></tr><tr><td>Texture</td><td>5500</td><td>40</td><td>11</td><td>Real</td></tr><tr><td>Transplant</td><td>131</td><td>3</td><td>2</td><td>Real</td></tr><tr><td>Galaxy</td><td>323</td><td>4</td><td>2</td><td>Real</td></tr></tbody></table>

## 4.2 Quality

Evaluating the performance of a clustering algorithm is not as trivial as counting the number of errors or the precision and recall of a supervised classification algorithm. A popular strategy is to evaluate if the obtained clustering defines separations of the data similar to some ground truth set of classes [6].

In this paper, we used two external quality indexes which provide a measure of similarity between the cluster assignment proposed by the algorithms and the "true" labels, when they are known. Here we evaluate the clustering results using the Adjusted Rand Index (ARI) [8] and the Normalized Mutual Information score (NMI) [15]. These two indexes were computed for each data-set and each algorithm. We also computed a global measurement score following [20]:

$$ Score(A_i) = \frac{1}{N_d} \sum_j \frac{Ind(A_i, X_j)}{\max_i Ind(A_i, X_j)} \quad (9) $$

where Ind($A_i$, $X_j$) indicates the quality index value of algorithm $A_i$ for data-set $X_j$ and $N_d$ the number of tested data-sets. This score gives an overall evaluation of the performance of each approach relatively to the others. A value of 1 means that the approach is always the more efficient regarding the quality index. The lower the values in [0, 1], the less efficient is the algorithm in comparison to its competitors. The results are very similar between the two indexes and we chose to show here only the results obtained for the ARI index (Table 2).

The quality of the proposed approach is either comparable to the classical approaches, especially when the clusters' distributions follow a Gaussian law ("Gauss 1" and "Gauss 2"), or better than the other algorithms. In average, generative models perform better than K-means or Fuzzy C-means (FMC).
<table><caption>**Table 2.** Adjusted Rand Index (ARI) for each data-set and each algorithm.</caption><thead><tr><th>Data-set</th><th>K-means</th><th>FCM</th><th>GMM diag</th><th>GMM full</th><th>Proposed</th></tr></thead><tbody><tr><td>Gauss 1</td><td>0.97</td><td>0.97</td><td>0.97</td><td>0.97</td><td>0.97</td></tr><tr><td>Gauss 2</td><td>1.00</td><td>1.00</td><td>1.00</td><td>1.00</td><td>0.98</td></tr><tr><td>Rect 1</td><td>0.77</td><td>0.72</td><td>0.99</td><td>0.98</td><td>1.00</td></tr><tr><td>Rect 2</td><td>0.68</td><td>0.68</td><td>0.49</td><td>0.68</td><td>0.80</td></tr><tr><td>Comets</td><td>0.65</td><td>0.67</td><td>0.65</td><td>0.94</td><td>0.92</td></tr><tr><td>Gradients</td><td>0.81</td><td>0.78</td><td>0.94</td><td>0.85</td><td>0.96</td></tr><tr><td>Atom</td><td>0.18</td><td>0.22</td><td>0.02</td><td>0.03</td><td>0.72</td></tr><tr><td>Chainlink</td><td>0.09</td><td>0.09</td><td>0.91</td><td>0.91</td><td>0.99</td></tr><tr><td>Ecoli</td><td>0.23</td><td>0.53</td><td>0.00</td><td>0.37</td><td>0.72</td></tr><tr><td>Letter</td><td>0.15</td><td>0.00</td><td>0.11</td><td>0.18</td><td>0.19</td></tr><tr><td>Page-blocks</td><td>0.10</td><td>0.01</td><td>0.06</td><td>0.19</td><td>0.22</td></tr><tr><td>Satimage</td><td>0.53</td><td>0.53</td><td>0.50</td><td>0.47</td><td>0.51</td></tr><tr><td>Seeds</td><td>0.77</td><td>0.77</td><td>0.68</td><td>0.72</td><td>0.78</td></tr><tr><td>Texture</td><td>0.51</td><td>0.47</td><td>0.44</td><td>0.69</td><td>0.75</td></tr><tr><td>Transplant</td><td>0.61</td><td>0.77</td><td>0.74</td><td>0.59</td><td>0.85</td></tr><tr><td>Galaxy</td><td>0.27</td><td>0.27</td><td>0.27</td><td>0.22</td><td>0.33</td></tr><tr><td><strong>Score</strong></td><td><strong>0.70</strong></td><td><strong>0.66</strong></td><td><strong>0.70</strong></td><td><strong>0.82</strong></td><td><strong>0.99</strong></td></tr></tbody></table>

We also see a clear increase of quality with the increase of generality of the model, a full Gaussian Mixture Model (GMM) being better than the diagonal GMM and the proposed approach being in average better than the GMM.

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Visual examples of clustering results obtained by various algorithms. Top to bottom: "Gauss 1", "Gradients", "Comets", "Rect 1" and "Atom".</figcaption></figure>
It is interesting to note that the proposed algorithm, despite using a FMC to initialize its membership matrix, shows much better clustering results than FMC. The GMM approaches are very good for many of the tested data-sets, but sometime fail to produce the desired clustering (remarkable examples are data-sets "Atom" and "Ecoli"). In this experiment, there is no clear impact of the number of observations, dimensions or clusters on the quality of the obtain clustering. We suppose that the complexity of the data structure, in term of clusters' distributions and overlapping, plays a much more important role.

Figure 1 illustrates the observed differences in quality among the algorithms. In these examples, some of the algorithms' limitations are clearly visible. In particular, FCM is suited for hyper-spherical clusters such as in "Gauss 1", but lack the flexibility to detect correctly clusters from other type of distributions. Diagonal GMM is slightly better, but is unable to model correlations between features ("Comets", "Rect 1"). Finally, the full GMM is more efficient, but have difficulties with far-from-Gaussian distributions (e.g. "Rect 1" or "Atom").

## 4.3 Generation of new samples

Generative models are powerful tools to model the data distribution and can be used to generate new samples following the same distribution. As the proposed approach compute an estimation of the empirical distribution instead of a mixture of Gaussian, we expect that its ability to generate new data is better than the GMM. To test this assumption, we generated samples following the distributions learn from the sixteen training data-sets, and we compared the distribution of the generated data to the distribution of the original data. The similarity between the two distribution, based on the data, were computed with a Earth mover's distance (EMD) also known as the Wasserstein metrics. The EMD between two distributions is proportional to the minimum amount of work required to convert one distribution into the other [14]. The Wasserstein distance between two distributions u and v is:

$$l_1(u, v) = \inf_{\pi \in \Gamma(u, v)} \int_{\mathbb{R} \times \mathbb{R}} |x - y| d\pi(x, y) \quad (10)$$

where $\Gamma(u, v)$ is the set of (probability) distributions on $\mathbb{R} \times \mathbb{R}$ whose marginals are u and v on the first and second factors respectively. Note that the input distributions can be empirical, i.e. described from data samples.

All distances for each algorithm and each data-sets are presented in Figure 2. Note that the values can vary a lot from a data-set to another, based on their size and dimension. In order to increase the readability of the results, the distances have been normalized such that the less efficient approach for each data-set have a score of 1. A score of 0 would indicate a perfect match between the two distributions. The results show that, as expected, the proposed approach is usually much better than the GMM to generate new data matching the distribution of a training data-set. For some data-set, a full GMM is as efficient as the histogram-based model (see data-sets "Satimage" or "Texture").
but in other cases the proposed algorithm is much better (for example "Rect 1",
"Gradients", "Ecoli" or "Letter").

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** For each generative algorithm, Normalized Wasserstein distance between each training data-set and the generated data. Smaller values indicate a better fit.</figcaption></figure>

# 5 Conclusion

In this paper, we introduced a new generative unsupervised learning algorithm based on the computation of histograms to represent the data distributions. The main idea is to reduce the model complexity for each class via different projections on independent axes and to compute a one-dimensional histogram for each of these axes. Axes being independent, the computation of the join probability distribution is greatly simplified.

The proposed algorithm has a complexity comparable to the complexity of a Gaussian Mixture Model (GMM), while being able to model a wider variety of distributions. To validate its quality experimentally, we compared the proposed approach to several classical algorithms. The results show that the obtained model is in average better than models obtained with other algorithms. In addition, the proposed approach is more efficient than a GMM to generate new instances with the same distribution as the training data.

To pursue this study, we plan to test the use of non-linear projections instead of the current linear projections. We expect that this will improve the performances of the model when the data distribution have non-convex components. We also plan to reduce the complexity of the algorithm by limiting the number of principal components in the projections.
Acknowledgements

This work was supported in part by the Pro-TEXT project (No ANR-18-CE23-0024) financed by the ANR (Agence Nationale de la Recherche).

References

1. Baldi, P., Brunak, S., Bach, F.: Bioinformatics: the machine learning approach. MIT press (2001)

2. Benaglia, T., Chauveau, D., Hunter, D.R.: An em-like algorithm for semi- and nonparametric estimation in multivariate mixtures. Journal of Computational and Graphical Statistics 18(2), 505–526 (2009)

3. Bezdek, J.C., Ehrlich, R., Full, W.: FCM: The fuzzy c-means clustering algorithm. Computers & Geosciences 10(2-3), 191–203 (1984)

4. Cabanes, G., Bennani, Y., Grozavu, N.: Unsupervised learning for analyzing the dynamic behavior of online banking fraud. In: IEEE 13th International Conference on Data Mining. pp. 513–520 (2013)

5. Dempster, A.P., Laird, N.M., Rubin, D.B.: Maximum likelihood from incomplete data via the em algorithm. Journal Of The Royal Statistical Society, Series B 39(1), 1–38 (1977)

6. Dudoit, S., Fridlyand, J.: A prediction-based resampling method for estimating the number of clusters in a dataset. Genome Biology 3(7), 1–21 (2002)

7. Ester, M., Kriegel, H.P., Sander, J., Xu, X.: A density-based algorithm for discovering clusters in large spatial databases with noise. In: International Conference on Knowledge Discovery and Data Mining. pp. 226–231 (1996)

8. Hubert, L., Arabie, P.: Comparing partitions. Journal of Classification 2(1), 193–218 (1985)

9. Jain, A.K.: Data clustering: 50 years beyond k-means. Pattern Recognition Letters 31(8), 651–666 (2010)

10. Jebara, T.: Machine learning: discriminative and generative, vol. 755. Springer Science & Business Media (2012)

11. Maimon, O., Rokach, L.: Data Mining and Knowledge Discovery Handbook. Springer-Verlag New York, Inc., Secaucus, NJ, USA (2005)

12. McLachlan, G.J., Basford, K.E.: Mixture models: Inference and applications to clustering, vol. 84. M. Dekker New York (1988)

13. Rastin, P., Cabanes, G., Matei, B., Bennani, Y., Marty, J.M.: A new sparse representation learning of complex data: Application to dynamic clustering of web navigation. Pattern Recognition 91, 291–307 (2019)

14. Ruschendorf, L.: Wasserstein metric. In: M, H. (ed.) Encyclopedia of mathematics. Springer, Berlin (2001)

15. Strehl, A., Ghosh, J.: Cluster ensembles — a knowledge reuse framework for combining multiple partitions. J. Mach. Learn. Res. 3, 583–617 (Mar 2003)

16. Train, K.E.: Mixed Logit, p. 138–154. Cambridge University Press (2003)

17. Ultsch, A.: Fundamental clustering problems suite (fcps) (2005)

18. Vanschoren, J., van Rijn, J.N., Bischl, B., Torgo, L.: Openml: Networked science in machine learning. SIGKDD Explorations 15(2), 49–60 (2013)

19. Yue, H.H., Tomoyasu, M.: Weighted principal component analysis and its applications to improve fdc performance. In: IEEE Conference on Decision and Control (CDC). vol. 4, pp. 4262–4267 (2004)

20. Zhao, H., Fu, Y.: Dual-regularized multi-view outlier detection. In: International Conference on Artificial Intelligence. pp. 4077–4083. AAAI Press (2015)