查看: 3100|回复: 0

[其他资源] 【数据聚类】第八章第二节：谱聚类算法之切图聚类、算法流程及其实现

[复制链接]

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2022-9-12 18:41 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

【数据聚类】第八章第二节：谱聚类算法之切图聚类、算法流程及其实现

本文部分内容源自刘建平博客，在此基础上进行总结拓展

原文链接
文章目录
一：谱聚类与图划分
（1）比例割
（2）规范割（常用）
二：谱聚类算法流程
三：Python实现
四：谱聚类算法优缺点
（1）优点
（2）缺点
一：谱聚类与图划分
无向图切图：谱聚类算法根据数据点之间的相似度将数据点划分到不同簇中，因此将数据点映射到无向图之后，可以转化为图划分的问题。对于无向图G GG，切图的目标是将图G ( V , E ) G(V,E)G(V,E)切分成互相无连接k kk个子图，其中

每个子图点的集合为{ A 1 , A 2 , . . . , A k } \{A_{1},A_{2},...,A_{k}\}{A
1

,A
2

,...,A
k

}，且满足A i ∩ A j = ∅ A_{i}\cap A_{j}=\emptyA
i

∩A
j

=∅、A 1 ∪ A 2 ∪ . . . ∪ A k = V A_{1}\cup A_{2}\cup ... \cup A_{k}=VA
1

∪A
2

∪...∪A
k

=V
对于任意两个子图点的集合A AA、B BB，我们定义A AA和B BB之间的切图权重为W ( A , B ) = ∑ i ∈ A , j ∈ B w i j W(A,B)=\sum\limits_{i\in A,j \in B} w_{ij}W(A,B)=
i∈A,j∈B
∑

w
ij

对于k kk个子图点的集合{ A 1 , A 2 , . . . , A k } \{A_{1},A_{2},...,A_{k}\}{A
1

,A
2

,...,A
k

}，定义切图c u t ( A 1 , A 2 , . . . , A k ) = 1 2 ∑ i = 1 k W ( A i , A ˉ i ) cut(A_{1},A_{2},...,A_{k})=\frac{1}{2}\sum\limits_{i=1}^{k}W(A_{i},\bar A_{i})cut(A
1

,A
2

,...,A
k

)=
2
1

i=1
∑
k

W(A
i

,
A
ˉ

i

) （其中A ˉ i \bar A_{i}
A
ˉ

i

为A i A_{i}A
i

的补集）
可以看出，c u t cutcut描述了子图之间的相似性，c u t cutcut越小那么子图的差异性就越大。但是c u t ( A 1 , A 2 , . . . , A k ) = 1 2 ∑ i = 1 k W ( A i , A ˉ i ) cut(A_{1},A_{2},...,A_{k})=\frac{1}{2}\sum\limits_{i=1}^{k}W(A_{i},\bar A_{i})cut(A
1

,A
2

,...,A
k

)=
2
1

i=1
∑
k

W(A
i

,
A
ˉ

i

)在划分子图时并没有考虑每个子图中节点的个数。所以在某些情况下，最小化c u t ( A 1 , A 2 , . . . , A k ) cut(A_{1},A_{2},...,A_{k})cut(A
1

,A
2

,...,A
k

)可能会把一个数据点或是很少数据点看做一个子图，导致子图划分结果不平衡

例如下图，选择一个权重最小的边缘的点，比如C CC和H HH之间进行c u t cutcut，这样可以最小化c u t ( A 1 , A 2 , . . . , A k ) cut(A_{1},A_{2},...,A_{k})cut(A
1

,A
2

,...,A
k

)但是却不是最优的切图

为了解决这个问题，会引入一些正则化方法。最常用的两种方法为比例割和规范割

比例割：R a t i o c u t ( A 1 , A 2 , . . . , A k ) = 1 2 ∑ i = 1 k W ( A i , A ˉ i ) ∣ A i ∣ Ratiocut(A_{1},A_{2},...,A_{k})=\frac{1}{2}\sum\limits_{i=1}^{k}\frac{W(A_{i},\bar A_{i})}{|A_{i}|}Ratiocut(A
1

,A
2

,...,A
k

)=
2
1

i=1
∑
k

∣A
i

∣
W(A
i

,
A
ˉ

i

)

规范割：N C u t ( A 1 , A 2 , . . . , A k ) = 1 2 ∑ i = 1 k W ( A i , A ˉ i ) v o l ( A i ) NCut(A_{1},A_{2},...,A_{k})=\frac{1}{2}\sum\limits_{i=1}^{k}\frac{W(A_{i},\bar A_{i})}{vol(A _{i})}NCut(A
1

,A
2

,...,A
k

)=
2
1

i=1
∑
k

vol(A
i

)
W(A
i

,
A
ˉ

i

)

（1）比例割
引入指示向量（点击可查看指示向量定义）h j ∈ { h 1 , h 2 , . . . , h k } h_{j}\in\{h_{1},h_{2},...,h_{k}\}h
j

∈{h
1

,h
2

,...,h
k

}，j = 1 , 2 , . . . , k j=1,2,...,kj=1,2,...,k。对于任意一个向量h j h_{j}h
j

，它是一个n nn维向量（n nn表示样本数），定义h i j h_{ij}h
ij

如下

h i j = { 0 ， v i ∉ A j ∣ A j ∣ ， v i ∈ A j h_{ij}=
{0，vi∉Aj|Aj|−−−√，vi∈Aj
{0，vi∉Aj|Aj|，vi∈Aj
h
ij

={
0，v
i

∈
/
A
j

∣A
j

∣

，v
i

∈A
j

于是，对于h i T L h i h_{i}^{T}Lh_{i}h
i
T

Lh
i

，根据拉普拉斯矩阵性质可知

对于任意向量f = ( f 1 , . . . , f n ) T ∈ R n f=(f_{1},...,f_{n})^{T} \in R^{n}f=(f
1

,...,f
n

)
T
∈R
n
，有f T L f = 1 2 ∑ i , j = 1 n w i j ( f i − f j ) 2 f^{T}Lf=\frac{1}{2}\sum\limits_{i,j=1}^{n}w_{ij}(f_{i}-f_{j})^{2}f
T
Lf=
2
1

i,j=1
∑
n

w
ij

(f
i

−f
j

)
2

h i T L h i = 1 2 ∑ m = 1 ∑ n = 1 w m n ( h i m − h i n ) 2 = c u t ( A i , A ˉ i ) ∣ A i ∣ h_{i}^{T}Lh_{i}=\frac{1}{2}\sum\limits_{m=1}\sum\limits_{n=1}w_{mn}(h_{im}-h_{in})^{2}=\frac{cut(A_{i},\bar A_{i})}{|A_{i}|}
h
i
T

Lh
i

=
2
1

m=1
∑

n=1
∑

w
mn

(h
im

−h
in

)
2
=
∣A
i

∣
cut(A
i

,
A
ˉ

i

)

严格证明过程请看刘建平博客：链接
可以看到，对于某一个子图i ii，R a t i o n C u t RationCutRationCut就对应于h i T L h i h_{i}^{T}Lh_{i}h
i
T

Lh
i

，那么对于k kk个子图

R a t i o C u t ( A 1 , A 2 , . . . , A k ) = ∑ i = 1 k h i T L h i = ∑ i = 1 k ( H T L H ) i i = t r ( H T L H ) RatioCut(A_{1},A_{2},...,A_{k})=\sum\limits_{i=1}^{k}h_{i}^{T}Lh_{i}=\sum\limits_{i=1}^{k}(H^{T}LH)_{ii}=tr(H^{T}LH)
RatioCut(A
1

,A
2

,...,A
k

)=
i=1
∑
k

h
i
T

Lh
i

=
i=1
∑
k

(H
T
LH)
ii

=tr(H
T
LH)

因此，R a t i o n C u t RationCutRationCut切图本质就是最小化t r ( H T L H ) tr(H^{T}LH)tr(H
T
LH)。又因为H T H = I H^{T}H=IH
T
H=I（单位矩阵），则切图优化目标为

a r g m i n ⏟ H t r ( H T L H ) s . t . H T H = I \underbrace{argmin}_{H} tr(H^{T}LH) s.t.H^{T}H=I
H
argmin

tr(H
T
LH)s.t.H
T
H=I

对于优化目标t r ( H t L H ) tr(H^{t}LH)tr(H
t
LH)中的每一个优化子目标h i T L h i h_{i}^{T}Lh_{i}h
i
T

Lh
i

，其中的h hh是单位正交基，L LL为对称矩阵，所以此时h i T L h i h_{i}^{T}Lh_{i}h
i
T

Lh
i

的最大值即为L LL的最大特征值、最小值即为L LL的最小特征值。而在谱聚类中，我们的目标就是要找到目标的最小特征值，得到对应特征值向量，此时切图效果最佳。所以对于h i T L h i h_{i}^{T}Lh_{i}h
i
T

Lh
i

，目标就是找到L LL的最小特征值，而对于t r ( H t L H ) = ∑ i = 1 k h i T L h i tr(H^{t}LH)=\sum\limits_{i=1}^{k}h_{i}^{T}Lh_{i}tr(H
t
LH)=
i=1
∑
k

h
i
T

Lh
i

，则目标就是要找到k kk个最小的特征值

因此，通过找到L LL的最小的k kk个特征值，可以得到对应的k kk个特征向量，这k kk特特征向量组成一个n nn×k kk维矩阵，也即H HH。一般需要对矩阵H HH按行做标准化，如下

一般来说，k kk远小于n nn，也就说进行了降维
h i j ∗ = h i j ( ∑ t = 1 k h i t 2 ) 1 2 h_{ij}^{*}=\frac{h_{ij}}{(\sum\limits_{t=1}^{k}h_{it}^2)^{\frac{1}{2}}}
h
ij
∗

=
(
t=1
∑
k

h
it
2

)
2
1

h
ij

这里需要注意，降维后导致得到的指示向量h hh对应的H HH现在并不能完全指示各样本的归属，因此一般在得到n × k n×kn×k维的矩阵H HH后还需要对每一行进行一次传统的聚类，比如使用K-Means聚类

（2）规范割（常用）
规范割和比例割类似，只是把比例割的分母∣ A i ∣ |A_{i}|∣A
i

∣换成了v o l ( A i ) vol(A_{i})vol(A
i

)，定义指示向量h i j h_{ij}h
ij

如下

h i j = { 0 ， v i ∉ A j v o l ( A i ) ， v i ∈ A j h_{ij}=
{0，vi∉Ajvol(Ai)−−−−−−√，vi∈Aj
{0，vi∉Ajvol(Ai)，vi∈Aj
h
ij

={
0，v
i

∈
/
A
j

vol(A
i

)

，v
i

∈A
j

于是，对于h i T L h i h_{i}^{T}Lh_{i}h
i
T

Lh
i

，根据拉普拉斯矩阵性质可知

对于任意向量f = ( f 1 , . . . , f n ) T ∈ R n f=(f_{1},...,f_{n})^{T} \in R^{n}f=(f
1

,...,f
n

)
T
∈R
n
，有f T L f = 1 2 ∑ i , j = 1 n w i j ( f i − f j ) 2 f^{T}Lf=\frac{1}{2}\sum\limits_{i,j=1}^{n}w_{ij}(f_{i}-f_{j})^{2}f
T
Lf=
2
1

i,j=1
∑
n

w
ij

(f
i

−f
j

)
2

h i T L h i = 1 2 ∑ m = 1 ∑ n = 1 w m n ( h i m − h i n ) 2 = c u t ( A i , A ˉ i ) v o l ( A i ) h_{i}^{T}Lh_{i}=\frac{1}{2}\sum\limits_{m=1}\sum\limits_{n=1}w_{mn}(h_{im}-h_{in})^{2}=\frac{cut(A_{i},\bar A_{i})}{vol(A_{i})}
h
i
T

Lh
i

=
2
1

m=1
∑

n=1
∑

w
mn

(h
im

−h
in

)
2
=
vol(A
i

)
cut(A
i

,
A
ˉ

i

)

严格证明过程请看刘建平博客：链接
可以看到，对于某一个子图i ii，R a t i o n C u t RationCutRationCut就对应于h i T L h i h_{i}^{T}Lh_{i}h
i
T

Lh
i

，那么对于k kk个子图

N C u t ( A 1 , A 2 , . . . , A k ) = ∑ i = 1 k h i T L h i = ∑ i = 1 k ( H T L H ) i i = t r ( H T L H ) NCut(A_{1},A_{2},...,A_{k})=\sum\limits_{i=1}^{k}h_{i}^{T}Lh_{i}=\sum\limits_{i=1}^{k}(H^{T}LH)_{ii}=tr(H^{T}LH)
NCut(A
1

,A
2

,...,A
k

)=
i=1
∑
k

h
i
T

Lh
i

=
i=1
∑
k

(H
T
LH)
ii

=tr(H
T
LH)

但此时H T H ≠ I H^{T}H \not=IH
T
H

=I，而是H T D H = I H^{T}DH =IH
T
DH=I

这是因为h i T D h i = ∑ j = 1 n h i j 2 d j = 1 v o l ( A i ) ∑ j ∈ A i d j = 1 v o l ( A i ) v o l ( A i ) = 1 h_{i}^{T}Dh_{i}=\sum\limits_{j=1}^{n}h_{ij}^{2}d_{j}=\frac{1}{vol(A_{i})}\sum\limits_{j\in A_{i}}d_{j}=\frac{1}{vol(A_{i})}vol(A_{i})=1h
i
T

Dh
i

=
j=1
∑
n

h
ij
2

d
j

=
vol(A
i

)
1

j∈A
i

∑

d
j

=
vol(A
i

)
1

vol(A
i

)=1
因此，此时切图优化目标为

a r g m i n ⏟ H t r ( H T L H ) s . t . H T D H = I \underbrace{argmin}_{H} tr(H^{T}LH) s.t.H^{T}DH=I
H
argmin

tr(H
T
LH)s.t.H
T
DH=I

但是现在矩阵H HH中的指示向量h hh并不是标准正交基，所以需要对H HH做一定转换。令H = D − 1 2 F H=D^{-\frac{1}{2}}FH=D
−
2
1

F，则H T L H = F T D − 1 2 L D − 1 2 F H^{T}LH=F^{T}D^{-\frac{1}{2}}LD^{-\frac{1}{2}}FH
T
LH=F
T
D
−
2
1

LD
−
2
1

F、H T D H = F T F = I H^{T}DH=F^{T}F=IH
T
DH=F
T
F=I，于是优化目标变更为
a r g m i n ⏟ F t r ( F T D − 1 2 L D − 1 2 F ) s . t . F T F = I \underbrace{argmin}_{F} tr(F^{T}D^{-\frac{1}{2}}LD^{-\frac{1}{2}}F) s.t.F^{T}F=I
F
argmin

tr(F
T
D
−
2
1

LD
−
2
1

F)s.t.F
T
F=I

现在，和比例割一样，通过找到D − 1 2 L D − 1 2 D^{-\frac{1}{2}}LD^{-\frac{1}{2}}D
−
2
1

LD
−
2
1

（就是之前的L LL）的最小的k kk个特征值，可以得到对应的k kk个特征向量，这k kk特征向量组成一个n nn×k kk维矩阵，也即F FF，最后对F FF进行传统聚类

一般来说，D − 1 2 L D − 1 2 D^{-\frac{1}{2}}LD^{-\frac{1}{2}}D
−
2
1

LD
−
2
1

相当于对L LL做了一次标准化，也即L i j d i ∗ d j \frac{L_{ij}}{\sqrt{d_{i}*d_{j}}}
d
i

∗d
j

L
ij

二：谱聚类算法流程
给定数据集D = { x 1 , x 2 , . . . , x n } D=\{x_{1}, x_{2}, ... , x_{n}\}D={x
1

,x
2

,...,x
n

}

根据输入的相似矩阵生成方式（一般为高斯核函数）构建相似矩阵S SS（AffinityMatrix）
根据相似矩阵S SS构建邻接矩阵W WW，再构建度矩阵D DD
计算拉普拉斯矩阵L = D − W L=D-WL=D−W
得到标准化后的拉普拉斯矩阵D − 1 2 L D − 1 2 D^{-\frac{1}{2}}LD^{-\frac{1}{2}}D
−
2
1

LD
−
2
1

计算D − 1 2 L D − 1 2 D^{-\frac{1}{2}}LD^{-\frac{1}{2}}D
−
2
1

LD
−
2
1

最小的k kk个特征值对应的特征向量f ff
将特征向量f ff组成矩阵并按行标准化，最终组成n nn×k kk维的特征矩阵F FF
F FF中每一行作为一个k kk维的样本，共n nn个样本，采用某种聚类方法进行聚类，假设聚类维数为k 、 k^{、}k
、

得到簇划分C( c 1 , c 2 , . . . , c k 、 ) (c_{1}, c_{2}, ... , c_{k^{、}})(c
1

,c
2

,...,c
k
、

)
三：Python实现
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
from sklearn.cluster import KMeans
from sklearn.metrics.pairwise import rbf_kernel
from sklearn.datasets import make_blobs
from sklearn.preprocessing import normalize

def get_affinity_matrix(data_set):
#  利用高斯核函数计算相似矩阵(全连接)
rbf = rbf_kernel(data_set)
for i in range(len(rbf)):
      rbf[i, i] = 0
return rbf

def distance(x1, x2):
"""
获得两个样本点之间的距离
:param x1: 样本点1
:param x2: 样本点2
:return:
"""
dist = np.sqrt(np.power(x1-x2,2).sum())
return dist

def get_dist_matrix(data):
"""
获取距离矩阵
:param data: 样本集合
:return: 距离矩阵
"""
n = len(data)  #样本总数
dist_matrix = np.zeros((n, n)) # 初始化邻接矩阵为n×n的全0矩阵
for i in range(n):
      for j in range(i+1, n):
         dist_matrix[j] = dist_matrix[j] = distance(data, data[j])- n  e. {# Z5 T- q4 g
return dist_matrix
3 g5 ~1 c9 V( b: I
3 b8 m% _' M  p  _def get_W(data, k):9 }. g2 i: M  U4 Q! k  {+ B- o
# 获取邻接矩阵（K邻近法）9 B! s+ Y* d9 y. [1 O. S* e
n = len(data)
' G* F9 C( N4 l0 ^ dist_matrix = get_dist_matrix(data)5 _# q7 l. d) @8 W  l6 d
W = np.zeros((n, n))
: D9 \4 t# T  f: q6 e for idx, item in enumerate(dist_matrix):) T8 m! |+ A" C# p( L3 g) T
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表
+ x! r  l# V' @2 |& ]       W[idx][idx_array[1:k+1]] = 1
0 ]; u, W. |9 K transpW =np.transpose(W)
5 \) X& ]$ {, E' l1 D% M return (W+transpW)/2
2 M( m- @" b+ q# g+ g! t! W6 X/ h. w. i0 m4 t0 }5 O
def spectral_clustering(data_set, k):
4 P3 _. ]# ~3 d # 利用相似矩阵S得到邻接矩阵W
; S# a2 n- e; a6 G) C/ J5 A4 ]6 V) x W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
! C' \: ?+ P8 ~( f8 K #  W = get_W(data_set, k)  # K邻近法5 M4 V# B8 Y0 f& Y
% R% d' N) }7 o. R$ Q  Y$ i" [  W; |- {
# 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）
$ e# D% R) h( H- X& O D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5)): ~- T1 g5 x' {- O9 _9 f# Z

! H$ p7 d( \- g # 计算拉普拉斯矩阵L=D-W7 E% t/ E. _% L, V& V
# 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
) z$ b% K% s5 C1 U% a L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)
" s. I) |+ n# e, E! O2 }$ N
) m6 f1 w" X: P; l/ U # 得到特征值和特征向量
, w# x" q# w* R eigvals, eigvecs = np.linalg.eig(L)3 E; j4 F3 C- z+ T+ C* Y
1 i0 F1 w7 t: l$ @9 |7 Y7 ^
# 找到前k个最小的特征值（索引）4 V7 ^" h! U& _2 c% r; A
k_smallest_eigvals_index = np.argsort(eigvals)[:k]
7 m4 j8 \7 B; N6 Z# U
8 j. O$ t) F+ c, z& R% J7 u% C # 取出这k小特征值对应的特征向量，并正则化
/ J' {- s9 _% J8 l k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])
2 Q/ V  h5 _2 [; |! O0 j. Y1 _7 d( s0 G1 Q. v! U4 O
# 使用K_Means聚类1 ]0 L2 F8 Y# r5 f5 w
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)
& v5 u6 A) O9 v  V, @' j2 k* o% \0 X1 o
+ P3 ^) G9 S2 c% E; N
raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)6 f5 A" ?( P/ `
raw_data.columns = ['X', 'Y']  z6 L5 t1 `9 e+ t/ H
x_axis = 'X'
& h/ x6 F: Z  D! {( Ty_axis = 'Y'! y  N' T+ Z" p, a! g" y
7 }( r1 v; M8 X2 I/ l! Z5 J
examples_num = raw_data.shape[0]
& F7 O$ u& j6 r* m! r# X7 i- N( p0 Wtrain_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)
/ y- {  q* E$ U! {0 H  }) m6 j" C4 \( J; V" A, G

( A: J* T1 H: N, y' ^1 P- R% {. jmin_vals = train_data.min(0)
8 W! Y( ~+ z) l% i8 f7 @3 amax_vals = train_data.max(0)* G2 y! H- o- w# u1 j2 n
ranges = max_vals - min_vals" o' c7 p* `0 G: N
normal_data = np.zeros(np.shape(train_data))4 q0 @" w5 [  t4 E2 b
nums = train_data.shape[0]* W/ i# {, B8 B
normal_data = train_data - np.tile(min_vals, (nums, 1))3 S- p7 ]! \1 T" Y$ ]
normal_data = normal_data / np.tile(ranges, (nums, 1))0 S7 o6 c. E7 l* u9 a  t

+ W$ f0 l+ }0 Z( [labels = spectral_clustering(normal_data, 2)$ {7 C9 l1 _4 j) G0 l/ y9 _4 W

# \! y8 d) O7 H1 r6 g# 原数据
9 h0 t& w. C& H" l: G/ O1 f* ]- {fig, (ax0, ax1) = plt.subplots(ncols=2)
4 g- m5 K" @/ r  K" Y; v4 Bax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')0 }- f0 Q, v& k
ax0.set_title('raw data')' P, I5 M- f+ e1 [, @4 e: w
# 谱聚类结果
+ ~. }; _. X8 hax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels). |( |4 h: p; j+ ^, l
ax1.set_title('Spectral Clustering')
' k8 V$ R( |- x9 v) d6 s3 n3 @
1 c2 b$ \: D" P6 Y0 M. ?plt.show()
: H' o/ U# y' X- n& B$ M/ P9 T0 {$ h- Z$ X( Z" Z
1+ s: i. A' M; d( g! c4 O
2
" |$ Y  x) ?: w0 U3' g* ]4 \) I& A- c1 H9 x& ?7 g" u
4
$ D& Z8 e( D/ C$ J+ R" c5; j/ O; d, N5 _7 ^6 R
6
% l& X' G; Z& Y8 p7
* a* U+ V' K, F! Q$ z+ ?/ r8. E+ h/ d8 L. ]
9
- W3 {7 G! D- u. B1 |3 p10( X/ i  q, \/ Q' v: ^7 O2 B. X
11
* E3 h4 f3 V+ }% D6 {' P9 {0 N12
. o' r: u7 c0 p. E" Y  _1 F8 B3 @13
: {) @, Q; P# Q# [  H( C4 S& b144 V( x2 A+ ^4 N8 X
15
, r+ x! `6 e  `5 ]2 w3 \& P162 n. g; N* s# }# |
171 u- x6 j8 p+ t7 K* ], |
18- o* U4 U1 ^1 e) U
19
- ?4 S, @6 s2 e5 \! \0 ^20. o8 V9 ^( J2 d
21/ h: z5 S5 a* M, S' Z
22' |  I* \" \# F1 C
23& c; J  b$ s9 c5 @  Q
24, E# L  U/ r3 X8 C  p
25
2 C5 c  W2 b, F7 b8 O2 V6 ~26
, w* P. G6 F$ Z6 S4 c27  U; u" x! V" ^8 ~7 J/ C( |
281 J5 f, m* J8 _
29
: J' m8 l/ s5 F8 u$ T8 T30
# i& M/ x' M; s. l9 Q( C31. E' o0 K0 F+ s5 M  f
326 l) V! q- O, }) k9 d
33
2 S% Q* i- R( N0 \34
5 Y2 o. |) w- k2 i2 i6 w, o356 L/ y/ p7 ]3 W0 }( }& u
36* e3 W, F3 ]0 o' _7 J% U) A( n$ }% _
37
, W, S* F0 z- V2 d, y38$ A/ O8 p' ?) ^8 T
39
8 g+ i( {5 c" }+ c+ b$ {. p40
3 M* q2 U8 E' u: D413 Z# d5 }. h4 @( @. C
42
2 U2 {, c& X1 _% U+ N43
$ {. v7 l' Y  Q5 J- Z) h44
! l. k+ X' G4 ^5 e: l0 [3 p8 O# P& X454 l4 _, ~0 k  W% b1 ?) h/ r2 @
46
) G. z/ D3 N8 Y; b47
0 _; m. w+ I) X; c! _48! q, R2 f3 @% D! _; g1 Z; ^) t0 {
49
$ {, i3 K' I5 K! |; _" o50& p4 k# F; v8 h2 f
51  s- }; q1 o  T$ \- Q
52
& [8 s+ @8 B' P0 x0 o) L" a/ |53- r! @/ n( U/ f- b
54
' }) V/ y, Y/ o/ }1 L8 [6 O8 `( M55
* h1 G4 W0 k% O: B56# [" M7 X3 F3 a% U
57
- j, m$ }* P5 H! Q1 |4 Y58
, Y' o5 h: W7 O+ o: p598 k1 r" q1 |% d- K7 a  u
608 x5 \7 N3 T+ q9 W  J+ C
61. a  }. \8 U+ A" `$ W6 y2 k+ X
62$ H, A1 }2 I8 w% Q+ q4 }* T5 e$ K
63* O. b) u  B( |) A0 V' r
64
/ A8 t; T# s0 A9 ^# V& \  I4 ?! w65
; y6 u* b- e) K. b9 ?6 v66# L% a' t) e: J: H( N9 ?
67! P2 d( C4 y/ ^% N4 I  i, v
68
* D+ s8 K7 }" B$ u' U69
+ p% F( A- k; z# b) ~5 i70$ {. ^1 F( }, l4 J. m. {  d1 Z
717 b' r5 D" M* X7 d
72
, D, s) Q5 y' V9 G/ o: h732 u# e$ ^$ l! l& q8 o. i
742 M' G/ E5 v1 E" q* `$ T* k- b) a
75, c6 W! G( p$ c4 R1 e8 E, z
767 \0 b  a3 o+ P( X
777 a0 d+ p3 Q- y% M: A" ^
78
0 Z4 t$ Z3 p5 U+ ^* p+ r79
( ?% q6 e4 Z7 q- M* [; f80$ k, q! q, |7 |& q" B& I  a
814 R4 Y- Y1 l+ y" S
82
& \7 k  u/ U4 H+ N; p; S83
6 D; w- t7 J1 [- K$ m# @2 |84" l4 L7 X# h! J: `  R9 c
85
: y# F- W  g* `% Z3 {+ g1 E$ @865 p# @- a; {% Z7 N- n! ?
87
0 K5 k0 V  k7 O4 P6 S' S' W88
$ r# G" D3 ^4 w6 H9 ~# z89
2 ]( \5 \+ |1 @6 e. q90
" o9 i4 j5 H  s# b3 x' j91  p. x; M8 v- ~7 t" C$ r4 ^
92
: |6 T3 d8 j! n$ B0 q# ?0 s93( M- C9 v$ H" p+ X
946 q: U4 q. M, b8 {8 L1 K0 S
95
' }  B  \+ x* d96  x$ B- Z7 Y# e8 ^' h+ T. Z1 M: I
97
' o6 |% [8 z6 }& y98
; }1 W3 Z2 @: _7 |- P# c5 R1 r5 ]! R99
# a) ?0 T1 [& @100
8 n! Q' f( T& K5 K% p) ?- \101
7 m. n) Q8 u! m  ^102  X7 J5 H7 k! a4 z: m
103- ]/ d  r, H' v* K
（高斯核函数）5 C2 D7 \% d8 o* Y
' _$ h& T( k( y. i; s8 H
2 q/ ~5 e7 Y0 h
（K邻近法）1 o3 \6 _: H) j+ s% [1 o4 g5 Y

! @2 d; p0 c5 p# A# C) ~- R* U' {
% `) A. Y% |  g0 F3 F6 e. a四：谱聚类算法优缺点
, I. g: U' R/ S! Z: {6 C（1）优点: d/ n- Y  Z% `- @, K. A9 [
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效
( @/ I& _9 [: p. A  S使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法
( w$ ?% ]) R: _0 B谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解: e& @8 t6 q9 q1 j. n6 Z
（2）缺点1 m( p  S) |" y; P$ J/ d
如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好) m9 O' Y! E$ [; Z
聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同
: l7 ]- e+ G7 {, [5 c, G, a0 [————————————————
& G8 Z" d& k- Z* X2 [4 r" e8 f版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
' N7 Z) Z. }. o* d+ K9 z* l; ~原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494/ ?4 A( ]' E- }# J5 @3 D

- f: o4 \, ~) i, M/ [9 q0 ~" S- S  c2 i! Q! L