![](https://csdnimg.cn/release/download_crawler_static/13657538/bg7.jpg)
graph Laplacians is used. We name both algorithms after two popular papers, for more references and
history please see Sec tion 9.
Normalized spectral clustering according to Shi and Malik (2000)
Input: Similarity matrix S ∈
R
n×n
, number k of clusters to construct.
• Construct a similarity graph by one of the ways described in Section 2. Let W
be its weighted adjacency matrix.
• Compute the unnormalized Laplacian L.
• Compute the first k generalized eigenvectors u
1
, . . . , u
k
of the generalized eigenprob-
lem Lu = λDu.
• Let U ∈
R
n×k
be the matrix containing the vectors u
1
, . . . , u
k
as columns.
• For i = 1, . . . , n, let y
i
∈
R
k
be the vector corresponding to the i-th row of U.
• Cluster the points (y
i
)
i=1,...,n
in
R
k
with the k-means algorithm into clusters
C
1
, . . . , C
k
.
Output: Clusters A
1
, . . . , A
k
with A
i
= {j| y
j
∈ C
i
}.
Note that this algorithm uses the generalized eigenvectors of L, which according to Proposition 3
correspond to the eigenvectors of the matrix L
rw
. So in fact, the algorithm works with eigenvectors of
the normalized Laplacian L
rw
, and hence is called normalized spectral clustering. The next algorithm
also uses a normalized Laplacian, but this time the matrix L
sym
instead of L
rw
. As we will see, this
algorithm needs to introduce an additional row normalization step which is not needed in the other
algorithms. The reasons will become clear in Section 7.
Normalized spectral clustering according to Ng, Jordan, and Weiss (2002)
Input: Similarity matrix S ∈
R
n×n
, number k of clusters to construct.
• Construct a similarity graph by one of the ways described in Section 2. Let W
be its weighted adjacency matrix.
• Compute the normalized Laplacian L
sym
.
• Compute the first k eigenvectors u
1
, . . . , u
k
of L
sym
.
• Let U ∈
R
n×k
be the matrix containing the vectors u
1
, . . . , u
k
as columns.
• Form the matrix T ∈
R
n×k
from U by normalizing the rows to norm 1,
that is set t
ij
= u
ij
/(
P
k
u
2
ik
)
1/2
.
• For i = 1, . . . , n, let y
i
∈
R
k
be the vector corresponding to the i-th row of T .
• Cluster the points (y
i
)
i=1,...,n
with the k-means algorithm into clusters C
1
, . . . , C
k
.
Output: Clusters A
1
, . . . , A
k
with A
i
= {j| y
j
∈ C
i
}.
All three algorithms stated above look rather similar, apart from the fact that they use three different
graph Laplacians. In all three algorithms, the main trick is to change the representation of the abstract
data points x
i
to points y
i
∈
R
k
. It is due to the properties of the graph Laplacians that this change of
representation is useful. We will see in the next sections that this change of representation enhances
the cluster-properties in the data, so that clusters can be trivially detected in the new representation.
In particular, the simple k-means clustering algorithm has no difficulties to detect the clusters in this
new representation. Readers not familiar with k-means can read up on this algorithm in numerous
7