Designing GUI for Human Active
Learning in Constrained Clustering
Abstract
Seiji Yamada
Masayuki Okabe
National Institute ofToyohashi University ofInformatics / SOKENDAI /Technology
Tokyo Institute of Technology 1-1 Hibarigaoka, Tempaku
2-1-2 Hitotsubashi, Chiyoda
Toyohashi, 441-8580 JapanTokyo, 101-8430 Japanokabe@imc.tut.ac.jp
seiji@nii.ac.jp

Junki Mizukami
Tokyo Institute of Technology
4259 Nagatsuta, MidoriYokohama, 226-8503 Japanmizukami@ntt.dis.titech.ac.jp

In this paper, a novel GUI for human active learning inconstrained clustering is described. Clustering is the mostpopular data mining technology, and in particular,interactive constrained clustering that uses constraints
from a human is promising for practical applications. We
propose a GUI that can expose the eﬀects of given
constraints by emphasizing them at the clustered results
and provide multiple viewpoints that a user can ﬂexibly
change to derive human active learning. We fully
implemented an interactive constrained clustering systemwith the GUI as a web service. We also conducted anevaluation experiment on image clustering withparticipants, and obtained results to support theeﬀectiveness of our approach.

IntroductionCopyright is held by the author/owner(s).
IUI 2013 Workshop on Interactive Machine Learning,
19 March, 2013, Santa Monica, CA USA.

Clustering is the most popular data mining technology,
and in particular, interactive constrained clustering thatuses constraints from a user is promising for practicalapplication. In interactive constrained clustering, a user
plays the role of a teacher to a constrained clusteringsystem [2] and gives must/cannot-links as constraints. In
such a situation, a user tries to select eﬀective constraints
and this human ability is called human active learning [4].
Furthermore, because a user’s cognitive load necessary togive constraints is well known to be signiﬁcantly restrictedand the maximum number of pairwise constraints was
about 50 in our experiment, we needed to prepare amechanism to support human active learning. Thus we
propose a GUI that can derive human active learning. The
GUI has two characteristics, exposing the eﬀects of thelast constraint given from a user and providing multi
viewpoints with which a user can easily ﬁnd an eﬀective
data-pair as a constraint.

learns from triaging decisions made by operators in a
dynamic environment. It also had visualizations to support
operators to quickly and accurately triage alarms. These
interactive machine learning systems basically dealt withtraining data for classiﬁcation learning, not constraints forconstrained clustering, and explicitly did not provide aninteraction design for deriving human active learning.

Designing a GUI for human active learning
Some constraints are not eﬀective [6] in constrained
clustering, and the cognitive load necessary for a user togive constraints is high in interactive clustering, thus weneed to provide a mechanism in which a user can easily
select only eﬀective constraints for an interactive
constrained clustering system. Since the constraints are
considered to be training data for classiﬁcation learning,
traditional computational active learning like uncertainty
sampling [11] and query by committee [13] might beuseful in non-interactive constrained clustering. Forinteractive constrained clustering, we should use humanactive learning [4].
As far as we know, popular data mining tools that include
Weka [9] do not provide an environment for interactive
constrained clustering and a suitable GUI for human activelearning. Interactive machine learning systems are closelyrelated to this work. Such systems provide a user interface
that supports a user in giving training data to the systems.
Fails et al. originally proposed an interactive machinelearning framework that supports the interactive trainingof pixel classiﬁers with a user for image segmentation [7].
CueFlik [8] also provided an end-user machine learning
environment in which users can easily create rules for
re-ranking images according to their visual characteristics.
It was implemented for web image searches. CuteT [1]was designed to use interactive machine learning thatWe made an interactive constrained clustering systemwith a GUI that can derive human active learning, andinvestigated its eﬀectiveness in performing clustering. Theinteractive constrained clustering system was implemented
on a web server by using MATLAB, Perl, and JavaScript,
and could run on a web browser. Figure 1 shows asnapshot of the interactive constrained clustering system’sUI. The system had the two following special functions forhuman active learning.
(b)

(a)

(c)
(4)
(d)

(e)

Figure 1: GUI for human active learning.

Figure 2: Exposing the eﬀects ofa given constraint.

Figure 3: Multiple-views
selection (Figure 1(e)).

• Exposing the eﬀects of given constraints: Theinteractive constrained clustering system can expose
data inﬂuenced by the last given constraint. We
expect this function to make a user recognize theeﬀects caused by his/her given constraint and to
derive human active learning. The inﬂuenced data
are identiﬁed by checking the change of a cluster towhich data belonged after every clustering, and areemphasized by being circled like in Figure 2.
• Multiple viewpoints for the results of clustering :The interactive constrained clustering systemenables a user to change viewpoints to see thedistribution of data. We used multi-dimensional
scaling [3] to show data in the 2D coordination, andprovided multiple viewpoints by preparing pairs ofeigenvalues as a 2D-coordination. In Figure 3, whichshows 1(e), a user can freely select a viewpoint bymouse clicking, and the data distribution with theselected viewpoint is updated as in Figure 1(a).
COP-Kmeans [14] was used in our interactive constrained
clustering system as a constrained clustering algorithm.
Another approach to constrained clustering ismetric/distance learning [10]. However, since it costs
much because it needs complicated optimization and theresponse is suﬃciently quick, we did not use it. The user
gives only must-links. The user selects a pair of data for amust-link by using a main window (a), a magnifying
window (b) and a selected data pair window (c), as shownin Figure 1. After the user determines a must-link in (d),the constrained clustering run and the data in (a) areupdated. This procedure is repeated.

Experiment
We conducted a within-subject experiment with 16
participants (12 males, 4 females, ages 18∼52). Twoconditions, a proposed GUI (p-GUI) and a traditional GUI
without the two functions (t-GUI), were prepared, andtheir ordering was counterbalanced. In each trial, aparticipant was asked to give 50 constraints one by one.
The data were image ﬁles generated from CALTECH 256
by using bag of features [5] with SIFT [12]. A data set ofthree clusters comprised of “motorcycles”, “laptop PCs”
and “starﬁshes” was prepared, and each cluster had about
50 pieces of image data.
We measured the number of constraints (must-links)
necessary to achieve normalized mutual information(NMI) = 1.0 and the maximum NMI for 50 constraints asan evaluation. The average number of constraints (theupper limit = 50) for the p-GUI and t-GUI was 35.9
(SD = 10.6) and 46.1 (SD = 10.3), and the average
maximum NMI was .97 (SD = .08) and .84 (SD = .13).
These results are shown in Figures 4 and 5. We applied at-test to them and found signiﬁcant diﬀerences between
the two levels in both evaluations (p = .007, .006). Theseresults supported the eﬀectiveness of our proposed GUI.
We also found that this human active learning**

60504030
20
100p-GUIt-GUI

Figure 4: Number of constraints to NMI = 1.0.

**
1
0.8
0.6
0.4
0.2
0p-GUIt-GUI

Figure 5: Maximum NMI for 50 constraints.

outperformed computational active learning withuncertain sampling-like heuristics.

Conclusion
We proposed a novel GUI for human active learning ininteractive constrained clustering. The GUI can expose theeﬀects of the last given constraint to a user so that he/shecan easily recognize the causality between constraints andclustering, and it can provide multiple viewpoints so thata user can quickly ﬁnd eﬀective data pairs as constraints.
We conducted experiments with image clustering by using
popular data sets to evaluate our proposed GUI. We
experimentally compared the proposed GUI with aconventional system without the GUI, and obtained
results to support the advantages of our proposed GUI.

References[1] S. Amershi, B. Lee, A. Kapoor, R. Mahajan, andB. Christian. Human-guided machine learning forfast and accurate network alarm triage. In IJCAI’11,pages 2564–2569, 2011.
[2] S. Basu, I. Davidson, and K. Wagstaﬀ, editors.
Constrained Clustering: Advances in Algorithms,
Theory, and Applications. Chapman and Hall/CRC,
2008.
[3] I. Borg and P. Groenen. Modern multidimensional

scaling: Theory and applications. Springer Verlag,
1997.
[4] R. M. Castro, C. Kalish, R. Nowak, R. Qian,
T. Rogers, and X. Zhu. Human active learning. In
NIPS’08, pages 241–248, 2008.
[5] G. Csurka, C. Dance, L. Fan, J. Willamowski, andC. Bray. Visual categorization with bags ofkeypoints. In Workshop on statistical learning incomputer vision, volume 1, page 22, 2004.
[6] I. Davidson. Two approaches to understanding whenconstraints help clustering. In KDD’12, pages
1312–1320, 2012.
[7] J. A. Fails and D. R. Olsen, Jr. Interactive machinelearning. In IUI’03, pages 39–45, 2003.
[8] J. Fogarty, D. Tan, A. Kapoor, and S. Winder.
Cueﬂik: interactive concept learning in image search.
In CHI’08, pages 29–38, 2008.
[9] M. Hall, E. Frank, G. Holmes, B. Pfahringer,P. Reutemann, and I. H. Witten. The weka data
mining software: an update. ACM SIGKDD
Explorations Newsletter, 11(1):10–18, 2009.
[10] P. Jain, B. Kulis, I. Dhillon, and K. Grauman. Online
metric learning and fast similarity search. In
NIPS’08, volume 22, pages 761–768, 2008.
[11] D. Lewis and W. Gale. A sequential algorithm fortraining text classiﬁers. In SIGIR’94, pages 3–12,
1994.
[12] D. Lowe. Distinctive image features fromscale-invariant keypoints. International journal ofcomputer vision, 60(2):91–110, 2004.
[13] H. S. Seung, M. Opper, and H. Sompolinsky. Queryby committee. In COLT’92, pages 287–294, 1992.
[14] K. Wagstaﬀ, C. Cardie, S. Rogers, and S. Schroedl.
Constrained k-means clustering with backgroundknowledge. In ICML’01, pages 577–584, 2001.