Self-Organizing Map with False Neighbor Degree
between Neurons for Effective Self-Organization
Haruna Matsushita and Yoshifumi Nishio
Department of Electrical and Electronic Engineering, Tokushima University
2-1 Minami-Josanjima, Tokushima 770-8506, JAPANemail: {haruna, nishio}@ee.tokushima-u.ac.jp
Keywords: Self-Organizing Map (SOM), unsupervised learning, learning









(a)
(b)
Figure 1: What are the “neighbors”? The houses B and
C is A’s next-door neighbors on the left and on the right,
respectively. (a) The house B is at the top of a mountain.
(b) The river between A and B does not have a bridge.

LD

UN

I

VE

RSI

Proceedings of the 6th International Workshop on Self-Organizing Maps (WSOM 2007)
Published by the Neuroinformatics Group, Bielefeld University, Germany
All contributions to WSOM 2007 are available online at: http://biecoll.ub.uni-bielefeld.de

EFE



EL



BI

Since we can accumulate a huge amount of data in recent years, it is important to investigate various clustering methods [1]. Then, the Self-Organizing Map (SOM)
has attracted attention for its clustering properties. SOM isan unsupervised neural network introduced by Kohonen in1982 [2] and is a model simplifying self-organization process of the brain. SOM obtains statistical feature of input
data and is applied to a wide field of data classifications.
We can obtain the map reflecting the distribution state of
input data using SOM. In the learning algorithm of SOM,
a winner, which is a neuron with the weight vector closest to the input vector, and its neighboring neuron are updated, regardless of the distance between the input vector
and the neighboring neuron. For this reason, if we apply
SOM to clustering of the input data which includes some●

1 Introduction

clusters located at distant location, there are some inactive
neurons between clusters. Because inactive neurons are ona part without the input data, we are misled into thinking
that there are some input data between clusters.
Meanwhile, in the real world, it is not always true that the
next-door house is close to my house. For example, a casethat the next-door house is at the top of a mountain whereas
my house is at the foot (as Fig. 1(a)), and another case that
there is a river, which does not have a bridge, between myhouse and my next-door house (as Fig. 1(b)). This meansthat “neighbors” are not always “true neighbors”.
On the other side, the synaptic strength is not constantin the brain. So far, the Growing Grid network was proposed in 1985 [3]. Growing Grid increases the neighborhood distance between neurons by increasing the numberof neurons. However, there are few researches changing
the synaptic strength as far as we know even though there
are algorithms which increase the number of neurons or
consider rival neurons [4], [5].
In our past study, we proposed the algorithm whichchanges the neighborhood distance between neurons [6].
However, the algorithm used the rank order of the distances
between the input data and weight vectors of neurons in addition to changing the neighborhood distance. Thus the algorithm did not work well if the positions of all the weightvectors of the neurons were not taken into consideration.
Moreover, the algorithm needs a lot of calculation amountbecause we have to calculate the rank order at every updating of the weight vector.
In this study, we propose a new SOM algorithm, SOM
with False Neighbor degree between neurons (called FNSOM) without the rank order. False-neighbor degrees areallocated between adjacent rows and adjacent columns of
FN-SOM. We find the neuron q which has become the winner least frequently, and the neurons, which is the most distant from q in a set of direct topological neighbors of q, aresaid to be “false neighbors” of q. The initial values of allof the false-neighbor degrees are set to zero, however, they
are increased with learning, and the false-neighbor degrees
act as a burden of the distance between map nodes when
the weight vectors of neurons are updated.
We explain the learning algorithm of FN-SOM in detailin Section 4. The learning behaviors of FN-SOM for 2-

TY

Abstract— In the real world, it is not always true thatthe nextdoor house is close to my house, in other words,“neighbors” are not always “true neighbors”. In this study,
we propose a new Self-Organizing Map (SOM) algorithm,
SOM with False Neighbor degree between neurons (called
FN-SOM). The behavior of FN-SOM is investigated withlearning for various input data. We confirm that FN-SOM
can obtain the more effective map reflecting the distribution
state of input data than the conventional SOM and Growing
Grid.

2

i

(1)

where k · k is the distance measure, Euclidean distance.
(SOM3) The weight vectors of the neurons are updated aswi (t + 1) = wi (t) + hc,i (t)(xj − wi (t)),(2)

where t is the learning step. hc,i (t) is called the neighborhood function and is described as a Gaussian function;¶µkr i − r c k2,
(3)hc,i (t) = α(t) exp −2σ 2 (t)where kr i − r c k is the distance between map nodes c andi on the map grid, α(t) is the learning rate, and σ(t) corresponds to the width of the neighborhood function. Bothα(t) and σ(t) decrease with time, in this study, we use following equations;α(t) = α0 (1 − t/tmax ), σ(t) = σ0 (1 − t/tmax ),(4)

where α0 and σ0 are the initial value of α and σ, respectively, and tmax is the maximum number of the learning.
(SOM4) The steps from (SOM1) to (SOM3) are repeated
for all the input data.

3 Growing Grid
We explain an overview of the Growing Grid. The networkof Growing Grid consists of nm neurons located at a rectangular n × m grid. Each neuron has an d-dimensional

where α0 is a constant learning rate, and σ0 is a constantwidth parameter. dg (c, i) is the distance on the grid between a winner c and each neuron i and is calculated bycity-block distance (which is also known as L1 -norm). At
each learning step, the winning frequency of c is incremented by γc new = γc old + 1.
After n × m × λg number of learning steps have been
performed, we determine the neuron q which has become
the winner most frequently;
q = arg max{γi }.
i(7)

We find the neuron f which is with the most different
weight vector in 1-neighbor of q. We insert a new row (orcolumn) between q and f . The weight vectors of the newneurons are interpolated from their neighbors which does
increase the density of weight vectors in the vicinity of wq .
The number n of rows (or m of columns) are increased,
then all the winning frequency is reset. We continue with
the next round of learning unless nm ≥ nmmax is fulfilled.
The growth process is finished, we perform the fine-tune
the weight vectors using a decreasing learning rate. We
perform t′max = n × m × λf steps according to Eq. (5)′′using α(t′ ) = α0 (α1 /α0 )t /tmax . t′ denotes the learning
step in the fine-tuning phase which starts after the growth
step is finished.

4 SOM with False Neighbor Degree(FN-SOM)
We explain a new SOM algorithm, SOM with False Neighbor Degree between neurons (FN-SOM). False-neighbor
degrees of rows Rr (1 ≤ r ≤ n − 1) are allocated between
adjacent rows of FN-SOM with the size of n × m grid (asFig. 2). Likewise, false-neighbor degrees of columns Ck(1 ≤ k ≤ m − 1) are allocated between adjacent columnsof FN-SOM. In other words, R1 means the false-neighbor
degree between neurons of the 1st row and the 2nd row, andC4 is the false-neighbor degree between neurons of the 4thcolumn and the 5th column. The initial values of all of thefalse-neighbor degrees are set to zero, and the initial valuesof all the weight vectors are given over the input space at
LD

UN

I

VE

RSI

Proceedings of the 6th International Workshop on Self-Organizing Maps (WSOM 2007)
Published by the Neuroinformatics Group, Bielefeld University, Germany
All contributions to WSOM 2007 are available online at: http://biecoll.ub.uni-bielefeld.deEFE

c = arg min{kwi − xj k},where hGc,i (t) is the neighborhood function of Growing
Grid;
¶
µ
dg 2 (c, i),(6)hGc,i (t) = α0 exp −
2σ0 2

EL

(SOM1) An input vector xj is inputted to all the neurons
at the same time in parallel.
(SOM2) Distances between xj and all the weight vectors
are calculated. The winner, denoted by c, is the neuron withthe weight vector closest to the input vector xj ;

(5)

BI

We explain the learning algorithm of the conventional SelfOrganizing Map (SOM). SOM consists of n × m neurons
located at a regular low-dimensional grid, usually a 2-D
n × m rectangular grid. The basic SOM algorithm is iterative. Each neuron i has a d-dimensional weight vector wi = (wi1 , wi2 , · · · , wid ) (i = 1, 2, · · · , nm). The
initial values of all the weight vectors are given over the
input space at random. The range of the elements of ddimensional input data xj = (xj1 , xj2 , · · · , xjd ) (j =1, 2, · · · , N ) are assumed to be from 0 to 1.

wi (t + 1) = wi (t) + hGc,i (t)(xj − wi (t)),●

2 Self-Organizing Map

weight vector wi as the conventional SOM. A winning frequency γi is associated with each neuron and is set to zero
initially.
An input vector xj is inputted to all the neurons, and awinner c is found according to Eq. (1). The weight vectorsof the neurons are updated according toTYdimensional input data, Swiss Roll data and Iris data areinvestigated. Learning performance is evaluated both visually and quantitatively using two measurements. Furthermore, the results are compared with those obtained by
the conventional SOM and Growing Grid. We can confirm that there are few inactive neurons using FN-SOM,
and FN-SOM can obtain the most effective map reflecting
the distribution state of input data in the three algorithms.

3

the false-neighbors every time when the learning steps are
performed for λ input data.

Cm-1

R1

Considering F alse-N eighbors(FN-SOM7) We find the neuron q which has become thewinner least frequently:

R2nq = arg min{γi },

(11)

i

Rn-1
m

Figure 2: A false-neighbor degree of row Rr (1 ≤ r ≤n − 1) and column Ck (1 ≤ k ≤ m − 1). Neurons of
FN-SOM are located at a n × m rectangular grid.

random. Moreover, a winning frequency γi is associatedwith each neuron and is set to zero initially.
Learning Steps(FN-SOM1) An input vector xj is inputted to all the neurons at the same time in parallel.
(FN-SOM2) Distances between xj and all the weight vectors are calculated, and a winner c is found according to
Eq. (1).
(FN-SOM3) Increment the winning frequency of winner c
by γc new = γc old + 1.
(FN-SOM4) The neighboring distances between the winner c and the other neurons are calculated. For instance,
for two neurons s1 , which is located at r1 -th row and k1 -thcolumn, and s2 , which is located at r2 -th row and k2 -th column, the neighboring distance is defined as the following
measure;kX
2 −1

Ck )2 ,

k=k1

(8)
Pr2 −1R
means
thewhere r1 < r2 , k1 < k2 , namely, r=rr1
sum of the false-neighbor degrees between the rows r1 andPk2 −1
r2 , and k=k1 means the sum of the false-neighbor degrees between the column k1 and k2 .
(FN-SOM5) The weight vectors of the neurons are updatedaswi (t + 1) = wi (t) + hF c,i (t)(xj − wi (t)),

i ∈ Nq 1(12)(FN-SOM9) A false-neighbor degree between q and its
false neighbor f , Rr or Ck , is increased. If q and f arein the r-th row and in the k-th and (k + 1)-th column (asFig. 3(a)), the false-neighbor degree Ck between columns
k and k + 1 is increased according to¶¾½µ
kwf − wq k4newold, (13)Ck= Ck + 1 − exp −2σF 2where σF is the constant width parameter of the Gaussianfunction.
In the same way, if q and f are in the k-th column and inthe (r +1)-th and r-th row (as Fig. 3(b)), the false-neighbor
degree Rr between rows r and r + 1 is also increased according to¶¾½µ
kwf − wq k4newold. (14)Rr= Rr + 1 − exp −2σF 2(FN-SOM10) The winning frequency of all the neurons arereset to zero:γi = 0.
(15)(FN-SOM11) The steps from (FN-SOM1) to (FN-SOM10)
are repeated for all the input data.

5 Experimental Results(9)

where hF c,i (t) is the neighborhood function of FN-SOM:¶µdf (c, i).
(10)hF c,i (t) = α(t) exp − 2
2σ (t)Pnm(FN-SOM6) If i=1 γi ≥ λ is satisfied, we find the falseneighbors and increase the false-neighboring degree, according to steps from (FN-SOM7) to (FN-SOM10). If not,we perform step (FN-SOM11). In other words, we consider

We apply FN-SOM to various input data and compare FNSOM with the conventional SOM and Growing Grid.

5.1 For 2-dimensional data
First, we consider 2-dimensional input data as shown in
Fig. 4(a). The input data is generated artificially as follows. Total number of the input data N is 1200, and the
input data include three clusters. 400 data are distributed
within a range from 0.1 to 0.9 horizontally and from 0.05
LD

UN

I

VE

RSI

Proceedings of the 6th International Workshop on Self-Organizing Maps (WSOM 2007)
Published by the Neuroinformatics Group, Bielefeld University, Germany
All contributions to WSOM 2007 are available online at: http://biecoll.ub.uni-bielefeld.de

EFE

r=r1

Rr )2 +(|k1 −k2 |+

i

EL

rX
2 −1

f = arg max{kwi − wq k},BIdf (s1 , s2 ) = (|r1 −r2 |+where, if more than one γi is minimum, the neuron i withthe smallest index is chosen.
(FN-SOM8) A false-neighbor f of q is chosen from the setof direct topological neighbors of q denoted as Nq 1 .f is theneuron whose weight vector is most distant from q:

●

C2

TY

C1

4

1

1

1

1

0.9

0.9

0.9

0.9

0.8

0.8

0.8

0.8

0.7

0.7

0.7

0.7

0.6

0.6

0.6

0.6

0.5

0.5

0.5

0.5

0.4

0.4

0.4

0.4

0.3

0.3

0.3

0.3

0.2

0.2

0.2

0.2

0.1

0.1

0.1

0.1

0
0

0.6

0.4

0.2

0.8

1

0
0

0.4

0.2

(a)

0.6

0.8

1

(b)

0
0

0.2

0.4

0.6

0.8

1

0
0

0.2

0.4

(c)

0.6

1

0.8

(d)

Figure 4: Learning results of three algorithms for 2-D data. (a) Input data. (b) Conventional SOM. (c) Growing Grid.
(d) FN-SOM.

(a)

(b)

Figure 3: Increment the false-neighbor degree. (a) q and its
false-neighbor f are in the 3rd row and in the 2nd and 3rdcolumn, respectively. Then, the false-neighbor degree C2
between columns 2 and 3 is increased by Eq. (13). (b) q
and f are in the 2nd column and in the 4th and 3rd row,
respectively. Then, the false-neighbor degree R3 between
rows 3 and 4 is increased by Eq. (14).

Quantization Error Q: This measures the average distance between each input vector and its winner;NQ=
to 0.15 vertically. The other 400 data are distributed withina range from 0.1 to 0.9 horizontally and from 0.45 to 0.55
vertically. The remaining 400 data are distributed withina range from 0.1 to 0.9 horizontally and from 0.85 to 0.95
vertically. All the input data are sorted at random.
Both the conventional SOM and FN-SOM has nm =100 neurons (10 × 10). Growing Grid starts learning witha 2 × 2 neurons, and new rows and columns are inserted aslong as the number of neurons is less than nmmax = 100.
We repeat the learning 15 times for all input data, namely
tmax = 18000. The parameters of the learning are chosen
as follows;(For SOM)
α0 = 0.3, σ0 = 4,
(For Growing Grid)α0 = 0.1, σ0 = 0.9, λg = 20, α1 = 0.005, λf = 100,
(For FN-SOM)
α0 = 0.3, σ0 = 4, σF = 0.05, λ = 500,

1 X
kxj − w̄j k2 ,
N j=1

(16)

where w̄j is the weight vector of the corresponding winner of the input vector xj . Therefore, the small value Q is
more desirable.
Neuron Utilization U: This measures the percentage ofneurons that are the winner of one or more input vector
in the map [5];
nm
1 X
ui ,
(17)
U=
nm i=1

where ui = 1 if the neuron i is the winner of one or more
input data. Otherwise, ui = 0. Thus, U nearer 1.0 is moredesirable.
The calculated two measurements are shown in Table. 1.
The quantization error Q of FN-SOM is the smallest value
in the three algorithms, and by using FN-SOM, the quantization error Q has improved 18.9% from using the conventional SOM. This is because the result of FN-SOM has
no inactive neurons, therefore, the more neurons can selforganize the input data. This is confirmed by the neuron
LD

UN

I

VE

RSI

Proceedings of the 6th International Workshop on Self-Organizing Maps (WSOM 2007)
Published by the Neuroinformatics Group, Bielefeld University, Germany
All contributions to WSOM 2007 are available online at: http://biecoll.ub.uni-bielefeld.de

EFE

q

EL

R3

BI

f

f

●

q

where we use the same α0 and σ0 to SOM and FN-SOM forthe comparison and the confirmation of the false-neighbor
degree effect.
The learning results of the conventional SOM and Growing Grid are shown in Figs. 4(b) and (c), respectively. We
can see that there are some inactive neurons between threeclusters. The other side, the result of FN-SOM is shown in
Fig. 4(d). We can see from this figure that there are no inactive neurons between three clusters, and FN-SOM can obtain the more effective map reflecting the distribution stateof input data than SOM and Growing Grid.
Furthermore, in order to the learning performance of FNSOM in comparison with the conventional SOM and Growing Grid, we use the following two measurements to evaluate the training performance of the three algorithms.

TY

C2

5

Next, we consider “Swiss Roll” data used by Tenenbaum etal. [7], as shown in Fig. 5. Total number of the input data
N is 1000, and the input data are normalized and are sorted
at random.

1
0.5
0
1
0.8

1
0.8

0.6
0.6

0.4
0.4

0.2

0.2

0

0

Figure 5: Swiss Roll data for 3-dimensional input data.

We repeat the learning 15 times for all input data, namely
tmax = 15000. The learning conditions are the same usedin Fig. 4 except σF = 0.03 and λg = 300 for FN-SOM.
The learning results of the three algorithms are shownin Figs. 6(a)-(c), respectively. Furthermore, Figs. 6(d)-(f)show the results of Figs. 6(a)-(c) in 2-D (namely, X-Y coordinate), respectively. We can see from these figures that
FN-SOM can obtain the most effective map reflecting the
distribution state of input data.
The calculated the quantization error Q and the neuron utilization U are shown in Table. 2. We confirm thatthe quantization error Q of FN-SOM is the smallest value
in the three algorithms, and Q of FN-SOM has improved
14.6% from using the conventional SOM. Moreover, theneuron utilization U of FN-SOM is the largest value in thethree algorithms and is 1.0, which is the maximum value,as in the case of the 2-dimensional input data. From thistable and Fig. 6, we can say that the result of FN-SOM has
the fewest inactive neurons.

Furthermore, we apply FNN-SOM to the real world clustering problem. We use the Iris plant data [8] as real data.
This data is one of the best known databased to be foundin pattern recognition literatures [9]. The data set contains
three clusters of 50 instances respectively, where each classrefers to a type of iris plant. The number of attributes is four
as the sepal length, the sepal width, the petal length and thepetal width, namely, the input data are 4-dimension. The
three classes correspond to Iris setosa, Iris versicolor andIris virginica, respectively. Iris setosa is linearly separablefrom the other two, however Iris versicolor and Iris virginica are not linearly separable from each other.
We repeat the learning 100 times for all input data,
namely tmax = 15000. The input data are normalized andare sorted at random. The learning conditions are the sameused in Fig. 4 except σF = 0.02 for FN-SOM.
The calculated quantization error Q and the neuron utilization U are shown in Table. 3. We confirm that the quantization error Q of FN-SOM is the smallest value in thethree algorithms, and Q of FN-SOM has improved 16.7%
from using the conventional SOM. This is because the result of FN-SOM hardly has inactive neurons between Iris
setosa and the other two, therefore, the more neurons canself-organize the data of Iris versicolor and Iris virginica.
The neuron utilization U of FN-SOM is the largest value
in the three algorithms. From these results, we can confirm
the efficiency of FN-SOM.
Table 3: Quantization error Q and Neuron utilization U for
Iris data.
FN-SOM
Growing Grid
SOM
0.00150.00270.0018Q
0.78000.73150.7300U

6 Conclusions
In this study, we have proposed a new SOM algorithm,
SOM with False Neighbor degree between neurons (called
FN-SOM). False-neighbor degrees are allocated between
adjacent rows and adjacent columns of FN-SOM. The initial values of all of the false-neighbor degrees are set tozero, however, they are increased with learning, and thefalse-neighbor degrees act as a burden of the distance beLD

UN

I

VE

RSI

Proceedings of the 6th International Workshop on Self-Organizing Maps (WSOM 2007)
Published by the Neuroinformatics Group, Bielefeld University, Germany
All contributions to WSOM 2007 are available online at: http://biecoll.ub.uni-bielefeld.de

EFE

5.2 For Swiss Roll data

5.3 For Iris dataEL

FN-SOM
5.0902 × 10−4
1.0

BI

Q
U

Growing Grid
7.1131 × 10−40.8056SOM
6.2756 × 10−40.8200●

Table 1: Quantization error Q and Neuron utilization U for
2-dimensional input data.

Table 2: Quantization error Q and Neuron utilization U for
Swiss Roll data.
FN-SOM
Growing Grid
SOM
0.01040.01230.0121Q
1.0
0.98210.9400U

TY

utilization U . The neuron utilization U of FN-SOM is thelargest value in the three algorithms and is 1.0 which is the
maximum value. It means that all the neurons of FN-SOM
are the winner of one or more input data, namely, no neurons are inactive neurons.

6

1

1

1

0.5

0.5

0.5

0
1

0
1

0
1

0.8

1

0.6

0.8

0.8

1

0.6

0.6

0.4

(a)

0.4

0.2

(b)

(c)

0.9

0.9

0.9

0.8

0.8

0.7

0.7

0.7

0.6

0.6

0.6

0.5

0.5

0.5

0.4

0.4

0.4

0.3

0.3

0.3

0.2

0.2

0.2

0.1
0.4

0.6

0.8

1

0
0

0

1

0.8

0.1

0.2

0

0

1

0.2

0.6

0.4

0.2

0

0

1

0
0

0.8

0.4

0.2

0.2

0

1

0.6

0.6

0.4

0.4

0.2

0.8

0.8

0.1
0.2

0.6

0.4

(d)

(e)

0.8

1

0
0

0.2

0.4

0.6

0.8

1

(f)

Figure 6: Learning results of three algorithms for Swiss Roll data. (a) Conventional SOM. (b) Growing Grid. (c) FNSOM. (d) Result of SOM shown in 2-D (X-Y coordinate). (e) Result of Growing Grid shown in 2-D. (f) Result of
FN-SOM shown in 2-D.

I

RSI

EFE

UN

EL

LD

VE

Proceedings of the 6th International Workshop on Self-Organizing Maps (WSOM 2007)
Published by the Neuroinformatics Group, Bielefeld University, Germany
All contributions to WSOM 2007 are available online at: http://biecoll.ub.uni-bielefeld.de

BI[1] J. Vesanto and E. Alhoniemi, “Clustering of the
Self-Organizing Map,” IEEE Trans. Neural Networks,
vol. 11, no. 3, pp. 586–600, 2002.
[2] T. Kohonen, Self-organizing Maps, Berlin, Springer,
1995.
[3] B. Fritzke, “Growing Grid – a self-organizing network with constant neighborhood range and adaptation strength,” Neural Processing Letters, vol. 2, no. 5,
pp. 9–13, 1995.
[4] L. Xu, A. Krzyzak and E. Oja, “Rival penalized competitive learning for clustering analysis, RBF net, and●References

curve detection,” IEEE Trans. Neural Networks, vol. 4,
no. 4, pp. 636–649, 1993.
[5] Y. Cheung and L. Law, “Rival-Model Penalized SelfOrganizing Map,” IEEE Trans. Neural Networks,
vol. 18, no. 1, pp. 289–295, 2007.
[6] H. Matsushita and Y. Nishio, “Self-Organizing Map
Considering False Neighboring Neuron,” Proc. of ISCAS’07, 2007.
[7] J. B. Tenenbaum, V. de Silva and J. C. Langford, “A
global geometric framework for nonlinear dimensionality reduction,” Science, vol. 290, pp. 2319–2323,
2000.
[8] D. J. Newman, S. Hettich, C. L. Blake and C. J. Merz,
UCI Repository of Machine Learning Database, 1998,[http://www.ics.uci.edu/ mlearn/MLRepository.html].
[9] R. A. Fisher, “The Use of Multiple Measurements in
Taxonomic Problems,” Annual Eugenics, no.7, part II,
pp. 179–188,1936.

TY

tween map nodes when the weight vectors of neurons are
updated. We have applied FN-SOM to 2-dimensional data,
Swiss Roll data and Iris data, and we have investigatedthe learning behaviors of FN-SOM. Furthermore, the results were compared with those obtained by the conventional SOM and Growing Grid. We have confirmed thatthe quantization error of FN-SOM was the smallest value
in the three algorithms. Moreover, the neuron utilizationof FN-SOM was the largest value in the three algorithms.
From these results, we have confirmed the efficiency of FNSOM.
In the future we intend to investigate FN-SOM in moredetail in particular its use for high-dimensional data.