# Spectral Nonlinearly Embedded Clustering Algorithm

Authors: Mingming Liu; Bing Liu; Chen Zhang; Wei Sun
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

As is well known, traditional spectral clustering (SC) methods are developed based on themanifold assumption, namely, that two nearby data points in the high-density region of a low-dimensional data manifold have the same cluster label. But, for some high-dimensional and sparse data, such an assumption might be invalid. Consequently, the clustering performance of SC will be degraded sharply in this case. To solve this problem, in this paper, we propose a general spectral embedded framework, which embeds the true cluster assignment matrix for high-dimensional data into a nonlinear space by a predefined embedding function. Based on this framework, several algorithms are presented by using different embedding functions, which aim at learning the final cluster assignment matrix and a transformation into a low dimensionality space simultaneously. More importantly, the proposed method can naturally handle the out-of-sample extension problem. The experimental results on benchmark datasets demonstrate that the proposed method significantly outperforms existing clustering methods.


---

## Body

## 1. Introduction

As one of the fundamental topics in data mining and machine learning, clustering has been successfully applied in various fields. Generally speaking, the target of clustering is to group the examples into a number of classes, or clusters. Over the past decades, a large family of clustering algorithms has been studied extensively, which is mainly divided into two categories: generative clustering approaches and discriminative clustering models. Generative clustering approaches, for example, mixture models [1, 2], generally integrate Bayesian approaches into its models. However, generative models add restrict assumptions on the class-conditional densities, which might lead to unconvincing clustering results when these assumptions do not hold. Discriminative methods, such as spectral clustering (SC) [3] andK-means clustering [4], learn discriminative models based on loss functions from unlabeled data through the low-density separation assumption.Recently, discriminative clustering methods, such as the variants of kernel-based clustering and spectral clustering, have attracted more and more renewed attentions. It is easy to perform them to capture nonlinear cluster structures. Motivated by the outstanding performance of support vector machine (SVM) in supervised learning, maximum margin clustering (MMC) [5–7] methods have been developed to obtain a decision boundary that can separate data points into different clusters to the utmost extent. Although these clustering methods have the ability of exploiting nonlinear data structures, they are still sensitive to high-dimensional data points. For example,K-means clustering iteratively computes the distance between each data point and the center of each cluster. Hence, its clustering performance severely depends on the distance measurement. However, high-dimensional data, such as some image data, would have a bad influence on the similarity computation by virtue of Euclidian distance, and the performance ofK-means clustering would be degraded dramatically. SC can perform clustering by utilizing the spectrum of the similarity matrix to discover the nonlinear and low-dimensional manifold structure of data points. In other words, it heavily relies on the manifold assumption [8, 9], namely, that two nearby data points of a low-dimensional manifold have the same class label. However, for high-dimensional and sparse data, the manifold assumption may not hold due to the bias caused by the curse of dimensionality. Nie et al. [10] have validated that graph-based spectral clustering methods cannot always exploit the low-dimensional manifold structure, which would result in the performance degradation of SC. Another challenge for traditional SC methods is that they do not solve the out-of-sample extension problem; that is, the discrete cluster assignment vectors for some new unseen samples cannot be automatically obtained. The algorithm proposed in [11] takes advantage of the Nyström method to approximate the eigenfunction for the unseen data points. The method described in [12] makes good use of some heuristics to evaluate the implicit eigenfunction for the new data points. But, the performance of these methods heavily relies on the estimated affinity matrix defined between training and new data points.To improve the clustering performance of SC for high-dimensional data further, in this paper, we firstly propose a general spectral embedded clustering framework, which incorporates dimensionality reduction methods into the model of SC. Secondly, by using different low-dimensional embedding functions, we derive the corresponding optimization models and develop the spectral nonlinearly embedded algorithms based on extreme learning machine (ELM) and kernel functions, respectively. Our main contributions include the following:(1)
A general spectral embedded clustering framework is presented by imposing a linearity regularization on the objective function of SC. The proposed framework introduces dimensionality reduction of the training data by controlling the error between the cluster assignment matrix and the low-dimensional embedding of the data.
(2)
Based on the proposed general framework, several models can be derived by using different embedding functions, which include the linear embedding functions and the nonlinear functions in Reproducing Kernel Hilbert Space (RKHS) as well as in ELM feature space. The spectral embedded clustering model (SEC) proposed in [12] can be considered as the special case of the general framework.
(3)
We prove that the spectral nonlinearly embedded clustering model based on ELM (ESEC) is an approximation of the kernel-based spectral nonlinearly embedded clustering (KSEC) method under some conditions. The fast spectral nonlinearly embedded clustering algorithm is proposed based on ESEC by utilizing the efficient learning ability of ELM.
(4)
The out-of-sample extension problem can be naturally solved for the clustering methods under our proposed SEC framework.
(5)
Experimental results on benchmark datasets demonstrate that the proposed ESEC outperforms the existing SC methods,K-means clustering, and SEC and KSEC for in-sample clustering. For out-of-sample clustering, ESEC also has better generalization capability over the Nyström method and superior performance thanK-means clustering, SEC, and KSEC.The rest of this paper is organized as follows. Related works are introduced in Section2. In Section 3, we present the general spectral embedded clustering framework and derive several different models by using different embedding functions. The relationship between ESEC and KSEC is demonstrated and the ESEC clustering algorithm is described in detail. In addition, clustering for out-of-sample data is also discussed. To validate our model, experimental results are reported in Section 4. Finally, we give the related conclusions and a discussion of future works in Section 5. In order to avoid confusion, we give a list of the main notations used in this paper in Notations section.


## 2. Related Works

### 2.1. Spectral Clustering

Given a datasetX
=
x
i
i
=
1
n, the main task of clustering is to partition X into c clusters. SC aims at finding a cluster assignment matrix of the training data by a weighted graph G whose vertices are over X. Several SC algorithms have been proposed in [3, 13, 14]. In this paper, we mainly discuss the SC algorithm withk-way normalized cuts [3].Specifically, denote an undirected weighted graph byG
=
{
X
,
W
}, where X is a vertex set and W
∈
R
n
×
n represents an affinity matrix. Each entry W
i
j of the symmetric matrix W is used to record the edge weights that characterize the similarity relationship between a pair of vertices of G. W
i
j is commonly defined by (1)
W
i
j
=
exp
⁡
-
x
i
-
x
j
2
σ
2
if
x
i
,
x
j
are  neighbors
,
0
otherwise
.The Laplacian graph L is defined by L
=
D
-
W, where D is a diagonal matrix with the diagonal elements as D
i
i
=
∑
j
W
i
j
,
∀
i. Based on the normalized cut criterion, where the size of a subset of a graph is measured by the weights of its edges and the normalized Laplacian matrix is used, the optimization problem can be transformed into the following trace maximization problem [3]:(2)
m
a
x
F
T
F
=
I
c
t
r
F
T
D
-
1
/
2
W
D
-
1
/
2
F
,where I
c denotes the identity matrix of size c by c and F
∈
R
n
×
c represents the cluster assignment matrix with continuous values by relaxation. Then optimal solution F of (2) can be obtained by eigenvalue decomposition of the matrix D
-
1
/
2
W
D
-
1
/
2.


### 2.2. Extreme Learning Machine

The output function of ELM for generalized single-hidden-layer feedforward neural networks (SLFNs) in the case of one output node is(3)
f
L
x
=
∑
i
=
1
L
β
i
h
i
x
=
h
x
β
,where β
=
β
1
,
…
,
β
L
T is the vector of the output weights between the hidden layer ofL nodes and the output node and h
x
=
h
1
x
,
…
,
h
L
x is the output (row) vector of the hidden layer with respect to the input x. In fact, h
x maps the data from thed-dimensional input space to theL-dimensional hidden-layer feature space (ELM feature space) H. ELM is to minimize the training error as well as the norm of the output weights [15](4)
min
β
⁡
C
2
H
β
-
T
2
+
1
2
β
2
,where C is a tradeoff parameter between the complexity and fitness of the decision function and H is the hidden-layer output matrix denoted by(5)
H
=
h
x
1
h
x
2
⋮
h
x
n
=
h
1
x
1
…
h
L
x
1
h
1
x
2
…
h
L
x
2
⋮
⋮
⋮
h
1
x
n
…
h
L
x
n
.Similar to support vector machine (SVM), to minimize the norm of the output weightsβ is actually to maximize the distance of the separating margins of the two different classes in the ELM feature space: 2
/
β, which actually controls the complexity of the function in the ELM feature space.


## 2.1. Spectral Clustering

Given a datasetX
=
x
i
i
=
1
n, the main task of clustering is to partition X into c clusters. SC aims at finding a cluster assignment matrix of the training data by a weighted graph G whose vertices are over X. Several SC algorithms have been proposed in [3, 13, 14]. In this paper, we mainly discuss the SC algorithm withk-way normalized cuts [3].Specifically, denote an undirected weighted graph byG
=
{
X
,
W
}, where X is a vertex set and W
∈
R
n
×
n represents an affinity matrix. Each entry W
i
j of the symmetric matrix W is used to record the edge weights that characterize the similarity relationship between a pair of vertices of G. W
i
j is commonly defined by (1)
W
i
j
=
exp
⁡
-
x
i
-
x
j
2
σ
2
if
x
i
,
x
j
are  neighbors
,
0
otherwise
.The Laplacian graph L is defined by L
=
D
-
W, where D is a diagonal matrix with the diagonal elements as D
i
i
=
∑
j
W
i
j
,
∀
i. Based on the normalized cut criterion, where the size of a subset of a graph is measured by the weights of its edges and the normalized Laplacian matrix is used, the optimization problem can be transformed into the following trace maximization problem [3]:(2)
m
a
x
F
T
F
=
I
c
t
r
F
T
D
-
1
/
2
W
D
-
1
/
2
F
,where I
c denotes the identity matrix of size c by c and F
∈
R
n
×
c represents the cluster assignment matrix with continuous values by relaxation. Then optimal solution F of (2) can be obtained by eigenvalue decomposition of the matrix D
-
1
/
2
W
D
-
1
/
2.


## 2.2. Extreme Learning Machine

The output function of ELM for generalized single-hidden-layer feedforward neural networks (SLFNs) in the case of one output node is(3)
f
L
x
=
∑
i
=
1
L
β
i
h
i
x
=
h
x
β
,where β
=
β
1
,
…
,
β
L
T is the vector of the output weights between the hidden layer ofL nodes and the output node and h
x
=
h
1
x
,
…
,
h
L
x is the output (row) vector of the hidden layer with respect to the input x. In fact, h
x maps the data from thed-dimensional input space to theL-dimensional hidden-layer feature space (ELM feature space) H. ELM is to minimize the training error as well as the norm of the output weights [15](4)
min
β
⁡
C
2
H
β
-
T
2
+
1
2
β
2
,where C is a tradeoff parameter between the complexity and fitness of the decision function and H is the hidden-layer output matrix denoted by(5)
H
=
h
x
1
h
x
2
⋮
h
x
n
=
h
1
x
1
…
h
L
x
1
h
1
x
2
…
h
L
x
2
⋮
⋮
⋮
h
1
x
n
…
h
L
x
n
.Similar to support vector machine (SVM), to minimize the norm of the output weightsβ is actually to maximize the distance of the separating margins of the two different classes in the ELM feature space: 2
/
β, which actually controls the complexity of the function in the ELM feature space.


## 3. General Spectral Embedded Clustering Framework

As mentioned above, SC methods greatly depend on the construction of the affinity matrixW. For some high-dimensional data, it might not exhibit an evident low-dimensional manifold structure. In this case, the clustering performance of SC may be inferior to theK-means clustering.In the following subsections, we will firstly propose a general spectral embedded clustering framework, which incorporates a linearity regularization into the traditional normalized SC model. By using different embedding functions, this framework can generate a family of spectral embedded clustering algorithms, such as SEC, KSEC, and ESEC. Secondly, we demonstrate the relationship between ESEC and KSEC. The ESEC algorithm is then proposed for high-dimensional data clustering. Finally, the out-of-sample extension problem is discussed for our proposed ESEC method.


### 3.1. Formulation

Generally, clustering models of traditional SC methods can be transformed into the following minimization problem:(6)
m
i
n
F
T
F
=
I
c
t
r
F
T
L
~
F
,where L
~
=
D
-
(
1
/
2
)
L
D
-
(
1
/
2
)
=
I
n
-
D
-
(
1
/
2
)
W
D
-
(
1
/
2
) is the normalized Laplacian matrix.To make use of the underlying dense grouping structure of data in a low-dimensional subspace, the proposed general framework introduces a regularization term into the optimization problem (6), which controls the error between the cluster assignment matrix and the low-dimensional embedding of the data. Specifically, we minimize the following objective function:(7)
m
i
n
F
T
F
=
I
c
t
r
F
T
L
~
F
+
μ
ϕ
X
-
F
2
+
γ
g
ϕ
2
,where μ and γ
g are two regularization parameters and ϕ
X
=
ψ
1
X
,
…
,
ψ
c
(
X
)
∈
R
n
×
c is the low-dimensional embedding of training data. The second term represents the error between the relaxed cluster assignment matrix F and the low-dimensional embedding of the data. The third term is the norm penalty of ϕ
X and represents the complexity of functions in a high-dimensional feature space.In dimensionality reduction, linear embedding functions and nonlinear embedding functions are commonly used to address out-of-sample problems. This is due to the fact that they contain few parameters, which are not expensive in computational time and memory. In this paper, we mainly discuss kernel-based and ELM-based nonlinear embedding functions.If we choose a linear embedding functiony
=
W
T
x
+
b, ϕ
X
=
X
T
W
+
1
n
b
T, where W
∈
R
d
×
c and b
∈
R
c
×
1, the optimization problem (7) becomes(8)
m
i
n
F
,
W
,
b
F
T
F
=
I
c
t
r
F
T
L
~
F
+
μ
X
T
W
+
1
n
b
T
-
F
2
+
γ
g
t
r
W
T
Wwhich is equivalent to the SEC method proposed in [12].If we use a nonlinear embedding function in RKHS, that is,y
=
f
x
=
∑
i
=
1
n
α
i
k
(
x
,
x
i
), then ϕ
X
=
K
α, where K is a symmetric kernel matrix and α
=
α
1
,
…
,
α
n
T
∈
R
n
×
c; problem (7) can be rewritten as(9)
m
i
n
F
,
α
F
T
F
=
I
c
t
r
F
T
L
~
F
+
μ
K
α
-
F
2
+
γ
g
t
r
α
T
K
αwhich is referred to as KSEC.Alternatively, if we consider an embedding function in ELM feature space, that is,f
x
=
∑
i
=
1
L
β
i
h
i
x
=
h
x
β, then ϕ
X
=
H
β, where H represents the hidden-layer output matrix of ELM. Problem (7) can be reformulated as (10)
m
i
n
F
,
β
F
T
F
=
I
c
t
r
F
T
L
~
F
+
μ
H
β
-
F
2
+
γ
g
t
r
β
T
β
,which is referred to as ESEC.


### 3.2. Method

Firstly, to solve the optimization problems (9), we transform them into another simple form and have the following theorem.Theorem 1.
The optimization problems (9) can be transformed into the following minimization problem:(11)
m
i
n
F
T
F
=
I
c
t
r
F
T
L
~
+
μ
L
F
F
,where L
F
=
I
n
-
K
(
K
+
γ
g
I
n
)
-
1 and I
n denotes the identity matrix of sizen byn.Proof.
Problem (9) is firstly transformed into the following form:(12)
m
i
n
F
,
α
F
T
F
=
I
c
t
r
F
T
L
~
F
+
μ
t
r
F
-
K
α
T
F
-
K
α
+
γ
g
t
r
α
T
K
α
,where α
=
α
1
,
…
,
α
n
T
∈
R
n
×
c.
By setting the derivatives of the objective function (16) with respect to α to zero, we have(13)
α
=
γ
g
I
n
+
K
-
1
F
.By substituting α in (12) by (13), the optimization problem (12) becomes(14)
m
i
n
F
T
F
=
I
c
t
r
F
T
L
~
F
+
μ
t
r
F
T
I
n
-
K
K
+
γ
g
I
n
-
1
Fwhich can be denoted as follows:(15)
m
i
n
F
T
F
=
I
c
t
r
F
T
L
~
+
μ
L
F
F
,where L
F
=
I
n
-
K
(
K
+
γ
g
I
n
)
-
1. This completes the proof of Theorem 1.Based on Theorem1, the relaxed cluster assignment matrix F
∗ of KSEC can be achieved by computing the eigenvectors of L
~
+
μ
L
F corresponding to the c smallest eigenvalues. The columns of F
∗ are corresponding to the top c eigenvectors. Finally, the discrete-valued cluster assignment matrix can be obtained by clustering each row of F
∗.To inherit the advantage of fast learning speed of ELM, we mainly discuss ESEC based on ELM with multioutputs, since ELM with single output can be regarded as a special case of it. We have the following theorem on ESEC, which is the foundation of the proposed ESEC algorithm.Theorem 2.
The optimization problem (10) can be transformed into the following minimization problem:(16)
m
i
n
F
T
F
=
I
c
t
r
F
T
L
~
+
μ
L
H
F
,where L
H
=
I
n
-
H
H
T
(
γ
g
I
n
+
H
H
T
)
-
1 or L
H
=
I
n
-
H
(
γ
g
I
L
+
H
T
H
)
-
1
H
T. I
L denotes the identity matrix of size c by c and L is the number of hidden layer nodes in ELM.Proof.
By setting the derivatives of the objective function (10) with respect to β to zero, we have(17)
β
=
H
T
γ
g
I
n
+
H
H
T
-
1
F
.By substituting β in (10) by (17), the optimization problem (10) becomes(18)
m
i
n
F
T
F
=
I
c
t
r
F
T
L
~
F
+
μ
t
r
F
-
H
H
T
γ
g
I
n
+
H
H
T
-
1
F
T
F
-
H
H
T
γ
g
I
n
+
H
H
T
-
1
F
+
γ
g
t
r
F
T
γ
g
I
n
+
H
H
T
-
1
H
H
T
γ
g
I
n
+
H
H
T
-
1
F
.Problem (18) can be further transformed into the following objective function:(19)
m
i
n
F
T
F
=
I
c
t
r
F
T
L
~
F
+
μ
t
r
F
T
I
n
-
H
H
T
γ
g
I
n
+
H
H
T
-
1
Fwhich can be denoted as follows:(20)
m
i
n
F
T
F
=
I
c
t
r
F
T
L
~
+
μ
L
H
F
,where L
H
=
I
n
-
H
H
T
(
γ
g
I
n
+
H
H
T
)
-
1. L
H can be transformed into another form as follows: (21)
L
H
=
I
n
-
H
γ
g
I
L
+
H
T
H
-
1
·
γ
g
I
L
+
H
T
H
·
H
T
γ
g
I
n
+
H
H
T
-
1
=
I
n
-
H
γ
g
I
L
+
H
T
H
-
1
H
T
.This completes the proof of Theorem 2.ESEC makes good use of an embedding function in ELM feature space instead of RKHS. Thus, the form of ESEC is similar to that of KSEC. It can be proved that there is a link between ESEC and KSEC. We have the following theorem.Theorem 3.
If the mappingh
x in ELM is (
1
/
L
)
k
b
1
x
,
a
1
,
k
b
2
x
,
a
2
,
…
,
k
b
L
(
x
,
a
L
), where k denotes any kernel function andL is the number of hidden nodes in ELM and a
i
,
b
i
i
=
1
L (b
i is the parameter of kernel function k
(
x
1
,
x
2
)) are random sampling points from any continuous probability distribution, then ESEC is an approximation of KSEC by discretizing the embedding function f
x
=
∑
i
=
1
n
α
i
k
(
x
i
,
x
).Proof.
Sincek
x
,
x
i
=
k
x
i
,
·
·
k
x
,
· in RKHS, f
x can be denoted as(22)
f
x
=
k
x
1
,
·
·
k
x
,
·
,
…
,
k
x
n
,
·
·
k
x
,
·
α
,where α
=
(
γ
g
I
n
+
K
)
-
1
F. Let h
(
x
)
=
(
1
/
L
)
(
k
b
1
x
,
a
1
,
k
b
2
x
,
a
2
,
…
,
k
b
L
(
x
,
a
L
)
) and H
=
h
x
1
,
h
x
2
,
…
,
h
x
n; then(23)
f
x
≈
h
x
H
T
γ
g
I
n
+
H
H
T
-
1
F
=
h
x
β
.Thus, we approximately derive the embedding function of ESEC from KSEC. This completes the proof of Theorem 3.The proposed ESEC algorithm is described as follows.Algorithm 1.
Input. The input is the training dataset X
=
x
1
,
x
2
,
…
,
x
n
∈
R
d
×
n and the number of clusters c.
Output. The output is the class assignment matrix of cluster Y.
Step  1. Construct the graph Laplacian L from X.
Step  2. Randomly generate input weights a
i
,
b
i
i
=
1
L and initiate an ELM network of L hidden neurons; calculate the output matrix of the hidden layer.
Step  3.If
L
≤
n; let L
H
=
I
n
-
H
(
γ
g
I
L
+
H
T
H
)
-
1
H
T.
Else
L
H
=
I
n
-
H
H
T
(
γ
g
I
n
+
H
H
T
)
-
1.
Step  4. Compute the matrix L
~
+
μ
L
H.
Step  5. Find the eigenvectors of L
~
+
μ
L
H corresponding to the c smallest eigenvalues, which form the optimal F
∗.
Step  6. Treat each row of F
∗ as a new training sample, and use theK-means algorithm to cluster the n training samples into c clusters. Let F
D
∗ be the final discrete class assignment matrix of cluster for training data.
Return the class assignment matrix of cluster F
D
∗.


### 3.3. Computational Complexity

From Algorithm1, we can see that the most costly computation is computing the matrix L
H and carrying out the eigen-decomposition of L
~
+
μ
L
H. If L
≪
n, computing L
H needs to obtain the inversion of γ
g
I
L
+
H
T
H, whose computational complexity is O
L
3
+
L
n
2. In addition, the computational complexity of eigenvalue decomposition of L
~
+
μ
L
H is O
n
3. Thus, the total computational complexity of ESEC is O
n
3
+
L
3
+
L
n
2, where L
≪
n. Correspondingly, for KSEC, computational complexity of calculating L
F is O
n
3 and its total computational complexity is O
2
n
3. Consequently, ESEC has lower computational complexity than KSEC.


### 3.4. Clustering for Out-of-Sample Data

By performing Algorithm1, we can obtain the cluster assignment matrix F
D
∗ for the training data. Thus, β can be easily computed by using formula (17). Then, for any new data point x
∈
R
d, we can obtain the prediction result (24)
y
=
h
x
β
=
h
x
H
T
γ
g
I
n
+
H
H
T
-
1
F
D
∗
.In this paper, we use the spectral rotation method to calculate the discrete cluster assignment vector for x. Firstly, an orthogonal matrix R is computed by the following spectral rotation method:(25)
m
i
n
Y
∈
B
n
×
c
,
R
∈
R
c
×
c
Y
-
Y
∗
R
2
s
.
t
.
Y
1
c
=
1
n
,
R
T
R
=
I
c
,where 1
c and 1
n denote the c
×
1 and n
×
1 vectors of all 1s, respectively. R
∈
R
c
×
c is an orthogonal matrix and Y
∗ is defined by(26)
Y
∗
=
D
i
a
g
F
∗
F
∗
T
-
1
/
2
F
∗
,where D
i
a
g
(
A
) represents a diagonal matrix with the same diagonal elements as the square matrix A. Secondly, the discrete cluster assignment vector for x is calculated as follows:(27)
y
~
=
R
T
y
y
2
.Finally, the class of the data point x is(28)
l
a
b
e
l
=
a
r
g
max
i
⁡
y
~
i
,where y
~
(
i
) is theith element in the vector y
~.


## 3.1. Formulation

Generally, clustering models of traditional SC methods can be transformed into the following minimization problem:(6)
m
i
n
F
T
F
=
I
c
t
r
F
T
L
~
F
,where L
~
=
D
-
(
1
/
2
)
L
D
-
(
1
/
2
)
=
I
n
-
D
-
(
1
/
2
)
W
D
-
(
1
/
2
) is the normalized Laplacian matrix.To make use of the underlying dense grouping structure of data in a low-dimensional subspace, the proposed general framework introduces a regularization term into the optimization problem (6), which controls the error between the cluster assignment matrix and the low-dimensional embedding of the data. Specifically, we minimize the following objective function:(7)
m
i
n
F
T
F
=
I
c
t
r
F
T
L
~
F
+
μ
ϕ
X
-
F
2
+
γ
g
ϕ
2
,where μ and γ
g are two regularization parameters and ϕ
X
=
ψ
1
X
,
…
,
ψ
c
(
X
)
∈
R
n
×
c is the low-dimensional embedding of training data. The second term represents the error between the relaxed cluster assignment matrix F and the low-dimensional embedding of the data. The third term is the norm penalty of ϕ
X and represents the complexity of functions in a high-dimensional feature space.In dimensionality reduction, linear embedding functions and nonlinear embedding functions are commonly used to address out-of-sample problems. This is due to the fact that they contain few parameters, which are not expensive in computational time and memory. In this paper, we mainly discuss kernel-based and ELM-based nonlinear embedding functions.If we choose a linear embedding functiony
=
W
T
x
+
b, ϕ
X
=
X
T
W
+
1
n
b
T, where W
∈
R
d
×
c and b
∈
R
c
×
1, the optimization problem (7) becomes(8)
m
i
n
F
,
W
,
b
F
T
F
=
I
c
t
r
F
T
L
~
F
+
μ
X
T
W
+
1
n
b
T
-
F
2
+
γ
g
t
r
W
T
Wwhich is equivalent to the SEC method proposed in [12].If we use a nonlinear embedding function in RKHS, that is,y
=
f
x
=
∑
i
=
1
n
α
i
k
(
x
,
x
i
), then ϕ
X
=
K
α, where K is a symmetric kernel matrix and α
=
α
1
,
…
,
α
n
T
∈
R
n
×
c; problem (7) can be rewritten as(9)
m
i
n
F
,
α
F
T
F
=
I
c
t
r
F
T
L
~
F
+
μ
K
α
-
F
2
+
γ
g
t
r
α
T
K
αwhich is referred to as KSEC.Alternatively, if we consider an embedding function in ELM feature space, that is,f
x
=
∑
i
=
1
L
β
i
h
i
x
=
h
x
β, then ϕ
X
=
H
β, where H represents the hidden-layer output matrix of ELM. Problem (7) can be reformulated as (10)
m
i
n
F
,
β
F
T
F
=
I
c
t
r
F
T
L
~
F
+
μ
H
β
-
F
2
+
γ
g
t
r
β
T
β
,which is referred to as ESEC.


## 3.2. Method

Firstly, to solve the optimization problems (9), we transform them into another simple form and have the following theorem.Theorem 1.
The optimization problems (9) can be transformed into the following minimization problem:(11)
m
i
n
F
T
F
=
I
c
t
r
F
T
L
~
+
μ
L
F
F
,where L
F
=
I
n
-
K
(
K
+
γ
g
I
n
)
-
1 and I
n denotes the identity matrix of sizen byn.Proof.
Problem (9) is firstly transformed into the following form:(12)
m
i
n
F
,
α
F
T
F
=
I
c
t
r
F
T
L
~
F
+
μ
t
r
F
-
K
α
T
F
-
K
α
+
γ
g
t
r
α
T
K
α
,where α
=
α
1
,
…
,
α
n
T
∈
R
n
×
c.
By setting the derivatives of the objective function (16) with respect to α to zero, we have(13)
α
=
γ
g
I
n
+
K
-
1
F
.By substituting α in (12) by (13), the optimization problem (12) becomes(14)
m
i
n
F
T
F
=
I
c
t
r
F
T
L
~
F
+
μ
t
r
F
T
I
n
-
K
K
+
γ
g
I
n
-
1
Fwhich can be denoted as follows:(15)
m
i
n
F
T
F
=
I
c
t
r
F
T
L
~
+
μ
L
F
F
,where L
F
=
I
n
-
K
(
K
+
γ
g
I
n
)
-
1. This completes the proof of Theorem 1.Based on Theorem1, the relaxed cluster assignment matrix F
∗ of KSEC can be achieved by computing the eigenvectors of L
~
+
μ
L
F corresponding to the c smallest eigenvalues. The columns of F
∗ are corresponding to the top c eigenvectors. Finally, the discrete-valued cluster assignment matrix can be obtained by clustering each row of F
∗.To inherit the advantage of fast learning speed of ELM, we mainly discuss ESEC based on ELM with multioutputs, since ELM with single output can be regarded as a special case of it. We have the following theorem on ESEC, which is the foundation of the proposed ESEC algorithm.Theorem 2.
The optimization problem (10) can be transformed into the following minimization problem:(16)
m
i
n
F
T
F
=
I
c
t
r
F
T
L
~
+
μ
L
H
F
,where L
H
=
I
n
-
H
H
T
(
γ
g
I
n
+
H
H
T
)
-
1 or L
H
=
I
n
-
H
(
γ
g
I
L
+
H
T
H
)
-
1
H
T. I
L denotes the identity matrix of size c by c and L is the number of hidden layer nodes in ELM.Proof.
By setting the derivatives of the objective function (10) with respect to β to zero, we have(17)
β
=
H
T
γ
g
I
n
+
H
H
T
-
1
F
.By substituting β in (10) by (17), the optimization problem (10) becomes(18)
m
i
n
F
T
F
=
I
c
t
r
F
T
L
~
F
+
μ
t
r
F
-
H
H
T
γ
g
I
n
+
H
H
T
-
1
F
T
F
-
H
H
T
γ
g
I
n
+
H
H
T
-
1
F
+
γ
g
t
r
F
T
γ
g
I
n
+
H
H
T
-
1
H
H
T
γ
g
I
n
+
H
H
T
-
1
F
.Problem (18) can be further transformed into the following objective function:(19)
m
i
n
F
T
F
=
I
c
t
r
F
T
L
~
F
+
μ
t
r
F
T
I
n
-
H
H
T
γ
g
I
n
+
H
H
T
-
1
Fwhich can be denoted as follows:(20)
m
i
n
F
T
F
=
I
c
t
r
F
T
L
~
+
μ
L
H
F
,where L
H
=
I
n
-
H
H
T
(
γ
g
I
n
+
H
H
T
)
-
1. L
H can be transformed into another form as follows: (21)
L
H
=
I
n
-
H
γ
g
I
L
+
H
T
H
-
1
·
γ
g
I
L
+
H
T
H
·
H
T
γ
g
I
n
+
H
H
T
-
1
=
I
n
-
H
γ
g
I
L
+
H
T
H
-
1
H
T
.This completes the proof of Theorem 2.ESEC makes good use of an embedding function in ELM feature space instead of RKHS. Thus, the form of ESEC is similar to that of KSEC. It can be proved that there is a link between ESEC and KSEC. We have the following theorem.Theorem 3.
If the mappingh
x in ELM is (
1
/
L
)
k
b
1
x
,
a
1
,
k
b
2
x
,
a
2
,
…
,
k
b
L
(
x
,
a
L
), where k denotes any kernel function andL is the number of hidden nodes in ELM and a
i
,
b
i
i
=
1
L (b
i is the parameter of kernel function k
(
x
1
,
x
2
)) are random sampling points from any continuous probability distribution, then ESEC is an approximation of KSEC by discretizing the embedding function f
x
=
∑
i
=
1
n
α
i
k
(
x
i
,
x
).Proof.
Sincek
x
,
x
i
=
k
x
i
,
·
·
k
x
,
· in RKHS, f
x can be denoted as(22)
f
x
=
k
x
1
,
·
·
k
x
,
·
,
…
,
k
x
n
,
·
·
k
x
,
·
α
,where α
=
(
γ
g
I
n
+
K
)
-
1
F. Let h
(
x
)
=
(
1
/
L
)
(
k
b
1
x
,
a
1
,
k
b
2
x
,
a
2
,
…
,
k
b
L
(
x
,
a
L
)
) and H
=
h
x
1
,
h
x
2
,
…
,
h
x
n; then(23)
f
x
≈
h
x
H
T
γ
g
I
n
+
H
H
T
-
1
F
=
h
x
β
.Thus, we approximately derive the embedding function of ESEC from KSEC. This completes the proof of Theorem 3.The proposed ESEC algorithm is described as follows.Algorithm 1.
Input. The input is the training dataset X
=
x
1
,
x
2
,
…
,
x
n
∈
R
d
×
n and the number of clusters c.
Output. The output is the class assignment matrix of cluster Y.
Step  1. Construct the graph Laplacian L from X.
Step  2. Randomly generate input weights a
i
,
b
i
i
=
1
L and initiate an ELM network of L hidden neurons; calculate the output matrix of the hidden layer.
Step  3.If
L
≤
n; let L
H
=
I
n
-
H
(
γ
g
I
L
+
H
T
H
)
-
1
H
T.
Else
L
H
=
I
n
-
H
H
T
(
γ
g
I
n
+
H
H
T
)
-
1.
Step  4. Compute the matrix L
~
+
μ
L
H.
Step  5. Find the eigenvectors of L
~
+
μ
L
H corresponding to the c smallest eigenvalues, which form the optimal F
∗.
Step  6. Treat each row of F
∗ as a new training sample, and use theK-means algorithm to cluster the n training samples into c clusters. Let F
D
∗ be the final discrete class assignment matrix of cluster for training data.
Return the class assignment matrix of cluster F
D
∗.


## 3.3. Computational Complexity

From Algorithm1, we can see that the most costly computation is computing the matrix L
H and carrying out the eigen-decomposition of L
~
+
μ
L
H. If L
≪
n, computing L
H needs to obtain the inversion of γ
g
I
L
+
H
T
H, whose computational complexity is O
L
3
+
L
n
2. In addition, the computational complexity of eigenvalue decomposition of L
~
+
μ
L
H is O
n
3. Thus, the total computational complexity of ESEC is O
n
3
+
L
3
+
L
n
2, where L
≪
n. Correspondingly, for KSEC, computational complexity of calculating L
F is O
n
3 and its total computational complexity is O
2
n
3. Consequently, ESEC has lower computational complexity than KSEC.


## 3.4. Clustering for Out-of-Sample Data

By performing Algorithm1, we can obtain the cluster assignment matrix F
D
∗ for the training data. Thus, β can be easily computed by using formula (17). Then, for any new data point x
∈
R
d, we can obtain the prediction result (24)
y
=
h
x
β
=
h
x
H
T
γ
g
I
n
+
H
H
T
-
1
F
D
∗
.In this paper, we use the spectral rotation method to calculate the discrete cluster assignment vector for x. Firstly, an orthogonal matrix R is computed by the following spectral rotation method:(25)
m
i
n
Y
∈
B
n
×
c
,
R
∈
R
c
×
c
Y
-
Y
∗
R
2
s
.
t
.
Y
1
c
=
1
n
,
R
T
R
=
I
c
,where 1
c and 1
n denote the c
×
1 and n
×
1 vectors of all 1s, respectively. R
∈
R
c
×
c is an orthogonal matrix and Y
∗ is defined by(26)
Y
∗
=
D
i
a
g
F
∗
F
∗
T
-
1
/
2
F
∗
,where D
i
a
g
(
A
) represents a diagonal matrix with the same diagonal elements as the square matrix A. Secondly, the discrete cluster assignment vector for x is calculated as follows:(27)
y
~
=
R
T
y
y
2
.Finally, the class of the data point x is(28)
l
a
b
e
l
=
a
r
g
max
i
⁡
y
~
i
,where y
~
(
i
) is theith element in the vector y
~.


## 4. Experiments

To evaluate the in-sample clustering and out-sample clustering performance of different clustering methods, we test all algorithms on UCI datasets (Iris, Glass, Wine, WPBC, SpectHeart, and Isolet (http://archive.ics.uci.edu/ml/datasets.html.)), face recognition datasets (Yale (http://vision.ucsd.edu/~leekc/ExtYaleDatabase/Yale%20Face%20Database.htm.), ORL (http://www.cl.cam.ac.uk/research/dtg/attarchive/facedatabase.html.)), digits recognition datasets (USPS (http://www-i6.informatik.rwth-aachen.de/~keysers/usps.html)), and object recognition datasets (COIL-20 (http://www.cs.columbia.edu/CAVE/software/softlib/coil-20.php.)). Some datasets are resized, and the basic information of datasets is listed in Table 1. All the experiments have been performed in MATLAB R2013a running in a 3.10 GHZ Intel Core™i5-2400 with 4 GB RAM.Table 1
Dataset description.
Dataset
Size
Dimensions
Classes
Iris
150
4
3
Glass
214
10
6
Wine
178
13
3
WPBC
198
33
2
SpectfHeart
267
44
2
USPS
900
256
3
Yale
165
1024
15
COIL20
1440
16384
20
Isolet
390
1234
13
ORL
100
4096
10In in-sample clustering, we assign a cluster label to each unlabeled in-sample data point. The proposed ESEC algorithm is compared withK-means (KM) clustering, SC [3], SEC [12], and KSEC. For KM, an EM-like algorithm is used to assign cluster labels as in [16]. In out-sample clustering, the cluster label of each unseen data point is assigned to the closest cluster center learned from the in-sample data points for KM. We use the proposed out-of-sample approach to cope with unseen data for ESEC. Similar out-of-sample method is also used for KSEC and SEC by using different embedding functions. Since the Nyström method [10] can be used to deal with unseen data, we also compare ESEC with the Nyström method for the out-of-sample SC.


### 4.1. Experimental Setup

Each dataset is randomly divided into seen and unseen samples, and we use the seen data to obtain the optimal parameters of different clustering methods by cross-validation. Then, we use the unseen data to test the performance of all algorithms using the obtained optimal parameters. In the experiments, 80% of the data are randomly selected as seen data and the remaining data are used as unseen data.The self-tuning SC method [17] is used to determine the parameter σ in (1) for SC, SEC, KSEC, and ESEC. The parameterK ofK-nearest-neighbor graph is set to 5 empirically. For fair comparisons, we set the parameters γ
g in SEC, KSEC, and ESEC as 1 and select the parameter μ in these methods from 10
-
9
,
10
-
6
,
10
-
3
,
…
,
10
0
,
…
,
10
3
,
10
6
,
10
9
,
10
12
,
10
15.For the Nyström SC method, we set the sameσ
=
2
σ
0, where σ
0
=
1
/
A, with A being the mean value of the square distance between the in-sample data as suggested in [18] and r
=
-
3
,
-
2
,
-
1,0
,
1,2
,
3. For the in-sample clustering, the best clustering results from the best parameters for SEC, KSEC, and ESEC are reported in Table 2. For ESEC, we use the RBF kernel as the hidden node function and a grid search of the number of hidden nodes L on {
10
,
20
,
…
,
900
,
1000
} is conducted to seek for the optimal result by using fivefold cross-validation. By means of the optimal parameters in in-sample setting, the results for the out-of-sample clustering are obtained and reported in Table 3.Table 2
Performance comparison of clustering accuracy using KM, SC, SEC, KSEC, and ESEC for the in-sample clustering on ten datasets.
Dataset
KM
SC
SEC
KSEC
ESEC
Iris
82.1 ± 1.9
83.3 ± 1.9
68.9 ± 1.5
83.3 ± 1.8
90.4 ± 2.3
Glass
54.9 ± 0.9
58.9 ± 1.3
59.3 ± 1.6
59.8 ± 2.1
72.2 ± 1.6
Wine
57.1 ± 1.8
57.9 ± 1.9
44.9 ± 1.8
60.1 ± 2.4
61.8 ± 1.8
WPBC
63.6 ± 1.9
74.2 ± 1.4
77.2 ± 1.4
77.2 ± 1.3
74.1 ± 1.2
SpectfHeart
61.6 ± 3.1
78.7 ± 3.7
55.4 ± 1.3
79.8 ± 3.9
76.7 ± 2.5
USPS
63.7 ± 1.2
61.3 ± 2.4
65.1 ± 1.7
61.9 ± 2.5
65.9 ± 2.6
Yale
37.8 ± 1.5
35.9 ± 1.7
30.9 ± 3.4
37.3 ± 1.6
40.8 ± 1.9
COIL20
67.0 ± 3.4
76.2 ± 3.3
67.6 ± 1.4
78.8 ± 2.8
77.0 ± 2.4
Isolet
66.6 ± 0.9
65.4 ± 2.6
68.7 ± 1.8
76.4 ± 2.2
70.6 ± 2.6
ORL
59.3 ± 1.5
58.2 ± 2.9
50.9 ± 3.8
61.4 ± 1.9
60.7 ± 2.7Table 3
Time cost comparison of KM, SC, SEC, KSEC, and ESEC for the in-sample clustering on ten datasets.
Dataset
KM
SC
SEC
KSEC
ESEC
Iris
0.285
0.267
0.296
0.336
0.294
Glass
0.319
0.333
0.304
0.492
0.455
Wine
0.434
0.342
0.260
0.313
0.300
WPBC
0.471
0.475
0.394
0.599
0.319
SpectfHeart
0.662
0.416
0.408
0.744
0.357
USPS
0.316
9.840
10.228
26.031
10.602
Yale
0.602
0.723
1.206
0.982
0.571
COIL20
0.839
74.387
64.485
106.438
83.458
Isolet
0.799
4.479
5.407
5.190
0.893
ORL
0.438
0.919
1.901
1.664
1.149It should be noted that the results of all clustering methods rely on the initialization. To get statistical results for different parameters and random partitions, all clustering algorithms are independently repeated 50 times, and we report the mean clustering result and standard deviation using the best parameters on the seen and unseen data. In the experiments, we set the number of clusters as the number of classesc in each dataset. The clustering accuracy (ACC) (refer to [19] for its definition) and time cost are used to evaluate the clustering performance.


### 4.2. In-Sample Clustering Experiments

To compare clustering performances of various clustering algorithms, we report the in-sample clustering results on all the datasets in Table2. As can be seen from Table 2, SC outperforms KM for most of the low dimensionality datasets, such as Iris, Glass, Wine, WPBC, and SpectfHeart. But, it might become worse on the high dimensionality datasets, such as Yale and Isolet. This is due to the fact that SC prefers the datasets that have a clear manifold structure in a low-dimensional space. If this assumption does not hold, it even performs worse than the KM algorithm. The performance of SEC is better than KM and SC on Glass, WPBC, USPS, and Isolet. Hence, it does not achieve overwhelming advantages for in-sample clustering on all datasets. One possible explanation is that SEC improves SC by introducing the linear embedding functions, which is only applicable to the data with linear or approximately linear structures. KSEC and ESEC significantly outperform KM, SC, and SEC in most cases. KSEC and ESEC all achieve 5 best in-sample clustering results among all datasets. It should be noted that KSEC and ESEC also have superior clustering performance for low dimensionality datasets, since they all introduce regularization terms into SC and can be considered as regularized SC. Compared with KSEC, ESEC achieves better or at least comparable results, which demonstrates that the proposed ESEC method is effective on all the datasets and has the ability to handle the datasets that do not have a clear manifold structure in a low-dimensional space. The running time of all algorithms is listed in Table 3. It is shown that ESEC runs much faster than KSEC, which is consistent with the theoretical analysis, and the running time of ESEC and KSEC is lower than that of KM, SC, and SEC for most of the datasets. Overall, compared with other methods, the proposed ESEC method has better or comparative in-sample performance at much faster training speed.In Figure1, we further analyze the sensitivity of the in-sample clustering performances of SEC, KSEC, and ESEC with respect to the parameter μ. We can see from Figure 1 that ESEC prefers a large value for μ on Yale and ORL, and its performance on these datasets is relatively stable when μ is set as a large value. While ESEC and KSEC favor a small value of μ for COIL20 and Isolet. We can observe that ESEC outperforms KSEC and SEC in a wide range of μ; that is, the clustering accuracy of ESEC is less sensitive to the parameter for most of the datasets when compared with SEC and KSEC.Figure 1
Clustering accuracy of SEC, KSEC, and ESEC with differentμ for the in-sample clustering on the six datasets. (a) Iris. (b) USPS. (c) Yale. (d) COIL20. (e) Isolet. (f) ORL.
(a)
(b)
(c)
(d)
(e)
(f)


### 4.3. Out-of-Sample Clustering Experiments

We also study the performances of KM, Nyström SC, SEC, KSEC, and ESEC for the out-of-sample extension. Table4 shows the clustering accuracies of these methods for the out-of-sample clustering on all the datasets. The optimal parameters of SEC, KSEC, and ESEC are determined by cross-validation from the in-sample clustering. From Table 4, it can be seen that SEC, KSEC, and ESEC significantly outperform the Nyström method for out-of-sample clustering. The reason is that the Nyström method utilizes Nyström extension to evaluate the similarity matrix between the unseen data, which might be inaccurate or even has a serious deviation. However, our proposed framework aims at minimizing the error between the cluster assignment matrix and the low-dimensional embedding of the data, which is feasible for handling real-world data. Thus, ESEC has the natural ability of solving out-of-sample extension problems. In addition, KM is sharply degraded on Yale and ORL compared with the corresponding results in Table 2. This is due to the fact that the unseen face data has the large variation compared to the seen data. On the other hand, the clustering accuracies of ESEC are comparable to the in-sample testing results, which validates that ESEC has better generalization performance. ESEC achieves 6 best clustering results among all ten testing results and has comparable results on the rest of the datasets when compared to KSEC. Consequently, the proposed ESEC algorithm provides a new way to cope with the out-of-sample data in clustering tasks.Table 4
Performance comparison of different algorithms for the out-of-sample clustering on ten datasets.
Dataset
Nyström SC
KM
SEC
KSEC
ESEC
Iris
73.6 ± 1.8
75.6 ± 1.9
63.0 ± 1.9
77.1 ± 2.7
79.8 ± 2.1
Glass
49.7 ± 0.9
57.4 ± 1.2
58.6 ± 1.6
58.9 ± 2.4
63.1 ± 2.5
Wine
45.2 ± 0.9
54.6 ± 2.1
49.7 ± 1.9
61.2 ± 2.3
63.7 ± 1.9
WPBC
52.2 ± 2.8
64.7 ± 1.5
73.5 ± 1.5
74.3 ± 1.6
76.2 ± 1.4
SpectfHeart
51.4 ± 1.9
66.8 ± 2.9
53.5 ± 1.7
72.2 ± 2.3
70.8 ± 2.6
USPS
48.3 ± 4.5
56.0 ± 2.2
61.5 ± 2.4
65.1 ± 1.6
62.3 ± 2.8
Yale
20.7 ± 2.3
23.0 ± 1.6
35.9 ± 1.7
42.5 ± 1.6
45.8 ± 1.9
COIL20
63.9 ± 2.4
61.6 ± 3.3
68.9 ± 2.5
72.4 ± 2.7
70.2 ± 3.1
Isolet
34.8 ± 2.7
39.2 ± 1.2
45.3 ± 2.9
66.0 ± 1.8
68.4 ± 1.5
ORL
43.5 ± 2.1
47.6 ± 1.8
55.2 ± 1.5
60.7 ± 1.9
58.7 ± 1.7


## 4.1. Experimental Setup

Each dataset is randomly divided into seen and unseen samples, and we use the seen data to obtain the optimal parameters of different clustering methods by cross-validation. Then, we use the unseen data to test the performance of all algorithms using the obtained optimal parameters. In the experiments, 80% of the data are randomly selected as seen data and the remaining data are used as unseen data.The self-tuning SC method [17] is used to determine the parameter σ in (1) for SC, SEC, KSEC, and ESEC. The parameterK ofK-nearest-neighbor graph is set to 5 empirically. For fair comparisons, we set the parameters γ
g in SEC, KSEC, and ESEC as 1 and select the parameter μ in these methods from 10
-
9
,
10
-
6
,
10
-
3
,
…
,
10
0
,
…
,
10
3
,
10
6
,
10
9
,
10
12
,
10
15.For the Nyström SC method, we set the sameσ
=
2
σ
0, where σ
0
=
1
/
A, with A being the mean value of the square distance between the in-sample data as suggested in [18] and r
=
-
3
,
-
2
,
-
1,0
,
1,2
,
3. For the in-sample clustering, the best clustering results from the best parameters for SEC, KSEC, and ESEC are reported in Table 2. For ESEC, we use the RBF kernel as the hidden node function and a grid search of the number of hidden nodes L on {
10
,
20
,
…
,
900
,
1000
} is conducted to seek for the optimal result by using fivefold cross-validation. By means of the optimal parameters in in-sample setting, the results for the out-of-sample clustering are obtained and reported in Table 3.Table 2
Performance comparison of clustering accuracy using KM, SC, SEC, KSEC, and ESEC for the in-sample clustering on ten datasets.
Dataset
KM
SC
SEC
KSEC
ESEC
Iris
82.1 ± 1.9
83.3 ± 1.9
68.9 ± 1.5
83.3 ± 1.8
90.4 ± 2.3
Glass
54.9 ± 0.9
58.9 ± 1.3
59.3 ± 1.6
59.8 ± 2.1
72.2 ± 1.6
Wine
57.1 ± 1.8
57.9 ± 1.9
44.9 ± 1.8
60.1 ± 2.4
61.8 ± 1.8
WPBC
63.6 ± 1.9
74.2 ± 1.4
77.2 ± 1.4
77.2 ± 1.3
74.1 ± 1.2
SpectfHeart
61.6 ± 3.1
78.7 ± 3.7
55.4 ± 1.3
79.8 ± 3.9
76.7 ± 2.5
USPS
63.7 ± 1.2
61.3 ± 2.4
65.1 ± 1.7
61.9 ± 2.5
65.9 ± 2.6
Yale
37.8 ± 1.5
35.9 ± 1.7
30.9 ± 3.4
37.3 ± 1.6
40.8 ± 1.9
COIL20
67.0 ± 3.4
76.2 ± 3.3
67.6 ± 1.4
78.8 ± 2.8
77.0 ± 2.4
Isolet
66.6 ± 0.9
65.4 ± 2.6
68.7 ± 1.8
76.4 ± 2.2
70.6 ± 2.6
ORL
59.3 ± 1.5
58.2 ± 2.9
50.9 ± 3.8
61.4 ± 1.9
60.7 ± 2.7Table 3
Time cost comparison of KM, SC, SEC, KSEC, and ESEC for the in-sample clustering on ten datasets.
Dataset
KM
SC
SEC
KSEC
ESEC
Iris
0.285
0.267
0.296
0.336
0.294
Glass
0.319
0.333
0.304
0.492
0.455
Wine
0.434
0.342
0.260
0.313
0.300
WPBC
0.471
0.475
0.394
0.599
0.319
SpectfHeart
0.662
0.416
0.408
0.744
0.357
USPS
0.316
9.840
10.228
26.031
10.602
Yale
0.602
0.723
1.206
0.982
0.571
COIL20
0.839
74.387
64.485
106.438
83.458
Isolet
0.799
4.479
5.407
5.190
0.893
ORL
0.438
0.919
1.901
1.664
1.149It should be noted that the results of all clustering methods rely on the initialization. To get statistical results for different parameters and random partitions, all clustering algorithms are independently repeated 50 times, and we report the mean clustering result and standard deviation using the best parameters on the seen and unseen data. In the experiments, we set the number of clusters as the number of classesc in each dataset. The clustering accuracy (ACC) (refer to [19] for its definition) and time cost are used to evaluate the clustering performance.


## 4.2. In-Sample Clustering Experiments

To compare clustering performances of various clustering algorithms, we report the in-sample clustering results on all the datasets in Table2. As can be seen from Table 2, SC outperforms KM for most of the low dimensionality datasets, such as Iris, Glass, Wine, WPBC, and SpectfHeart. But, it might become worse on the high dimensionality datasets, such as Yale and Isolet. This is due to the fact that SC prefers the datasets that have a clear manifold structure in a low-dimensional space. If this assumption does not hold, it even performs worse than the KM algorithm. The performance of SEC is better than KM and SC on Glass, WPBC, USPS, and Isolet. Hence, it does not achieve overwhelming advantages for in-sample clustering on all datasets. One possible explanation is that SEC improves SC by introducing the linear embedding functions, which is only applicable to the data with linear or approximately linear structures. KSEC and ESEC significantly outperform KM, SC, and SEC in most cases. KSEC and ESEC all achieve 5 best in-sample clustering results among all datasets. It should be noted that KSEC and ESEC also have superior clustering performance for low dimensionality datasets, since they all introduce regularization terms into SC and can be considered as regularized SC. Compared with KSEC, ESEC achieves better or at least comparable results, which demonstrates that the proposed ESEC method is effective on all the datasets and has the ability to handle the datasets that do not have a clear manifold structure in a low-dimensional space. The running time of all algorithms is listed in Table 3. It is shown that ESEC runs much faster than KSEC, which is consistent with the theoretical analysis, and the running time of ESEC and KSEC is lower than that of KM, SC, and SEC for most of the datasets. Overall, compared with other methods, the proposed ESEC method has better or comparative in-sample performance at much faster training speed.In Figure1, we further analyze the sensitivity of the in-sample clustering performances of SEC, KSEC, and ESEC with respect to the parameter μ. We can see from Figure 1 that ESEC prefers a large value for μ on Yale and ORL, and its performance on these datasets is relatively stable when μ is set as a large value. While ESEC and KSEC favor a small value of μ for COIL20 and Isolet. We can observe that ESEC outperforms KSEC and SEC in a wide range of μ; that is, the clustering accuracy of ESEC is less sensitive to the parameter for most of the datasets when compared with SEC and KSEC.Figure 1
Clustering accuracy of SEC, KSEC, and ESEC with differentμ for the in-sample clustering on the six datasets. (a) Iris. (b) USPS. (c) Yale. (d) COIL20. (e) Isolet. (f) ORL.
(a)
(b)
(c)
(d)
(e)
(f)


## 4.3. Out-of-Sample Clustering Experiments

We also study the performances of KM, Nyström SC, SEC, KSEC, and ESEC for the out-of-sample extension. Table4 shows the clustering accuracies of these methods for the out-of-sample clustering on all the datasets. The optimal parameters of SEC, KSEC, and ESEC are determined by cross-validation from the in-sample clustering. From Table 4, it can be seen that SEC, KSEC, and ESEC significantly outperform the Nyström method for out-of-sample clustering. The reason is that the Nyström method utilizes Nyström extension to evaluate the similarity matrix between the unseen data, which might be inaccurate or even has a serious deviation. However, our proposed framework aims at minimizing the error between the cluster assignment matrix and the low-dimensional embedding of the data, which is feasible for handling real-world data. Thus, ESEC has the natural ability of solving out-of-sample extension problems. In addition, KM is sharply degraded on Yale and ORL compared with the corresponding results in Table 2. This is due to the fact that the unseen face data has the large variation compared to the seen data. On the other hand, the clustering accuracies of ESEC are comparable to the in-sample testing results, which validates that ESEC has better generalization performance. ESEC achieves 6 best clustering results among all ten testing results and has comparable results on the rest of the datasets when compared to KSEC. Consequently, the proposed ESEC algorithm provides a new way to cope with the out-of-sample data in clustering tasks.Table 4
Performance comparison of different algorithms for the out-of-sample clustering on ten datasets.
Dataset
Nyström SC
KM
SEC
KSEC
ESEC
Iris
73.6 ± 1.8
75.6 ± 1.9
63.0 ± 1.9
77.1 ± 2.7
79.8 ± 2.1
Glass
49.7 ± 0.9
57.4 ± 1.2
58.6 ± 1.6
58.9 ± 2.4
63.1 ± 2.5
Wine
45.2 ± 0.9
54.6 ± 2.1
49.7 ± 1.9
61.2 ± 2.3
63.7 ± 1.9
WPBC
52.2 ± 2.8
64.7 ± 1.5
73.5 ± 1.5
74.3 ± 1.6
76.2 ± 1.4
SpectfHeart
51.4 ± 1.9
66.8 ± 2.9
53.5 ± 1.7
72.2 ± 2.3
70.8 ± 2.6
USPS
48.3 ± 4.5
56.0 ± 2.2
61.5 ± 2.4
65.1 ± 1.6
62.3 ± 2.8
Yale
20.7 ± 2.3
23.0 ± 1.6
35.9 ± 1.7
42.5 ± 1.6
45.8 ± 1.9
COIL20
63.9 ± 2.4
61.6 ± 3.3
68.9 ± 2.5
72.4 ± 2.7
70.2 ± 3.1
Isolet
34.8 ± 2.7
39.2 ± 1.2
45.3 ± 2.9
66.0 ± 1.8
68.4 ± 1.5
ORL
43.5 ± 2.1
47.6 ± 1.8
55.2 ± 1.5
60.7 ± 1.9
58.7 ± 1.7


## 5. Conclusion

In this paper, we propose a general spectral embedded clustering framework based on the objective function of SC, from which SEC, KSEC, and ESEC can all be derived by using different embedding functions. By virtue of ELM, the fast spectral nonlinearly embedded clustering algorithm (ESEC) is proposed, which can naturally solve the out-of-sample extension problem for the clustering tasks. Experimental results on benchmark datasets validate the effectiveness and efficiency of the proposed ESEC method for both in-sample and out-of-sample clustering. In the future, we intend to develop a new semisupervised clustering framework by incorporating pair constraints into the present framework and propose some semisupervised clustering algorithms based on spectral nonlinearly embedded clustering models.



---

*Source: 9264561-2016-06-27.xml*