Efficient Soft-Constrained Clustering
for Group-Based Labeling
Ryoma Bise1 , Kentaro Abe1 , Hideaki Hayashi1 , Kiyohito Tanaka2 , and Seiichi
Uchida1
1

Kyushu University, Fukuoka City, Japan. bise@ait.kyushu-u.ac.jp
2
Kyoto Second Red Cross Hospital, Kyoto, Japan.

Abstract. We propose a soft-constrained clustering method for group-based labeling of medical images. Since the idea of group-based labeling is to attach thelabel to a group of samples at once, we need to have groups (i.e., clusters) withhigh purity. The proposed method is formulated to achieve high purity even fordifficult clustering tasks such as medical image clustering, where image samples of the same class are often very distant in their feature space. In fact, thoseimages degrade the performance of conventional constrained clustering methods.
Experiments with an endoscopy image dataset demonstrated that our method outperformed various state-of-the-art methods.

1 Introduction
Collecting a large number of labeled images as training data is required in machinelearning classification tasks because deep neural networks require sufficient training
data to learn discriminative features for robust classification. In general object image
recognition tasks, crowdsourcing services (e.g., Amazon MechanicalTurk) have been
widely used for labeling images efficiently and quickly by using workers from all over
the world. However, we cannot use such services for medical images because mostannotators of the services cannot attach appropriate labels due to a lack of biomedical knowledge. Considering the large diversity of recent classification tasks of medical
images, there is a huge demand for systems that reduce the labeling effort.
To label data efficiently, several group-based labeling methods [1–3] have been
proposed, where the data is first clustered and then the images of each cluster are labeled
by an expert, as shown in Fig. 1(a). If the purity of each cluster is high enough (i.e.,
if each cluster is mostly comprised of the images from the same class), group-basedlabeling is far more effective than instance-based (i.e., one-by-one) labeling. Imagine asituation that all images of a cluster are listed in a file viewer and an expert observes
them. If the expert finds that all of them belong to the same class, she/he can attach thesame label to them at once. Even when a cluster contains a small number of images
from different classes, it is still easy to find and exclude them before labeling; this isbecause those images will be visually salient in the list.
In order to increase the purity of each cluster for higher efficiency of group-basedlabeling, constrained clustering, such as [4, 5], is a reasonable choice. As shown in
Fig. 1 (b), an expert selects a small number of samples from the dataset and put links
to them before clustering. If a pair of two samples must (cannot) belong to the same

Overview2

R. Bise et al.
(a)

(c)

group-basedlabeling

clustering→Fundus→PyloricZone

put links toa small amountof images(b)constrained
clusteringcannot(hard)

Feature Extraction
feature vector
feature vector
feature vector

Fundusmust(soft)Class 2

Constraints

CNN
1%

LabeledClass 1・・・

・・・

cannot(hard)

these must-linked images are mixed-up
from the same organ but
clusterhave different appearancesgroup-based labelingmust(hard)(d)must?
(hard)

cannot(hard)

Soft-Constrained
Clustering

mark the instances that
correspond to the largest
subset of a particular category

Fig. 1. (a) Group-based labeling with clustering. (b) Hard-constrained clustering. (c) An unexpected result by hard-constrained clustering; the middle of the mixed-up cluster is better to belong
to another cluster. (d) The proposed soft-constrained clustering for group-based labeling.

cluster, they are linked by a must-link (cannot-link). Then a clustering is performed
while satisfying the constraints indicated by the links. A small effort of putting thelinks will greatly help to increase the purity of the resulting clusters.
If a class is unimodal and thus the samples belong to the class can be grouped by asingle cluster, the conventional constrained clustering will work well without any sideeffect; however, if a class is not unimodal, the must-link constraints may adversely affect clustering. As shown in Fig. 1 (c), a must-link for distant samples causes a mixed-up
cluster in order to satisfy the constraint by the must-link. Such an undesired must-link is
not avoidable, especially for medical image applications. The appearance of a medical
image often changes even in the same class due to huge appearance variations, different shooting angles, etc., and the class distribution often becomes multimodal whose
components are distant to each other.
In this paper, we propose a novel soft-constrained clustering method for medical
image labeling tasks. Different from the conventional constrained clustering methods,
we allow the violation of must-link constraints to deal with the classes with multimodal(scattered) distributions, as shown in Fig. 1 (d). Specifically, must-links are evaluatedas penalties while cannot-links are still treated as hard constraints. In addition, the proposed method is formulated as a single optimization problem, whereas the conventional
soft-constrained clustering methods first solve the hard-constrained problem and thenmodify the cluster assignment. We have evaluated the performance of the proposed
method in the task to put 20 labels to about 12,000 endoscopic images collected fromseveral hospitals. Specifically, the proposed method achieved higher performance measurements (purity and recall of the clusters) than state-of-the-art clustering methods
under different numbers of clusters and rates of links (i.e, constraints).

Efficient Soft-Constrained Clustering for Group-Based Labeling3

2 Related work
The most famous constrained clustering method is COP-Kmeans [4], which modifies
the assignment step of K-means to satisfy must/cannot-link constraints. It performs
hard-constrained clustering and thus is not suitable for medical images. Soft-constraint
clustering methods, such as CVQE [6] and LCVQE [7] have been proposed to relax
the hard constraints to a penalty evaluation. For example, CVQE penalizes violationof must-link constraints by adding a penalty of the distance between the two nearest
cluster centers of these two points. LCVQE improves the computational costs by modifying the penalty term in the objective function of CVQE. Similar to these methods,
PCK-means [8] and MPCK-means [9] methods design the penalty function as 0/1-Loss.
Those soft-constrained clustering algorithms first solve the hard-constrained problem
and then update the cluster assignment of each sample. This two-step organization isreasonable for discarding a small number of erroneous constraints but not for dealing
with multimodal distributions; this is because as shown in Fig. 1(c) the must-links under multimodal distributions may disturb the first step. Recently, Le et al. [5] proposeda Binary Optimization for Constrained K-means (BOCK) where the optimization problem formulated as a single binary linear programming problem. Although it uses nota two-step formulation, it performs hard-constrained clustering and thus is not suitable
for medical images.
Our soft-constrained clustering method is formulated as a single optimization problem while dealing with the must-constraints in a penalty term. As shown in the later
experimental result, this formulation is very suitable for medical image labeling tasks
because the multimodal distribution of medical images will give many undesired mustlinks and thus the typical two-step optimization will fail. To the authors’ best knowledge, any soft-constrained clustering method like ours has been neither proposed nor
applied to medical images.

3 Efficient labelingFig. 1(d) shows the overview of our labeling scheme including the proposed clustering
method. In this scheme, features are first extracted for each image by DenseNet [10]pre-trained by ImageNet.3 An expert attaches labels to a very few samples (1%). From
the attached label, must-link and cannot-link constraints are defined; must-link (cannotlink) for a pair of samples from the same class (different classes). Next, the proposed
soft-constrained clustering method is applied by using the must-link as a penalty andthe cannot-link as a hard constraint. Then, the images in the “prominent” cluster, whichcontains the most labeled samples among all clusters, is shown to an expert and theexpert attaches the labels to all samples. If the cluster only contains samples from thesame class, the expert can attach the same class label to them at once. Even if thecluster contains several samples from different classes, the expert can do the same justafter discarded those samples. The remaining samples (the discarded samples and thesamples in other clusters) are fed to the clustering at the next round. Finally, this process
is repeated until all samples have been labeled.
3

We selected one of the most famous networks as a feature representation network.

4

R. Bise et al.

4 Soft-constrained clustering
4.1 Problem setting
The formulation of our soft-constrained clustering method can be started from that of
the K-means clustering. Given N samples X = {xj ∈ RD }N
j=1 , where D is the dimension of the feature vector, the goal of K-Means is to find a set C containing K cluster’s
centroids C = {ci ∈ RD }K
i=1 and assign each sample xj to one of non-overlapping
clusters. The optimal clustering minimizes the within cluster sum of squares (WCSS).
According to [5], it is formulated as:min ∥X − SC∥2F ,C,Ss.t. sij ∈ {0, 1} ∀i, j,K∑

sij = 1 ∀j = 1, . . . , N,

(1)

i=1

where X ∈ RD×N is the matrix whose the j-th column corresponds to xj ∈ RD ,and C ∈ RD×K is a cluster centroid matrix whose i-th column corresponds to thecentroid ci . S ∈ RK×N is a cluster assignment matrix, where its (i, j)-th element sij
has the value of 1 if the sample xi is assigned to the j-th cluster and 0 otherwise. The
first constraint restricts S to be a binary assignment matrix and the second constraint
represents each sample to be assigned to only one cluster. The j-th column of SC
indicates the centroid of the cluster to which the j-th sample xj is assigned. | · |Fdenotes the Frobenius norm of a matrix.
In the constrained clustering task, we need to specify must-links and cannot-links.
A must-link will be attached to a sample pair that need to belong to the same cluster. A
cannot-link will be attached to a pair that cannot belong to the same cluster. Here, we
assume that an expert attaches correct labels to a small number of samples for each class(i = 1, . . . , Nc ), where Nc is the number of classes. Denoting Li as the set of labeled
samples for class i, xj ∈ Li indicates that the j-th sample belongs to the i-th class.
Using the labeled samples, we then generate the must-link and cannot-link constraints.
A pair of samples is registered to the must-link set M if these labels are the same, andto the cannot-link set D if different.
The proposed soft-constrained clustering method also tries to optimize the set of
K cluster centroids C and the cluster assignments that minimize the sum of the WCSS
distortion. The main difference from (1) is that the cannot-links D are imposed as hardconstraints. Another, more important difference is that the must-links are evaluated aspenalties; must-link constraints can be violated but penalized. This non-consistent treatment for the cannot-link and must-link comes from the property of medical images; as
we noted, must-links are often too hard to satisfy for the class with a multimodal (scattered) distribution.
Consequently, the proposed method is formulated as:∑min ∥X − SC∥2F + ω
C,S

K
∑

|sip − siq |1 ,(2)

sij = 1 ∀j = 1, . . . , N,

(3)(xp ,xq )∈M i=1

s.t. sij ∈ {0, 1} ∀i, j,

K
∑
i=1

sip + siq ≤ 1, ∀i = 1, . . . , K ∀(xp , xq ) ∈ D,(4)

Efficient Soft-Constrained Clustering for Group-Based Labeling5

where (4) represents the cannot-link constraints. If two samples xp and xq are pairedby a cannot-link (i..e, (xp , xq ) ∈ D) and they try to belong to the same cluster i,
sip + siq = 1 + 1 ≰ 1; consequently, this situation violates the constraint and is notallowed. The second term of the objective function (2) represents soft-constraints of themust-link. If two samples xp and xq are paired by a must-link (i.e., (xp , xq ) ∈ M) andthey try to belong to different clusters, it becomes sip − siq = 1 > 0 and thus penalizes
the objective function by ω, which is a positive constant.
4.2 Optimization for soft-constraints clustering
To minimize (2) with constraints (3) and (4), we take an alternating optimization approach that alternatively updates the cluster centroid matrix C and the assignment matrix S until convergence, which is similar to the original K-means optimization approach(EM algorithm). In the update step for C by fixing S, we can ignore the constraints andthe second penalty term of the objective function. We update C by solving the regularized least square problem to avoid numerical issues for large-scale problems [11]:min ∥X − SC∥2F + λ∥C∥2F ,C(5)where λ is the regularization parameter and we set λ to be 10−4 in our experiments. The
problem is a convex quadratic optimization problem and it can be solved in closed-form.
C = XST (SS + λI)−1 ,(6)

where (SS + λI) is guaranteed to be full-rank.
Next, we update S by fixing C. Let Y ∈ RK×N be a matrix whose (i, j)-th element
yij is the squared distance from xj to its centroid ci ; namely, yij = ∥ci − xj ∥22 . By
using Y, the first term of (2) can be written as ⟨Y, S⟩, which represents Frobenius innerproduct of Y and S.
By rewriting the second term with KM variables γi,(p,q) , which is defined for eachpair of p and q which satisfies (xp , xq ) ∈ M, the updating problem of S becomes:min ⟨Y, S⟩ + ω
s,γ

∑

K
∑

γi,(p,q) ,(7)

sij = 1 ∀j = 1, . . . , N,

(8)(xp ,xq )∈M i=1

s.t. sij ∈ {0, 1} ∀i, j,

K
∑
i=1

sip + siq ≤ 1, ∀i = 1, . . . , K ∀(xp , xq ) ∈ D,

(9)sip − siq ≤ γi,(p,q) , −sip + siq ≤ γi,(p,q) , ∀i ∀(xp , xq ) ∈ M,

(10)

where the set γ = {γi,(p,q) }. This problem is a mixed binary linear programming;that is, the combination of the binary programming problem for S and the linear programming problem for γ. We solve this problem by the branch-and-bound optimization
technique. In our experiments using over 10,000 images, the convergence time is about
30 seconds for this step. These two steps for updating C and S are alternatively iterated
until convergence.

6

R. Bise et al.

Table 1. 20 classes defined for stomach endoscope images. BD, UP, MD, LO, LD, and LU standfor (stomach) body, upper, middle, lower, (camera) look-down, and look-up, respectively.
FundusFundus on UP BD/ LU UP BD/ LU
UP BD/ LD
UP-MD BD/ LU
UP-MD BD/ LD
MD BD/ LU
MD BD/ LD
MD-LO BD/ LU
MD-LO BD/ LD
LO BD/ LD
Angular Incisure LO BD/ LD
AntralZone on LO BD/ LD Angular Incisure
Angular Incisure-Antral Zone Antral Zone
Pyloric Antral
Pyloric Zone
PylorusJunction

Table 2. Quantitative performance evaluation by purity and recall. Larger is better.
MetricConditions

KM BOCK[5] MPCK[9] LCVQE[7]K=100, R=1% 0.602
K=100, R=3% 0.726
K=100, R=5% 0.681
purityK=50, R=1% 0.623
K=50, R=3% 0.668
K=50, R=5% 0.637
K=100, R=1% 0.132
K=100, R=3% 0.156
K=100, R=5% 0.162
recall
K=50, R=1% 0.254
K=50, R=3% 0.287
K=50, R=5% 0.262

0.627
0.673
0.716
0.549
0.648
0.694
0.138
0.167
0.169
0.230
0.281
0.296

0.421
0.544
0.494
0.369
0.521
0.498
0.109
0.147
0.170
0.170
0.263
0.258

0.573
0.660
0.587
0.616
0.636
0.643
0.122
0.155
0.159
0.230
0.269
0.279

Proposed
Proposed
w/o must link
0.658
0.712
0.747
0.517
0.651
0.662
0.147
0.158
0.174
0.218
0.273
0.295

0.715
0.789
0.747
0.660
0.727
0.702
0.159
0.179
0.174
0.270
0.310
0.297

5 Experimental results
In this section, we conducted experiments to evaluate the capability of the proposed
method to support efficient ground-truth annotation for endoscopic image clustering.
The endoscopy images were collected from several hospitals, including 11,599 stomach
images captured by endoscopy. In the clustering task, these stomach images captured
were classified into 20 classes listed in Table 1, according to the part in stomach andtwo camera capturing angles (look-down/look-up) for several parts.
We designed the performance metrics that fit the situation where clustering is used
for the actual labeling process. In the evaluation scenario, we randomly select a certain amount of the samples along with their correct label and have cannot-links andmust-links by using them. Then, we perform our soft-constrained clustering and get K
clusters. Among them, as described in Section 3, we pick up the “prominent” cluster
for each class. The prominent cluster contains the most samples labeled by the expert
with a certain class and thus a reliable cluster. We thus show the images belonging to
the prominent cluster to the expert for finalizing the labeling of the samples. The expert
will observe the images and discard the images from different classes and put the sameclass label to all the remaining images. Consequently, we need to have high purity andhigh recall at the prominent cluster to reduce this finalizing operation. The purity foreach class is the number of true positives divided by the number of unlabeled samples
in the prominent cluster. The recall for each class is the number of true positives in theEfficient Soft-Constrained Clustering for Group-Based Labeling(a) Ground-truth(b) Clustering results(Proposed)

Must-link Constraints(c) Corresponding cluster(Proposed)

True Positive（Fundus）

False Positive（ Others ）7(d) Corresponding cluster(BOCK)Class:03

Fig. 2. Clustering result examples at K = 50 and R = 0.03. tSNE is used for these twodimensional visualizations. (a) Distribution of samples whose true label is “Fundus.” Green dots
indicate unlabeled samples and red indicate labeled samples that were used as must-link constraints. (b) Clustering results from our method. (c) Results of proposed methods and (d) resultsof BOCK [5]. In (c) and (d), magenta dots indicate samples from other classes.
(a)(b) rank=1 Class:01

rank=2 Class:01

rank=45 Class:09

・・・

rank=204 Class:03 rank=205 Class:01

9・・・

Fig. 3. (a) Accumulated purity curve with distance from the centroid of the cluster, where thecluster corresponds with the one in Fig. 2(c). The vertical axis indicates accumulated purity, andhorizontal axis indicates sorted order by distance from centroid. (b) Images in cluster. Images
were sorted by distance from centroid from left to right. “rank” shows the order by the distancein the cluster and rank=1 is the closest. “Class” is a true label of the image (e.g., Class:01 is“Fundus.”)prominent cluster divided by the total number of the samples of the class. In the later
result, these measurements are averaged over all classes.
The performance of the proposed method was compared with several clustering
methods: K-Means (KM) that is non-constrained clustering and the Binary Optimization approach for Constrained K-means (BOCK) that is hard-constrained clustering.
Metric-based Pairwise Constrained K-means (MPCK) [9] and Linear-time Constrained
Vector Quantization Error (LCVQE) [7] that are state-of-the-art soft-constrained clustering4 . As discussed in Section 2, both soft-constrained clustering methods were designed to discard a small number of erroneous constraints. In addition, we evaluated the
proposed method without using must link as an ablation study. The parameter ω was set
to 50 for all experiments. To demonstrate the robustness for the rate of labeled samples
over the total data R and the number of clusters K, we evaluated the performance under
several conditions: K = 50, 100 and R = 1%, 3%, 5%, where the labeled samples wererandomly picked up, and then the must-link and cannot-link constraints were generated
4

A most popular hard-constrained clustering, COP-Kmeans [4] has not been compared; it did
not work due to its heavy computational complexity for our large dataset.

11

8

R. Bise et al.

on the basis of the labeled data. When R = 1%, the average number of labeled data ineach class is about 29.
As shown in Table 2, our method achieved the best performance under all conditions. When K = 100, the purity of the proposed method was over 0.7. Here, we notethat the purity was computed using only the unlabeled data, and thus it could occurthat the purity with R = 5% is better than that with R = 10%. In the annotation task
for separating a set of images to a particular class and others, this purity value is highenough to improve the efficiency of the annotation task compared with the individual
annotation process. In particular, in the case where the number of labeled data was low(1%), the purity of the proposed method is the highest and shows 8%(= 0.715 − 0.627)
improvement compared with the second best, BOCK. Our method also achieved thebest recall.
Fig. 3 shows the image examples in a cluster corresponding with class “Fundus.”
To analyze the relationship the distance from the centroid and the class label of thesample, we sorted the data by distances from the cluster centroid. Fig. 3(a) shows theaccumulated purity curve. In this plot, the samples near the centroid tend to have thesame label as the labeled samples in the cluster.
The average running time for clustering over 10,000 images was 14s, 1119s, 10s,
1824s, and 130s by KM, BOCK, MPCK, LCVQE, and the proposed method, respectively. Our method was much faster than the other state-of-the-arts, BOCK and LCVQE,
and its speed is acceptable for the group-based labeling scheme.

6 Conclusion
We proposed a soft-constrained clustering suitable for group-based labeling. The proposed method performs clustering by using must-links for penalties instead of hardconstraints by considering that the class distribution of medical images is often notunimodal but multimodal whose components are distant to each other. The advantage
of our method is that we formulate the soft-constrained clustering problem as a single
optimization problem rather than a typical two-step optimization where the problem issolved as a hard-constrained problem and then update the result. Our method achieved
higher purity and recall than several state-of-the-art clustering methods under various
conditions with different numbers of clusters and rates of the must/cannot-links.
Acknowledgments. This work was supported by JSPS KAKENHI Grant Number
JP19K22895 and AMED Grant Number JP18lk1010028.

References
1. Biswas, A. and Jacobs, D. Active image clustering: Seeking constraints from humans tocomplement algorithms. Proc. CVPR, pp.2152-2159, (2012).
2. Galleguillos, C., McFee, B., and Lanckriet, G. Iterative category discovery via multiple kernel
metric learning. IJCV, 108(1-2), pp.115-132, (2014).
3. Bruce, M.W., Draper, A. and Beveridge, J.R. Efficient Label Collection for Unlabeled Image
Datasets. Proc. CVPR, pp.4594-4602, (2015).

Efficient Soft-Constrained Clustering for Group-Based Labeling9

4. Wagstaff, K., Cardie, C., Rogers, S., and Schrodl, S. Constrained k-means clustering withbackground knowledge. Proc. ICML, pp.577-584, (2001).
5. Le, H.M., Eriksson, A., Do, T.T., and Milford, M. A binary optimization approach for constrained K-Means clustering. Proc. ACCV, (2018).
6. Davidson, I., Ravi, S.S. Clustering with constraints: Feasibility issues and the k-means algorithm. Proc. on SIAM Data Mining, (2005).
7. Pelleg, D., Baras, D., K-means with large and noisy constraint sets. Proc. ECML, pp.674-682,(2007).
8. Basu, S., Banerjee, A., and Mooney R.J. Active semi-supervision for pairwise constrained
clustering. Proc. SIAM on Data Mining pp.333-344, (2004).
9. Bilenko, M., Basu, S., Mooney, R.J. Integrating constraints and metric learning in semisupervised clustering. Proc. ICML, pp.81-88, (2004).
10. Huang, G., Liu, Z., Maaten, L., and Weinberger, K.Q. Densely connected convolutional
networks. Proc. CVPR, (2017).
11. Rifkin, R.M. and Lippert, R.A. Notes on regularized least squares MIT-CSAIL Technical
Report, (2007).