On Information-Maximization Clustering:
Tuning Parameter Selection and Analytic Solution

Masashi Sugiyama
sugi@cs.titech.ac.jp
Makoto Yamada
yamada@sg.cs.titech.ac.jp
Manabu Kimura
kimura@sg.cs.titech.ac.jp
Hirotaka Hachiya
hachiya@sg.cs.titech.ac.jp
Department of Computer Science, Tokyo Institute of Technology, Tokyo, Japan.

Abstract
Information-maximization clustering learns
a probabilistic classiﬁer in an unsupervisedmanner so that mutual information between
feature vectors and cluster assignments is
maximized. A notable advantage of thisapproach is that it only involves continuous optimization of model parameters, which
is substantially easier to solve than discrete optimization of cluster assignments.
However, existing methods still involve nonconvex optimization problems, and therefore ﬁnding a good local optimal solution is
not straightforward in practice. In this paper, we propose an alternative informationmaximization clustering method based on asquared-loss variant of mutual information.
This novel approach gives a clustering solution analytically in a computationally efﬁcient way via kernel eigenvalue decomposition. Furthermore, we provide a practicalmodel selection procedure that allows us toobjectively optimize tuning parameters included in the kernel function. Through experiments, we demonstrate the usefulness ofthe proposed approach.

To cope with this problem, various non-linear clustering methods have been developed. Kernel k-means(Girolami, 2002) performs k-means in a feature spaceinduced by a reproducing kernel function. Spectralclustering (Shi & Malik, 2000) ﬁrst unfolds non-linear
data manifolds by a spectral embedding method, andthen performs k-means in the embedded space. Blurring mean-shift (Fukunaga & Hostetler, 1975) uses
a non-parametric kernel density estimator for modeling the data-generating probability density and ﬁnds
clusters based on the modes of the estimated density. Discriminative clustering (Xu et al., 2005; Bach
& Harchaoui, 2008) learns a discriminative classiﬁer
for separating clusters, where class labels are also
treated as parameters to be optimized. Dependencemaximization clustering (Song et al., 2007; Faivishevsky & Goldberger, 2010) determines cluster assignments so that their dependence on input data is
maximized.

The goal of clustering is to classify data samples into
disjoint groups in an unsupervised manner. K-means
is a classic but still popular clustering algorithm. However, since k-means only produces linearly separated
clusters, its usefulness is rather limited in practice.

These non-linear clustering techniques would be capable of handling highly complex real-world data. However, they suﬀer from lack of objective model selection
strategies1 . More speciﬁcally, the above non-linear
clustering methods contain tuning parameters such as
the width of Gaussian functions and the number ofnearest neighbors in kernel functions or similarity measures, and these tuning parameter values need to beheuristically determined in an unsupervised manner.
The problem of learning similarities/kernels was addressed in earlier works, but they considered supervised setups, i.e., labeled samples are assumed to begiven. Zelnik-Manor & Perona (2005) provided a useful unsupervised heuristic to determine the similarity
in a data-dependent way. However, it still requires thenumber of nearest neighbors to be determined man-Appearing in Proceedings of the 28 th International Conference on Machine Learning, Bellevue, WA, USA, 2011.
Copyright 2011 by the author(s)/owner(s).

1‘Model selection’ in this paper refers to the choice oftuning parameters in kernel functions or similarity measures, not the choice of the number of clusters.

1. Introduction

On Information-Maximization Clusteringually (although the magic number ‘7’ was shown to
work well in their experiments).

2.1. Formulation of Information-Maximization
Clustering

Another line of clustering framework called
information-maximization clustering (Agakov &Barber, 2006; Gomes et al., 2010) exhibited thestate-of-the-art performance. In this informationmaximization approach, probabilistic classiﬁers suchas a kernelized Gaussian classiﬁer (Agakov & Barber,
2006) and a kernel logistic regression classiﬁer (Gomes
et al., 2010) are learned so that mutual information(MI) between feature vectors and cluster assignments
is maximized in an unsupervised manner. A notableadvantage of this approach is that classiﬁer training
is formulated as continuous optimization problems,
which are substantially simpler than discrete optimization of cluster assignments. Indeed, classiﬁer
training can be carried out in computationally efﬁcient manners by a gradient method (Agakov &Barber, 2006) or a quasi-Newton method (Gomes
et al., 2010). Furthermore, Agakov & Barber (2006)
provided a model selection strategy based on thecommon information-maximization principle. Thus,
kernel parameters can be systematically optimized in
an unsupervised way.

Suppose we are given d-dimensional i.i.d. feature vectors of size n,

However, in the above MI-based clustering approach,
the optimization problems are non-convex, and ﬁnding a good local optimal solution is not straightforward in practice. The goal of this paper is to overcome this problem by providing a novel informationmaximization clustering method. More speciﬁcally,
we propose to employ a variant of MI called squaredloss MI (SMI), and develop a new clustering algorithm whose solution can be computed analytically in
a computationally eﬃcient way via eigenvalue decomposition. Furthermore, for kernel parameter optimization, we propose to use a non-parametric SMI estimator called least-squares MI (LSMI) (Suzuki et al.,2009), which was proved to achieve the optimal convergence rate with analytic-form solutions. Throughexperiments on various real-world datasets such as images, natural languages, accelerometric sensors, andspeech, we demonstrate the usefulness of the proposed
clustering method.

2. Information-Maximization
Clustering with Squared-Loss
Mutual Information
In this section, we describe our novel clustering algorithm.

{xi | xi ∈ Rd }ni=1 ,which are assumed to be drawn independently from a
distribution with density p∗ (x). The goal of clustering
is to give cluster assignments,{yi | yi ∈ {1, . . . , c}}ni=1 ,to the feature vectors {xi }ni=1 , where c denotes thenumber of classes. Throughout this paper, we assume
that c is known.
In order to solve the clustering problem, we take theinformation-maximization approach (Agakov & Barber, 2006; Gomes et al., 2010). That is, we regard clustering as an unsupervised classiﬁcation problem, andlearn the class-posterior probability p∗ (y|x) so that ‘information’ between feature vector x and class label yis maximized.
The dependence-maximization approach (Song et al.,2007; Faivishevsky & Goldberger, 2010) is related to, but substantially diﬀerent from theabove information-maximization approach. In thedependence-maximization approach, cluster assignments {yi }ni=1 are directly determined so that theirdependence on feature vectors {xi }ni=1 is maximized.
Thus, the dependence-maximization approach intrinsically involves combinatorial optimization with respect to {yi }ni=1 . On the other hand, the informationmaximization approach involves continuous optimization with respect to the parameter α included in aclass-posterior model p(y|x; α). This continuous optimization of α is substantially easier to solve than
discrete optimization of {yi }ni=1 .
Another advantage of the information-maximization
approach is that it naturally allows out-of-sample clustering based on the discriminative model p(y|x; α),i.e., a cluster assignment for a new feature vector canbe obtained based on the learned discriminative model.
2.2. Squared-Loss Mutual Information
As an information measure, we adopt squared-loss mutual information (SMI). SMI between feature vector x
and class label y is deﬁned by
)2
( ∗
∫ c
1 ∑ ∗
p (x, y)∗SMI :=− 1 dx,p (x)p (y)2 y=1p∗ (x)p∗ (y)(1)

On Information-Maximization Clustering

where p∗ (x, y) denotes the joint density of x and y,and p∗ (y) is the marginal probability of y. SMI is thePearson divergence (Pearson, 1900) from p∗ (x, y) top∗ (x)p∗ (y), while the ordinary MI (Cover & Thomas,
2006) is the Kullback-Leibler divergence (Kullback &Leibler, 1951) from p∗ (x, y) to p∗ (x)p∗ (y):
MI :=

∫ ∑
c

p∗ (x, y) log

y=1p∗ (x, y)p∗ (x)p∗ (y)

dx.

(2)

The Pearson divergence and the Kullback-Leibler divergence both belong to the class of Ali-Silvey-Csiszárdivergences (which is also known as f -divergences, see(Ali & Silvey, 1966; Csiszár, 1967)), and thus theyshare similar properties. For example, SMI is nonnegative and takes zero if and only if x and y arestatistically independent, as the ordinary MI.
In the existing information-maximization clustering
methods (Agakov & Barber, 2006; Gomes et al., 2010),
MI is used as the information measure. On the other
hand, in this paper, we adopt SMI because it allows
us to develop a clustering algorithm whose solution
can be computed analytically in a computationally efﬁcient way via eigenvalue decomposition, as described
below.
2.3. Clustering by SMI Maximization
Here, we give a computationally-eﬃcient clustering algorithm based on SMI (1).
We can express SMI as
SMI =

=

1
2
1
2

∫ ∑
c

1
p∗ (x, y)dx −p∗ (x, y) ∗∗p (x)p (y)
2
y=1

∫ ∑
c

p∗ (y|x)p∗ (x)

y=1

(3)

(4)

Suppose that the class-prior probability p∗ (y) is set to
be uniform: p∗ (y) = 1/c. Then Eq.(4) is expressed as
c
2

∫ ∑
c

1
p∗ (y|x)p∗ (x)p∗ (y|x)dx − .
2
y=1

(5)

n
∑

αy,i K(x, xi ),Further approximating the expectation with respect
to p∗ (x) included in Eq.(5) by the empirical averageof samples {xi }ni=1 , we arrive at the following SMI
approximator:∑
1d := cSMIα⊤ K 2 αy − ,2n y=1 y2cwhere ⊤ denotes the transpose,(αy,1 , . . . , αy,n )⊤ , and Ki,j := K(xi , xj ).

(8)
αy

:=

2
2
For each cluster y, we maximize α⊤
y K αy under∥αy ∥ = 1. Since this is the Rayleigh quotient, themaximizer is given by the normalized principal eigenvector of K (Horn & Johnson, 1985). To avoid all thesolutions {αy }cy=1 to be reduced to the same principal eigenvector, we impose their mutual orthogonality:′α⊤y αy ′ = 0 for y ̸= y . Then the solutions are givenby the normalized eigenvectors ϕ1 , . . . , ϕc associatedwith the eigenvalues λ1 ≥ · · · ≥ λn ≥ 0 of K. Since
the sign of ϕy is arbitrary, we set the sign as

where sign(·) denotes the sign of a scalar and 1n denotes the n-dimensional vector with all ones.
On the other hand, since∫n1∑p∗ (y) = p∗ (y|x)p∗ (x)dx ≈p(y|xi ; α) = α⊤y K1n ,
n i=1
and the class-prior probability p∗ (y) was set to be uniform, we have the following normalization condition:

Let us approximate the class-posterior probabilityp∗ (y|x) by the following kernel model:p(y|x; α) :=where Nt (x) denotes the set of t nearest neighbors forx (t is the kernel parameter), σi is a local scaling factor(t)(t)
deﬁned as σi = ∥xi − xi ∥, and xi is the t-th nearest
neighbor of xi .

e = ϕ × sign(ϕ⊤ 1n ),
ϕ
y
y
y

∗

1
p (y|x)dx − .
p∗ (y)
2sparse variant of the local-scaling kernel (Zelnik-Manor& Perona, 2005):
()∥xi − xj ∥2exp − 2σ σi jK(xi , xj ) =
(7)
if
x
∈
N
(x

i
t
j ) or xj ∈ Nt (xi ),0otherwise,

(6)

i=1

where K(x, x′ ) denotes a kernel function with a kernel parameter t. In the experiments, we will use aα⊤y K1n = 1/c.
Furthermore, probability estimates should be nonnegative, which can be achieved by rounding up negative outputs to zero. Taking these issues into account,2
Note that this unit-norm constraint is not essential
since the obtained solution is renormalized later.

On Information-Maximization Clustering

cluster assignments {yi }ni=1 for {xi }ni=1 are determinedasyi = argmaxye )]i[max(0n , ϕy,emax(0n , ϕ )⊤ 1nywhere the max operation for vectors is applied in theelement-wise manner and [·]i denotes the i-th element
e = λy ϕe in theof a vector. Note that we used K ϕyyabove derivation.
We call the above method SMI-based clustering(SMIC).
2.4. Kernel Parameter Choice by SMI
Maximization
Since the above clustering approach was developedin the framework of SMI maximization, it would benatural to determine the kernel parameters so that
SMI is maximized. A direct approach is to use thed also for kernel parameter
above SMI estimator SMI
choice. However, this direct approach is not favord is an unsupervised SMI estimatorable because SMI(i.e., SMI is estimated only from unlabeled samples{xi }ni=1 ). In the model selection stage, however, wehave already obtained labeled samples {(xi , yi )}ni=1 ,and thus supervised estimation of SMI is possible. Forsupervised SMI estimation, a non-parametric SMI estimator called least-squares mutual information (LSMI)(Suzuki et al., 2009) was shown to achieve the optimal
convergence rate. For this reason, we propose to use
d (8).
LSMI for model selection, instead of SMI
LSMI is an estimator of SMI based on paired samples{(xi , yi )}ni=1 . The key idea of LSMI is to learn thefollowing density-ratio function,p∗ (x, y)r∗ (x, y) := ∗,p (x)p∗ (y)(9)

without going through density estimation of p∗ (x, y),p∗ (x), and p∗ (y). More speciﬁcally, let us employ thefollowing density-ratio model:∑r(x, y; θ) :=θℓ L(x, xℓ ),(10)ℓ:yℓ =ywhere L(x, x′ ) is a kernel function with kernel parameter γ. In the experiments, we will use the Gaussian
kernel:)(∥x − x′ ∥2.
(11)
L(x, x′ ) = exp −2γ 2
The parameter θ in the above density-ratio model islearned so that the following squared error is mini-

mized:∫ c)2
1 ∑(r(x, y; θ) − r∗ (x, y) p∗ (x)p∗ (y)dx. (12)2 y=1Among n cluster assignments {yi }ni=1 , let ny be thenumber of samples in cluster y. Let θ y be theparameter vector corresponding to the kernel bases{L(x, xℓ )}ℓ:yℓ =y , i.e., θ y is the ny -dimensional subvector of θ = (θ1 , . . . , θn )⊤ consisting of indices{ℓ | yℓ = y}. Then an empirical and regularized version of the optimization problem (12) is given for eachy as follows:[]
1 c (y)⊤ b (y)⊤min θ ⊤
H
θ
−
θ
h
+
δθ
θ
(13)
y
y
y y ,
θy
2 y
(y)

c
where δ (≥ 0) is the regularization parameter. H(y)bis the ny × ny matrix and his the ny -dimensional
vector deﬁned as
n
∑
(y)
(y)
b (y)′ := nyHL(xi , xℓ )L(xi , xℓ′ ),ℓ,ℓn2 i=1
1 ∑
(y)
(y)
b
hℓ :=
L(xi , xℓ ),n i:y =yi(y)where xℓ is the ℓ-th sample in class y (which corre(y)sponds to θbℓ ).

b(y)A notable advantage of LSMI is that the solution θ
can be computed analytically as(y)b(y) = (Hb (y) .
c + δI)−1 hθThen a density-ratio estimator is obtained analyticallyas follows:
rb(x, y) =

ny
∑
(y)
(y)
θb L(x, x ).
ℓ

ℓ

ℓ=1

The accuracy of the above least-squares densityratio estimator depends on the choice of the kernel parameter γ and the regularization parameter δ.
They can be systematically optimized based on crossvalidation as follows (Suzuki et al., 2009). The samples Z = {(xi , yi )}ni=1 are divided into M disjoint subsets {Zm }M
m=1 of approximately the same size. Thena density-ratio estimator rbm (x, y) is obtained using
Z\Zm (i.e., all samples without Zm ), and its out-ofsample error (which corresponds to Eq.(12) without
irrelevant constant) for the hold-out samples Zm is
computed as∑∑
1
1
CVm :=
rbm (x, y)2 −rbm (x, y).
2
2|Zm ||Zm |x,y∈Zm(x,y)∈Zm

On Information-Maximization Clustering

This procedure is repeated for m = 1, . . . , M , and theaverage of the above hold-out error over all m is computed. Finally, the kernel parameter γ and the regularization parameter δ that minimize the average holdout error are chosen as the most suitable ones.
Based on the expression of SMI given by Eq.(3), an
SMI estimator called LSMI is given as follows:()∥xi −xj ∥2
exp − 2σ, where σi is a local scaling factor dei σj(t)

If D − 2 W D − 2 is regarded as a kernel matrix, spectral clustering will be similar to the proposed SMIC
method described in Section 2.3. However, SMIC does
not require the post k-means processing since the principal components have clear interpretation as parameter estimates of the class-posterior model (6). Furthermore, our proposed approach provides a systematic
model selection strategy, which is a notable advantage
over spectral clustering.
1

1 ∑1
LSMI :=
rb(xi , yi ) − ,2n i=12n(14)

where rb(x, y) is a density-ratio estimator obtained
above. Since rb(x, y) can be computed analytically,
LSMI can also be computed analytically.
We use LSMI for model selection of SMIC. More specifically, we compute LSMI as a function of the kernel parameter t of K(x, x′ ) included in the cluster-posterior
model (6), and choose the one that maximizes LSMI.

(t)ﬁned as σi = ∥xi − xi ∥, and xi is the t-th nearest
neighbor of xi . t is the tuning parameter in the local
scaling similarity, and t = 7 was shown to be useful (Zelnik-Manor & Perona, 2005; Sugiyama, 2007).
However, this magic number ‘7’ does not seem to work
always well in general.
1

3.2. Blurring Mean-Shift Clustering

MATLAB implementation of the proposed clustering method is available from ‘http://sugiyamawww.cs.titech.ac.jp/˜sugi/software/SMIC’.

Blurring mean-shift (Fukunaga & Hostetler, 1975) is a
non-parametric clustering method based on the modesof the data-generating probability density.

3. Existing Methods

In the blurring mean-shift algorithm, a kernel density
estimator (Silverman, 1986) is used for modeling thedata-generating probability density:

In this section, we qualitatively compare the proposed
approach with existing methods.
3.1. Spectral Clustering
The basic idea of spectral clustering (Shi & Malik,
2000) is to ﬁrst unfold non-linear data manifolds bya spectral embedding method, and then perform kmeans in the embedded space. More speciﬁcally, given
sample-sample similarity Wi,j ≥ 0, the minimizer ofthe following criterion with respect to {ξ i }ni=1 is obtained under some normalization constraint:n∑1
1
Wi,j √
ξi − √
ξj
D
D
i,i
j,j
i,j

2

,

where D is the diagonal∑matrix with i-th diagonal eln
ement given by Di,i := j=1 Wi,j . Consequently, theembedded samples are given by the principal eigenvec1
1
tors of D − 2 W D − 2 , followed by normalization. Notethat spectral clustering was shown to be equivalent toa weighted variant of kernel k-means with some speciﬁc kernel (Dhillon et al., 2004).
The performance of spectral clustering depends heavily on the choice of sample-sample similarity Wi,j .
Zelnik-Manor & Perona (2005) proposed a useful unsupervised heuristic to determine the similarity in adata-dependent manner, called local scaling: Wi,j =

)
1∑ (
2
K ∥x − xi ∥ /σ 2 ,n i=1npb(x) =

where K(ξ) is a kernel function such as a Gaussian
kernel K(ξ) = e−ξ/2 . Taking the derivative of pb(x)with respect to x and equating the derivative at x = xi
to zero, we obtain the following updating formula forsample xi (i = 1, . . . , n):∑nj=1 Wi,j xj
xi ←− ∑n,′j ′ =1 Wi,j()
2
where Wi,j := K ′ ∥xi − xj ∥ /σ 2 and K ′ (ξ) is thederivative of K(ξ). Each mode of the density is regarded as a representative of a cluster, and each data
point is assigned to the cluster which it converges to.
Carreira-Perpiñán (2007) showed that the blurring mean-shift algorithm can be interpreted asan EM∑nalgorithm (Dempster et al., 1977), where
Wi,j /( j ′ =1 Wi,j ′ ) is regarded as the posterior probability of the i-th sample belonging to the j-th cluster. Furthermore, the above update rule can be expressed in a matrix form as X ←− XP , where X =(x1 , . . . , xn ) is a sample matrix and P := W D −1 isa stochastic matrix of the random walk in a graphwith adjacency W (Chung, 1997). D is deﬁned as

An attractive property of blurring mean-shift is thatthe number of clusters is automatically determined as
the number of modes in the probability density estimate. However, this choice depends on the kernelparameter σ and there is no systematic way to determine σ, which is restrictive compared with the proposed method. Another critical drawback of the blurring mean-shift algorithm is that it eventually converges to a single point (Cheng, 1995), and therefore asensible stopping criterion is necessary in practice. Although Carreira-Perpiñán (2006) gave a useful heuristic for stopping the iteration, it is not clear whether
this heuristic always works well in practice.

4. Experiments
In this section, we experimentally evaluate the performance of the proposed and existing clustering methods.
4.1. Illustration
First, we illustrate the behavior of the proposed
method using artiﬁcial datasets described in the top
row of Figure 1. The dimensionality is d = 2 and thesample size is n = 200. As a kernel function, we used
the sparse local-scaling kernel (7) for SMIC, where thekernel parameter t was chosen from {1, . . . , 10} basedon LSMI with the Gaussian kernel (11).
The top graphs in Figure 1 depict the cluster assignments obtained by SMIC, and the bottom graphs in
Figure 1 depict the model selection curves obtainedby LSMI. The results show that SMIC combined with
LSMI works well for these toy datasets.
4.2. Performance Comparison
Next, we systematically compare the performance ofthe proposed and existing clustering methods using
various real-world datasets such as images, natural languages, accelerometric sensors, and speech.
We compared the performance of the following methods, which all do not contain open tuning parame-

0.5
SMI estimate

0.45
0.4
0.35
0.3

2 4 6 8 10
Kernel parameter t

0.25

2 4 6 8 10
Kernel parameter t

0.5
0.45
0.4
0.35
0.3
0.25
0.2

SMI estimate

1.5
1.4
1.3
1.2
1.1
1
0.9
0.8
0.7

SMI estimate∑nDi,i :=
j=1 Wi,j and Di,j = 0 for i ̸= j. If P is
independent of X, the above iterative algorithm corresponds to the power method (Golub & Loan, 1996)
for ﬁnding the leading left eigenvector of P . Then,
this algorithm is highly related to the spectral clustering which computes the principal eigenvectors of1
1
D − 2 W D − 2 (see Section 3.1). Although P depends
on X in reality, Carreira-Perpiñán (2006) insisted that
this analysis is still valid since P and X quickly reacha quasi-stable state.

SMI estimate

On Information-Maximization Clustering

2 4 6 8 10
Kernel parameter t

0.4
0.35
0.3
0.25
0.2
0.15
0.1
0.05
0

2 4 6 8 10
Kernel parameter t

Figure 1. Illustrative examples. Cluster assignments obtained by SMIC (top) and model selection curves obtainedby LSMI (bottom).

ters and therefore experimental results are fair andobjective: K-means (KM), spectral clustering with theself-tuning local-scaling similarity (SC) (Zelnik-Manor& Perona, 2005), mean nearest-neighbor clustering(MNN) (Faivishevsky & Goldberger, 2010), MI-based
clustering for kernel logistic models (MIC) (Gomes
et al., 2010) with model selection by maximumlikelihood MI (Suzuki et al., 2008), and the proposed
SMIC.
The clustering performance was evaluated by the adjusted Rand index (ARI) (Hubert & Arabie, 1985)
between inferred cluster assignments and the groundtruth categories. Larger ARI values mean better performance, and ARI takes its maximum value 1 when
two sets of cluster assignments are identical. In addition, we also evaluated the computational eﬃciency ofeach method by the CPU computation time.
We used various real-world datasets including images, natural languages, accelerometric sensors, andspeech: The USPS hand-written digit dataset (‘digit’),the Olivetti Face dataset (‘face’), the 20-Newsgroups
dataset (‘document’), the SENSEVAL-2 dataset(‘word’), the ALKAN dataset (‘accelerometry’), andthe in-house speech dataset (‘speech’). Detailed explanation of the datasets is omitted due to lack of space.
For each dataset, the experiment was repeated 100
times with random choice of samples from a pool.
Samples were centralized and their variance was normalized in the dimension-wise manner, before feedingthem to clustering algorithms.
The experimental results are described in Table 1. For
the digit dataset, MIC and SMIC outperform KM, SC,
and MNN in terms of ARI. The entire computation
time of SMIC including model selection is faster thanKM, SC, and MIC, and is comparable to MNN which
does not include a model selection procedure. For theOn Information-Maximization Clustering
Table 1. Experimental results on real-world datasets (withequal cluster size). The average clustering accuracy (andits standard deviation in the bracket) in terms of ARI andthe average CPU computation time in second over 100 runs
are described. The best method in terms of the average
ARI and methods judged to be comparable to the best
one by the t-test at the signiﬁcance level 1% are describedin boldface. Computation time of MIC and SMIC corresponds to the time for computing a clustering solution
after model selection has been carried out. For references,computation time for the entire procedure including model
selection is described in the square bracket.

ARI
Time

Digit (d = 256, n = 5000, and c = 10)
KM
SC
MNN
MIC
SMIC
0.42(0.01) 0.24(0.02)
0.44(0.03) 0.63(0.08) 0.63(0.05)
835.9
973.3
318.5
84.4[3631.7] 14.4[359.5]

ARI
Time

Face (d = 4096, n = 100, and c = 10)
KM
SC
MNN
MIC
SMIC
0.60(0.11) 0.62(0.11) 0.47(0.10) 0.64(0.12) 0.65(0.11)
93.3
2.1
1.0
1.4[30.8]
0.0[19.3]

ARI
Time

Document (d = 50, n = 700, and c = 7)
KM
SC
MNN
MIC
0.00(0.00) 0.09(0.02)
0.09(0.02)
0.01(0.02)
77.8
9.7
6.4
3.4[530.5]

SMIC
0.19(0.03)
0.3[115.3]

ARI
Time

Word (d = 50, n = 300, and c = 3)
KM
SC
MNN
MIC
0.04(0.05) 0.02(0.01)
0.02(0.02)
0.04(0.04)
6.5
5.9
2.2
1.0[369.6]

SMIC
0.08(0.05)
0.2[203.9]

ARI
Time

Accelerometry (d = 5, n = 300, and c = 3)
KM
SC
MNN
MIC
SMIC
0.49(0.04) 0.58(0.14) 0.71(0.05) 0.57(0.23) 0.68(0.12)
0.4
3.3
1.9
0.8[410.6]
0.2[92.6]

ARI
Time

Speech (d = 50, n = 400, and c = 2)
KM
SC
MNN
MIC
SMIC
0.00(0.00) 0.00(0.00)
0.04(0.15) 0.18(0.16) 0.21(0.25)
0.9
4.2
1.8
0.7[413.4]
0.3[179.7]

face dataset, SC, MIC, and SMIC are comparable toeach other and are better than KM and MNN in termsof ARI. For the document and word datasets, SMIC
tends to outperform the other methods. For the accelerometry dataset, MNN and SMIC work better thanthe other methods. Finally, for the speech dataset,
MIC and SMIC work comparably well, and are significantly better than KM, SC, and MNN.
Overall, MIC was shown to work reasonably well, implying that model selectoin by maximum-likelihood MI
is practically useful. SMIC was shown to work evenbetter than MIC, with much less computation time.
The accuracy improvement of SMIC over MIC was
gained by computing the SMIC solution in a closedform without any heuristic initialization. The computational eﬃciency of SMIC was brought by the analytic
computation of the optimal solution and the class-wise
optimization of LSMI (see Section 2.4).
The performance of MNN and SC was rather unstable because of the heuristic averaging of the numberof nearest neighbors and the heuristic choice of local
scaling. In terms of computation time, they are rela-

Table 2. Experimental results on real-world datasets underimbalanced setup. ARI values are described in the table.
Class-imbalance was realized by setting the sample size ofthe ﬁrst class m times larger than other classes. The results
for m = 1 are the same as the ones reported in Table 1.

m=1
m=2

Digit (d = 256, n = 5000, and c = 10)
KM
SC
MNN
MIC
SMIC
0.42(0.01) 0.24(0.02) 0.44(0.03) 0.63(0.08) 0.63(0.05)
0.52(0.01) 0.21(0.02) 0.43(0.04)
0.60(0.05) 0.63(0.05)

m=1
m=2
m=3
m=4

Document (d = 50, n = 700, and c = 7)
KM
SC
MNN
MIC
0.00(0.00) 0.09(0.02) 0.09(0.02)
0.01(0.02)
0.01(0.01) 0.10(0.03) 0.10(0.02)
0.01(0.02)
0.01(0.01) 0.10(0.03) 0.09(0.02) -0.01(0.03)
0.02(0.01) 0.09(0.03) 0.08(0.02) -0.00(0.04)

m=1
m=2

Word (d = 50, n = 300, and c = 3)
KM
SC
MNN
MIC
SMIC
0.04(0.05) 0.02(0.01) 0.02(0.02)
0.04(0.04) 0.08(0.05)
0.00(0.07) -0.01(0.01) 0.01(0.02) -0.02(0.05) 0.03(0.05)

m=1
m=2
m=3
m=4

Accelerometry (d = 5, n = 300, and c = 3)
KM
SC
MNN
MIC
0.49(0.04) 0.58(0.14) 0.71(0.05) 0.57(0.23)
0.48(0.05) 0.54(0.14) 0.58(0.11)
0.49(0.19)
0.49(0.05) 0.47(0.10) 0.42(0.12)
0.42(0.14)
0.49(0.06) 0.38(0.11) 0.31(0.09)
0.40(0.18)

SMIC
0.19(0.03)
0.19(0.04)
0.16(0.05)
0.14(0.05)

SMIC
0.68(0.12)
0.69(0.16)
0.66(0.20)
0.56(0.22)

tively eﬃcient for small- to medium-sized datasets, butthey are expensive for the largest dataset, digit. KM
was not reliable for the document and speech datasets
because of the restriction that the cluster boundaries
are linear. For the digit, face, and document datasets,
KM was computationally very expensive since a large
number of iterations were needed until convergence toa local optimum solution.
Finally, we performed similar experiments under imbalanced setup, where the the sample size of the ﬁrst
class was set to be m times larger than other classes.
The results are summarized in Table 2, showing thatthe performance of all methods tends to be degradedas the degree of imbalance increases. Thus, clustering
becomes more challenging if the cluster size is imbalanced. Among the compared methods, the proposed
SMIC still worked better than other methods.
Overall, the proposed SMIC combined with LSMI wasshown to be a useful alternative to existing clustering
approaches.

5. Conclusions
In this paper, we proposed a novel informationmaximization clustering method, which learns classposterior probabilities in an unsupervised manner sothat the squared-loss mutual information (SMI) between feature vectors and cluster assignments is maximized. The proposed algorithm called SMI-based clustering (SMIC) allows us to obtain clustering solutions
analytically by solving a kernel eigenvalue problem.
Thus, unlike the previous information-maximization

On Information-Maximization Clustering

clustering methods (Agakov & Barber, 2006; Gomes
et al., 2010), SMIC does not suﬀer from the problem of local optima. Furthermore, we proposed to use
an optimal non-parametric SMI estimator called leastsquares mutual information (LSMI) for data-driven
parameter optimization. Through experiments, SMIC
combined with LSMI was demonstrated to compare
favorably with existing clustering methods.

Acknowledgments
We would like to thank Ryan Gomes for providing us
his program code of information-maximization clustering. MS was supported by SCAT, AOARD, and the
FIRST program. MY and MK were supported by the
JST PRESTO program, and HH was supported by the
FIRST program.

References
Agakov, F. and Barber, D. Kernelized infomax clustering.
NIPS 18, pp. 17–24. MIT Press, 2006.
Ali, S. M. and Silvey, S. D. A general class of coeﬃcientsof divergence of one distribution from another. Journalof the Royal Statistical Society, Series B, 28(1):131–142,
1966.
Bach, F. and Harchaoui, Z. DIFFRAC: A discriminativeand ﬂexible framework for clustering. NIPS 20, pp. 49–
56, 2008.
Carreira-Perpiñán, M. Á. Fast nonparametric clusteringwith Gaussian blurring mean-shift. ICML, pp. 153–160,
2006.
Carreira-Perpiñán, M. Á. Gaussian mean shift is an EM
algorithm. IEEE Transactions on Pattern Analysis andMachine Intelligence, 29:767–776, 2007.
Cheng, Y. Mean shift, mode seeking, and clustering. IEEE
Transactions on Pattern Analysis and Machine Intelligence, 17:790–799, 1995.
Chung, F. R. K. Spectral Graph Theory. American Mathematical Society, Providence, 1997.
Cover, T. M. and Thomas, J. A. Elements of Information
Theory. John Wiley & Sons, Inc., 2nd edition, 2006.
Csiszár, I. Information-type measures of diﬀerence of
probability distributions and indirect observation. Studia Scientiarum Mathematicarum Hungarica, 2:229–318,
1967.
Dempster, A. P., Laird, N. M., and Rubin, D. B. Maximum
likelihood from incomplete data via the EM algorithm.
Journal of the Royal Statistical Society, series B, 39(1):1–38, 1977.
Dhillon, I. S., Guan, Y., and Kulis, B. Kernel k-means,
spectral clustering and normalized cuts. ACM SIGKDD,
pp. 551–556, 2004.

Faivishevsky, L. and Goldberger, J. A nonparametric information theoretic clustering algorithm. ICML, pp. 351–
358, 2010.
Fukunaga, K. and Hostetler, L. D. The estimation of
the gradient of a density function, with application inpattern recognition. IEEE Transactions on Information
Theory, 21(1):32–40, 1975.
Girolami, M. Mercer kernel-based clustering in feature
space. IEEE Transactions on Neural Networks, 13(3):780–784, 2002.
Golub, G. H. and Loan, C. F. Van. Matrix Computations.
Johns Hopkins University Press, 1996.
Gomes, R., Krause, A., and Perona, P. Discriminative clustering by regularized information maximization. NIPS
23, pp. 766–774. 2010.
Horn, R. A. and Johnson, C. A. Matrix Analysis. Cambridge University Press, 1985.
Hubert, L. and Arabie, P. Comparing partitions. Journalof Classification, 2(1):193–218, 1985.
Kullback, S. and Leibler, R. A. On information and sufﬁciency. Annals of Mathematical Statistics, 22:79–86,
1951.
Pearson, K. On the criterion that a given system of deviations from the probable in the case of a correlated systemof variables is such that it can be reasonably supposed tohave arisen from random sampling. Philosophical Magazine, 50:157–175, 1900.
Shi, J. and Malik, J. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888–905, 2000.
Silverman, B. W. Density Estimation for Statistics andData Analysis. Chapman and Hall, 1986.
Song, L., Smola, A., Gretton, A., and Borgwardt, K. A
dependence maximization view of clustering. ICML, pp.
815–822, 2007.
Sugiyama, M. Dimensionality reduction of multimodal labeled data by local Fisher discriminant analysis. Journalof Machine Learning Research, 8:1027–1061, 2007.
Suzuki, T., Sugiyama, M., Sese, J., and Kanamori, T. Approximating mutual information by maximum likelihooddensity ratio estimation. JMLR Workshop and Conference Proceedings, 4:5–20, 2008.
Suzuki, T., Sugiyama, M., Kanamori, T., and Sese, J. Mutual information estimation reveals global associations
between stimuli and biological processes. BMC Bioinformatics, 10(1):S52, 2009.
Xu, L., Neufeld, J., Larson, B., and Schuurmans, D. Maximum margin clustering. NIPS 17, pp. 1537–1544. 2005.
Zelnik-Manor, L. and Perona, P. Self-tuning spectral clustering. NIPS 17, pp. 1601–1608, 2005.