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

HAL
open science

# A simultaneous two-level clustering algorithm for automatic model selection

Guénaël Cabanes, Younès Bennani

► To cite this version:

Guénaël Cabanes, Younès Bennani. A simultaneous two-level clustering algorithm for automatic model selection. International Conference on Machine Learning and Applications (ICMLA), Dec 2007, Cincinnati, United States. pp.316-321, 10.1109/ICMLA.2007.71 . hal-05001486

HAL Id: hal-05001486

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

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Simultaneous Two-Level Clustering Algorithm for Automatic Model Selection

Guénaël CABANES and Younès BENNANI

LIPN-CNRS, UMR 7030, University of Paris 13

99, Avenue J-B. Clment 93430 Villetaneuse - FRANCE

`{cabanes, younes}@lipn.univ-paris13.fr`

## Abstract

One of the most crucial questions in many real-world cluster applications is determining a suitable number of clusters, also known as the model selection problem. Determining the optimum number of clusters is an ill posed problem for which there is no simple way of knowing that number without a priori knowledge. In this paper we propose a new two-level clustering algorithm based on self organizing map, called S2L-SOM, which allows an automatic determination of the number of clusters during learning. Estimating true numbers of clusters is related to the cluster stability which involved the validity of clusters generated by the learning algorithm. To measure this stability we use the sub-sampling method. The great advantage of our proposed algorithm, compared to the common partitional clustering methods, is that it is not restricted to convex clusters but can recognize arbitrarily shaped clusters. The validity of this algorithm is superior to standard two-level clustering methods such as SOM+k-means and SOM+Hierarchical agglomerative clustering. This is demonstrated on a set of critical clustering problems.

## 1. Introduction

Unsupervised classification, or clustering, is a very powerful tool for automatic detection of relevant sub-groups or clusters in unlabeled data sets, when one does not have prior knowledge about the hidden structure of these data. Patterns in the same cluster should be similar to each other, while patterns in different clusters should not (internal homogeneity and the external separation). Clustering plays an indispensable role for understanding various phenomena described by data sets. A grouping problem can be defined as the task of partitioning a set of items into a collection of mutually disjoint subsets. Clustering is a grouping problem which is considered as one of the most challenging problems in unsupervised learning. Various approaches has been proposed to solve the problem [9].

The most traditional clustering approaches are hierarchical methods and partitional algorithms. Hierarchical agglomerative clustering (HAC) separates patterns with a tree hierarchy (dendrogram) built from the patterns to be clustered. In this structure, sibling nodes partition the cluster denoted by their common parent [15], while partitional methods group data into some clusters without the hierarchical structure. An efficient method to grouping problems is the Self Organizing Map (SOM) [10, 11]. The SOM is a neuro-computational algorithm to map high-dimensional data to a two-dimensional space through a competitive and unsupervised learning process. This unsupervised learning algorithm is a popular nonlinear technique for features reduction and data visualization. The representation of different number of groups in this approach is usually detected using others clustering techniques such K-means or hierarchical methods. In the first phase of the process, the standard SOM approach is used to partition each subset. In the second phase, the groups obtained from the subsets are used to form the final partitioning of data using a traditional clustering method. Such approach is called a two-level clustering method. In this work, we focus particular attention on two-levels clustering algorithms. One of the most crucial questions in many real-world cluster applications is determining a suitable number of clusters k, also known as the model selection problem. Without a priori knowledge there is no simple way of knowing that number. The purpose of this paper is to provide a simultaneous two-level clustering approach using SOM which can be applicable to large datasets. The proposed method divides automatically a given dataset into a collection of subset (clusters), i.e., the number of clusters is determined automatically during learning process, i.e., no a priori hypothesis for the number of clusters is required. This approach has been tested on a set of critical clustering problems and shows excellent results compared to usual approaches.

The remainder of this paper is organized as follows. Section 2 presents the simultaneous two-level clustering algorithm based on SOM. Section 3 describes the validation databases and experimental protocol. In section 4 we show
validation results and their evaluation. Conclusion and future work are given in section 5.

## 2. Simultaneous Two-Level Clustering based on Self Organizing Maps

In high dimensions data may be sparse (the curse of dimensionality), making it difficult for a clustering algorithm to find any structure in the data. Indeed, when dimensionality increases, data becomes increasingly sparse in the space that it occupies. Definitions of density and distance between points, which is critical for clustering and outlier detection, become less meaningful. To improve this problem, a large number of dimension reduction approaches have been developed and tested in different application domains and research communities. The main idea behind these techniques is to map each pattern into a lower dimensional space that preserve the topology of data. The reduced data present in the lower dimensional representation can be used to perform clustering more efficiently. Various approaches have been proposed for the two-level clustering problem [2, 8, 14, 5, 12].

The key idea of the two-level clustering approach based on SOM is to combine the dimension reduction and the fast learning capabilities of SOM in the first level to construct a new reduced vector space, then applies an other clustering method in this new space to produce a final set of clusters in the second level [8, 14, 5]. Although the two-levels methods are more interesting than the traditional approaches (in particular by reducing the computational time and by allowing a visual interpretation of the partition result), the data segmentation obtained from the SOM is not optimal, since a part of information is lost during the first stage (dimension reduction). Moreover, this separation in two stages is not suited for a dynamic (incremental) segmentation of data which move in time, in spite of important needs for analysis tools for this type of data.

We propose here a new unsupervised learning algorithm (S2L-SOM) which learns simultaneously the structure of the data and its segmentation (section 2). We tested the performances of this new algorithm on set of critical clustering problems having various difficulties of segmentation (section 3). These performances were compared with those of the traditional clustering algorithms (K-Means and HAC) and others two-levels clustering approaches (SOM+k-means, SOM+HAC) (section 4).

### 2.1. Principle

The Kohonen SOM can be classified as a competitive unsupervised learning neural network [10, 11]. When an observation is recognized, activation of an output cell competition layer leads to inhibit activation of other neurons

and reinforce itself. It is said that it follows the so called “Winner Takes All” rule. Actually, neurons are specialized in the recognition of one kind of observations. A SOM consists in a two dimensional map of neurons which are connected to n inputs according to n weights connections $w_{.j} = (w_{0j}, ..., w_{nj})$ and to their neighbours with topological links. The training set is used to organize these maps under topological constraints of the input space. Thus, a mapping between the input space and the network space is constructed; two closed observations in the input space would activate two closed units of the SOM. An optimal spatial organization is determined by the SOM from the input data, and when the dimension of the input space is lower than three, both position of weights vectors and direct neighbourhood relations between cells can be represented visually. Thus, a visual inspection of the map provides qualitative information of the map and the choice of its architecture. The winner neuron updates its prototype vector, making it more sensitive for latter presentation of that type of input. This allows different cells to be trained for different types of data. To achieve a topological mapping, the neighbors of the winner neuron can adjust their prototype vector towards the input vector as well, but in a lesser degree, depending on how far away they are from the winner. Usually a radial symmetric Gaussian neighbourhood function $K_{ij}$ is used for this purpose. In the S2L-SOM algorithm, we propose to associate each neighbourhood connection a real value $\Psi$ which indicates the relevance of the connected neurons. Given the organization constraint of the SOM, both best closet prototypes of each data must be connected by a topological connection. This connection “will be rewarded” by an increase of its value, whereas all other connections from the winner neuron “are punished” by a reduction of their values. Thus, at the end of the training, a whole of inter-connected prototypes will be an artificial image of the relevant sub-group of the whole data set.

### 2.2. S2L-SOM algorithm

The connectionist learning is often presented as a minimization of a cost function. In our case, it will be carried out by the minimization of the distance between the input samples and the map prototypes, weighted by a neighbourhood function $K_{ij}$. To do that, we use a gradient algorithm. The cost function to be minimized is defined by:

$$ \tilde{R}(w) = \frac{1}{N} \sum_{k=1}^{N} \sum_{j=1}^{M} K_{jN(x^{(k)})} \| w_{.j} - x^{(k)} \|^2 \quad (1) $$

$N$ represents the number of learning samples, $M$ the number of neurons in the map, $N(x^{(k)})$ is the neuron having the closest weight vector to the input pattern $x^{(k)}$ and $K_{ij}$ is a positive symmetric kernel function: the neighbourhood
function. The relative importance of a neuron i compared to a neuron j is weighted by the value of the kernel function $K_{ij}$ which can be defined as:

$$K_{ij} = \frac{1}{\lambda(t)} \times e^{-\frac{d_{ij}^2}{\lambda^2(t)}} \quad (2)$$

$\lambda(t)$ is the temperature function modeling the topological neighbourhood extent, defined as:

$$\lambda(t) = \lambda_i(\frac{\lambda_f}{\lambda_i}) \frac{t}{t_{max}} \quad (3)$$

$\lambda_i$ and $\lambda_f$ are respectively initial and the final temperature (for example $\lambda_i=2$, $\lambda_f=0.5$). $t_{max}$ is the maximum number allotted to the time (number of iterations for the $x$ learning sample). $d_1(i, j)$ is the Manhattan distance defined between two neurons i and j on the map grid, with the coordinates $(k, m)$ and $(r, s)$ respectively:

$$d_1(i, j) = \| r - k \| + \| s - m \| \quad (4)$$

The S2L-SOM training process is highly similar to the Competitive Hebbian Learning (CHL) approach [13]. The difference so far is that the CHL method does not change reference vectors at all (which could be interpreted as having a zero learning rate). It only generates a number of neighbourhood edges between the units of the SOM without values. In the S2L-SOM we associate each neighbourhood connection a real value which indicates the relevance of the connected couple for the local neuron prototype vector. The value of this connection is adapted during learning process. It was proved by Martinetz [13] that the so generated graph is optimally topology-preserving in a very general sense. In particular each edge of this graph belongs to the Delaunay triangulation corresponding to the given set of reference vectors. The S2L-SOM learning algorithm proceeds essentially in three phases:

### 1. Initialization phase:

* Define the topology of the SOM.

* Initialize all weights vectors of the map $w$ (prototypes) randomly.

* Initialize all neighbourhood connections values $\Psi$ to zero.

### 2. Competition phase:

* Present an input pattern $x^{(k)}$ to the SOM.

* Choose the first best match unit (winner neuron):

$$N_1(x^{(k)}) = \underset{1 \le i \le M}{\operatorname{Argmin}} \| x^{(k)} - w_i \|^2$$

* Choose the second best match unit $N_2(x^{(k)})$:

$$N_2(x^{(k)}) = \underset{1 \le i \le M, i \ne N_1}{\operatorname{Argmin}} \| x^{(k)} - w_i \|^2$$

### 3. Adaptation phase:

* Update prototype vectors $w_j$ of each neuron $j$ according to the learning rate $\epsilon(t)$:

$$w_j(t) = w_j(t-1) - \epsilon(t) K_{jN_1(x^{(k)})} (w_j(t-1) - x^{(k)})$$

* Let $\mathfrak{N}(N_1)$ be the topological neighbourhood of the first best match unit; adapt the neighbourhood connections values $\Psi$ according to the following rules:

$$\Psi_{N_1, N_2}(t) = \Psi_{N_1, N_2}(t-1) + \delta_r \cdot R(t)$$

and

$$\begin{gathered} \Psi_{N_1, N_i}(t) = \Psi_{N_1, N_i}(t-1) - \delta_p \cdot R(t) \\ \forall N_i \in \mathfrak{N}(N_1), i \ne 2 \end{gathered}$$

with:

$$R(t) = \frac{P}{1 + e^{(-\frac{\alpha \cdot t}{t_{max}} + \beta)}}$$

where $P(t)$ is the number of punished connections at time $t$ and $\alpha, \beta, \delta_r, \delta_p$ are hyperparameters for regularization.

Repeat steps 2 and 3 until no change of neuron position that is more than a small positive number is observed or until $t = t_{max}$.

At the end of the clustering process, a cluster is a set of prototypes which are linked together by neighbourhood connections with positive values. Thus, the right number of cluster can be determined easily.

## 3. Experiments

### 3.1. Databases description

To demonstrate the effectiveness of the proposed two-level clustering method, the performances of the S2L-SOM algorithm were tested on 8 databases presenting various clustering difficulties. The databases “Hepta”, “Chain-link”, “Atom” and “TwoDiamonds” come from Fundamental Clustering Problem Suite (FCPS) [14]. We also generated four other interesting databases (“Rings”, “Spirals”, “HighDim” and “Random”). “Rings” is made up of 3 groups in 2 dimensions not linearly separable with different densities and variances: a ring of radius 1 with 700 points (strong density), a ring of radius 3 with 300 points
(low density) and a ring of radius 5 with 1500 point (average density). “HighDim” consists of 9 quite separate groups of 100 points each one in a 15 dimensions space. “Random” is a random generation of 1000 points in 8 dimensions space. Finally “Spirals” consists of two parallel spirals of 1000 points each one in rings of 3000 points. The density of points in the spirals decreases with the radius.

<figure><img src="image_3.png" /><figcaption>Figure 1. Data visualisations.</figcaption></figure>

## 3.2. Experimental protocol

We compared the performances of the S2L-SOM algorithm in term of segmentation quality and stability compared to the traditional methods with one or two levels. The selected algorithms for comparison are K-means, SingleLinkage and Ward applied to the data or to the prototypes of the trained SOM. The Davis-Bouldin index [4] is used to determine the best cutting of the dendrogram (SingleLink and Ward) or the optimal number K of centroids for K-means. S2L-SOM determines the number of clusters automatically and does not need to use this index. In this paper the quality of the clustering was evaluated using external criteria (Overlap Indices Rand and Jaccard) frequently used [6, 7]. Indeed if data-independent labels (categories) are available, the question may be asked of how well a given cluster solution corresponds to these external labels.

$$ Rand = \frac{a_{00} + a_{11}}{a_{00} + a_{01} + a_{10} + a_{11}} \quad (5) $$

$$ Jaccard = \frac{a_{11}}{a_{01} + a_{10} + a_{11}} \quad (6) $$

Then $a_{11}$ is the number of object pairs where both objects belong to the same label and to the same cluster. $a_{01}$ is the number of pairs that belong to the same label but different clusters, while $a_{01}$ are the pairs in the same cluster but with different labels. Finally, $a_{00}$ is the number of object pairs that share neither label nor cluster.

Internal criteria (Davis-Bouldin [4] and Calinski-Harabasz [3]) was also used in this work. Here the principal question is: how good does a particular cluster solution or individual cluster fit the data? In the absence of external labels, cluster solutions can still be assessed by internal criterion functions such as cluster compactness and cluster separation.

The index suggested by Davies and Bouldin [4] for different values k (cluster number) is typically initiated as follows to capture the concepts of cluster separation (denominator) and cluster compactness (numerator):

$$ DB(k) = \frac{1}{K} \sum_{i=1}^{K} \frac{s_i + s_j}{\| c_i - c_j \|^2} \quad (7) $$

with si the square root of the average error (within-cluster variance) of cluster i with the centroid $c_i$.

The Calinski-Harabasz index [3] is still the most widely used and preferred model selection criterion in traditional clustering methods. It can be defined as:

$$ CH(k) = \frac{\text{trace}(B)/(k-1)}{\text{trace}(W)/(N-k)} \quad (8) $$

The trace(W) and trace(B) are the within- and between-cluster sums-of-squares, and k and N denote the number of clusters and the total number of objects, it can be concluded that the CH-index divides the between-cluster variability of a solution by the corresponding within cluster variability, both corrected for their respective degrees of freedom. As such, the CH-index will attain high values for solutions with enough but not too many clusters. For a better legibility, the values of these indices were standardized between 0 and 1 for each test.

The concept of cluster stability is also used as an indicator for assessing the validity of data partitionings found by different algorithms. In order to evaluate the stability of the various algorithms, we use sub-sampling based method for each data bases [1]. The samples are partitioned using a clustering algorithm. We then rerun the clustering process based on the sub-sampling a fraction of the samples and group the sub-samples into clusters. We then compute the difference between the two different segmentations using the Jaccard index. We repeat this several times to get the average of the index which regarded as a reliable estimate of the clustering stability.
## 4. Results

The results for the external indices show that for all the databases S2L-SOM is able to find without any error the awaited data segmentation and the right number of clusters. It is not the case of the other algorithms, in particular when the groups have an arbitrary form or when there is no structure in the data (see table 1 and figure 2).

<table><caption>Table 1. Number of clusters obtained by various methods (S2L denotes our method).</caption><thead><tr><th>Database</th><th>SL</th><th>W</th><th>KM</th><th>SSL</th><th>SW</th><th>SKM</th><th>S2L</th><th>True</th></tr></thead><tbody><tr><td>HighDim</td><td>9</td><td>9</td><td>8</td><td>4</td><td>9</td><td>9</td><td>9</td><td>9</td></tr><tr><td>Chainlink</td><td>15</td><td>12</td><td>13</td><td>3</td><td>9</td><td>11</td><td>3</td><td>3</td></tr><tr><td>Atom</td><td>15</td><td>8</td><td>10</td><td>6</td><td>12</td><td>6</td><td>3</td><td>3</td></tr><tr><td>TwoDiamonds</td><td>5</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td></tr><tr><td>Rings</td><td>12</td><td>15</td><td>15</td><td>2</td><td>12</td><td>13</td><td>2</td><td>2</td></tr><tr><td>Spirals</td><td>14</td><td>15</td><td>10</td><td>12</td><td>10</td><td>10</td><td>2</td><td>2</td></tr><tr><td>Hepta</td><td>7</td><td>7</td><td>7</td><td>5</td><td>8</td><td>7</td><td>7</td><td>7</td></tr><tr><td>Random</td><td>11</td><td>15</td><td>15</td><td>10</td><td>15</td><td>15</td><td>1</td><td>1</td></tr></tbody></table>

SL: Single-Linkage, W: Ward, KM: K-Means, SSL: SOM+Single-Linkage, SW: SOM+Ward, SKM: SOM+K-Means, S2L: S2L-SOM

<figure><img src="image_4.png" /><figcaption>Figure 2. Clustering quality using the Jaccard index for each algorithm on each database.</figcaption></figure>

The clustering results obtained by the S2L-SOM are excellent quality according to external indices when the data are grouped in compact and more or less hyperspheric clusters (“Hepta” or “HighDim” for example). On the other hand these indices are not adapted to all clouds structures (arbitrary structures) like “Rings”, “Spirals”, “Chainlink” or “Atom”, which explains the bad performances of the S2L-SOM algorithm in this case. Indeed, these indices are high when each member of the cluster is near to each other, but it is not the case in arbitrary shaped groups. Since traditional

methods always try to produce hyperspheric clusters that maximise these external criterias, results are better than S2L-SOM with these indices. It is necessary to also note that we cannot evaluate a segmentation with only one group, as it is the case for database Random (see figure 3).

<figure><img src="image_5.png" /><figcaption>Figure 3. Clustering quality using the Calinski-Harabasz index for each algorithm on each database.</figcaption></figure>

With regard to stability, the S2L-SOM shows excellent results for the data grouped in hyperspheric clusters, whatever the dimension (“Hepta” and “HighDim”), and also in the cases where the groups have arbitrary forms in two dimensions (“Rings” and “Spirals”) and when the data are not structured (“Random”). It is noticed that in this last case the segmentation obtained by the most traditional methods is extremely unstable (figure 4).

<figure><img src="image_6.png" /><figcaption>Figure 4. Stability index for each algorithm on each database.</figcaption></figure>

When the data are not linearly separable in dimensions higher than two (“Atom” and “Chainlink”), the algorithm S2L-SOM is limited by the topological constraint in two dimensions of the SOM network and the stability of the segmentation is not maximum. One can however note that even in this case the S2L-SOM algorithm remains more stable than the traditional methods. On the other hand, while presenting a relatively high stability, the S2L-SOM algorithm
is less stable than the majority of the traditional methods when the clusters have a contact point ("TwoDiamonds"). Indeed, this contact point supports the reinforcement of the topological connections value between the two groups in our algorithm.

The results are also confirmed via visualization. Indeed, the S2L-SOM clustering algorithm is a powerful tool for visualization of the obtained segmentation in two dimensions. Clusters are easily and clearly identifiable, as well as fields without data. As one can notice it on figures 5 results obtained by the S2L-SOM algorithm are more closer to reality than those found by the traditional algorithms.

<figure><img src="image_7.png" /><figcaption>**Figure 5.** Segmentation of the databases by, from the left to the right, S2L-SOM, SOM+WARD and SOM+Kmeans.</figcaption></figure>

## 4.1. Conclusion and Future Work

In this paper, we proposed a simultaneous two-level clustering method. It uses the SOM as dimension reduction technique and achieves an improved final clustering in the second level. The performance was evaluated by testing the two-level S2L-SOM on a set of critical clustering problems, and comparing it to classical two-level SOM using both K-means and AHC. The experimental results demonstrate that the proposed clustering method achieves a better quality clustering than classical approaches. The results also demonstrate that the great advantage of the S2L-SOM algorithm, compared to the common partitional clustering methods, is that it is not restricted to convex clusters but can recognize arbitrarily shaped clusters. Finally, the number of

clusters in our approach is determined automatically during learning process, i.e., no a priori hypothesis for the number of clusters is required. In the future we plan to incorporate in the S2L-SOM algorithm the plasticity, to evaluate its impact to the cluster quality and stability.

**Acknowledgment:** This work was supported in part by the Sillages project financed by the ANR (Agence Nationale de la Recherche).

## References

[1] A. Ben-Hur, A. Elisseeff, and I. Guyon. A stability based method for discovering structure in clustered data. *Pacific Symposium on Biocomputing*, 7:6-17, 2002.

[2] E. L. J. Bohez. Two level cluster analysis based on fractal dimension and iterated function systems (ifs) for speech signal recognition. *IEEE Asia-Pacific Conference on Circuits and Systems*, pages 291-294, 1998.

[3] T. Calinski and J. Harabasz. Dendrite method for cluster analysis. *Communications in Statistics*, 3(1):1-27, 1974.

[4] D. L. Davies and D. W. Bouldin. A cluster separation measure. *IEEE Transactions on Pattern Recognition and Machine Intelligence*, 1(2):224-227, 1979.

[5] S. Guérif and Y. Bennani. Selection of clusters number and features subset during a two-levels clustering task. In *Proceeding of the 10th International Conference Artificial intelligence and Soft Computing 2006*, pages 28-33, Palma de Mallorca, Spain, August 2006.

[6] M. Halkidi, Y. Batistakis, and M. Vazirgiannis. On Clustering Validation Techniques. *Journal of Intelligent Information Systems*, 17(2-3):107-145, 2001.

[7] M. Halkidi, Y. Batistakis, and M. Vazirgiannis. Cluster Validity Methods. *SIGMOD Record*, 31(2,3):40-45, 19-27, 2002.

[8] M. F. Hussin, M. S. Kamel, and M. H. Nagi. An efficient two-level SOMART document clustering through dimensionality reduction. In *ICONIP*, pages 158-165, 2004.

[9] A. K. Jain and R. C. Dubes. *Algorithms for clustering data*. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1988.

[10] T. Kohonen. *Self-Organization and Associative Memory*. Springer-Verlag, Berlin, 1984.

[11] T. Kohonen. *Self-Organizing Maps*. Springer-Verlag, Berlin, 2001.

[12] E. E. Korkmaz. A two-level clustering method using linear linkage encoding. *International Conference on Parallel Problem Solving From Nature, Lecture Notes in Computer Science*, 4193:681-690, 2006.

[13] T. Martinetz. Competitive hebbian learning rule forms perfectly topology preserving maps. In S. Gielen and B. Kappen, editors, *Proceedings of the International Conference on Artificial Neural Networks (ICANN-93)*, Amsterdam, pages 427-434, Heidelberg, 1993. Springer.

[14] A. Ultsch. Clustering with SOM: U*C. In *Proceedings of the Workshop on Self-Organizing Maps*, pages 75-82, 2005.

[15] J. H. Ward. Hierarchical grouping to optimize an objective function. *Journal of the American Statistical Association*, 58(301):236-244, 1963.