查看: 3007|回复: 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])
& ~* g; w5 I, ?, K) d2 m8 E return dist_matrix  p1 n: s- T& D0 X$ ?

4 Q2 ~2 t6 V  T  s! a3 s" cdef get_W(data, k):7 H' A- B  }, k$ u; ^2 \2 @
# 获取邻接矩阵（K邻近法）3 X/ u8 Q3 p( Y: z% j9 A. _' E' V
n = len(data)
6 u5 t/ H& I3 k' Y2 u- _5 w  J dist_matrix = get_dist_matrix(data)
/ q' j  Z' m/ D! G! g$ z& Q- \4 A W = np.zeros((n, n))0 o# i4 b$ Y8 G6 X9 v
for idx, item in enumerate(dist_matrix):5 C' F$ K4 n) |% ^* S0 ^$ _, O3 e
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表
1 E9 C* ]# s" Q# Z       W[idx][idx_array[1:k+1]] = 1  e. Z3 [/ O: h' }" m; |  m6 x
transpW =np.transpose(W)4 ?. ?# [" m! Q) i# R* h
return (W+transpW)/2
  Y3 K$ E8 ]8 F& o. \1 J# R, q/ i  }, H) P
def spectral_clustering(data_set, k):
# 利用相似矩阵S得到邻接矩阵W
" I& r7 X5 X& B; I$ A# Y, N) v- Y W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）; p/ E* {# ^5 a: U+ M' o
#  W = get_W(data_set, k)  # K邻近法; @, L8 b+ y6 [
# T) ~8 k. f) d
# 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）( b5 L$ u+ v0 A& m, G( A
D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))
; P' s- T' H$ n- @7 g5 W; B+ B  F8 {  M& r( u5 h
# 计算拉普拉斯矩阵L=D-W
  L1 \1 q0 o$ z1 L' f; W # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
' k. u7 L" f: C7 i' ] L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)
% a+ r8 g0 n4 K$ H
0 x8 T" l# h) `5 g # 得到特征值和特征向量1 y% y, c' w1 Y; I
eigvals, eigvecs = np.linalg.eig(L)8 B5 ]0 h( n. [2 `/ I! N% _( W

3 N! X) M. u0 ] # 找到前k个最小的特征值（索引）! N+ I' l" o& Y6 J/ Z0 j. s( I  H; `& u
k_smallest_eigvals_index = np.argsort(eigvals)[:k]
1 [  m% e5 l2 q; j% E( r2 t  S, T
# 取出这k小特征值对应的特征向量，并正则化/ r7 P' F4 W9 N$ T% j. V( E
k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])6 t- r( V: G, c$ B  W( Z: e! S4 J

5 B% _/ G5 p9 V0 | # 使用K_Means聚类2 U+ h6 Q9 _7 y0 |* w
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)2 n2 d( }: k. P. X/ o1 K
. v* g5 M: A! [1 H$ @6 |

% H7 `7 j  a+ t7 `2 \2 _$ \; `$ j; ?raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)3 S# F+ l6 ^; L
raw_data.columns = ['X', 'Y']( @: J. M8 Z' O9 |- j1 \" R5 }
x_axis = 'X'0 y( L* Z# |" Z8 l! r0 Y0 U  w* _
y_axis = 'Y'
2 l  J) y7 d0 L, o% \$ f% t& d" i( b3 p9 L3 v4 O. T' w
examples_num = raw_data.shape[0]9 B/ X, H7 ~" H9 m
train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)
7 B* l; f- u, P, [1 a& e) T! o" ^( u: M" Z* [
, t: @. y' N' X( r$ i6 r6 A- s
min_vals = train_data.min(0)
/ D1 n/ d# p$ H+ {" T' f( V3 vmax_vals = train_data.max(0)9 @& ^" \4 l- a5 N
ranges = max_vals - min_vals
2 i7 k4 R) n- ]$ O0 H6 Wnormal_data = np.zeros(np.shape(train_data))
0 o% R! G2 W2 R- h5 S/ ^nums = train_data.shape[0]7 h& I5 X9 j+ ~9 b
normal_data = train_data - np.tile(min_vals, (nums, 1))
6 f" \  [9 K0 l. b/ b0 Rnormal_data = normal_data / np.tile(ranges, (nums, 1))
. [# {# R( w$ b$ D  d' _7 R1 S9 N+ l( A. Y9 p
labels = spectral_clustering(normal_data, 2)
" s4 R( Y  `/ ^! d
" a* }% b# y' K+ b# 原数据! z* o" G9 L, t. U
fig, (ax0, ax1) = plt.subplots(ncols=2)
7 F7 u1 `" k* p, t* E) tax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')0 {5 r/ F3 B, ]- B( G- s+ i
ax0.set_title('raw data')# L0 }0 \# T0 D6 v
# 谱聚类结果
+ v  z4 }+ B0 dax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)
: w3 n0 g1 [& ?, n/ Aax1.set_title('Spectral Clustering')
4 P5 H$ S8 `  K  |. O" M. z5 J: }! V
plt.show()
; S7 I( w- l, ?3 U  |7 V& v% G3 m8 h4 M! W
1( v- O0 }' k7 T! x2 x; M
23 ^! `, r% z* K; y& Q  q
35 y" D! g( F* K0 c9 e- q/ _, s
4
+ C' c* ]/ X/ L+ l* ~4 o4 K& L53 Q' b, u/ O6 x2 I, v) a
6  `. i6 _" o. Z. a
7
9 E( O' C8 A% e0 n7 }% W  P8
0 f! ~- M0 ~1 ?1 V! U1 E90 t3 Z0 d9 [4 h( o. M* b
10
# d, z# h  V* {! ~# M+ ^- r3 R$ e111 j% D/ K- ]1 F1 [1 H: ~2 X" a
122 B3 q1 r& b! F' c
13  z1 ?) Q! s( p  \
14* Q5 e- V+ u$ T6 m# v7 x. ~
15$ D5 E6 [8 o9 E! O
16
4 ], }) n2 m  Q+ G8 Q) `3 h4 }3 T8 l17
. F# l/ k5 @$ h7 e! D! ^0 z: e18
- E# a; g$ M, Q, w" g9 s6 o8 b19, Q7 k8 Q# R6 g" D
20
8 F* e& g( t# r214 H3 K) j9 @6 e$ O7 B
22
23+ [) A2 s  o: n0 l6 X" N
24
* S0 I0 ~1 {1 k$ a254 [* `: q2 ]& T( p: t
26
" @" d1 a( Y- t$ Q& N* i/ i272 l6 m8 k2 [2 @* c, B
28
! n- J" l3 c" X) F0 g29
& r* S$ E4 x7 {9 f$ [5 \30
; N* y) K; `( y1 W$ s$ G, @& s0 k31) M& {. ?% Z8 m3 ^9 b
32
. [5 z( C: B8 T: X5 T33
6 e; }; t( |( |# M" h! f34
2 R1 u$ }6 @5 B) s7 F6 F) \354 G/ Z! [: Z1 K9 \# s
365 d1 m3 u4 t, B) P8 T
37
/ r% A8 t% Y9 u4 T" U- x. n38
) Z4 O( g9 }* Q+ }- m39/ t2 B. H, x# ?/ n; `# v  H) R
40# m9 U4 ~8 k$ n: v% P& x! ~# M
41
- G6 e. P3 `  T: A1 v' {42
" l4 Z& x) M8 Y0 M. K43
/ y- l5 n* t6 K- D44
& C8 Z: g, S/ \1 d% T. \45  B& v& e  R" @, V0 W+ u' v
460 I+ D' j$ v& e( c
47
* u$ @' ?% ^5 A1 a: K- |48
. v. u4 S  H# h& b0 N49
+ k8 ]; Z4 v3 u) S; {9 R50
( Y  J* @2 P; I( ?6 h) [51
' V3 S& W* B  \1 ]52- v( T( r; F( W% u9 C# O* h
53( N+ U9 b5 ]1 Z7 t# Y
54
- a9 t! ?% B4 W3 P" D" a& x557 \7 m5 J" {. J0 X  a. R( }
56: R, F$ c6 g2 x3 n7 V6 [. }
576 d8 g% S- ?, G3 m: r* u
58' H: M: l; a5 }, `; t
59
0 @; |. i  o- Q( R: I7 |60
. V6 R4 J/ i7 c0 i$ Q: a4 a61
  J' p. |5 ^& i1 \  E62
8 z: l! S! c. y& ]& B637 C4 H6 r( \& o. a  ]
64
9 ^8 A& g/ i/ `5 S  E65/ j* l- [1 K- d1 U8 K0 N- ]
660 T4 E; ]' s+ B
67
2 o/ h! c$ _6 V68
' X. y  _* Q1 }0 `: @& ]4 D+ G69
# h& f( k5 O1 t6 Q+ J) b7 [: l70
; _% e* M& b9 H& X718 k3 a$ ~* n$ p
723 C; o6 T7 R, i5 v6 u
73! c3 n, W6 J' M4 _( f) W, L; ?
74
& ^& f2 G" M( R750 O4 i4 c0 G% u5 k: L
76% Z6 K/ ^' i. H+ F' b
77
: d6 G; ?7 W+ ]! e# Y' M/ N, f3 J787 o& a/ r# S( q1 N& H6 z* \
79) q# R9 I5 J) S# v9 W1 F1 M
80
! m( ?: V3 Y4 o81
3 o) J9 ^+ x4 y9 n. O9 \$ E824 ?  `4 e# C, b/ W4 B
83
9 U& b, x+ ^! f7 i, _+ R5 J84
  Q; P& L7 V% \( \85, s* u, D2 |# U) ]9 r! Y
86" X2 l9 F: @/ m! W$ x0 _3 ?* A2 H0 a
87
: J8 N" L( V3 q: i6 Z; T88' t' }' m1 y8 @- E; [0 n& F* s# J  g
89' ^; A! B4 w+ @% w( j2 f% c6 Y* A
90
: c  m9 ]) |% I7 Z91* |4 N+ T! O+ o. h1 S; C2 w9 F
92( G/ U3 z1 l- O3 W; Q! G$ I
93
/ }9 d2 G' C* W+ E; r! ^$ ?+ I947 q' G+ r2 P( e: ]2 k# o, N
95
  W& z( Z# r, \96% K8 D$ O. i+ I7 f
973 X3 i: r( s( F3 |
98
' o! W- u+ _- ?- O0 p99
) d4 n& j1 k1 b) y: l& ]$ _- z100
, W- ~3 a3 U- o1 a: f6 V101
1 @$ M, ^0 {0 g7 T$ K: ]* E* m, r102
9 t5 U, R9 c9 c7 N103
7 h, H& \. {$ N8 S9 |5 G（高斯核函数）. p; |9 w9 C, [7 I+ g" |

: S: W$ h* j  d9 b( J* h/ d7 K& e* d# H! a+ w0 F+ V
（K邻近法）' ^, ]# ~( p8 ~. L% P$ I- n
* v( T& @/ ^' `6 u

1 i, L$ q& k$ o四：谱聚类算法优缺点+ \  b2 `: ^( v* F. A% x
（1）优点& F) i% g' v+ g- Z6 ?
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效
# r" ]9 s2 ]: {  c! z/ q9 z& `使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法$ ]  e5 g. `6 R. Y# A" i. v
谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解
  v  I7 \: A& R. C$ V) n( }（2）缺点5 f/ l, q$ G6 Q$ a' [
如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
' G% E' ~, d4 r9 O聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同
* A! {+ I7 Z; d. @& S————————————————
2 m. t, d# b& ?版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
$ i* K8 ]3 W/ O" r原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494
" k6 m5 h! E6 O9 e9 d2 V# S4 j2 b' }, U$ c1 q3 }' R+ O
6 N' `1 b0 g, X" p, E$ C# `