Batch Self-Organizing Maps for Distributional Data with an Automatic Weighting of Variables and Components

Abstract

This paper deals with a batch self organizing map algorithm for data described by distributional-valued variables (DBSOM). Such variables are characterized to take as values probability or frequency distributions on numeric support. According to the nature of the data, the loss function is based on the L₂ Wasserstein distance, that is one of the most used metrics to compare distributions in the context of distributional data analysis. Besides, to consider the different contributions of the variables, four adaptive versions of the DBSOM algorithm are proposed. Relevance weights are automatically learned, one for each distributional-valued variable, in an additional step of the algorithm. Since the L₂ Wasserstein metric allows a decomposition of the distance into two components, one related to the means and one related to the size and shape of the distributions, relevance weights are automatically learned for each of the two components to emphasize the importance of the different characteristics, related to the moments of the distributions, on the distance value. The proposed algorithms are corroborated by applications on real distributional-valued data sets.

Appendix: : Fast Computation of Silhouette Coefficient for Euclidean Spaces

Let us consider a table Y containing N numerical data vectors y_i = [y_i1,…,y_iP] of P components. Without loss of generality, the N vectors are clustered in two groups, namely, A and B, having, respectively, size N_A and N_B such that N_A + N_B = N. Let $\bar {y}_{Aj}= n_{A}^{-1}\sum \limits _{\mathbf {y_{i}}\in A}y_{ij}$ and $\bar {y}_{Bj}= n_{B}^{-1}\sum \limits _{\mathbf {y_{i}}\in B}y_{ij}$, j = 1,…,P, be the two cluster means, and $\text {SSE}_{Aj}=\sum \limits _{\mathbf {y_{i}}\in A}{y_{ij}^{2}}- n_{A} (\bar {y}_{Aj})^{2}$ and $\text {SSE}_{Bj}=\sum \limits _{\mathbf {y_{i}}\in B}{y_{ij}^{2}}- n_{B} (\bar {y}_{Bj})^{2}$ the two sum of squares deviations from the respective cluster means.

1.1 The Average Euclidean Distance Between a Point to all the Other Points of a Set Where It Is Contained

Let consider that y_i ∈ A, the average distance of y_i with respect all the other vectors in A is computed as follows:

$$(n_{A}-1)^{-1}\sum\limits_{\mathbf{y}_{k}\in A}\sum\limits_{j=1}^{P}{(y_{ij}-y_{kj})^{2}}.$$

It is easy to show, for a single variable j, that:

$$\sum\limits_{\mathbf{y}_{k}\in A}{(y_{ij}-y_{kj})^{2}}=n_{A}(y_{ij})^{2}+\sum\limits_{\mathbf{y}_{k}\in A}{(y_{kj})^{2}}-2 y_{ij}\sum\limits_{\mathbf{y}_{k}\in A}{y_{kj}}=$$

$$ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~=n_{A}(y_{ij})^{2}+\left[\text{SSE}_{Aj}+n_{A}(\bar{y}_{Aj})^{2}\right]-2n_{A}y_{ij}\bar{y}_{Aj}= $$

$$ ~~~~=n_{A}\left( y_{ij}-\bar{y}_{Aj}\right)^{2}+\text{SSE}_{Aj}. $$

Then, the average distance is:

$$(n_{A}-1)^{-1}\sum\limits_{\mathbf{y}_{k}\in A} {(y_{ij}-y_{kj})^{2}}=\frac{n_{A}\left( y_{ij}-\bar{y}_{Aj}\right)^{2}}{n_{A}-1}+\frac{\text{SSE}_{Aj}}{n_{A}-1}$$

1.2 The Average Euclidean Distance of a Point from all the Other Points of a Set Where It Is Not Contained

Let consider that y_i ∈ A and we want to compute the average distance of y_i with respect to all the other vectors in B. The average squared Euclidean distance between y_i and all the other vectors in B, for each variable, is given by:

$$(n_{B})^{-1}\sum\limits_{\mathbf{y}_{k}\in B}\sum\limits_{j=1}^{P}{(y_{ij}-y_{kj})^{2}},$$

for a single variable j, it is easy to show that:

$$\sum\limits_{\mathbf{y}_{k}\in B}{(y_{ij}-y_{kj})^{2}}=n_{B}(y_{ij})^{2}+\sum\limits_{\mathbf{y}_{k}\in B}{(y_{kj})^{2}}-2 y_{ij}\sum\limits_{\mathbf{y}_{k}\in B}{y_{kj}}=$$

$$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~=n_{B}(y_{ij})^{2}+\left[\text{SSE}_{Bj}+n_{B}(\bar{y}_{Bj})^{2}\right]-2n_{B}y_{ij}\bar{y}_{Bj}=$$

$$~~~~=n_{B}\left( y_{ij}-\bar{y}_{Bj}\right)^{2}+\text{SSE}_{Bj}.$$

Then, the average distance is that:

$$(n_{B})^{-1}\sum\limits_{\mathbf{y}_{k}\in B} {(y_{ij}-y_{kj})^{2}}=\left( y_{ij}-\bar{y}_{Bj}\right)^{2}+\frac{\text{SSE}}{Bjn_{B}}.$$

1.3 The Silhouette Coefficient

As stated above, the silhouette coefficient for a single y_i is given by:

$$ s(i)=\frac{b(i)-a(i)}{max[a(i),b(i)]} ,$$

where, in the case of two groups A and B, if i ∈ A:

$$a(i)=(n_{A}-1)^{-1}\sum\limits_{\mathbf{y}_{k}\in A}\sum\limits_{j=1}^{P}{(y_{ij}-y_{kj})^{2}}$$

and

$$b(i)=(n_{B})^{-1}\sum\limits_{\mathbf{y}_{k}\in B}\sum\limits_{j=1}^{P}{(y_{ij}-y_{kj})^{2}}.$$

If we consider the original formulation, for computing N silhouette indexes, the computational complexity is in the order of $\mathcal {O}(N^{2})$, if N is sufficiently larger than P. If we use the formulas suggested here, once computed the averages and the SSE, the computational cost is approximately of $\mathcal {O}(N)$. In fact, it is possible to compute a(i) and b(i) as follows:

$$a(i)=\sum\limits_{j=1}^{p}\left[\frac{n_{A}\left( y_{ij}-\bar{y}_{Aj}\right)^{2}}{n_{A}-1}+\frac{\text{SSE}_{Aj}}{n_{A}-1}\right]$$

and

$$b(i)=\sum\limits_{j=1}^{p}\left[ \left( y_{ij}-\bar{y}_{Bj}\right)^{2}+\frac{\text{SSE}_{Bj}}{n_{B}}\right].$$

Considering that the squared L2 Wasserstein distance is a Euclidean distance between quantile functions, that the SSE computed for distribution functions is defined as a sum of squared distance, and that the average distributions are Fréchet means with respect to the squared L₂ Wasserstein distance. The same simplification can be applied for computing the silhouette coefficient when data are distributions, and they are compared using the squared L₂ Wasserstein distance.