Dávid Ferenci: K-means clustering of incomplete data (Paper by Eiben, Fomin, Golovach, Lochet, Panolan and Simonov)

ELTE Alkalmazott Diszkrét Matematika szeminárium

Abstract:
Clustering is one of the most widely used technique in machine learning and
statistics. In general the purpose of clustering is to put similar objects
into k boxes, in such way, that similar objects end up in the same box.
K-means clustering is a special case of this, when according to the data we
determine k points- the centers-, and assign each observation to the
closest center.
This problem is NP-hard for k=2 already. Further complications can be if
the data is corrupted or incomplete.
During my talk I will define the latter problem in general, and show the
main steps of an approximating algorithm by Eduard Eiben et al.