4. 0 is an eigenvalue of L
rw
with the constant one vector
1
as eigenvector. 0 is an eigenvalue of
L
sym
with eigenvector D
1/2
1
.
5. L
sym
and L
rw
are positive semi-definite and have n non-negative real-valued eigenvalues 0 =
λ
1
≤ . . . ≤ λ
n
.
Proof. Part (1) can be proved similarly to Part (1) of Proposition 1.
Part (2) can be seen immediately by multiplying the eigenvalue equation L
sym
w = λw with D
−1/2
from the left and substituting u = D
−1/2
w.
Part (3) follows directly by multiplying the eigenvalue equation L
rw
u = λu with D from the left.
Part (4): The first statement is obvious as L
rw
1
= 0, the second statement follows from (2).
Part (5): The statement about L
sym
follows from (1), and then the statement about L
rw
follows from
(2). 2
As it is the case for the unnormalized graph Laplacian, the multiplicity of the eigenvalue 0 of the
normalized graph Laplacian is related to the numb er of connected components:
Proposition 4 (Number of connected components and spectra of L
sym
and L
rw
) Let G be
an undirected graph with non-negative weights. Then the multiplicity k of the eigenvalue 0 of both L
rw
and L
sym
equals the number of connect ed components A
1
, . . . , A
k
in the graph. For L
rw
, the eigenspace
of 0 is spanned by the indicator vectors
1
A
i
of those components. For L
sym
, the eigenspace of 0 is
spanned by the vectors D
1/2
1
A
i
.
Proof. The proof is analogous to the one of Proposition 2, using Proposition 3. 2
4 Spectral C lust eri ng Algorithms
Now we would like to state the most common spectral clustering algorithms. For references and the
history of spectral clustering we refer to Section 9. We assume that our data consists of n “points”
x
1
, . . . , x
n
which can be arbitrary objects. We measure their pairwise similarities s
ij
= s(x
i
, x
j
)
by some similarity function which is symmetric and non-negative, and we denote the corresponding
similarity matrix by S = (s
ij
)
i,j=1...n
.
Unnormalized spectral clustering
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 eigenvectors u
1
, . . . , u
k
of L.
• 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
}.
There are two different versions of normalized spectral clustering, depending which of the normalized
6
剩余31页未读，继续阅读
维纳斯的双臂
- 粉丝: 0
- 资源: 5
我的内容管理
展开
最新资源
- Vue实现iOS原生Picker组件：详细解析与实现思路
- Arduino蓝牙小车：参数调试与功能控制
- 百度Java面试精华：200页精选资源涵盖核心知识点
- Swift使用CoreData填坑指南：CoreData在Swift 3.0的变化
- 微距离无线充电器创新设计及其实验探索
- MTK Android平台开发全攻略：44步详解流程
- RecyclerView全面解析：替代ListView的新选择
- Android开发：自动适配中英文键盘解决方案
- Android调用WebService接口教程
- Android开发：BitmapUtil图片处理全解析与实例
- Android多线程断点续传实现详解
- PCA算法在人脸识别会议签到系统中的应用
- EventBus 3.0：Android事件总线详解与实战应用
- Android FileUtil：全面解析文件操作实用技巧与实例
- RecyclerView添加头部和尾部实战教程
- Android实现微博滑动固定顶部栏实战与优化
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
