查看: 2295|回复: 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]). _& C. p0 |" o$ B" C' s
return dist_matrix. Y) Y4 l5 y9 t; W9 i

" n4 c7 r5 R. F; y: `5 M( [def get_W(data, k):1 `$ a4 O0 x, ]+ R2 H( Q$ u
# 获取邻接矩阵（K邻近法）
5 |8 ?7 F' c& X- ^ n = len(data)1 I) |  T: P2 L1 F; B$ I7 x* e; f
dist_matrix = get_dist_matrix(data)& c' J& ~! A8 F2 x9 r- ?+ P
W = np.zeros((n, n))
5 ^  r* H' c, I1 {  l2 O0 Y6 A for idx, item in enumerate(dist_matrix):% _+ g! _  u8 x; N5 g, k
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表1 X' C0 q3 A6 p; x; B) A
      W[idx][idx_array[1:k+1]] = 12 a; a# S! S4 I  k8 @/ N" H
transpW =np.transpose(W)# P  Z* `+ c3 f7 y& h4 \% z' [3 Y' z
return (W+transpW)/2
5 J: l: m1 k0 k8 ]
- {) n$ l& X( `7 ?$ l" Idef spectral_clustering(data_set, k):
- n3 X8 F' i3 c9 x! e # 利用相似矩阵S得到邻接矩阵W5 _5 }* V( Z% ~/ g5 @% o
W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
3 x) I7 T" k: P/ G- u7 M  _8 z #  W = get_W(data_set, k)  # K邻近法( |* W! A! d- f/ B: r

1 U7 F, k4 h/ `5 U; d0 r # 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）
" J5 X% g5 s$ r! g$ y; D- G D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))9 S6 m* G8 F- x# g- O

7 Z7 v; z( q; _* a9 ?4 i) j( \ # 计算拉普拉斯矩阵L=D-W
; W/ k# t1 c1 Y, P  w # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv" N( |0 Z3 F& y4 s" o+ q& t
L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv): p# l& f, `! s' [; m2 R
+ a% v% b* X; ?. f
# 得到特征值和特征向量9 K7 c6 Q/ j4 z( S. W( j
eigvals, eigvecs = np.linalg.eig(L)$ c8 J5 c6 n- d2 A( l* i
* h* j/ L/ e1 V8 J8 F9 X& V& l; N
# 找到前k个最小的特征值（索引）
+ _5 I8 c$ R9 b% ^5 K% E& I8 v k_smallest_eigvals_index = np.argsort(eigvals)[:k]
" P, T/ p+ `- }- J& l4 o, \* v( v* V" @
# 取出这k小特征值对应的特征向量，并正则化; s; j* }5 H0 M5 E% G0 G2 r) W
k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])* X, q; a# o( |" r3 R

' m3 t5 a4 ]: G' O7 a0 n # 使用K_Means聚类
& s/ B7 N$ |7 t/ A$ j: F4 y/ \, H7 N2 J return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)
  J+ S/ g$ z0 ]
1 E* ^/ j7 K, z# P  a, ~% w7 u1 Y1 j. @4 F$ [8 P1 z( d
raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None), g2 b5 s9 S- ^
raw_data.columns = ['X', 'Y']8 Y; x3 q- c" d4 ^% N8 Q
x_axis = 'X'6 B/ j2 s* @* ~6 F- ?
y_axis = 'Y'
7 P' b3 s' y" _$ |
# b  U  K  \7 \. n9 P- j5 sexamples_num = raw_data.shape[0]% d. `  K0 s$ V7 y& v
train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)3 ?: |  U% w; M, z5 c+ C- n- V$ C
( i+ u  U. m) V6 q/ x

! o8 O1 `9 |) W  \9 fmin_vals = train_data.min(0)( u3 S- F' U8 {, |( }) M
max_vals = train_data.max(0)
3 \% r7 p0 [  _+ G( w! kranges = max_vals - min_vals
- |" w9 \. }/ W, I: w' T0 Pnormal_data = np.zeros(np.shape(train_data))
# d9 ^) ]# e  Z5 L- y4 fnums = train_data.shape[0]% L7 M8 K! j% L1 [& Z5 w
normal_data = train_data - np.tile(min_vals, (nums, 1))
: [7 x$ r" s& l. enormal_data = normal_data / np.tile(ranges, (nums, 1))" b( @+ q! ^  A
: b. S# m! ?, b% F
labels = spectral_clustering(normal_data, 2)9 h! a5 T8 D, A( p. H0 R
9 K0 z  j' m3 c* N" N0 X
# 原数据
9 x: e: l& L2 ~  S2 ?8 x0 wfig, (ax0, ax1) = plt.subplots(ncols=2)& R- t! _4 c3 f0 M( a4 n7 m5 L
ax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')
) V. I7 c4 ^( w. aax0.set_title('raw data')6 g) ~0 F: T) A  W, _
# 谱聚类结果
$ e% @/ ?& d* ]/ k1 P  Sax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)3 I& u- x0 z& T0 T: |/ S
ax1.set_title('Spectral Clustering')
5 n; ]9 h( f7 ]- c. k1 s4 K. x! Z9 Q8 C) @; f. A
plt.show()
6 z% \0 S( m- f  L" V) P) C; O/ o* w9 C5 o7 K
11 w  \! v8 P  U% r, h! E; o) r
2$ h0 f# a' L& }* l
3
* c( n- Y! `& q# {% P+ M5 E9 Z2 ~4
+ C; R+ a' B+ d' R9 ^* [5
1 F# F% U& l* R6
9 _% ?* e; d8 O6 c7
2 ]1 W: Z' [6 G0 P3 Q84 t/ r5 T5 X( ?  |, B4 i0 N
9
; f- R& S* u8 z! X/ F, t4 S; |9 T10* I$ O- `3 R0 w6 n* x$ J# A. P* [
11
& J+ a. ~  M0 N( L120 _) o) }. e  `4 z
13, l, ^6 k. q/ q1 r
14& T0 V% }  S3 C8 h  h' i
15
' G' Q% q+ D6 L. \* [3 V16
& |4 Q& O8 p) b: h# j9 c) H171 a" Y5 u1 W# A9 x5 A
185 J, M% S* a6 j# R( P5 m: e* o
19% z# |7 T2 z) L2 g- E
207 ~" b  k1 ?) ^; c- h- l
21
! y, h) g. H* I; D% Z) g22
; Y2 ~2 [' m* s( S" |6 X236 }, l7 [' x  U5 w9 D
24
" @. q$ ^6 t' H& q3 Z25
: y. s) U* i: m26
8 v" x# G) U  Z; i8 S6 S5 c. h27) ?  z, w3 ?1 k
28
2 a% v: U1 k) m297 p% W0 v  x  v4 @+ i" g3 ]
30
% r# z% d* b0 w0 K# ~1 V31; g& S5 T3 g1 J2 @3 U' o- F
32; e3 S1 ]8 a/ q0 F, b
33( y% [# G$ K* ^* P: A
34
/ c$ B$ D6 @; K) D! ^352 V# d2 q" W+ ~
36
9 z% j2 Y/ y- C3 a/ r" }/ H37% ~& e2 q, V9 W, |
38
  r7 C% A4 t7 m39% e+ @! S$ v2 S6 Y
40  D% y$ |+ a6 q  ~( Y- W, I3 {6 x
41
* E+ y- Q  r9 y0 x  f7 N& ?42( \, @" K. u; G" g% w
43
3 ~1 @! O4 V6 c44
5 y* \) [" z# w3 B45( p) {- k* s/ O, p  S
46
& `5 t5 j* D# `1 U47- p! c9 |# ~6 t  N4 r; n( G
48
) G0 Z1 c0 [- u, y3 z1 q4 C49
4 p+ @0 L* @6 U6 d9 d* }502 @4 i: C3 m  o+ e
51: H8 j7 k) }: x( A6 l& y+ w
52
- i! u1 Y% p+ @" O  Q) w( K53" C" }* F. t" u' \# |8 z3 g# N  j
54# Q" d9 w" N# n% m; x3 {
55; `8 h6 K6 u2 A, N+ Y( R0 ^7 u9 t
56
- ]/ J& p- Y* v  Z& ^578 ^9 s  Z4 `8 Q- j# B" l
58  G0 }8 Z: A( K- k2 `( g8 \
59
9 R) U( `9 T2 \. x( N4 n( h" {8 I60
9 F( O* E6 ?+ \. r+ `  d  e. |61
/ C2 F1 O" z8 C& j( j62
- S) {+ d' z7 H! R9 b3 t634 {! y0 r6 [6 ^! \5 ^9 ~6 E! v
64
( b" e% j9 {5 q; k- G" y9 W65" [7 [# `& @( k6 \/ A" N* ^
66) P4 a1 S. V# y" P" i; f
67, T! I: M8 L0 M% i% G' Y1 `; z
680 ^* B; Q* ]# H" T0 P  D. N  _
69$ N* n) R9 F. W# H7 U  G, s
70$ I3 \( m9 o) u
71
6 y' I4 X0 j; |) p. Z% [( P72: w% A0 t; C" J9 q
73* d2 T9 @, f1 z8 {+ [  I! ?
74$ m( @$ H8 M$ n0 r& e/ J
75, ^0 p7 @5 [! ^% v* ?; R
76. d/ I. T$ V' o" y( C2 V% ?4 }
77) R) W$ y, i% R6 i9 o
78
! S/ O/ [" ~. Q79
8 @: m. z1 ?9 i9 e- v: y80# f# C/ f# P/ b# Z( z8 v8 G
81
+ q+ j1 F% q; _* o! F82/ Y1 e2 b* ^% _  s  c; y9 Q5 [
83  `) R' }* r" Q! \7 m# F, `/ v6 J  e0 k* ]
84" W& a) h( u  `0 m9 j
852 i6 ^0 s5 q  ^9 j5 D! Y+ S
86+ }4 Y" O3 _; T8 q3 `1 j
87" ?) \7 }9 m6 c  V" F
883 H: J- ?9 k  l& U% e
89
8 ?6 m0 [2 Y& f0 _- P5 V% @903 |5 t& q# T: S/ W2 ^/ S  {
91
! _+ b  e$ h( T1 H) f92% s) u* F3 N0 N" v- u' }
93
5 K9 e$ Y7 A- d9 n) @94+ S# U$ N: l; X1 i, C* c6 ]
957 j- {3 C9 R0 h, Z6 U. }6 M
96
) v. H, V6 D' J97& C+ J% U5 F( Y. D* b) g
98
( V: ]3 R2 |+ I3 M! x6 |99/ e) j) X1 M" Y/ ^# |
1003 V5 w& @0 |- c2 X, n  R
101! G. X  a. C; X0 o9 o
102
  `  L( s3 H5 ]7 Z1037 X: |- c) k/ C1 t& r5 e9 x
（高斯核函数）+ t+ `. V/ {) `0 [2 B% w' i

& P* ]; T5 A: A3 s) O. _5 W" L; p' k$ b$ q) P2 _  X5 a
（K邻近法）
1 c+ p" m5 e! u; K8 l/ [9 v3 {) ~3 B1 }2 I0 _$ U$ q
0 U- @" i" Z2 F! O( |7 z
四：谱聚类算法优缺点
+ N+ b4 N3 @7 i# W! [（1）优点& f5 x4 b( W: y1 G. U% ?5 G; d5 H! P
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效
7 ~9 S0 e( }7 l使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法
9 f3 H' J( S- x, u( @, R+ L谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解
& M& I4 U' j. g; u  E1 K# c（2）缺点/ i9 `8 X" K6 v+ v( ^
如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
! \, o! d2 o! P3 U4 A$ T聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同
* k' o" p* i& }4 x( \————————————————# f8 K0 E) h5 w0 K5 u5 E& J. S
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
; T0 V, ^( M+ G9 u, ]原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494* a  l! j! F- h" ?

/ J/ P0 ?8 H/ F, a, ^
1 ?7 G' u0 \: V) n( d5 ?5 F