查看: 3120|回复: 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])% b: L1 o8 K& Q$ q  ^  C4 H
return dist_matrix1 k* M1 V  _! l4 W! s: X2 q

" s( W; J) C  q' c6 ^def get_W(data, k):. J) O/ x# S& g
# 获取邻接矩阵（K邻近法）2 Z0 U# v# }9 n) p9 x# t4 I
n = len(data)+ f3 m8 V( w" f
dist_matrix = get_dist_matrix(data)) @# q$ t: C- P5 L7 Z
W = np.zeros((n, n))& R. [- _4 }- y3 p# Q6 T' f$ U
for idx, item in enumerate(dist_matrix):
1 r2 H& b& z% A1 e1 W       idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表  f. q* N" A" p5 T" P# m
      W[idx][idx_array[1:k+1]] = 1
5 u% C9 M7 e$ M5 n! |5 W" w% c/ r transpW =np.transpose(W)
2 S% o7 v  U/ y/ v return (W+transpW)/2
  e5 @0 W5 P: c& ^: e! Y! D- S2 S
def spectral_clustering(data_set, k):
. U9 M; ^" d1 r/ J # 利用相似矩阵S得到邻接矩阵W
& Q+ n0 p& t2 ^' p$ c! [1 ?+ M W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
0 [( I9 U1 ^( @4 |" |/ X+ ` #  W = get_W(data_set, k)  # K邻近法
, A4 n% G. T0 f; r5 t3 c
0 ~, ]- P0 G. P& e/ { # 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）! `4 Y3 g% g6 W9 N' p" h
D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))( r. I- z/ A  e, G

- f( \5 s( p$ O$ j5 P # 计算拉普拉斯矩阵L=D-W
+ L% f5 ~- ]; [4 w! [& i) Q # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
! p5 G. S) F  V) }$ r! f- S' F L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)
( |# ~2 J5 {5 f6 [+ E, d- m- V% a3 J9 P1 O/ w
# 得到特征值和特征向量. _3 X3 c* q2 W! o4 k
eigvals, eigvecs = np.linalg.eig(L)
( H- r$ ^! x2 e: |. |9 ^4 ?  [% E$ M; S3 ]; a
# 找到前k个最小的特征值（索引）
, h# m9 y/ u, z3 J$ {, a k_smallest_eigvals_index = np.argsort(eigvals)[:k]3 r' b+ K5 x0 o& D" G6 E/ M

8 }3 w% {$ {  V( N; @; P; v # 取出这k小特征值对应的特征向量，并正则化
, U8 |3 x1 L+ I' g k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])! U8 K! H& k- j9 {# a/ `
  s# j5 c3 K: ]5 h2 K* T$ l
# 使用K_Means聚类7 `) w9 {* s' d# x* U' Q
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs), C! {: k5 I+ R7 o. Y& h9 L
! v6 K4 T. }; w* w0 o* r* N

2 d2 X" U! S. j" x8 Vraw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)5 t6 N+ R7 H" w. j9 z. g9 ~
raw_data.columns = ['X', 'Y']
( Q6 }3 @1 w# Cx_axis = 'X'
- z) C. O# Y. u! p' O9 Ny_axis = 'Y'9 w) E2 K0 R' r) c# m

& {8 k6 Q* I; [* v# h! Xexamples_num = raw_data.shape[0]' I' J8 e# `7 n/ k) x
train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)
2 e! X2 c( ^" ?/ \- N- l! H
$ q4 s; w7 A- c8 d5 H
3 e. u, [, i1 @& l* Hmin_vals = train_data.min(0)
& S: I+ d  s3 m& t# e0 E$ j& lmax_vals = train_data.max(0)
0 V- l# Y1 ?) i! z5 {  iranges = max_vals - min_vals
" A- m( h8 q- F! q& [9 unormal_data = np.zeros(np.shape(train_data))' l3 S7 x, _% x! S" D7 @
nums = train_data.shape[0]
  c/ L" `% Z/ e+ Z+ g6 {normal_data = train_data - np.tile(min_vals, (nums, 1))
7 g$ l/ j" i; }) l' \/ }+ J- qnormal_data = normal_data / np.tile(ranges, (nums, 1)): k! g8 O) Q3 A. I4 U

. M* R8 |3 _* q% I. {0 tlabels = spectral_clustering(normal_data, 2)5 k( v5 F' d/ Q
! y7 ]3 H9 q0 _4 V
# 原数据
* V3 Q+ g; i7 d) K7 z/ w; Kfig, (ax0, ax1) = plt.subplots(ncols=2)7 Q$ o0 ]# L4 D
ax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')& U0 f0 l' ]  ~6 [6 h
ax0.set_title('raw data')
6 z. n& N5 T( |4 m# 谱聚类结果
! b# F% c* o+ R! v7 wax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)
) x- I  I$ r/ d2 a/ J& Sax1.set_title('Spectral Clustering')  m5 q! L6 ?1 j3 w# D

7 ~6 g8 M1 u2 _) \9 p" r# S$ O# jplt.show()
* M8 q. H) w$ b$ [* {
/ H! H( v" O& a" @1
1 I6 n$ E' }# X( A7 z$ l9 s2
8 i0 {! w# T" @$ \: k/ Y36 X, J8 J4 |1 Q
44 f, s( ?$ \* S0 I+ J, ^
5
/ m) a$ e% L0 o% l: R: z: ]3 ~6
# c0 N$ E" h2 Q0 D, k9 b( I7
5 O7 ?0 J6 M$ b. F! i9 }# L2 m8& ^. r# a4 W/ \0 o/ y
9
" ^" m0 v5 T* c0 n0 m10
* E* F" s* Y, s8 D! c$ S) I; @11
/ O! K* Z- M# q# R7 h9 e9 ~12# h2 ], _1 x" a: b  ]+ _
13
& C3 E2 D# \* y4 n& g  C14
9 J* i' U- m8 X. E15
: Y; O* T8 r( p, Q2 k16
2 c5 Q; w' q. j% O- \) r17
% Q4 R% F1 L+ H; J  {# f9 V, h( x18/ K: H. o. p% @' f$ k$ Z1 q) K% z. r
197 _; }3 o  y2 s
20
6 }- ^9 v( F5 d' z& z21
; C* G1 i6 Z+ \4 Z1 l& p- h1 Q8 R22. B+ w( ~3 O' ?. Q- d
23$ [$ v9 v  c+ u1 S3 H; C, I" m& ?
24: y- f! O) e3 @4 v+ n
25
8 B& u. }( _2 H8 Q26
/ K' N) v8 X6 M, T3 a; f27' x2 N# I3 W- r! F" Z7 {, d
28" Z4 E; S# q, ^8 G- f2 y
29
/ x% u8 F6 }. {+ @& c5 C2 \8 U30
4 V0 R: x. k# x; C31) H% i7 i# i  l8 ~( ^9 j2 p6 W
32
% T$ m$ d* h9 G5 h% X- k* R, V33
9 }0 D* _" x! x5 Y34
& T" K- Q+ T7 H4 z35
* E" T7 i( n3 G5 p7 T36
, d0 `6 X2 V, u% W' o- `37" ]. u; m2 C+ }5 L' }
384 x1 D% {1 p, g8 t
39' [. k% x* A, [- z
403 h5 N3 Z* y; v4 e1 a5 N
41: m9 I* n  D  Q  \# ?
42# d6 Z4 s4 n% E* T3 c* A2 I! y
43( |! ]2 ^' R  z& `" q
44
; `1 W2 `( z, O$ b% d* D0 c45
. t" ~( B0 T  A% e0 }  f" X46
2 l* @. L% X$ q/ k$ b478 _  M9 F. u. t7 s2 G& _
48' `6 Q0 X0 Q" S: }# ^" a7 M' Q
494 u, {: O: J+ k8 Z: ^
50
6 ?+ B/ |& j0 ^$ }/ }51
: C# i- ^$ M" F, l52
1 t& w" g  Q5 W4 ~532 a5 f5 J1 c$ o( y# R
54
7 {9 f0 p& h& K5 z55* x- H& y) U1 c5 l
56
* O0 q9 n3 g1 @* l* E  u3 o57: y7 a% N/ `4 M7 {9 G$ F4 r: u
58
. n1 |" l) y1 B. g. P3 A591 c/ i' M2 z2 z8 J: Q- _2 `8 r
60* O0 w  c7 a, o/ E; v/ W
61& ]6 @* Z$ e" p
62
" _  [5 U! I  G+ M, x  g63
7 |5 s$ X. h4 S5 g; m; p4 U5 o64% C8 C6 ^! N3 t0 b) d, b
658 X3 ?: A) ?2 J' s
66
: V. X& u3 X2 c. s& U" R67
% Z; s8 d: T$ v* `68
" t& k4 ?* v- N6 v7 h+ k69; F, K$ e0 o. e8 C+ a& l: B$ V# K
70% u9 E2 i6 G3 I
71
2 f' n  W) Z- c72: B4 X# t% w5 R6 k7 W( y
73
% \% M3 `. ~4 T5 }74
+ w6 k+ m& O4 B& f754 J& ^- Q- V- k* O4 ~
76
1 B/ B# J" y) W77
' }5 d2 f, d0 M6 V! [78
. Y" L  u! I# H$ N1 N3 j2 f79
! q0 K8 q. e. e80# M9 H1 S# Y  P
81  ]2 C* D# `: f2 P( ?
827 o2 N2 ~. H3 Q+ c# ?: q
83
. `5 f2 E0 ?( r% U: z3 v# C5 U7 g. V84% \9 ^9 a6 t% ]/ a; v
85
( h6 y+ W! U% b' X( |- m7 y) m4 q865 l. f, @' u, \& l0 A3 }* r  k/ N
877 |3 G% A5 @5 ]. b, p1 X3 Q
88# H9 w6 G3 ~* f) E. J
890 X! d1 g3 @. P
90
% @1 l5 @8 P) s, P* l3 F6 {/ A91
5 }9 x9 {+ a; _( l0 a# M92
' |6 T) v, j" t2 u3 A# ]933 \2 j/ {  O) E0 B( \
94
. j0 m1 ?" I- j) B& |4 d5 k95. u) L/ A- W+ p! ^5 Z7 Y- T
96
% K2 o9 b  _& e' ]( f9 B975 Q# m+ H" q1 p* m  _/ Z
98
- S9 q( b' ]! s& E+ Z/ S99
5 G, c- S$ l' y6 u# {+ i100) A' v, `: O7 `4 S9 J1 Y) r2 O
101: J& e! y, R8 L- r3 d9 H. ]2 t
102+ H$ Q7 @+ m( x' n  S
103
) g2 I" h# V! l2 T: N7 i（高斯核函数）
# v# x! J8 j( ?$ k* @) Z
1 f1 P& U2 W& r! c: b/ ^  V0 F
4 n" |5 `7 m; R: e+ H' _8 w（K邻近法）, R" d+ j! ~! e. [& Y7 a1 z. v
) e9 Y( S! U5 ?9 U- @

9 d% `) u9 p2 }7 r% _7 h  C0 d四：谱聚类算法优缺点
+ N" M9 N) g! ]  F7 _1 A（1）优点
+ B/ _3 Q0 u( e8 h5 r4 |; e谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效1 n3 G1 x% r8 l4 K  \
使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法
0 b) r" a  t& d! T, Z" P! l3 r谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解& k* Q1 ~2 D+ t: W4 E
（2）缺点
- u! q; o, k. s1 t( R2 P如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
7 @, r1 R6 X  Z9 O3 u. E' u聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同
4 ?. m' h* |' H6 m————————————————4 M7 c  A6 g3 F7 N+ ^$ ^
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
6 Q+ m( b5 m5 C% ^4 F& K原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494( O" b" k3 [, m* a9 K+ O7 w1 d# ]! W

7 V2 J) U: h9 Z7 u* M+ t" l& s# s