Publication
Title
Bounded correlation clustering
Author
Abstract
Correlation clustering is to partition a set of objects into clusters such that the number of false positives and negatives is minimized. In this paper, we combine correlation clustering and user interaction. More specifically, we allow the user to control the quality of the clustering by providing error bounds on the number of false positives and negatives. If no clustering exists that satisfies these bounds, a set of edges is returned for user inspection such that the deletion or relabeling of these edges guarantees the existence of a clustering consistent with the error bounds. A user, however, may reject the deletion or relabeling of certain edges and ask for an alternative set of edges to be provided. If no such set of edges exists, a minimal change to the error bounds should be provided, after which the interactive process continues. The focus of this paper is on the algorithmic challenges involved in returning a minimal set of edges to the user. More specifically, we formalize the Bounded Correlation Clustering problem and show that it is intractable. Therefore, we propose an approximation algorithm based on the well-known region growing technique. We experimentally validate the efficiency and accuracy of the approximation algorithm.
Language
English
Source (journal)
International journal of data science and analytics
Publication
2016
Volume/pages
(2016), p. 1-19
Full text (Publishers DOI)
Full text (publishers version - intranet only)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
Affiliation
Publications with a UAntwerp address
External links
Record
Identification
Creation 07.03.2016
Last edited 22.11.2016
To cite this reference