JOURNAL OF EMERGING TECHNOLOGIES IN WEB INTELLIGENCE, VOL. 4, NO. 1, FEBRUARY 201243

Graph-cut based Constrained Clustering byGrouping Relational Labels
Masayuki Okabe
Toyohashi University of Technology
Tempaku 1-1, Toyohashi, Aichi, Japanokabe@imc.tut.ac.jp

Seiji Yamada
National Institute of Informatics
Chiyoda, Tokyo, Japanseiji@nii.ac.jp

Abstract— This paper proposes a novel constrained clustering method that is based on a graph-cut problem formalized
by SDP (Semi-Definite Programming). Our SDP approachhas the advantage of convenient constraint utilization compared with conventional spectral clustering methods. The
algorithm starts from a single cluster of a whole dataset
and repeatedly selects the largest cluster, which it thendivides into two clusters by swapping rows and columns ofa relational label matrix obtained by solving the maximum
graph-cut problem. This swapping procedure is effective
because we can create clusters without any computationallyheavy matrix decomposition process to obtain a cluster label
for each data. The results of experiments using datasetsfrom the ODP and WebKB corpus demonstrated that our
method outperformed other conventional and the state of
the art clustering methods in many cases. In particular, we
discuss the difference between our approach and anothersimilar one that uses the same SDP formalization as ours.
Since the number of constraints used in the experiments is
relatively small and can be practical for human feedback, we
consider our clustering provides a promising basic method
to interactive Web clustering.

from pre-given constraint information according to theframework of the transductive learning.
Our method is based on the graph-cut problem. Although graph-cut based clustering (e.g., spectral clustering) is a well known approach and many methods
have been proposed so far [8], [9], their solutions aremostly based on the graph spectrum obtained by eigen
decomposition, which requires complicated processes to
add in the constraint information. Our approach is to solve
it as a semi-definite programming (SDP) problem. The
advantage of SDP is that we can naturally incorporate
constraints without any complicated processing and do
not need any specific objective functions (e.g., normalizedcut) to avoid a trivial solution (as is the case with manyother spectral clustering methods).
In terms of formalization, our problem is the sameas Li’s [10] or Hoi’s [11], although the introduction iscompletely different. The most critical difference is theinterpretation of the SDP solution. They interpret thesolution as a kernel matrix and use it for multi-classclustering, while we interpret it as a label matrix (asdescribed above) and use it for two-class clustering. As
we will show in the experiments, our two-class clustering
approach performs better than the multi-class clustering
approach. Our approach is based on the divide and conquer algorithm. It starts from a single cluster of a complete
dataset and repeatedly selects the largest cluster, which
it then divides into two clusters until we get the target
numbers of clusters. In each iteration, we obtain relationallabels for all data pairs from the solution of the SDP
problem. We then use the label matrix to create clusters
by swapping rows and columns to reduce the clusters’label distribution entropies. This swapping procedure isvery effective because we can create clusters without any
computationally heavy matrix decomposition processing.
In summary, we propose a constrained clustering
method that has the following features.
• Clustering is performed based on the relational labelsof all data pairs that are obtained by solving agraph-cut problem formalized by semi-definite programming. Our SDP approach has the advantage
convenient constraint utilization compared with conventional spectral clustering methods.
• The interpretation of the obtained matrix is different
from Li and Hoi’s approaches, although the problem

I. I NTRODUCTION
Clustering has long been one of the most essential andpopular techniques in data mining [1]. It is used not only
for visualization of huge data sets but also for image
segmentation [2], medical applications, recommendation
systems, and so on.
Constrained clustering is a semi-supervised learning
approach that utilizes pre-given knowledge about data
pairs to improve normal clustering accuracy [3], [4].
The knowledge used is generally of two simple types:
a constraint about data pairs that must be in the samecluster, and a constraint about data pairs that must be ina different cluster. These are usually called must-link andcannot-link, respectively.
Recent research about distance metric learning interprets the constraint information as the distance or kernel
value of data pairs and tries to produce a new distancemeasure or kernel matrix for a whole dataset to ensure
the distance of must-link is small and the distance of
cannot-link is large [5], [6], [7]. In this research, we do
not interpret the constraint as a distance or kernel value
but rather as a relational label that indicates whether data
pairs should be in the same cluster or not. Our objective isto predict the correct label for each data pair (not for eachindividual piece of data) by using sample labels converted© 2012 ACADEMY PUBLISHER
doi:10.4304/jetwi.4.1.43-50

44

JOURNAL OF EMERGING TECHNOLOGIES IN WEB INTELLIGENCE, VOL. 4, NO. 1, FEBRUARY 2012

formalization is similar. They use the matrix as akernel matrix for one-time multi-class clustering,
while we use it as binary label matrix for divideand conquer-based two-class clustering.
These advantages make constrained clustering more efficient, especially in the case of small number of constraints
such as interactive web clustering like [12].
The rest of the paper is organized as follows. First we
explain the standard maximum graph cut problem andits solution by semi-definite programming relaxation in
Section II. Next, we describe our clustering algorithm,
which is based on the approximate solution of the SDP.
We describe the entire clustering procedure including
binarizing and swapping of the solution matrix in Section
III. Section IV shows the results of experiments performed
using datasets from the ODP and WebKB corpus. We
discuss our methods in Section V, and finally we conclude
our work in Section VI.

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

Figure 1. Cannot-link is not applicable in divide and conquer approach

maximum cut problems. While there are constrained versions of spectral clustering methods, we adopt a different
approach, solution by semi-definite programming (SDP),
which is practically easier to use because it can handle
constraints intrinsically.

II. C ONSTRAINED G RAPH C UT P ROBLEM
Graph-cut formalization is a powerful clustering approach that many algorithms have adopted. In this section,
we first formalize the maximum cut problem and thenintroduce a solution by semi-definite programming.
A. Maximum Cut Problem
The objective of the problem is to divide a graph into
two parts as its cut amount reaches the maximum. Moreformally, consider a graph G = (V, E), where V is a setof vertices and E is a set of edges. The problem is to findpartitioning (V1 , V2 ) such as V1 ∪V∑
2 = V and V1 ∩V2 = φ
and a maximum cut amount ofi∈V1 ,j∈V2 wij . Here,wij is the weight of an edge between data i ∈ V1 anddata j ∈ V2 . We decide on a “maximum” cut when wij
is defined by some distance (e.g., Euclid distance). In
contrast, if wij is defined by some similarity (e.g., Gausskernel), the “minimum” cut is appropriate.
By introducing a cluster label variable ui for eachvertex, we can formalize the maximum cut problem asfollows.
Maximum Cut Problem
maximize1 ∑ ∑wij (1 − ui uj )4

B. Formalization by SDP
Semi-definite programming is a kind of convex optimization that is used to relax several optimization
problems such as combinatorial optimization, 0-1 integer
programming, and non-convex quadratic programming.
Since the maximum cut problem is an example of 0-1
integer programming, SDP can also relax it.
For the standard formalization of SDP, we transformthe above objective function into a matrix representation
with a weight matrix W and a matrix X whose element
is the product of ui and uj .
∑ ∑wij (1 − ui uj ) =(diag(W e) − W ) • X

i∈V1 j∈V2= L•X
X = uT uu = (u1 , u2 , ..., un ),n = |V |L is the graph Laplacian matrix and e is a vector whose
elements are all one. As a final step, we add must-link
constraints to formalize the constrained maximum cut
problem as follows.

i∈V1 j∈V2subject to

u2k = 1 (k ∈ V ){+1 (k ∈ V1 )uk =−1 (k ∈ V2 )According to the standard method of spectral clusteringor segmentation by the random walk model, we can solve
this problem with the method of Lagrange multipliers.
The ui labels are obtained as eigen vectors corresponding
to the second largest eigen value.
Our aim is to incorporate given constraints into theabove problem and find a method to solve constrained© 2012 ACADEMY PUBLISHER

Maximum Cut Problem with SDP Relaxation
maximizesubject toL•XEii • X = 1,
Eij • X = 1,
XO(i = 1 ∼ n)(i, j) ∈ M

Eij is an n × n matrix in which only the (i, j) element
is 1, and all others are 0. M is a set of must-link.

JOURNAL OF EMERGING TECHNOLOGIES IN WEB INTELLIGENCE, VOL. 4, NO. 1, FEBRUARY 2012



                45!!!                                                                                                                                                             

  

  

                                                                                                                                                                                                           ! !
 !                                                                                        

# " %!$#       (a) Grouping patterns       (b) Sort pattern groups

Figure 2. Clustering process using label matrix                            S1

                                          S2

                            6:              

7: Let C = D0
8: for i = 1 to K-1 do                            S3

                            S4                                          Figure 3. Clustering Boundary

Although available constraints are not limited to mustlink, meaning we can also use cannot-link, it is very
difficult to select applicable cannot-links during multiclass clustering because the partitioning order determinedin the graph cut process is usually unpredictable inadvance. Figure 1 gives an idea of the difficulty of using
cannot-link. There are three data in the figure - a, b, c and cannot-link is applicable only at the second cut. It
cannot be used at the first cut because b and c are in thesame cluster at that time.
There are several freely available SDP solvers that we
can use to obtain an approximate solution X̃. Although
we need to decompose X̃ to obtain partitioning label u,
we found a way to complete partitioning by using only
X̃. We explain this method in the next section.
III. C LUSTERING THROUGH S WAPPING ROWS AND
C OLUMNS IN A L ABEL M ATRIXIn this section, we describe a concrete partitioning
procedure using matrix X̃, which is given as the SDP
solution, and then an entire clustering with an iterativedual-partitioning process.
As described in the previous section, we solve themaximum cut problem with relaxed SDP, so the elements© 2012 ACADEMY PUBLISHER

Algorithm 1 Constrained Iterative Graph Cut Clustering
1: Input: D0// Dataset
2:
W// Weight Matrix
3:M// Must-Link Set
4:K// Number to be Clustered
5: Output: C = {D1 , D2 , ..., DK }// K clusters

Select the largest cluster Dtmax
Extract a subset of must-link constraints Mtsub
related to Dtmax
11:
Input Dtmax and Mtsub to SDP solver and get
divided clusters {Dt1 , Dt2 }12:
Subtract Dtmax from C
13:
Add {Dt1 , Dt2 } to C
14: end for9:10:of X̃ are assigned a real value ranging from -1 to 1.
We therefore decided on a different approach in which
we first binarize X̃ with 0-1 values, then swap rows andcolumns to maximize the evaluation measure, and finallydetermine the partitioning border.
The concrete procedures are as follows.
1) Each element of X̃ is binarized as follows.
{
1, if X̃ij ≥ 0
X̃ij =
0, if X̃ij < 0
The value does not matter because we treat 0 and
1 as a character in the following steps.
2) For each row, treat the column’s value as a character (0 or 1) and make a string (or pattern) byconcatenating each character in the original order.
Next, make groups of the same string (select a
representative of each kind of string). Figure 2(a)illustrates this procedure.
3) Determine the most frequent string s0 , and calculate
the Hamiltonian distance between s0 and the otherstrings. Next, align other strings in descending orderof the Hamming distance. String s1 is the most

46

JOURNAL OF EMERGING TECHNOLOGIES IN WEB INTELLIGENCE, VOL. 4, NO. 1, FEBRUARY 2012

TABLE I.
D IRECTORIES USED IN ODP CORPUS
No.
1
2
3
4
5
6
7
8
9
10
11
12

Directory
Anomalies and Alternative Science
Science in Society
Environment/Water Resources
Astronomy
Technology/Structural Engineering
Agriculture
Biology/Genetics
Social Sciences/Linguistics
Physics
Earth Sciences
Math
Chemistry

TABLE III.
W EB KB CORPUS
#data
47
45
42
24
24
19
16
15
15
11
10
6

TABLE II.
DATASETS IN ODP CORPUS
Datasetodp odd
odp even
odp small
odp all

#data
154
120
92
274

#cluster
6
6
7
12

similar to s0 . Figure 2(b) illustrates this procedure.
4) Determine the partitioning boundary according to
the following measure.
F (i, j) =4∑

−pSi log(pSi )−(1−pSi ) log(1−pSi )k=1(i, j) represents the partitioning boundary. If wepartition the above aligned matrix in the boundary
between i’s row and j’s row (i.e., also in theboundary of i’s column and j’s column ), there
are four partitioned areas in the matrix. pk0 and pk1
are the probabilities of 0 and 1, respectively, thatappears in the area k. Thus, F (i, j) is the sum of
the entropy in four areas when partitioned between
ith and jth row (and column). The more clearlypartitioned, F (i, j) becomes lower.
5) Determine the boundary at the lowest F (i, j).
This is a heuristic method because the original problem
is a combinatorial one and practically intractable. Thereis no guarantee for obtaining global optimum. However,experimentally it works well, as described in the next
section.
We describe an entire procedure of our clustering
algorithm in Algorithm 1.
IV. E XPERIMENTS
A. Datasets
We evaluated our proposed method on two Web page
corpora. One is a ODP corpus, a set of web pages
extracted from the Open Directory Project (ODP)1 byourselves. We selected 12 subdirectories from the the“Science” top directory, and downloaded top pages of the
1 http://www.dmoz.org/© 2012 ACADEMY PUBLISHER

Datasetstudent
facultystaff
courseproject
other

#data
558
153
46
244
86
3033

#cluster
4
4
4
4
4
4

Web sites listed in each directory. We removed tags andstopwords from the pages, and stemmed each word. The
summary of each directory is listed in Table I.
We treated each directory as a target cluster, andmade four datasets using those clusters. One is a dataset(odp all) using all the directories in the corpus. The othertwo (odp odd and odp even) are half size of odp all. The
directories of odp odd and odp even are selected fromthe odd and even number ones in Table I, respectively.
The final one (odp small) is a set of small directories(No.6∼12) that include under 20 data. We summarize
about datasets in Table II.
We also used the WebKB corpus 2 . This corpus consistsof seven datasets, and each one has fixed five clusters
named “Cornel”, “Texas”, “Washington”, “Wisconsin”
and “misc”, respectively. Since the last “misc” cluster
consists of Web pages from miscellaneous universities
and lacks unity, we removed it from each dataset. We also
removed department dataset because it has only one pagefor each cluster. The datasets are summarized in Table III.
We applied the same preprocessing as ODP corpus andevaluated each method on all the datasets.
B. Compared methods
We compared our proposed method with other threemethods. The notation and brief introduction of eachmethod is listed below.
GCUT This is our proposed method. We calculated
the Euclid distance for the weight of the graphedge, which is indicated as wij in the maximum
graph cut problem in Section II. We used the
SDPT3 package 3 to solve SDP. The default
parameters are used for each run.
PCP PCP is one of the state of the art distancemetric learning methods proposed by Li [10].
It learns a kernel matrix using the same SDP
formulation with ours. The difference between
two methods lies in the usage of the solution
matrix. PCP uses it as a kernel matrix for kernel
k-means while ours uses it for iterative graphcut. The weight of the graph edge and theparameters for SDPT3 are the same with GCUT.
Since this method can use both must/cannotlink constraints, we conducted two trials. One
is the trial using only must-link constraints, theother uses both must/cannot-link constraints. the2 http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-20/www/data/
3 http://www.math.nus.edu.sg/ mattohkc/sdpt3.html

JOURNAL OF EMERGING TECHNOLOGIES IN WEB INTELLIGENCE, VOL. 4, NO. 1, FEBRUARY 2012

!#)"

47

!#)"

!#("

!#("
-./0"

!#'"

-./0"

!#'"

1.123456"!#&"

1.1236"
7089"

!#%"

1.123456"!#&"

1.1236"
7089"

!#%"

.:8"
!#$"

.:8"
!#$"

!"

!"
!"

$!"

%!"

&!"

'!"

(!"

)!"

*!"

+!"

,!" $!!"

!"

$!"

%!"

&!"

(a) odp odd

'!"

(!"

)!"

*!"

+!"

,!" $!!"(b) odp even

!#*"

!#($"
!#("

!#)"

!#'$"

!#("
-./0"

!#'"

-./0"

!#'"

1.123456"!#&$"

1.123456"!#&"

1.1236"!#&"

1.1236"

7089"

!#%"

.:8"
!#$"

!#%$"

7089"

!#%"

.:8"

!#!$"
!"
!"

$!"

%!"

&!"

'!"

(!"

)!"

*!"

+!"

,!" $!!"

!"
!"

%!"

&!"

'!"

(!"

$!"

)!"

*!"

+!"

,!" %!!"(d) odp all(c) odp small

Figure 4. Results of ODP corpus (horizontal axis is the number of constraints and vertical axis is NMI)

former is denoted by PCP(m) and the latter is
PCP(m/c).
ITML ITML is an another distance metric learning
method proposed by Jain [13]. It learns a transform matrix to calculate desired distance. Since
this method follows online learning process,we tuned its learning parameter η by selecting
the best value from 0.1 to 1.0 with 0.1 steps.
Clustering is done by normal k-means withlearned Euclid distance. Since cannot-link on
this method showed terrible performance deterioration, we applied only must-link for it.
CKM CKM is the constrained k-means clustering
algorithm (called COP-Kmeans) proposed by
Wagstaff [14]. Since cannot-link often caused
deadlock and stopped all the algorithm procedure, we applied must-link only as well as
ITML.

C. Other settings
We use normalized mutual information (NMI) to measure the clustering accuracy. NMI is calculated by the© 2012 ACADEMY PUBLISHER

following formula.
NMI(C, T ) =I(C, T )√H(C)H(T )where C is the set of clusters returned by each algorithm
and T is the set of true clusters. I(C, T ) is the mutual
information between C and T , and H(C) and H(T ) are
the entropies.
Constraints are selected randomly. We changed thenumber of constrains from 0 to 100 with 10 steps. For
each number of constraints, we selected 10 different setsof constraints and used the same sets for each method.
The NMI is calculated as the average value of those 10
sets.
D. Results
Figure 4 is the results of the ODP corpus. The horizontal axis is the number of constraints and the vertical axis
is the value of normalized mutual information (NMI).
In this corpus, GCUT outperformed other methods inall the datasets, especially at the points where the numberof constraints is small.
PCP(m/c) showed comparable or slightly better performance at some points in the odp odd, the odp even and48

JOURNAL OF EMERGING TECHNOLOGIES IN WEB INTELLIGENCE, VOL. 4, NO. 1, FEBRUARY 2012

!#($"

!#,"
!#+"

!#("

!#*"

!#'$"

!#)"

-./0"

!#'"

-./0"

!#("

1.123456"!#&$"

1.123456"!#'"

1.1236"!#&"

1.1236"

!#&"

7089"

!#%$"

7089"

!#%"

.:8"

!#%"

.:8"

!#!$"

!#$"

!"

!"
!"

$!"

%!"

&!"

'!"

(!"

)!"

*!"

+!"

!"

,!" $!!"

%!"

&!"

'!"

(!"

$!"

)!"

*!"

+!"

,!" %!!"(b) faculty(a) student

$"

!#*"

!#,"

!#)"

!#+"
!#*"

-./0"

!#("

-./0"

!#)"

1.123456"!#'"

1.123456"!#("

1.1236"!#'"

1.1236"

!#&"

7089"

!#&"
.:8"

!#%"

7089"
!#%"

.:8"

!#$"

!#$"
!"

!"
!"

$!"

%!"

&!"

'!"

(!"

)!"

*!"

+!"

,!" $!!"

!"

$!"

%!"

&!"

(c) staff

'!"

(!"

)!"

*!"

+!"

,!" $!!"(d) course

!#*"

!#($"

!#)"

!#("

!#("

-./0"

!#'"

1.123456"
1.1236"

!#&"

7089"
!#%"

-./0"

!#!'"

1.123456"!#!&"

1.1236"
7089"

!#!%"

.:8"

.:8"
!#!$"

!#$"
!"

!"
!"

$!"

%!"

&!"

'!"

(!"

)!"

*!"

+!"

,!" $!!"(e) project

!"

(!"

$!"

)!"

%!"

*!"

&!"

+!"

'!"

,!" (!!"(f) other

Figure 5. Results of the WebKB corpus (horizontal axis is the number of constraints and vertical axis is NMI)

odp small datasets though it remained the second best or
worse in other points. PCP(m) is slightly worse than PCP.
CKM outperformed other methods without GCUT in the
odp all dataset. ITML did not show the good results inthis corpus.
Figure 5 shows the results of the WebKB corpus. The
meaning of the horizontal and vertical axis is the sameas the ODP corpus. In this corpus, GCUT indicated thebest results in four datasets. The results in the other two
datasets is comparable and slightly worse than the othermethods. GCUT showed clearly better performance especially in the student and “other” datasets whose numberof data is relatively larger than others. The performance© 2012 ACADEMY PUBLISHER

of all methods in “other” dataset is low because the topic
of this dataset is diverse and does not have unity as acluster. GCUT also showed better performance than othermethods in the staff and project datasets whose number ofdata is relatively small. In those datasets, performance gap
between GCUT and others widened as the number of constraints increased. PCP showed comparable and slightly
better performance in the course and faculty datasets. We
did not observe significant difference between PCP(m/c)
and PCP(m) in this corpus. The performance of CKM
and ITML remained worse than GCUT and PCP in all
the datasets.
The performance of GCUT as well as all the other

JOURNAL OF EMERGING TECHNOLOGIES IN WEB INTELLIGENCE, VOL. 4, NO. 1, FEBRUARY 2012

methods does not grow monotonically and sometimes
drops despite the increase of constraints. This is because
the effectiveness of constraints are generally quite uneven.
Some sets of constraints may work better for somemethods. On the other hand some sets may bring negative effect (e.g. because of must-link constraints related
outliers).
V. D ISCUSSIONS
Our proposed clustering method (GCUT) repeatedly
divides the largest cluster into two sub-clusters until the
given number of clusters is obtained. This procedure
delivers a good property compared to a one-time multiclass clustering approach represented by PCP as shown in
the experiments. The results indicate that we can obtain
more accurate clusters if we interpret the SDP problem
described in Section II as a constrained graph cut problem
and use its solution for iterative two-class clustering.
As described in Section I, our method uses the same
SDP formulation as PCP. However the purpose, derivationand interpretation of the solution for our method isdifferent from PCP. In this section, we explain a brief
introduction of PCP and clarify the difference from our
method, and then discuss the cause of the experimental
results in the previous section.
PCP is a method to produce a kernel matrix of a dataset
by projecting original feature vectors to a higher dimensional space. Constraints are used as desired inner productvalues for some selected data pairs in the projected feature
space. In order to propagate the effect of the constraints
to other data pairs, Li et al. formulated an optimization
problem according to a well-known regularization inspectral graph theory.
Optimization Problem derived in PCP
1 ∑φ(xi ) φ(xj ) 2
wi,j || √− √ ||F
2 i,j=1
dii
djjnminimizesubject to< φ(xi ), φ(xi ) >F = 1 i = 1, 2, ..., n< φ(xi ), φ(xj ) >F = 1 ∀ (xi , xj ) ∈ M< φ(xi ), φ(xj ) >F = 0∀(xi , xj ) ∈ C

Here, φ(xi ) is a feature vector in the projected space,w∑ij is an initial similarity between data i and j, dii isk wik , and < ·, · >F indicates inner product calculationin the projected space. The objective function of the above
problem can be finally transformed into the formula L•X
that is the same one as described in Section II.
In this way, GCUT and PCP solve the same SDP
problem except for the use of cannot-link. However theirderivations of the problem are different from each otherlike following.
1) PCP places the SDP problem as a basis to define
a proximity measure in a dataset. Thus it solves a
SDP problem only once for a clustering trial. The
proximity measure is actually got as a kernel matrix.
© 2012 ACADEMY PUBLISHER

492) The SDP problem in GCUT is a constrained graphcut clustering problem itself. Thus it iterates tosolve SDP k − 1 times. k is a target number ofclusters.
Though the reason for the performance increase of
GCUT compared with PCP superficially seems to be
multiple SDP executions, it is more important that thederivations of the SDP problem in both methods aredifferent. GCUT derives from a constrained graph cut
problem while PCP derives from a problem to define adesired proximity measure.
VI. C ONCLUSIONSIn this paper, we proposed a constrained clustering
method that is based on a graph-cut problem formalized
by semi-definite programming and deterministic iterative
two-class partitioning approach. While graph-cut based
clustering is a particularly promising way to improve
conventional techniques like k-means method, few methods have been proposed, which can naturally incorporate
constraint like must-link.
Our method has the advantages of more convenient
constraint incorporation compared to other graph-cut
based method such as spectral clustering and can utilize SDP’s solution matrix more appropriately comparedwith other SDP-based methods. Since our method adopts
deterministic clustering approach unlike k-means using
random seeds, the performance is stable and robust to outliers. These advantages were clearly demonstrated throughexperiments using many datasets from two Web corpus.
Results showed that our proposed clustering method constantly outperformed conventional methods in many cases
and utilized constraints effectively.
A few problems still remain in this work. First, weneed to investigate how the constraint quality influences
the clustering. This is an active learning problem andin the future we aim to develop a new active-learningtechnique by utilizing the properties of our clustering
methods. Second, we need to develop a constraint propagation method to improve clustering accuracy even if thenumber of constraint is small. There are already various
propagation methods in place [15], but we need something
more powerful to improve the effectiveness of very small
constraints.
The advantages of our proposed clustering is efficiency,
especially in the case of small number of constraints.
Thus we are planning to apply this clustering method tointeractive (Web) clustering with GUI [12].
R EFERENCES[1] M. Kantardzic, Data Mining: Concepts, Models, Methods,
and Algorithms. John Wiley & Sons, 2003.
[2] Z. Wu and R. Leahy, “An optimal graph theoretic approachto data clustering: Theory and its application to image
segmentation,” IEEE Transactions on Pattern Analysis andMachine Intelligence, vol. 15, pp. 1101–1113, 1993.

50

JOURNAL OF EMERGING TECHNOLOGIES IN WEB INTELLIGENCE, VOL. 4, NO. 1, FEBRUARY 2012[3] S. Basu, A. Banjeree, E. Mooney, A. Banerjee, and R. J.
Mooney, “Active semi-supervision for pairwise constrained
clustering,” in In Proceedings of the 2004 SIAM International Conference on Data Mining (SDM-04, 2004, pp.
333–344.
[4] O. Chapelle, B. Scholkopf, and A. Zien, Semi-Supervised
Learning. The MIT Press, 2006.
[5] S. Shwartz, Y. Singer, and A. Y. Ng, “Online and batchlearning of pseudo-metrics,” in Proceedings of the 21stInternational Conference on Machine Learning, 2004, pp.
94–101.
[6] W. Tang, H. Xiong, S. Zhong, and J. Wu, “Enhancing semisupervised clustering: A feature projection perspective,”in Proceedings of the 13th International Conference on
Knowledge Discovery and Data Mining, 2007, pp. 707–
716.
[7] K. Q. Weinberger and L. K. Saul, “Distancemetric learning for large margin nearest neighborclassification,” J. Mach. Learn. Res., vol. 10,
pp. 207–244, June 2009. [Online]. Available:
http://portal.acm.org/citation.cfm?id=1577069.1577078[8] S. X. Yu and J. Shi, “Segmentation given partial grouping
constraints,” IEEE Transactions on Pattern Analysis andMachine Intelligence, vol. 26, no. 2, pp. 173–183, 2004.
[9] A. Ng, M. Jordan, and Y. Weiss, “On spectral clustering:
Analysis and an algorithm,” in Neural Information Processing Systems, no. 14, 2001, pp. 849–856.
[10] Z. Li, J. Liu, and X. Tang, “Pairwise constraint propagation by semidefinite programming for semi-supervisedclassification,” in Proceedings of the 25th international
conference on Machine learning, 2008, pp. 576–583.
[11] S. C. H. Hoi, R. Jin, and M. R. Lyu, “Learning nonparametric kernel matrices from pairwise constraints,” in Proceedings of the 24th international conference on Machinelearning, 2007, pp. 361–368.
[12] M. Okabe and S. Yamada, “An interactive tool for human active learning in constrained clustering,” Journal of
Emerging Technologies in Web Intelligence, vol. 3, no. 1,
pp. 20–27, 2011.
[13] P. Jain, B. Kulis, I. S. Dhillon, and K. Grauman, “Online
metric learning and fast similarity search,” in Proceedingsof Neural Information Processing Systems, 2008, pp. 761–
768.
[14] K. Wagstaff and S. Roger, “Constrained k-means clusteringwith background knowledge,” in Proceedings of the 18th
International Conference on Machine Learning, 2001, pp.
577–584.
[15] D. Klein, S. D. Kamvar, and C. D. Manning, “Frominstance-level constraints to space-level constraints: Making the most of prior knowledge in data clustering,”
in Proceedings of the 19th International Conference on
Machine Learnning, 2002, pp. 307–314.
Masayuki Okabe is an assistant professor at Toyohashi University of Technology. He received B.S. (1996) degree from Soka
University and M.S. (1998) and the Ph.D. (2001) degrees from
Tokyo Institute of Technology. His research interests include
information retrieval, machine learning and data mining. He isa member of The Japanese Society for Artificial Intelligence.
Seiji Yamada is a professor at the National Institute of Informatics. Previously he worked at Tokyo Institute of Technology.
He received B.S. (1984), M.S. (1986) and the Ph.D. (1989)
degrees in artificial intelligence from Osaka University. His
research interests are in the design of intelligent interaction
including Human-Agent Interaction, intelligent Web interaction
and interactive machine learning. He is a member of IEEE,
AAAI, ACM, JSAI, IPSJ and HIS.
© 2012 ACADEMY PUBLISHER