查看: 3038|回复: 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])
6 E+ S& B% a$ t# \7 _" G2 g return dist_matrix5 ]; t* G! D) k- x: d$ }9 V# \2 @; U

5 }; ^1 z4 g0 ^( e4 Y" T- O4 bdef get_W(data, k):
' N. R; r$ c& N8 P1 l # 获取邻接矩阵（K邻近法）
$ W+ @  q- u) E; p% V/ i+ @! _ n = len(data)
1 A  J5 \0 I9 ]7 D+ w dist_matrix = get_dist_matrix(data)) u8 l( n" S2 s! X8 o
W = np.zeros((n, n))
) h: H8 i( c$ N$ f. m) d for idx, item in enumerate(dist_matrix):
2 a8 i0 @2 W  M& v7 O       idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表! T) r( ~; t7 t) n: p- h' R
      W[idx][idx_array[1:k+1]] = 16 d. p7 y  l7 x* V* W
transpW =np.transpose(W)
5 y" J; F  `  _& z# _+ e0 n! R return (W+transpW)/2
9 V! S$ \7 }# _+ O& z, r8 N! X% g' E+ r0 w5 d
def spectral_clustering(data_set, k):9 O2 k6 X1 L* S7 B. X
# 利用相似矩阵S得到邻接矩阵W
+ U( b0 |% m7 b; e W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）! P5 j$ V+ f8 @
#  W = get_W(data_set, k)  # K邻近法8 F3 |3 a9 d' b9 ~. n
, V( a$ `* W. z) P2 D6 ~5 R
# 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）
$ S  n/ v' {6 L+ a# k# U D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))
$ D% t' c+ K/ P
: ^: S  |9 e+ e- P, ?, S( @# r0 [* J # 计算拉普拉斯矩阵L=D-W1 N: o" D9 h  U- r2 B( }9 E1 |: t/ g0 i+ m6 T
# 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
, n0 P. v! w6 j# J: i, M3 C L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv): R3 b- A% Q* f" `0 @

5 v! B& ]$ p; [8 p$ o# G6 w5 ?7 h # 得到特征值和特征向量' p) @: x/ d: H( Y5 F
eigvals, eigvecs = np.linalg.eig(L)& k% S* c9 H$ o9 p1 k

2 ~  G* C8 F$ { # 找到前k个最小的特征值（索引）% y8 {7 L! a# B& R
k_smallest_eigvals_index = np.argsort(eigvals)[:k]
  N- O; T1 l3 a, r9 _3 d0 h/ Z5 r
# 取出这k小特征值对应的特征向量，并正则化$ U( u: J. d* l/ J$ m
k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index]). R# r: ]1 u; F9 @0 T  y4 u

4 Q3 @0 |8 h; l2 W # 使用K_Means聚类5 x' [, y0 o  k
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)
$ I9 P0 j0 K/ A& }4 f5 q* |  \$ `
& \5 B9 R' {9 o5 W, o$ m5 F6 M, K  V* h
raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)+ K& ]' M8 V' I3 q: [; B3 B
raw_data.columns = ['X', 'Y']# R7 W2 x% z- t6 C8 m
x_axis = 'X'8 ^1 Q7 d6 u+ U! F4 T
y_axis = 'Y'/ A' w& q8 R. x5 E6 {
# ^1 D8 z& r# t: P9 W8 n# z
examples_num = raw_data.shape[0]
- C, q8 K4 }( ?4 Ltrain_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2), Z4 l; _$ u. l1 A: ^2 t6 }! ]; k
+ E: K, h3 w" M( _" N2 a
" O6 b/ x- g7 k. t# H
min_vals = train_data.min(0)+ O  V: k) w  q1 R3 i" A! m2 Q3 q
max_vals = train_data.max(0)
& H3 z. m* J( x& e: xranges = max_vals - min_vals$ k3 a/ n/ J; }" n  F
normal_data = np.zeros(np.shape(train_data))
. [/ r2 X+ ~) ~( l& t' b  ^* znums = train_data.shape[0]- H) n1 P, D3 o, b
normal_data = train_data - np.tile(min_vals, (nums, 1))
; C. j  x7 o6 q! Qnormal_data = normal_data / np.tile(ranges, (nums, 1))9 l! K8 z% X8 o, Q' k2 X; U6 \
9 t3 R& s* D: U" N3 C. v
labels = spectral_clustering(normal_data, 2)
" W  S- F; ~1 |% ~7 O3 Q8 `6 ?
: W# |4 K+ l' {& n: m+ f3 G# 原数据4 B) o  a; O- r! q, G- P) ~& H# J& t
fig, (ax0, ax1) = plt.subplots(ncols=2)
" L2 z& k# Z  ^  _# i$ F: Xax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black'); p( Z/ A0 Q7 X2 R/ Y) H: D
ax0.set_title('raw data')
9 l9 x/ N- [! ^# 谱聚类结果( n4 p; E  b& f3 Q% e9 j
ax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)
& K& V2 R% f1 U) @' G& G! Bax1.set_title('Spectral Clustering')- T* l+ q1 I1 R+ D* b& c

' {% O6 }5 t+ G4 G% hplt.show()
1 V- g) @: D0 B* K+ L* ]8 G
& G$ q1 T7 m! G* W* O, F1, D/ T& g0 i, R4 f" L8 U& Y
25 O4 z% C$ w7 l1 l
3' B3 K7 P( R7 u4 w( i6 R
4
0 X6 t5 ~  H" W) b5, f3 M" s+ l8 D5 i6 b) a
6
% k. `- C* X/ {& ^/ _7 J- L; \7
( g5 T( v$ F4 x" b81 p. R* @( z# m
9- U9 f$ \+ M5 A* |0 {3 u: e4 G
10
1 s! H  I& O, b+ Y- l2 @% o11
% N; e0 F' V. L0 ]12
( H1 |5 k) e4 y8 `% [0 Y13
4 L/ m6 |; D1 w# r14. `: A, r5 J7 V' k
15# Y3 F9 N  j+ j  n" B! Z* G
16
% D  R' n  ?9 R" y6 x- G- M3 U175 F3 g" F' _8 r
185 c# M  f/ j( y4 Y1 ]9 P
19
, h4 ^1 d1 H! E: M/ d( A201 {/ R1 I+ `2 M. u- Z, }
21& n8 I5 Q! C6 u6 _5 B8 u6 V" C' t
22: c" ]; _# a# ]( U0 |% E4 K
23
& U: w. F" [6 X5 G24
% C5 D: W# p" m6 M258 f' w' a: v5 ?1 L
26  `0 r& ]! T5 F2 ?0 d6 n* m
27
  B: s# U' K  T5 p9 s7 m28  e1 [5 i5 J6 ^% W! |- W+ F
290 p. Y$ y2 q6 s# \
30
+ [1 m) w8 [3 z7 C/ x/ N$ \( o31
+ ~2 y5 r2 k5 F' W" f: z322 N) k+ x' C( `1 [! ]' ~" P) v; z0 u
33
4 K( ~4 d+ z# e; F+ }34% i( _3 ?7 I7 o4 X: v
353 ~5 \4 c) |/ w& u8 x
36! o3 K5 P/ l+ V; P
37
7 x0 ?* [3 n3 O9 ~" ~38- R" ^) E/ G  i( C9 {" B( b8 K
39
* g; ?+ F# y0 _% O40( Q: S# T- `8 B- N
41
# @1 j; p4 {# ~8 S42
- U- h1 b7 P8 X. C7 N, g43
& K- l6 w/ M+ d$ z! g, S" P& E" n448 q$ b" L+ N, Q9 D0 q) [8 K8 J. V
45
; p4 y& G/ c" q9 ?7 C. r46
9 {# W. U3 Y8 k( s47
# r/ L' x, i0 D+ R48# b* i/ d" y  B  S+ |& t9 }
49! p  h+ i6 r$ P5 ]
50" D: y0 H! x1 C  `% I' `9 ]
51) i% q/ Q- x* i7 h! ?
52
6 W* j3 C9 E. s; R6 ?  ~. |537 |% n9 h8 h# ?# a8 \
545 ?; x8 n, v: A. z( x- O
55% g1 W3 y/ E/ Y% r
56) \8 R* T; N& j
57
" g7 ^# c2 h, p9 W58
1 [" _& y. r( u1 V9 X: X5 L, c59
0 h; h  {' D) A60$ o8 P0 [- `9 w1 s
61
) n5 v0 x! m7 X( P. }62
, D3 ^, s4 Y7 Y7 W6 ?! i63$ z. B4 v8 i4 H" o( r% W
64; U* S; z& {) J; O  v
65
- s" m- L0 D3 b5 d: o8 ~666 K7 }3 h/ Y  Y& \- v$ e
67
& S) ^% T, C! I0 g' i% E7 b+ q8 J# ?" H68
3 t& H( @' y3 c5 W! e- o69. {' e4 u- t2 y8 l% l
703 W  y7 H5 J; e
71
, l8 g! |. K, y8 a9 p72) d$ b' p) L. T" _3 ]8 P7 z
73( m  ~3 `6 f* t
74
) f+ v, N2 W+ g' f2 I: O9 L$ P75
' Y9 v) Y( X% H4 h  L767 {7 C1 ]& k; f  A
77) o4 L5 k, g( [9 x
78; C/ _7 n0 j0 H: k1 o- ?7 |
79, N2 W5 g1 i5 y, w
80  g2 F. m: q8 ]+ F1 k% E
815 f. m8 }' z5 f/ E+ m" ~
82, p" C' w2 V6 r% {9 n
832 a5 |0 R' \4 e; E5 J4 e
841 H) M/ I5 h+ Y$ \2 S( N* x
85! l# X! v+ c6 q- h4 z1 T; m
86
* `; J  B$ s2 {87* e% {3 k% L6 M0 E) j8 C
88
" d& ]  y" A% W: R89
3 z* j4 q2 {# C& c90
. ]* ~  z( t0 N% X' P91
& n8 n/ q- X; F% X! J! ~2 a; m92
& S' J2 I, Z& r$ l# A, ~93
6 @/ F0 W+ p7 D, D+ S: B94
& {- e/ j9 E7 u% a3 s4 w95
" [/ l2 m& ^: V7 l5 y$ j. R$ T+ G968 b: h7 t/ e" w5 v/ H
971 L/ K  \, g( a" k( g2 A, g) \3 d
98& f  p% |5 x( b# ]2 n1 K' ^1 o% Y& Z
99
" X; I" S4 R  f- e3 S0 }! K# F: I100* ]; p. T8 q& e; ?: E/ F
1013 t: k: c9 n- X
102
3 \( \6 @( _: X# k8 Q103
3 @/ t6 r) {  d/ u" @- Z3 K2 g6 ?（高斯核函数）( i) r5 I( t+ r* y# V# y
' e* n) R) U+ h; @  L

7 d3 }. J7 y0 i! p$ _2 s（K邻近法）
& \  M$ \" [. Q1 k
8 k! j4 ~3 h% T$ r" n% e* y. _" P! P0 h0 u  O
四：谱聚类算法优缺点# X, k: w1 l3 d7 @3 D/ g
（1）优点: I- N4 N/ c$ A6 P( ~6 N
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效/ a% {( B! K1 R' Z1 H4 ]& U( |8 A
使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法
" M5 F8 T' a  ?. u, s9 r谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解! I" F, F; {" b4 [2 ?1 O8 d: r
（2）缺点4 v8 D8 Z) i- i7 S5 L, i) j( S
如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好' O! }( A5 Y7 f( W
聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同
* N7 O6 n  ~8 y6 e: P+ q- W————————————————- O3 x. ~' [0 _- B
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
* U7 Z, Q. R7 T1 l原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494
6 v( D2 ?( E. O) h7 d: p4 q% E5 r$ {

3 S; o- R: }5 s& a! h9 ?