MSc thesis of Eleni Mpakali
On the meaningful instances of clustering
Supervisor: Dimitris Achlioptas
Clustering is a problem with many different definitions, approaches and applications, but not well defined mathematically. Especially it is not clear how to define meaningfulness, and how to de- termine if a solution is meaningful, in the sense that it reveals some existing inherent in the data structure. When we refer to clustering via optimization of some objective functions, it is usually a task performed efficiently, despite that most existing objective functions are NP-hard. We will present some existing results showing that “meaningful” instances can be solved effi- ciently. In these papers is made apparent (implicitly or explicitly) a connection between structure in the data, and the behavior of the objective function over the space of solutions. We will propose a method exploiting this connection, that could decide for each pair {objective function, dataset}, if it is “meaningful” the particular dataset to be clustered by optimizing (or ap- proximating) this particular objective function.
Defended: Dec. 15, 2014.