TY - JOUR
T1 - Improving clustering with pairwise constraints
T2 - A discriminative approach
AU - Zeng, Hong
AU - Song, Aiguo
AU - CHEUNG, Yiu Ming
N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.
PY - 2013/8
Y1 - 2013/8
N2 - To obtain a user-desired and accurate clustering result in practical applications, one way is to utilize additional pairwise constraints that indicate the relationship between two samples, that is, whether these samples belong to the same cluster or not. In this paper, we put forward a discriminative learning approach which can incorporate pairwise constraints into the recently proposed two-class maximum margin clustering framework. In particular, a set of pairwise loss functions is proposed, which features robust detection and penalization for violating the pairwise constraints. Consequently, the proposed method is able to directly find the partitioning hyperplane, which can separate the data into two groups and satisfy the given pairwise constraints as much as possible. In this way, it makes fewer assumptions on the distance metric or similarity matrix for the data, which may be complicated in practice, than existing popular constrained clustering algorithms. Finally, an iterative updating algorithm is proposed for the resulting optimization problem. The experiments on a number of real-world data sets demonstrate that the proposed pairwise constrained two-class clustering algorithm outperforms several representative pairwise constrained clustering counterparts in the literature.
AB - To obtain a user-desired and accurate clustering result in practical applications, one way is to utilize additional pairwise constraints that indicate the relationship between two samples, that is, whether these samples belong to the same cluster or not. In this paper, we put forward a discriminative learning approach which can incorporate pairwise constraints into the recently proposed two-class maximum margin clustering framework. In particular, a set of pairwise loss functions is proposed, which features robust detection and penalization for violating the pairwise constraints. Consequently, the proposed method is able to directly find the partitioning hyperplane, which can separate the data into two groups and satisfy the given pairwise constraints as much as possible. In this way, it makes fewer assumptions on the distance metric or similarity matrix for the data, which may be complicated in practice, than existing popular constrained clustering algorithms. Finally, an iterative updating algorithm is proposed for the resulting optimization problem. The experiments on a number of real-world data sets demonstrate that the proposed pairwise constrained two-class clustering algorithm outperforms several representative pairwise constrained clustering counterparts in the literature.
KW - Discriminative approach
KW - Maximum margin clustering
KW - Pairwise constraints
KW - Robust pairwise loss function
UR - http://www.scopus.com/inward/record.url?scp=84880072082&partnerID=8YFLogxK
U2 - 10.1007/s10115-012-0592-8
DO - 10.1007/s10115-012-0592-8
M3 - Journal article
AN - SCOPUS:84880072082
SN - 0219-1377
VL - 36
SP - 489
EP - 515
JO - Knowledge and Information Systems
JF - Knowledge and Information Systems
IS - 2
ER -