Conference Proceedings

Are approximation algorithms for consensus clustering worthwhile?

Michael Bertolacci, Anthony Wirth, C Apte (ed.), B Liu (ed.), S Parthasarathy (ed.), D Skillicorn (ed.)

PROCEEDINGS OF THE SEVENTH SIAM INTERNATIONAL CONFERENCE ON DATA MINING | SIAM | Published : 2007

Abstract

Consensus clustering has emerged as one of the principal clustering problems in the data mining community. In recent years the theoretical computer science community has generated a number of approximation algorithms for consensus clustering and similar problems. These algorithms run in polynomial time, with performance guaranteed to be at most a certain factor worse than optimal. We investigate the feasibility of the approximation algorithms, in an attempt to link data-mining and theoretical research. On realistic data sets, algorithms with quadratic runnirig times are impractical. Unfortunately these and even worse running times are typical of approximation algorithms. To circumvent this, ..

View full abstract