查看: 2950|回复: 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])
$ S$ ~3 g$ |, f0 a% O- S return dist_matrix5 [# ]" H& S0 c/ m

" [% Q+ |2 m9 mdef get_W(data, k):7 x& g& W$ ~6 p& a$ s# b
# 获取邻接矩阵（K邻近法）# j/ K3 G  }4 H2 X
n = len(data)
2 w4 U2 O1 ^  Z3 g1 u: s dist_matrix = get_dist_matrix(data)- N6 D$ I: v' j8 Q. G
W = np.zeros((n, n))
: M7 y6 B) r+ A, l6 \" M9 r for idx, item in enumerate(dist_matrix):
+ Y3 T4 k9 {4 Q' l/ D) Z, ]7 {& h( U       idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表. U1 ]0 z4 m- ^5 U- N
      W[idx][idx_array[1:k+1]] = 1- h5 \- R5 X0 t* U% J& m2 w) l
transpW =np.transpose(W)
# w! I, I, i4 @8 _( ?# e$ ] return (W+transpW)/2& x! ^) z; ]6 C& v; [" X

3 Z1 ^- k( T0 g( z  i$ r; p( odef spectral_clustering(data_set, k):7 R6 g( Y( E! v- h( l% U$ l
# 利用相似矩阵S得到邻接矩阵W
4 i  E& V+ x0 U. r8 q) ~: U W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
* I; z8 U1 i; e) |- U4 T# Y: x( | #  W = get_W(data_set, k)  # K邻近法' h9 b& g! D" o" y

* ^" _5 l, I6 \ # 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）. J. D$ m$ V7 O; N
D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))
+ S$ h% g/ c2 L* h1 O, L8 G
. z" f+ n6 N6 {2 z # 计算拉普拉斯矩阵L=D-W
  X* t0 ?9 R8 A; n8 e2 | # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
  @1 P. W3 ~& y. ^1 d% D L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)  [, O" t+ C' d! H. }, Z
4 G8 U% |0 C0 w  z0 f0 @2 }
# 得到特征值和特征向量) _* X2 {0 c! b0 d# y8 w+ k
eigvals, eigvecs = np.linalg.eig(L)
' @9 @; V7 i& U! g5 X
, J8 u- ?' u7 w' z8 P* j& | # 找到前k个最小的特征值（索引）
& p# Z& E0 Y' c; s k_smallest_eigvals_index = np.argsort(eigvals)[:k]
! \! Y) F. F. I9 \" W4 {+ |
7 \0 Q: ]: V6 H8 ` # 取出这k小特征值对应的特征向量，并正则化
$ l8 `8 l5 J& f# C k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])# k' V5 ^- r3 e0 T+ M- z$ w
5 O! m! {/ ?1 O8 |/ t! p
# 使用K_Means聚类) r* s3 J! r: I4 J
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)) a" {" c9 M3 ?

8 q7 t& q  o& f9 `+ k% ?0 x4 w
% ~) P8 m& X( u' G  _- ~raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)0 q& V. ?# @. ^; L, w
raw_data.columns = ['X', 'Y']
; x) c: D0 s' @/ h4 N0 Z0 Tx_axis = 'X'
2 h! W8 r/ B- M. X1 s# Ty_axis = 'Y'+ ^! h) \$ }& v0 n. p

5 A7 t2 u5 O* y4 p. zexamples_num = raw_data.shape[0]
3 T+ g0 m% N' i8 I9 w# `train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)
5 q( Z1 O. }% A5 B% G
6 Z% w- k; [4 j( E! u4 V
3 S4 u: f3 a8 u3 z' g8 nmin_vals = train_data.min(0)8 K3 M6 \. B( j+ u" Q- j& @
max_vals = train_data.max(0)
! s( ?$ P% D5 _7 V" E- oranges = max_vals - min_vals
8 x! ~2 a* u+ j! Q/ I* R( vnormal_data = np.zeros(np.shape(train_data))
; j/ P: ~9 Y- @  z, |1 ]5 ?nums = train_data.shape[0]1 r8 B0 k, q4 Z" ?/ g+ p6 V
normal_data = train_data - np.tile(min_vals, (nums, 1))
) S9 J. u8 O. N9 V$ Q8 r' R0 gnormal_data = normal_data / np.tile(ranges, (nums, 1))* L% `$ p: o& ?/ }% g

5 H; U2 ?& f# E4 f0 Rlabels = spectral_clustering(normal_data, 2)
& ]! s% a1 j0 P. C9 s
9 ]4 W8 Z* A2 c& s  _) x8 F8 b+ A# 原数据
2 b3 s# b- j7 }- X; D2 \, z9 Xfig, (ax0, ax1) = plt.subplots(ncols=2)
& R" Q2 N" [5 v3 M$ v6 h+ Qax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')" z9 x5 i( t1 X! p9 W( b+ J" [
ax0.set_title('raw data')
2 N  w/ _8 Q+ P# u  T8 i. e# 谱聚类结果
; }& \% z6 g  X- rax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)
) }1 [# L5 b% t  m' I. {" w5 Aax1.set_title('Spectral Clustering')
- O3 k! z2 t% F" O9 N
$ l' L* V6 k: T' p* oplt.show()
2 u9 b7 a, A: X5 N) r* u% ~  l4 }' I# p( S  }; f
1
  G# m. z- [4 @# s% L20 n; |# r1 C1 f2 x8 J
3$ o" J& k1 t4 }- k: m! s8 A
4( S& v$ M( j& ^, r: b7 w, j
51 O# c1 o3 v  c4 S. D
6
9 I0 A7 j! V7 N1 S7
# U' L; L( ^6 s% F( W0 A) M86 p" _7 E) K; Y0 _: W$ C7 v  g2 o8 Q
9' L1 d# y' M) j# p
10- x5 A9 G! e* {, V  y8 @, ~
11, s: L) o$ g/ J5 L: L, N
12& C/ L, w4 h0 {! l' E2 V3 }
13
0 R9 p, G$ M, m& {9 {149 p, u/ l- ~9 w
15
! k- B& Q5 a* C1 J, ~- X0 Z6 f16
5 _: h' y4 R+ T& J. y17
$ L) N* S" K7 C& @18
# y6 o4 }5 @7 i0 v% p7 Q1 n19
0 D8 M# d6 Q& D& Q5 ?3 j2 p20# p5 f6 \8 x8 I2 b
216 g0 W" g( q3 A- d4 k
22- j3 X+ t& Y3 V/ \
23
6 u) B2 A1 n% p2 r" _' B- t24
2 r" _6 w, k, C! t25
7 \7 \3 I# H) `$ H5 X. |3 N26
" ^- y/ J2 t! {8 O, E27; P' m& H! D8 A( ?4 h$ s* P7 G& z
28
, |) {' l, M3 `7 z) Q29& ^6 {, U. a" J0 f' y4 E) v
30
( I+ J9 o7 H  h  _0 r4 q* `3 @315 L7 L5 L5 r& j) L4 b, J
32
: k& B: h/ }7 ~. I0 U33
9 c' ]/ G4 m' L4 _/ P* D) T34
% g- h9 S6 z, C35
9 W" J" k9 u) B! T36& |+ w4 L2 F$ U, e' Z0 e# b
37
. J% x5 N1 c, h7 g' K' P; m38' A' O$ [0 h9 w. r& ?; s7 M
39
6 i0 S4 m& C- C; G* V2 @40
6 b) \& Y" B1 F5 d+ W41
: y. y/ V: B# ~1 s421 U( N1 w  E" U4 C6 D$ g7 o
43
1 ?- Q5 i5 I" L  x6 T44
; H- m" h* I! k45
: Z0 `! y  D/ C46" W" O5 o# d4 c
47" D* d% W! H% Y. r
48
4 Y# D- I+ m& e5 C4 }. f( b49
% ^& E3 c9 c/ G; _503 |8 m! W* M, m
51! z4 r  L; v. J* H, q# d! g6 J; x
52. n; D/ g( \4 e: @
53
8 B' r4 M+ [) l4 O54. l/ p; [! |$ f
555 C1 a5 h5 S6 g9 K  ?
56$ z: N0 n0 L+ C' G( y9 {
57
. @4 t* I% v" p) B58% ?, \0 @7 C& j7 N) Q7 i* b
59
& M' x( w6 m7 a! O/ [& |, X4 V$ P60
% q( h5 y$ L( C5 C; B, C618 f, r9 K$ a; o! I/ O7 X
62
) f$ Y7 d7 }! X63
7 x* y) O8 C) V6 B640 S# R- ~# Z4 I4 ]" E
655 R) g( g$ ]3 |% s5 n6 S/ ]2 W
666 b+ p; V3 U" Q- y! H1 M) N" @
67
6 `4 q6 |7 ~! |8 P687 H# h, ]! Q2 s( ^/ c; w0 s
69
. R+ e4 j% X; W( b70& A$ p% O& Q5 U) C( o. m! A' }3 M
71" T4 {6 ^* b% z5 Q! U3 R
72
# g# n( B. |$ J$ d73
6 I: E/ x. q7 ^1 L/ ^3 z74% @/ F' ]$ D# }: E. F
75
+ X5 e. Z( S8 K) Z! }8 M1 Y" f3 T, P76* [8 S, _) g5 h0 }  [3 B" S
77, S) ^$ \, @, q! q0 R( E7 h
789 j* w! `9 s. c: l4 U& q0 Z
79
* }5 K, O2 e2 Z) P" {80
. F% t1 |1 _% f; |% V' r, u1 {81
* N: p* b4 l" L; n) ~( L4 J! S82( ~( W+ b  [0 g3 P
83
& q4 a; \* A6 k5 O, `84# R; e- |4 p1 O% H2 R! j
85
6 x( }5 c4 T+ ~7 `86
3 E) I2 Y- f; m# R3 Q9 O. g8 P+ C87
! T- ?3 ^8 R0 {88
8 P; H* I7 s0 x2 G2 U- d89  r! z# h  W; \- S; E7 U
90$ V/ w% J$ h0 l6 j
91, O6 D( G. L: f  g" U/ b
92* E( x: ^9 [( |% l5 |$ Y& G( y* z! U
93
1 d/ Q+ P7 Y! d2 f2 u94
" \3 n( G; v/ i: R: r& w, P9 d95
$ N3 a9 H4 s( l2 s96  I/ _1 }( P. z% a
978 R" n5 D2 P" |" u. @; C
985 z" ^8 _! I2 N7 l  a( I, z, j1 ^
99
2 I: ^3 }/ ?7 |& G" d" G1 W! I100# g$ S% O3 Q5 H6 }
101
4 i( _4 }- c, k8 Y  M2 P/ M102
1 G8 e4 _# S5 J& @: T103
8 [, p0 _5 u! Q6 b1 {, }（高斯核函数）( J3 h) v5 G  q  {$ e4 R0 {4 o) K9 o
; Q" j8 Q4 D! i) C8 @9 N" @* y
" l% x. T7 u3 y5 ]
（K邻近法）
1 P# z9 v+ [3 _1 g
$ Z" p* @) L; T9 G6 S( H) T* Q7 k5 V1 ]8 |
四：谱聚类算法优缺点4 \/ A5 c4 h4 h1 |- e
（1）优点
( V# B+ b: y( Y. c. X4 `# j- z谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效
, g& U) ]6 P( |, N1 c使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法
2 b5 D6 Z7 m4 {1 p8 |( y% @谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解: h/ r$ j4 \! c, D
（2）缺点
. G  L" ~( C8 c如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好) T$ w0 a8 d- I% S1 s' z6 T
聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同
$ e& R, m6 r, b8 ?3 ]————————————————3 e7 J* ~2 l! ^0 q
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。+ ~8 s0 k& d6 J( r( c
原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494
" @' _% |4 I, Y1 V
' j( j5 x4 @2 I0 a. j0 v2 F7 W1 z$ `) k' n