查看: 2946|回复: 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])
4 x. P- Z  H( X8 D. [( U return dist_matrix
, T3 j8 [8 j0 F3 n; `+ l: R
' t$ E! D  [( W7 Q$ Vdef get_W(data, k):6 F0 j% x5 O; N" q
# 获取邻接矩阵（K邻近法）
" D8 Y6 f. V6 K2 v3 |. r n = len(data)
( u+ `0 H$ I: W2 k dist_matrix = get_dist_matrix(data)
- s4 s# f5 G7 U% Z) x W = np.zeros((n, n))+ ~, }1 K1 Y6 g- {; A
for idx, item in enumerate(dist_matrix):9 h6 o  Y! P9 J
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表
8 b# H  g# C6 O* m& @) [       W[idx][idx_array[1:k+1]] = 18 w1 ]& H7 A' w! U$ r
transpW =np.transpose(W)
3 B* z7 B) C- x, i) Q) n return (W+transpW)/2
& }; q) q$ N$ h3 I' }6 C4 E$ _8 y. D4 @! s
def spectral_clustering(data_set, k):2 K. t, K' j9 }. s) q4 A
# 利用相似矩阵S得到邻接矩阵W
, D% q/ X; r) u' e: R W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）7 x+ x" c- ~! B" c! f! g7 H
#  W = get_W(data_set, k)  # K邻近法2 D5 Q* r0 e2 R! R. Z' Q$ B
! W6 |1 P9 r  H" n
# 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）
* Z) \$ y. D2 H+ B8 b D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))
6 Z4 v1 y7 L' F2 Q8 l* T+ d( _6 w
, j0 j7 J7 s/ O! j" D2 W # 计算拉普拉斯矩阵L=D-W
/ m  f* x4 z% E2 X # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
4 q: v3 ^* L! ~2 I  s L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)
' r1 C+ `1 t9 ^( @; a4 p# P1 Y1 _. f( d8 d. J& n8 N
# 得到特征值和特征向量# b/ F1 M' X# R( Y2 O. g2 l
eigvals, eigvecs = np.linalg.eig(L)7 e- ~9 e" j+ h% C1 ~

9 @- y8 {! `# F) ~' W# L- C7 w& @' n # 找到前k个最小的特征值（索引）
( j4 P$ S9 f# z/ `2 n5 n k_smallest_eigvals_index = np.argsort(eigvals)[:k]( t1 X/ H' x  A( p
/ ~6 K& G' W, a
# 取出这k小特征值对应的特征向量，并正则化8 w9 f( }9 }" @1 v: F
k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])
. l" g# f0 C+ P- @
6 a" V9 f9 T$ V$ `) r# ^6 a; c # 使用K_Means聚类
* A& i2 T$ j4 m0 }) P3 } return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)
# K! @% m" E. _- \/ D
# @% b) b* J" w& ]# X! S) B1 @7 i' E& X0 m
raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)
4 v+ t/ G4 R% y8 Uraw_data.columns = ['X', 'Y']
: O; f# x: ?/ Q# F$ r5 |" `x_axis = 'X'
$ X+ m2 z/ a' Ty_axis = 'Y'
) y! `4 g" k5 [$ K0 p0 }: Z( r) m9 T. B7 R3 C( E5 b+ j7 W9 K
examples_num = raw_data.shape[0]6 P/ }. r) H) i1 l
train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)
" z: x+ q5 t( N5 W2 D
6 j) C% a' l! \! H4 p! L: _
) x8 l# T4 t: f4 i% G) ?" i6 pmin_vals = train_data.min(0)
( q4 `5 r- F+ Y7 vmax_vals = train_data.max(0)& E% J5 r4 h1 W+ c0 h
ranges = max_vals - min_vals
8 Q" z7 T0 e2 h* o# k# cnormal_data = np.zeros(np.shape(train_data))6 x, h! R: d6 J+ P9 E. L9 g& S/ u
nums = train_data.shape[0]
6 Z* T. |9 ?5 E' ?( M4 ]normal_data = train_data - np.tile(min_vals, (nums, 1))( r5 A3 j3 Z5 N2 D/ i
normal_data = normal_data / np.tile(ranges, (nums, 1))
5 g  I/ M0 t% s$ h% Z7 L0 I. @$ M) _, x" l6 {
labels = spectral_clustering(normal_data, 2), M+ x: L; f0 Z4 P( v, U) V7 }0 U
! i& t$ O* ~; f- d6 g6 e
# 原数据
  O3 k' V$ [/ R" ffig, (ax0, ax1) = plt.subplots(ncols=2); I( J- U' A+ @! M4 U
ax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')
- i# h4 V# x$ M# nax0.set_title('raw data')+ H* [$ o! U6 X5 q6 p
# 谱聚类结果8 I4 C# M7 ?: j" X: [6 ?, G' l
ax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)
- Z9 {  I% `" c: N5 ?  k- e$ U* eax1.set_title('Spectral Clustering')7 k2 b* z! v# e: S# \

3 t' k! f+ v; q( G; W4 h1 m; V9 Pplt.show()( Z5 f1 v6 m9 o7 }* v, o) U) }
8 P5 J) t5 [0 M" ]
17 T) P4 X5 U. m
2
4 m: ?( r5 \( n3
. p% T9 o) Z2 X! w; R' V9 m% n% H47 n' G8 ?% U8 e5 z2 b# g" S
5% t3 ]: H# P+ m8 F, b
60 G! E7 a4 X3 {8 f
72 g$ u7 D4 t' ?# s. W/ I
8* k. M6 M4 S9 }
9: f( A! ^( c$ h/ i) O( N8 q0 I. t
10( A( G; [/ ?/ Z1 M2 r
11% y- v8 S7 r% `! c( f/ |
12
2 X1 V- s8 T6 ]: e13
% R. m8 C% X! k# K; E# @14' M3 s8 o* F+ H; ]" W% n
15! w8 C% f: K7 `! p# x9 f' d
16
17
: S$ z+ R4 d! \/ S! D, B6 ^) c18
# N2 j( T- |2 a* |1 ~198 Z: c0 ~  W4 q
20
  o$ o- T, R6 }% E216 [7 ~  {, r7 d
224 P: u' A: {3 r9 _: L9 n
23
3 u: l5 w; F/ o7 [4 l246 U5 O" B" h8 C( f4 s. Z" X
25
7 A  l) |/ a7 T5 a6 H. R4 u& R26
. w8 m/ _8 O  e274 V" }. T/ e. ^4 F# }
28
4 @. U( |" @$ D0 k# `. K; D295 B( x  E& ]6 H* T
308 n! s' t3 J$ y3 M
31
- z; u2 A$ G. f+ l5 {32
' U! k0 ?1 P& q( k1 }# X8 q) }7 A8 T339 O& Q4 P' G# ^" }
34# n0 ~. y2 s5 H- O" M) X0 L
35% P7 }1 O* B7 P% b  g3 E
36
) g! n9 \; ~2 [. b37
5 o, b' o' o+ o9 I38
( {: t2 y, C7 T, I: }4 R6 _4 t397 s/ E- |+ q4 @! O
40
% m! x( X, }0 J: t41) G* R5 D& V: c- H! x# p1 @/ I
420 x: O3 O' f3 T3 S3 \
43
, C# Y) t7 d. L7 w6 n' M44) Q) e4 S5 m2 o, G
454 B3 W' ]1 e' i4 d; _0 K
46
/ `* ~; U+ E. X  X+ Y47
% l% I& b2 H! s6 P48
2 R/ F: [+ p8 [8 `8 C! f7 H49
. d. \) S* Y# Y% ]50* ^* j+ ^. v. X* n
515 }, q+ A& v, q) T3 B( O+ K/ x
52
1 `1 W% u$ K5 e  E+ E7 m53' c' l9 ~6 h8 q
54! H; P" h3 U8 s3 C+ H
55
  C/ ~- L+ B6 ^- k! d* c565 M7 J/ Z+ _* {9 R9 r
57+ W: N. X+ C( g. k  O$ }
58" @" d# ?+ n& g- l: R$ Q
591 U4 e! z+ X+ a3 z) C3 C# @
60
/ G: v  }1 ^* k% S1 U1 b61
1 Q1 c* P& ~+ ?2 H62
7 J1 J9 z) F: b/ a9 L632 N/ J* B$ ?0 t4 q9 F
64
) @4 S* S/ L1 n* a65
4 v4 N/ U4 D# i, |. i66: v* @0 Y7 |5 d% f" m
67
- z8 D" ^/ ~/ n3 O$ T* G( N68
1 Y7 ], ]" E3 @- x) v2 }69
% h0 R* X. k8 D. |3 P% e70
8 @! a. @  l* ~% S, l* B71
8 M! V$ ]0 h- _! n5 j7 [724 m* S' I) m7 I2 E% j3 E; F
73% {, y9 l2 S+ O  _. N: n$ G% X
74' [8 @  H6 g# S; `% G& {1 \
75
2 C( s0 x+ c* A9 d. N76
, S6 U, m; f! K) a6 J0 S9 G77' r  H! c- |+ i- ?: T6 [8 d' \. }
78' U" D$ s1 o# S7 b9 x
79
- V: l  |; d7 S" Q. s80
" C0 T! n8 ?+ x2 S0 _: Z5 z81, t8 N6 `% R8 b5 ~/ r( S
82
  s  x. C( V) `% N83
+ Z/ ^) X. M: D84
6 H/ o" W6 }9 G8 X( G5 y' c85/ A% F) M' |% N( F/ |
86; l' h  R# Z" v% E2 A0 S6 a2 d
87, H3 @/ a! Y- |
88
3 V  y  G4 ^& \& Q! [1 N4 @89
0 Y9 Z4 h9 u% u; y" O9 Q. f' }! j90: s# Q6 w3 [# @
91
  p! m* d+ n% Z6 v92
& c5 e3 g' Q0 K93
# V$ \5 M6 _# ?% ^, O8 O9 J94
% S: ~( s" ?$ r) {& M: V95" i, w' [5 q# \. a
96
& m/ p! r* [* Z& `' ^97- e7 s1 D+ u  z+ \
98- j) c) b, [4 s8 B2 Z, ?
99! _$ F8 s9 N1 C; t+ y$ |' q' E- c
100
6 s! x* K9 @, X0 y% E- y101
% j' A5 x. n2 k2 b2 v: n102
; R" M: D/ m0 v6 w9 V/ N; m, j& H103: Y7 b* `0 ?$ J# B
（高斯核函数）
" {5 V1 K( Z+ Y' s# Q, ~$ l" S" w& V) ]+ E0 J1 G7 h. C- v5 i! R8 U  o  p
: h' c+ a" X. j& a. C. w$ z1 y$ ^
（K邻近法）
  H! p. [4 F0 I: i, y0 E
* y+ n6 d! [/ I' K+ j
) O- [& p! J: [. X四：谱聚类算法优缺点2 ^5 Y$ O7 J# c7 u. I7 p3 Z$ O1 n
（1）优点) b' }8 |+ O  [
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效
+ S# v" k$ ?3 `6 ~% w% j# d使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法9 k. V( L3 a. c4 y
谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解5 c5 n1 A7 d, D2 Q8 v7 w0 u
（2）缺点
% O5 a- j0 L! K' ?如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
! \: _4 \/ [& X3 T' \3 ?0 G聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同
* p1 V+ w( D: f————————————————/ D; C% x8 z/ Q  }2 j1 r
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。+ i9 Z1 m) E- Z/ d; `" r
原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494
2 c% N& b3 Y+ `3 w" x( ^
4 a# m  f  D; q( O3 x6 g  j. E% [
  o) F/ u/ ~% ?6 p* l4 x