Okabe, M. and Yamada, S.

Paper:

Active Sampling for Constrained Clustering
Masayuki Okabe∗ and Seiji Yamada∗∗∗ Information and Media Center, Toyohashi University of Technology

1-1 Tempaku, Toyohashi, Aichi 441-8580, Japan
E-mail: okabe@imc.tut.ac.jp∗∗
National Institute of Informatics, SOKENDAI
2-1-2 Chiyoda, Tokyko 101-8430, Japan[Received October 15, 2013; accepted January 31, 2014]

Constrained clustering is a framework for improving clustering performance by using constraints aboutdata pairs. Since performance of constrained clustering depends on the set of constraints used, a method isneeded to select good constraints that promote clustering performance. In this paper, we propose an active
sampling method working with a constrained cluster
ensemble algorithm that aggregates clustering resultsthat a modified COP-Kmeans iteratively produces bychanging the priorities of constraints. Our method follows the approach of uncertainty sampling and measures uncertainty using variations of clustering results
where data pairs are clustered together in some results but not in others. It selects the data pair to belabeled that has the most variable result during cluster ensemble process. Experimental results show that
our method outperforms random sampling. We further investigate the effect of important parameters.

Keywords: active learning, constrained clustering, cluster ensemble

1. Introduction
Clustering is known to be a basic technique in the fieldof information retrieval or data mining that is applied
to tasks such as image segmentation [1] and topic analysis [2]. There have been vigorous studies to enhanceclustering performance by using labeled data pairs in theframework of constrained clustering [3, 4].
Constrained clustering is a semi-supervised learningtechnique that uses labeled and unlabeled data to enhancelearning performance. Constrained clustering is different from normal clustering in the use of constraints aboutsome data pairs where each data item of a pair is constrained about cluster assignment. Such constraints areof two kinds, usually called must-link and cannot-link.
Must-link is a constraint for a data pair that must be in
the same cluster, and cannot-link is a constraint for a data
pair whose halves must be separated from each other.
Several methods have been proposed to utilize such
constraints to improve clustering performance. One

232

method introduced constraint to a k-means algorithm, forexample, to reduce erroneous data grouping [5], and another method used it to create a better distance measure or
kernel matrix [6–10].
Although the use of constraints is an effective approach, we find problems in preparing constraints. One
problem is the efficiency of the process. Because constraints must be manually labeled must-link or cannotlink, the user cognitive cost seems very high. We must
help users cut down on such labeling cost. Another problem is the effectiveness of prepared constraints. Manyexperimental results in recent studies have shown thatclustering performance does not improve monotonically– and sometimes may even deteriorates – as the number
of applied constraints increases [8, 10, 11]. The degreeof performance improvement depends on the quality of
constraints, not on the quantity. These results imply that
constraints are not all useful and that some are effective
but others are not effective – or even may be harmful tothe clustering. We also must help users to select only effective constraints that improve clustering performance.
These problems are solved by the active learning framework [12] that automatically selects constraint candidates
expected to be useful.
We propose an active sampling method to select a data
pair that is expected to be the most effective if its true constraint label, or must/cannot-link, is given. Our method isbased on a bagging-based cluster ensemble technique [13]and constrained k-means with a random data assignment
order. This realizes a cluster ensemble framework thatcreates partially coherent data groups from clustering iteration and integrates them into a set of final clusters.
Cluster variation is created by changing the data assignment order in a constrained k-means algorithm that is a
modified version of COP-Kmeans [5]. The original COPKmeans algorithm tends to create inconsistent clusters because results depend significantly on its data assignment
order, which is generally undecidable, thus we use such
behavior to produce diversity for the cluster ensemble.
Once we produce a diversity of clustering results, weobserve the diversity of a data pair to be clustered together(or not) during the cluster ensemble process. We regard
diversity as an uncertainty sampling measurement [14]that is one of major criteria for active learning [15] to se-

Journal of Advanced Computational Intelligenceand Intelligent Informatics

Vol.18 No.2, 2014

Active Sampling for Constrained Clustering

Algorithm 1 Cluster Ensemble
1: INPUT: Data X = {x1 , . . . , xn },2:Constraints S = {(i1 , j1 , y1 ), . . . , (im , jm , ym )},3:
4:

Priorities P = {p(i1 , j1 ) , . . . , p(im , jm ) },Bagging steps T

5: OUTPUT: Clusters C = {C1 ,C2 , . . . ,Ck }6: for t = 1 to T do
7:
8:
9:

Randomize priorities P for constraints S.
Run modified COP-Kmeans procedure (Algorithm 2).
Create kernel matrix K t from the above clusteringresult. 1
if xi and x j belong to the same cluster
K t (i, j) =−1 if xi and x j belong to different clusters• It produces a clustering result regardless of whether

10: Calculate final kernel matrix K.
Tt

it fails to satisfy some constraints.

K = ∑K• It utilizes constraint priorities that are continuously

t=1

11: Run a kernel k-means algorithm with K, and return

final set of clusters C.

lect data to be labeled. In this research, we propose an
active sampling method that follows the approach of uncertainty sampling and measures uncertainty using variations in clustering results where a data pair is clustered
together in some results but not in others. It selects thedata pair to be labeled that has the most variable results
during the cluster ensemble process.
This paper is organized as follows. We first introduce
a constrained clustering algorithm that we consider an active sampling method in Section 2. We then propose an
active sampling method based on the constrained clustering algorithm in Section 3. Section 4 presents experimental results for six benchmark datasets. We further discuss
the effect of important parameters of our proposed method
in Section 5. Section 6 presents conclusions.

2. Constrained Clustering Algorithm
In this section, we introduce a constrained clustering algorithm that we consider an active sampling method. Thisalgorithm consists of a bagging-based cluster ensemble
technique and modified COP-Kmeans with a random dataassignment order.
Algorithm 1 shows the cluster ensemble procedure
based on a bagging process that is a well-known ensemble learning technique that aggregates different patterns
of predictions produced by a weak learner. In this case,the modified COP-Kmeans works as a weak learner that
produces diverse clustering results with some moderatequality. These results are then aggregated in the form of akernel matrix. Since each K t is positive semidefinite (Appendix A), linear combination K is also positive semidefinite. We run a kernel k-means using the aggregated kernel
Vol.18 No.2, 2014

matrix to get the final clustering result.
A clustering result produced by the modified COPKmeans in each bagging step t is transformed as a kernel
matrix K t in which each element corresponds to a data
pair. They are labeled with +1 or −1 to indicate whether
the corresponding data pair belongs to the same cluster ornot. From the point of the bagging framework, the modified COP-Kmeans works as a weak learner to predict alabel, or must/cannot-link, of each data pair using constraints as training examples. The quality of a clusteringresult depends on label prediction accuracy, thus we intend to increase accuracy using bagging that expands theperformance of a weak learner.
Algorithm 2 lays out the entire modified COP-Kmeans
procedure. Our modified COP-Kmeans algorithm has thefollowing refinements compared to the original one:

controlled by the bagging process in order to decide
the data assignment order in clustering.
The order of data assignment in COP-Kmeans is usually
decided at random. Our modified algorithm decides theorder by sorting constraint priorities so that a constraint
with higher priority is more likely to be satisfied than thatwith lower priority because the likelihood of constraint
satisfaction generally increases if it is considered earlier
than other constraints. Our algorithm uses this empiricalbut practically useful heuristic to decide the order. Although it follows the basic standard k-means algorithm
procedure [5], its data assignment process is rather complicated because we introduce the concept of priority foreach data pair to produce, in turn, the diversity of clustering results.
There are two main procedures in the modified COPKmeans clustering loop. The first is a procedure for assigning unconstrained data to the nearest cluster centers,
which follow the standard k-means algorithm. The second is a procedure for assigning constrained data to thenearest cluster centers. This procedure has many conditional branches because we must consider the assignmentof two data in a constrained data pair at the same time. To
do so, we utilize the priority given for constraints to createclustering diversity. Conditional branches are caused forthe following reasons:• We consider whether each data of a pair has alreadybeen assigned. Since some data is restricted by morethan one constraint, one or both data may have already been assigned. We must prepare proceduresfor such conditions.
• We must consider the type of constraint. Dependingon the situation above, we prepare different procedures based on the type of constraint the data pairhas.
Concrete procedures about such conditions are given inlines 8 to 36 in Algorithm 2.

Journal of Advanced Computational Intelligenceand Intelligent Informatics

233

Okabe, M. and Yamada, S.

Algorithm 2 modified COP-Kmeans
1: INPUT: Data X, Constraints S, Priorities P,
2:
R: No. of maximum repeats in K-means
3: OUTPUT: Clusters C
4: Select initial cluster centers
5: for r = 1 to R do
6:
Sort constraints in descending order according to P.
7:
Assign constrained data pairs (xi , x j ) to cluster centers insorted order according to the following procedure.
8:
9:

10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:

if Both of (xi , x j ) are not assigned yet thenLet ci , c j be nearest cluster centers for xi and x j respectively, then let d(xi , ci ), d(x j , c j ) be distances their nearest cluster centers.
if (xi , x j ) is constrained by must-link thenif d(xi , ci ) < d(x j , c j ) thenAssign xi and x j to ci .
else
Assign them to c j .
else if (xi , x j ) is constrained by cannot-link thenif ci = c j thenAssign xi to ci , x j to c j , respectively.
else
if d(xi , ci ) < d(x j , c j ) thenAssign xi to ci , x j to the second nearest center.
else
Assign x j to c j , xi to the second nearest center.
else if xi has been already assigned and x j has not been yet
assigned thenLet ci be cluster center to which xi is assigned.
if xi and x j are constrained by must-link thenAssign x j to ci .
else if xi and x j are constrained by cannot-link thenAssign x j to cluster center that is nearest to data andis different from ci .
else if xi has not been yet assigned and x j has already been
assigned thenLet c j be cluster center to which x j is assigned.
if xi and x j are constrained by must-link thenAssign xi to c j .
else if xi and x j are constrained by cannot-link thenAssign xi to cluster center that is nearest to data andis different from c j .

35:
36:

else if Both of (xi , x j ) are already assigned then
Even if the constraint about (xi , x j ) is not satisfied, theassignment process will continue.

37:

Assign rest of data that are not constrained to their nearest
cluster centers.

38:

if Clustering result does not change from previous one
then
Return result and exit.
else
Update cluster centers and go to next step.

39:
40:
41:

pair that is expected to promote the most clustering performance if it is labeled. In this research, we propose
an active learning method using a concept of uncertainty
sampling [14]. Uncertainty sampling is a hypothesis thatindicates whether we should label data for which it is themost difficult for a classifier to infer the class. Applying
the hypothesis to our case of constrained clustering, weshould label the data pair that is the most difficult for ourclustering algorithm to infer whether the pair is must-link
or cannot-link.
To find such a data pair, we first must decide a criterion to quantify the “uncertainty” produced when ourclustering algorithm predicts the label of each data pair.
We determine criteria using the cluster ensemble property,
namely, the diversity of clustering results. Our clustering
algorithm is based on a bagging-based cluster ensemble
technique, which utilizes constraints to produce a variety
of clustering results. In the cluster ensemble process, adata pair may be clustered together in some results or be
assigned to different clusters in other results. We regard
such instability as an estimation of uncertainty and quantify behavior using entropy.
Let (xi , x j ) be a data pair and pi j be the probability thatthe data pair is grouped in the same cluster in a bagging
sequence. We estimate pi j using the number of times thatthe pair belongs to the same cluster during a sequence ofbagging steps.
T∑ lit j. . . . . . . . . . . (1)pi j ≈ p̃i j = t=1T
1 if (xi , x j ) is grouped in the same cluster
lit j =
0 if (xi , x j ) is grouped in different clusters
where T is the number of bagging steps.
Using estimate p̃i j , we calculate entropy Ei j for each(xi , x j ) as follows:
Ei j = − p̃i j log p̃i j − (1 − p̃i j ) log(1 − p̃i j ). . (2)(1 − p̃i j ) is the estimation of the probability that the data
pair is grouped in different clusters in a bagging sequence,thus Ei j expresses the uncertainty of the data pair to belabeled as must-link or cannot-link.
Once we calculate entropies for all candidate data pairs
to be labeled, we sort them in descending order and selectseveral top-ranked pairs from the list, then label them as
must-link or cannot-link using true labels, as summarizedin Algorithm 3.

4. Experiments
4.1. Datasets and Settings

3. Active Sampling for Constrained Clustering
We consider an active learning method based on thecluster ensemble introduced in the previous section. The
objective of our active learning method is to select a data234

We evaluated our proposed method using the six
datasets summarized in Table 1. Glass, wdbc and balance are from the UCI repository1 and tr11, tr12 and tr23
1. http://archive.ics.uci.edu/ml/

Journal of Advanced Computational Intelligenceand Intelligent Informatics

Vol.18 No.2, 2014

Active Sampling for Constrained Clustering

Algorithm 3 Active Sampling
1: INPUT:
2:
3:
4:

Initial constraints S = {(i1 , j1 , y1 ),. . . , (im , jm , ym )},U: No. of maximum repeats in Active sampling,
N: No. of data pairs to select

5: for u = 1 to U do
6:
7:
8:
9:
10:

Run cluster ensemble procedure (Algorithm1).
For each data pair (xi , x j ), calculate entropy Ei j .
Sort data pairs in descending order according to
Ei j .
Select N data pairs from the top of the sorted list.
Label those selected data pairs.
Add them to S.
Table 1. Datasets.

glass
wdbc
balance
tr11
tr12
tr23

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

are from the CLUTO datasets.2 For CLUTO datasets,
we made a feature vector by calculating and normalizing
tf·idf for each attribute.
We compared the following methods for constraint
sampling:• active: This is our proposed method. Our algorithm

starts from 10 randomly selected source constraints
and repeats active sampling until it gets 100 constraints. The number of constraints to add at active
sampling N is set to 10 in experiments.
• random: This method selects data pairs to be labeled

at random. Similar to active sampling, it starts from
10 source constraints and repeats random sampling
until it gets 100 constraints. Parameter N is also set
to 10.
Both methods are based on the constrained clustering algorithm described in Section 2. Bagging step T was set
to 100 in both cases. Distance metric we used in experiments was Euclidean distance.
We used normalized mutual information (NMI) to measure clustering accuracy. NMI was calculated by using thefollowing formula:I(C, T )NMI(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 mutual
2. http://glaros.dtc.umn.edu/gkhome/cluto/cluto/download

Vol.18 No.2, 2014

information between C and T and H(C) and H(T ) areentropies.
We prepared 10 sets of source constraints. In eachdataset, we run 10 trials for both methods by changing
source constraints. The final result is the average NMI of
10 trials.

4.2. Results
Figure 1 shows results. The horizontal axis indicatesthe number of constraints and the vertical axis indicates
NMI. Number of bagging steps T was set to 100 in bothcases. The number of constraints to be added in an active
learning step was set to 10.
Our active method showed better or comparable performance compared to random sampling method random inall datasets. For the three UCI datasets, active clearly outperformed random, especially for glass and wdbc, eventhough random showed little performance improvement
when increasing constraints. For three CLUTO datasets,
although we could not see any significant effect of active
sampling, active did not show lower performance in any
active sampling step.

5. Discussion
Our method has two parameters, N and T , that influence active sampling performance. N is the number of
constraints to add in an active sampling step. T is thenumber of bagging steps. In this section, we investigate
the effect of these parameters in more detail.

5.1. Effect of N
Figure 2 shows the effect of parameter N, which is thenumber of constraints to add in an active sampling step.
We test the values of parameters 1, 5, 10. A small numberof N needs more calculation time, however we expect abetter performance improvement because a smaller number of N has a great possibility of avoiding data pairs thatare not effective in improving clustering performance under the assumption of uncertainty sampling.
For three UCI datasets, results of N = 1 showed thebest performance. N = 5 results showed no significant improvement, however the number of promising data pairs isvery limited in experiments. We did not see any marked
change in CLUTO datasets.
5.2. Effect of T
Figure 3 shows the effect of parameter T , which is thenumber of bagging steps. By increasing T , we expect abetter estimation of p̃i j that directly influences the choiceof data pairs to be sampled.
Contrary to our expectations, parameter T did not haveany significant effect except for the UCI balance dataset.
For the balance dataset, the result of T = 300 showed thebest performance. Since the result of T = 500 showed
lower performance than T = 300, increasing T would notnecessarily produce a positive effect.

Journal of Advanced Computational Intelligenceand Intelligent Informatics

235

Okabe, M. and Yamada, S.

!



!
 

     
 









 













   















!

"









   









!

"









   (a) glass







!

"



   (b) wdbc

!



(c) balance


!

 









 

     


 














!

   

"

















!

"

















         (d) tr11(e) tr12(f) tr23

!

"



!



 

 



#





!





Fig. 1. Results (T = 100, N = 10).

#######















  





!

"









    

(a) glass





!

"





(b) wdbc





#





  

# ####




!

"









  

!

"



  

##





!

"

#  

(e) tr12(d) tr11







  













!



 





(c) balance






  

"





  

!



#













  





!

"



  

(f) tr23

Fig. 2. Effect of number of constraints to add N.

5.3. Entropy of Selected Data Pairs
We used entropy as a measurement for the uncertaintyof active sampling and investigated the average entropy
for selected data pairs in both active and random. Table 2 shows average and standard deviation of entropy for
100 selected data pairs during active sampling using bothmethods. The average value of active is clearly higher
236

than that of random in all datasets. In active, the value
becomes slightly higher as N increases in UCI datasets,
however there was no clear difference in CLUTO datasets.
This indicates that our proposed method is promising as
active sampling technique for constrained clustering eventhough it is not enough to narrow the numbers of data paircandidates to be selected.

Journal of Advanced Computational Intelligenceand Intelligent Informatics

Vol.18 No.2, 2014

Active Sampling for Constrained Clustering

 

!



 $   

 







 

"

  
















 $




 


 $ $  












  

(a) glass



!

"

#





(b) wdbc





 $





  

 $

!

 $ $ $ $


!

"

#







!

"

#



 



"



!

 



(c) balance






  

#





 

"



 $

 $ $ $


 










  

 

 $





!

"

#









   

(e) tr12(d) tr11





!

"

#



 

(f) tr23

Fig. 3. Effect of bagging steps number T .
Table 2. Selected constraint entropy.

ACTIVE (N = 10)
ACTIVE (N = 5)
ACTIVE (N = 1)
RANDOMglass
0.99±5.34e-06
0.99±8.37e-09
0.99±4.54e-10
0.10±0.06

wdbc
0.77±0.09
0.80±0.09
0.93±0.02
0.01±0.00

6. Conclusions

tr11
0.99±0.00
0.99±0.00
0.99±0.00
0.03±0.01

tr12
0.99±0.00
0.99±0.00
0.99±0.00
0.05±0.02

tr23
0.99±0.00
0.99±0.00
0.99±0.00
0.14±0.08

References:

In this paper, we have proposed an active sampling
method for constrained clustering that selects data pairs to
be constrained by using variations in clustering iteration.
This consists of a bagging-based cluster ensemble algorithm that integrates a sequence of clustering results produced by a modified COP-Kmeans with random ordereddata assignment. Using this base clustering, our sampling
method measures the uncertainty of the belongingness ofeach data pair, which is represented by entropy calculated
from the probability of belongingness. Experimental results showed that our method outperforms clustering withrandom sampling for six datasets. Even though improvement was not so significant, it should be noted that our
method achieved the required performance despite a relatively small set of constraints.
Active sampling for constrained clustering has not been
well developed, however our method is an option. We will
investigate the behavior of the method and test it on manyother datasets.

Vol.18 No.2, 2014balance0.99±0.00
0.99±0.00
0.99±0.00
0.04±0.02[1] Z. Wu and R. Leahy, “An Optimal Graph Theoretic Approach to
Data Clustering: Theory and Its Application to Image Segmentation,” IEEE Trans. on Pattern Analysis and Machine Intelligence,
Vol.15, pp. 1101-1113, 1993.
[2] L. Dey, A. Mahajan, and S. M. Haque, “Document Clustering for
Event Identification and Trend Analysis in Market News,” In Proc.
of the 2009 Seventh Int. Conf. on Advances in Pattern Recognition,
ICAPR’09, pp. 103-106, IEEE Computer Society, 2009.
[3] S. Basu, I. Davidson, and K. L.Wagstaff (Eds.), “Constrained Clustering,” CRC Press, 2008.
[4] O. Chapelle, B. Scholkopf, and A. Zien, “Semi-Supervised Learning,” The MIT Press, 2006.
[5] K. Wagstaff and S. Roger, “Constrained K-means Clustering with
Background Knowledge,” In Proc. of the 18th Int. Conf. on Machine
Learning, pp. 577-584, 2001.
[6] S. C. H. Hoi, R. Jin, and M. R. Lyu, “Learning nonparametric kernel
matrices from pairwise constraints,” In Proc. of the 24th Int. Conf.
on Machine learning, pp. 361-368, 2007.
[7] P. Jain, B. Kulis, I. S. Dhillon, and K. Grauman, “Online Metric
Learning and Fast Similarity Search,” In Proc. of Neural Information Processing Systems, pp. 761-768, 2008.
[8] D. Klein, S. D. Kamvar, and C. D. Manning, “From Instance-level
Constraints to Space-level Constraints: Making the Most of Prior
Knowledge in Data Clustering,” In Proc. of the 19th Int. Conf. on
Machine Learnning, pp. 307-314, 2002.
[9] Z. Li, J. Liu, and X. Tang, “Pairwise constraint propagation bysemidefinite programming for semi-supervised classification,” In
Proc. of the 25th Int. Conf. on Machine learning, pp. 576-583, 2008.
[10] W. Tang, H. Xiong, S. Zhong, and J. Wu, “Enhancing SemiSupervised Clustering: A Feature Projection Perspective,” In Proc.
of the 13th Int. Conf. on Knowledge Discovery and Data Mining,pp. 707-716, 2007.

Journal of Advanced Computational Intelligenceand Intelligent Informatics

237

Okabe, M. and Yamada, S.

[11] Y. Liu, R. Jin, and A. K. Jain, “BoostCluster: boosting clustering
by pairwise constraints,” In Proc. of the 13th ACM SIGKDD Int.
Conf. on Knowledge discovery and data mining, KDD’07, pp. 450459, New York, NY, USA, 2007.
[12] S. Tong and D. Koller, “Support Vector Machine Active Learningwith Applications to Text Classification,” J. of Machine Learning
Research, Vol.2, pp. 45-66, March 2002.
[13] L. Breiman and L. Breiman, “Bagging Predictors,” In Machine
Learning, pp. 123-140, 1996.
[14] D. Lewis and W. Gale, “A sequential algorithm for training textclassifiers,” In Proc. of the 17th Annual ACM SIGIR Conf., pp. 312, 1994.
[15] S. Basu, A. Banjeree, E. Mooney, A. Banerjee, and R. J. Mooney,“Active Semi-Supervision for Pairwise Constrained Clustering,” In
In Proc. of the 2004 SIAM Int. Conf. on Data Mining (SDM-04),
pp. 333-344, 2004.

Name:
Masayuki Okabe

Affiliation:
Toyohashi University of Technology

Address:
1-1 Tenpaku, Toyohashi, Aichi 441-8580, Japan

Brief Biographical History:
2001- Researcher of JST, Kyoto University
2003- Research Associate, Toyohashi University of Technology

Appendix A. Proof of K t as Positive Semidefinite

Main Works:

K t is a n-dimensional square matrix. Suppose indicesof the row (or column) of matrix K t are aligned for members of clusters. That is, members of cluster 1 are alignedwith indices from 1 to l1 in row K t and members of cluster
2 are aligned with indices from l1 + 1 to l1 + l2 , etc. Here,li is the number of members in the i-th cluster.
K t is represented as follows:⎞ ⎛⎛⎞1 1 1 1C1 O O O⎜ O C2 O O ⎟ ⎜ 1 1 · · · 1 ⎟⎟ ⎜⎟Kt = 2 ⎜⎝ O O . . . O ⎠ − ⎝ 1 ... . . . ... ⎠ .

Membership in Academic Societies:

O

O

O

1 1 ···

Ck

l1

∑ zi

+

i=1

≥ 0.

l1 +l2∑ zi

i=l1 +1

Name:
Seiji Yamada

Affiliation:
National Institute of Informatics, Graduate University for Advanced Studies (SOKENDAI)

Address:
2-1-2 Hitotsubashi, Chiyoda, Tokyo 101-8430, Japan

Brief Biographical History:
1989- Research Associate, Osaka University
1991- Lecturer, Osaka University
1996- Associate Professor, Tokyo Institute of Technology
2002- Professor, National Institute of Informatics / SOKENDAI

Main Works:• human-agent interaction• intelligent interactive systems• interactive machine learning

Membership in Academic Societies:zAz = zC1 z + zC2 z + · · · + zCk z=• The Japanese Society for Artificial Intelligence (JSAI)

1

where Ci is a square matrix whose dimension is equal to
the number of members in the i-th cluster and elements
are all 1. O is a matrix whose elements are all 0, thus
elements except for Ci in K t are all zero. Elements of thesecond matrix in the above formula are all 1.
Letting A and B be the first and the second matrix inthe above formula, that is, K t = 2A − B, K t is positive
semidefinite if A and B are positive semidefinite because
K t is a linear combination of these matrices.
For any vector z = {z1 , z2 , . . . , zn }, we calculate zAz as
follows:2• machine learning• information retrieval• data mining

2

+···+

2

n

∑

i=n−lk +1

zi• Association for Computing Machinery (ACM)• The Institute of Electrical and Electronics Engineers (IEEE)• Association for the Advancement of Artificial Intelligence (AAAI)• The Japanese Society for Artificial Intelligence (JSAI)

A is positive semidefinite. We prove that B is positive
semidefinite in a similar way.
zBz =

n

2

∑ zi

i=1

≥0
Since both A and B are positive semidefinite, K t is also
positive semidefinite.

238

Journal of Advanced Computational Intelligenceand Intelligent Informatics

Vol.18 No.2, 2014