查看: 2987|回复: 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])
9 F) ?) b5 r5 B4 L$ _  T% u' O return dist_matrix# U9 P  D* G& j& }0 y' c

4 h! c0 A9 }: [6 adef get_W(data, k):* Q$ R2 ~6 Y( k7 H2 I8 Y
# 获取邻接矩阵（K邻近法）) C$ ^3 Q# T$ G/ L
n = len(data)
8 F. }+ N3 A' C9 J2 Q# l% P" p- W& h! U dist_matrix = get_dist_matrix(data)  {0 w) f* E5 K8 ]1 f
W = np.zeros((n, n))2 S- C( C8 A+ _
for idx, item in enumerate(dist_matrix):2 D2 h5 J  a1 m6 E# |+ A" N& ?
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表2 b2 v- C. k. Z: ~) [5 d6 W6 R
      W[idx][idx_array[1:k+1]] = 1
+ }7 o  W- b$ E' o+ } transpW =np.transpose(W)
9 h0 W+ H& }. ]. g return (W+transpW)/22 d: D2 G! w& K4 l3 D

% r7 U) |$ }, ^  i# tdef spectral_clustering(data_set, k):; l& v0 g8 G. }# r* Z$ H0 b# T( N$ o  j
# 利用相似矩阵S得到邻接矩阵W
  u' T6 P) r. O6 D# J) p W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）/ T! Q( K9 F( X$ w1 B. u! J
#  W = get_W(data_set, k)  # K邻近法
1 E7 J' _0 t5 N5 n7 T1 f2 L
9 V$ K$ r: `2 j7 ?# d # 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）
) l% [% R/ [5 }2 g3 i D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))
& o; @$ M1 g' W/ `
0 e; H  @4 D, m # 计算拉普拉斯矩阵L=D-W& M. `/ ]) S+ q1 V0 B
# 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
9 z6 D( m, w! _! [, m$ ^ L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)2 W$ M! _! w& Q- y: \

4 c7 Q( m( n0 O) u: z # 得到特征值和特征向量# B3 ^6 ?. {4 E4 u8 {  x
eigvals, eigvecs = np.linalg.eig(L)) D# E* i& O0 j* h: {6 V
# Z! @' E# ]: j- A
# 找到前k个最小的特征值（索引）; q) n3 K8 O0 Y% y; n8 W7 A
k_smallest_eigvals_index = np.argsort(eigvals)[:k]
, C4 v* z% W$ ]" G/ n( q& m
. b  I$ C% A% |) e5 C6 ? # 取出这k小特征值对应的特征向量，并正则化4 W# L1 f  _5 P9 \: J1 k
k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])
: Z% ^4 q# T0 \( P5 m1 y
: U8 U, A2 }5 u" J1 S3 x9 ? # 使用K_Means聚类/ {9 t3 ^9 A5 M: @
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)/ J6 J4 g& J, H( S' b# n+ e$ {" c; l
+ x0 W- z6 ~: \2 i9 ?
" P; p' E! V  [% S. s2 c
raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)' X, j; M3 H3 f( C; M
raw_data.columns = ['X', 'Y']
8 h$ A/ h) q- m! px_axis = 'X'
- e' r: \6 y6 e" f# {+ @9 Ty_axis = 'Y'
7 |" e& D/ G, ^- H+ U1 v
+ T0 l  W, a" b2 N' V4 W( Zexamples_num = raw_data.shape[0]9 P3 @9 _' v1 L5 I2 z' V
train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)
) S" |8 t5 Q: p/ |7 H( A: z/ i
: F  s& \* Y- \( A
! j/ ]( v* ~2 ]0 s# c# K8 l* j/ dmin_vals = train_data.min(0)' |6 N2 {* Y9 d; Y* O4 z0 N
max_vals = train_data.max(0)
6 f* }) ]1 w  D1 Cranges = max_vals - min_vals
6 [7 L3 u% [* T3 [1 Gnormal_data = np.zeros(np.shape(train_data))9 F8 t9 R  _& D0 i" K" L4 g
nums = train_data.shape[0]; H7 f, N3 u% n2 k; P, T* h9 a
normal_data = train_data - np.tile(min_vals, (nums, 1))
( |8 r. X+ H# T% l* C# ~& inormal_data = normal_data / np.tile(ranges, (nums, 1))  S5 L; V: W3 o7 G1 H- Z

" @$ x. O  e& z% G# u* Olabels = spectral_clustering(normal_data, 2)
: p) E% y" u! W9 D
( |" b; t/ I. D3 i! w/ G# 原数据1 D* S! B# k1 S; |7 E0 i. P
fig, (ax0, ax1) = plt.subplots(ncols=2)% G% x) m, r- I' I
ax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')% p* P) W. }1 U; a$ X4 M; p
ax0.set_title('raw data')
) V; F, Z- ~( A, w$ m% x) S# 谱聚类结果: a2 {; d4 i8 V# Z" M* |+ K! ?
ax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)0 w) q7 M. y, N$ P) \3 Z+ E$ [
ax1.set_title('Spectral Clustering')% C3 X8 ?- K$ F: T
$ ~; A9 `1 p# W7 Y' ?
plt.show()
: {" y' I; l* L. e1 }& Z5 \1 U* _  ^- {. f4 B
1
. t& q; D" B* I( O4 S4 t6 G2
/ `! J; L- e, v2 j. E! b  Z3/ Z8 y+ a7 T  x
41 W8 e3 `2 r: u& a; h: U- P; [
5
: l7 p& N3 q" B8 l& j7 h, x' N0 p* ]6, x6 N* T+ k8 ~; _& J+ E& O% I+ x
7
6 d- z2 }* R# [* t8/ Y7 R+ W; U* [4 J' d6 G- P% N
97 n' U% u" D4 z1 L3 }2 z; x
104 c, T* n- f5 ~# E4 F
11
; E1 I; G% p- c" J5 X12% P* Q3 Q* i. i1 Q
13
+ j/ V, T" m8 M14; W1 j2 G  i; a4 C; o
155 x" j# g1 |, {( t
16: X' K/ ~" P1 @; i( L
17
! \- z0 @0 w* j0 x18# i1 J" D& ~# j6 C
19
3 r5 {, x! u7 u3 P- I+ [208 \# }7 N( N' r9 {7 ^
21
: E. q4 P; m: {& s, p  V229 A$ O6 \" l, i  o7 C, S
23
5 c+ O, }1 Z6 E! K& a0 X24$ b# N% Z6 b; m  {
25
) C" ]! R) _6 O  N8 i26
. \1 K1 `, w- r& \' a27
& K1 {7 G" C$ P& P, \! O# Y4 Z28
4 U; F  H3 A5 L: |/ @0 b3 T2 K29
+ R( J. k$ U9 K. b306 V2 W3 v3 a2 N
31
% u& C) j: ~4 g6 j3 p) N% G328 n- @. y' y2 O4 b$ n
336 V  e1 L3 Y+ [: ^& b  i9 m
34
& v: e8 B: @6 T9 r5 R  g35
4 P% v3 u: L* [. e364 Y1 ?/ Z3 F, q# d5 v8 Z4 _) D8 m8 Q5 G& x& ]
37
& S% V9 r0 Z7 h* J; ?) D4 f) t  L38
, ]" p: |8 Q. P' Y39
; V6 p, o( Y: k0 B40. E1 |0 U7 t. B
41
# Q3 s& E( N) e" r8 p6 U/ R0 i42
8 U6 W6 l$ r4 k. U43
3 j! k& h% O4 g, B6 |# D! Y443 q3 @7 j+ \6 |
45
& f4 |: q9 w: I( `46( L/ v0 X6 C# M* @. |; W- H4 h
47- U6 a" Z$ h5 N7 G' r" R7 F
481 f' C. p, P% d4 g. \( R5 f9 r# {
49
4 ~. M' ~# J& {! P) Y% ~50
( a6 c5 Z( ?/ I" I3 n6 L# g51
$ Q5 X' ]$ Z/ z3 {. ~527 @% J0 r8 I- j" M/ c' n
53
2 a, N5 `- F. v7 C. e! `$ @1 r54
: ^  z- Y$ d4 [* O8 p: m551 N' }& B1 u' H* u
56
6 B2 d* I6 o9 p4 N% S0 a. D57( H7 h9 p4 v, T# F8 R
58
, ]3 S( `( @7 g+ N0 X59- g- U1 x8 x1 ?) d8 j
60
# X1 r9 C! {  _8 G, S- c5 _; |61
% ~8 P8 J7 A5 S- b$ ^4 i. p625 w, S" s3 ~( Q/ @# a
63
6 m/ v$ p" O: I642 K  [) J! h/ L2 o& G
656 R6 K! k" }6 [- g4 T$ U
66
2 U( X" U' {& ?9 i5 t0 L67
/ j9 y9 P+ h  ?8 u! L68
7 v$ R6 A& m8 {$ f4 e0 Z9 p695 G, L3 \8 ~  _( _( {
70
8 o- G" E! x! a/ z0 L" g- b712 V4 R% _: r0 X5 {- c0 W" k, u: q7 U
72+ a( v6 N( V( v
73; y8 |: z! R& i) O
74
4 F) H2 K2 C  b4 J; o: B# A75
+ a* Z- H( f. @: p1 u' H8 a76
4 {6 g+ y6 S: s7 y# r" E6 `775 H- t3 a: W$ v+ s/ |
78
% e/ P, p3 L3 r/ E79* m2 r. F: z; p- ~& g7 K
80
; t0 c( U' ^+ `# h+ d1 P. s81
9 T8 l8 n1 B" \8 g# s4 _& A821 [$ b. q# k6 k: ]/ N& I
83& D/ ^2 @( `% Y5 ^  K6 C; O/ f: h
84. w3 b: e9 [% p, m0 }1 b
855 S7 N) d" P6 ]0 y! t- J
86$ V% ?; ?6 k/ t8 F6 ~( @
87( t1 j7 m! V3 L2 }& |
88
: \0 `$ p5 A! J1 w. }! r# D9 _2 u89* B3 |$ {/ }2 ^% d2 X
902 ?5 y0 c; Q$ e8 `, e' _
91
6 k" m2 w* k- s# l923 G* k( L3 D6 L$ J
937 j- M& X2 N8 o6 }
94" f% X% o9 }( e1 f* x
95$ ~4 g) S7 J$ ]9 W: U2 g& n
96
" {) G: Z7 r# O4 Y' O976 j3 m* j# X- D- m' _+ I
98
! `/ x5 a  O4 c  d& m99% W, G) B, h* E5 K* o2 |
100. z0 Y7 L! D" d+ |# d! s
101
; ]7 \8 j% ?- G  \+ W" T; L$ A1026 K, w' o5 U( E7 w7 v
103
. }3 g& @2 s, q& E6 y（高斯核函数）4 b$ [3 E% B6 K$ H3 @

; O% L2 Q2 s0 W! R
) r% R0 z( Y; F# G* S; y" f（K邻近法）
$ s' s( g- P# L1 u% b3 m; E7 ~% P1 h4 l$ I( T

4 f, \% O% G8 ]! e- d3 z四：谱聚类算法优缺点
# U) Y% h. N" w（1）优点* N( R! z: u! U5 B( h3 _7 {  @7 k
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效4 X+ s  R' b+ b  K5 G
使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法
5 f) i9 a; @/ r: X2 U# I谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解2 N9 O; a0 d: y1 |# g! S  |2 E% ?4 t
（2）缺点
0 d" U+ q, p/ j6 {; O如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
) u2 }* d' G3 m. |/ e聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同
' A4 z$ c7 b- q1 D8 i2 {————————————————- ]5 h" B+ Z) x1 m3 }
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。; y7 d2 v! Z# ]; [; C2 x
原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494/ w  f) p- R( K. O0 [! v4 ~
4 G2 C) ]6 T4 e3 y9 E$ Q5 G- }  J6 W: M7 E
, P4 O3 e8 l$ g& {( Q+ q$ U' \- t