查看: 3024|回复: 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])1 m; ^9 e% ]* N5 F9 `
return dist_matrix4 ?% t% q6 i% G9 [% {4 c

2 U! G, q" W- q: H3 w/ Q1 udef get_W(data, k):3 K2 G( [' r# b/ R; [: L" Z* ?/ E! }9 P
# 获取邻接矩阵（K邻近法）8 Z4 x5 O- a' u% Q% W/ R! B
n = len(data)% {  B% U) @1 ~$ ?" x3 z2 |
dist_matrix = get_dist_matrix(data)( C4 m! d- }7 d
W = np.zeros((n, n))5 ], J1 j7 Q9 i6 f9 T+ b! k  }( G, y: w
for idx, item in enumerate(dist_matrix):
0 b; Y4 i: ?; N       idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表, D3 Z& W/ L: |5 F" t& U* K, O
      W[idx][idx_array[1:k+1]] = 1
: G& c6 ?1 h: E' u- W; y. u* {% U transpW =np.transpose(W)
' y& v9 k$ c8 [4 b: A$ g* l return (W+transpW)/22 j/ ?& ?3 F& f( q  a

+ f" }* c: x* x* ^def spectral_clustering(data_set, k):
% L: I" k9 J2 ~4 s # 利用相似矩阵S得到邻接矩阵W( q% `+ n/ M0 X0 I4 N; x& a
W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
4 q1 P1 X: N7 T2 Z$ N6 `# J4 y #  W = get_W(data_set, k)  # K邻近法
* O2 r2 @6 t! q5 d+ o
( G# m5 Q" p, E  |* d1 Z. m9 | # 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）" `" r% B) T$ s' {6 L8 X  m
D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))/ z. N' O2 X& ~+ `( c

8 T7 w0 \( M6 V% P  j # 计算拉普拉斯矩阵L=D-W9 ~7 Z+ c7 c% u5 B* s
# 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv& r0 Z: ?: H9 Y% _3 m" H$ W
L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)
% `9 K7 m6 _! t# S% A# z" Q  e1 y# {% O2 c% u) E4 k8 ?1 S7 T6 x) f
# 得到特征值和特征向量
0 }% x& k% D& Q; w' d) Y1 h eigvals, eigvecs = np.linalg.eig(L)1 t! C$ S. W$ K/ B+ K" W

3 X# t' g+ U% S$ {2 i; W # 找到前k个最小的特征值（索引）5 ^6 C  h4 ]3 B' M5 W
k_smallest_eigvals_index = np.argsort(eigvals)[:k]
* @* W0 Q# s3 w; U% {
" I: K8 n# P8 E% ~' Z # 取出这k小特征值对应的特征向量，并正则化
4 S% ?" @+ \% X k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])6 z$ w; e7 M/ q
- m0 k) A/ {5 d; e" E. N
# 使用K_Means聚类9 `2 S& E. e* ~. p7 t
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)
" c) S0 [) j$ u) b: X0 }9 W6 o  |: |
% u8 z; x) g' ~
raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)
7 f& D. l  `& s- [raw_data.columns = ['X', 'Y']6 ?* \2 l, m( @4 l
x_axis = 'X'
, j. z; ^. B$ z$ @+ |7 ^y_axis = 'Y'
3 U; R) x) D% [
" E* Z2 g2 v2 L/ S2 [examples_num = raw_data.shape[0]
7 v( @: a5 l, ltrain_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)
5 B& U) [3 y: w9 ^: b
0 V1 j* T" W1 f
% k4 c* H, X' h1 K- wmin_vals = train_data.min(0)
. c, }8 Q% [+ T1 E- l- wmax_vals = train_data.max(0)
/ F5 I4 ?: y1 }6 Yranges = max_vals - min_vals
6 L' H3 v9 _2 t2 x3 [2 Snormal_data = np.zeros(np.shape(train_data))
/ Y5 V0 B# ^! f8 F: B3 b% Onums = train_data.shape[0]
+ g& i* `/ o2 \# S% \) I7 znormal_data = train_data - np.tile(min_vals, (nums, 1))" L* f% U; e+ h7 P# e/ p6 P
normal_data = normal_data / np.tile(ranges, (nums, 1))
! b4 }; x. N2 R# T4 q+ d: B! N; v* O2 m/ N2 ?% t$ H+ Z& Y. P0 V
labels = spectral_clustering(normal_data, 2)% C5 K4 T) p- v' }% h) m
" s( M% k; Q3 b6 \( U
# 原数据
, C9 V9 C2 z( b8 k' ufig, (ax0, ax1) = plt.subplots(ncols=2)
4 N, C/ H# i3 {0 u0 f2 U! D0 jax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')0 l/ B3 l! n2 O
ax0.set_title('raw data'). B; n8 u1 E2 h; ^. j+ d% U4 g8 y
# 谱聚类结果
6 w* P4 j5 v# kax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)( @7 d/ {0 q- ?0 U9 H
ax1.set_title('Spectral Clustering')+ ]9 x0 M3 y" K

- v" j) [. [- y) E5 r, h, Tplt.show()
! ~7 ?; \2 ]  b5 O/ ?2 R/ Q' W+ v1 ?7 Z( h& O7 V4 M. F7 t
16 q/ q: Z" Q5 u7 V
2$ w8 U& A, Z0 V, p2 v
3/ J7 B' ~( F- Q
4
$ |/ B4 f% w: p# b0 \+ v5! u7 T2 F" N& S5 Y; ~5 p; Q& a
63 j& X+ ~* M# _; A+ K2 u5 r
7+ k- Z9 z( U. s! x1 K# ~# [
8+ e+ e: q8 f0 s) h( x2 f
9
4 f" h( {. `" g3 A* |10% j; u5 f  n. y6 `3 Q# Q! \& o
11! Q, k/ i! w* R
12
: W9 S! R7 `" O7 f13% a7 U5 Q; T# x4 z- d( N7 ^" ]
14- I. [. L* Z+ N7 o
15
8 Q3 m) n+ b' b% ?, q4 d) P( R16
4 E9 W# d- q5 A171 Y% b- A$ s- i; \" S! P
18* j: b9 L' d$ V# F) y+ }/ ?( l
19( a/ t! n" m$ I) }8 N  r
20% g8 \1 v6 Q" F
21  {( Z. |0 A# x0 j: K; O" T; `: H
22: \8 b& L* D9 `5 e1 K7 z
23
- W- O7 I2 J7 P4 P24
  R# d8 q, j9 N& T6 X25
; }: O3 O" |2 e5 ~$ i1 r26
) D* L7 N0 h/ K3 L  ?27
$ D3 {, x7 D( Y1 Z288 Y# a5 D# |8 Z' v5 V; }+ `. P2 L3 N
29! s- U! z( w3 H9 @
301 W7 s5 o4 _. \" u9 X# ?
31
' S. W( n" i+ p; c( J32! K$ \# F3 ?6 s! D+ c1 L2 _" @) n# u- j
33
' {  q- s9 ]+ t. e, P34
. e( g$ b2 @8 \1 `' X5 H* Z+ j) Y8 Q358 a4 V: b# ^+ X
36
  K' R3 b! _5 V! `* A37
0 V9 ~: E9 D  X0 @5 b& S4 j38
/ {) ]+ l1 J+ y2 v8 T- S2 {% d0 x1 k39/ y) R) [8 P. T* s
40
5 U- I$ i( h" J' @7 [- ?41
% f2 B% m0 N" R0 m428 _5 D% Z& x& x6 \- O: U9 \) o
43
% l' |3 V. @( D- K1 x" j44
& V. t2 I+ y9 }, Y45
8 _$ M9 ~: J. ^% p8 n, \( a46- b( W2 V' O, s( U! R: z/ S* X
47" V% J; [) K6 x
48# P* q6 @$ M( ^' l" l4 \
49
- L2 v# u! q( u& v( r/ Q( v) [50
1 ?* n% t% ~& ?0 u4 @2 W51
9 i+ X  a- W# L6 `% J4 a52. ?/ A/ O$ S/ h  [6 y
53& o% H* f' i" o6 w0 `
545 g+ H' B" z8 y5 @2 b3 v
55
* X% Z, C; [( P7 l56
; i% H& V1 h( @+ w0 @  V) x57" k$ I8 D4 h9 o. \# c
58* J$ N2 Z+ \# W9 U
59
% d) o9 O: e1 `60
; @* Y& o) @3 y61& F3 @; i; ]; g
62. v( s) [3 S1 R* w; m. L
636 o# k) X! F( Y% |/ ~# S* ]$ I0 V
64
' F* k4 K- y3 |65
( _: x1 P3 X, {% h- `4 J; x9 S662 b" d$ {0 y# }+ O% X9 ^/ ~
67' {" o, ~) }" z4 I5 t. }
68
/ \, ^, y" u1 k69
0 J8 }1 p2 {( F, Q70
' f0 Z% G0 a8 f! [- q  Y71
8 T" h5 I0 r1 R- d. M8 M72
/ x0 q+ }& x7 x( ~73& p; o: h% `: E3 `
748 X: X* E( Q- y5 p$ a  T0 e+ w
75
7 p7 M- |3 J& l! E7 z. P- H76
  w0 Q% I. H( F77
( P  x& V: X* ]/ w/ i  C78
* n2 n7 m0 k% k% R* j+ m4 E5 ~79, J7 A& N) j4 r8 ^, V1 _) t9 X7 V
80
( n% g" v% ]: ^/ n+ O8 Y/ [814 M2 T* S% \* p2 E
82
" Q1 E' S+ y2 G: ]1 z# p83
/ g8 E+ ]* x" M0 Q  O* \84
" q% s1 f8 N3 H( w- _( T- y& X85
- ]1 O* M! a8 b$ o86" q& b# Q0 d+ w  j# \3 V; g
87
5 A; g# g4 E3 p" i887 e* x$ o3 [; t+ P4 y8 d& v
89
4 u9 _1 R. P, i0 p& D. c3 G( S: a# S1 ~904 Q4 ]1 H% B* U' m) _1 y# {
91
4 M( K& W; G  V$ p) ?0 _92! T, |! `, }  n* L
93( D! f! L8 h0 K( m9 U0 e  w
94# ]2 C' h% I, D, U2 E- a, D
95+ H( ?  U, E6 d& S1 b! x
967 R6 D6 c5 b6 \* O: \
97) j0 b! c% |* ^' n
98
# }6 p4 @4 p/ {! O5 ~99& P, q1 N9 {% i% ]7 {$ z
100
- F4 v- w) C  I$ s9 P# p9 C101; G- @6 p9 t: r, |# a6 A8 ^' ~4 o+ Q
1022 V- L7 ~* ?- L/ f" {
103
+ D, f+ _% Z& n, i7 `（高斯核函数）! \' l9 ]2 Y1 o9 E* s# Q
5 M4 s; n8 t3 T* ]) I& W" p
) u! z5 e0 D- F8 X
（K邻近法）- b5 L& ?" n# E% f, X

9 [3 _( ?2 ]& P; m1 W) |3 I; X9 n6 k6 B; E2 q8 K6 }6 @
四：谱聚类算法优缺点
1 w! L" `9 b" k- L, @（1）优点
, a* X7 }* f+ Y/ ^. j; d- a  X, S谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效
  F3 Q! ?3 ]) M5 [使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法' P/ Q: z& z5 T4 y4 F% ~/ T- {
谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解* @. D- O+ j3 O2 a3 r' u
（2）缺点/ q/ t& g3 V/ L( ~  A
如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
; o5 W% b4 _) e) A& E聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同7 T6 l" l& M0 v- x
————————————————5 ]  U8 a; o5 D! x: e9 ^: n
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
: ^9 S0 l; C+ Y3 x! q3 p原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494
# L4 g+ l' m/ X# {7 T% u4 J
% e) F; J  b! p1 Z" v) h8 l- t; H7 U# J! m* M: Z