A multidimensional °ocking algorithm for clustering spatial data

Abstract

|In this paper, we describe the e±cient implementation of M-Sparrow, an adaptive °ocking algorithm based on the biology-inspired paradigm of a °ock of birds. We extended the classical °ock model of Reynolds with two new characteristics: the movement in a multi-dimensional space and di®erent kinds of birds. The birds, in this context, are used to discovery point having some desired characteristics in a multidimensional space. A critical point of the algorithm is the e±cient search of the k-neighbors in a multidimensional space. This search was e±ciently implemented using the ANN libraries.

Ants'colonies, °ocks of birds, termites, swarms of bees

etc. are agent-based insect models that exhibit a collective intelligent behavior (swarm intelligence) [ 2 ] that may be used to de¯ne new distributed clustering algorithms. In these models, the emergent collective behavior is the outcome of a process of self-organization, in which insects are engaged through their repeated actions and interaction with their evolving environment. Intelligent behavior frequently arises through indirect communication between the agents using the principle of stigmergy [ 6 ]. This mechanism is a powerful principle of cooperation in insect societies. According to this principle an agent deposits something in the environment that makes no direct contribution to the task being undertaken but it is used to in°uence the subsequent behavior that is task related. Swarm intelligence (SI) models have many features in common with Evolutionary Algorithms (EA). Like EA, SI models are population-based. The system is initialized with a population of individuals (i.e., potential solutions). These individuals are then manipulated over many iteration steps by mimicking the social behavior of insects or animals, in an e®ort to ¯nd the optima in the problem space. Unlike EAs, SI models do not explicitly use evolutionary operators such as crossover and mutation. A potential solution simply '°ies' through the search space by modifying itself according to its past experience and its relationship with other individuals in the population and the environment.

These algorithms show a high level of robustness to change by allowing the solution to dynamically adapt itself to global changes by letting the agents self-adapt to the associated local changes.

In this paper, we present a prototype using a new algorithm based on the concepts of a °ock of birds that move together in a complex manner with simple local rules, to explore multidimensional spaces for searching interesting objects. The algorithm is an extension of the classical °ock model of Reynolds with two new characteristics: the movement in a multi-dimensional space and di®erent kinds of birds. The birds, in this context, are used to discovery point having some desired characteristics in a multidimensional space. The implementation is based on SWARM [ 7 ], a software package for multi-agent simulation of complex systems, developed at the Santa Fe Institute.

From an e±ciency point of view the most critical point of the algorithm is the e±cient search of the k-neighbors (i.e. the cardinality of the neighborhood) in a multidimensional space. This search was e±ciently implemented using the ANN (Approximate Nearest Neighbor) libraries.

The remainder of this paper is organized as follows. Section 2 describes the adaptive °ocking algorithm, section 3 shows how the approach was applied to multidimensional spaces. Section 4 shows some interesting experimental results about the e±ciency of the algorithm and its e±cacy in ¯nding interesting patterns. Finally section 5 draws some conclusions.

II. The adaptive flocking algorithm

The classical °ocking model, introduced by Reynolds [ 8 ], moves in a two dimensional space and all the birds have the same characteristics. In the next subsections, we describe the two extensions introduced in M-Sparrow, the use of birds having di®erent characteristics (represented by di®erent colors) and the movement in a multidimensional space.

A. Reynolds' original °ock model

The °ocking algorithm was originally proposed by

Reynolds as a method for mimicking the °ocking behavior of birds on a computer both for animation and as a way to study emergent behavior. Flocking is an example of emergent collective behavior: there is no leader, i.e., no global control. Flocking behavior emerges from the local interactions. Each agent has direct access to the geometric description of the whole scene, but reacts only to °ock mates within a certain small radius. The basic °ocking model consists of three simple steering behaviors: separation, cohesion and alignment.

Separation gives an agent the ability to maintain a certain distance from others nearby. This prevents agents from crowding too closely together, allowing them to scan a wider area. Cohesion gives an agent the ability to cohere (approach and form a group) with other nearby agents.

Steering for cohesion can be computed by ¯nding all agents in the local neighborhood and computing the average position of the nearby agents. The steering force is then applied in the direction of that average position. Alignment gives an agent the ability to align with other nearby characters. Steering for alignment can be computed by ¯nding all agents in the local neighborhood and averaging together the 'heading' vectors of the nearby agents.

B. An adaptive colored °ocking algorithm adaptively adjusted as the agents change their color moving to explore data until they reach the goal.

Green and yellow agents compute their movement observing the positions of all other agents that are at most at some ¯xed distance (dist max ) from them and applying the rules of Reynolds' [ 8 ] with the following modi¯cations: ² Alignment and cohesion do not consider yellow agents,

since they move in a not very attractive zone. ² Cohesion is the resultant of the heading towards the average position of the green °ockmates (centroid), of the attraction towards red agents, and of the repulsion by white agents. ² A separation distance is maintained from all the

agents, whatever their color is.

Agents will move towards the computed destination with a speed depending from their color: green agents will move more slowly than yellow agents since they will explore denser zones of clusters. An agent will speed up to leave an empty or uninteresting region whereas it will slow down to investigate an interesting region more carefully. The variable speed introduces an adaptive behavior in the algorithm. In fact, agents adapt their movement and change their behavior (speed) on the basis of their previous experience represented from the red and white agents.

M-SPARROW extends the Reynolds' °ocking algorithm, described in the previous subsection, considering four different kinds of agents, classi¯ed on the basis of some properties of data in their neighborhood. These di®erent kinds are characterized by a di®erent color: red, revealing interesting patterns in the data, green, a medium one, yellow, a low one, and white, indicating a total absence of patterns.

In practise, the °ock follows an exploring behavior in which individual members (agents) to ¯rst explore the environment searching for goals whose positions are not known a priori, and then, after the goals are located, all the °ock members should move towards these goals. Agents search for i=1 : : : MaxIterations the goals in parallel and signal the presence or the lack of foreach agent (yellow, green) signi¯cant patterns into the data to other °ock members, age=age+1; by changing color. The main idea behind our approach is if (age > Max Life) to take advantage of the colored agent in order to explore generate new agent();die(); more accurately the most interesting regions (signaled by endif the red agents) and avoid the ones without clusters (sig- if (not visited (current point)) naled by the white agents). Red and white agents stop property = compute property(current point); moving in order to signal this type of regions to the oth- mycolor= color agent(property); ers, while green and yellow ones °y to ¯nd more dense endif clusters. Indeed, each °ying agent computes its heading by end foreach taking the weighted average of alignment, separation and cohesion (as illustrated in ¯gure 1). The entire °ock then moves towards the agents (attractors) that have discovered interesting regions to help them, avoiding the uninteresting areas that are instead marked as obstacles. The color is assigned to the agents by a function associated with the data analyzed. In practice, the agent computes the property of the explored point and then it chooses the color (and the speed) in accordance to the simple rules showed in table I. end for

So red, reveals a high density of interesting patterns in the data, green, a medium one, yellow, a low one, and Fig. 2. The pseudo-code of M-SPARROW. white, indicates a total absence of patterns. The color is used as a communication mechanism among °ock members During simulations a cage e®ect, was observed; in fact, to indicate them the roadmap to follow. The roadmap is some agents could remain trapped inside regions surforeach agent (yellow, green)

dir= compute dir(); end foreach foreach agent (all) switch (mycolor)f case yellow, green: move(dir, speed(mycolor)); break; case white: stop(); generate new agent(); break; case red: stop(); generate new close agent(); break; g end foreach rounded by red or white agents and would have no way to go out, wasting useful resources for the exploration. So, a limit on their life was imposed to avoid this e®ect; hence, when their age exceeded a determined value (maxLife) they were killed and were regenerated in a new randomly chosen position of the space.

C. Exploring multidimensional spaces

We wanted use our adaptive °ocking algorithm in order to explore multidimensional space for searching point having desired properties. A continuous data point can be represented in a multidimensional Euclidean space, simply normalizing its attributes. Our algorithm can search for any kind of properties. In particular, we describe a useful property for the task of clustering. Given a radius (Eps) and a minimum number (MinPts) of points. A core point is a point with at least MinPts number of points in an Epsneighborhood of the itself. Searching points having these characteristic could be useful for di®erent task (i.e. dbscan [ 3 ] use these points to perform the task of clustering databases). In the experimental section, we will show the evaluation of our algorithm in e®ectively cope with this task.

In the following, we give a more formal description of the extension of the °ocking algorithm to the multidimensional space. Consider a multidimensional space with dimension d. Each bird k can be represented as a point in this space, having coordinates xk1; xk2; : : : ; xkd and having direction µk1; µk2; : : : ; µkd, where µki represent the angle between the new direction of the bird k (computed using the rules of the previous subsection) and the axis i. Each bird moves following the the rules of the previous subsection having speed vk. Then, for each iteration t, the new position of the bird k can be computed as:

ANN (Approximate Nearest Neighbor) [ 1 ] is a library written in C++, which supports data structures and algorithms for both exact and approximate nearest neighbor searching in high dimensional spaces. As showed in ¯gure 4, we integrated ANN libraries using Java Native Interface with M-Sparrow in order to e±ciently compute the neighbors necessary to our algorithm. xki(t + 1) = xki(t) + vk £ cki

(1) these formulas can be computed as a generalization of the three-dimensional case illustrated in ¯gure 3.

From a computational point of view, a critical point of our algorithm is the e±cient search of the k-neighbors in a multidimensional space. Computing exact nearest neighbors can be very expensive when dimension increases.

In two previous papers, we demonstrated the goodness where cki represents the projection along the i axis of our algorithm in discovering clusters with di®erent sizes, of the direction of the boid k. Note that each compo- shapes in noise data [ 5 ] and also with di®erent densities [ 4 ] nents is obtained summing the respective three compo- in a two dimensional space. nents of alignment, separation and cohesion (i.e. cki = Now, we want to show how the algorithm works in a c alignmentki + c separationki + c cohesionki). In a mul- multidimensional space. We have built two dataset, each tidimensional space, we can compute the components as: one constituted by two gaussian distributions with di®erent densities of 1500 points. The ¯rst was three dimensional d¡1 and the latter four dimensional. We run our algorithm usck1 = Y cos(µkj ) ing 200 birds for 600 iterations with k = 50 and radius =

j=1 20. It succeeds in separating almost perfectly the two gausd¡1 (2) sian distributions in both the cases. The three dimensional cki = sin(µki¡1) Y cos(µkj ) i = 2 : : : d case is illustrated in ¯gure 5.

j=i Furthermore, we want to verify the e±ciency of the ANN based implementation and then we run our algorithm comparing execution times of the latter ANN-based version with the previous that used brute force computation for searching the k-neighbors. The results of this comparison for a three dimensional case are reported in ¯gures 6 a and b. Experiments show that the ANN libraries outperforms the brute force approach in all the cases and the di®er

III. Experimental results ence is really considerable when the number of neighbors to search is greater than 50. If we consider datasets with dimension larger than 3, ANN outperforms the brute force approach by at least two order of magnitude, also for small values of k.

IV. Conclusions

We have presented an e±cient implementation of an

adaptive °ocking algorithm that e±ciently search multidimensional spaces. The implementation is based on the ANN libraries performing an e±cient search of the k neighbors. Experiments showed that the algorithm is able to separate clusters in multidimensional spaces and it outperforms the previous brute force approach in terms of execution time.

References

[1] Sunil Arya , David M. Mount , Nathan S. Netanyahu, Ruth Silverman, and Angela Y. Wu. An optimal algorithm for approximate nearest neighbor searching ¯xed dimensions . Journal of ACM , 45 ( 6 ): 891 { 923 , 1998 .

[2] Eric Bonabeau , Marco Dorigo, and Guy Theraulaz . Swarm intelligence: From natural to arti¯cial systems . J. Arti¯cial Societies and Social Simulation , 4 ( 1 ), 2001 .

[3] Martin Ester , Hans-Peter Kriegel , Jorg Sander, and Xiaowei Xu . A density-based algorithm for discovering clusters in large spatial databases with noise . In Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining , pages 226 { 231 , 1996 .

[4] Gianluigi Folino , Agostino Forestiero, and Giandomenico Spezzano . Swarming agents for discovering clusters in spatial data . ispdc, 2003 .

[5] Gianluigi Folino and Giandomenico Spezzano . An adaptive °ocking algorithm for spatial clustering . In PPSN , pages 924 { 933 , 2002 .

[6] P.P. Grass . La Reconstruction du nid et les Coordinations InterIndividuelles chez Beellicositermes Natalensis et Cubitermes sp . La Thorie de la Stigmergie : Essai d'interprtation du Comportement des Termites Constructeurs in Insect . Soc. 6 . Morgan Kaufmann, 1959 .

[7] N. Minar , R. Burkhart , C. Langton , and M. Askenazi . The swarm simulation system, a toolkit for building multi-agent simulations , 1996 .

[8] Craig W. Reynolds . Flocks, herds and schools: A distributed behavioral model . In SIGGRAPH '87: Proceedings of the 14th annual conference on Computer graphics and interactive techniques , pages 25 { 34 , New York, NY, USA, 1987 . ACM Press.