World Automation Congress © 2010 TSI Press.

AN INTERACTIVE TOOL FOR CONSTRAINED CLUSTERINGMASAYUKI OKABE AND SEIJI YAMADA
Toyohashi University of Technology, Tempaku, Aichi, Japan
National Institute of Informatics, Chiyoda, Tokyo, Japan

ABSTRACT—This paper describes an interactive tool for constrained clustering that helps users toselect effective constraints efficiently during the clustering process. This tool has some functions
such as 2-dimensional visual arrangement of a data set and constraint assignment by mousemanipulation. Moreover, it can execute distance metric learning and k-medoids clustering. In thepaper, we show the overview of the tool and how it works, especially in the functions of display
arrangement by multi-dimensional scaling and incremental distance metric learning.
Keywords: visual interface, constrained clustering

1. INTRODUCTION
Constrained clustering is a promising approach for improving the accuracy of clustering by using someprior knowledge about data. As the prior knowledge, we generally use two types of simple constraints
about a pair of data. The first constraint is called “must-link”. It is a pair of data that must be in the samecluster. The second one is called “cannot-link”. It is a pair of data that cannot be in the same cluster. There
have been proposed several approaches to utilize these constraints so far. For example, a well-known
constrained clustering algorithm the COP-Kmeans proposed by Wagstaff [1] uses these constraints as
exceptional rules for the data allocation process in the k-means algorithm. A data may not be allocated tothe nearest cluster center if the data and a member of the cluster is a pair of cannot-link, or the data and amember of other cluster is a pair of must-link. Another researches [2,3,4] are based on the supervised
metric learning that utilize the constraints to modify an original distance (or similarity, kernel) matrix tosatisfy the target distance (or value) of each constraint. Hybrid method [5] is also proposed.
Although the use of constraints is an effective approach, we have some problems in preparing
constraints. One problem is the efficiency of the process. Because users are generally negative to themanual operation, i.e. labeling data pairs as “must-link” or “cannot-link”, we need a system to help userscut down the operation cost. The other problem is the effectiveness of the prepared constraints. Manyexperimental results in recent researches show clustering performance does not monotonically improve(sometimes decreases) as the number of applied constraints increases. The degree of performance
improvement relies on a set of constraints, namely the quality of constraints. These results indicate that
constraints are not all useful, some are effective but some are not effective or even harmful to the clustering.
We need a system to help users select only effective constraints that improve the clustering performance.
The second problem is much related to the active learning that has not been researched yet so far.
We approach these problems by developing an interactive tool that helps users to select effective
constraints efficiently during the clustering process. The main objectives of the tool can be sum up asfollows.
1.
2.

To provide an interactive environment in which users can visually recognize the proximity of data,and give constraints easily by mouse manipulation.
To provide hints for the better selection strategies through the interaction process between thesystem and users.

Besides 2-dimensional visual arrangement of a data set and constraint assignment function, our prototype
tool has distance metric learning and k-medoids clustering that can be executed as the background process.
Using these functions, users can compare the results of clustering before and after constraints addition. We
consider such interactions help to provide hints for the better selection strategies.
In the following sections, we first explain the overview of our tool in Section 2. Then we describe twomain functions of the tool - display arrangement by multi-dimensional scaling and incremental distancemetric learning, in Section 3 and 4. Finally we conclude in Section5.

2. OVERVIEW OF THE SYSTEM
In this section, we explain the process of interactive constrained clustering with our proposed tool.
Figure I shows the user interface (UI) of the tool, which consists of some buttons and display area for data
distribution. Each data is represented by a colored circle in the figure. Users can interactively selectadditional constraints and reflect them to update the clustering result through the UI. We briefly describe
the interaction process between a user and our tool.
1.
A user loads a data set to be clustered to our tool. Each data must be represented by a featurevector with pre-defined format. The tool calculates the initial distance matrix from the featurevector.
2.
The tool runs modules of clustering (k-medoids) and multi-dimensional scaling (MDS) [6] to get
the temporal clustering result and coordinates of the data set to display on the UI. We explain thedetails of MDS in the next section. Then the tool displays and colors the data on the UI according
to the coordinates calculated by MDS and temporal clustering result.
3.
If the user does not satisfy the clustering result, he/she can add constraints. The tool updates thedistance matrix using additional constraints. We describe the details of the update procedure inSection 4.
4.
Repeat step no.2 and no.3 until the user gets a satisfactory clustering result.
Users can select a pair of data to assign a constraint by clicking colored circles. In Figure I, two redcolored data with bold 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 the k-medoids algorithm for the clustering process. Since we only update thedistance matrix of a data set (do not calculate each data vector from the modified distance matrix), wecannot use the normal k-means algorithm that uses ad-hoc centroids. In k-medoids, k representative data iscalled medoids. They are used substitutes for centroids in k-means.
Most of the researches in constrained clustering use labeled data sets in their experiments and prepare
constraints at random. However, it is clear that random selection is much wasteful when human must
determine the labels of constraints. Our tool helps to reduce the 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 find better selection strategies.

Figure I. User Interface of the Tool

3. DATA ARRANGEMENT BY MULTI-DIMENSIONAL SCALING
In this section, we describe the method of data arrangement. When we apply clustering to a data set,we generally use a multi-dimensional feature vector to represent a data that cannot be displayed in our 2dimensional user interface. We need to display the proximity relationship that reflects the relation in theoriginal space. We use multi-dimensional scaling (MDS) [6] to realize such function in our tool. MDS is awell-known technique that calculates spatial arrangement from a distance (or similarity) matrix of a data set.
We do not need to care about the dimension of the feature vector. We do not need row data but only adistance matrix. This is very suitable for our environment as we describe in later sections. We describe abrief introduction of MDS in the following.
MDS is based on the eigen-decomposition that is a factorization technique of a square matrix. Let S isa square matrix and v is an eigen vector of S .

Sv = λv
λ is an eigen value corresponding to v . Then S can be factorized as€€€−1
S = VΛV€
where V is the square matrix whose columns are eigen vectors of S . Since we calculate S from asymmetric distance matrix€D , S is€also symmetric. Thus S can be factorized as€€€€ €S = VΛV T= VΛ1/ 2 Λ1/ 2V€T
€ 1/ 2= VΛ (VΛ1/ 2 )T€

1/ 2The row of VΛ is the coordinate of each data in MDS. Though we need only 2-dimensional coordinate,
we often need more dimensions to display a data set that has potentially more than 3 clusters. Thus wecalculate n-dimensional coordinate and display data using arbitrary combinations of two axes. Figure II(a)€and Figure II(b) shows the examples of such combinations. We used the “soybean-small” data set fromUCI repository [7] to make Figure II. Two clusters (purple and blue) are overlapping in Figure II(a), but are€
separated in Figure II(b).

S can be calculated from D that we repeatedly update though the interaction with our tool. Using
centering matrix Gn , S is calculated as€€€ €(a) Combination No.1(b) Combination No.2

Figure II. Examples of Data Arrangement (two combinations of two axises)

1
S = − Gn DGnT ,21Gn = In − 1n1tnnThe centering matrix can remove€the effect of the original point.

4. INCREMENTAL DISTANCE MATRIX LEARNING AND DEMONSTRATIONS€In this section, we describe an algorithm of distance learning adopted in our tool. This algorithm is
proposed by Jain et al. [8] and is based on the framework of online learning. It repeatedly updates thedistance matrix using constraints given through the interaction process described in Section 2. It requires
less computational cost than other techniques that need some optimization procedures. This advantage isvery desirable for our tool that needs quick reaction to users.
The algorithm is based on the problem of learning a Mahalanobis distance function. Given ndimensional vectors u and v, the squared Mahalanobis distance between them is defined 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 featurevectors. 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 to update dA (u,v) incrementally and proposed anonline algorithm that receives one constraint at a time. We briefly describe how they introduce the update€formula.
Let At be the distance matrix that is updated at t-th step, and (ut ,v t , y t ) be a €constrained data pairgiven at that time. Here y t is the target distance that€dA (u,v) must satisfy. If the data pair is must-link,y t is 0. If cannot-link, y t is 1. Jain et al. formalize an online learning problem to solve At +1 byintroducing a regularization function D(A, At ) and a loss function l(dA (ut ,v t ), y t ) .

€At +1 =€argmin{D(A, At ) + ηl(dA (ut ,v t ), y t )}

€€

A 0

€

€

−1−1
D(A, At ) = tr(AA€t ) − logdet(AAt ) − d€l(dA (ut ,v t ), y t ) = (dA (ut ,v t ) − y t ) 2€
that determines the degree of the influence of the constraint. In order toη is the regularization parameter
derive update formula analytically, dA (ut ,v t ) is approximated by dA t (ut ,v t ) . Though we omit the details€ the update distance matrix can be solved analytically.
of the introduction process,€€

ηy t yˆ t −1+ (ηy t yˆ t −1) 2 + 4ηyˆ t2
dA t +1 (ut ,v t ) =€2ηyˆ tyˆ = dA t (ut ,v t )Our tool can incrementally change the clustering result that is based on the distance matrix updated by€ III shows a series of cluster changes achieved by this incremental algorithm. The
the above formula. Figure
data set used in the Figure III is also the “soybean-small”. Two clusters (green and red) is slightly€ but are clearly separated in Figure III(b). Relationship between two clusters
overlapping in Figure III(a),(purple and blue) also changes from Figure III(b) to Figure III(c). The clusters in Figure III(d) seems to be
more condensed than Figure III(c). We can see the clusters are gradually separated as the distance learning
proceeds.

(a) Result at 1 step(b) Result at 5 step(c) Result at 10 step(d) Result at 15 step

Figure III. Results of Incremental Distance Learning

5. CONCLUSIONSThis paper presents an interactive tool for constrained clustering that provides some basic functions
such as the display of 2-dimensional visual arrangement of a data set, constraint assignment by mousemanipulation, 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 lesswork than the clustering process that uses randomly selected constraints. In addition, selection bias of theconstraints may help users find better selection strategies.
The tool described in this paper is still a prototype. We have much work to do. For example, displaying
data information is very important function because users determine the labels of constraints based on theinformation. However methods to display depends on the data type. We have to implement different
methods when displaying images and news articles. We also consider implementing the function of active

learning that is important but rarely explored research area. The function may help users, or users may
notice the drawback of the active learning algorithm.

REFERENCES
1.
2.
3.
4.
5.
6.
7.
8.

1

K. Wagstaff and S. Roger., “Constrained K-means Clustering with Background Knowledge,”
ICML’01, 2001, pp. 577-584.
D. Klein and et al., “From Instance-level Constraints to Space-level Constraints,” ICML’02, 2002,
pp. 307-314.
S. Hoi and et al., “Learning Nonparametric Kernel Matrices from Pairwise onstraints,” ICML’07,
2007, pp. 361-368.
Z. Li and et al., “Pairwise Constraint Propagation by Semi-definite Programming for Semisupervised Classification,” ICML’08, 2008, pp. 576-583.
S. Basu and et al., “A probabilistic Framework for Semi-Supervised Clustering,” KDD’04, 2004, pp.
59-68.
I. Borg and P. Groenen, “Modern multidimensional scaling,” Theory and applications, 1997.
A. Asunction and D. J. Newman, UCI Machine Learning Repository1. Irvine, CA: University ofCalifornia, School of Information and Computer Science, 2007.
P. Jain and et al., “Online metric learning and fast similarity search,” NIPS’08, 2008, pp. 761-768.

[http://www.ics.uci.edu/~mlearn/MLRepository.html]