2009
2009IEEE/WIC/ACM
IEEE/WIC/ACMInternational
InternationalJoint
JointConferences
Conference on
on WebWeb IntelligenceIntelligence andand Intelligent
Intelligent Agent
Agent Technologies
Technology

Clustering with Constrained Similarity Learning
Masayuki Okabe
Toyohashi University of Technology
Tenpaku 1-1, Toyohashi, Aichi, Japanokabe@imc.tut.ac.jp

Seiji Yamada
National Institute of Infomatics
Chiyoda, Tokyo, Japanseiji@nii.ac.jp

Abstract—This paper proposes a method of learning asimilarity matrix from pairwise constraints for interactive
clustering. The similarity matrix can be learned by solving
an optimization problem as semi-deﬁnite programming where
we give additional constraints about neighbors of constrained
pairwise data besides original constraints. For interactive
clustering, since we can get only a few pairwise constraints
from a user, we need to extend such constraints to richer ones.
Thus this proposed method to extend the pairwise constraints
to space-level ones is effective to interactive clustering. First we
formalize clustering with constrained similarity learning, andthen introduce the extended constraints as linear constraints.
We verify the effectiveness of our proposed method by applying
it on a simple clustering task. The results of the experimentsshows that our method is promising.

to allocate pairs of data with must-link to different clusters
and not to allocate pairs of data with cannot-link to thesame cluster. This approach is simple but it becomes too
difﬁcult to make consistent clusters with constraints when
the number of must/cannot-link pairs increases. Since COPKmeans does only greedy search, its clustering procedure
may stop on the way.
Meanwhile, another approach uses constraints to modify
similarities between data as similarities of must-link pairs
are forced to be large and similarities of cannot-link pairs
are forced to be small. There are several methods to realize this approach [Klein 02], [Shwartz 04], [Davis 07],
[Tang 07], [Hoi 07], [Li 08]. For example, Klein et. al
proposed a clustering algorithm to deal with space-level
constraints in addition to ordinary instance-level constrains
with must/cannot-links [Klein 02]. They claimed neighborsaround data constrained by must/cannot-links should beconstrained in the similar way to the data, and developed
concrete methods to propagate space-level constrains bysatisfying triangle inequality with all-pairs-shortest-paths
and utilizing complete-link hierarchical agglomerative clustering. Li et. al proposed a method to learn a kernel matrix
that is obtained by solving an optimization problem as
semi-deﬁnite programming. They integrate must/cannot-link
constraints into the optimization problem to propagate local
constraints to the whole kernel matrix. However how themust/cannot-link constraints inﬂuence the kernel value of theother pairs is not clear though it ensures the kernel value of
constrained pairwise data.
Based on these two methods, we propose a similarity
learning method that produces a similarity matrix. Though
our method obtains the similarity matrix by solving an
optimization problem as the same way Li et. al do, we
impose additional constraints about neighbors of constrained
pairwise data on it. By imposing the additional constraints,
similar data move together when given must/cannot-link to
one of them. This approach is very similar to Klein’s in terms
of propagating space-level constrains under a complete-linkhierarchical agglomerative clustering, however our approach
does not need a special clustering algorithm and is independent of a clustering algorithm. Also our method can control
coverage of the propagation by changing the number ofneighbors.

I. I NTRODUCTION
Interactive clustering is a signiﬁcant method to realize
intelligent Web interaction because it is very useful tointeractive visualization, data mining, data analysis of theweb[Wu04]. Interactive clustering consists of two maintechniques: active learning and constrained clustering. The
active learning is for selecting effective data, which are
judged by a user and then used as constraints. Also theconstrained clustering is used to categorize the data undersuch constrains from a user. The common requirement in theboth technique is to cope with a few constraints form a user.
In this paper, we propose constrained clustering to utilize
such a few constraints as much as possible by extendinga few constraints to richer ones. Semi-Supervised learningthat makes classiﬁers or clusters from a little supervised
information and a lot of unlabeled data has been researchedvigorously in recent years. Constrained clustering is one ofsuch learning problems. In the typical setting of constrained
clustering, several numbers of pairwise data are given as
either must-link or cannot-link constraints. The pair of mustlink data must be in the same cluster. On the other hand,the pair of cannot-link data cannot be in the same cluster.
One simple use of these constraints is to build a procedure
into clustering algorithms to check whether temporal clusters
break constraints or not. COP-Kmeans proposed by Wagstaff[Wagstaff 01] is such a representative method. COP-Kmeans
is a modiﬁed version of the K-means algorithm. It ﬁrst
selects cluster centers, and second allocates each data to
one of those centers not to break given constraints, i.e. not978-0-7695-3801-3/09 $26.00 © 2009 IEEE
DOI 10.1109/WI-IAT.2009.223

30

        





   

         Figure 1.

Difference of neighbor’s movement between base and proposed method

where L̄ • K represents the inner product between L̄ and K.
L̄ • K is calculated as follows.
nn ¯lij kijL̄ • K =In the following sections, we ﬁrst explain about similarity
learning and formalize it as semi-deﬁnite programming insection 2. Then we describe about our proposed method that
impose additional constraints to the original optimization
problem in section 3. section 4 shows experimental results
where obtained similarity matrix is applied on a simple
clustering task. Finally, we conclude our work in section
5.

i=1 j=1¯lij is the element of L̄. This objective function measures inconsistency between the original and new similarity matrix.
Thus the solver of the optimization problem tends to keep
similarities between pairs with no constraints the same value
as far as possible. Pairwise constraints are translated into
kij = 1 for must-link pairs, kij = 0 for cannot-link pairs.
K  0 means K is a semi-deﬁnite matrix. This conditionis necessary to guarantee the solution is a metric on the
Euclidean space. By solving this optimization problem, we
can obtain a new similarity matrix K that is used for semisupervised learning.

II. S IMILARITY L EARNING
In this section, we formalize a similarity learning as asemi-deﬁnite programming.
Let P denote a data collection where each data pi ∈Rm (i = 1, ..., n) is a vector of length m. Let S ∈ Rn×n
denote its similarity matrix where each sij (0 ≤ sij ≤ 1)
is a similarity between pi and pj . Pairwise constraints are
given as follows.
M= {(i, j) | (pi , pj ) is a must-link pair}C= {(i, j) | (pi , pj ) is a cannot-link pair}

III. E XTENDING CONSTRAINS FROM PAIRWISE TO
NEIGHBORS

The optimization problem introduced in the previous
section returns a similarity matrix. To satisfy the pairwise
constraints and the semi-deﬁnite condition, returned similarity matrix changes from the original one. Although the
purpose of similarity learning is not only to modify similarities between constrained data pairs but also to inﬂuence
those constraints to their neighbors, it is not clear how theinﬂuence of constraints are propagated to non-constrained
data. Thus we propose to impose additional constraints
about neighbors of constrained data pairs to the optimization
problem.
We illustrate this desirable effect in Figure 1, where
two pairs of data (one data of red color and two data ofblue color) are constrained as must-link and cannot-linkrespectively. Since the original optimization problem considers only the relation between constrained data pairs, thesolution may result the data allocation illustrated in Figure1(a), where only the data of red color moves. However
we expect that not only constrained data pairs but also

The objective of similarity learning is to create a newsimilarity matrix K that satisﬁes above constraints. We formalize an optimization problem to obtain K as semi-deﬁnite
programming. Before formalizing, we describe about thegraph Laplacian that is used as coefﬁcient for K in the
optimization
problem. Let D a diagonal matrix where dii =nj=1 sij . We can deﬁne the graph Laplacian L as follows.
L=D−S
1

1

Using its normalized version L̄ = I − D− 2 SD− 2 , we canformalize an optimization problem as follows:
minK : L̄ • K
s.t. :

kii = 1, i = 1, ..., nkij = 1, ∀ (i, j) ∈ M,
kij = 0, ∀ (i, j) ∈ C,K031

their neighbors are affected by the constraints illustrated in
Figure 1(b), where the data of red color and its neighbors(two data of green color maked with black bold rectangle)
move together. To realize the latter phenomena, we impose
additional constraints to the optimization problem. Morespeciﬁcally, for a data pair (i, j) with must-link or cannotlink, we impose the following constraints:

5) After assignment ﬁnished, calculate whole similarity
Ddescribed below.
D=

where Ck is a cluster. Let D as Dorig
6) For each pi , replace pi and each ci and calculate Dtmp .
If Dtmp −Dorig < 0, stock the pair (pi , ci ). Then ﬁnd
the pair (p∗i , c∗i ) that produce the smallest Dtmp −Dorig . Replace p∗i and c∗i . Let Dorig = Dtmp (p∗i , c∗i ),and return procedure 2. If no pair (pi , ci ) produce
Dtmp − Dorig < 0, this algorithm stops and returnthe temporal clusters.
We compare the following two methods to investigate theeffect of additional constraints we impose.
• A method with constraints about must-link and cannotlink that are originally given.(KK-MEANS)• A method with constraints about neighbors in addition to the original must-link and cannot-link (NKKMEANS). In the experiments, we set k = 1 for thenumber of neighbors to consider as constraints.
We use Normalized Mutual Information (NMI) as theperformance measure. This measure is deﬁned as follows.

where kjrti (t = 1, .., k) is neighbors of pj , and −¯lij =√ sij
is a value of regularized sij . In the same manner,dii djj

we impose the following constraints about pj .

tt

if (i, j) ∈ M
if (i, j) ∈ C

These constraints means not only pj but also its neighbors
kjrti move closer to pi if (i, j) is must-link, and they movefarther if (i, j) is cannot-link. After all, the ﬁnal optimization
problem is formalized as follows.
minK : L̄ • K
s.t. :

kii = 1,kij = 1,kij = 0,kirj ≤ −¯lirj , kjrti ≤ −¯ljrti ,ttkirj ≥ −¯lirj , kjrti ≥ −¯ljrti ,ttK0(pi − ct )2

t=1 pi ∈Ck

kjrti ≤ −¯ljrti , if (i, j) ∈ M
kjrti ≥ −¯ljrti , if (i, j) ∈ C

kirj ≤ −¯lirj ,ttkirj ≥ −¯lirj ,Nk 

i = 1, ..., n(i, j) ∈ M,∀(i, j) ∈ C,∀(i, j) ∈ M∀(i, j) ∈ C∀

NMI(C, T ) =I(C, T )
H(C)H(T )where C is the set of clusters returned by the k-means
algorithm, and T is the set of true clusters. I(C, T ) is themutual information between C and T , and H(C) and H(T )are the entropies.
We test several numbers of constraints. For each numberof constraints, constrained data pairs are randomly generated
10 times. Initial seeds for K-means are also randomly generated 10 times. Thus the evaluated values are the averageof total 100 results. Table I shows the results. For theexperiments of NKK-MEANS, we change the number ofneighbors for the additional constraints (represented by t
in the table). The performance of our proposed method
NKK-MEANS is better than KK-MEANS at evary numberof constraints when t = 1. NKK-MEANS needs only 50
constraints to achieve KK-MEANS’s performance with 100
constraints. This property is very useful if we do not haveenough number of constraints such as interactive clustering.
However we need more experiments and analysis to realize
the reason that the performance degrades as t increases forevery number of constraints.

The fourth and ﬁfth constraints are different from the original problem. By imposing these constraints we intend toensure that similarities between constrained pairwise data
and their neighbors changes in the same way.
IV. E XPERIMENTS
In this section, we evaluate our proposed method on
a clustering task. We use a dataset tr31 from evaluation
datasets for the CLUTO system. The tr31 is a document
dataset derived from TREC collection. It consists of 926
documents and 7 categories. We use cosine distance for the
initial similarity measure, and the SDPA package1 for the
optimization tool, and K-medoids algorithm for clustering.
The procedure including K-medoids algorithm is described
below.
1) Calculate the initial similarity matrix S.
2) Solve the optimization problem described in section 3
and obtain a new similarity matrix K.
3) Select initial cluster centers ci (i = 1 ∼ Nk )4) For each data pi , sort ci in descending order of thesimilarity between pi and ci . Assign pi to the top ci .

V. C ONCLUSION
We proposed a method of learning a similarity matrix
from pairwise constraints. Our method is based on thesame approach proposed by Li et.al, which produces asimilarity matrix by solving an optimization problem as
semi-deﬁnite programming. However we impose additional

1 http://sdpa.indsys.chuo-u.ac.jp/sdpa/

32

Table I
R ESULTS
Num. of constraints
10
50
100
200
500

KK-MEANS
0.076
0.173
0.222
0.254
0.304

t=1
0.150
0.225
0.239
0.288
0.331

constraints that neighbors of constrained pairwise data arealso inﬂuenced by the constraints, i.e. neighbors of a mustlinked pair also become similar to the pair, and neighborsof a cannot-link pair also become not-similar. Experimental
results on a simple clustering task shows that our approachis promising though we must test it on other test beds andanalyze in detail.
In future work, we have a plan to conduct systematic
experiments to evaluate our method in documents clustering
using large data bases. Also we will investigate the inﬂuenceof the number of neighbors and develop how to control it,
and ﬁnd out more effective constrains on the neighbors.

NKK-MEANS
t=2
t=3
t=4
0.100
0.08
0.03
0.224
0.214 0.189
0.235
0.207 0.231
0.240
0.235 0.258
0.308
0.320 0.342

t=5
0.06
0.185
0.211
0.270
0.314

[Li 08] Li, Z., Liu, J. and Tang, X.: “Pairwise Constraint Propagation by Semideﬁnite Programming for Semi-Supervised
Classiﬁcation”, In Proceedings of the 25th International Conference on Machine Learning , pp.576-583, 2008.

R EFERENCES[Wu04] Wu, W., Yu, C., Doan, A. and Meng, W., “An interactive
clustering-based approach to integrating source query interfaces on the deep Web”, In Proceedings of the 2004 ACM
SIGMOD international conference on Management of data,
pp.95-106, 2004.
[Wagstaff 01] Wagstaff, K. and Roger, S. : “Constrained K-means
Clustering with Background Knowledge”, In Proceedings ofthe 18th International Conference on Machine Learning ,pp.577-584, 2001.
[Klein 02] Klein, D., Kamvar, S. D. and Manning, C. D., “FromInstance-level Constraints to Space-Level Constraints: Making the Most of Prior Knowledge in Data Clustering”, In
Proceedings of the 19th International Conference on Machine
Learning, pp.307-314, 2002.
[Shwartz 04] Shwartz, S., Singer, Y. and Ng, A. Y. : “Online andBatch Learning of Pseudo-Metrics”, In Proceedings of the
21st International Conference on Machine Learning , pp.94101, 2004.
[Davis 07] Davis, J., Kullis, B. and et.al. : “Information-Theoretic
Metric Learning”, In Proceedings of the 24th International
Conference on Machine Learning , pp.209-216, 2007.
[Tang 07] Tang, W., Xiong, H., Zhong, S. and Wu, J. : “Enhancing
Semi-Supervised Clustering: A Feature Projection Perspective”, In Proceedings of the 13th International Conference on
Knowledge Discovery and Data Mining, pp.707-716, 2007.
[Hoi 07] Hoi, S. C. H., Jin, R. and Lyu, M. R.: “Learning Nonparametric Kernel Matrices from Pairwise Constraints”, In
Proceedings of the 24th International Conference on Machine
Learning , pp.361-368, 2007.
33