Title | ||
---|---|---|
A Kernel-Learning Approach to Semi-supervised Clustering with Relative Distance Comparisons |
Abstract | ||
---|---|---|
We consider the problem of clustering a given dataset into k clusters subject to an additional set of constraints on relative distance comparisons between the data items. The additional constraints are meant to reflect side-information that is not expressed in the feature vectors, directly. Relative comparisons can express structures at finer level of detail than must-link (ML) and cannot-link (CL) constraints that are commonly used for semi-supervised clustering. Relative comparisons are particularly useful in settings where giving an ML or a CL constraint is difficult because the granularity of the true clustering is unknown. Our main contribution is an efficient algorithm for learning a kernel matrix using the log determinant divergence (a variant of the Bregman divergence) subject to a set of relative distance constraints. Given the learned kernel matrix, a clustering can be obtained by any suitable algorithm, such as kernel k-means. We show empirically that kernels found by our algorithm yield clusterings of higher quality than existing approaches that either use ML/CL constraints or a different means to implement the supervision using relative comparisons. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1007/978-3-319-23528-8_14 | ECML/PKDD |
Field | DocType | Volume |
k-medians clustering,Fuzzy clustering,Canopy clustering algorithm,CURE data clustering algorithm,Correlation clustering,Pattern recognition,Artificial intelligence,Constrained clustering,Cluster analysis,Mathematics,Single-linkage clustering | Conference | 9284 |
ISSN | Citations | PageRank |
0302-9743 | 4 | 0.42 |
References | Authors | |
23 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ehsan Amid | 1 | 21 | 6.83 |
Aristides Gionis | 2 | 6808 | 386.81 |
antti ukkonen | 3 | 114 | 7.47 |