查看: 3103|回复: 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])
3 z) R* o/ @& ~# _5 K1 m2 X% l return dist_matrix
0 I& _: i6 T7 U1 v8 l3 t- o
( s- G, z; F* Y" Idef get_W(data, k):" p+ s: L1 z- F# x% L3 \# r- F) ?
# 获取邻接矩阵（K邻近法）. {8 [2 |  Q3 y, F$ a3 K
n = len(data)
& O  t$ }& _' C: D/ f/ p1 V1 _. c dist_matrix = get_dist_matrix(data)
" ?! H' D  }9 L( F3 a+ p$ r  A W = np.zeros((n, n))4 {. R8 U) v' p; a: G
for idx, item in enumerate(dist_matrix):8 H: r+ J0 Z5 m" O  Z1 F
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表
- g: O- T0 J* P8 p       W[idx][idx_array[1:k+1]] = 16 C  l$ m4 A! z6 A
transpW =np.transpose(W)5 K" }7 E" q) J8 o+ N
return (W+transpW)/2  H1 [9 N8 s- D, a. H7 D4 ~: S

- k# R% E( T! Sdef spectral_clustering(data_set, k):2 r4 X- `6 s. o0 O2 {' P2 }
# 利用相似矩阵S得到邻接矩阵W- e8 Z9 ?3 o: k7 j( T
W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）$ T6 ^: e4 W5 k# Z7 P3 _% d; |0 J+ u
#  W = get_W(data_set, k)  # K邻近法
$ R# I" p$ ?% R/ G
0 |! ]7 o( t  H4 z# v( ]9 E7 z # 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）
$ l9 g- H$ Z) E( g D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))' }9 c, F( I8 _2 L/ t5 d

/ J7 o5 F( ~: h; g0 m/ ? # 计算拉普拉斯矩阵L=D-W5 E1 v. S; I* M6 p
# 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
4 E1 ~7 ^1 r+ u8 L$ K L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)4 }! q# Q% j5 {# Q( S8 g
* Y7 X0 y' J, b% ^! M0 X' T5 `1 n
# 得到特征值和特征向量" t6 Y2 w! s  a
eigvals, eigvecs = np.linalg.eig(L)
- |: i+ ~9 y. i2 D, j5 l8 J2 R& m
' ?  I& H5 F  E2 L2 u8 k. ^ # 找到前k个最小的特征值（索引）( A* R1 p( Q' v' M" u! o. c8 x9 u
k_smallest_eigvals_index = np.argsort(eigvals)[:k]
0 \% T$ l8 R4 M  J' Y9 |  _# P3 y/ A9 k
# 取出这k小特征值对应的特征向量，并正则化( Q' ?6 ]# T; L
k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])0 K2 X  n. e2 {6 y! D2 x
9 D5 h8 v- D  {5 \2 o- {6 n7 s
# 使用K_Means聚类
2 i+ O  R' _. f% r$ O8 T% e) m+ U/ S return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)8 P) T3 D7 t! M# {8 Z7 g2 ?" L' t

; l4 Y& w* \6 r& t# H% x# |& O. _' m, y8 R4 g8 ]
raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)4 m. Z/ y8 S5 X' x( P8 o! {2 Z* w
raw_data.columns = ['X', 'Y']' \5 H+ a, d2 v1 j
x_axis = 'X'
: H# |( ~2 e2 y# U2 R3 H( u" Ry_axis = 'Y'
  E  G8 d3 e. O: }% ?) \
+ l. Y8 e2 R* D0 O- }! j1 ?examples_num = raw_data.shape[0]$ @8 l" f8 h3 ^1 }
train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)
. v5 t9 w  y- k; B" b' M( t* f( }5 C6 w2 U& u; C. G
& k0 a7 K# {) \+ I" L: K: N
min_vals = train_data.min(0)
9 b, E0 s$ W: l0 C+ m" o( q( G: fmax_vals = train_data.max(0)3 U) n0 j3 H: D  B2 \, h- x6 \+ D! b
ranges = max_vals - min_vals
8 y& i5 v, P4 y8 B: pnormal_data = np.zeros(np.shape(train_data))% t. m' [$ a6 x" ~* a7 D# o7 \
nums = train_data.shape[0]/ ?0 n9 t  ~6 C
normal_data = train_data - np.tile(min_vals, (nums, 1))
/ ~& x, {% [# w$ b$ y) Mnormal_data = normal_data / np.tile(ranges, (nums, 1))
+ w* C  J. v0 J8 }( R
) X* K+ v3 ^. S) u' Klabels = spectral_clustering(normal_data, 2)& l) q( {, l7 W! h3 v, N

( |- x; L/ K8 C8 _" m/ _# 原数据3 \* e/ X* }- `" ^) L# o
fig, (ax0, ax1) = plt.subplots(ncols=2)/ ]3 P9 V" u1 a; N- x& R# ]( |7 R
ax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')
# [" o" e- t4 X( n9 s6 Sax0.set_title('raw data')
1 Q, |, |" `' A7 h( [# 谱聚类结果4 s9 R5 O3 {  v9 u* c
ax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels). }+ P2 L8 d: d( {$ q/ j$ f
ax1.set_title('Spectral Clustering')& l1 W" `3 j/ t8 u
9 s! |  m" i- m! e# v7 s" l- `1 D* W
plt.show()' @3 w% X/ y) @0 |) ]

9 G" o( [; P; ^6 B- \2 V; N19 y, P) |* Q' _- S
2
, {0 W! n6 Y( N( c3
7 B5 Z" J0 e/ W. L6 J! x( l& i4
1 T0 C5 w; Z) w9 T# X  e5
# c3 v/ ~; S- G66 G0 ~- f  U  f
7
5 P* ]; e* E7 C9 z& O7 H' C2 y8
" v% i) w8 I$ {9
3 [% {$ |3 c1 s1 f10
, f  i6 c: _; N" o8 {11
9 F0 Q6 m0 k$ t& L! X* q2 _12
9 g  C" B) f" z6 Y6 e; f9 d13
, ?7 L( E5 P. S8 ~& @0 T14. p7 g+ k+ r5 F2 Q) @( ^
15+ ?5 w8 t5 l) I. B. J8 G0 K5 }, |
16
/ K' J+ Z: Z" i7 I: Y17, }- b! t  E6 ?3 G" p7 ?9 l  ~
181 M# u2 J0 y* }$ W" m6 \+ x
19
9 E; w1 \. O  J. o20
+ O% D" ]2 D- ^- M21
6 V1 K& }1 e/ v* t& G; e$ W22. s% _* X: _6 L, z
23
2 l$ z9 `! \! q+ P247 _1 F$ m1 R, b# b, b6 `6 H
25
) J* I' `5 ~  t$ s4 p26! n! p# N' a- |% R
276 j/ P& |5 y! w: n
28. B' Q9 ^; Y2 X8 w# l6 y
29& k! y" ^8 W1 u+ }
30
( I0 A' @/ j" K5 S- q; b& j$ D31
! g" C$ X  f% Q( U- x32
8 i: V$ {0 r+ J33
/ ]: N6 F1 J' G( W/ e% R8 P+ e34
: _% S0 e1 R( G) d* p35
- l+ R; N" I+ j8 C, F  T36
6 z6 j' O" h) M37/ M2 \  q2 Y$ {6 c/ C
38- D# C- Q& [, ^" f, c
39
: j: G3 C1 X* J  W40
" j9 d. E; o$ c! @4 l41
1 H. Z3 J% x9 H) m6 p0 g& s0 m42
0 M% a1 a8 L1 Z* P43
1 V5 c) ~6 K5 Y; m449 `& y9 U5 F% D' v$ g; I; X
45
" [( l: z4 a8 l. D2 }; A$ H460 u3 E; U+ v9 x* N
47% y" Y$ c# g2 K& c0 J. [, h
48
+ L4 J& j$ H- m+ ?) @) b1 A. D# a49
% _/ V* B$ ~& H6 L% d- p( g* A+ k, {50- y0 S, E) ?' n$ Q! @4 c0 f
51: K" V) y2 V9 K
52
533 V; f$ o' b- ^. g
54# Z. U8 X4 w/ Q* b7 D' y
55: e8 I( I# c& I6 [2 a  ~1 j$ E
56
9 U+ k, M* |7 n, o57
. M5 V7 Y# F! k2 }) C0 b( ]58
9 c; S% X" b8 o4 \5 E8 u1 j599 y& L; L0 W4 V+ O+ _% ^5 ]8 `
60
+ ]/ y, x4 K. Q61( c- q0 T1 ^# _$ N' H: c( l
62( a) y! a+ a8 @: b) p3 g* z( g
63
9 \9 A# B  x, ~64
  x# u. n9 q1 t. q; @, Q8 r65
) f' h$ b. @3 N% l4 S& [' Z% m, J66' G. U( ~) O. x9 c- y
676 O( G+ L- E, k" [
68
5 n4 l9 x$ y0 G! [69
3 F6 Z! [* P; K( P70$ H* u/ f2 r" Z5 G, k7 v. a# _' W
71* l3 V& ^: Y% F" e4 u- O5 S. m* b
72
& u# e6 h2 S& L! F' ?, t+ c73
3 k: z; C" G  Q4 C9 f74
9 I3 J9 I+ I1 e+ y! ~75
9 Q0 _/ m8 c: y# B* @763 F% S3 j# h& V% k
77
0 Y: R/ j9 k9 @78( B* v, [. k5 P2 h: l* E8 C
79
$ h5 i' D5 ]4 B% J" r- [80  W' Q" ^0 d! h2 s
817 N, i5 l: a# r' h, ^/ T1 D
82
" ^2 Q- ]* N( p1 w4 Q4 P1 x83
/ }3 p# T+ I2 n% b; U$ I! Y" B84
9 d) O5 _2 P/ p6 {1 U3 k' t0 @85
9 O8 P! R* B6 a9 W7 Y; o86
87
$ o' i" ?2 ^1 P9 x- J: O1 v88
3 r# f* m) q$ k5 {* G89) h! Y4 T1 a+ S+ O+ w" Q: J
90
8 v% n- E3 M. D! P. k+ \919 E; C6 j7 x# J7 `+ M
92( p; ?' A6 L5 {1 U
93
) _1 ?# E( F4 J! K! N4 H94
6 L7 A/ k5 S: r$ A9 d- Q95. A. P$ F% w9 Q
96
+ [9 u  `% \8 c97
7 J; g4 q7 z$ }# k& b% S98
1 l( O' D! ?- m- Y- t3 ?6 B99
: j& m% Q1 L( O) H3 a# P, b) }100
& K2 O, k9 b, @101
% G0 ]# u  q/ N9 {/ U8 M$ ?102
! g" R+ w& s: Z4 |# A% M" X# p; t' U103" H9 f9 w: y0 m$ C
（高斯核函数）1 p( v& J, A+ @$ s* d
/ L6 j* V( k- J' k
% H: k7 |$ G3 |/ i, A) B7 d0 d
（K邻近法）
/ R! F2 {( C% H3 t  r, o3 U* @' ^8 g+ b3 E0 w  p7 O

. ^1 ~5 t! U7 M! b9 C' c8 a, g四：谱聚类算法优缺点3 N# d: `- L5 w$ q# m4 _8 o+ B
（1）优点' F* r% h8 f9 \- S" A9 r. ]
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效
8 ]6 H# U( r2 ^4 a2 ^8 ]8 ?1 Q' K) ?使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法' \5 u' u/ ^+ @; W) o
谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解8 i/ e% M4 B, l8 U' y$ ^# a8 w. k+ ?: Z
（2）缺点! g& j8 d* D0 c8 ?
如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
0 h# l/ \8 S- {. F; g4 ~9 P聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同
& U5 ~1 S; t- {————————————————! e5 d" q( v/ Q1 c
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
; n( [( B" [. M$ q( O原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494. ]# h# Q0 u6 L9 F  L7 }
2 v& ~' i7 B/ |& P" G
! s/ q1 z9 F9 P6 P! z/ Z