SCIS & ISIS 2010, Dec. 8-12, 2010, Okayama Convention Center, Okayama, Japan

Constrained Clustering with Interactive Similarity
Learning
Masayuki Okabe

Seiji Yamada

Toyohashi University of Technology
Tenpaku 1-1, Toyohashi, Aichi, Japanokabe@imc.tut.ac.jp

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

Abstract—This paper describes an interactive tool for constrained clustering that helps users to select effective constraints
efficiently during the constrained clustering process. This tool
has some functions such as 2-D visual arrangement of a data set
and constraint assignment by mouse manipulation. Moreover, it
can execute distance metric learning and k-medoids clustering.
In this paper, we show the overview of the tool and how it works,
especially in the functions of display arrangement by multidimensional scaling and incremental distance metric learning.
Eventually we show a preliminary experiment in which humanheuristics found through our GUI improve the clustering.

I. I NTRODUCTION
Constrained clustering is a promising approach for improving the accuracy of clustering by using some prior knowledge
about data. As the prior knowledge, we generally use two typesof simple constraints about a pair of data. The first constraint
is called “must-link” which is a pair of data that must be in thesame cluster. The second one is called “cannot-link” which is apair of data that must be in different clusters. There have been
proposed several approaches to utilize these constraints so far.
For example, a well-known constrained clustering algorithm
the COP-Kmeans [1] uses these constraints as exceptionalrules for the data allocation process in a k-means algorithm.
A data may not be allocated to the nearest cluster center if
the data and a member of the cluster form a cannot-link, or
the data and a member of the other cluster form a must-link.
Another studies [2], [3], [4] are based on supervised metriclearning that utilizes the constraints to modify an original
distance (or called “similarity”, “kernel”) matrix to satisfy thetarget distance or value of each constraint. Also hybrid method[5], [?] is proposed.
Although the use of constraints is an effective approach, wehave some problems in preparing constraints. One problem isthe efficiency of the process. Because a human user generally
needs to label many constraints with “must-link” or “cannotlink”, his/her cognitive cost seems very high. Thus we needan interactive system to help users cut down such an operation
cost. The other problem is the effectiveness of the prepared
constraints. Many experimental results in recent studies haveshown clustering performance does not monotonically improve(sometimes deteriorates) as the number of applied constraints
increases. The degree of performance improvement relies on
the quality of constraints, not the amount. These results imply
that constraints are not all useful, some are effective but

some are not effective or even harmful to the clustering.
We also need an interactive system to help users select only
effective constraints that improve the clustering performance.
The second problem is much related to active learning that has
not been researched much in the field of constrained clusteringso far.
We approach these problems by developing an interactive
tool that helps users to select effective constraints efficiently
during clustering process. The main objectives to build theinteractive tool can be sum up as follows.
1) To provide an interactive environment in which users
can visually recognize the proximity of data, and give
constraints easily by mouse manipulation.
2) To provide hints for the better selection strategies
through the interaction process between the interactive
system and users.
Besides 2-D visual arrangement of a data set and constraint
assignment function, our prototype tool has distance metriclearning and k-medoids clustering that can be quickly executed
as the background process. Using these functions, users cancompare the results of clustering before and after constraints
addition easily. We consider such interactions help to provide
hints for the better selection strategies.
II. OVERVIEW OF THE S YSTEM
In this section, we explain the process of interactive constrained clustering with our proposed tool. Figure 1 shows GUI(Graphical User Interface) of the tool, which consists of somebuttons and a 2-D display area to visualize data distribution.
Each data is represented by a colored circle in the 2-D display
area. Users can interactively select additional constraints andreflect them to update the clustering result through the GUI.
We briefly describe the interaction process between a user andour tool in the following.
1) A user loads a data set to be clustered to our tool. Eachdata must be represented by a feature vector with predefined format. The tool calculates the initial distancematrix from the feature vectors.
2) The tool runs modules of clustering (k-medoids) andmulti-dimensional scaling (MDS) [6] to get the temporalclustering result and coordinates of the data set todisplay on the GUI. We explain the details of MDS

1295

Fig. 1.

Graphical User Interface

in the next section. Then the tool displays and colors
the data on the GUI according to the 2-D coordinates
calculated by MDS and temporal clustering result.
3) If a user does not satisfy the clustering results, he/she
can add constraints. The tool updates the distance matrix
according to additional constraints. We describe thedetails of this update procedure in Section 4.
4) Repeat step 2 and step 3 until the user satisfies theclustering results.
Users can select a pair of data to assign a constraint byclicking colored circles. In Figure 1, two red colored data withbold black circle are selected data. After selecting data, users
can assign a constraint to it by clicking “must” or “cannot”
button. Then they update distance matrix and re-clustering by
clicking “update” button. We use a k-medoids algorithm for aclustering process. Since we only update the distance matrix
of a data set, not calculate each data vector from the modified
distance matrix, we cannot use a normal k-means algorithm
that uses ad-hoc centroids. In k-medoids, k representative datais called medoids and they are used substitutes for centroids
in k-means.
Most of the studies in constrained clustering use labeled data
sets in their experiments and prepare constraints at random.
However, it is clear that random selection is very wasteful for ahuman user when he/she needs to determine many labels. Our
tool reduces such labeling cost. In addition, we have selection
bias for the constraints because we can recognize the proximity
relation between data. This functionality may help users to findbetter selection strategies.

III. DATA A RRANGEMENT BY M ULTI -D IMENSIONALS CALING
In this section, we describe a method of data arrangement.
When we apply clustering to a data set, we generally use
a high-dimensional feature vector to represent a data thatcannot be displayed in our 2-D GUI. We need to display
proximity relationships that reflects relations in the original
space. We use multi-dimensional scaling (MDS) [6] to realize
such 2-D visualization in our tool. MDS is a well-known
technique that calculates spatial arrangement from a distance(or similarity) matrix of a data set. It does not need to careabout the dimension of the feature vector, and also does notneed row data but only a distance matrix. These advantagesof MDS are very suitable for our environment as we describe
in later sections. We describe a brief introduction of MDS in
the following.
MDS is based on the eigen-decomposition that is a factorization technique of a square matrix. Let S is a square matrix
and v is an eigen vector of S.
Sv = λv
λ is an eigen value corresponding to v. Then S can befactorized as
S = V ΛV −1
where V is the square matrix whose columns are eigen vectorsof S. Since we calculate S from a symmetric distance matrix

1296

(a) Combination No.1

Fig. 2.

(b) Combination No.2

Examples of Data Arrangement (two combinations of two axises)

D, S is also symmetric. Thus S can be factorized asS= V ΛV T(1)= V Λ1/2 Λ1/2 V T= V Λ1/2 (V Λ1/2 )T

(2)
(3)

The row of V Λ1/2 is the coordinate of each data in MDS.
Though we need only 2-D coordinate, we often need moredimensions to display a data set that has potentially more than
three clusters. Thus we calculate n-D coordinate and display
data based on arbitrary combinations of two axes. Figure 2(a)and Figure 2(b) shows the examples of such combinations. We
used a “soybean-small” data set from UCI repository [7] for
Figure 2. Two clusters (purple and blue) are overlapping in
Figure 2(a), but are separated in Figure 2(b) because the pairsof axes are different.
S can be calculated from D that we repeatedly update
though the interaction with our tool. Using a centering matrix
Gn , S is calculated as
1
S = Gn DGTn ,21
Gn = In − 1n 10n
n
The centering matrix can remove the effect of the original
point.
IV. A LGORITHM FOR I NCREMENTAL L EARNING OF
D ISTANCE M ATRIX

repeatedly updates the distance matrix according to constraints
given through an interaction process described in Section
2. It requires less computational cost than other constrained
clustering techniques that need some optimization procedures.
This advantage is very desirable for our tool because it
needs quick responses in indicating updated results with given
constraints to users.
The algorithm is based on the problem of learning a
Mahalanobis distance function. Given n-dimensional vectors
u and v, the squared Mahalanobis distance between them isdefined asdA (u, v) = (u − v)T A(u − v)
where A is initially the unit matrix and thus dA (u, v) is
initially the Euclid distance between feature vectors. The
objective of the learning is to get a semi-definite matrix A that
produces desirable dA (u, v) for the constrained data pairs. Jain
et al. considered a method to update incrementally dA (u, v)
and proposed an online algorithm that receives one constraint
at a time [8]. We briefly describe how they introduced the
update formula.
Let At be the distance matrix that is updated at t-th step,and (ut , vt , yt ) be a constrained data pair given at that time.
Here yt is the target distance that dA (u, v) must satisfy. If thedata pair is must-link, yt is 0. If it is a cannot-link, yt is 1.
Jain et al. formalize an online learning problem to solve At+1
by introducing a regularization function D(A, At ) and a loss
function l(dA (ut , vt ), yt ) like the following.

In this section, we describe an algorithm of distance learning
adopted in our tool. This algorithm is proposed by Jain etal. [8] and is based on a framework of online learning. It

1297

At+1 = arg min D(A, At ) + ηl(dA (ut , vt ), yt )A0

−1
D(A, At ) = tr(AA−1t ) − log det(AAt ) − d(a) Result at 1 step(b) Result at 5 step(c) Result at 10 step(d) Result at 15 step

Fig. 3.

Results of Incremental Distance Learningl(dA (ut , vt ), yt ) = (dA (ut , vt ) − yt )2

distance matrix can be solved analytically.
√ηyt ŷt − 1 + (ηyt ŷt − 1)2 + 4η ŷt2
dAt+1 (ut , vt ) =2η ŷtη is a regularization parameter that determines the degree of
constraint’s influence. In order to derive update formula analytically, dA (ut , vt ) is approximated by dAt (ut , vt ). Though
we omit the details of the introduction process, the updateŷt = dAt (ut , vt )Our tool can incrementally change the clustering result
based on the distance matrix updated by the above formula.

1298

)$

($

!"(#$
!"'%$

!"($
!"'#$

!"'$

;<=

;<=

!"'$
!"&%$

-./01$
20134/$

!"&$

!"&#$

-./01$!"&$

20134/$

!"%#$
!"%$

!"#%$

!"##$
!"#$

!"#$
($ )$ *$ +$ %$ ,$ #$ &$ '$ (!$(($()$(*$(+$(%$(,$(#$(&$('$)!$)$ *$ +$ ,$ #$ %$ &$ '$ ($ )!$))$)*$)+$),$)#$)%$)&$)'$)($*!$

5$46$7418920:198

5$46$7418920:198(a) Soybean-small(b) Iris
Fig. 4.

Evaluation of Simple Selection Heuristics

Figure 3 shows a series of cluster changes achieved by thisincremental algorithm. The data set used in the Figure 3 is also
the “soybean-small”. Two clusters (green and red) is slightly
overlapping in Figure 3(a), but are clearly separated in Figure3(b). Relationship between two clusters (purple and blue) alsochanges from Figure 3(b) to Figure 3(c). The clusters in Figure
3(d) seems to be more condensed than Figure 3(c). We cansee the clusters are gradually separated as the distance learning
proceeds.
V. P RELIMINARY E XPERIMENTS - E VALUATION OF
S IMPLE S ELECTION H EURISTICS
We have developed a prototype of this tool. Through thetest interactions with this tool, we found by chance a simple
heuristics for selecting better constraints. The heuristics is,
1. to select a large cluster that may be unseparated fromother clusters, 2. to find a must-link pair being apart as far as
possible in the cluster. We compared the performance of thisheuristics with random selection. Figure 4 shows the results,
in which each axis means the number of constrains used inclustering and NMI (Normal Mutual Information) as evaluation measure. We used two data sets “Soybean-small” and“Iris” from UCI repository. In both data sets, selection withabove heuristics by a human outperforms random selection,
especially in early selection.
Although we need more experiments on various data sets,
it is very interesting that heuristics found by human intuition
works well in two data sets. This type of research is much
related to “human active learning”[9]. Different from theirexperiments, our interest exists in “human sampling”, where
human only selects training examples and learning itself isdone by machine. We consider this is more important to put
machine learning to practical.
VI. C ONCLUSION
This paper presented an interactive tool for constrained clustering that provides some basic functions such as the display of
2-D visual arrangement of a data set, constraint assignment bymouse manipulation, incremental learning of distance matrix
and clustering by k-medoids. These functions helps users

intervene the process of constrained clustering and finally
get the satisfied clustering result with less user’s cognitive
load than that for clustering process under randomly selected
constraints. In addition, selection bias of the constraints mayhelp users find better selection strategies.
The tool described in this paper is still a preliminary
prototype. We have much work to do. For example, displaying
data information is a very important function because users
determine the labels of constraints based on the information.
However a methods to display them depends on their data type.
We need to implement different methods when displaying
images data and document data. We also consider implementing the function of active learning that is important but
rarely explored in constrained clustering, especially interactive
constrained clustering. We think the active learning function
may help users, or users may notice the drawback of the active
learning algorithm.
R EFERENCES[1] K. Wagstaff and S. Roger, “Constrained k-means clustering with background knowledge,” in In Proceedings of the 18th International Conference on Machine Learning, 2001, pp. 577–0584.
[2] 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 In Proceedings of the 19th International Conference
on Machine Learning, 2002, pp. 307–314.
[3] S. C. H. Hoi, R. Jin, and M. R. Lyu, “Learning nonparametric kernel
matrices from pairwise constraints,” in ICML ’07: Proceedings of the24th international conference on Machine learning. New York, NY,
USA: ACM, 2007, pp. 361–368.
[4] Z. Li, J. Liu, and X. Tang, “Pairwise constraint propagation by semidefinite programming for semi-supervised classification,” in ICML ’08:
Proceedings of the 25th international conference on Machine learning.
New York, NY, USA: ACM, 2008, pp. 576–583.
[5] S. Basu, M. Bilenko, and R. Mooney, “A probabilistic framework forsemi-supervised clustering,” in Proceedings of the tenth ACM SIGKDD
international conference on Knowledge discovery and data mining.
ACM, 2004, pp. 59–68.
[6] I. Borg and P. Groenen, Modern multidimensional scaling: Theory andapplications. Springer Verlag, 1997.
[7] A. Asuncion and D. Newman, “UCI machine learning repository,” 2007.
[8] P. Jain, B. Kulis, I. S. Dhillon, and K. Grauman, “Online metric learningand fast similarity search,” in In Proceedings of Twenty-Second Annual
Conference on Neural Information Processing Systems, 2008, pp. 761–
768.

1299

[9] R. Castro, C. Kalish, R. Nowak, R. Qian, T. Rogers, and X. Zhu, “Humanactive learning,” Advances in Neural Information Processing Systems(NIPS), vol. 22, 2008.

1300