| Authors: |
Elth Ogston
and Benno J. Overeinder
and Maarten van Steen
and Frances M. T. Brazier
|
| URL: |
http://www.cs.vu.nl/~elth/papers/decentralized_clustering.pdf |
| Tags: |
Agents
Clustering
DDM
|
| Abstract: |
This paper examines a method of clustering within a fully decentralized
multi-agent system. Our goal is to group agents with similar objectives
or data, as is done in traditional clustering. However, we add the
additional constraint that agents must remain in place on a network,
instead of first being collected into a centralized database. To
do this we connect agents in a random network and have them search
in a peer-to-peer fashion for other similar agents. We thus aim to
tackle the basic clustering problem on an Internet scale and create
a method by which agents themselves can be grouped, forming coalitions.
In order to investigate the feasibility of a decentralized approach,
this paper presents a number of simulation experiments involving
agents representing two-dimensional points. A comparison between
our method's clustering ability and that of the k-means clustering
algorithm is presented. Generated data sets containing 2,500 to 160,000
points (agents) grouped in 25 to 1,600 clusters are examined. Results
show that our decentralized agent method produces a better clustering
than the centralized k-means algorithm, quickly placing 95% to 99%
of points correctly. The the time required to find a clustering depends
on the quality of solution required; a fairly good solution is quickly
converged on, and then slowly improved. Overall, our experiments
indicate that the time to find a particular quality of solution increases
less than linearly with the number of agents. |
@inproceedings{Ogston2003,
title = {A method for decentralized clustering in large multi-agent systems},
author = {Elth Ogston and Benno J. Overeinder and Maarten van Steen and Frances M. T. Brazier},
booktitle = {International Joint Conference on Autonomous Agents and Multiagent
Systems},
pages = {789--796},
url = {http://www.cs.vu.nl/~elth/papers/decentralized_clustering.pdf},
year = {2003},
abstract = {This paper examines a method of clustering within a fully decentralized
multi-agent system. Our goal is to group agents with similar objectives
or data, as is done in traditional clustering. However, we add the
additional constraint that agents must remain in place on a network,
instead of first being collected into a centralized database. To
do this we connect agents in a random network and have them search
in a peer-to-peer fashion for other similar agents. We thus aim to
tackle the basic clustering problem on an Internet scale and create
a method by which agents themselves can be grouped, forming coalitions.
In order to investigate the feasibility of a decentralized approach,
this paper presents a number of simulation experiments involving
agents representing two-dimensional points. A comparison between
our method's clustering ability and that of the k-means clustering
algorithm is presented. Generated data sets containing 2,500 to 160,000
points (agents) grouped in 25 to 1,600 clusters are examined. Results
show that our decentralized agent method produces a better clustering
than the centralized k-means algorithm, quickly placing 95% to 99%
of points correctly. The the time required to find a clustering depends
on the quality of solution required; a fairly good solution is quickly
converged on, and then slowly improved. Overall, our experiments
indicate that the time to find a particular quality of solution increases
less than linearly with the number of agents.},
keywords = {Agents Clustering DDM }
}
::