Affiliations: [a] LIAAD-INESC TEC, Porto, Portugal | [b] Instituto de Telecomunicações, Instituto Superior Técnico, Lisbon, Portugal | [c] GECAD-ISEP, Institute of Engineering, Polytechnic of Porto, Porto, Portugal
Abstract: Constrained data clustering algorithms allow the incorporation of a priori knowledge for specific problems into the clustering task in the form of constraints. The quality of the constraints have great impact in the performance of the constrained clustering algorithms. Therefore, special care must be taken while building the sets of constraints. In order to take the maximum advantage of the constrained clustering algorithms, these constraints must be highly informative and non-redundant. We propose two constraint acquisition methods based on user-feedback. The first method searches for non-redundant intra-cluster and inter-cluster query-candidates supported by information contained in an initial partition of the data set, ranks the candidates by decreasing order of interest and, finally, prompts the user the most relevant query-candidates. The constraints may optionally be used for learning a new data representation, which may enhance the performance of clustering. The second method iterates between using the previous method for expanding the set of constraints, and producing an updated partition of the data. The motivation is to iteratively increment the set of constraints by including new informative and non-redundant constraints at each iteration. Experimental results advocate that the proposed constraint acquisition methods increase the performance of data clustering.
Keywords: Constraint acquisition, constrained data clustering, semi-supervised learning
