查看: 2947|回复: 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])
- E9 T! @* `9 p$ S return dist_matrix3 N$ d' u. Z/ k) x6 D

6 i8 `! Z4 d" O- f% u* X% y- |def get_W(data, k):" V; ~( n* }3 G1 c" @) G
# 获取邻接矩阵（K邻近法）8 F% W1 P: O3 H8 j& W% \0 T
n = len(data)
$ G  a+ L1 Y) d! O5 u, c dist_matrix = get_dist_matrix(data)
/ f& d: Y: |" s9 B W = np.zeros((n, n))0 j- Z0 ^9 H1 y# ]
for idx, item in enumerate(dist_matrix):. P# s% i1 [# z, Q. W$ p$ Y
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表
  r9 Z) Y* S- @. N) F' w( i' O# I2 R       W[idx][idx_array[1:k+1]] = 1: a' y0 o2 _) _. G
transpW =np.transpose(W)
& O$ {# f' V4 @  K4 I return (W+transpW)/2
8 x" h7 A- j& b3 F9 G, V; E3 y7 H; H4 R+ i6 ]
def spectral_clustering(data_set, k):
6 C, J2 s3 `& u* o# E  o # 利用相似矩阵S得到邻接矩阵W# q# ^% o( `& r
W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）! m5 Z  s- S- H! P+ w: g6 f' ]5 L7 M
#  W = get_W(data_set, k)  # K邻近法
' b2 W; N+ |$ p1 M" b. r
6 z8 `  }; S/ v # 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）
' k2 V% u4 I9 J! k, s- c2 B D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))
( w  J6 ]& Z1 _0 e3 s% G- v0 W
. T$ Q0 d( {$ Q7 N! h9 f # 计算拉普拉斯矩阵L=D-W
6 G% F) @1 _8 ^1 x# S8 d! H  q- ? # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
  Y, A' s) Y& L1 h L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)0 y/ g, A; B; _% q

" O4 q- t) H2 h # 得到特征值和特征向量
8 ~/ w! ?$ W0 I5 s eigvals, eigvecs = np.linalg.eig(L)9 s  B4 P  a2 e: N8 Q
/ u! d/ I- ^9 Q+ H3 _, s
# 找到前k个最小的特征值（索引）
& M/ o4 A, D; w# I8 i4 D: F2 q k_smallest_eigvals_index = np.argsort(eigvals)[:k]
. {8 N6 n- W$ F
3 H' b( r( h$ K0 T/ ]$ K4 k # 取出这k小特征值对应的特征向量，并正则化) C: ~- k3 v0 w. P2 n3 a+ K
k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])
# ]. @7 p# j8 v2 S8 i' A0 L
3 T  ?/ O3 f; }+ I2 _ # 使用K_Means聚类# X2 V5 j2 V' d/ a4 }+ ]7 B0 G$ P' G
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)( W$ i5 O% H! m0 R5 X
$ @: j# Q1 b" a' J2 {
" J0 R6 t  K/ P! i! h3 X$ Z
raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)
% H' r4 X* R, M3 d* z6 N3 X& _- ~raw_data.columns = ['X', 'Y']
0 E+ A( C" E, K) o+ o1 o0 lx_axis = 'X'
! l% U, O6 a* s6 Z* gy_axis = 'Y'
% f8 _5 A8 d4 M. R
& X/ W0 W, y+ _examples_num = raw_data.shape[0]9 d/ Q9 m: j% I
train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)' s1 j% J9 b: y+ x" k3 T9 Z
) {' h2 v6 S! ~' H$ k% K

" u! P& {4 S$ y3 T) y! R0 ~5 n! @min_vals = train_data.min(0)/ v3 U: U: ]( t. {: k& @" a/ o3 S
max_vals = train_data.max(0)
2 u6 \; }' V' J: Lranges = max_vals - min_vals
! F# \( C; \/ Wnormal_data = np.zeros(np.shape(train_data))& ]4 @2 f2 t  c( x* Z/ A
nums = train_data.shape[0]
0 F1 v5 C: X! C* {; }normal_data = train_data - np.tile(min_vals, (nums, 1))& L- U# j+ H+ K  _% ?  U
normal_data = normal_data / np.tile(ranges, (nums, 1))+ w; L( j; z: f

( ~! S: v5 _! Qlabels = spectral_clustering(normal_data, 2)
- U5 H2 U$ i% l- S1 w$ @- q. O; u
2 T8 }) w4 I5 a1 i2 Z) g* T# 原数据
/ s  T2 W1 x+ b* l! o* zfig, (ax0, ax1) = plt.subplots(ncols=2)1 |6 `7 K6 l& f' [# C4 u. o
ax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')
, T0 q. ~: |/ s/ Q$ z# q; ]* Lax0.set_title('raw data')
0 Y, a( o2 }# ?0 _- P' |* V' z( x! ^# 谱聚类结果: x% W# S' z! z+ b
ax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)
+ [, J: z8 W( O2 [: P6 oax1.set_title('Spectral Clustering')/ x$ N- p' b- ~

' _3 a% N% I; R: dplt.show()

( d3 i$ f$ q) G1
- v% `3 ?0 f$ C7 r  T" ]5 I( m  K2& P+ r% ~: `; ~" v; p
3
& k% W: v' O; Y+ [40 @' F" O. A1 u
5
# x: u$ M- ]* E  `7 s- ]$ w. u6# K% }- C& w2 q8 q
79 I. s  h5 B% G
85 q: H( d& U: J' w
9
6 Z6 l- @* T6 }* u3 H10
, v3 I& |, J2 Q9 K; ~& _: G6 y11- q' w+ P! m; r- M
12' s6 S0 ^# U% K2 r: R- I
136 W5 [0 t' F+ I. ?
14
- V5 d3 |  k0 J/ s7 g- }2 g0 o15$ s2 @  I4 M& _0 K7 }' I) h
16
% c) M2 X: s* {; x3 \17; H( `1 [) V. r
18
' }3 P; \' U0 G5 @9 q# H19; Y3 r3 |0 |0 ^
20$ X0 J7 g3 @. E4 K. A6 d
21- D  i* ]) V2 O# P
22& A  z7 {+ Y4 d9 n" i$ h* s) T
231 A$ w& f5 c# G' C' m. s
24& D4 X$ Y5 @0 Q! D
25! k5 v1 u& ~6 }" k% i. W7 X
26' y+ s3 f* b( j3 \, b3 l
27
# U6 Q5 G, \8 G5 H281 t, P- N' ?; d' }. z( m; h5 |
290 [+ t5 e: s6 L
30! a- e! q2 a1 [3 R: p1 V! p' [. I
31! I1 `9 R$ T* o4 v
32
! @' P1 J$ f) e6 P/ m333 K9 L, H/ P6 y+ `6 S) {
34
$ N3 p3 G  q  V( u( \35( R6 q! q+ z+ P! K. M5 t  f
36
1 U4 l; [$ L4 ]  M5 w! L37# i9 t9 ?4 M9 {8 l3 w/ w
38
6 _2 e$ O% M, z; d39* p: r, y8 |5 ?4 i
40  w' j5 I+ D7 L8 e# |( c8 ?
41
% w  k& ?' u/ D4 }6 z42
8 \, a! x4 ~+ h+ t" h7 W6 Y4 s43
# J6 \& L/ g2 F& p5 B44
: ?! ~. x1 s6 a( l; p455 C( \3 `2 u$ G- A  \: H
46
" l$ Y9 N7 Z4 a47
* K' H+ L7 ~6 u. K48
/ k: }+ O. {. F  s) p7 d$ i49( P, u& a- Y2 p# u2 q
50! A8 M: \4 @5 X$ _, N  _5 E
51( Y0 x! B8 r% p
52
+ ?5 \! A% V9 M8 g6 _) S" s( v534 i, F5 n$ U% E3 E; @  f7 r
54
) \7 R$ e& y$ \9 n! y55% W0 E9 u7 Z3 _% J/ K: P' S+ @+ g$ U
56
( ^6 b* {5 A! p- n572 s( q* m% y. |* c5 i$ I
582 {+ Z$ o( A& \6 I8 ~% ^. F6 i
599 I2 [5 c2 Z& t- ~
60
6 y5 I7 [+ p6 d+ U1 @61- O4 G# i8 \+ |$ \9 j0 k: Z
62
. C' R+ n7 Q' f63
2 n% p4 G, `  e* }  W' N64  W7 j( @0 r5 C( H
65
) R) _  f* W9 z) ~66- K' J6 q  q* p" m, e: l/ p( ~
67
; M6 w: S5 i9 ~" A$ E& G( Y68) I" Z6 t8 U1 K5 E" J3 K, v
69/ _' P% J0 I0 C8 `- z% v
704 i5 U- j. B8 O
71
72( P- |) g; D: F9 _0 B+ b5 ^7 d% [
73
9 z  F# t9 B9 p5 q- C74
; n) M2 J. k7 h5 K. _; J3 H75
, n; q, q' b. r' _76
1 u0 O8 ^: Z7 g773 P, Z2 X6 `8 C: I5 Z
78
5 x% y6 K( k8 \, o3 Q) r79
. P& n& N2 t6 X80
; ^& a, y1 z; a+ ?81
! M; u& Z' i* m; K, B# t82  Q# N* Y0 a$ m- `0 F
83
* V; f( I1 j: m84/ }5 {! n+ k0 d$ W) b" m/ q
85. v( n$ E' _5 k& o& y
86: J( t" b6 v9 @, ~1 x7 A4 E7 j) e
87, b' O2 T! W% a9 Q  p. b5 i/ _8 D
888 g, W1 k& v( I7 }2 D
89; c9 n5 \8 i- H& t# q8 z) H
901 O2 d4 N) Q- q/ x5 }+ K) m; u7 p
914 c$ g4 M% y  r  D( u, R
92
2 k1 e( u1 }2 P; O5 [: {938 C6 H. }2 G$ p& l
94/ {1 }9 W* G& N
95' Q1 ]/ ~5 K: U5 _
96
& q, t2 I0 v! H: r975 H! L2 \$ Z$ @+ L
981 B" V3 H, o% n. g4 r
997 |% L, u2 D7 \. ]+ [4 y  T6 ~) }5 D
100
+ B( I2 A2 F2 x1015 p* P! X; J$ ^
102  ~. N7 M3 S7 p7 n+ K0 F; ?% X$ t- \
1036 H- r' C7 M4 q% {. R. b2 q
（高斯核函数）
" ^5 K' H! d* _! x. M8 \
% _" c. A( u" ~, r0 ^# \0 h2 c9 Q. ?2 A" M
（K邻近法）
$ v2 ?: {1 b) D) }
3 p; k1 ]# M) y3 M# F5 a" O  ]- Z" D. b& [/ }" n2 E7 @& q' f9 Y
四：谱聚类算法优缺点
/ |% ^; U. ^" k* C  y（1）优点  i5 B; M3 S- \! f( f) F: h& `
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效
: O7 |0 N  C8 b* T) O9 b使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法( t3 f0 j' M3 ~& v; o5 s& Z
谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解. V% S: X4 G+ P" s6 T
（2）缺点
! f% W6 o; y' U& Z. Z  J" u如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好3 @# J. b; J  n  D+ ?+ {- J
聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同! F2 S' R1 I' |5 r( e" o: ^, m
————————————————1 b/ K5 p) E8 z! m- L5 W/ j4 D- x3 U
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
* P8 c6 l, Y$ \4 v- V: u2 H3 N原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494
$ T- @" {7 X/ D6 P8 g( X6 \2 _6 I9 P# w* X8 u2 F* U

# j! N3 X5 c. G& ^8 X: M9 ?