Databases Reference
In-Depth Information
W
;
A
V
= [
v
1
,
v
2
,
v
3
]
U
= [
u
1
,
u
2
,
u
3
]
0.5
0
0.5
0
−1
−
0.5
−
0.5
0
10
20
30
40
50
60
0
10
20
30
40
50
60
1
0.5
0
1
0.5
0
0
10
20
30
40
50
60
0
10
20
30
40
50
60
0.4
0.2
−0.2
1
0.5
−0.5
0
0
0
10
20
30
40
50
60
0
10
20
30
40
50
60
Figure11.11
The new dimensions and the clustering results of the Ng-Jordan-Weiss algorithm.
Source:
Adapted from Slide 9 at
http://videolectures.net/micued08 azran mcl/
.
5.
Assign the original data points to clusters according to how the transformed points
are assigned in the clusters obtained in step 4.
In the Ng-Jordan-Weiss algorithm, the original object
o
i
is assigned to the
j
th
cluster if and only if matrix
Y
's row
i
is assigned to the
j
th cluster as a result of step 4.
In spectral clustering methods, the dimensionality of the new space is set to the
desired number of clusters. This setting expects that each new dimension should be able
to manifest a cluster.
Example11.15
The Ng-Jordan-Weiss algorithm.
Consider the set of points in Figure 11.11. The
data set, the affinity matrix, the three largest eigenvectors, and the normalized vec-
tors are shown. Note that with the three new dimensions (formed by the three largest
eigenvectors), the clusters are easily detected.
Spectral clustering is effective in high-dimensional applications such as image pro-
cessing. Theoretically, it works well when certain conditions apply. Scalability, however,
is a challenge. Computing eigenvectors on a large matrix is costly. Spectral clustering can
be combined with other clustering methods, such as biclustering. Additional informa-
tion on other dimensionality reduction clustering methods, such as kernel PCA, can be
found in the bibliographic notes (Section 11.7).
11.3
ClusteringGraphandNetworkData
Cluster analysis on graph and network data extracts valuable knowledge and informa-
tion. Such data are increasingly popular in many applications. We discuss applications
and challenges of clustering graph and network data in Section 11.3.1. Similarity mea-
sures for this form of clustering are given in Section 11.3.2. You will learn about graph
clustering methods in Section 11.3.3.
In general, the terms
graph
and
network
can be used interchangeably. In the rest of
this section, we mainly use the term
graph
.
