The paper is oriented to the problem of clustering for large datasets with high-dimensions. We propose a two-phase combined method with regard to high dimensions and exploiting the standard clustering algorithm. The first step of the method is based on the learning phase using artificial neural network, especially Self organizing map, which we find as a suitable method for the reduction of the problem complexity. Due to the fact, that the learning phase of artificial neural networks can be time-consuming operation (especially for large highdimensional datasets), we decided to accelerate this phase using parallelization to improve the computational efficiency. The second phase of the proposed method is oriented to clustering. Because the visualization provided by Self organizing maps is depending on the map dimension, and is not as clear and comprehensible in the cases of clustering applications, we decided to use spectral clustering algorithm to obtain sufficient clusters. According to our results, the proposed combined method is sufficiently rapid and quite accurate.
Artificial neural networks (ANN) are the mathematical models inspired by the
structure and functionality of the biological neural systems capable of parallel
and distributed computation [
The model typically consists of interconnected groups of neurons, organized in the layers of the system. The basic system of ANN has three layers (the input neurons, the second layer of neurons and the output layer of neurons). All the layers are interconnected through synapses, which have assigned weights used for the calculations of network function f (x). The network function is then defined as a composition of other functions appropriate to the neurons on each layer of the network.
ANN is typical of its possibility of learning. Given a class of functions F , learning is a process of finding the optimal solution f ∗ ∈ F for a specific task, using a set of observations. For the efficiency measurement is used a cost function C : F → R such, that for the optimal solution f ∗ is C(f ∗) = min C(f ), ∀f ∈ F .
There are known two basic approaches to the learning phase of ANN: supervised learning, unsupervised learning and their extensions or combinations. Supervised learning is the approach, where the network function is inferred from the supervised training data collection. The set of training examples consists on pairs of the input vectors and the appropriate output values. The network function is then typically used for pattern recognition or classification (for discrete output) or for regression (for continuous output). As an example of commonly used supervised algorithms, we can mention multilayer Perceptron with Backpropagation method.
Unsupervised learning approach is used for solving the problems oriented to discovery and determination of the data structure. Among commonly used algorithms we can include Self organizing maps (SOM) and its extensions. The ANN with unsupervised learning are commonly used for the tasks like clustering, estimation of statistical distributions, filtering or compression problems. 1.1
Self organizing map (SOM), also called Kohonen map, is a type of artificial neural
network invented by professor Teuvo Kohonen in 1982 [
SOM technique has been applied in many spheres like speech recognition
[
The model of SOM consists of two layers of nodes. The input layer for
receiving and transmitting the input information and the output layer called the
map represented the output characteristics. The output layer is commonly
organized as the two-dimensional map of nodes, but there are known extensions as,
for example, hexagonal grid of output layer. The both layers are feed-forward
connected. It is known, that the maps with the smaller grid of the output layer
have the behavior similar to K-means clustering [
The SOM input layer is given by input vectors x ∈ Rn. Each node of this layer is then connected with one of the output nodes K by means of a weight of reference vector wk ∈ Rn, k = 1, . . . , K. During the learning phase, the weight vector wk(t) is computed for the network at time t, where t = 0, 1, . . . is discrete time index for each input vector x(t). The passage through the network at time t is an epoch. The learning (training) phase is performed through competitive learning, where for each training example x(t) is computed similarity to all weight vectors wk(t). The output neuron with the most similar vector is then called as the best matching unit (BMU). The weights of the winning neuron and the neurons in the closest neighborhood are then updated and adjusted for the appropriate input vector. The weight vector initialization is commonly assigned randomly, or by using other data mining methods. Concrete implementation of the SOM depends on the method used for the weight vectors’ actualization during the training phase.
SOM networks are especially suitable for hidden knowledge presentation. Both the structure of data clusters and query result can be easily visualized. For the overall view of learned data, we use the so-called Unified distance matrix (Umatrix), which records the values in clusters and cluster boundaries. The values are assigned to the neuron which wins competition for them, and the distances between neighbouring neurons are recorded with grayness level. Darker colors usually mean greater distance. On the other hand, close data can be colored with similar colors, in this case the boundary between clusters is shown as a steep change in color hue. 1.2
Spectral clustering algorithm uses eigenvalues and eigenvectors of a similarity matrix derived from the data set to find the clusters.
Given a set of data points {x1, . . . xn} ∈ Rl and similarity (cosine measure) aij ≥ 0 between all pairs of the data points xi and xj .
Let G = (V, E) be an undirected graph with vertex set V = {v1, . . . , vn}.
Each vertex vi in this graph represents the data point xi. Two vertices are
connected, if the similarity aij between the corresponding data points xi and xj is
positive, and the edge is weighted by aij . The weighted adjacency matrix of the
graph is the matrix A = (aij ) i, j = 1, . . . , n. If aij = 0 than (vi, vj ) ∈/ E(G).
For undirected graph it governs that A is symmetric. The degree of a vertex
n
vi ∈ V is defined as di = P aij . The degree matrix D is defined as the diagonal
j=1
matrix with the degrees d1, . . . , dn on the diagonal. The unnormalized graph
Laplacian matrix is defined as L = D − A. In[
The survey of data clustering relevant to the clustering document collection
is published in [
Serial SOM Algorithms As conventional variant of the serial algorithm interpretations can be considered standard On-line SOM.
On-line SOM Algorithm is the conventional method, where the weight vectors wk(t) are updated during the training phase recursively for each input vector x(t). The BMU dc is commonly selected by calculating the similarity using Euclidean distance: dk(t) = kx(t) − wk(t)k2, dc(t) ≡ min dk(t).
k The weight vectors are then updated using a learning-rate factor σ(t) and a neighborhood function hck(t):
wk(t + 1) = wk(t) + σ(t)hck(t)[x(t) − wk(t)].
The learning-rate factor σ(t) is used for the correction of the weight vectors;
during the learning phase is reduced. The concrete updated weight vectors wk(t)
are set by the neighbor function hck(t), which determines the distance between
nodes c and k. The distance is typically decreasing during the learning phase,
from an initial value (often comparable to the dimension/or the half of
dimension of the lattice) to the value equal to one neuron (one node in the lattice).
Commonly is used the standard Gaussian neighborhood function. For the serial
online SOM algorithm were published several variants to improve its
computational efficiency; as an example we can mention WEBSOM [
Parallel SOM Algorithms Till lately, most of the conventional algorithms were designed as sequential. The sequential algorithms were well suited to the past generation of computers, which basically performed the operations in the sequential fashion. With the development of the parallel computation, where the operations were performed simultaneously, there is growing the necessity to redesign the serial algorithms to their parallel implementations.
The parallelization of SOM learning algorithms can be implemented by the
network partitioning. The network partitioning is the implementation, where
the neural network is partitioned among the processors. Then, each input data
sample is processed by its assigned processor or the parallel task. The network
partitioning was implemented by several authors [
The main principle of our parallel implementation is based on division of the neural network into the parts, where each part is assigned to one processor. This division is shown in the Fig. 1, where we have the map of 5 × 4 nodes. This map is divided into 3 parts which are associated with 3 processors. Not always there is the possibility to divide the map into the identical parts. In these cases, there is the neural network (map) divided using the principle, that the parts of the network differ in at the most one neuron.
Fig. 1. SOM Map Division The training phase is based on the serial version of the SOM algorithm. Each process finds its own BMU in its part of the map; this node is then compared with other BMU obtained by other processes. The information about the BMU of the whole network is then transmitted to all the processes, which in accordance with this information update weights of the appropriate nodes in their parts of the network. 2.2
The experiment is oriented to the problem of effective clustering for the large datasets with the high-dimension. Due to this reason, we had to find suitable (sufficiently adequate) method for the reduction of the problem complexity. We have decided to used the SOM method. Consider the training set of n-dimensional objects O = {oij ; oi ∈ Rn, i = 1, . . . m}, where |O| = m. SOM allows us to transfer the original problem with m × n dimension to 2-dimensional matrix A of dimension l × l represented by the SOM map, where l max(m, n). Our motivation was to facilitate tasks with objects of high dimension.
Because the visualization provided by SOM is depending on the map dimension, and is not as clear and comprehensible in the cases of clustering applications, we decided to use the appropriate algorithm for clustering. As the SOM map can be thought as a graph, and the node weights can be thought as similarity measures, we decided to use the spectral clustering method for dividing the SOM map into the clusters with the close nodes. In other words, we transformed the SOM map to the similarity matrix of the individual nodes.
For each graph G, represented by the similarity matrix, the second smallest
eigenvalue λ2 of the Laplacian matrix designates algebraic connectivity a(G)
[
By the recursive application of minimal cut to the graph we have obtained the sequence of the clusters. For each connected subgraph Gi we have obtained its a(Gi), algebraic connectivity. The graph division is finished, when a(Gi) becomes descending as presented in Algorithm 1.
Algorithm 1 Application of Spectral Clustering Method to SOM 1. Construction of the SOM map. 2. Consider graph G1 = (V, E), which is given by the similarity matrix A(G1) of dimension l × l from the SOM map. l 3. Construct Laplacian matrix L(G1) = D(G1) − A(G1), dii = P aij . i=1 4. Compute a(G1), u(G1), where algebraic connectivity a(G1) = λ2(G1), u(G1) is appropriate eigenvector. 5. Divide graph Gj to connected subgraphs G0j+1 = {vi ∈ Vj , where ui ≤ 0}, G0j0+1 = {vj ∈ Vj , where uj > 0}, but it is possible that this subgraph is not connected.
Then find the all connected components which create the subgraphs G(ji+)1. 6. For each subgraph compute a(G(ji+)1) and appropriate u(Gij+1). 7. If a(Gj+1) < θ then do not divide else step 5, where θ ∈ R is the threshold for algebraic connectivity. 3
The experiments were divided into two phases according to the phases of proposed algorithm. The first phase of the experiments was oriented to the acceleration of the SOM algorithm. As mentioned above, we have tested the parallel implementation of the SOM algorithm training phase for various dimensions of the SOM map and the input vector.
The second phase of the experiments was related to the division of the SOM map using spectral clustering. Both phases are documented by obtained issues and the appropriate figures, see below. 3.1
All the experiments were performed on Windows HPC server 2008 with 6 computing nodes, where each node has 8 processors with 12 GB of memory.
The first experiment was provided on the training set of 300 2-dimensional samples, while the dimension of the neural network (SOM map) was changed. The outputs are presented in the Table 1, where the records with asterisk (*) were provided only by one computing node. In these cases, there is not provided the network communication between processes and due to this fact is the computation faster.
The second experiment was provided on the map with selected dimension of 100 × 100 nodes, while the input vector dimension of the training data set was changed. There was used the training set of 150 records. The outputs are presented in the Table 2, where the records with asterisk (*) were provided only by one computing node. In this cases, there is not provided the network communication between processes; due to this fact is the computation faster.
As we can see from Tables 1 and 2, the acceleration of the SOM algorithm is appreciable. With growing number of processors is increasing the computation effectiveness, and the computational time is sufficiently reducing. 3.2
The next phase of the experiments was oriented to the testing of the proposed algorithms for the SOM map division using spectral clustering, concretely with the Fiedler vector. We have used three training data collections called TwoDiamonds, Lsun a Hepta from the Fundamental Clustering Problems Suite (FCPS)1. Short description of selected dataset used in our experiments is given in Table 3.
For comprehensible interpretation we have used U-matrix and its 3D visualization of the SOM map obtained after the dimension reduction of the input dataset . The visualization of the first input data set TwoDiamonds, the SOM map after the first phase of proposed algorithm and its division by spectral clustering are presented on the Fig. 2. The U-matrix for this dataset, presented on the Figs. 2(b) and 2(c), is accurately matching to the division provided by the Fiedler vector on the Fig. 2(d).
The same situation occurs for the second input data set Lsun, for visualization see Fig. 3(a). As we can see from the Figs. 3(b) and 3(c), the division provided by the SOM and Fiedler vector, Fig. 3(d), is also accurately matching as in the experiment with the first dataset.
The visualization of the third input data set Hepta, the SOM map after the first phase of proposed algorithm and its division by spectral clustering are presented on the Fig. 4. From the Figs. 4(b) and 4(c) we can see, that the division provided by Fig. 4(d) is not as corresponding as in both previous experiments. The experiment with dataset Hepta demonstrates, that some edges are determined in spectral clustering differently then in U-Matrix, but both results are correct. 4
In this paper we presented the parallel implementation of the SOM neural network algorithm. Parallel implementation was tested on HPC cluster containing 6 nodes and 40 processor cores. The achieved speed-up was very good.
Moreover, the partitioning of the resulting SOM map using spectral clustering method was presented. The spectral clustering was applied on U-matrix. This method automatically detected the parts of the SOM that represent the 1 http://www.uni-marburg.de/fb12/datenbionik/data?language_sync=1
TwoDiamonds, n = 800, dimension = 2, classes = 2, main problem: cluster border defined by density 1.5 1 0 Hepta, n = 212, dimension = 3, classes = 7 main problem: none, i.e clear defined clusters 4 2 clusters in original high-dimensional data. The detected clusters correspond to the clusters perceived by the human being.
In the future work we intend to focus on more precise specification of the threshold for the algebraic connectivity in the spectral clustering.
This work is partially supported by Grant of Grant Agency of Czech Republic No. 205/09/1079, and SGS, VSB – Technical University of Ostrava, Czech Republic, under the grant No. SP2011/172.