Efficient agent-based cluster ensembles

ABSTRACT

Numerous domains ranging from distributed data acquisition to knowledge reuse need to solve the cluster ensemble problem of combining multiple clusterings into a single unified clustering. Unfortunately current non-agent-based cluster combining methods do not work in a distributed environment, are not robust to corrupted clusterings and require centralized access to all original clusterings. Overcoming these issues will allow cluster ensembles to be used in fundamentally distributed and failure-prone domains such as data acquisition from satellite constellations, in addition to domains demanding confidentiality such as combining clusterings of user profiles. This paper proposes an efficient, distributed, agent-based clustering ensemble method that addresses these issues. In this approach each agent is assigned a small subset of the data and votes on which final cluster its data points should belong to. The final clustering is then evaluated by a global utility, computed in a distributed way. This clustering is also evaluated using an agent-specific utility that is shown to be easier for the agents to maximize. Results show that agents using the agent-specific utility can achieve better performance than traditional non-agent based methods and are effective even when up to 50% of the agents fail.

REFERENCES

• 1: A. Agogino and K. Tumer. Efficient evaluation functions for multi-rover systems. In The Genetic and Evolutionary Computation Conference, pages 1--12, Seatle, WA, June 2004.
• 2: Christopher M. Bishop, Neural networks for pattern recognition, Oxford University Press, Oxford, 1996
• 3: Daniel Boley , Maria Gini , Robert Gross , Eui-Hong Han , George Karypis , Vipin Kumar , Bamshad Mobasher , Jerome Moore , Kyle Hastings, Partitioning-based clustering for Web document categorization, Decision Support Systems, v.27 n.3, p.329-341, Dec.1999 [doi>10.1016/S0167-9236(99)00055-X]
• 4: S. V. Chakravarthy and J. Ghosh. Scale-based clustering using the radial basis function network. IEEE Trans. on Neural Networks, pages 1250--61, September 1996.
• 5: Inderjit S. Dhillon , Dharmendra S. Modha, Concept decompositions for large sparse text data using clustering, Machine Learning, v.42 n.1/2, p.143-175, Jan. 2001 [doi>10.1023/A:1007612920971]
• 6: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 7: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 8: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual conference on Design automation, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
• 9: B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 42(2):291--307, 1970.
• 10: J. Kim and T. Warnow. Tutorial on phylogenetic tree estimation. In "Intelligent Systems for Molecular Biology", Heidelberg, Germany, 1999.
• 11: T. Kohonen. Self-organized formation of topologically correct feature maps. Biological Cybernetics, 43:59--69, 1982.
• 12: J. MacQueen. Some methods for classification and analysis of multivariate observations. In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, volume 1, pages 281--297, 1967.
• 13: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 14: Alexander Strehl , Joydeep Ghosh, Relationship-based clustering and cluster ensembles for high-dimensional data mining, 2002
• 15: Alexander Strehl , Joydeep Ghosh, Cluster ensembles: a knowledge reuse framework for combining partitionings, Eighteenth national conference on Artificial intelligence, p.93-98, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 16: Alexander Strehl, Joydeep Ghosh, and Raymond J. Mooney. Impact of similarity measures on web-page clustering. In Proc. AAAI Workshop on AI for Web Search (AAAI 2000), Austin, pages 58--64. AAAI/MIT Press, July 2000.
• 17: Kagan Tumer , David H. Wolpert , Kagan Turner, Collectives and Design Complex Systems, SpringerVerlag, 2004
• 18: Kagan Tumer , David Wolpert, Collective Intelligence and Braess' Paradox, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.104-109, July 30-August 03, 2000
• 19: Ian H. Witten , Eibe Frank, Data Mining: Practical Machine Learning Tools and Techniques, Second Edition (Morgan Kaufmann Series in Data Management Systems), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 20: D. H. Wolpert and K. Tumer. Optimal payoff functions for members of collectives. Advances in Complex Systems, 4(2/3):265--279, 2001.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Algorithms, Performance

Keywords:
clustering, multiagent systems, reinforcement learning