查看: 3006|回复: 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])! q* W- P: y: E2 \9 \
return dist_matrix
1 F# ^6 e" x) T" G* A6 J$ ?: G. G: b& r7 B8 Q5 y, [: N# s& s8 \, c
def get_W(data, k):, O' r8 t! q+ Z1 f! M
# 获取邻接矩阵（K邻近法）
; u$ ?3 \$ f8 N# o3 l; J: a n = len(data)1 k1 u" v$ Y$ U8 N
dist_matrix = get_dist_matrix(data)4 g: t' o7 M9 B+ L
W = np.zeros((n, n))
8 @1 M( N1 o) V9 k4 Q3 d for idx, item in enumerate(dist_matrix):  z/ Y. A9 {. }" i# _; k, d
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表
! T. H$ I* e" N/ L8 l8 ^       W[idx][idx_array[1:k+1]] = 1
  @3 I1 I  v( Z# x+ O$ e9 h" E- B transpW =np.transpose(W)' E: x. C9 r/ z( }3 F) y* Z) b" |
return (W+transpW)/20 W# ^& D2 u  E! p7 g& x: s

& o* `  l/ z6 ]% Y7 |def spectral_clustering(data_set, k):* h! _$ r. c0 J) t0 G7 J8 U7 T
# 利用相似矩阵S得到邻接矩阵W4 s) u) D, G7 J8 Z! ?2 U
W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）- N( y; G2 m) G& A/ E: \# U
#  W = get_W(data_set, k)  # K邻近法& V: o. z0 P  r4 Q4 w
  L5 v3 u+ B; o, I) }+ C, F
# 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）
% t  I$ Y4 c3 p, l. |  q7 x7 o& ~ D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))) v! r" X1 |, z' V: w
3 k* N; A: b2 A
# 计算拉普拉斯矩阵L=D-W" \3 ^- O* C. a+ R$ j2 f
# 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
; n. u/ a, P$ B7 o* _0 l' X L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)8 u+ `! B  O5 C  F

- V1 z$ [; P! G/ I5 G # 得到特征值和特征向量
+ G3 `* S3 G, M' s. \2 p( i( t/ m eigvals, eigvecs = np.linalg.eig(L), B; @3 z9 W1 s* g5 G/ Y

; b5 S9 ?) ^! M0 A% ^! m: C # 找到前k个最小的特征值（索引）  }0 M& r" n6 \- t0 \, V/ z/ m1 D  e
k_smallest_eigvals_index = np.argsort(eigvals)[:k]# T% i4 A! Q' J5 H9 Y
7 s  {" l/ i$ L. f
# 取出这k小特征值对应的特征向量，并正则化' ]5 j% k3 ~8 f, E$ _, Q) q& U
k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])+ s& q2 U' U  u% n
: h$ w8 P$ ?$ X* C6 Q, n
# 使用K_Means聚类$ s+ o" U+ I" s& _( m* p# ]2 k
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)
( B. ~5 Q# e: C
2 _9 L8 A& f3 X
/ a7 W; u( O5 Q+ J; G1 f) Zraw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)* z2 T, D, [! ?
raw_data.columns = ['X', 'Y']
5 z* c9 O# n0 M3 Gx_axis = 'X'
: \' y& o: p# b' [( ~1 Yy_axis = 'Y'
2 P) v! T7 ], E9 h7 ?, r  g& s
examples_num = raw_data.shape[0]' L" y" a0 C" j+ ]8 Q
train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)
, b: v  K* V! Y! [% \
( h) N- ?. R* n3 N# O: }0 B) l5 ^+ d1 B) J* |
min_vals = train_data.min(0)
+ r0 I! @1 ^* M* i6 smax_vals = train_data.max(0)
. s& H+ v2 G$ w( k: x. lranges = max_vals - min_vals7 q# t1 B5 I- }
normal_data = np.zeros(np.shape(train_data))# R& w. ?: X- N% h
nums = train_data.shape[0]" T: c. d# A5 D: J4 x& A
normal_data = train_data - np.tile(min_vals, (nums, 1))
& b, S9 V; u& n. y- M5 @# B: Onormal_data = normal_data / np.tile(ranges, (nums, 1))

6 G. N  C- R  Z" P. |' jlabels = spectral_clustering(normal_data, 2)5 O* q1 y9 B( U/ d6 }7 T
, N! a5 t9 \. u! h
# 原数据
$ o) r$ H' ]! ufig, (ax0, ax1) = plt.subplots(ncols=2). t9 S3 E; E4 ~5 p; Z
ax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')( h1 B8 k3 S7 m$ v( X
ax0.set_title('raw data')
, g) _) t# @: o. M# 谱聚类结果* Q$ |9 d( S8 c4 q$ U3 {
ax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)4 A( a: B2 X* `! j0 |8 _
ax1.set_title('Spectral Clustering')" \% \2 A8 E6 |0 T) h

3 y+ G" w9 ^+ b4 k/ x& c5 X2 kplt.show()7 d. w" M# w. c0 N

/ w$ V  @6 f( I1
6 P1 f' R% d0 U& Z+ o, @/ N2
. x" S5 F7 T$ [% ^- S3 }9 C) Z/ a& Z3) x3 _" ^4 o$ O0 A/ z
4
2 K$ I; Z' T5 \' A5" ?' K2 ]/ K" ~$ c4 |' y  _
6
, o0 }  m& l, p+ o" W75 X0 _3 {. p0 ?
8
' f% f- R4 f% L( ?9
4 z; r" y3 |: `/ t: J10
" j1 ~! [/ p/ y11; w7 S7 {; [7 ~* B' Y
12
9 x1 r, T5 d" J! Q1 L13' g- z) N; r' v) I
144 G' ]/ d1 a1 `" q1 c! t7 z; F; ]+ [
154 D5 _, X$ d9 I0 ]/ @+ A- \
16
1 o: s1 |- V5 I175 f2 }1 n; i7 @6 x3 C/ }/ X
18! I5 {4 Z4 q! f9 @+ T; _$ c0 C0 w
198 `) \5 d; C# @9 P, t
20
; Q6 _7 {) C: [5 ]& f1 a6 X4 S21
0 b1 d* E6 A( R22
1 u' Q0 t: V# s) E  S: \23
: l5 \* E' m2 v" |% h2 D* G24! n7 T; M# i- O) I4 x
25! |* J& |9 n3 D& p2 v3 w( }
26+ L0 T! b# I1 W6 O; w, Y1 V* N/ U
27
& c9 j  u# I+ m2 r1 Z3 d281 @" R& S4 W( T2 s4 i
29
4 i  U- E0 m! @) Y) w301 G! \8 G/ x9 C! ^
319 @* b2 p7 t  a. a8 q, x* C
32
8 d. e1 K, z6 Z# i( {7 }33  ?& \. W8 V8 e# b& v! b
34
! q! L) T  \! g, y35
" T/ m& b4 l; h36: ^  S. m% ]% C7 j- j+ e
379 s* W- g4 E- F4 r
384 M" H5 r: y9 C
39% P1 x2 Z- C) a
408 \! J0 T+ w; W7 {7 b
41
" d  G  b$ g7 B: V42
/ T( Y- W$ x/ K; H" p. _/ u/ y: L$ \4 t43
/ B7 N* ^& k5 }: ~# b* b- P& {; n44+ B" K  c) L5 W: J! ?  H
45! T9 x7 {4 S+ d* Q) [
468 O5 `# B! e9 K' O
47
4 V1 X3 \9 n, |48$ J( s1 }+ U6 Y! O
498 N3 @7 g$ ?; M
50
6 w4 H4 f+ V1 H# I51( S5 q! x* A5 Q* T4 L$ y1 T% A
529 n  F; U' K7 x* p
53/ g2 I& l( d4 l  f
54
8 [4 A2 i3 _/ t. @55
/ J6 Q+ [0 s7 }56  V, e9 L4 m/ R  r
57
/ m+ e" ~# _9 p0 n# z" y/ H3 ?9 x58& p! y/ y, b- r% J" N
59
8 Z3 K$ A: n0 i( D) t606 A3 O! R2 B' [
61
& r2 p7 z2 M9 D! J9 f, g9 c62. Z2 ^2 N2 j2 o. r" z
63
2 N2 F# C1 a- K) L$ _64
4 }9 |4 h- T: T658 Y7 H2 P5 O7 X& i
66
' p1 Z* r# }, m8 D67
0 x2 v3 A* x! n( V68
. b" W4 l( _, l5 n% ]- g69
) t0 G7 I' e4 [3 n) x4 q. J2 y70
- }7 y5 a* S! _2 Q715 F) A. d! q+ m/ b/ F7 Y$ W
72  |2 f1 z# @3 {( A
739 j9 @9 @/ X7 p+ r& G
74
+ ?. E5 {+ W3 K* c. E  I75
2 c+ S3 M* n: n; D" k4 ?5 G" `76
, `  Q1 k0 O! R/ H6 g' L77
6 s# u) m1 Y' a- Z8 ~78% N: W% j. o3 s
793 N- S2 ?9 d- v% }# G
80
! r+ R- p2 T$ H. f! `8 x( W812 u* w$ D/ B/ G3 f: Q  Z; J( N' Z
82
  U3 g; @+ a; w; d4 m3 d* V& v83) u9 E6 ^$ W4 ]: }; K
84
4 V( z" T  q# C- J/ ], @, s85
- R0 |1 w$ d# h  z860 X" c$ Z1 k9 J; G' V
87
; H2 F/ {8 P" G" w# u; d6 W" U+ P889 q2 y7 @' \5 u3 c" d& o1 b. e
89
; v# k: J' o4 G90/ J: a) ]/ _& X; u4 a% o
91
0 k- y5 P+ I  y92
$ f6 v- p8 y7 ~$ s& e  D) \93, w' B% p/ x- F. B' H
949 Y/ l# X( u$ p' d8 i' e" N1 N
95
* I8 F2 ^, k  S; ?  S; [2 C96# z: S) S9 ~7 R  _5 P
97( R# T' i4 a/ i# a* E8 `" X
98( `5 H) |0 Y( c
99
8 `! J# I, |/ _+ `% ], u8 u7 u$ g1001 P- ~5 v" N: D$ ~8 T/ ?
101
( D( D% S. s7 o102
, H& C" T+ f8 a* ~0 d  S1037 W/ t! ]% t. N2 m. w5 @" p" p
（高斯核函数）. F. `- T# Y2 Z, Y: h, \
3 U" q$ i  ^; |0 O
/ a( ^$ y5 K" e" e( \0 U8 \( Z
（K邻近法）
$ v0 ~* S, p1 m1 R$ b% u& D! k3 v& f, x8 \  t' \2 Y( k  @& b

# T' v7 O0 m0 F, Q0 @四：谱聚类算法优缺点
) Y" n- K; }# J（1）优点
9 P+ e7 i1 ^+ g9 _$ t4 e谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效
7 P6 L  g$ Z1 T  k* H6 G使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法' f4 a$ z, t! n3 l' M$ ~
谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解- f- w% F0 e* o- B/ V9 s# `. \# e
（2）缺点9 \# p" F. ?: W0 e4 I0 _9 E1 x
如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
8 W2 P" A' o% j, B+ I聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同+ I6 i6 n, Y3 X) E
————————————————2 t  L# Z5 _* M$ M6 i
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
7 Y6 V8 X! C. ^0 V) w原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494
% F9 M7 l& t0 a% ~
# v" F2 u6 |% r6 ]2 S
! x/ S& ^* {9 f' C! ~