Growing Grid with False-Neighbor Degree
Haruna Matsushita† and Yoshifumi Nishio††Department of Electrical and Electronic Engineering, Tokushima University
2–1 Minami-Josanjima, Tokushima 770–8506, JAPAN
Email: {haruna, nishio}@ee.tokushima-u.ac.jp
Abstract
We apply the self-organization considering falseneighbor degree to the fine-tuning of Growing Grid after
the growth process is finished. This study proposes a Growing Grid with False-Neighbor degree (FN-GG). We confirm
that FN-GG can self-organize the input data, which is in arectangular input space, most effectively.
1. Introduction
It is important to investigate various clustering methods [1], since we can accumulate a huge amount of data
in recent years. The Self-Organizing Map (SOM) is an unsupervised neural network [2] and has attracted attention
for its clustering properties. SOM can obtains statisticalfeatures of input data, so, it is simplified model of the selforganization process of the brain.
However, the topology of the conventional SOM has tobe fixed in advance. It is difficult to understand statistical feature of the high-dimensional input data and choose
an appropriate topology in advance. Therefore, Growing
Grid network [3], which one kinds of SOM, was proposed.
The network structure is a rectangular grid which increases
its size during learning. By inserting complete rows orcolumns of neurons, the network can adapt its height/width
ratio to the distribution of the input data automatically.
In our past study, we have proposed a new SOM algorithm, SOM with False-Neighbor degree between neurons(called FN-SOM) [5]. False-Neighbor degrees are allocated between adjacent rows and adjacent columns of FNSOM. They are increased with learning and act as a burdenof the distance between map nodes when the weight vectorsof neurons are updated.
In this study, we combine the concept of Growing
Grid and FN-SOM and propose a Growing Grid withFalse-Neighbor degree (called FN-GG). We apply the selforganization considering false-neighbor degree to the finetuning of Growing Grid after the growth process is finished.
We explain the learning algorithm of FN-GG in detail in Sect. 2. The learning behaviors of FN-GG for 2dimensional input data are investigated with applying to theclustering in Sect. 3.1. In addition, we apply FN-GG to thefeature extraction problem in Sect. 3.2. Learning performance is evaluated both visually and quantitatively using
three measurements in comparison with the conventional

SOM, Growing Grid and FN-SOM. From these results, we
confirm that the results of FN-GG have the fewest inactive
neurons and its map topology is the most appropriate forthe input data which is in a rectangular input space.
2. Growing Grid with False-Neighbor Degree
We explain the learning algorithm of the Growing Grid
with False-Neighbor Degree (FN-GG). The network of FNGG consists of nm neurons located at a rectangular n × m
grid. Each neuron has a d-dimensional weight vector wi
wi = (wi1 , wi2 , · · · , wid ) (i = 1, 2, · · · , nm) as the conventional SOM. The initial values of all the weight vectors
are given over the input space at random. A winning frequency γi is associated with each neuron and is set to zero
initially. The range of the elements of d-dimensional input data xj = (xj1 , xj2 , · · · , xjd ) (j = 1, 2, · · · , N ) are
assumed to be from 0 to 1.
2.1. Learning(FN-GG1) An input vector xj is inputted to all the neurons
at the same time in parallel.
(FN-GG2) Distances between xj and all the weight vectors
are calculated. A winner, denoted by c, is the neuron withthe weight vector closest to the input vector xj ;c = arg min{kwi − xj k},i(1)where k · k is the distance measure, in this study, the Euclidean distance is used.
(FN-GG3) Increment of the winning frequency of winner c
by γc new = γc old + 1.
(FN-GG4) The weight vectors of the neurons are updated
according towi (t + 1) = wi (t) + hGc,i (t)(xj − wi (t)),(2)

where hGc,i (t) is the neighborhood function of FN-GG;()
dg 2 (c, i)
hGc,i (t) = α0 exp −
,
(3)
2σ0 2
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) as- 74 -

dg (s1 , s2 ) = |r1 − r2 | + |k1 − k2 |,(4)where s1 is located at r1 -th row and k1 -th column, and s2
is located at r2∑-th row and k2 -th column.
nm(FN-GG5) If i=1 γi ≥ λg is satisfied, we insert newrows and columns according to steps from (FN-GG6) to(FN-GG9). If not, we return to (FN-GG1).
2.2. Insertion of new rows and columns(FN-GG6) 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 }.

where t0 denotes the learning step in the fine-tuning phasewhich starts after the growth phase is finished.
dg (c, i) is calculated considering false-neighbor degrees.
For instance, for two neurons s1 , which is located at r1 -th
row and k1 -th column, and s2 , which is located at r2 -th
row and k2 -th column, the neighboring distance is definedas the following measure;
)
(
r∑
2 −1
df (s1 , s2 ) = |r1 − r2 | +
Rr
(

(5)

i

+

r=r1

|k1 − k2 | +

k∑
2 −1

)
Ck

(9)
,

k=k1

We find the neuron f which is with the most different
weight vector in direct topological neighbors of q denotedas Nq 1 .
(FN-GG7) We insert a new row (or column) between q and
f . Without loss of generality, we assume that q and f arein the r-th row and k-th and (k + 1)-th columns. We insert
a new column k 0 with n neurons between columns k andk + 1. The weight vectors of the new neurons are interpolated from their neighbors which does increase the densityof weight vectors in the vicinity of wq .
()
wrk0 = 0.5 wrk + wr(k+1) , 1 ≤ r ≤ n. (6)(FN-GG8) The number n of rows (or m of columns) are
increased; n = n + 1, then all the winning frequencies arereset: γi = 0.
(FN-GG9) If nm ≥ nmmax is fulfilled, we stop growth
process and perform Fine-tuning of the weight vectors according to steps from (FN-GG10) to (FN-GG15). If not,we continue with the next round of learning, i.e., return to(FN-GG1).

∑r2 −1
where r1 < r2 , k1 < k2 , namely, r=r
Rr means the1
sum of the false-neighbor degrees between the rows r1 and∑k2 −1
r2 , and k=k
Ck means the sum of the false-neighbor de1
grees between thecolumn k1 and k2 .
∑nm
(FN-GG11) If i=1 γi ≥ λ is satisfied, we find the falseneighbors and increase the false-neighboring degree, according to steps from (FN-GG12) to (FN-GG15). If not,we return to (FN-GG10).
(FN-GG12) We find a set of neurons S which have never
become the winner:
S = {i | γi = 0}.

If the neurons, which have never become the winner, do
not exist, namely S = ∅, we return to (FN-GG10) without
considering the false-neighbors.
(FN-GG13) A false-neighbor fq of each neuron q in S ischosen from the set of Nq 1 . fq is the neuron whose weightvector is most distant from q;
fq = arg max{kwi − wq k}, q ∈ S, i ∈ Nq 1 .
i2.3. Fine-tuning considering false-neighbors
After the growth process is finished, the network has
false-neighbor degrees. The false-neighbor degrees of rows
Rr (1 ≤ r ≤ n − 1) and of columns Ck (1 ≤ k ≤ m − 1)
are allocated between adjacent rows and columns of FNGG, respectively. The initial values of Rr and Cr are set tozero.
(FN-GG10) We fine-tune the weight vectors using a decreasing learning rate with considering the false-neighbors.
We perform t0max = n × m × λf steps according to steps
from (FN-GG1) to (FN-GG4). λf denotes how many finetuning steps per neurons are performed.
In Eq. (2), we use following neighborhood function
hF c,i (t0 ) in place of hGc,i (t)()
df 2 (c, i)
hF c,i (t0 ) = α(t0 ) exp −
.
2σ02

0

0

(11)

(FN-GG14) A false-neighbor degree between each q andits false-neighbor fq , Rr or Ck , is increased. If q and fq
are in the r-th row and in the k-th and (k + 1)-th column,
the false-neighbor degree Ck between columns k and k + 1
is increased according to
Ck new = Ck old +

1
.
n

(12)

In the same way, if q and fq are in the k-th column and inthe (r + 1)-th and r-th row, the false-neighbor degree Rrbetween rows r and r + 1 is also increased according to
Rr new = Rr old +

1
.
m

(13)

(FN-GG15) The winning frequency of all the neurons arereset to zero: γi = 0.

(7)
3. Experimental Results

where α(t0 ) is time-dependent learning rateα(t0 ) = α0 (α1 /α0 )t /tmax ,

(10)

(8)

We apply FN-GG to various input data and compare withthe conventional SOM, Growing Grid and FN-SOM.

- 75 -

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

0.2

0.4

0.6

0.8

1

0.2
0

(a)

0.2

0.4

0.6

0.8

1

0.2
0

(b)

0.2

0.4

0.6

0.8

1

0.2
0

0.2

(c)

0.4

0.6

0.8

1

(d)

Figure 1: Learning results for 2-dimensional data. (a) Conventional SOM. (b) FN-SOM. (c) Growing Grid. (d) FN-GG.
Map size of (c) and (d) after learning are 9 × 12.
0.2

0.25

0.14

0.16

0.2

0.2
0.12

0.14
0.15

0.12

0.15

0.1

0.1

0.08

0.1

0.1

0.08

0.06

0.06
0.05

0.04

(a)

0.25

0.16

0.18

0.05

0.04

(b)

(c)

(d)

Figure 2: U-matrix of each learning result. (a) Conventional SOM. (b) FN-SOM. (c) Growing Grid. (d) FN-GG.

3.1. Application to ClusteringFirst, we consider 2-dimensional landscape input data.
Total number of the input data N is 1500 and all the input
data are sorted at random.
Both the conventional SOM and FN-SOM has nm =100 neurons (10 × 10). Growing Grid and FN-GG starts
learning with 2 × 2 neurons, and new rows and columns
are inserted as long as the number of neurons is less than
nmmax = 100. We repeat the learning 21 times for all
input data. The parameters of the learning are chosen as
follows; α0 = 0.5, σ0 = 0.9, α1 = 0.006, λg = 30, λf =100, λ = 15.
Respective learning results of four algorithms are shownin Fig. 1, and Fig. 2 shows its U-matrix [4] which represent the learned maps in output space. Each gray value
corresponds to the distance between the neurons. We consider the conventional SOM and FN-SOM which have predefined structure. The map of SOM is not matching the
network topology and has a lot of inactive neurons between
clusters as Fig. 1(a). Therefore, Fig. 2(a) can not reflect
the distribution state of the input data correctly. The resultof FN-SOM has few inactive neurons as Fig. 1(b) by effects of the false-neighbor degree, however, it is a distorted
map for the input data as the conventional SOM. On theother hand, the result of Growing Grid is able to automatically choose an appropriate row/column ratio during the
growth process shown in Fig. 1(c). However, it is hard tounderstand boundaries between clusters from Fig. 2(c) because there are a lot of inactive neurons in this result. The
result of FN-GG (see Fig. 1(d)) can obtain the statisticalfeatures of the input data and fits the given data. Consequently, we can understand the structure of the input datafrom Fig. 2(d).
Furthermore, in order to evaluate the learning performance of FN-GG in comparison with other three algorithms, we use the following three measurements.
Quantization Error Qe: This measures the average distance between each input vector and its winner [2];1 ∑kxj − w̄j k,
N j=1
N

Qe =

(14)

where w̄j is the weight vector of the corresponding winnerof the input vector xj . Therefore, the small value Qe is
more desirable.
Topographic Error Te: This describes how well the SOM
preserves the topology of the studied data set [7];1 ∑u(xj ),
N j=1
N

Te =

(15)

where N is the total number of input data, u(xj ) is 1 if thewinner and 2nd winner of xj are NOT 1-neighbors eachother, otherwise u(xj ) is 0. The small value T e is moredesirable. Unlike the quantization error, it considers the
structure of the map. For a strangely twisted map, the topographic error is big even if the quantization error is small.
Neuron Utilization U: This measures the percentage of- 76 -

1

1

1

1

0.8

0.8

0.8

0.8

0.6

0.6

0.6

0.6

0.4

0.4

0.4

0.4

0.2

0.2

0.2

0.2

0
1

0
1

0
1

0.5
0

0

0.2

0.4

0.6

0.8

1
0.5
0

(a)

0

0.2

0.4

0.8

0.6

0
1

1
0.5
0

(b)

0

0.2

0.4

0.6

0.8

1
0.5
0

(c)

0

0.2

0.4

0.6

0.8

1

(d)

Figure 3: Learning results for Langford data. (a) Conventional SOM. (b) FN-SOM. (c) Growing Grid. (d) FN-GG. Map
size of (c) and (d) after learning are 8 × 13.

Table 1: Quantization error Qe, Topographic error T e and
Neuron utilization U for 2-dimensional data.

Qe
Te
U

SOM

Growing Grid

FN-SOM

FN-GG

0.01770.16530.78000.01880.06470.74070.01580.19870.92000.01580.17870.9907

Qe
Te
U

neurons that are the winner of one or more input vector
in the map [6];
nm
1 ∑
U=
ui ,
nm i=1

Table 2: Quantization error Qe, Topographic error T e and
Neuron utilization U for Langford data.

(16)

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 and larger value of U means fewer inactive neurons.
Table 1 shows the calculated three measurements. Qe
and U of FN-GG are the best values. T e of Growing Grid isthe smallest, but we can confirm that FN-GG has improved
from FN-SOM.

SOM

Growing Grid

FN-SOM

FN-GG

0.05230.227
0.91000.0581
0.157
0.93270.05070.298
0.96000.04950.142
0.9711

4. Conclusions
This study has proposed the Growing Grid with FalseNeighbor degree (FN-GG). This method applied the falseneighbor degree to the Growing Grid network. We have applied FN-GG to clustering and feature extraction and haveconfirmed its efficiency.
References[1] J. Vesanto and E. Alhoniemi, “Clustering of the SelfOrganizing 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 withconstant neighborhood range and adaptation strength,” Neural Processing Letters, vol. 2, no. 5, pp. 9–13, 1995.
[4] A. Ultsch, “Clustering with SOM: U*C”, Proc. Workshop on
Self-Organizing Maps, pp. 75–82, 2005.

3.2. Application to Feature Extraction
Next, we apply FN-GG to the feature extraction for thedata generated by Langford equation [8]. The data is onto
2-torus and has the cavity. The total number of data N is
1000.
The learning results are shown in Fig. 3. We can confirm
that FN-GG can self-organize up to the edge of the input
data in all the methods. Furthermore, the calculated measurements are shown in Table 2. For all measurements, FNGG obtains the best values. These results mean that in thelearned map of FN-GG, there are few errors between the
input data and the neurons as FN-SOM, and FN-GG selforganizes most effectively with maintenance of top quality
topology.

[5] H. Matsushita and Y. Nishio, “Self-Organizing Map withFalse-Neighbor Degree between Neurons for Effective
Self-Organization,” IEICE Transactions on Fundamentals,
vol. E91-A, no. 6, pp. 1463–1469, Jun. 2008.
[6] Y. Cheung and L. Law, “Rival-Model Penalized SelfOrganizing Map,” IEEE Trans. Neural Networks, vol. 18,
no. 1, pp. 289–295, 2007.
[7] K. Kiviluoto, “Topology Preservation in Self-Organizing
Maps”, Proc. of International Conference on Neural Networks, pp. 294–299, 1996.
[8] W. F. Langford, “Numerical Studies of torus bifurcations,”
International Series of Numerical Mathematics, vol.70,
pp.285-295, 1984.

- 77 -