Okabe, M. and Yamada, S.

Paper:

Learning Similarity Matrix from Constraints ofRelational Neighbors
Masayuki Okabe∗ and Seiji Yamada∗∗∗ Information and Media Center, Toyohashi University of Technology

1-1 Tenpaku, Toyohashi, Aichi 441-8580, Japan
E-mail: okabe@imc.tut.ac.jp∗∗ National Institute of Informatics, the Graduate University for Advanced Studies (SOKENDAI)
2-1-2 Hitotsubashi, Chiyoda, Tokyko 101-8430, Japan[Received December 15, 2009; accepted March 8, 2010]

This paper describes a method of learning similarity
matrix from pairwise constraints assumed used under
the situation such as interactive clustering, where we
can expect little user feedback. With the small number of pairwise constraints used, our method attempts
to use additional constraints induced by the affinity relationship between constrained data and their neighbors. The similarity matrix is learned by solving an
optimization problem formalized as semidefinite programming. Additional constraints are used as complementary in the optimization problem. Results ofexperiments confirmed the effectiveness of our proposed method in several clustering tasks and that our
method is a promising approach.

Keywords: learning similarity matrix, semidefinite programming, constrained clustering

1. Introduction
Interactive clustering is a significant method to realize
intelligent Web interaction because it is very useful forinteractive visualization, data mining and data analysis of
the Web [1]. Interactive clustering consists of two maintechniques: active learning and constrained clustering.
The active learning selects effective data as judged by theuser, then is used as constraints [2]. The constrained clustering categorizes the data under such constraints from auser. Both pursue the common requirement of dealing
with constraints from the user [3].
In this paper, we propose a method of constrained clustering using as few constraints as possible by expanding them into richer constraints. Semi-supervised learning creating classifiers or clusters from limited supervised
information and much unlabeled data has been vigorously researched [4], with constrained clustering used asa learning problem. In the typical setting for constrained
clustering, several pairwise data are given as either mustlink or cannot-link constraints. Must-link pair data must
be in the same cluster, but cannot-link pair data cannot be.
One simple use of these constraints is to build a402

procedure into clustering algorithms to check whether
clusters break constraints. COP-K-means proposed by
Wagstaff [5] is one such representative method. COP-Kmeans is a modified version of the K-means algorithm. It
first selects cluster centers to which it allocates data while
ensuring that the given constraints are not broken, i.e.,pairs of data with must-links are not allocated to different
clusters and vice versa. While simple, this approach is too
difficult for creating consistent clusters with constraints
as must/cannot-link pairs increases. Since COP-K-means
conducts only a greedy search, causing clustering to stop
before a task is completed.
Meanwhile, another approach uses constraints to modify the similarities between data as the similarities ofmust-link pairs must be large and the similarities ofcannot-link pairs must be small. There are several
methods to realize this approach [6–11]. For example,
Klein et al. proposed a clustering algorithm to deal withspace-level constraints in addition to ordinary instancelevel constrains with must/cannot-links [6]. They maintained that neighbors around given data constrained bymust/cannot-links should be constrained similarly to data,
and developed ways to concretely propagate space-level
constraints by satisfying triangle inequality using allpairs-shortest-paths and complete-link hierarchical agglomerative clustering. Li et al. [11] proposed a method
to learn a kernel matrix that is obtained by solving an optimization problem as semidefinite programming. They integrate the must/cannot-link constraints into the optimization problem to propagate local constraints into the wholekernel matrix. How such constraints influence the kernel
value of other pairs remains unclear, although it ensures
only the kernel value of constrained pairwise data.
Based on these two methods, we propose a similarity
learning method producing a similarity matrix by solving an optimization problem in the same way as Li et al.
We additionally impose constraints on the neighbors ofconstrained pairwise data to move similar data together
based on the movement of pairwise constrained data. Thisis similar to Klein’s approach in propagating space-level
constrains under complete-link hierarchical agglomerative clustering, although we need no special clustering algorithm such as agglomerative clustering and is indepen-

Journal of Advanced Computational Intelligenceand Intelligent Informatics

Vol.14 No.4, 2010

Learning Similarity Matrix from Constraintsof Relational Neighbors

dent of such algorithms. Our method controls constraint
propagation coverage by changing the number of neighbors.
In the sections that follow, we first explain similarity
learning and formalize it as a form of semidefinite programming in Section 2. We then discuss learning similarity matrix imposing additional constraints on the original optimization problem in Section 3. Section 4 presents
experimental results in which the similarity matrix thus
obtained is applied to a simple clustering task. Section 5
presents conclusions.

2. Basic Similarity Learning
In this section, we formalize similarity learning as asemidefinite programming problem.
Let P be a data collection where each data pi ∈ Rm (i =1, ..., n) is a vector of dimension m. Let S ∈ Rn×n be its
similarity matrix, where each si j (0 ≤ si j ≤ 1) is the similarity between pi and p j . Pairwise constraints are given
as follows:
M = {(i, j) | (pi ,p j ) is a must-link pair}(1)
C = {(i, j) | (pi ,p j ) is a cannot-link pair}The objective of similarity learning is to create a newsimilarity matrix K satisfying the above constraints, i.e.,
data pairs in M must be similar (ki j = 1) and data pairs in
C must be dissimilar (ki j = 0). Before formalizing an optimization problem to obtain K as semidefinite programming [12], we use a graph Laplacian [13] as a coefficientfor K in the optimization problem, letting D be a diagonal
matrix where dii = ∑nj=1 si j and defining the graph Laplacian L as follows:
L = D − S . . . . . . . . . . . . . . . (2)Using normalized version L̄ = I − D− 2 SD− 2 , we formalize an optimization problem for the similarity learning
as follows:
minK : L̄ • K
1

1

kii = 1, i = 1, ..., nki j = 1, ∀ (i, j) ∈ M, . . . . . . (3)ki j = 0, ∀ (i, j) ∈ C,
K0s.t. :

L̄ • K represents the inner product between L̄ and K.
L̄ • K is calculated as follows.
nnL̄ • K = ∑ ∑ l¯i j ki j . . . . . . . . . . . (4)i=1 j=1l¯i j is the element of L̄. This objective function assigns
a large or small value to a data pair whose original similarity is high or low to get a matrix satisfying constraints
while maintaining the original dataset affinity by solving
the optimization problem. K  0, a condition making K
a semidefinite matrix guarantees a matrix K is a Mercer
kernel matrix.

Vol.14 No.4, 2010

Several available software packages solve generalsemidefinite programming problems, as used below tosolve this optimization problem.

3. Constraints Extended from Pairwise to
Neighbors
New similarity matrix K returned by the above solver
differs from original similarity matrix S. In this section,
we question how the new similarity matrix is changed
by constraints because we consider that constraint influence should be propagated locally, i.e., in local nonconstrained data. For this, we introduce additional pseudo
constraints for local propagation created by given constraints, as shown in Fig. 1, where two pairs of data (onestar and two diamonds) are constrained as a must-link anda cannot-link in 2-dimensional data space respectively.
The original optimization problem takes into account only
the relationship between constrained data pairs, so the solution may result in the data allocation in Fig. 1(a), where
only the star data moves. We posit, however, both constrained data pairs and their neighbors are affected byconstraints in Fig. 1(b), where star data and its neighbors– two diamonds called relational neighbors – move together. To achieve this influence of constraints, we impose additional constraints on the optimization problem,i.e., for data pair (i, j) with must-link or cannot-link, we
impose the following constraints:
kir j ≤ −l¯ir j , k jrti ≤ −l¯jrti , i f (i, j) ∈ Mtt. . (5)k j ≥ −l¯ j , k i ≥ −l¯ i , i f (i, j) ∈ C
irt

irt

jrt

jrt

rti is the t-th nearest neighbor of pi , rtj is the t-th nearest
neighbor of p j , kir j is the similarity between pi and rtj , k jrtits
is the similarity between p j and rtj , and −l¯i j = √ i j isdii d j ja regularized value of si j . rti is thus a relational neighborof p j , and rtj is a relational neighbor of pi , as shown in
Fig. 2.
By adding these constraints,we expect that not only pijand p j move closer but also pi and rt , p j and rti movecloser if pi and p j are must-link pair. Similarly, if they
are cannot-link pair, we expect not only pi and p j movefarther but also pi and rtj , p j and rti move farther.
After all, the final optimization problem is formalized
as follows:
minK : L̄ • K
s.t. :

i = 1, ..., nkii = 1,
∀ (i, j) ∈ M,
ki j = 1,∀ (i, j) ∈ C,
ki j = 0,
kir j ≤ −l¯ir j , k jrti ≤ −l¯jrti , ∀ (i, j) ∈ Mtt
kir j ≥ −l¯ir j , k jrti ≥ −l¯jrti , ∀ (i, j) ∈ C
t
t
K0

(6)

The fourth and fifth constraints are different from theoriginal problem. By imposing these constraints, we en-

Journal of Advanced Computational Intelligenceand Intelligent Informatics

403

Okabe, M. and Yamada, S.

cannot-link
must-linkLearning Similarity

Learning Similarity

Star-shaped data and its
neighbors moves

Only star-shaped data moves(b) Proposed Method(a) Base MethodFig. 1. Difference in neighbor’s movement between base and proposed method.

After learning

Before learning


pi
rti

l irt j

rt j


pj

l jrti


pi
rti

kir j

rt j

t


pj

k jr it

Fig. 2. Relational neighbors.

sure that similarities between constrained pairwise data
and their relational neighbors change in the same way.

4. Experiments
In this section, we evaluate our proposed method on
several clustering tasks. We used four datasets, Iris, Soybean, Wine, and Glass from the UCI Machine Learning
Repository1 . We standardize attribute values for the Winedataset alone. The details about these datasets are summarized in Table 1. The experimental procedure consistsof two main steps. First, a similarity matrix of a dataset
is calculated from constraints. Second, a clustering algorithm is applied to the dataset with the above matrix. Thenthe results are evaluated. We use the k-medoids clustering
algorithm in this procedure. A detailed description of thealgorithm is shown as Algorithm 1.
The elements of the initial similarity matrix are calcu22
lated by using si j = e−di j /σ , where si j is a value of the
1. http://www.ics.uci.edu/˜mlearn/

404

Table 1. Datasets.

Datasetdata
attribute
class
σ

Iris
150
4
3
0.271

Soybean
47
35
4
0.5

Wine
178
13
3
0.055

Glass
214
9
6
0.473

similarity between data i and j, di j is an Euclidean distance, and σ is the parameter shown in Table 1. We use
the SDPA package2 for solving the semidefinite programming.
We compare the following two methods of similarity
learning to investigate the effect of additional constraints
in our method.
• A method that uses only given constraints (data pairsof must/cannot-link) for learning a similarity matrix.
(KK-MEANS)
2. http://sdpa.indsys.chuo-u.ac.jp/sdpa/

Journal of Advanced Computational Intelligenceand Intelligent Informatics

Vol.14 No.4, 2010

Learning Similarity Matrix from Constraintsof Relational Neighbors

Algorithm 1 Clustering Procedure
1: Calculate initial similarity matrix S.

 
 

2: Solve the optimization problem described in Sec- 

tion 3 to obtain new similarity matrix K.
3: Select initial cluster centers ci (i = 1 ∼ Nk ).

              

4: For each data pi , sort ci in descending order of simi-    

larity between pi and ci . Assign pi to top ci .
 

Nk

D = ∑ ∑ (pi − ct )2          

t=1 pi ∈Ck

Ck is a cluster. Let D as Dorig If Dtmp − Dorig < 0,  

Fig. 3. Iris.

stock pair (pi , ci ). Then find pair (p∗i , c∗i ) that produces smallest Dtmp − Dorig . Replace p∗i and c∗i . Let
Dorig = Dtmp (p∗i , c∗i ), and go to Step 2. If no pair(pi , ci ) produces Dtmp − Dorig < 0, stop and return
temporal clusters.


 
 



 

           • A method that uses given constraints and constraints

concerning the relational neighbors of given constraints. (NKK-MEANS). For this method, we test
t = 1 ∼ 5 (the number of relational neighbors) oneach dataset.

           

Vol.14 No.4, 2010

 
 

(7)

 



C is the set of clusters returned by the K-means algorithm, and T is the set of true clusters. I(C, T ) is the mutual information between C and T , and H(C) and H(T )are the entropies.
Following Li et al. [11], we test different sets of constraints. For the j-th constraint set, j must-link constraints
for each class, and j cannot-link constraints for every twoclasses are randomly generated. Thus for a database of
k classes, the j-th constraint set consists of a total ofj × (k + k(k − 1)/2) constraints. We also follow the setting of j that ranges from 1 to 10.
The results are shown in Figs. 3-6. Fig. 3 shows theIris dataset results. The horizontal axis shows the number of constraints, and the vertical axis represents the
NMI value. For every method, the performance improvesas the number of constraints increases with few exceptions. These exceptions suggest that some constraints do
not help to improve the performance. In this dataset, ourmethod outperforms the base one on almost every point.
The Soybean in Fig. 4 shows similar characteristics to theIris dataset. In the Wine dataset (Fig. 5), our method performed pretty well although the constraints do not help toimprove the performance. However, our method does notwork well or performs worse in the Glass dataset where
the base method maintains a stable performance. We consider the reason of the result and the effect of the constraints of relational neighbors in the next section.

  

Fig. 4. Soybean.

                      

 
 


            

Fig. 5. Wine.
 
 
 



NMI(C, T ) = . . . . . . .
H(C)H(T )    

We used Normalized Mutual Information (NMI) as theperformance measure. This measure is defined as follows:
I(C, T )                       

 
 






          

Fig. 6. Glass.

Journal of Advanced Computational Intelligenceand Intelligent Informatics

405

Okabe, M. and Yamada, S.

 







































Fig. 8. Soybean.

Fig. 7. Iris.

 
 
 
 
 
 
 
 
 
 
 

 





 



 



 



 








































    

Fig. 10. Glass.

Fig. 9. Wine.

5. Discussion


































































































































 









 



 















    

Table 2. Distribution of class members.

In the previous section, we stated that our method outperforms the base method in three datasets. We first investigated the effect of additional constraints that are used in
our proposed method in more detail. Figs. 7-10 show theperformance of each method for each set of constraints.
The number listed in the right side of each graph is thenumber of constraints. Each method is shown along horizontal axis. For example, NKK-MEANS (t = 2) is our
proposed method where two relational neighbors are considered for each other’s pairwise data. Thus, in this case, a
total of four additional constraints is appended when calculating a similarity matrix.
These graphs show the effect of the number of relational neighbors. Although the appropriate number of relational neighbors may differ from dataset to dataset, 3∼5is the proper range for the datasets used in this experiment(without Glass dataset). It seems that the effect of thenumber of relational neighbors is not related to the number of constraints. In the Iris dataset, the performance
partially decreases when the number of constraints was
24 and 42. However, the strength of the influence differs from the number of relational neighbors. For exam406











































 



















































































 





 



 







 




 









 





 





 

 



 

Iris
SoybeanWine
Glass(50,50,50)(10,10,10,17)(48,59,71)(9,13,17,29,70,76)

ple, when the number of constraints is 24, the influenceis bad at t = 1, 2, however, not so much at t = 3, 4. In
contrast, when the number of constraints is 42, the influence is limited at t = 1, 2, but, terrible at t = 3, 4. These
results indicate that there may be good or bad constraints
combination. Thus, we need to select an appropriate setof constraints, and this is our open problem.
Finally, we investigated why our method does not workon the Glass dataset. Table 2 lists the distributions of thenumber of class members in each dataset. For example,
the distribution (48, 59, 71) in the Iris dataset represents
that it has three classes and the number of members ineach class is 48, 59, 71, respectively. The Glass dataset isrelatively different from the others. It has more classes(6 classes), and the distribution bias is relatively large
compared with the other datasets. Our method takes into

Journal of Advanced Computational Intelligenceand Intelligent Informatics

Vol.14 No.4, 2010

Learning Similarity Matrix from Constraintsof Relational Neighbors

account the same number of relational neighbors even if
there is a lot of bias between the number of class members for a pairwise data. Although this may not become aproblem when a pairwise data is must-linked, it may be a
problem when the pair is cannot-linked because the probability of the member of a small class may be highly constrained, and then they may be included in the conflictedconstraints. Given this perspective, we need to create afunction that controls the number of relational neighbors
according to the size of a class that a constrained data pairbelongs.

[12] K. Fujisawa, M. Kojima, and K. Nakata, “Exploiting sparsity inprimal-dual interior-point methods for semidefinite programming,”
Mathematical Programming, Series B 79, pp. 235-253, 1997.
[13] I. S. Dhillon, “Co-clustering documents and words using bipartite
spectral graph partitioning,” In Proc. of the seventh ACM SIGKDD
Conf., pp. 269-274, 2001.

Name:

6. Conclusion

Masayuki Okabe

We proposed a method for 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
semidefinite programming. However, we impose additional constraints whereas the neighbors of constrained
pairwise data are also influenced by the constraints, i.e.,neighbors of a must-linked pair also become similar tothat pair, and the neighbors of a cannot-link pair also become dissimilar. Experimental results for several clustering tasks show that our approach is promising even though
we must test it on other test beds and analyze it in detail.
In future work, we plan to investigate the influence ofthe number of neighbors and develop how to control it,
and will try to find more effective constraints on the neighbors.

Affiliation:
Toyohashi University of Technology

Address:
1-1 Tenpaku, Toyohashi, Aichi 441-8580, Japan

Brief Biographical History:
2001- Researcher of JST at Kyoto University
2003- Research Associate, Toyohashi University of Technology

Main Works:• Information retrieval• Machine learning

Membership in Academic Societies:• The Japanese Society for Artificial Intelligence (JSAI)

References:[1] W. Wu, C. Yu, A. Doan, and W. Meng, “An interactive clusteringbased approach to integrating source query interfaces on the deep
Web,” In Proc. of the 2004 ACM SIGMOD Int. Conf. on Management of data, pp. 95-106, 2004.
[2] D. Lewis and W. Gale, “A sequential algorithm for training textclassifiers,” In Proc. of the Seventeenth ACM-SIGIR Conf., pp. 312, 1994.
[3] S. Basu, I. Davidson, and K. L. Wagstaff, “Constrained Clustering,”
CRC Press, 2008.
[4] O. Chapelle, B. Scholkopf, and A. Zien, “Semi-Supervised Learning,” The MIT Press, 2006.
[5] K. Wagstaff and S. Roger, “Constrained K-means Clustering with
Background Knowledge,” In Proc. of the 18th Int. Conf. on Machine
Learning, pp. 577-584, 2001.
[6] D. Klein, S. D. Kamvar, and C. D. Manning, “From Instance-level
Constraints to Space-Level Constraints: Making the Most of Prior
Knowledge in Data Clustering,” In Proc. of the 19th Int. Conf. on
Machine Learning, pp. 307-314, 2002.
[7] S. Shwartz, Y. Singer, and A. Y. Ng, “Online and Batch Learning ofPseudo-Metrics,” In Proc. of the 21st Int. Conf. on Machine Learning, pp. 94-101, 2004.
[8] J. Davis et al., “Information-Theoretic Metric Learning,” In Proc. ofthe 24th Int. Conf. on Machine Learning, pp. 209-216, 2007.
[9] W. Tang, H. Xiong, S. Zhong, and J. Wu, “Enhancing SemiSupervised Clustering: A Feature Projection Perspective,” In Proc.
of the 13th Int. Conf. on Knowledge Discovery and Data Mining,pp. 707-716, 2007.
[10] S. C. H. Hoi, R. Jin, and M. R. Lyu, “Learning Nonparametric Kernel Matrices from Pairwise Constraints,” In Proc. of the 24th Int.
Conf. on Machine Learning, pp. 361-368, 2007.
[11] Z. Li, J. Liu, and X. Tang, “Pairwise Constraint Propagation by
Semidefinite Programming for Semi-supervised Classification,” In
Proc, of the 25th Int. Conf. on Machine Learning, pp. 576-583,
2008.

Vol.14 No.4, 2010

Name:
Seiji Yamada

Affiliation:
National Institute of Informatics, the Graduate
University for Advanced Studies (SOKENDAI)

Address:
2-1-2 Hitotsubashi, Chiyoda, Tokyo 101-8430, Japan

Brief Biographical History:
1989- Research Associate, Osaka University
1991- Lecturer, Osaka University
1996- Associate Professor, Tokyo Institute of Technology
2002- Professor, National Institute of Informatics, SOKENDAI

Main Works:• Human-agent interaction• Intelligent interactive systems• Interactive machine learning

Membership in Academic Societies:• The Institute of Electrical and Electronics Engineers, Inc. (IEEE)• Association for the Advancement of Artificial Intelligence (AAAI)• The Japanese Society for Artificial Intelligence (JSAI)

Journal of Advanced Computational Intelligenceand Intelligent Informatics

407