查看: 2999|回复: 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 M% ~, ~; P' R! z* r2 G return dist_matrix
+ `/ v8 V3 @3 {# b; W; e9 Q8 }6 L3 W9 i$ H2 U; X& W
def get_W(data, k):
6 m5 T$ T1 \/ n1 y # 获取邻接矩阵（K邻近法）
4 ^7 O9 F: A6 `  _+ K  g  J7 f n = len(data)2 L8 E# V2 x9 l; D* a' s% W
dist_matrix = get_dist_matrix(data)4 K/ C6 Z: ^; y) O: w' y
W = np.zeros((n, n))
& h+ B, ~) F, w* |: P/ a; }! y for idx, item in enumerate(dist_matrix):5 s! W. z% A! I# T
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表  B' E# u  P, a1 V1 }
      W[idx][idx_array[1:k+1]] = 1
* d8 ?' z+ g2 S$ P transpW =np.transpose(W)3 W- p# z: i; j8 K- l
return (W+transpW)/2+ F! a, M" \. \9 [- E' y
6 E7 h4 z( C4 E3 Y
def spectral_clustering(data_set, k):
2 t  q% A4 b# o  ? # 利用相似矩阵S得到邻接矩阵W
8 C8 I( C( ^  i$ H  {6 ^ W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
! X6 w* L  \9 E( q9 J; R9 d #  W = get_W(data_set, k)  # K邻近法. A7 Z5 Y  j! c  E0 K) C

- d$ p  W" h2 W% u+ b, G' I # 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）
! W% L% ^) P( K  |& u2 `' t  ~ D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))/ c4 {4 G: a+ \- _2 F% p
4 q8 e( ]9 T1 T
# 计算拉普拉斯矩阵L=D-W
6 Y1 e0 \' M8 c" D  J6 F # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv, E( v/ x6 g) r
L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)# U6 S5 F$ ^! C* J

0 o$ [5 h/ X% J1 O9 m # 得到特征值和特征向量
( \+ X. K2 i6 f3 s eigvals, eigvecs = np.linalg.eig(L)9 X  [9 s2 W3 A' h; c
9 S; @! o% H& k* x: z( B4 B
# 找到前k个最小的特征值（索引）; g. |6 \7 u* v5 }
k_smallest_eigvals_index = np.argsort(eigvals)[:k]7 `; y2 j; v6 o# U
+ @; {) P  g- G& x8 \
# 取出这k小特征值对应的特征向量，并正则化
% e" ~, E: F6 m* g+ p6 C k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])
$ c. A# |# Z4 r* U  S* \% h: i  p" o; x7 S9 U( h
# 使用K_Means聚类
3 n. A" s! h/ B2 Y  T6 d return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)- w" u: H) t+ a# |3 o( r' \
5 B6 Z6 n- k( r
. g" A0 @0 A( q7 K# o0 w& }* u
raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)) F8 R& R7 S( M/ }
raw_data.columns = ['X', 'Y']
% e" a- K, y- x& @9 v( hx_axis = 'X'8 |1 ~9 |9 J, n- |5 o
y_axis = 'Y'' E$ Z& i1 o' y: e& C4 d, V' f

! o$ ^& s! F7 k8 D$ F- Eexamples_num = raw_data.shape[0]
  o* z3 Z3 q: D6 X  ?- rtrain_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)! }, ~( `9 U/ J9 i, n+ _3 }3 S' [
# c& V; p- Z" Y7 y1 L! b% G) K

7 Z7 ^" p: l$ ~! i) ]8 k- Emin_vals = train_data.min(0)5 X* U; X  @3 w/ q0 i1 d
max_vals = train_data.max(0)* |1 L" e/ a* G) u. e
ranges = max_vals - min_vals8 ?' r7 Y- j6 A; d
normal_data = np.zeros(np.shape(train_data))1 N/ @& g. J, L4 }+ A" Q
nums = train_data.shape[0]" \4 `) ^1 n9 D5 p$ Q; I- ]. l
normal_data = train_data - np.tile(min_vals, (nums, 1))
2 M5 E2 f6 F, Dnormal_data = normal_data / np.tile(ranges, (nums, 1))
+ n/ c8 [, m' I: N) R3 `; Q
, H8 o& l& ?8 X; _* Slabels = spectral_clustering(normal_data, 2)
3 r$ P+ \* d5 [; g% V* Y3 d6 C, U. l& y/ {( i* C
# 原数据
6 z$ ^' {# }& A0 _$ Q; t( z" ufig, (ax0, ax1) = plt.subplots(ncols=2)
8 x; S! Z: H- @, j+ qax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')3 Z# R, C" k4 S7 E% {
ax0.set_title('raw data')
) K3 k* r- i  e+ j/ K6 P# 谱聚类结果
7 H' R) B7 c1 b0 e: d+ nax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)! N% [' T% b3 c3 f
ax1.set_title('Spectral Clustering')
0 u; v' X' N5 i+ [6 a+ R! b3 d0 W, o/ r  C0 u2 X- U- C
plt.show()
- t+ v6 I. s3 y' Q  Q2 Y$ A& }  x$ R7 V
10 Z: e/ ?& _1 p# }  E3 s7 P8 |, ]
2# v: Q- Z) N# o0 Q
34 R7 m) p5 v4 s) f6 F
4
- O, k3 u( C7 A+ u5$ G8 I, l! t; a1 k/ z* V
63 c- w, W. x0 m' Y4 H; K
7
) }6 a2 v: y$ ^/ P5 f1 f8
! U1 \8 e7 D! v) m& u9
/ O! W$ u7 |6 O$ ~8 |4 p10
' L' R3 F) [1 u# F  A7 j11
5 c& ~& R  d7 {& O2 F12
% F. O& j+ w( G9 ^13
" K& o7 u; ?# Z  q9 m" t# w14
' b+ n$ ]( u& D/ M, q( b9 m# F$ f158 x  Y# }4 a2 ], M- R
16
3 m# N# L9 [0 V9 P17
! y- o  v# H0 {+ G" s  ^8 k18) c0 D) i& i* m: D* ~
19
: L# @( x$ l3 p2 m20$ s: p1 q# o: k' r
21/ E! W% u8 D& F/ _0 E
224 H& S% p& c! K2 v3 X
23
4 S- n5 G1 W+ s24
" B1 f) A4 l3 G- [+ l, k25
$ ]" a! X0 w  A$ A26
& h4 P, |( c0 [7 D27: ~" j" Y, ~& D6 t
28% o* s% x; _( n0 d$ t3 \
296 W$ U$ m2 f8 ]
30
" T8 u: Y" M3 t5 r; H( T31
& z6 a8 J4 c5 A0 [+ a329 s3 f  h$ X5 H" }7 \/ B4 I
33
0 c. i# q3 c" d3 W9 `34
1 l  J7 X7 S" b0 X/ E6 B+ Z+ \2 A- a356 Y& A' T4 D, f/ C; o
36) H" Q9 d% q/ l  P6 I' v+ ]' j7 ]
37
5 Z6 N. V7 p' \- c38/ X7 l* D1 g- e
39. x, M" E" I. f2 E: j; z
40
! }! }( L9 Y( F. t( b9 y' m+ k410 [' ~* L7 |2 @& u. g
422 P) q' k. L; J( X4 N
43
  s- R; o/ K# D0 T: a6 f44
" p; y( t$ X* Y; r. Y. O5 s! Z4 ]45
- B4 N  [* _) q+ E# ^# Y46; V' K1 L, k5 Q% z! ^9 `5 S3 i
47
8 @# j7 s! ?: ^3 M8 M( g* k48( Z3 P, c8 F. i: C- X: v
496 z+ }5 C; V  C4 ^: x) U1 h' e
50
1 L. ?% Y$ u! n' s51  `3 n/ z) L0 k
52
3 B+ i7 I9 R" f. }0 V: H* E" g' e2 A, z53
* g  n& O+ P& m1 b9 t; ?: @7 L54
- C: |1 z5 A: }4 J( Z55
$ r5 T/ c8 }. x  D7 e565 M* Z( I$ X& k
57. }4 ^* O  B! n
58. s# |. x. y! i* @9 L+ ]! A, a
59
- \2 P) \6 E. g3 x1 z; {2 l( [608 r8 k+ B7 D) ^- @' ~. G6 W
61
1 p* L5 s+ W5 ]. B' {) ^7 Z62
4 N( W' m* W! i. ]" U1 g63; G8 I. r; [4 P# l( d4 L( D1 C
64
6 M% A9 F* l- A5 h; s- Q65
+ j1 G8 T6 z+ E8 e! c* g; [! Z% W666 I' `4 [& G$ Y' x1 R' {3 b6 ~% T
67
  s6 C; e+ d: n$ R; z68
- b% ?5 g0 z" r, J69
3 d2 ~9 K5 J9 X2 a, I, S, E70
) e! w" h. q0 v1 M717 g1 Y( n8 c* |7 \! n
72
0 C; n, o. c; V( t- N9 \73
/ d( y- q! D" O3 E" W) ?74
" A' U( J3 N$ r. o% {$ A3 A1 o0 }, N75
' K, H! Q  B8 w  e76
. N6 j( n1 T# p- E( e0 I77
$ V9 T" d- k* b6 J78) x% K, t  f) n9 H% T/ i
79; z! x. _! i- u$ {. f! v. F' E
80# U6 ~3 [3 ^1 D( N( g. M
81
: q6 d( \' q  k- j( V" c' f82
" S0 i  K7 @; I4 S5 t1 D' s83; ^7 \9 d2 a+ R; g
84
7 G$ _+ u3 D1 o4 a! U+ W$ }0 W- T85: G* Z% ?7 K% |
86; f# Z, x: c" \1 L  g! G2 q
87
/ K3 L% x% N) n. [885 s4 i$ I3 F/ ?: b8 q
890 i# ]" l* X$ q3 Q" M1 ^1 o9 E
90
9 ?/ g' o# `. H3 ~! u& o91
/ G6 [7 Z- g. n7 {- Z( u9 J92& ]3 C5 Y1 H4 B
933 I# |; ^  L) t* I0 \1 _
94
  m0 J; \/ k1 a0 U95
+ ~& j0 U; n0 E) X8 h" `& J96
. N2 e; S, x, l9 C) [8 J97
. `" n6 S' k& i: c: z989 K! w) c3 T8 l. O" e
99
+ j4 A( V3 z3 {( i100% s  V0 D3 P! d* \# ~1 ?
1019 W  W2 T4 F8 T
1023 E  a* l! n5 k# r. c2 H
103
  f: W* p) q! R3 |（高斯核函数）
( n, |3 U9 G4 D9 y, d
$ a2 U" x6 {! v# ^% D6 z' e' C/ f  y3 j# Z2 j2 y- Y
（K邻近法）
/ i6 |7 i8 X% H  B  p$ l
5 r; r9 k* J6 F
+ \. q* F0 a* J0 U$ R/ k# {四：谱聚类算法优缺点
( j/ `( I& k  B3 p* R5 e3 a（1）优点0 Z9 I! w% Q2 L, n7 s
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效
( U& j7 g' t- \" d使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法
) @/ }( }/ d) w4 X9 h谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解; \' W; ?4 p  T# O! c) w
（2）缺点
% N) m% V4 {: S如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好( _  C6 s" k8 d1 N4 K* q3 T0 W3 \) H
聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同5 X& b* I1 E+ W0 |! R5 ~
————————————————
/ f" Y1 G! ?1 c; Z4 W, N3 n) V* s1 |版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
9 O" A" @( b! j0 y) A4 D原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494' {9 ~7 l- e% @" C, m. b

. i9 M; T9 a, l8 W4 V" x8 _6 ~  ~/ f2 d; O