查看: 2310|回复: 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])
; ^) m  }; l2 ?6 N6 R" K" C return dist_matrix
: w/ H' e/ o5 a7 T3 i/ g
( D# O( O+ z* h2 Q6 r% i+ ?4 bdef get_W(data, k):, g% V! X0 u6 V2 J
# 获取邻接矩阵（K邻近法）
n = len(data)7 a% D; u5 j- h9 T8 T/ T# H
dist_matrix = get_dist_matrix(data)( x- F6 ~* i+ b4 p+ s) H5 Z0 K
W = np.zeros((n, n))8 S6 X& h. w$ l" `) `% }3 A
for idx, item in enumerate(dist_matrix):
  C6 a, Q8 H8 f5 S( P3 H8 q       idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表" C& t- p+ s' \1 s" X2 Q
      W[idx][idx_array[1:k+1]] = 1
* L8 ^) [1 M& A. c1 D5 ~- { transpW =np.transpose(W)
2 _, ]2 m8 c1 V6 C/ U( ^4 I return (W+transpW)/2+ l2 ^& s0 {" d( v0 A: R$ \' Q1 y
2 W4 l3 d4 n& u8 F& o
def spectral_clustering(data_set, k):2 g0 r4 k+ t5 l$ L$ w
# 利用相似矩阵S得到邻接矩阵W, s: p! ~1 F0 ]7 f, Y
W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
1 Z, }; Z1 x7 J. D* G1 C #  W = get_W(data_set, k)  # K邻近法
; s  @5 G4 |& T9 E7 {; K
( U/ r6 U  ]$ G' _1 c# w # 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）
  n. M, y  B' K: u' P. L( e  Q D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))8 U. c, M1 P* p& h' |
: i$ j9 S* D2 [) K
# 计算拉普拉斯矩阵L=D-W* ]2 N% m5 z3 l9 ]$ N; a1 i+ U  U
# 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv6 Q  ]# ?3 w* \% }  A# b9 k9 P2 q
L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)
" C2 D0 j. y: x$ v4 \6 B) \% u- m' b* S+ z# f! ?
# 得到特征值和特征向量
- ~. u( T' ~" ^, @8 i eigvals, eigvecs = np.linalg.eig(L)
, {( j' b! u% h) y0 L; ]" n
. j% |  t2 X5 G" v" A" T( H # 找到前k个最小的特征值（索引）% J% b8 n$ u: h1 ?
k_smallest_eigvals_index = np.argsort(eigvals)[:k]" n! \  K/ V$ @4 e( f( C- @8 o
4 K  f' ~5 D  K: O
# 取出这k小特征值对应的特征向量，并正则化
5 p  x8 C* u  U0 q+ k k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])) i! J& \, a0 H% t# g+ S
1 S! q& h& C$ F  ?
# 使用K_Means聚类& @/ x3 B) o- F0 i8 e
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)2 Y6 ^+ c2 r) `3 `4 u/ v

. a" H' P; x' r- @- p3 `
7 t7 h  v- _- Zraw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)
! P3 ^4 E; S0 z* t0 ~. }raw_data.columns = ['X', 'Y']+ C7 w% f/ R) Q* m) x" G8 i8 `
x_axis = 'X'. A9 _& e+ c; p7 H2 Z
y_axis = 'Y'
- B4 o1 q& f& l+ k8 }3 R* [6 f& |8 c" Z( g: B
examples_num = raw_data.shape[0]
" @5 M& v0 {2 e" U( r. H0 itrain_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)6 y1 a2 u1 C/ B7 c6 \7 o

; m: R! Z6 B. U% ^. B& C) ]; V5 x/ o3 S. x
min_vals = train_data.min(0)- O! a# E9 _. X$ i, T! O! C2 x
max_vals = train_data.max(0)
. P- \% p$ c+ I$ M2 dranges = max_vals - min_vals, m9 K. X2 I/ A" ?& q
normal_data = np.zeros(np.shape(train_data))
/ v; \( w. x7 |) l6 @nums = train_data.shape[0]1 E# i  Y9 `2 @1 b# C5 d
normal_data = train_data - np.tile(min_vals, (nums, 1))
& T& q: h! ?  m+ |3 s" Z, A" ]normal_data = normal_data / np.tile(ranges, (nums, 1))
: n0 O% v+ U* T% H5 y, t9 Q2 n& p, E8 q; J9 A$ `3 u5 G- e' R
labels = spectral_clustering(normal_data, 2)8 J3 x0 T6 V* r# v+ ]; c; w
8 F) N! S) g8 j; t$ b* w: P
# 原数据
! d6 w  W* w7 N! [fig, (ax0, ax1) = plt.subplots(ncols=2)( i  G& P  E* R- ~6 x$ ^# n3 A$ j: m
ax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')6 h/ f5 [) O! h& }* r4 e) L
ax0.set_title('raw data')
0 W. q3 l( v9 z2 M" \. y# 谱聚类结果9 Q( i) x6 F" w8 W
ax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)+ k+ A4 p2 t; B- L' Q: H! Q$ w
ax1.set_title('Spectral Clustering')
, r2 N7 R0 H( R' Z/ n' g: n
0 H$ j3 A3 s- u. h0 [! Bplt.show()5 x+ Q% i5 h4 T. X& X7 @6 S9 _) K
4 s: ~6 F% z& K; R" o8 s5 i/ l! @7 }5 P
1
. O5 h( d# g6 `! P2
; A- n+ J6 r7 W8 `- Q3
9 q7 J! ?1 e. S4 ~2 z- E. h4
* d7 ~9 Z4 x% b4 R5
! `" _" A% ?/ ]6
4 O# W) V$ G2 g6 _, Y7" L. E. }4 {# U* b: J. ^
83 @( X6 g+ G. B* i4 W& z( v
97 i2 r* p/ }5 z# `4 ]# P
10# U9 d, Z5 r6 Y8 ^! g) z
112 e0 D: D. E& }: o3 L
12$ Q, E9 g+ Z+ b+ L% E
13
( O" A% |- |$ d: I0 m5 O. f4 n14
6 J  b: w* r6 y; p& n15: I$ r+ y6 P) e. E' \) _" l8 x  P
16
6 w* \9 `, P7 s1 T# b) p17; W; b( l) W9 @
18% l! {, `6 N( w
19
7 J6 z7 C; L* S" K4 P/ _8 a' F/ V20) \8 u  }+ k" h: Q6 q1 f* V8 s3 X
21
4 B  [) P* ?( D0 \22: e2 K! u0 P8 D: e
23
. n# u+ h' u' A) E% t# u9 |! j; x* e24
4 F8 D# j5 p1 ^7 w6 L0 a25
" |! z# H0 g8 l7 S26
: j/ ^( v1 o, m+ I  w1 v8 i4 J27+ _1 j& {, v" X6 B; n, v
284 U$ N) ?0 y4 E: Y3 a) D
29% _3 n/ B5 C: K. N. c0 k
30! T8 A, C7 `7 D: n( j
31
4 ~' b  S/ D# u$ l32
9 K- b. ]/ V, |' ~9 d6 a& `* l33
7 ?* W' F: L. C& j1 g- _34
' N) u4 W3 C* T* U; e5 X* |35
4 Q, x8 ^4 M! s. ^4 ?36
% V( E- O% R$ O- Z+ R7 V' t( g37
2 H' S1 Z$ U, a% U$ |9 Q3 Q2 m- A38" j! g4 h, p" i# _9 |
39' T% j( p8 N  m
40
: R7 ~8 E! r: f" q+ c2 l! x6 t41' N, R- k! c% v
426 \- H  U6 V* i6 o, N. p
43
" D5 l- _7 c( Q. ]6 s( t" W5 f9 F4 f441 E5 f% o2 Y8 X" s( o
45
. x7 e& w* A0 h- u) x( i46
9 u8 @6 P% i9 p7 e1 Q3 n47- c+ M3 p# D8 f' U) N
48
: J# ^4 j) B* d# v9 W/ R49" m3 N" v7 [0 r
50
7 x& r+ I; k6 D8 k. [0 ]2 E51
. A7 e) c5 s% W8 ?/ t52
; O# x6 D3 u* V4 I. I1 m53: A7 t( }, D4 R5 m# q
54
3 e$ P! O8 x1 d4 I9 P, {: A55
( _4 q; ?+ h1 v; [; H, j56# R: T& z8 C" C" n. \
57
1 P+ u$ c/ x9 j6 x% a58: ~) M- Z3 Z/ Y* {# ^; ]( w
59
) G/ o5 T% o5 P1 b7 a; ]60: O/ w8 S  N, L$ \
61
' O; s' x  n, }: \9 W62* b+ Z3 m+ [( d6 }( q$ h1 F
63! [6 h4 P  Q4 K1 L! q
64
! `. U' w) B0 I/ ~, m* H# `- s! {0 R657 j, C! ^5 e8 b
66& M: S% r0 O3 Z! L6 s- `. Q: I
67
, S6 z2 s& c' v% j5 O4 ?3 k68" V3 U8 I- t4 h& ~( {# i% Z: {; n7 c
69
  ^# I- f; ?2 Q) Q3 d9 n70& q' d2 _4 i' q7 z: e, C, o7 r
71
* @7 Z5 N6 \  O6 J- i9 i8 }) c" ]72( v% o" i: X) l1 m. r) D0 R/ m
73
$ {  y; L( K7 O0 e" W* u3 g74
/ f8 d# f9 Y% k2 n5 @75
; t! A4 @5 K% Z% x0 I4 e; `5 l76
$ G- Z/ C2 u, Y. D) a( l. w- B778 D$ a) K# R2 y9 [  ^9 X  y
78
$ m  ?5 e( I6 O! c' `/ x  H79+ q) ^3 |% P7 c
80" a) d5 T6 m8 C7 @  T6 K" d
81' D* _) G- J5 R7 F0 J# Z- ^2 _- W
827 _$ m2 d; i* I* V' A# a% ]
83
4 W- c7 U* O2 `6 `84
. v$ ~5 X! ~) G  r! @: x6 N85
1 D. w! k0 q( w- ~86
2 s9 |7 ^) E& f' c( S: ?87/ f) e7 h  o7 U1 ]
88
- |4 N( }) ]8 O$ K1 x89( Z: ~' @- |: |$ h! Z
90
/ Y& |7 p. e1 z( n91! B9 c1 X" S% q: w
92
& r2 w+ L- M& h9 D937 X% h% B, y' p. N8 u5 k
94
: J3 ]+ W/ ^" f7 R! v5 y% O95
  e5 m: S5 M5 A" |96
* C3 U  K8 s8 k1 S3 y. u97! [% j% E: e! @" }
98% g& Z* w) O8 z& G
99( \& U+ }7 v3 g" Q9 i2 f
100
- A! y% W; J+ ]3 v! E1011 D* i& e9 V8 {  i9 a5 f4 ?7 Q
102
; q+ ^$ m+ M6 P2 h9 U103
/ z5 D0 `1 Q7 f; b' Y（高斯核函数）
' b, P  j6 g! H/ b; @2 [; s
& {5 j) S; n. [/ Z2 D% A! i" G$ E! Q8 J* R( L* ^. u4 a
（K邻近法）! Z% O0 b+ T: C6 r1 X: u% B7 E
  Z$ ^# W# g8 Y3 L
4 K5 W; u" E. S
四：谱聚类算法优缺点  V8 q' l0 x( N. l
（1）优点, [: `# f" M7 L# g
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效
' [. ]' c) K% ^4 N/ H. Y使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法
2 J/ Z3 U7 Q! Q- o5 {8 z+ v谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解$ s4 P! ?" T, g& c% V
（2）缺点; J0 ^& P4 U3 y8 z5 m
如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好# }1 ~. g( a- E" B
聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同! l( ~$ X+ `4 ?4 U% x
————————————————* b/ e. P1 i/ O" f
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。9 O: \7 X3 q9 j0 X
原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494! V9 ]( y/ u2 \2 d) y

2 Q: F. c: V! M' ?7 |
- w/ J' b. M% e+ k' u9 `3 f