SCIS-ISIS 2012, Kobe, Japan, November 20-24, 2012

Active Sampling for Constrained Clustering
Masayuki Okabe

Seiji Yamada

Information and Media Center
Toyohashi University of Technology
Email: okabe@imc.tut.ac.jp

National Institute of Informatics
Email: seiji@nii.ac.jp

Abstract—Constrained Clustering is a framework of improving
clustering performance by using supervised information, which is
generally a set of constraints about data pairs. Since performanceof constrained clustering depends on a set of constraints to use,
we need a method to select good constraints that are expected
to promote clustering performance. In this paper, we propose
such a method, which actively select data pairs to be constrainedby using variance of clustering iteration. This method consistsof a bagging based cluster ensemble algorithm that integrates a
set of clusters produced by a constrained k-means with random
ordered data assignment. Experimental results show that our
method outperforms clustering with random sampling method.

I. I NTRODUCTION
Constrained clustering[1], [2] is a kind of semi-supervised
learning technique that utilizes labeled and unlabeled data
to enhance learning performance. Difference from normal
clustering is the use of background knowledge, which 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. The challenge of
constrained clustering to develop utilization methods of such
constraints. Some researches proposed to use them in the kmeans algorithm as knowledge for assigning data to cluster
centers, and some others proposed to use them as constraints
for an optimization problem [3].
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 constraints must belabeled as “must-link” or “cannot-link” manually by human,
his/her cognitive cost seems very high. We need support
to help users cut down such an operation cost. The otherproblem is the effectiveness of the prepared constraints. Manyexperimental results in recent studies have shown 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 needsupport to help users select only effective constraints that
improve the clustering performance. These problems can be
resolved by the framework of active learning that automaticallyselects constraint candidates expected to be useful.

978-1-4673-2743-5/12/$31.00 ©2012 IEEE

We propose an active sampling 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 for it. Our method
is based on a bagging[4] based cluster ensemble techniqueand a constrained k-means with random data assignment
order. This is a realization of cluster ensemble frameworkthat exploits partially coherent data group from clustering
iteration and integrates them into a set of final clusters. Cluster
variation can be created by changing data assignment order ina constrained k-means algorithm that is a modified version of
COP-Kmeans proposed by Wagstaff[5]. Though original COPKmeans algorithm tends to create inconsistent clusters because
the results heavily depends on its data assignment order thatis generally undecidable, we use such behavior to produce
diversity for cluster ensemble.
Once we can produce diversity of clusters, we can measure
uncertainty of belongingness of each data pair. Here, belongingness means whether a data pair belongs to a same or not
and we can measure such uncertainty by using entropy thatis calculated from the probability of the belongingness. It is
well known that “uncertainty” is one of major criteria for
active learning [6] to select candidates of training data. Thisis generally called uncertainty sampling [7]. In this research,
we need uncertain data pairs that are expected to be useful toimprove clustering performance if they are used as constraints.
We expect that constraints added by such uncertainty sampling
are more effective than constraints selected at random.
The rest of this paper is organized as follows. We first
introduce a constrained clustering method based on a bagging
framework in Section II. Then we propose our method of
active constraint sampling based on the clustering algorithm in
Section III. Section IV presents the results of the experiments
conducted using six datasets. We finally conclude our work in
Section V.
II. C LUSTERING A LGORITHM
We first propose a constrained clustering algorithm that isbased on a bagging based cluster ensemble technique and aconstrained k-means with random data assignment order.
Bagging is one of the ensemble learning techniques used to
produce a classifier by integrating weak hypotheses generated
by a weak learner that has outperforms random classifiers tosome extent. Algorithm 1 is our clustering algorithm based onbagging. According to the normal description of the bagging,
we can correspond each element of our algorithm as a

399

SCIS-ISIS 2012, Kobe, Japan, November 20-24, 2012

Algorithm 1 Ensemble of Constrained K-means

Algorithm 2 Constrained K-means

1: INPUT: Dataset X = {x1 , ..., x|X| },2: Constraints S= {(i1 , j1 , y1 ), ..., (i|S| , j|S| , y|S| )},k: No. of clusters
3: OUTPUT: Clusters C = {C1 , C2 , ..., Ck }4: for t = 1 to T do
5:

Run constrained k-means procedure(Algorithm2).
Then, create kernel matrix K t{
1(xi , xj ) belongs to same cluster
K t (i, j) =−1 (xi , xj ) belongs to different clusters

6: end for
7: Calculate final kernel matrix K

K=

T
∑

Kt

(1)

t=1

8: Run kernel k-means algorithm with K, and return final

set of clusters C••

Weak Learner → Constrained K-means((Argorithm2))
Training data → Constraints (must/cannot-link).

A constrained cluster produced by the constrained k-meansin each bagging step is used as a kernel matrix. Each elementof this kernel matrix indicates whether or not the corresponding data pair belongs to the same cluster. Thus, the kernel
matrix represents the link connections of the clusters. From thepoint of a weak learner, the modified COP-Kmeans predicts
the existence of the link between any data pair in the clusters
using the constraints as a set of training data. The kernel matrix
is an aggregation of these predictions. The kernel matrices are
summed up as a kernel. The final clustering result is generatedusing this final kernel matrix.
Algorithm 2 lays out the entire procedure of our constrained
k-means. Although it follows the basic procedure of thestandard k-means algorithm, which assigns data to its nearest
cluster center, its assignment process is rather complicatedsince we must consider the weight of constraint. There aremainly 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 (forconstrained data). We must take several cases like those listed
below into consideration.
Whether or not one of the data pairs has already been
assigned?
Our algorithm assigns a constrained data pair at the sametime. Since some data contain several constraints, one (orboth) of the data may have already been assigned in somecases. We must prepare procedures for such situations.
• Which constraint the data pair has? - must-link or cannotlink?
•

978-1-4673-2743-5/12/$31.00 ©2012 IEEE400

1: INPUT: Dataset X, Constraint Set S, No. of clusters k,
2:
Weights of Constraints wn (n = 1 ∼ |S|)
3: OUTPUT: Clusters C
4: Select initial cluster centers
5: for r = 1 to rmax do
6:Assign a random value to each wn
7:
Sort constraints in descending order according to wnt
8:Assign constrained data pairs (xi , xj ) to cluster centers insorted order following procedure below
Let (xi , xj ) be data pair to be assigned, then each data will beassigned to one cluster centers according to following cases.
10:
if Both of (xi , xj ) have not been yet assigned then11:
Let ci , cj be nearest cluster centers for xi and xj respectively, then let d(xi , ci ), d(xj , cj ) be distances between eachdata and its nearest cluster center.
12:
if (xi , xj ) is constrained by must-link then13:
if d(xi , ci ) < d(xj , cj ) then14:
Assign xi and xj to ci
15:
else
16:
Assign them to cj
17:
end if18:
else if (xi , xj ) is constrained by cannot-link then19:
if ci 6= cj then20:
Assign xi to ci , xj to cj , respectively
21:
else
22:
if d(xi , ci ) < d(xj , cj ) then23:
Assign xi to ci , xj to second nearest center
24:
else
25:
Assign xj to cj , xi to second nearest center26:
end if27:
end if28:
end if29:
else if xi has been already assigned and xj has not been yet
assigned then30:
Let ci be cluster center to which xi is assigned
31:
if xi and xj are constrained by must-link then32:
Assign xj to ci
33:
else if xi and xj are constrained by cannot-link then34:
Assign xj to cluster center that is nearest to data and isdifferent from ci
35:
end if36:
else if xi has not been yet assigned and xj has already been
assigned then37:
Let cj be cluster center to which xj is assigned
38:
if xi and xj are constrained by must-link then39:
Assign xi to cj
40:else if xi and xj are constrained by cannot-link then41:
Assign xi to cluster center that is nearest to data and isdifferent from cj
42:
end if43:
end if
44:
Assign rest of data that are not constrained to their nearest
cluster centers
45:
if Clustering result does not change from previous one then46:
Return result and exit
47:
else
48:
Update cluster centers and go to next step49:
end if
50: end for
9:

Depending on the situation described above, we must prepare different procedures according to which constraint
the data pair has.

SCIS-ISIS 2012, Kobe, Japan, November 20-24, 2012

TABLE IDATASETS

We describe the concrete procedure considering the above
cases in Algorithm 2 (l.9 ∼ 42).
glass
wdbc
balance
tr11
tr12
tr23

III. ACTIVE C ONSTRAINTS S AMPLING
The constrained clustering algorithm introduced in previous
section produces a variety of clusters. It may occur that adata pair belongs to a same cluster in a bagging step, butthey do not in another step. In this way, we can calculate
probabilities that a data pair belongs to a same cluster or
not from the bagging process. We calculate the entropy foreach data pair according to the probabilities and use it as ameasurement of “uncertainty” to select constraint candidates
for future clustering.
Let (xi , xj ) be a data pair and pij be a probability that they
belongs to a same cluster. We can calculate a entropy Eij foreach (xi , xj ) as follows.
Eij = −pij log pij − (1 − pij ) log(1 − pij )(2)Here, pij can be estimated from the number of occurrence
that (xi , xj ) belongs to a same cluster during bagging steps
1 ∼ T.
Once we can calculate entropies, we select several data pairsthat has higher values as constraint candidates and give themconstraint labels (must/cannot-link). This sampling process
follows “uncertainty sampling” that is one of major and usefulactive learning framework. We consider a data pair that has
high entropy value to be a good candidate since their constraintlabel is difficult to predict.
IV. E XPERIMENTS
We evaluated our proposed method on six datasets. The
datasets are summarized in Table I. Glass, wdbc and balance
are from the UCI repository1 and tr11, tr12 and tr23 are fromthe CLUTO datasets 2 .
We compared the following methods for constraint sampling.
• active: This is our proposed method, which selects data
pairs to be labeled based on the entropy calculated by
the clustering sequence obtained during bagging process.
Our algorithm starts from 10 (randomly selected) source
constraints and repeats active sampling until it gets 100
constraints. In an active sampling, it selects and labels 10
constraint candidates. We repeated this sampling process
10 times and show the average score as the final results.
• random: This method randomly selects data pairs to belabeled. We repeated 10 sampling process and show theaverage score in a similar way as our active method.
Both methods are based on a clustering algorithm describedin Section II. The bagging step T was set to 100. Distancemetric we used in the experiments was the Euclid distance.
We used normalized mutual information (NMI) to measure
the clustering accuracy. The NMI was calculated by using the1 http://archive.ics.uci.edu/ml/
2 http://glaros.dtc.umn.edu/gkhome/cluto/cluto/download

978-1-4673-2743-5/12/$31.00 ©2012 IEEE

No. of Data
214
569
625
414
313
204

No. of Class
6
2
3
9
8
6

No. of Attribute
10
30
4
6429
5804
5832

following formula.
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.
Fig.1 shows the results on the six datasets. In every graph,horizontal axis indicates the number of constraints used forclustering, and vertical axis indicates the NMI value. Our
method slightly outperforms random sampling method in all
datasets. Although our method showed little improvement in
tr11 and tr23, in other datasets, it outperformed random sampling method and extended the gap as constraints increased.
In addition, our method achieved performance improvementin glass and wdbc despite random method did not show any
improvement at all.
V. C ONCLUSION
In this paper, we proposed a sampling method for constrained clustering, which actively selects data pairs to beconstrained by using variance of clustering iteration. Thismethod consists of a bagging based cluster ensemble algorithm
that integrates a sequence of clustering results produced by aconstrained k-means with random ordered data assignment.
Using this base clustering method, our sampling methodmeasure uncertainty of belongingness of each data pair, whichis represented by entropy calculated from the probability of thebelongingness. Experimental results showed that our method
outperforms clustering with random sampling on six datasets.
Though the improvement was mostly slight, it should be notedthat our method achieved the performance despite relatively asmall set of constraints.
Since active sampling 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 manyother datasets.
R EFERENCES[1] O. Chapelle, B. Scholkopf, and A. Zien, Semi-Supervised Learning. The
MIT Press, 2006.
[2] S. Basu, I. Davidson, and K. L.Wagstaff, Eds., Constrained Clustering.
CRC Press, 2008.
[3] W. Tang, H. Xiong, S. Zhong, and J. Wu, “Enhancing semi-supervised
clustering: A feature projection perspective,” in Proceedings of the 13th
International Conference on Knowledge Discovery and Data Mining,
2007, pp. 707–716.

401

SCIS-ISIS 2012, Kobe, Japan, November 20-24, 2012

!"'$

!"'$
-./01$-./01$

2-3456$2-3456$
!"&$

7=>

7=>

!"&$

!"%$

!"%$

!"#$

!"#$
(!$

)!$

*!$

+!$

#!$

%!$

&!$

'!$

,!$

(!$

(!!$

)!$

*!$

+!$

#!$

%!$

&!$

75"$58$953:;2-<3;:

75"$58$953:;2-<3;:(a) glass(b) wdbc

!"'$

!#%"

!"&$

,!$

(!!$

,!$

(!!$

7=>

7=>

!#&"

'!$

!#$"

-./01$!"%$-./01"

2-3456$2-3456"
!"

!"#$
$!"

%!"

&!"

'!"

(!"

)!"

*!"

+!"

,!"

$!!"

(!$

)!$

*!$

+!$

#!$

%!$

&!$

75#"58"953:;2-<3;:

75"$58$953:;2-<3;:(c) balance(d) tr11

'!$

!"'$

!"%$

7=>

7=>

!"&$

!"%$

-./01$-./01$

2-3456$2-3456$
!"#$

!"#$
&!$

'!$

(!$

)!$

*!$

+!$

#!$

%!$

,!$

(!$

&!!$

#!$

%!$

&!$

'!$

)!$

*!$

75"$58$953:;2-<3;:

75"$58$953:;2-<3;:(e) tr12(f) tr23
Fig. 1.

[4] L. Breiman and L. Breiman, “Bagging predictors,” in Machine Learning,
1996, pp. 123–140.
[5] K. Wagstaff and S. Roger, “Constrained k-means clustering with background knowledge,” in Proceedings of the 18th International Conference
on Machine Learning, 2001, pp. 577–584.

,!$

(!!$

Resultssemi-supervision for pairwise constrained clustering,” in In Proceedingsof the 2004 SIAM International Conference on Data Mining (SDM-04,
2004, pp. 333–344.
[7] D. Lewis and W. Gale, “A sequential algorithm for training text classifiers,” in Proceedings of the 17th Annual ACM SIGIR Conference, 1994,
pp. 3–12.

[6] S. Basu, A. Banjeree, E. Mooney, A. Banerjee, and R. J. Mooney, “Active

978-1-4673-2743-5/12/$31.00 ©2012 IEEE+!$402