查看: 3031|回复: 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])
! ?+ J* a0 y8 B/ G6 G! f( p return dist_matrix, H" _) B: o1 {  W
% B/ U- L; J. i- J& S) J7 b, B
def get_W(data, k):
- L! I) w* O& e) U # 获取邻接矩阵（K邻近法）* z3 ~, }0 n1 A& x
n = len(data)
! k4 j& }9 Q; Z: Z4 K dist_matrix = get_dist_matrix(data)1 K# z" }  c1 |) {" I5 {' r
W = np.zeros((n, n))
) K( E! b9 F+ w for idx, item in enumerate(dist_matrix):/ L- a/ y' |* O+ ]3 ?
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表/ D8 C/ N  {* d
      W[idx][idx_array[1:k+1]] = 1) D2 G3 `, x8 E! f! D2 B
transpW =np.transpose(W)% \3 p7 _; N$ d/ F7 m9 M6 C: c
return (W+transpW)/2
9 {) I/ q, s, d1 [( r8 C) @( p* ]- s' g3 S6 @/ }$ |# V  L2 M9 N$ N
def spectral_clustering(data_set, k):
* M! L1 v3 I! z3 S6 o, D # 利用相似矩阵S得到邻接矩阵W
. t0 o  }+ k+ I* |" K0 ?& o4 q W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
1 x$ N# {3 E3 P  B- { #  W = get_W(data_set, k)  # K邻近法
/ r9 M9 R3 S7 P6 t, G- W/ F3 u3 f, Y1 ]+ W3 E
# 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）) U: M/ }) g' n
D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))
5 M# @: v2 |4 E- l- M7 e
& v; S  w. Y1 n# w% A # 计算拉普拉斯矩阵L=D-W% u5 U3 J$ B( H3 z" z" @
# 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv" y  s3 Q! i( q* o5 ~$ G
L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)1 o& j! g6 f( r) ?, t
; o4 P) O# Q; [5 L. U
# 得到特征值和特征向量9 f' Z5 ]% @3 n: ?- u% g
eigvals, eigvecs = np.linalg.eig(L)2 y" o/ ]! @) P0 ?3 e* Q' |

0 {7 P7 c$ f5 j) W, V8 P; b # 找到前k个最小的特征值（索引）
: H7 C" u& ?: a+ K. t1 R# l/ b% G k_smallest_eigvals_index = np.argsort(eigvals)[:k]) _: g. K" m. R2 R5 @

! M6 y2 |; m) F$ g # 取出这k小特征值对应的特征向量，并正则化5 D2 [# _/ N( Y
k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])" V% |( q& S, b2 @
: ?. N9 V6 y9 r7 p, \2 N
# 使用K_Means聚类. ~# F. @" P1 S! m) a4 F% L, m
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)
5 a# D; a/ L8 z" B3 h8 ?2 P6 D
6 D! j2 V$ X5 R0 l" k7 d" }) O. |1 F9 y9 w' }. L
raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)' ~, Z) W1 o. I6 J% b
raw_data.columns = ['X', 'Y']8 g- Z2 V! L4 K. \
x_axis = 'X'
  W" W, I- s2 _# D% py_axis = 'Y'
  `9 J; L- N- P, `. h# m2 e  ]& C) E# a. n! ^. J
examples_num = raw_data.shape[0]
8 @% I/ O% P- G# J4 etrain_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)
- V% _6 ^+ h2 s9 [' Z0 r  v
/ @* N0 j# p9 k: S( w7 N9 ?2 S
3 ~; Z: c" k) y% ^min_vals = train_data.min(0)
" {! m  l" z+ O' A$ O& Kmax_vals = train_data.max(0)
8 v! A" y  }6 W7 j) g& Dranges = max_vals - min_vals% I+ B4 `' C7 I2 S$ @; w2 d
normal_data = np.zeros(np.shape(train_data))/ @- e, Y/ M( |% I- {( K$ y7 D
nums = train_data.shape[0]
4 J+ t  y2 S6 B: g* Y) O/ cnormal_data = train_data - np.tile(min_vals, (nums, 1))8 d$ Z: d3 I5 j" ?+ c% ^* @" P) l
normal_data = normal_data / np.tile(ranges, (nums, 1))1 r# e6 m/ v: i( G$ z( ?

% T( a& f6 A' l0 z( Hlabels = spectral_clustering(normal_data, 2)' h# E" s2 v1 c3 s' S5 p; |
3 B# F# u% u4 s5 C+ w% y1 {
# 原数据
# [3 ]+ @8 b/ }% ~fig, (ax0, ax1) = plt.subplots(ncols=2)
) T, X& r$ I0 R6 P, ^ax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')5 m- f; D5 I6 ~( d7 H' @
ax0.set_title('raw data')" O6 q6 e/ B! q: f, i) g+ Y
# 谱聚类结果) K4 s) b4 }  O) V. R3 v/ V+ H
ax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)) B% ~( K; u, a& n
ax1.set_title('Spectral Clustering')
! k) [! ?5 }% a% q
& p- @+ R0 H+ M6 V6 X& z4 R* yplt.show()) m; u9 u3 b- N7 Q9 U& M& R

: V  |/ w( {8 C# ~! x$ O0 N$ C  F14 V. j, K$ ~3 n4 s
2
; o% c4 G5 c/ q$ [, L39 c9 `8 S$ y$ R! y( v# G1 W
4
; m. j9 |3 K" K! C1 p5 b5+ L9 u+ p3 r/ V) T
6
! J# D% q' o8 [: M4 v% |7/ r: @& H  x- ]. z8 I0 q7 r
82 b9 E1 M' o7 g1 e* v( c9 o6 d! Q
9, R# ^' _! l& C3 }
10' e) J. {0 a* X
11: ~9 l. V0 A2 ^$ r9 ]
12
, d- `" I1 m+ b' U$ N! F4 B135 e! v% M" [+ Y# q; a4 C  x  }/ j
148 L7 o, X% T+ V6 ~$ s9 T1 |
15+ ?3 p5 u* b2 [& T' |2 a/ P/ ^
16& G& K7 d1 }; K7 S) }! V9 d
173 G; b4 |- X$ k" r
18# g. L  e: q- A: A! U- Q3 @
191 ?0 e% `, V' X( X! n
20
- R, P" P0 P$ X% R- f0 B! |3 Q/ i% K21
; ]/ P) i4 g: o9 Q7 @( m22. n1 ~/ f; A7 \1 ?
23) s: X2 x  r6 X9 e
24
- f5 o( G* v/ }5 l4 r9 p25
7 h$ l5 `, s  R8 t# ~26
' D' T# A. P* z2 A- G, f7 X8 o+ P27
% u0 [6 d1 J; a- k" Y% b28
9 n4 f* ]5 L( N3 Q  `9 u; T299 R+ w* @+ t* P& u+ X" \* m
30
" \7 m5 {: o; ]* a7 A# C31; V5 n4 y/ e' w& _
326 G. D" }. l! F; F7 U* m
33
2 K1 H2 K6 S5 S- s  T' b0 P34. ?  U1 Q8 Z4 n7 l2 d; V
35
8 M3 V9 {. h. o6 J364 r7 w9 ], L; N
37
+ V% u& r; ?& [* E: c# |; w381 |4 U2 h! m/ u  N# W! V. Q% S. }6 F
391 C: }5 {( s, ?. w  N3 e$ s
405 N8 P6 e$ E( V  }' a' ^0 e
41
* }4 d9 Z" i! Y- R' A+ J, a2 E0 `2 `42% |, H: ?  q1 Z' @- H  \  D
43
+ i+ A( r+ h1 M" Q' S5 o44
& f, l; y. c( _; _9 D: @4 @456 b1 C8 \1 W# j, @
464 p: o/ ?$ P" G4 k; f! H5 a) X! x7 p
47
/ a6 r5 R; _. h# X6 b  [7 m9 X4 _487 e4 `- i' M6 H& H9 y, l3 g
49
! o; w- z- X, u& K50
  R! E' U4 ~/ d8 O2 I$ z51# e* K* n; d1 K
528 F! |( v1 n0 G0 S$ s' l9 R2 I
53
& P8 D% n# `% z' I54
; v1 J8 t9 W  I* Y2 w555 M! T% X& b, X& h' J
56
7 ]& W- L3 f9 v* S) \57! ^* d5 a4 m# [1 N0 g6 u
587 u$ {$ q- z1 L
59" H- h2 y- @5 f  c
60
8 B& N" d* Z! |1 [  t. }61
' X! ^) d& f3 t/ n( L62
7 \( k% |) c; O% m63
5 M" A# p  |& ~& E64
0 D* x9 h5 C% C% r- g65
, {, W+ {) P/ _+ _4 |66
' Q9 {+ k% ]; L. o: U67
3 L7 w7 D& [2 `1 J/ m5 X68' Z: N5 P0 [0 ]% a* V- V
694 @1 Y; D3 _1 _! b: [
707 b# m+ D: D- [6 X
71  C6 m% b' y- D% _5 g3 b
72/ l( _" O6 C2 T# g. v
73
4 D# _3 L8 G6 m$ @74- ?7 z! e5 D" D& i# E" P
75
! ]: U/ N. R$ l76( i* }: ?* t5 Z: Y& r4 ^7 s" ?, [
77
. @' Q- I; z1 a3 ^78
# |- A5 G9 N  Q$ |, O( H& O& \795 v$ {& s, N- E
80# r) U1 A) u/ h
81
9 H( k. t" D5 h9 {. t82! A$ i" i* ^+ j# H
830 s$ [' }+ g0 \0 K, K/ V0 W) s/ ?
84: X* o5 O. o; a$ Z5 k, t3 v
85* V: U1 h! K! g6 ~$ w- P+ F5 J
86
0 A8 y, s, |: {5 g1 E$ i  J1 j- \87
$ p# O8 o. v' A( U0 ]' q0 D; \88& C: A8 o6 Y- M, T8 J
89
( c& ?  v# B" v" `9 r0 c906 e+ @$ D0 A. {8 _2 m
91+ i0 _1 d* }- W) c
92
# `7 F% y& K) @5 l; z93
' @8 H6 d. s" W6 E" O. l94
5 D' L7 U/ C5 N  j95
4 g7 w+ M: T. X5 ]96
6 O3 e- k* ^/ s3 @97
' f: R- h2 r: P1 r; @! g98$ x8 ]" [* @6 E. c1 I! {
99
. Q' u1 L0 Y: d7 I8 x! w6 d100- y9 z* H% k& A
101
+ L1 I( K) E# w( ]102( o: h! M& e' F5 R* @; R
103
8 n3 K3 X7 `. ^0 ~  X3 l（高斯核函数）4 d1 S$ F* l& e! X6 J* U

* T' ^) B6 W: z+ L5 j" P2 y5 W) j1 |! n, R0 k" g6 `6 ]
（K邻近法）( z7 q, b9 O& v+ E6 A2 n! \

" y0 }' ?& f! Q. @1 {
  H4 ?! q0 r: \2 Y3 n四：谱聚类算法优缺点+ l+ Q7 d: B4 |9 Q3 f) Z  }5 l
（1）优点. L. i& J5 j) i$ R+ ^
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效
, q$ q6 u! J, E. a使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法! x: `2 d0 W9 ?$ _( C: l) x
谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解, y' C/ ]  [6 P  e
（2）缺点- _9 l8 c, R. W. W
如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
2 c' N* R! o# {4 B, Y聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同
. m( \7 R+ L$ J, i$ F% E( J/ S% p- f————————————————: E" T& E$ f! a5 e; v; R" Z
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
, f- C% k( k2 v0 R: I3 Y: @原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494
. U& J; {( {1 v! p& l8 I2 `- O) o9 d! F' X( M( Y
+ p) N9 N) B$ m- F