MAPK-means: A clustering algorithm with quantitative preferences on attributes

Article type: Research Article

Authors: El Moussawi, Adnan^{a; b; *} | Giacometti, Arnaud^a | Labroche, Nicolas^a | Soulet, Arnaud^a

Affiliations: [a] Laboratory of Computer Science, University of Tours, France | [b] Kalidea – Groupe Up, Gennevilliers, France

Correspondence: [*] Corresponding author: Adnan El Moussawi, Laboratory of Computer Science, University of Tours, France. E-mail: Adnan.ElMoussawi@univ-tours.fr.

Abstract: This paper describes a new semi-supervised clustering algorithm as part of a more general framework of interactive exploratory clustering, that favors the exploration of possible clustering solutions so that an expert tailors the best clustering according to her domain knowledge and preferences. Contrary to most existing approaches, the novel algorithm considers the feature space as a first class citizen for the exploration of alternative solutions. Our proposal represents and integrates quantitative preferences on attributes that will guide the exploration of possible solutions by learning an appropriate space metric. It also achieves a compromise clustering based on expert confidence, between a data-driven and a user-driven solution and converges with a good complexity. We show experimentally that our method is also able to deal with irrelevant user preferences and correct those choices in order to achieve a better solution. Experiments show that the best results may be achieved only with the addition of preferences to traditional metric learning algorithms and that our approach performs better than state-of-the-art algorithms.

DOI: 10.3233/IDA-184468

Journal: Intelligent Data Analysis, vol. 24, no. 2, pp. 459-489, 2020