查看: 3010|回复: 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])0 \) Y+ P$ }1 y. u
return dist_matrix
0 N0 s8 x* J+ G2 |2 {8 c8 g) d6 I' l! t- |7 e6 H1 k* B
def get_W(data, k):! K( ^$ S/ d2 D! S( G! M
# 获取邻接矩阵（K邻近法）
6 o% T5 B6 o) t& z n = len(data)
. n4 F7 g+ w+ E$ S8 N/ Q dist_matrix = get_dist_matrix(data)
4 F9 K8 x% n& E( h, U. U. m8 `; n: I W = np.zeros((n, n))
3 }& g# v& ?* w' ~4 j* x) X& M for idx, item in enumerate(dist_matrix):
! u, q: A. c9 B* n       idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表3 j: t$ n4 D; n
      W[idx][idx_array[1:k+1]] = 13 G( S) y; _* y& _, F. \, y* L
transpW =np.transpose(W)
* ~& W( e" l; Z6 |, ^ return (W+transpW)/2$ U2 R% J  H' u4 |- c4 `' j# Q
. t/ {* C. A: L9 f$ W
def spectral_clustering(data_set, k):
: s$ n9 N" G4 J: ^5 S, N9 ^ # 利用相似矩阵S得到邻接矩阵W
8 S' ^0 M2 a0 v+ d2 }( r W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）4 L4 h- {5 W& [4 z' _" L
#  W = get_W(data_set, k)  # K邻近法
* |# A0 [: E' K! }
) J$ F1 `5 P1 v, i8 ], z # 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）' y; \: S5 Z3 X2 V% @( T
D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))
  t+ L/ l* Z( w9 ]3 M# }: Y. L
1 X3 U  K4 q5 @ # 计算拉普拉斯矩阵L=D-W
) l5 k3 q$ o, o; O, \( l: r8 w # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
+ h4 I; W( {0 }3 t2 f, \3 E9 n# g L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)
' r4 `2 i6 r: T& p% m% U4 [5 Z% M/ Q& C. {8 @
# 得到特征值和特征向量* K1 J: V5 ^$ K1 W5 r6 B3 L
eigvals, eigvecs = np.linalg.eig(L)
% v' b; Z  V6 W
' P" O$ C" H& {: ]* O9 m4 M # 找到前k个最小的特征值（索引）
! R- d! o. |3 a; `3 p k_smallest_eigvals_index = np.argsort(eigvals)[:k]: e7 m2 `# o3 C) S

8 A6 z$ E( V% i4 b) } # 取出这k小特征值对应的特征向量，并正则化/ Q" P/ s$ }" o$ g  T- S
k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])
! S2 A+ M$ G% `" I' h# O) Z, U$ ^8 v) J/ f* v
# 使用K_Means聚类
! t4 R  T* ?' B* X6 z; h return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)
- e- C% B3 \6 ~! @: c1 l8 H2 z& h) v4 a( s+ @- z6 q

! K; K, Y1 S" traw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)! A+ R' `( _3 s9 y
raw_data.columns = ['X', 'Y']* Q- Z  i6 F: V
x_axis = 'X'
5 r9 j6 {; b- Gy_axis = 'Y'8 B$ a# ^7 k2 J' n8 I5 q2 w8 D, g

: c8 W  G% o& F* f! O2 F# fexamples_num = raw_data.shape[0]) p$ E6 x- Z' i+ k
train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)5 `( U. r% V& F6 {0 }
7 S8 y4 `/ M; _0 `% j

# Z; T. r$ B% L1 Dmin_vals = train_data.min(0)' x& g& C6 ~1 Z2 Q
max_vals = train_data.max(0)$ D6 |3 o- F( j# D
ranges = max_vals - min_vals
' H0 s1 m! h. ^4 Snormal_data = np.zeros(np.shape(train_data))
8 _9 W' a4 a5 i+ J3 ~nums = train_data.shape[0]# l5 D7 s! v* `) d$ C% C+ m% u' {
normal_data = train_data - np.tile(min_vals, (nums, 1))2 Y. k' J2 Z4 D" t; Z- l
normal_data = normal_data / np.tile(ranges, (nums, 1))
1 Z; Z$ t: d+ z, b) |9 }
5 I- s1 R3 m7 B2 t: L$ qlabels = spectral_clustering(normal_data, 2)6 g& k, m$ v% {! S
$ q5 I- ^( \: Z* a
# 原数据) c3 p8 g4 [* N6 V" g
fig, (ax0, ax1) = plt.subplots(ncols=2)
' J( e4 b( y) }ax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')2 o/ S, i! C7 Y0 \! p- Q( N
ax0.set_title('raw data')
7 b& M- w4 C/ X* W7 R% d# 谱聚类结果# W) L6 s# U$ ^+ H
ax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels): @0 D# D! t2 m! K1 q1 T; ]" c
ax1.set_title('Spectral Clustering')
, }; m7 b& R. ^7 ^9 M
) h  [8 [* d+ P6 D7 L7 zplt.show()
" c* u2 y$ S9 n6 B% j" Z
3 E( w( f& A6 m4 J: N% t1
/ q; U- F. j5 _, k2% c% }3 S  ]$ A$ b4 z5 g
3
% \# z$ q- o* ?& e4" Q/ ^* A, d% [& Y5 I* T
5
, Z  }8 W- C0 c+ ?6
% {, l% L, Y0 N. C( a/ l7
' S$ p! a* t2 W4 l8
2 s* M- p1 K. T9 G) _. A8 a9
/ Z0 a- C: R% W% ]5 V: ]2 L4 N- o10$ \9 X0 q7 ~' D9 _& Q/ f. D
112 Q4 P! v7 U5 |5 t+ I& O
12
% |% K+ F0 V  i& K& W13
1 `6 F  z- O' ^* M7 Q8 a- N" V14
, M+ u5 P$ |" u15' I& `- m1 T3 ^( n
16
8 Z- R; I# J) I1 c2 u( h175 w. _. T$ B* \
185 O  d% q, n" y
19- u0 R+ X( P  g6 [/ F8 c
20
; J. K7 V7 ?1 D% x% x1 Z21
( e6 _3 O  W1 X/ F  C; k, [# F22. l6 V4 G1 e* e  x0 x1 Z
231 `" _9 V& Y5 x3 }& s
24
6 Y- ?# A- c! b- C25
! [5 ^& `3 _, s- z0 }( V( ~26
0 c0 N# A9 L5 h0 S0 [3 q& e7 J8 d27
. b! \2 _$ k2 {9 S288 o9 [. B. T/ V
297 g2 @/ Q+ C# j. ^
309 M; P- X7 a/ J4 @
31
6 q# Z' |/ O, _4 M" |4 Y4 f32
% U7 w; d' l% [1 a$ i$ S0 [33
  m7 A- B; d" c5 S34
& O3 O: D1 N3 s359 C, E$ D  T( ]+ B% y
360 a2 \  k# [7 ?& q4 R( ]  l
372 q. {! F0 ]; G! a" B% k! E0 W
38% @; m& t+ s$ j. x
39/ N0 H0 f+ {5 m4 V
40! ?5 D. g) S' i+ y8 `/ d
41
! X& v/ A/ A( H" W3 D- l429 W' w6 P% A, x8 D; a5 q
43. u6 P' A' {* l: D: N, I
44/ u1 ]. O: G3 @
451 L3 i3 R) J+ I) B
46% M2 W% q$ z' H5 S4 g  B1 z; c
470 q/ i, v% u) E. I. J! {/ l/ R
48
3 V- S- ?/ [6 t$ A6 b49
" D+ N- M9 Z7 `* |9 g( p50$ p3 R$ m/ t% I
51
2 C  M% y5 G+ |" H52
2 D  r9 _! a  Q- H  \53, p( s" I% U9 I3 T0 P" v
54- Z- |4 g* f9 y- v% n. n3 C
55
- g7 f# \+ Y7 g# n6 x6 m' [8 ^" I565 K2 b. G6 E& }" {6 A
57
2 y8 }( V" A* M9 y4 S58
: _1 b: ~, j! O: W$ u/ S597 n0 A1 e) d! |9 }& D' w8 C4 Y6 U
602 ~5 h1 |; [5 T3 C1 F0 Z
61/ t6 J# d: U' E5 O, |5 V
62
% k* ?; b, h4 K, Z9 ~63
# M0 B6 \( ^# K+ N4 d" ~. u64
% u. P4 }1 U# k1 `/ A( R2 ^65; {2 c/ M" y- }: h
66
" y+ d, z" X! {. ?" M67
1 j) v, b: W! v& o4 ?4 F. S+ k68: n$ h3 B/ o* C; k3 }& H
69
: k( n# w- l0 P6 }/ o! |' n  ~3 ?0 }70. {3 K" n; R, C+ y4 O
71+ ?( i* @5 |9 O
72
. P. T. g$ E) W# i73
# n' Q& n/ e  m( Q3 V. N74
6 Y, Q) R" k6 R" z: L" C+ h. u75
8 ~7 _: c6 F# J1 C$ d76
: O% k% t' a3 t2 K! P. ^: s7 c* ]: W77
! H7 t  a8 h+ U78
8 J# V9 g+ n' r& m. k  l7 z79
0 A6 d3 Q3 {3 r( d1 ~4 D) e. ^80
8 A  b; @. Z; T( [3 {. x: y81
: H8 `+ S0 y+ a; Z- C; M82
. l) f# O! e; @& g1 x83
* _3 m6 Z' M; y$ u84' \; \0 U5 A3 l0 k' K
85
+ \  P. P6 q1 H1 X, a) v! X2 C86# ^' Y) i& L6 |( `% N6 `6 P& Y
87
* B, j+ P7 w; I: _88
) }. x2 _, k- u7 Q. R3 N" X; b. q89# c  u# x  H2 b" f* h9 l  q
90& D# S$ V: F! i$ [
91% E7 Y' D# a9 a6 ?2 k
92
# }& Z& N. U4 M) a& L, h8 E8 x. x93) d/ H3 `- v5 w! P/ Z
947 D1 e& |; P7 x1 J$ u, h
95
6 T' q0 l- \( u  b% j! @% ?9 B& s96
- u& a& @: o& A4 p$ a979 ^2 [1 c& o: }8 a" m7 I
98
" `+ o. l6 a5 N* ^8 D% g3 D99
7 h* Q! J( D2 G3 s1009 l+ x4 a8 f  {0 j% Q0 b+ [2 D
101# C$ S$ ?9 r- X) Y, h/ J. R
102/ O8 C9 G  h. f$ J4 C: S5 A9 w* B4 }
103
; o$ v) l- D6 o: X1 ]* @（高斯核函数）% b3 q; H5 h7 a9 G- g" T5 N: ^- p( V

4 ?9 i9 ]; N0 J0 i/ J9 V
3 b0 }5 q2 `) z（K邻近法）
" y8 s# w% K  |) m
  Y$ h$ G4 B- v; M! S( `- T+ D/ d4 N, N2 T
四：谱聚类算法优缺点
  c. P) u. M( D1 t, c7 B（1）优点4 M# A! b5 z4 H: ^4 i% ~
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效
) `4 a- n" \% i: d" D( o' d使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法  j( y0 l( ^# G! _0 T3 A
谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解& c; b6 Y, B1 J% i
（2）缺点
" [6 g4 l# ^. ^/ \* J# j" o如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好8 o4 y  |* h. K
聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同( H: ^' s) O  d. W; N" ], o
————————————————9 j' `+ X9 g% z' m/ b
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
& h' S" |9 n" E原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494. L# ], q4 V4 E

9 Q' a7 _4 _) }- E; O: A# H( h& R' D& W+ Y% {0 L/ f' d% c/ Z% }. [4 z