Fragmentary Synchronization in Chaotic Neural

E. Corchado et al. (Eds.): HAIS 2009, LNAI 5572, pp. 319–326, 2009.

? Springer-Verlag Berlin Heidelberg 2009

Fragmentary Synchronization in Chaotic Neural

Network and Data Mining

Elena N. Benderskaya 1 and Sofya V. Zhukova 2

1 St. Petersburg State Polytechnical University, Faculty of Computer Science,

Russia, 194021, St. Petersburg, Politechnicheskaya 21 bender@sp.ru 2 St. Petersburg State University, Graduate School of Management,

Russia, 199004, St. Petersburg Volkhovsky Per. 3 sophya.zhukova@https://www.sodocs.net/doc/4311809769.html,

Abstract. This paper proposes an improved model of chaotic neural network used to cluster high-dimensional datasets with cross sections in the feature space. A thorough study was designed to elucidate the possible behavior of hundreds interacting chaotic oscillators. New synchronization type - fragmen-tary synchronization within cluster elements dynamics was found. The paper describes a method for detecting fragmentary synchronization and it’s advan-tages when applied to data mining problem.

Keywords: clustering, cluster analysis, chaotic neural network, chaotic map lattices, fragmentary synchronization.

1 Introduction

General formalization of clustering problem consists in finding out the most rational clusterization K of input data samples X . The division is provided due to some simi-larity measure between various combinations of the n elements in the dataset (},...,,{21n x x x X =},...,,{,21ip i i i x x x x =). Every element is described by p features (dimension of input space) and can belong simultaneously only to one of m clusters.

The similarity measure depends greatly on mutual disposition of elements in the input dataset. If we have no a priori information about the type of groups (ellipsoidal, ball-shaped, compact, scattered due to some distribution or just chaotically, and this list is endless) then the probability of erroneous measure choice is very high [1, 2]. This is the main reason clusterization to be related to non-formalizable problems. In terms of neural networks it is solved by means of unsupervised learning or learning without a teacher [3], because the system is to learn by itself to extract the solution from input dataset without external aid.

Each clustering technique works under the assumption that input data can be suc-cessfully clustered using the concrete similarity measure or their combination.

It can lead to gross mistakes and as a result bring to erroneous solution if this supposition does not fulfill. Moreover it happens to be hard to find express recom-mendations which method is the most appropriate to cluster a concrete input dataset

320 E.N. Benderskaya and S.V. Zhukova

(N-dimensional image) without calling an expert. This in its turn leads us to conclu-sion that any clustering method allows to obtain only partial solution.

Information about the amount of groups and their topology is frequently unavail-able. In this case application of classical algebraic and probabilistic clustering meth-ods does not always provide unique and correct solution. The main idea of these methods is to determine typical representatives of clusters (centers of clusters) in terms of averaging-out [4].

Distributed processing in its pure form is capable to reduce computing complexity but not to improve solution quality. This remark fully agrees with recent applications of self organizing maps (Kohonen’s network) and ART neural networks, which pro-vide satisfactory solutions only when clusters separating curves are easily determined in features space or the concept of averaging-out is valid. These artificial neural net-work models [3] in fact are parallel interpretations of c-means method [1, 2] and thus they possess its drawbacks. Underlying cause lies in the insufficient complexity of the systems. These networks are static. But not only the structure of network (number of elements and links between them) but also its dynamics must meet the requirements of problems’ complexity level.

Another promising direction is designing dynamic neural networks. As if in sup-port of the idea numerous investigations in neurophysiology sphere reveal that bio-logical neural networks appear to be nonlinear dynamic systems with chaotic nature of electrochemical signals. Computer science development predetermined great abili-ties of computer modeling. It became possible to study complex nonlinear dynamics. Great evidence for rich behavior of artificial chaotic systems was accumulated and thus chaos theory came into being [5-7]. Dynamics exponential unpredictability of chaotic systems, their extreme instability generates variety of system’s possible states that can help us to describe all the multiformity of our planet. It is assumed to be very advantageous to obtain clustering problem solution using effects produced by chaotic systems interaction. In this paper we try to make next step in the development of universal clustering technique.

2 Oscillatory Clusters and Input Dataset

Emergence of clustering effects turns out to be universal concept in animate nature and in abiocoen. Self-organization occurs in various phenomena such as structures creation, cooperative behavior, etc. Clusters built up from atoms, molecules, neurons are examined in many scientific fields.

Primary results on modeling high dimensional chaotic map lattices were published by K. Kaneko [8]. These works showed up the fact that globally coupled chaotic map lattices exhibit formation of ensembles synchronously oscillating elements. These ensembles were called clusters serving as system’s attractors. If there appear to be several clusters then the system is characterized by multistability, when several attrac-tors coexist in the phase space at the same parameters values.

Kaneko’s model [8, 9] encompasses a number of identical logistic maps globally coupled with the same strength ε.

Fragmentary Synchronization in Chaotic Neural Network and Data Mining 321 In terms of neural networks that means that all synaptic weights ij w , that join ele-ment i and element j are equal ε=ij w . Variables change their state in the range [-1, 1] due to special transfer function )(1))((2t y t y f λ?=. The time evolution of the system is given by

,,1,,))(())(()1()1(1N j i t y f N t y f t y N i j j j i i =+?=+∑≠=ε

ε (1)

where N – number of variables. In [8] was shown that globally coupled chaotic sys-tem may occurs several phases: coherent (one cluster), ordered (several big clusters), partially ordered, turbulent (number of clusters coincide with number of variables). However, this abstract clustering phenomenon does not advance us in solving cluster-ing problem.

Leonardo Angelini and his colleagues proposed to apply oscillatory clustering phe-nomenon to image clustering [10, 12]. The information about input dataset was given to logistic map network by means of inhomogeneous weights assignment

,,1,,||,2exp }{2N j i x x d a d w W j i ij

ij ij =?=?????????== (2)

where N – number of elements, ij w - strength of link between elements i and j , ij d - Euclidean distance between neurons i and j , а – local scale, depending on k -nearest neighbors. The value of a is fixed as the average distance of k -nearest neighbor pairs of points in the whole system.

Each neuron is responsible for one object in the dataset, but the image itself is not given to inputs, because CNN does not have classical inputs – it is recurrent neural network with one layer of N neurons. Instead, the image (input dataset) predetermines the strength of neurons interactions (similar to Hopfield’s network [3]). Evolution of

each neuron is governed by

,...1 ,))((1)1(T t t y f w C t y N j i i ij i i ==+∑≠ (3)

)(21))((2t y t y f ?= (4) where N j i w C j

i ij

i ,1,,==∑≠, T – time interval, N – number of elements. Neurons state is dependent on the state of all other elements. After transitionary period start to appear synchronous clusters. To reveal them neurons outputs are rounded up to 0 and 1 values and Shannon information is calculated [10, 12] to detect mutual similarity of neurons dynamics.

322 E.N. Benderskaya and S.V. Zhukova

In the end neurons are joined in clusters several times, because a priori it is un-known the veritable threshold θ that corresponds to real clustering. The value of θi controls the resolution at which the data is clustered. Thresholds are chosen with some step in the range of minimum and maximum values in the information matrix. Neural network in which weight coefficients are calculated in compliance with (3) and evolution is given by (4) was called chaotic neural network (CNN). It’s name stresses the chaotic functioning dynamics of the system, guaranteed by transfer function (5).

3 CNN Modeling

For a start simple 2D clustering problem illustrated in Fig.1 was solved in terms of Angelini’s model. Since we know the answer for a test clustering problem then it is correct to order inputs by their belongings to clusters. It is important to stress that this operation will not change CNN functioning, because initial conditions are set in a random way in the range [-1, 1] as before. This will help us to watch CNN dynamics. 102030405010

20

30

40

(b)102030405010203040Fig. 1. Clustering problems: (a) - simple clustering problem (134 objects, each described by two coordinates (p =2), four clusters are compact and stand apart from each others, clusters comprise correspondingly 49, 36, 30, 19 objects-points); (b) – more complex clustering prob-lem (210 objects arranged with lower density in four clusters close to each other in future space, population is correspondingly 85, 50, 40, 35 points).

In accordance with Angelini’s algorithm we received dendrogram on Fig. 2a . Here we can see that decision-making about proper solution can be provided without an expert knowledge, because overwhelming majority of variants (82%) coincide with each other. Fig. 2a shows that when threshold θ ∈ [0.12; 0.69] we obtain the only one clusterization, displayed in Fig. 2b that fully agrees with our expectations. The analy-sis of analogous experimental results indicated that CNN is good enough in solving simple clustering problems as well as all other classical methods.

Next, more complex clustering problem in Fig 1b was solved by means of CNN. Clusterization results showed in Fig. 3 seem to be rather disappointing – only 23% of variants correspond to the expected answer. This makes it impossible to choose the proper clusterization without opinion of an expert, because it is impossible to “guess” automatically that more natural solution can be obtained for θ ∈ [0.48; 0.63].

Fragmentary Synchronization in Chaotic Neural Network and Data Mining

323

Fig. 2. Clustering results: (a) – dendrogram of solution variants; (b) – the most stable (repeat-ing) clusterization that coincides with real answer and takes 82% of all other variants

Fig. 3. Dendrogram of clusterizations for problem on Fig. 1b – only 23% of variants coincide with the expected one

10020030040050060070020

40

60

80

100

120

-0.500.5Fig. 4. Chaotic neural network dynamics (statistics of outputs dynamics) while clustering image in Fig. 1a . Color bar to the left shows correspondence between output’s absolute value and color in gray scale palette. CNN parameters: Tp = 1000, Tn = 1000, k = 20, random initial conditions.

324 E.N. Benderskaya and S.V. Zhukova

4 New Synchronization Type – Fragmentary Synchronization

To find the reason of the failure we have to analyze in detail the CNN dynamics. When clustering a simple image (Fig. 1a) the CNN outputs evolve synchronously within clusters.

Complete synchronization [8, 13, 14] within clusters takes place in case of simple images, look at Fig. 4. Due to complete agreement within a cluster oscillations and quite different fluctuations of three other clusters the choice of stable clustering result without an expert is not a problem.

CNN clustering results depend on mutual synchronization effects rather than on the processing method used to treat neurons dynamics. To widen the scope of concerned clustering method extensive analysis of possible CNN synchronous regimes has been undertaken.

4.1 Fragmentary Synchronization

More complex image predetermines more intricate CNN dynamics. As a result amount of coincident variants is not enough. To reveal the reason let us again look at outputs dynamics visualization. CNN may produce not only well-known synchroniza-tion [13, 14] types as: complete synchronization, phase synchronization, generalized synchronization, lag synchronization, intermittent lag synchronization, but also such synchronization when instant output values in one cluster do not coincide neither by amplitude nor by phase and there is even no fixed synchronization lag. In spite of everything joint mutual synchronization exists within each cluster. This synchroniza-tion is characterized by individual oscillation cluster melodies, by some unique “mu-sic fragments” corresponding to each cluster. From this follows the name we give to this synchronization type - fragmentary synchronization. For the second problem (look at Fig 1b) fragmentary synchronization is visualized in Fig. 5.

50

100

150

200

100200300400500600700

Fig. 5. Chaotic neural network dynamics while clustering image in Fig. 1b. Fragmentary syn-chronization takes place – each cluster is characterized by its own “fragment of a melody”. Neurons within one cluster can evolve rather asynchronously.

4.2 Proposed Method to Detect Fragmentary Synchronization

Thorough investigation indicated that unsuccessful results were induced by inefficient method of statistics processing. The use of Shannon’s entropy coarse loss of informa-tion about transfers consequences. Because in this case real values are replaced by Boolean ones. From results analysis we have inferred the following.

Fragmentary Synchronization in Chaotic Neural Network and Data Mining 325

(a)Fragmentary synchronization detection is to be based on the comparison of

instant absolute values of outputs but not approximated in this or that way values.

(b)Asynchronous oscillations within one cluster in case of fragmentary synchro-

nization can be nevertheless classified as similar. Let us consider some se-

quences be more alike than the others and easily related to the same group1.

Others may be alike but in a different way and they are joined in group2. To combine group1 and group2 into one we need only one more sequence in the same degree similar to both of groups. In other words joining up not neighboring neurons within one cluster occurs due to similar but not identical

dynamics of neurons that lay between them.

In this paper we propose to produce pair comparison of y i dynamics sequences just as it is done to detect complete synchronization. But besides admissible divergence in instant values of both sequences we introduce bearable percent of moments (counts) where the boundary of admissible divergence may be broken.

Two neurons belong to the same cluster if their dynamics difference is less than εand this condition is broken less than in p percents in the interval [Tp+1, Tn]. In com-pliance with suggested computational procedure were received experimental results displayed in Fig 6. The bar graph illustrates the appearance frequencies of various clusterizations. Number of analyzed variants is 100. They are received under the con-dition that threshold εis changed from 0.05 up to 0.5 with step 0.05, and threshold p is changed from 5% up to 50% with step 5%. To provide a vivid demonstration bar graph represent only variants that appeared more than once. The most frequent clus-terization found by means of new method corresponds to the number of four clusters. So the proposed dynamics treatment has obvious advantage over existing processing method, because there appear an: ability to reveal intricate structure of macroscopic attractor represented by means of fragmentary synchronized chaotic sequences and what is more important to find final clusterization without expert assistance because number of identical answers is large enough.

Wide set of clustering experiments with other images showed that fragmentary synchronization detection method can be also used to reveal phase and complete syn-chronization. Though as it is expected, high solution quality has a considerable cost of great computational complexity.

Fig. 6. Clustering results. The most stable variant of clusterization when we have 4 clusters found by improved CNN automatically without a priori information about number and topology of clusters, and the answer coincide with the expected one for problem on Fig. 1b.

326 E.N. Benderskaya and S.V. Zhukova

5 Conclusion

Increase of system’s dimension and nonlinearity degree produces more complex behav-ior of component parts and the system as a whole and demands complication of analysis techniques. Research results allow to improve clustering quality of chaotic neural net-work. The main advantage of proposed modifications is the opportunity to solve complex clustering problems without expert assistance in the case if input information about ob-jects is not contradictory (when even the expert cannot provide a decision). The syner-gism of obtained solution results from multidisciplinary hybridism (neural networks, self-organization, chaos theory, cybernetics) that fully reflects in CNN structure and discovered fragmentary synchronization type. This is one more evidence for the necessity of complex analysis and synthesis. In the paper we received important qualitative results. Future investigations would be devoted to the estimation of quantitative characteristics of the new algorithm, especially computational complexity. And this is sensible only in case of CNN hardware implementation, because both functioning and output processing stages can be provided on the base of array computation and distributed processing. References

1.Valente de Oliveira, J., Pedrycz, W.: Advances in Fuzzy Clustering and its Applications, p.

454. Wiley, Chichester (2007)

2.Han, J., Kamber, M.: Data Mining. In: Concepts and Techniques. The Morgan Kaufmann

Series in Data Management Systems, p. 800. Morgan Kaufmann, San Francisco (2005)

3.Haykin, S.: Neural Networks. In: A Comprehensive Foundation. Prentice Hall PTR, Upper

Saddle River (1998)

4.Dimitriadou, E., Weingessel, A., Hornik, K.: Voting-Merging: An Ensemble Method for

Clustering. In: Dorffner, G., Bischof, H., Hornik, K. (eds.) ICANN 2001. LNCS, vol. 2130, pp. 217–224. Springer, Heidelberg (2001)

5.Schweitzer, F.: Self-Organization of Complex Structures: From Individual to Collective

Dynamics, p. 620. CRC Press, Boca Raton (1997)

6.Mosekilde, E., Maistrenko, Y., Postnov, D.: Chaotic synchronization. World Scientific Se-

ries on Nonlinear Science. Series A 42, 440 (2002)

7.Haken, H.: Synergetics. In: Introduction and Advanced Topics, Physics and Astronomy

Online Library, p. 758. Springer, Heidelberg (2004)

8.Kaneko, K.: Phenomenology of spatio-temporal chaos. Directions in chaos., pp. 272–353.

World Scientific Publishing Co., Singapore (1987)

9.Kaneko, K.: Chaotic but regular posi-nega switch among coded attractors by cluster-size

variations. Phys. Rev. Lett. N63(14), 219–223 (1989)

10.Angelini, L., Carlo, F., Marangi, C., Pellicoro, M., Nardullia, M., Stramaglia, S.: Cluster-

ing data by inhomogeneous chaotic map lattices. Phys. Rev. Lett. N85, 78–102 (2000) 11.Angelini, L., Carlo, F., Marangi, C., Pellicoro, M., Nardullia, M., Stramaglia, S.: Clustering

by inhomogeneous chaotic maps in landmine detection. Phys. Rev. Lett. 86, 89–132 (2001) 12.Angelini, L.: Antiferromagnetic effects in chaotic map lattices with a conservation law.

Physics Letters A 307(1), 41–49 (2003)

13.Pikovsky, A., Rosenblum, M., Kurths, J.: Synchronization: A Universal Concept in

Nonlinear Sciences. Cambridge University Press, Cambridge (2003)

14.Osipov, G.V., Kurths, J., Zhou, C.: Synchronization in Oscillatory Networks. Springer

Series in Synergetics, p. 370. Springer, Heidelberg (2007)