2013 Conference on Technologies and Applications of Artificial Intelligence

Uncertainty Sampling for Constrained Cluster Ensemble
Masayuki Okabe
Information and Media Center
Toyohashi University of Technology
Aichi, Japan
Email: okabe@imc.tut.ac.jp

Seiji Yamada
Digital Content and Media Sciences Research Division
National Institute of Informatics
Tokyo, Japan
Email: seiji@nii.ac.jp

users reduce such operation cost. The other problem is theeffectiveness of the prepared constraints. Many experimental
results in recent studies have shown clustering performancedoes not monotonically improve (sometimes deteriorates) as
the number of applied constraints increases. The degree of
performance improvement relies on the quality of constraints
rather than the amount. These results imply that constraints
are not all useful, some are effective but some are noteffective or even harmful to clustering. We also need support
to help users select only effective constraints that improveclustering performance. These problems can be resolved by
the framework of active learning that automatically selectsconstraint candidates expected to be useful.
In this paper, we propose an active learning method to select a data pair as a constraint candidate that is expected to be
useful if true constraint label (must/cannot-link) is given. We
realize an uncertainty sampling based active learning method
on a constrained cluster ensemble algorithm that integrates
a sequence of clustering results produced by constrained kmeans using boosting framework. The cluster ensemble isbased on a boosting [9] framework with a constrained kmeans algorithm. Controlling the priorities of constraints byboosting, the constrained k-means that is a modiﬁed version
of COP-Kmeans [10] produces the variation of clusteringresults by changing the data assignment order.
We exploits this variation to measure the uncertainty fora data pair to be must-link or cannot-link. It is well known
that “uncertainty” is one of major criteria for active learning[11] to select candidates of training data. This is generally
called uncertainty sampling [12]. In this research, we need
uncertain data pairs that are expected to be useful to improveclustering performance if they are used as constraints. We
calculate the uncertainty using two measurements. One is
the number that a data pair belongs to the same or different
cluster during cluster ensemble process. The other is thekernel value that is produce for a data pair by boostingprocess. We expect that constraints selected by using uncertainty sampling are more effective than constraints selected
at random.
The rest of this paper is organized as follows. We ﬁrst
introduce our basic constrained cluster ensemble algorithmwith boosting and constrained k-means in Section II. Then

Abstract—Constrained Clustering is a framework of improving clustering performance by using a set of constraints
about data pairs. Since performance of constrained clustering
depends on a set of constraints to use, we need a method toselect good constraints that are expected to promote clustering
performance. In this paper, we propose such a method, which
actively selects data pairs to be constrained by using varianceof clustering iteration. This method consists of a boosting
based cluster ensemble algorithm that integrates a set ofclusters produced by a constrained k-means with controlled
data assignment order. Experimental results show that our
method outperforms clustering with random sampling method.
Keywords-active learning; constrained clustering; uncertainty sampling; cluster ensemble;

I. I NTRODUCTION
Clustering is a basic data mining technique to ﬁnd similar
data groups in a dataset. We can execute clustering algorithms by giving feature vectors and a similarity measure.
However, it sometimes happens that similarity measure does
not ﬁt the target dataset and get unsatisﬁed results.
Constrained clustering [1], [2] can be applied to such asituation. It is a kind of semi-supervised learning techniquethat utilizes labeled and unlabeled data to enhance learning
performance. Constrained clustering is different from normal
clustering in the use of background knowledge that is givenin the form of constraints about data pairs. Such constraints
have two kinds, usually called must-link and cannot-link
constraints. The former is constraints about data pairs thatmust be in a same cluster, while the latter ones is aboutdata pairs that must be in different clusters. According to thisframework, users can modify or ﬁx the problem of pre-given
similarity measure by giving such constraints. For example,
interactive image segmentation [3], [4] is a typical task
for constrained clustering. Depending on the segmentation
performance, users can give appropriate constraints to getbetter results.
Although there have been proposed several constrained
clustering methods [5], [6], [7], [8], we have some problems
in preparing constraints. One problem is the efﬁciencyof the process. Because constraints must be labeled as“must-link” or “cannot-link” manually by human, his/her
cognitive cost seems very high. We need support to help
978-1-4799-2528-5/13 $31.00 © 2013 IEEE
DOI 10.1109/.56

258
257

  



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

 






 



Constrained Cluster Ensemble 

Figure 1.

 







 








            



    





we propose our uncertainty sampling based active learning
method for constrained clustering in Section III. Section
IV presents the results of the experiments on six datasetsfrom UCI repository and public shape datasets. We ﬁnallyconclude our work in Section V.

Figure 2.

Constrained K-means

same cluster. Thus, the kernel matrix represents the linkconnections of the clusters. From the point of a weaklearner, the constrained k-means predicts the existence ofthe link between any data pair in the clusters using theconstraints as a set of training data. The kernel matrix is anaggregation of these predictions. As boosting step goes on,
constrained k-means produces different clustering results.
They are ﬁnally summed up as a kernel matrix with theirimportance values αt that are calculated by using the error
rate of the constraints satisfaction in each boosting step. The
ﬁnal clustering result is generated using this ﬁnal kernel
matrix.
Another important role of the boosting framework is to
give a priority wnt to each constraint. The priority wnt+1 fornth constraint at t + 1th boosting step is calculated by thefollowing formula.

II. C ONSTRAINED C LUSTER E NSEMBLE
In this section, we brieﬂy explain a constrained clustering
algorithm on which we consider active learning.
The constrained clustering algorithm is based on a cluster
ensemble approach, where a certain number of slightly or
signiﬁcantly different clustering results are integrated into
a set of clusters. One of the important things in cluster
ensemble is how to create such difference. While there are somany mechanisms to produce different patterns of clustering,
we adopt a boosting based method [13] that is appropriate
for our “constrained” cluster ensemble.
This method is based on a boosting technique and aconstrained k-means algorithm. Boosting is one of theensemble learning techniques used to produce a classiﬁer
by integrating weak hypotheses generated by a weak learnerthat outperforms random classiﬁers to some extent. The
boosting process mainly follows the AdaBoost algorithm[9],which is a well-known framework to enhance the classiﬁer
ability by ﬂexibly changing the weights of the training
data. Figure 1 illustrates how our clustering algorithm works
according to the AdaBoost procedure. Although we normallyuse boosting for classiﬁcation learning that is different fromconstrained clustering, we can naturally apply by ﬁnding
correspondences as follows.
• Weak Learner → Constrained k-means• Training data → Constraints (must/cannot-link)• Weights for training data → Weights for constraints.
Once given a set of constraints, the constrained k-means
algorithm that works as a weak learner for the boostingruns and produces a clustering result. The clustering result
produced in each boosting step is transformed into a kernel
matrix K t . Each element of this kernel matrix indicates
whether or not the corresponding data pair belongs to thewnt+1 = wnt exp(−αt yn K t (in , jn ))where yn is the label for nth constraint and K t (in , jn )) is thekernel value for nth constraint. The constraints that are notsatisﬁed by the weak learner will be given higher priorities
in order to be satisﬁed in the next round. These priorities areused to control the data assignment order in the constrained
k-means. The constraints with higher priorities will besatisﬁed earlier than those with low priorities. The priority
calculation can be dealt with by changing the coefﬁcients of
the loss function in the boosting.
Figure 2 illustrates how constrained k-means uses thepriorities for constraints. The constrained k-means algorithm
is developed from the COP-Kmeans [10] by modifying
to make work as a weak learner for constrained cluster
ensemble. Although it follows the basic procedure of thestandard k-means algorithm that assigns data to its nearest
cluster center, its assignment process is rather complicatedsince we must consider the weight of constraints. There are

258
259

      

























    








 



















 











   





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

Figure 3.

Variability of the Clustering Results

produced during the boosting process.
The ﬁrst criteria is the variability of the number that adata pair belong to the same or different cluster during theboosting process. As illustrated in Figure 3, the constrained
clustering algorithm introduced in previous section produces
a variety of clusters. It may occur that a data pair belongs
to the same cluster in a boosting step, but they do not in
another step. In this way, we can calculate probabilities thata data pair belongs to the same cluster or not from theboosting process. We measure the variability by calculating
the entropy for each data pair according to the probabilities
and use it as the ﬁrst criteria of “uncertainty” to selectconstraint candidates for future clustering. Let (xi , xj ) bea data pair and pij be a probability that they belongs toa same cluster. We can calculate an entropy Eij for each(xi , xj ) as follows.

mainly two parts to the assignment processes, which consistsof the procedure for the constrained and unconstrained data,
respectively. The latter one (for the unconstrained data)remains the same as that in a normal k-means process.
What we need to consider is the process for the previous
one (for constrained data). We must take several cases likethose listed below into consideration. Our algorithm assigns
a constrained data pair at the same time. Since some datacontain several constraints, one (or both) of the data may
have already been assigned in some cases. We must prepare
procedures for such situations. Depending on the conditions,
we must prepare different procedures according to whichconstraint the data pair has.
III. U NCERTAINTY S AMPLING FOR C ONSTRAINEDC LUSTER E NSEMBLE
Based on the constrained cluster ensemble algorithm, weconsider active learning that tries to infer the most promising
constraint in terms of improving clustering performance thebest. In this section, we propose an active learning techniquethat is based on the uncertainty sampling [12]. Uncertainty
sampling is based on a hypothesis that we should label thedata which is the most difﬁcult to infer. According to the
hypothesis, we should label the data pair that is the most
difﬁcult to infer that it is must or cannot-link. In order
to apply uncertainty sampling, we ﬁrst have to decide thecriteria to quantify “uncertainty”. Our criteria is based on
two types of variability of the clustering results that are

Eij = −pij log pij − (1 − pij ) log(1 − pij )(1)Here, pij can be estimated from the number of occurrence
that (xi , xj ) belongs to the same cluster during boosting
steps 1 ∼ T . Once we can calculate entropies, we selectseveral data pairs that has higher values as constraint candidates and give them constraint labels (must/cannot-link). We
consider a data pair that has high entropy value to be a goodcandidate since its constraint label is difﬁcult to predict.
The second criteria is the variability of the ﬁnal kernel
value that is produced for a data pair in each boosting step.
As we described before, clustering results are transformed

259
260

and integrated into a kernel matrix whose element indicatesthe strength of the corresponding data pair is a must or
cannot-link. Thus if the kernel value is positively large, we
can infer it is must-link. In the same way, if the kernel
value is negatively large, we can infer it is cannot-link. On
the other hand, we can also consider whether a data pairis must or cannot-link is uncertain if the absolute kernel
value is small. Since the ﬁnal kernel value is the sum of
positive and negative values produced during each boosting
step, smallness of the absolute kernel value can be used asa measurement of “uncertainty”.
Using above two types of measurement, we calculate thevalue of uncertainty U as follows.
Uij = Eij /Kij

Table IDATASETS

Iris
Glass
Ecoli
Wdbc
PathbasedSpiralNo. of Class
3
6
8
2
3
3

No. of Attribute
4
10
7
30
2
2

show the average score in a similar way as our active
method.
We used normalized mutual information (NMI) to measure the clustering accuracy. The NMI was calculated byusing the following formula.

(2)

where i and j means each index of a data pair, and K is akernel matrix. We calculate Uij for any unlabeled data pairand select a data pair that has the largest value.

NMI(C, T ) =I(C, T )
H(C)H(T )where C is the set of cluster labels returned by algorithms
and T is the set of true cluster labels. I(C, T ) is the mutual
information between C and T , and H(C) and H(T ) are theentropies.

IV. E XPERIMENTS
A. Datasets
We evaluated our proposed method on six datasets. The
datasets are summarized in Table I. Iris, Glass, Ecoli, Wdbc
are from the UCI repository1 and Pathbased and Spiral arefrom a public shape datasets for clustering 2 . We rescaled
the range of attribute values of each data 3 in four datasetsfrom UCI repository to avoid negative effect of attribute
scale unbalance. For two shape datasets, we applied RBF
kernel with local scaling[14] because they are difﬁcult to
be clustered in Euclidean space. We set 8 to the number ofnearest neighbors for local scaling.

C. Results
Figure 4 shows the results of the datasets. In each graph,horizontal axis indicates the number of constraints used forconstrained cluster ensemble, and vertical axis indicates the
NMI value.
As for UCI datasets, ACTIVE outperforms RANDOM
on Iris and Glass datasets. In Glass, the difference of
NMI expands as the number of constraints increases. For
other two datasets Ecoli and Wdbc, ACTIVE shows almost
comparable results even if it gets more constraints. Shapedatasets also showed similar results. ACTIVE is better thanRANDOM on Pathbased, but comparable on Spiral.

B. Methods and Evaluation
We compared the following methods for constraint sampling.
• ACTIVE: This is our proposed method, which selects
data pairs to be labeled using two types of “uncertainty”
measurement described in the previous section. Ouralgorithm starts from 100 (randomly selected) source
constraints and repeats uncertainty sampling until itgets 200 constraints. Since constrained clustering algorithms generally need a certain number of constraints
to produce their effect, we starts from 100 souce
constraints. In each sampling step, it selects one data
pair to be labeled. We repeated this sampling process
and show the average score as the ﬁnal results. The
number of maximum boosting steps T was set to 100.
• RANDOM: This method randomly selects data pairs
to be labeled. We repeated the sampling process and

V. C ONCLUSION
In this paper, we proposed an active learning method forconstrained clustering, which actively selects data pairs to
be constrained. Our active learning method is a realizationof uncertainty sampling on a constrained cluster ensemble
algorithm that integrates a sequence of clustering results
produced by constrained k-means using boosting framework.
We utilize the variability of the clustering results throughthe cluster ensemble process to measure the uncertainty forany data pair to be must or cannot-link. The uncertainty is
calculated by using two measurements. One is the numberthat a data pair belongs to the same or different cluster during
cluster ensemble process. The other is the kernel value thatis produce for a data pair by boosting process.
Experimental results showed that our method outperforms
or is comparable to a random sampling method on six
datasets. Though the effectiveness depends on data and basic
performance of our cluster ensemble method, we veriﬁed

1 http://archive.ics.uci.edu/ml/
2 http://cs.joensuu.ﬁ/sipu/datasets/
3 v =

No. of Data
150
214
336
569
300
312

v−min{v}(v  : rescaled attribute value)max{v}−min{v}

260
261

1

1

ACTIVERANDOM

0.8

0.6

NMI

NMI

0.8

ACTIVE

0.6

RANDOM
0.4

0.4

0.2

0.2

0
100

110

120

130

140 150 160
No. of constraints

170

180

190

0
100

200

110

120

130

(a) Iris1

140 150 160
No. of constraints

1

ACTIVE

0.6

0.6

NMI

NMI

0.8

0.4

0.4

0.2

0.2

120

130

140 150 160
No. of constraints

170

180

190

0
100

200

110

120

130

140 150 160
No. of constraints

1

ACTIVE

0.6

0.6

NMI

NMI

0.8

0.4

0.4

0.2

0.2

120

130

140 150 160
No. of constraints

180

190

200

190

200

ACTIVERANDOM

0.8

110

170

(d) Wdbc

RANDOM

0100

200

ACTIVE(c) Ecoli

1

190

RANDOM

0.8

110

180

(b) Glass

RANDOM

0
100

170

170

180

190

0
100

200

110

120

130

140 150 160
No. of constraints

170

180

(f) Spiral(e) Pathbased
Figure 4.

Resultsother datasets.

uncertainty sampling approach has potential to work wellon some datasets.

R EFERENCES

Since active learning for constrained clustering has notbeen well developed, our method can be an option. We will
investigate the behavior of the method and test it on many[1] O. Chapelle, B. Scholkopf, and A. Zien, Semi-Supervised
Learning. The MIT Press, 2006.

261
262

[2] S. Basu, I. Davidson, and K. L.Wagstaff, Eds., Constrained
Clustering. CRC Press, 2008.
[3] C. Rother, V. Kolmogorov, and A. Blake, “Grabcut: Interactive foreground extraction using iterated graph cuts,” in ACM
Transactions on Graphics (TOG), vol. 1, no. 212, 2004, pp.
309–314.
[4] Y. Boykov and M. Jolly, “Interactive graph cuts for optimal
boundary & region segmentation of objects in ND images,”in ICCV, no. July, 2001, pp. 105–112.
[5] W. Tang, H. Xiong, S. Zhong, and J. Wu, “Enhancing semisupervised clustering: A feature projection perspective,” in
KDD, 2007, pp. 707–716.
[6] Q. Xu, M. desJardins, and K. L. Wagstaff, “Active constrained clustering by examining spectral eigenvectors,” inProceedings of the 8th International Conference on Discovery
Science, 2005, pp. 294–307.
[7] S. C. H. Hoi, R. Jin, and M. R. Lyu, “Learning nonparametrickernel matrices from pairwise constraints,” in ICML, 2007,
pp. 361–368.
[8] L. Wu, R. Jin, S. C. H. Hoi, J. Zhu, and N. Yu, “Learning
bregman distance functions and its application for semisupervised clustering,” in NIPS, 2009, pp. 2089–2097.
[9] Y. Freund and R. E. Schapire, “A decision-theoretic generalization of on-line learning and an application to boosting,” in
EuroCOLT, 1995, pp. 23–37.
[10] K. Wagstaff and S. Roger, “Constrained k-means clusteringwith background knowledge,” in ICML, 2001, pp. 577–584.
[11] S. Basu, A. Banjeree, E. Mooney, A. Banerjee, and R. J.
Mooney, “Active semi-supervision for pairwise constrained
clustering,” in SDM, 2004, pp. 333–344.
[12] D. Lewis and W. Gale, “A sequential algorithm for training
text classiﬁers,” in SIGIR, 1994, pp. 3–12.
[13] M. Okabe and S. Yamada, “Clustering by learning constraints
priorities,” in ICDM, 2012, pp. 1050–1055.
[14] P. Perona and L. Zelnik-Manor, “Self-Tuning Spectral Clustering,” in Advances in Neural Information Processing Systems 17, vol. 2, 2005, pp. 1601–1608.

262
263