# A local density-based simultaneous two-level algorithm for topographic clustering

Guénaël Cabanes, Younès Bennani

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

To cite this version:

Guénaël Cabanes, Younès Bennani. A local density-based simultaneous two-level algorithm for topographic clustering. IEEE International Joint Conference on Neural Networks (IJCNN), Jun 2008, Hong Kong, China. pp.1176-1182, 10.1109/IJCNN.2008.4633948 . hal-05001484

HAL Id: hal-05001484

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

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 Local Density-based Simultaneous Two-level Algorithm for Topographic Clustering

Guénaël Cabanes and Younès Bennani

*Abstract*—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. The purpose of this paper is to provide a simultaneous two-level clustering algorithm based on self organizing map, called DS2L-SOM, which learn at the same time the structure of the data and its segmentation. The algorithm is based both on distance and density measures in order to accomplish a topographic clustering. An important feature of the algorithm is that the cluster number is discovered automatically. A great advantage of the proposed algorithm, compared to the common partitional clustering methods, is that it is not restricted to convex clusters but can recognize arbitrarily shaped clusters and touching clusters. The validity and the stability of this algorithm are 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.

## I. INTRODUCTION

UNSUPERVISED classification, or clustering, is a very powerful tool for automatic detection of relevant subgroups 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 clustering problem can be defined as the task of partitioning a set of objects into a collection of mutually disjoint subsets. Clustering is a segmentation problem which is considered as one of the most challenging problems in unsupervised learning. Various approaches have been proposed to solve the problem [12].

An efficient method to grouping problems is the Self Organizing Map (SOM) [13], [14]. 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 dimensionality 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 compute a set of reference vectors (prototypes) representing local means of the data. In the second phase,

the obtained prototypes 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-level clustering algorithms. One of the most crucial questions in many real-world cluster applications is how to determine 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, by learning at the same time the structure of the data and its segmentation, using both distance and density information. This new clustering algorithm assumes that a cluster is a dense region of objects surrounded by a region of low density [7], [21], [19], [2], [17], [18]. This approach is very effective when the clusters are irregular or intertwined, and when noise and outliers are present. The proposed clustering algorithm divides automatically a given dataset into a collection of subset (clusters), i.e., the number of clusters is determined automatically during the 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 DS2L-SOM algorithm (Density-based Simultaneous Two-Level - SOM). Section 3 describes the validation databases and experimental protocol. In section 4 we show validation results and their evaluation. Conclusion and future work perspectives are given in section 5.

## II. LOCAL DENSITY-BASED SIMULTANEOUS TWO-LEVEL CLUSTERING

High dimension 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 become increasingly sparse. Definitions of density and distance between objects, which is critical for clustering and outliers detection, become less meaningful. To improve the solution for 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 preserves the topology of data. The reduced data present at the lower

<footnote>Guénaël Cabanes and Younès Bennani are with the University of Paris 13, LIPN-CNRS, UMR 7030, 99 Avenue J-B. Clément, 93430 Villetaneuse, FRANCE (email: {cabanes, younes}@lipn.univ-paris13.fr)</footnote>
dimensional representation can be used to perform clustering more efficiently. Various approaches have been proposed for the two-level clustering problem [1], [4], [11], [19], [8], [15].

The key idea of the two-level clustering approach based on SOM is to combine the dimensionality reduction and the fast learning capabilities of SOM in the first level to construct a new reduced vector space. Then another clustering method is applied in this new space to produce a final set of clusters at the second level [11], [19], [8]. Although the two-level methods are more interesting than the traditional approaches, the data segmentation obtained from the SOM is not optimal, since a part of information is lost during the first stage (dimensionality reduction).

We propose here a new unsupervised learning algorithm (DS2L-SOM) which learns simultaneously the structure of the data and its segmentation using both distance and density information.

## A. Principle

Kohonen SOM can be defined as a competitive unsupervised learning neural network [13], [14]. When an observation is recognized, the activation of an output cell - competition layer - inhibits the 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 observation. A SOM consists in a two dimensional map of neurons which are connected to n inputs according to n weights connections $w^{(i)} = (w_0^{(i)}, ..., w_n^{(i)})$ and to their neighbors 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 close observations in the input space would activate two close 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 neighborhood relations between cells can be represented visually. Thus, a visual inspection of the map provides qualitative information about the map and the choice of its architecture. The winner neuron updates its prototype vector, making it more sensitive for later 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 at a lesser degree, depending on how far away they are from the winner. Usually a radial symmetric Gaussian neighborhood function $K_{ij}$ is used for this purpose.

In a previous algorithm, the S2L-SOM algorithm [5], we proposed to associate to each neighborhood connection a real value v which indicates the relevance of the connected

neurons. Given the organization constraint of the SOM, both best close 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, every group of inter-connected prototypes will define a specific region of the SOM, corresponding to a cluster of the learning data. However, the core part of a cluster can be defined as a region with high density. Then in most cases the cluster borders are defined either by low density region or “empty” region between clusters (i.e. large inter cluster distances) [19]. S2L-SOM can only detect borders defined by large inter cluster distances. In DS2L-SOM, we also learn an estimation of the local density, in order to detect either cluster borders defined by large distances or defined by low density.

## B. DS2L-SOM algorithm

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

$$R(w) = \frac{1}{N} \sum_{k=1}^{N} \sum_{j=1}^{M} K_{j,u^*(x^{(k)})} \| w^{(j)} - x^{(k)} \|^2$$

N represents the number of learning samples, M the number of neurons in the map, $u^*(x^{(k)})$ is the neuron having the weight vector closest to the input pattern $x^{(k)}$ (the best match unit: BMU), and $K_{ij}$ is a positive symmetric kernel function: the neighborhood 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_{i,j} = \frac{1}{\lambda(t)} \times e^{-\frac{d_{i,j}^2}{\lambda(t)}}$$

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

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

$\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 \|$$

The DS2L-SOM algorithm is an adaptation of the S2L-SOM algorithm [5]. In S2L-SOM, each neighborhood connection is associated with a real value v which indicates
the relevance of the connected neurons. The value of this connection is adapted during learning process. It was proved by Martinetz [16] 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. For each data, both best close prototypes are linked by a topological connection. The value of this connection will be increased, whereas the value of all other connections from the best match unit will be reduced. Thus, at the end of the training, the set of inter-connected prototypes will be an artificial image of well separated sub-groups of the whole data set. In the DS2L-SOM algorithm, we propose also to associate each unit i to an estimate of the local data density $D^{(i)}$, so as to detect local fluctuations of density, which define the borders of touching clusters. For each data, this density value will be increased for all unit, as a function of the Euclidean distance between the related prototype $w^{(i)}$ and the data. This method of evaluation is similar to the one proposed by [18]. One can notice that, in the DS2L-SOM algorithm, the estimation of the local density data is made during the training of the map, i.e. it is not necessary to keep the data in memory. The

DS2L-SOM learning algorithm proceeds essentially in three phases:

**Input :**

* Data $X = \{x^{(i)}\}_{i=1..N}$.

* SOM with M prototypes $\{w^{(i)}\}_{i=1..M}$.

* $t_{max}$ : maximum number of iterations.

**Output :**

* A partition $P = \{C_i\}_{i=1..L}$ sets of inter-connected units.

* Density values $\{D^{(i)}\}_{i=1..M}$ associated to each unit.

1) Initialization phase :

* Initialize all neighborhood connections values $v$ to zero.

* Initialize all unit density values $D^{(i)}$ to zero

2) Competition phase :

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

* Choose the first BMU $u^*$ and the second BMU $u^{**}$:

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

and

$$u^{**}(x^{(k)}) = \underset{1 \le i \le M, i \ne u^*}{\operatorname{Argmin}} \| x^{(k)} - w^{(i)} \|^2$$

3) Adaptation phase :

* Update prototype vectors $w^{(i)}$ of each unit i according to the learning rate $\epsilon(t)$:

$$w^{(i)}(t) = w^{(i)}(t-1) - \epsilon(t) K_{i,u^*(x^{(k)}),i} (w^{(i)}(t-1) - x^{(k)})$$

* Increase local density value $D^{(i)}$ for each unit i :

$$D^{(i)}(t) = D^{(i)}(t-1) + r(t)e^{-\frac{\|x^{(k)} - w^{(i)}(t)\|^2}{2\lambda^2(t)}}$$

with

$$r(t) = \frac{1}{1 + e^{-\frac{t}{t_{max}}}}$$

* Let $\mathfrak{N}(u^*)$ be the topological neighborhood of the first BMU; update the neighborhood connections values $v$ according to the following rules:

$$v_{u^*,u^{**}}(t) = v_{u^*,u^{**}}(t-1) + r(t)|\mathfrak{N}(u^*)|$$

and

$$v_{u^*,i}(t) = v_{u^*,i}(t-1) - r(t)|\mathfrak{N}(u^*)| \\ \forall i \in \mathfrak{N}(u^*), i \ne u^{**}$$

where $|\mathfrak{N}(u^*)|$ is the number of unit in $\mathfrak{N}(u^*)$.

4) Repeat steps 2 and 3 until $t = t_{max}$

5) Extract all clusters : Let $P = \{C_i\}_{i=1..L}$ the set of the L groups of linked unit such as $v > 0$ (see Fig.1(b)).

6) Return $P = \{C_i\}_{i=1..L}$.

At the end of the learning process, we use a refinement algorithm, which exploits connection and density information to detect clusters:

**Input :** $P$ and $\{D^{(i)}\}_{i=1..M}$.

**Output :** The refined clusters.

1) For each $C_k \in P$ do :

* Find the set $M(C_k)$ of density maxima (i.e. density mode, see Fig.1(c)).

$$M(C_k) = \{\text{unit } i \in C_k \mid D^{(i)} \ge D^{(j)}, \forall j \in \mathfrak{N}(i)\}$$

* Determine the threshold matrix :

$$S = [S(i,j)]_{i,j:1...|M(C_k)|}$$

with

$$S(i,j) = \left( \frac{1}{D^{(i)}} + \frac{1}{D^{(j)}} \right)^{-1}$$

* For all unit $i \in C_k$, label the unit i with one element label(i) of $M(C_k)$, according to an ascending density gradient along the topological connections. Each label represents a micro-cluster.

* For each pair of neighbors unit $(i, j)$ in $C_k$, if label(i) ≠ label(j) and if both $D^{(i)} > S(label(i), label(j))$ and $D^{(j)} > S(label(i), label(j))$ then merge the two micro-clusters.

2) Return refined clusters.

At the end of the learning process, the prototypes linked together by neighborhood connections having value $v > 0$
define well separate clusters. Thus, we use a “Watersheds” method (see [20]) on the density map of each of these clusters to find low density area inside well separate clusters, in order to characterize density defined sub-clusters. For each pair of adjacent subgroups we use a density-dependent index [21] to check if a low density area is a reliable indicator of the data structure, or whether it should be regarded as a random fluctuation in the density. This process is very fast because of the small number of prototypes. The combined use of these two types of group definition can achieve good results despite the low number of prototypes in the map.

### III. EXPERIMENTS

#### A. Databases description

To demonstrate the effectiveness of the proposed two-level clustering method, the performances of the DS2L-SOM algorithm have been tested on 10 databases presenting various clustering difficulties.

The databases “Hepta”, “Chainlink”, “Atom”, “Twodiamonds”, “Engytime” and “Wingnut” come from Fundamental Clustering Problem Suite (FCPS) [19]. We also generated four other interesting data bases (“Rings”, “Spirals”, “High-Dim” 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.

#### B. Experimental protocol

We compared the performances of the DS2L-SOM algorithm, in term of segmentation quality and stability, to S2L-SOM [5], and to the traditional two levels methods. The selected algorithms for comparison are K-means and SingleLinkage applied to the prototypes of the trained SOM. The Davies-Bouldin index [6] is used to determine the best cutting of the dendrogram (SingleLinkage) or the optimal number K of centroids for K-means. This index, suggested by Davies and Bouldin [6] for different values k (cluster number), is defined as in the following, in order to combine 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}$$

<figure><img src="image_3.png" /><figcaption>(a) Data base.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>(b) Output of the learning algorithm. Left: one set of connected units (in red) and some unconnected units (in gray). Right: density values for each unit.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(c) Density modes detection.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(e) Merging of irrelevant subgroups: final clustering.</figcaption></figure>

<caption>Fig. 1. Example of a sequence of the different stages of the refinement algorithm.</caption>

being $s_i$ the square root of the average error (within-cluster variance) of cluster i with the centroid $c_i$. S2L-SOM and DS2L-SOM determine the number of clusters automatically and do not need to use this index.
<figure><img src="image_7.png" /><figcaption>(a) "Rings" and "Spirals".</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>(b) "Chainlink" and "Atom".</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>(c) "Twodiamonds" and "Hepta".</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(d) "Engytime" and "Wingnut".</figcaption></figure>

<caption>Fig. 2. Data visualizations.</caption>

For the single link hierarchical clustering, the proximity of two clusters is defined as the minimum of the distance between any two objects in the two different clusters. The single link technique is good at handling non-elliptical shapes, but is sensitive to noise and outliers.

In this paper the quality of the clustering has been evaluated using external criteria (Overlap Indices Rand and Jaccard) frequently used [9], [10] :

$$Rand = \frac{a_{00} + a_{11}}{a_{00} + a_{01} + a_{10} + a_{11}}$$

$$Jaccard = \frac{a_{11}}{a_{01} + a_{10} + a_{11}}$$

Where $a_{11}$ denotes the number of object pairs belonging to the same label and to the same cluster, $a_{10}$ denotes the number of pairs that belong to the same label but different clusters, and $a_{01}$ denotes the pairs in the same cluster but with different labels. Finally, $a_{00}$ denotes the number of object pairs not sharing neither label nor cluster.

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.

The concept of cluster stability is also used as an indicator for assessing the validity of data partitioning found by different algorithms. In order to evaluate the stability of the various algorithms, we use sub-sampling based method for each data bases [3]. We then compute the difference between two different segmentations using the Jaccard index. We repeat this procedure several times to averaging the repeated index values. This average is regarded as a reliable estimate of the clustering stability.

## IV. RESULTS

The results for the external indices show that for all the databases DS2L-SOM is able to find without any error the expected data segmentation and the right number of clusters. This is not the case of the other algorithms, when the groups have an arbitrary form, or when there is no structure in the data or the groups are in contact (see table I and figure 3).

<table><caption>TABLE I
NUMBER OF CLUSTERS OBTAINED BY VARIOUS CLUSTERING METHODS
(SL=SINGLELINKAGE, KM=K-MEANS, SSL=SOM+SINGLELINKAGE, SKM=SOM+K-MEANS, S2L=S2L-SOM, DS2L=DS2L-SOM).</caption><thead><tr><th>Data</th><th>SL</th><th>KM</th><th>SSL</th><th>SKM</th><th>S2L</th><th>DS2L</th><th>True</th></tr></thead><tbody><tr><td>HighDim</td><td>9</td><td>8</td><td>4</td><td>9</td><td>9</td><td>9</td><td><b>9</b></td></tr><tr><td>Chainlink</td><td>15</td><td>13</td><td>2</td><td>11</td><td>2</td><td>2</td><td><b>2</b></td></tr><tr><td>Atom</td><td>15</td><td>10</td><td>6</td><td>6</td><td>2</td><td>2</td><td><b>2</b></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><b>2</b></td></tr><tr><td>Rings</td><td>12</td><td>15</td><td>7</td><td>13</td><td>3</td><td>3</td><td><b>3</b></td></tr><tr><td>Spirals</td><td>14</td><td>10</td><td>12</td><td>10</td><td>3</td><td>3</td><td><b>3</b></td></tr><tr><td>Hepta</td><td>7</td><td>7</td><td>5</td><td>7</td><td>7</td><td>7</td><td><b>7</b></td></tr><tr><td>Random</td><td>11</td><td>15</td><td>10</td><td>15</td><td>1</td><td>1</td><td><b>1</b></td></tr><tr><td>Wingnut</td><td>17</td><td>18</td><td>6</td><td>11</td><td>1</td><td>2</td><td><b>2</b></td></tr><tr><td>Engytime</td><td>18</td><td>15</td><td>10</td><td>10</td><td>1</td><td>2</td><td><b>2</b></td></tr></tbody></table>

<figure><img src="image_11.png" /><figcaption>Fig. 3. Clustering quality using the Jaccard index for each algorithm on each database.</figcaption></figure>
Considering the stability, the DS2L-SOM algorithm, like the S2L-SOM algorithm, 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 worth noticing that in this last case the segmentation obtained by the most traditional methods is extremely unstable (figure 4).

<figure><img src="image_12.png" /><figcaption>Fig. 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”), S2L-SOM and DS2L-SOM are limited by the topological constraint in two dimensions of the SOM network. Consequently, the stability of the segmentation is not maximum. However one can note that even in this case the DS2L-SOM algorithm remains more stable than the other methods. Moreover, when the clusters are defined only by the density (“Twodiamonds”, “Engytime”, “Wingnut”), sub-sampling may smooth the fluctuations of data density. This reduces the stability of the segmentation. In this case S2L-SOM is more stable than DS2L-SOM, because it can’t separate this kind of groups and always finds one group in each sub-sample.

The results are also confirmed by visual inspection. Indeed, the DS2L-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 regions without data (unconnected neurons). As one can notice it from figures 5 to 9, the results obtained by the DS2L-SOM algorithm are closer to reality than those found by the other algorithms. Figures 7 and 8 show that DS2L-SOM is able to detect density-defined clusters.

In these figures, each hexagon represents a prototype of the SOM together with its associated data. Hexagons showing the same color are in the same cluster. White hexagons are not part of any cluster.

<figure><img src="image_13.png" /><figcaption>Fig. 5. Clustering of “Rings” data.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Fig. 6. Clustering of “Spirals” data.</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>Fig. 7. Clustering of “Engytime” data.</figcaption></figure>
<figure><img src="image_16.png" /><figcaption>Fig. 8. Clustering of “Wingnut” data.</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>Fig. 9. Clustering of “Random” data. Data visualization is a two-dimensional projection of the “Random” database.</figcaption></figure>

## V. CONCLUSION AND FUTURE WORK

In this paper, we proposed a density-based simultaneous two-level clustering method. It uses SOM as dimensionality reduction technique and achieves an improved final clustering in the second level, using both distance and density information. The proposed algorithm DS2L-SOM locates regions of high density that are separated from one another by regions of low density. The performance of DS2L-SOM have been evaluated on a set of critical clustering problems, and compared to other two-level clustering algorithms. The experimental results demonstrate that the proposed clustering method achieves a better clustering quality than classical approaches. The results also demonstrate that DS2L-SOM is able to discover irregular and intertwined clusters, while conventional partitional clustering algorithms can deal with convex clusters only. Finally, the number of clusters in our approach is determined automatically during the learning

process, i.e., no a priori hypothesis for the number of clusters is required. In the future we plan to incorporate in the DS2L-SOM algorithm the plasticity property, to evaluate its impact on the cluster quality and stability.

## ACKNOWLEDGMENT

This work was supported in part by the *Sillages* project (Nº ANR-05-BLAN-0177-01) financed by the ANR (Agence Nationale de la Recherche).

## REFERENCES

[1] M. Aupetit, “Learning topology with the generative gaussian graph and the EM algorithm,” in *NIPS*, 2005.

[2] D. Beaton and I. Valora, “RADDACL: A recursive algorithm for clustering and density discovery on non-linearly separable data,” *Proceeding of International Joint Conference on Neural Networks*, pp. 1423–1428, Aug. 2007.

[3] A. Ben-Hur, A. Elisseeff, and I. Guyon, “A stability based method for discovering structure in clustered data,” *Pacific Symposium on Biocomputing*, vol. 7, pp. 6–17, 2002.

[4] E. L. J. Bohez, “Two level cluster analysis based on fractal dimension and iteratedfunction systems (ifs) for speech signal recognition,” *IEEE Asia-Pacific Conference on Circuits and Systems*, pp. 291–294, 1998.

[5] G. Cabanes and Y. Bennani, “A simultaneous two-level clustering algorithm for automatic model selection,” in *Proceedings of the International Conference on Machine Learning and Applications (ICMLA’07)*, Cincinnati, Ohio, USA, Dec. 2007.

[6] D. L. Davies and D. W. Bouldin, “A cluster separation measure,” *IEEE Transactions on Pattern Recognition and Machine Intelligence*, vol. 1, no. 2, pp. 224–227, 1979.

[7] M. Ester, H.-P. Kriegel, J. Sander, and X. Xu, “A density-based algorithm for discovering clusters in large spatial databases with noise.” in *KDD*, 1996, pp. 226–231.

[8] 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*, Palma de Mallorca, Spain, August 2006, pp. 28–33. [Online]. Available: http://www-lipn.univ-paris13.fr/ guerif/papers/guerif2006asc.pdf

[9] M. Halkidi, Y. Batistakis, and M. Vaziriannis, “On Clustering Validation Techniques,” *Journal of Intelligent Information Systems*, vol. 17, no. 2-3, pp. 107–145, 2001.

[10] ——, “Cluster Validity Methods,” *SIGMOD Record*, vol. 31, no. 2,3, pp. 40–45, 19–27, 2002.

[11] M. F. Hussin, M. S. Kamel, and M. H. Nagi, “An efficient two-level SOMART document clustering through dimensionality reduction,” in *ICONIP*, 2004, pp. 158–165.

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

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

[14] ——, *Self-Organizing Maps*. Berlin: Springer-Verlag, 2001.

[15] 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*, vol. 4193, pp. 681–690, 2006.

[16] T. Martinetz, “Competitive hebbian learning rule forms perfectly topology preserving maps,” in *Proceedings of the International Conference on Artificial Neural Networks (ICANN-93)*, Amsterdam, S. Gielen and B. Kappen, Eds. Heidelberg: Springer, 1993, pp. 427–434.

[17] A. Ocsa, C. Bedregal, and E. Cuadros-Vargas, “DB-GNG: A constructive self-organizing map based on density,” *Proceeding of International Joint Conference on Neural Networks*, pp. 1506–1511, August 2007.

[18] S. R. Pamudurthy, S. Chandrakala, and C. C. Sakhar, “Local density estimation based clustering,” *Proceeding of International Joint Conference on Neural Networks*, pp. 1338–1343, August 2007.

[19] A. Ultsch, “Clustering with SOM: U*C,” in *Proceedings of the Workshop on Self-Organizing Maps*, 2005, pp. 75–82.
[20] L. Vincent and P. Soille, "Watersheds in digital spaces: An efficient algorithm based on immersion simulation," *IEEE Trans. Pattern Anal. Mach. Intell.*, vol. 13, pp. 583-598, 1991.

[21] S.-H. Yue, P. Li, J.-D. Guo, and S.-G. Zhou, "Using greedy algorithm: DBSCAN revisited II," *Journal of Zhejiang University SCIENCE*, vol. 5, no. 11, pp. 1405-1412, 2004.