An Improved Probabilistic Ant based Clustering for Distributed Databases

1 Introduction

Swarm systems have recently become a source of inspiration for the design of various clustering algorithms in [Lumer and Faieta, 1994; Handl et al., 2003a; Handl et al., 2003b; Handl et al., 2005]. Ant based clustering and sorting was first introduced by [Bonabeau et al, 1999] to explain different types of naturally occurring emergent phenomena. It is an instance of the broad category of ant algorithms [Dorigo et al, 1999; Dorigo et al., 2000]; that is, algorithms that model 'some behavior' observed in real ants. In the case of ant-based clustering and sorting, two related types of natural ant behavior are modeled. While the traditional ant based algorithms have described clustering data in a single site, we focus on the clustering mechanisms for data in distributed sites [Johnson and Kargupta, 1999]. For example, we may have a number of banks belonging to a multinational banking chain, and each bank maintains a database describing its members. Then we may cluster the databases to learn new high-level concepts that characterize groups of banks. Rather than restricting learning to specific databases, with increasingly more databases becoming available on the Internet, we can globalize knowledge discovery and learn general patterns by this approach [Forman and Zhang, 2000].

The use of ant based clustering for distributed databases was explored in [Chandrasekar et al, 2006]. An algorithm called probabilistic ant based clustering for distributed databases (PACE) was proposed based on user-interaction or queries from the distributed database. The main advantage is that highly probable or most likely keywords from the query can be further analyzed instead of concentrating on the entire set of data available. It utilizes a commonly heard concept of hit ratio, which it calculates for the user query. Depending on this, a number of zones are formed throughout the database with priorities assigned to them. The sizes of these zones and their logical placement in the database are discussed in that paper. A colony building algorithm of ants is utilized for formation of the clusters with an extensive odor analysis model which determines the number and type of agents or ants surrounding a data item. The results obtained from PACE showed highly efficient retrieval from the final clusters formed. In spite of this there are many shortcomings with PACE. The convergence time for the algorithm is not shown to be quick. This is necessary because with increasing sizes of the database, though not shown, the entire process may take a correspondingly large time. Many parameters were not functions of the sizes of the data set to improve the convergence time. Also no further information could be gathered from the final solution obtained other than which points lay in what clusters according to the user queries. Rest of the paper is organized as follows; Section 2 describes the main motivations for our work, Section 3 gives an overview of PACE, Section 4 gives the proposed improvements, Section 5 some Experimental Results while Section 6 concludes our work.

2 MainMotivations for Our Work

Our work has been inspired by the rules specified in [Johnson and Kargupta, 1999]. The time duration of the algorithm should be less than or equal to that of clustering from a single site considering all the data to be present in a single site . To wait for each and every zone to complete its intra-zone clustering and then to perform inter-zone clustering would entail a substantial increase in time. To reduce this considerably, we propose the parallelization of the clustering algorithm so that inter-zone clustering can take place as and when zones become free after intra-zone clustering. There should also be a metric of dissimilarity between points and clusters obtained in the final solution. By the introduction of weights in our algorithm, the final heaps formed by the ants could be in a weighted order. A reasonably informative metric of dissimilarity could be a range of weights wmin and wmax between any two points which is more suitable for clusters formed depending on the user queries to the distributed database rather than calculating the minimum and maximum possible distances between any two points in the final tree. Data gathered from different sites should also not be transmitted to a single site for processing. To circumvent this, building of a global model from a number of local models was suggested in [Johnson and Kargupta, 1999]. Instead of this, the presence of well-defined zones and with parallelization of clustering reduces the transmission costs involved rather than transmitting data to a single site.

For our proposed improvements to PACE, data items in a zone-even after inter-zone clustering has taken place-are marked in a scale either individually or as a group with a weight, in ACO terms-a distinct odor, to denote their relevance to the user queries to the distributed database. If the odor associated with that group is strong then their associated weights are also correspondingly large and hence it makes sense to perform clustering in that region of data items first. This partially satisfies the criterion of a fast convergence time and this along with the idea the notion of parallelization of clustering between the zones provides a better performance than PACE as we show in our results. Another important improvement is the introduction of familial pheromone trails. A family of ants follows its own distinctive trails unless in some species, for example, a trait of trying to impersonate other species exists. This holds true even for a distinctive odor possessed by each and every species [Bonabeau et al, 1999] which formed the basis of identifying the number and type of agents surrounding a data item in PACE. We utilize this concept to enable the formation of clear and defined clusters by allowing each family or species of ants to follow their own familial trails. As we show later, this proves to be effective for different densities of data items. For the re-ordering and agglomeration each time after intra-zone and inter-zone clustering has been performed, it makes sense to re-order them based on those weights so that the quantities wmin and wmax can be calculated easily for effective representation to the user.

3 Overview of PACE Algorithm

From Chandrasekar [2006] it can be seen that the query from the user is disintegrated into atomic keywords each of which can be identified uniquely from the databases at various sites. The number of occurrences of each keyword in the sites is computed using a hit ratio.

The variable K represents the key words and the limit of the summation is 'n' which is equal to the number of keywords. Using this hit ratio each of the distributed sites is assigned a probability value,

The data sites are then ordered in descending order of their probabilities. Each data site is then divided into numerous bounded regions called zones. The agents (ants) are distributed across various zones. Clustering at each stage is achieved by agglomeration and sorting, which is performed in an iterative manner.

An ant in real situation identifies other group of ants of their same colony using a distinctive odor possessed by them that is unique to each colony [Bonabeau et al, 1999; Dorigo et al, 1999; Dorigo et al., 2000].This behavior of ants is exploited in PACE to identify and form a group of ants that carry related data. Again the ants in a real situation move freely in search of food sources. Whenever they find a food source, they cluster around it from Chandrasekar [2006]. Similar behavior is incorporated in PACE. Since the ants are free to move within their zones, they tend to move in search of data objects (Food). In doing so, ants tend to cluster around various data objects. The cluster of ants around groups of data objects hence forms a Family of Agents (FoA). In this way group of ants clustering around various data objects within different parts of a zone form numerous FoA. Thus the ants within a FoA begin to build their colony using the data that they have collected. This is called as an Ant Odor Identification Model (AOIM) which is extended in our work.

Once the FoA is formed, the ants begin to carry data items specific to their family (colony) according to the Picking (Pp) and Dropping (Pd) probabilities [Lumer and Faieta, 1994; Handl et al., 2003b] which depend on the environment surrounding the ants. In PACE, heaps formed are sorted so that the data items closer to the keywords in terms of relevance are placed so that they can be easily retrieved. Every FoA within the zones form their own colony and repeat the procedure. This is called as an Ant Colony Building Algorithm (ACB). The colonies that are built form the primary clusters. The final step would be to perform agglomeration. PACE uses complete-link type of agglomeration. This method assumes that all data items in the cluster are very similar to each other. This is possible because of the sequence of execution from intra-zone to inter-zone agglomeration.

These clusters are agglomerated through three different stages before the final cluster is formed. First is the IntraZone Agglomeration, where the primary clusters within the zone are agglomerated and then reordered by sorting. At the end of this stage a single cluster is obtained. Next is the Inter-Zone Agglomeration. In this stage the clusters from each zone are agglomerated to form a single cluster for the entire data site. In this way many clusters are obtained each data site. Again sorting of the cluster is performed to retain the data items with maximum relevance to the keywords in a way which can be easily retrieved. The final stage involves agglomerating the clusters from the distributed data sites to form a single final cluster. This cluster again is sorted and contains the best results corresponding to the user query.

4 Proposed Improvements

4.1 Introduction of weights

Depending on the hit ratio, individual or groups of data items are marked on a scale denoting their relevance to the query, called as dw or weights. dw denotes the odor associated with an item or a group of items surrounding it. If the odor is strong, then the associated weights are strong and hence it makes sense to perform clustering there first. There is an inherent relationship between the hit ratio and dw denoted by the following equation which holds true for both individual or groups of data items,

Where R is the radius of a zone and H(rm) is the hit ratio for the overall database. We further analyze the memory costs of allocating weights for individual or groups of data items. For individual data items, the memory costs may grow linearly with corresponding increase in data items. As an alternative, groups of data items which either partially or completely satisfies the queries can be marked with an odorin this case a collective weight or a collective odor-to eliminate the need for maintaining separate weights for the data items. This could be the case when the density of data items in a region on the toroidal grid is not too high. Traditionally ant based clustering algorithms have employed some kind of a 'look-ahead' memory [Handl et al., 2003b; Handl et al., 2003a] which is used to bias the search of the ants towards recently visited regions with a strong neighborhood function. From PACE, the neighborhood functions[Lumer and Faieta, 1994] can be obtained as:

Case 1:

Case3:

Case 4:

0, Otherwise

The power of .notdef is derived experimentally. We modify the neighborhood function of PACE and other ant based clustering algorithms as,

We include dw in the neighborhood function as a measure of the weight associated with a particular region. This can be modified to include dw for either individual or groups of data-items depending on the density of the region as,

Whenever n is the number of data items. By doing either or all of the above, the requirements of fast convergence are satisfied as the clusters are formed in the decreasing order of the regions with weights. This being so because ants get attracted to a stronger odor more easily than a weak one. So clusters tend to be formed first in those regions with a strong odor and then the remaining thus forming heaps which are more relevant to the user queries; the latter themselves being a standard set of queries. For Inter-Zone clustering, an average weight is associated with the clusters and the same procedure is repeated as above.

4.2 Familial Pheromone Trails

A Family of Ants which follows their own pheromone trails form clearly defined clusters. Instead of modifying the Ppick and Pdrop functions, data items picked according to dw are dropped around regions satisfying both FoA and dw in some measure. We build upon the concepts of PACE and in addition to defining a FoA as a family which is formed around groups of items, we define each FoA as to having its unique pheromone trails. As we shall show later, the effect of this is control over the definitions of-or demarcations between-the clusters formed. If more priority is given to dw then ants may pick up and drop items near highly odoriferous regions leading to overlapping or fused clusters. Alternatively if more priority is given to an Ant's FoA then data items may be grouped together which are totally unrelated to each other in certain cases or to the user queries in general. The relationship between FoA and dw is as follows,

The main advantage of choosing a proper balance between FoA and dw is for choosing clearly defined and compact clusters. By allowing for different groups of ants each part of their own FoA, considerable spreading of data in the grid takes place. Each group of ants lies separately in the grid without any overlapping of groups. To dampen the effects of outliers, which are points of non-agglomerative behavior, we follow a two- stage strategy.

In the first stage, during the ant colony building algorithm, ants tend to cluster around their own familiessurrounding groups of data items-hence isolated data items are those not having a strong odor and tend to appear at the bottom of the heaps formed by the ants. By this, an iterative agglomeration and re-ordering renders these data items in a way that they do not appear earlier to the users than more relevant data items. This re-ordering takes place more frequently after a number of clusters which have been merged together reduces the clusters to below a certain threshold, typically 1/3 of the original number. In the second stage during the final clustering steps when the granularity [Jain and Dubes, 1988;Jain et al, 1999] is very high, again the reordering is performed so that the irrelevant data items and their clusters, generally very small, are below the other clusters.

4.3 Relationship of Radius of Perception with Zone Radius and dw

The radius of perception is given by (.notdef-1)/2 [Lumer and Faieta, 1994] for the general neighborhood function. For our algorithm it depends on the Zone Radius and dw as follows,

Where Rp is the radius of perception and R the zone radius of that zone where the agent is currently placed. Increasing the radius of perception provides a better range for the agents to choose from but increases costs. To prevent this, we propose to initially allocate the Radius of Perception depending on the Zone Radius, increase it 'locally' for each ant depending on its environment and the values of dw. Thus it is kept as a parameter of the dataset as required by [Johnson and Kargupta, 1999]. There is no real need to modify the neighborhood and threshold functions, Ppick and Pdrop . Instead of the former, spatial separation between the clusters is maintained throughout by the introduction of weights and the familial pheromone trails. Instead of the latter, done to speed up the clustering process, biasing the movements of ants towards their own families and according to the distribution of weights provides a faster convergence time (See Section 4.1).

4.4 Weighted Agglomeration and Parallel Clustering

As mentioned earlier, the final heaps formed are arranged in a weighted order. For deriving information other than which points lie in what clusters, we use two values wmin and wmax as measures of dissimilarity between any two points in the heap. They are as follows,

wmin is a measure of the minimum difference in weights between any two points. Since the values are absolute and defined for every leaf node of the final heap, there is no need of explicitly calculating it every time like in [Johnson and Kargupta, 1999] where the minimum and maximum distances between any two points in a dendogram were calculated frequently from the final solution. Similarly wmax is a measure of the maximum difference in weights between any points and the same principles as wmin apply to it also. To save on processing time and to speed up the clustering, we have proposed the parallelization of the agglomeration process. Intra-zone agglomeration takes place simultaneously in the various sites starting from zones of higher priority as in PACE. Inter-zone agglomeration takes place as and when any zone finishes its own intra-zone process. Thus zones in these sites need not wait until all other zones in the distributed database have finished-thus speeding up the agglomeration process.

5 Experimental Results

In this section comparative results of the performance of our improved PACE algorithm (denoted as I-PACE) are reported against established clustering algorithms like the kmeans algorithm, the hierarchical agglomerative algorithm and PACE.

5.1 Experimental Setup

The evaluation methodology given here was inspired by [Handl et al., 2003a; Handl et al., 2003b].The first algorithm we compare against is the well-known k-means algorithm. Random initialization is used is used in our experiments, and the best result out of a few runs is selected. If empty clusters arise during the clustering process using the k-means algorithm [Bishop, 1995], these are reinitialized using a randomly selected data item. As a second method, an agglomerative hierarchical clustering algorithm [Day and Edelsbrunner, 1984] based on the linkage metric average link [Jain et al, 1999] is used. The data items are distributed in a number of toroidal grids with the assumption that the ants are able to move from one grid to another and that the edges are spherical to enable movements from all sides.

Synthetic Data

The Square1 dataset is the most popularly used type of data set used for evaluation purposes in ant based clustering. It is two-dimensional and consists of four clusters arranged as a square. To conform to distributed datasets, the Square1 dataset is spread uniformly among the various sites. They are generated by the Normal Distributions with corresponding points as (N(-5,2),N(-5,2)),(N(5,2),N(5,2)), (N(- 5,2),N(5,2)) and (N(5,2),N(-5,2)) and are each of size 200.

Real Data

The real data collections used were the Iris data, the Wine Recognition data and the Yeast data with the description of each collection in [Blake and Merz, 1998]. Each dataset is permuted and randomly distributed in the sites. Different evaluation functions proposed in [Handl et al., 2003a] are adapted for comparing the clustering results obtained from applying the three clustering algorithms on the test sets. The F-Measure [Rijsbergen, 1979], Dunn Index [Halkidi et al., 2000] and Rand Index [Rijsbergen, 1979] are the three measures and their respective definitions also mentioned in [Handl et al., 2003b] and each should be maximized.

5.2 Experimental Results

The results of the evaluation functions on both synthetic as well as the real data are shown in Table 1. It shows the mean and standard deviation (obtained over 60 runs) for each of the three measures. The above results demonstrate that in spite of clear cluster structures not being present in certain data, I-PACE is quite easily able to identify the correct number of clusters. With certain exceptions I-PACE performs well for all the three evaluation functions. Though k-means shows better performance for the synthetic data, it is clearly outmatched with respect to the real data by IPACE. Errors in each case for the I-PACE algorithm are also considerably smaller than the remaining three as shown here in Tables 2, 3 and 4 averaged over 80 runs.

TABLE IV

6 Conclusion

In this paper we have proposed an improved version of the PACE algorithm for ant-based clustering in distributed databases. The main features of this algorithm are the introduction of weights and familial pheromone trails as part of an Ant Odor Identification Model. The aims are manifold-to reduce the convergence time and thereby improve the runtime of the solution, to improve the quality of clustering by forming compact and clearly defined clusters, to separate out outliers from the final solution, to provide a metric which easily determines the dissimilarity between any two points in the final cluster, to parallelize the algorithm for again reducing the processing time. These aims are reasonably achieved by our algorithm as ably proven by our experimental results. Further investigation could be carried out with a large number of data-sets as an extended version of our algorithm.