2012 IEEE 12th International Conference on Data Mining

Clustering by Learning Constraints Priorities
Masayuki Okabe
Toyohashi University of Technology
Toyohashi, Japanokabe@imc.tut.ac.jp

Abstract—A method for creating a constrained clustering
ensemble by learning the priorities of pairwise constraints is
proposed in this paper. This method integrates multiple clusters
produced by using a simple constrained K-means algorithm
that we modify to utilize the constraints priorities. The cluster
ensemble is executed according to a boosting framework, which
adaptively learns the constraints priorities and provides themfor the modiﬁed constrained K-means to create diverse clusters
that ﬁnally improve the clustering performance.
The experimental results show that our proposed method
outperforms the original constrained K-means and is comparable to several state-of-the-art constrained clustering methods.
Keywords-Constrained Clustering; Cluster Ensemble; Boosting; Learning Kernel Matrix; K-means;

I. I NTRODUCTION
Constrained clustering [1] is a semi-supervised learning
approach that uses pre-given knowledge about data pairs to
improve the normal clustering accuracy. There are generally
two simple types of knowledge used: constraints concerning
data pairs that must (or cannot) be in the same cluster. These
are usually called must-link and cannot-link, respectively.
Recent research on distance metric learning interprets theconstraint information as the distance of data pairs and tries
to produce a new distance measure for a complete dataset toensure the distance of a must-link is small and the distanceof a cannot-link is large [2], [3].
They usually use these constraints “softly”, permitting certain violation to be overlooked when dealing with optimization problems such as SDP. Unfortunately, such approaches
often consume a lot of computational time [4]. Moreover,most of the algorithms for distance metric learning treat
constraints equally because no such information is pregiven. However, constraints may not always help to improveclustering performance [5]. It may happen that some sets ofconstraints works well but some others do not. We focus
on these problems and try to create a constrained clustering
algorithm that can adaptively select useful constraints as well
as being less time consuming.
Our method is based on the COP-Kmeans algorithm [6],which is simple and relatively less time consuming. Since itis hard-constrained clustering algorithms, it sometimes halts
along the way and returns no result, especially when thenumber of constraints is large. We complement such defects
1550-4786/12 $26.00 © 2012 IEEE
DOI 10.1109/ICDM.2012.150

Seiji Yamada
National Institute of Informatics / SOKENDAITokyo, Japanseiji@nii.ac.jp

and improve its performance using boosting [7] as the wayof creating a cluster ensemble [8].
In boosting, we treat COP-Kmeans as a weak learnerto predict whether or not each pairwise data is in thesame cluster. In order to make COP-Kmeans work as a
weak learner, we modify it not to halt even if it violates
some constraints, i.e. it may only satisfy partial constraints.
However, we positively utilize this property to produce avariety of clustering results by changing the data assignment
order with constraints priorities controlled by the boosting.
These multiple clustering results are combined as a kernel
matrix. Then it is used for the ﬁnal clustering. The main
originality of our proposed methods compared with otherboosting based techniques for distance metric or kernel
matrix learning [9], [10], [11] is the use of COK-Kmeans.
We adjust its algorithm to work as a weak learner for the
Adaboost.
Using COP-Kmeans and boosting will produce otherbeneﬁts. It generally produces a monotonically increasing
performance with an increase of the boosting steps. Thus,
it can ﬁnd the trade-off between the performance and thecomputational time. If we consume more time we can get
an improved performance. This is an important feature of theanytime algorithm [12] , which will be required, especiallyin practical situations.
In summary, we propose a constrained clustering methodthat has the following features.
• Using a cluster ensemble technique based on the
boosting and a modiﬁed COP-Kmeans algorithm thatcan use the adaptively learned constraints priorities,
and it ﬁnally produces clusters that satisfy the given
constraints as much as possible.
• We can estimate and maintain the balance between thecost and performance because the computational costof the proposed algorithm linearly increases along withthe total number of boosting steps.
II. OVERVIEW OF THE COP-K MEANS
COP-Kmeans is a representative algorithm for the constrained partitional clustering. It is based on a K-means
algorithm whose algorithm consists of the following threesteps.
1) Selection of initial cluster centers.
1050
799

2) Assignment of each data to one of the cluster centers.
3) Updating of cluster centers.
COP-Kmeans additionally considers not violating any
constraints when assigning data in Step 2. Thus a data will
not necessarily be assigned to its nearest cluster center.
It may be assigned to the second or nth nearest cluster
center to avoid committing constraint violations. Such usageof constraints has the following serious problems. One is
the failure of the algorithm. If no cluster centers exist thatsatisfy all the constraints, the algorithm halts and returns noresult. This often occurs when there are many constraints to
be satisﬁed. The other is an unstable performance because
clustering results depends on the order of data assignment.
Some orders perform well, but some may be bad.
We get rid of such drawbacks according to the following
approach, which aims to utilize the power of boosting-based
cluster ensemble technique.
• We modify COP-Kmeans not to halt even if it violates
some constraints. Instead, we repeat to run the modiﬁed
COP-Kmeans a certain number of times by changing
the data assignment order, and then integrate suchproduced multiple clustering results as a kernel matrix.
• We adopt the Boosting approach to integrate multiple
clustering results in the process. We use it to control
the order of data assignment in the modiﬁed COPKmeans. Boosting calculates the weight of each constraint, which is used as the priority to decide the orderof data assignment in the modiﬁed COP-Kmeans.

Algorithm 1 Boosted Constrained K-means

III. L EARNING C ONSTRAINTS P RIORITIES BY B OOSTING

11: Run kernel K-means algorithm with K, and return ﬁnal set of

1: INPUT: Dataset X = {x1 , ..., x|X| },Constraints S = {(i1 , j1 , y1 ), ..., (i|S| , j|S| , y|S| )}(i, j) is a pair of data index and y ∈ {+1, −1},
Parameters for loss function ρ, ξ, No. of clusters k
2: OUTPUT: Clusters C = {C1 , C2 , ..., Ck }
0
1
3: wn
← |S|
(n = 1 ∼ |S|)
4: for t = 1 to T do
5:
Run modiﬁed COP-Kmeans algorithm. Then, create kernel

matrix K t

K t (i, j) =
6:



1
−1

Calculate error rate tρt = ·
27:(xi , xj ) belongs to same cluster(xi , xj ) belongs to different clusters

|S|

n=1

wnt (1 − yn K t (in , jn ))

|S|

n=1

Using t , calculate importance value αt for K t
αt = ln

8:

(1)

wnt



1 − ttUpdate weight wnt+1 for each constraint

wnt+1 = wnt exp−αt (yn K t (in , jn ) − ξ)
ρ

(2)


(3)

9: end for
10: Calculate ﬁnal kernel matrix K

K=

T


αt K t(4)

t=1

clusters C

Following the approaches described in the previous section, we propose a constrained clustering method that consists of a modiﬁed COP-Kmeans algorithm and a cluster
ensemble framework based on the boosting. We ﬁrst introduce a boosting-based cluster ensemble framework, whichcalculates the constraints priorities for our modiﬁed COPKmeans algorithm to produce various clustering results ineach round, and ﬁnally integrates them as a kernel matrix to
produce the ﬁnal clusters. Then, we describe our modiﬁed
COP-Kmeans algorithm in detail, particularly concerning its
data assignment procedure using constraints priorities.

••

Training data → Constraints (must/cannot-link)
Weights for training data → Priorities for constraints.

We modify the original COP-Kmeans to use as a weaklearner for the boosting. This modiﬁed COP-Kmeans produces a constrained clustering according to the constraints
priorities given by this boosting process. We will describe
how we change the algorithm in the next Section. A
constrained clustering produced in each boosting step isrepresented as a kernel matrix whose element indicates
whether or not the corresponding data pair belongs to thesame cluster. From the point of a weak learner, the modiﬁed
COP-Kmeans learns this kernel matrix using the constraints
as a set of training data. These kernel matrices are summed
up with their importance values that are calculated by using
the error rate of the constraints satisfaction in each boostinground. The ﬁnal clustering result is generated using this ﬁnal
kernel matrix.
Another important role of the boosting framework is to
give a priority to each 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

A. Boosting Algorithm
Boosting is one of the ensemble learning techniques used
to produce a classiﬁer by integrating weak hypotheses generated by a weak learner that outperforms random classiﬁers tosome extent. Although various kinds of boosting techniques
have been proposed, our method is based on Adaboost[7],which is a well-known framework to enhance the classiﬁer
ability by ﬂexibly changing the weights of the training data.
Algorithm 1 is our clustering algorithm based on Adaboost. According to the normal description of the boosting,
we can correspond each element of our algorithm as a
• Weak Learner → modiﬁed COP-Kmeans

1051
800

are used to control the data assignment order in modiﬁed
COP-Kmeans. 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ﬁcientsof the loss function in the boosting. We will describe how
our modiﬁed COP-Kmeans works and the relation between
the data assignment order and the loss function in boostinglater in this paper.

Algorithm 2 Modiﬁed COP-Kmeans
1: INPUT: Dataset X, Constraints S, No. of clusters k,

Constraints Priorities wn (n = 1 ∼ |S|)

2: OUTPUT: Clusters C
3: Select initial cluster centers
4: for r = 1 to rmax do
5:Sort constraints in descending order of wnt and assign

each corresponding data pair (xi , xj ) to cluster centersconsidering the following cases.
6:
if Both of (xi , xj ) is not assigned then7:
Let ci , cj be nearest cluster centers for xi , xj respectively,
then let d(xi , ci ), d(xj , cj ) be distances between eachdata and its nearest cluster center.
8:
if (xi , xj ) is constrained by must-link then9:
if d(xi , ci ) < d(xj , cj ) then10:
Assign xi and xj to ci
11:
else
12:
Assign them to cj
13:
end if
14:
else if (xi , xj ) is constrained by cannot-link then15:
if ci = cj then16:
Assign xi to ci , and xj to cj , respectively
17:
else
18:
if d(xi , ci ) < d(xj , cj ) then19:
Assign xi to ci , xj to second nearest center
20:
else
21:
Assign xj to cj , xi to second nearest center22:
end if23:
end if24:
end if25:
else if xi is assigned and xj is not assigned then26:
Let ci be cluster center to which xi is assigned
27:
if xi and xj are constrained by must-link then28:
Assign xj to ci
29:else if xi and xj are constrained by cannot-link then30:
Assign xj to the nearest cluster center but ci
31:
end if32:
else if xi is not assigned and xj is assigned then33:
Let cj be cluster center to which xj is assigned
34:
if xi and xj are constrained by must-link then35:
Assign xi to cj
36:else if xi and xj are constrained by cannot-link then37:
Assign xi to the nearest cluster center but cj
38:
end if39:
end if40:
Assign unconstrained data to their nearest cluster centers
41:
if Clustering result does not change from previous one then42:
Return result and exit
43:
else
44:
Update cluster centers and go to next step45:
end if
46: end for

IV. T HE W EAK L EARNER IN BOOSTING
The boosting framework described in the previous section
is used as the framework of the cluster ensemble. In thecluster ensemble, clustering results to be integrated should
be as diverse as possible. We create this diversity by changing the constraints priorities. In this section, we explain how
the modiﬁed COP-Kmeans uses the priorities and how theloss function in the boosting affects the calculation of thepriorities.
A. Modiﬁed COP-Kmeans
As described in Section II, we modiﬁed the COP-Kmeans
algorithm so that it is suitable for use as a weak learner inthe boosting. Our modiﬁed COP-Kmeans algorithm has thefollowing reﬁnements compared to the original one.
• It produces a clustering result regardless if it fails tosatisfy some constraints.
• It utilizes the constraints priorities that are continuously
controlled by the boosting process in order to decide
the data assignment order in the clustering.
The order of the data assignment in COP-Kmeans isusually decided at random. Our modiﬁed algorithm decides
the order by sorting with constraints priorities so that a
constraint with higher priority is more likely to be satisﬁed
than with lower priority since the likelihood of constraint
satisfaction generally increases if it is considered earlier thanthe other constraints. Our algorithm uses this empirical but
practically useful heuristic to decide the order.
Algorithm 2 lays out the entire procedure of our modiﬁed
COP-Kmeans. Although it follows the basic procedure of
the standard K-means algorithm, which assigns data to
its nearest cluster center, its assignment process is rather
complicated. There are mainly two parts to the assignment
processes, which consists of the procedure for the constrained and unconstrained data, respectively. The latter one(for the unconstrained data) remains the same as that in anormal K-means process. What we need to consider is theprocess for the previous one (for constrained data). Since
the objective of this modiﬁcation is to use the constraints
priorities and they are given for data pairs, our algorithm ﬁrst
assigns constrained data pairs. The assignment procedure
for a data pair is more complicated than a single dataassignment. We must take several cases like those listed
below into consideration.

•

1052
801

Whether or not one of the data pairs has alreadybeen assigned?
Our algorithm assigns a constrained data pair at thesame time. Since some data contain several constraints,
one (or both) of the data may have already been
assigned in some cases. We must prepare proceduresfor such situations.













 



 

 

























 

 

 























 

 

 






















 



 

 























 

 



 



















 

 

 















(b) Gradual change(a) Radical change
Figure 1.





Behavior of data assignment order

Table IUCI DATASETSWhich constraint the data pair has? - must-link or
cannot-link?
Depending on the situation described above, we must
prepare different procedures according to which constraint the data pair has.
We describe the concrete procedure considering the above
cases in Algorithm 2 (l.9 ∼ 42).
•

Name
iris
wine
parkinsons
sonar
segmentation
glass
ionospherewdbc
balance

B. Loss Function and Priority Calculation
One of key roles of the weak learner in the boosting
is to create diverse hypotheses. In our case, a hypothesis
corresponds to a set of clusters or a kernel matrix that iscreated by our modiﬁed COP-Kmeans, and the diversity
can be created by changing the data assignment order. If
the order changes, the subset of satisﬁed constraints willchange, which indirectly produces diverse clusters.
The data assignment order is controlled by constraints
priorities, which are calculated by using formula (3) in
Algorithm 1 (l.8). We brieﬂy explain the introduction of
the formula according to the minimization of the expected
loss in the boosting, and then, describe how the parameters
introduced by us affect the calculation of the priorities andthe data assignment order.
We use the following loss function in our boosting Algorithm 1.
ξ − yf (xi , xj )L(y, f (xi , xj )) = exp(
)
(5)
ρ
T
where f (xi , xj )(= t αt K t (i, j)) is a function to predictwhether a data pair (xi , xj ) is a must-link or cannot-link
and y indicates -1 or 1 if a data pair (xi , xj ) belongs to thesame cluster or not. This function is slightly different fromthe one used in Adaboost. The loss function of Adaboost isexp(−f (xi , xj )) (stylized in our notation).
The main reason we introduce parameters ρ, ξ is to soften
the gap in the priority values between the satisﬁed andunsatisﬁed constraints. If we use a loss function used in
the standard Adaboost algorithm, the priority calculation is
too radical to create variations of the data assignment order.
The loss function tends to produce only a radically changed

No. of Data
150
178
195
208
210
214
351
569
625

No. of Class
3
3
2
2
7
6
2
2
3

No. of Attribute
4
13
23
60
19
10
34
30
4

order. However, we ﬁnd that such radical changes in theorder are not suitable for creating clustering variations, andthat gradual change is preferable.
Figure 1 illustrates how the data assignment order changes
depending on the loss function. Figure 1 (a) shows the
behavior of the standard loss function. The order radicallychanges when the boosting step increases. On the other hand,
Figure 1 (b) shows the behavior of our loss function. The
order can change rather gradually if we provide appropriate
values for parameters ρ and ξ.
V. E XPERIMENTS
We evaluated our proposed method on six datasets fromthe UCI repository1 . These datasets are summarized in detailin Table I.
We compared the following methods.
• BCKM: Boosted Constrained K-means is our proposed
method. We set parameters ρ = 5.0 and ξ = 0.5
respectively. The boosting step T is set to 100.
• DBOOST: DistBoost [10] is a method to learn a
distance function based on boosting and a Gaussian
mixture model. The approach is similar to ours. We set
its boosting step T = 100, and use default values forother parameters. The learned distance function is used
for normal k-means clustering algorithm. We evaluate
the performance of the produced clusters.
1 http://archive.ics.uci.edu/ml/

1053
802

Table II
C OMPUTATION T IME OF 500 CONSTRAINTS ( SEC )ITML: Information Theoretic Metric Learning [2] is astate-of-the-art distance metric learning method. We set
default values for the parameters. The learned distancemetric (Mahalanobis distance metric with learned translation matrix) is used for normal k-means clustering algorithm. We evaluate the performance of the produced
clusters.
• RCKM: This method uses randomly calculated priorities. The other part is the same as our method. We
conduct this method to evaluate the effect of the dataassignment order controlled by the constraints priorities
calculated through the boosting.
• CKM: This is the original COP-Kmeans. Using thesame way in our modiﬁed COP-Kmeans, we permit
constraint violation to produce ﬁnal clusters in any case.
Distance metrics we used for BCKM, RCKM and CKM in
the experiments were all the Euclid distance.
We used normalized mutual information (NMI) [8] tomeasure the clustering accuracy.
Constraints are randomly selected by ﬁrst picking a data
pair, then give it a label of must-link or cannot-link using
true class labels in each dataset. Thus cannot-link is relatively more frequent than must-link in any datasets. Wechanged the number of constraints to be tested from 100 to
500 in 100 steps and prepared 10 sets of constraints for eachnumber because algorithm performance generally changes
well depending on a set of constraints. The performance atn constraints is the average of the results on those 10 sets.
•

CKM
BCKM
DBOOST
ITML

iris
0.05
3.10
17.29
7.56

glass
0.06
5.56
14.96
17.01

wdbc
0.18
18.13
131.34184.34

Although DBOOST and BCKM are based on similar
boosting frameworks, difference of weak learner and theusage of constraints priorities produced substantially different results. ITML showed better performance, especiallywhen the number of constraints is relatively small though theperformance increase was saturated early and was surpassed
by BCKM on several datasets.
We could verify the advantage of data assignment orderin our modiﬁed COP-Kmeans in the experiments because
BCKM showed outperformed or comparable performancecompared with RCKM and CKM in all the datasets. The improvement is achieved by the effective usage of constraints
priorities.
B. Computational Cost
Table II shows the computation time of each algorithm
on several datasets with 500 constraints. We selected iris asa standard dataset, glass and wdbc as datasets that have relatively larger number of classes and attributes, respectively.
Computation time of CKM is the smallest in every dataset.
Though BCKM spent more than CKM since it repeats CKM
100 times (= boosting steps), the cost is less than DBOOSTand ITML, especially on wdbc dataset that has a relatively
large number of attributes.
Computational cost of BCKM grows linearly dependingon the number of data, class and boosting steps. This isan advantage of our method compared with algorithms that
suffer from the exponential growth of computational costwith data or attribute size.

A. Clustering Accuracy
Figure 2 shows the results. In every graph, horizontal axis
indicates the number of given constraints, and vertical axis
indicates the NMI value. DBOOST failed to produce resultsin parkinsons, sonar, segmentation ionosphere and balancedatasets because it halted by an error when calculating theinverse of covariant matrix for Gaussian distribution.
Our method BCKM showed good performance on mostof the datasets. It outperformed others when the numberof constraints increased. For example, it showed better orcomparable performance at 200 or more constraints oniris, parkinsons and sonar, at 300 or more on glass andionosphere. In particular, BCKM achieved the maximum
performance at 500 constraints on parkinsons and sonar
datasets.
On the other hand, BCKM showed worse performancecompared with others when the number of constraints is
relatively small, such as at 100 or 200 constraints on glass,ionosphere, wdbc and balance. This is because even normal
constrained k-means can satisfy most of constraints on suchsmall number of constraints. In such cases, data assignment
order in our modiﬁed COP-Kmeans becomes almost ﬁxed
and it cannot create diverse clustering results. In fact, RCKM
and CKM showed almost the same performance in suchcases.

VI. C ONCLUSION
We proposed a method for creating a constrained clustering ensemble by learning the priorities of pairwise constraints in this paper. This method integrates multiple clusters produced by using a simple constrained K-means algorithm that we modify to utilize the constraints priorities.
The cluster ensemble is executed according to a boosting
framework, which adaptively learns the constraints priorities
and provides them for the modiﬁed constrained K-means
to create diverse clusters that ﬁnally improve the clustering
performance.
The experimental results showed that our proposed
method outperforms the original constrained K-means and iscomparable to several state-of-the-art constrained clustering
methods. In addition to the performance, we clariﬁed that
our method has the advantage of the computational costcompared with other metric learning based approach.

1054
803






 

 

 



 

 



 





























 



 


















 




































 

 














 



 








 

 









 



 



 


















(g) ionosphere







(h) wdbc
Figure 2.









 























(f) glass









 











 











 







(e) segmentation(d) sonar
 











 

 














 















 







(c) parkinsons







(b) wine(a) iris
 























 

















(i) balance

Results on UCI Datasets

R EFERENCES[1] S. Basu, I. Davidson, and K. Wagstaff, Constrained Clustering:
Advances in Algorithms, Theory, and Applications. Chapman& Hall/CRC, 2008.
[2] J. V. Davis, B. Julis, P. Jain, A. Sra, and I. S. Dhillon,“Information-theoretic metric learning,” in ICML, 2007, pp.
209–216.
[3] K. Weinberger and L. Saul, “Distance metric learning forlarge margin nearest neighbor classiﬁcation,” The Journal of
Machine Learning Research, vol. 10, pp. 207–244, 2009.
[4] L. Wu, R. Jin, S. C. H. Hoi, J. Zhu, and N. Yu, “Learning bregman distance functions and its application for semi-supervised
clustering,” in NIPS, 2009, pp. 2089–2097.
[5] I. Davidson, K. L. Wagstaff, and S. Basu, “Measuring
constraint-set utility for partitional clustering algorithms,” in
PKDD, 2006, pp. 115–126.
[6] K. Wagstaff, C. Cardie, S. Rogers, and S. Schroedl, “Constrained k-means clustering with background knowledge,” in
ICML, 2001, pp. 577–584.

[7] 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.
[8] A. Strehl and J. Ghosh, “Cluster ensembles—a knowledge
reuse framework for combining multiple partitions,” JMLR,
vol. 3, pp. 583–617, 2003.
[9] K. Crammer, J. Keshet, and Y. Singer, “Kernel design using
boosting,” in NIPS, 2002, pp. 537–544.
[10] T. Hertz, A. Bar-Hillel, and D. Weinshall, “Boosting margin
based distance functions for clustering,” in ICML, 2004, pp.
393–400.
[11] Y. Liu, R. Jin, and A. K. Jain, “Boostcluster: boostingclustering by pairwise constraints,” in KDD, 2007, pp. 450–459.
[12] S. Zilberstein, “Using anytime algorithms in intelligent systems,” AI Magazine, vol. 17, no. 3, pp. 73–83, 1996.

1055
804