Abstract:
Constraint-based clustering leverages user-provided constraints to produce a clustering that matches the user’s expectation. In active constraint-based clustering, the algorithm selects the most informative constraints to query in order to produce good clusterings with as few constraints as possible. A major challenge in constraint-based clustering is handling noise: the majority of existing approaches assume that the provided constraints are correct, while that might not be the case. In this paper, we propose a method to identify and correct noisy constraints in active constraint-based clustering. Our approach reasons probabilistically about the correctness of the user’s answers and asks additional constraints to corroborate or correct the suspicious answers. We demonstrate the method’s effectiveness by incorporating it into COBRAS, a state-of-the-art method for active constraint-based clustering. Compared to COBRAS and other active-constraint-based clustering algorithms, the resulting system produces better clusterings in the presence of noise.
