查看: 3102|回复: 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])
1 \! y9 {* A7 J return dist_matrix' F9 G+ {) j, M" S7 q

8 e$ K" [. q7 \, Y3 odef get_W(data, k):
: S: i8 @5 O! i # 获取邻接矩阵（K邻近法）
' O) V; ~0 d( a. n5 @ n = len(data)3 I8 h0 P2 X6 X4 u9 A
dist_matrix = get_dist_matrix(data). o/ G4 D7 l1 N% ^1 y
W = np.zeros((n, n))
7 w  [& ?8 ?! K& g. l( O1 L, E8 m for idx, item in enumerate(dist_matrix):. J- i) }% l8 {0 ^5 j3 G
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表
9 g" N6 o! Q8 E8 i. o& i       W[idx][idx_array[1:k+1]] = 1, j: u7 j$ r: e
transpW =np.transpose(W)
8 k4 n+ R2 L: c4 h! _; ], O) E return (W+transpW)/2
4 I9 d2 r* w( b3 s
" y8 |6 x  i7 N% d5 b) Z1 c! Edef spectral_clustering(data_set, k):, E& r# \7 H% d2 L# y) r
# 利用相似矩阵S得到邻接矩阵W1 H( {! S( z6 n' z
W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
2 B% h6 a+ V. ?, I #  W = get_W(data_set, k)  # K邻近法
% E" E8 @! r( q4 J
8 D% L6 m3 \0 S/ I0 r # 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）5 [6 v5 t% [3 d" U  u2 O- z
D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))
4 h) ?3 }  F/ k% i; |# w, J/ H+ Q7 E8 D* c3 R2 Q2 r
# 计算拉普拉斯矩阵L=D-W
  G# C2 ~) b' P' p; ]' O # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv5 L- X1 g/ B) i
L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)$ `3 k" X+ i. X5 s4 o

1 _8 j8 ?* A- L; p # 得到特征值和特征向量
# M9 R- b5 z, T" C eigvals, eigvecs = np.linalg.eig(L)
2 L0 Q. u3 m& e0 K+ ?9 U, x9 T# x& _  H) z
# 找到前k个最小的特征值（索引）* P6 U1 |7 ~3 s9 h& ^
k_smallest_eigvals_index = np.argsort(eigvals)[:k]
* d5 z# u1 V( v) r  r0 Y
8 l' M/ D  B1 |2 S+ [$ V' c: { # 取出这k小特征值对应的特征向量，并正则化9 y5 P4 v- i, ]* p1 B0 o3 d, f
k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])4 D, N; Z$ ^5 U, K6 e

4 }8 u9 Q9 N( [ # 使用K_Means聚类
" n/ v2 }# K+ S; @; ?5 X* X2 G return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)
" x0 P- r& _- ]  G# {" ]! X
! V( ]# h# T0 Y$ s  T3 Y  D) a8 k7 G4 m! Z3 S
raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)! o3 V, b% ]9 ]9 i& g
raw_data.columns = ['X', 'Y']
8 ]% K4 }3 t( T) Bx_axis = 'X'
& q( b2 A0 r* Y7 Sy_axis = 'Y'% E$ A0 _* Q* ]! q+ S  ]

; M8 H" i$ G5 I6 h( G7 P8 C7 Uexamples_num = raw_data.shape[0]2 O! S# e2 s' p( {" u
train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2); }" G$ [+ o- n5 f* t
1 N- Y! A/ Q+ q3 u- a: l

2 Y7 c, b& w8 T: z) O  ?0 m$ A) gmin_vals = train_data.min(0)6 L6 p6 _) F! c3 s2 K
max_vals = train_data.max(0)
- }/ W7 `- ~, ~/ L, C2 M$ K, franges = max_vals - min_vals
$ h# W% g) o. s5 Xnormal_data = np.zeros(np.shape(train_data))# o0 t9 ?  {; l
nums = train_data.shape[0]
0 J! h! s  {6 {# \* |9 q3 l: ?normal_data = train_data - np.tile(min_vals, (nums, 1))" O% _: V' L# M" j; k% m0 }
normal_data = normal_data / np.tile(ranges, (nums, 1))
; s' i7 n: V3 g1 r! x$ G% n6 T% l+ k( I6 ?& a8 S5 @1 U3 C+ ]
labels = spectral_clustering(normal_data, 2)
; @4 t2 B; i& [- s( ~0 ?' @7 w7 ^3 F( _. d) P! A# O$ _9 s% A: u3 Q
# 原数据; G% a/ O7 D( b) Y# T, f# a. k* _
fig, (ax0, ax1) = plt.subplots(ncols=2)  u; i6 _; q. q+ C: B, L: s5 _0 P
ax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')
! l; O2 K# r. I1 ?0 N0 kax0.set_title('raw data')
) e7 g5 N4 L8 J# 谱聚类结果- ^1 O' {7 p5 }2 z. I7 m( r& g
ax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)1 g! q& h3 `4 l4 J0 T# c
ax1.set_title('Spectral Clustering')
% w: l  z8 l: [5 v0 G( Q/ ^/ ?5 b9 {' m; \1 C( F& ~/ m
plt.show(); D( n; A; {9 E' f

' F4 G+ y9 e4 V1 |1' P" r2 i1 X. ]$ V* }2 o5 ]" B
2
4 D6 q1 ]; B1 ~2 G3 b8 m3! @6 J/ y8 z, i/ j' Q5 W! S: U
4
7 Y  s. v2 ^" t1 s7 n/ i5. o  V. f  D( J: t
6( o3 ?0 Q2 |$ X: K- |1 w5 Y7 W- ^
7
1 ^  U" J" ~: v: F1 E& m& l84 ?: K- t9 u  O5 M. y$ Z  m
9
8 \6 b- k5 E( d" H. E102 H5 c( V' U# t( s6 u
11
' M; ]" Y, j, j7 D% q12, e( S5 X# J( d
13+ y# _) U( e+ G; `0 U
14! C% T' R$ g* H3 I; `
15
. `# ]4 Q: ?9 m( V# K; |. M16
* G: l2 ~; ?, E17
/ O- H# G9 i, k7 U4 N: ^+ Q3 N( h183 y9 ~, V2 F# d& `/ P# D& z$ B5 q; S
193 V. v- C2 z. J0 O
20
+ L8 a( e! ]6 |! j' d; n$ D21
2 h6 r' V" T7 K% m1 M22$ T. e% r! ?! C! C' V$ b3 r
23
9 m- v  {: b2 n7 h/ q24
! Y8 M8 |1 E8 H2 O' A25: {" }% z- }. ?7 D; e
263 P! v, R8 U4 V3 e$ j6 J
277 ?: A5 y2 N5 S
284 h8 E+ R2 S. {; d. u+ j! m' \
29" [0 a- q: F" \5 ?0 a/ F
30
) T2 I: j, d0 D  C& d* M31
( z6 e. v1 x4 G0 X: X8 [32
6 K$ I! Q' [- z- N33+ ~( P5 \& D7 J) Z; S* e/ t' d
34# E6 e, G5 o1 }* H8 c& _
35
* j. K, @# F2 h. t% j36
7 k* @% Q, U1 u* X* t7 j37" b& y; H- h) s8 L4 q0 e
38
. r$ y" p& p2 n9 ^6 V  k. \) X39& N- H* ~% x( J: W$ x
40
! j3 h3 a! G$ ^, M41+ A3 N4 H: f$ o3 `( L
42
% u! d3 N& L! Q+ j439 E# F+ b; v5 }5 K- ?
44# A$ N  ?- I; x; ], _* e0 |
45
- d6 W! ~" M: P4 k; t/ [$ B) k4 q465 i* q! O) r  \- a/ L; u
47
+ {" n0 X4 \: q& u/ ?486 y! @. e2 C3 ^7 S" X
49
5 i' C: t. u- Z4 a, L4 c50
& b1 s5 F7 W+ d51
" F' ^( H8 s& N$ S9 m6 x; ~9 N520 q/ W3 i* v. R  y* J
53
0 H  w# n# ~- O1 A$ U) Z541 f4 `6 d% D! o% e0 d+ a3 n
55
$ }% w& Q( a3 {6 O56
0 T1 c/ u  Q3 N# e57
) @* j: w6 z7 p- V+ P- i588 s; P9 w& [& z; L" g! B- T
59
; C* Z' [# [. Y" {/ H) e! l607 T' a; i+ r9 f4 a0 y
611 `3 N8 O1 B% H( L
62- Q. v+ O1 y: i# q
63
( Y2 {6 x" w" ]" l, P64
2 {1 E, q' \' ~) z1 I8 \- {4 n* Z65
* J" [7 n0 }( z6 ~, x( U669 o0 K# |2 [! Y5 L6 Z6 P: P% S
67, Z1 R: f  V4 f* s% i8 F
68$ @* R  k' p- I8 x
69; T  o- X8 y1 A# L$ p  m' u
705 C: }& a0 H& X. _  r) _0 c
71
9 G4 O$ _& R# V, Q. e: _1 E, W727 ^/ r) w; w: c8 J
73* N7 M8 w, M9 C3 Y6 H: x5 T
74% y( O3 K9 }* r+ W7 j, F
75
+ k8 x3 ?) j1 x. E# d# |76
* S6 D' r9 v3 f" Q77
* e* s- I" y6 ^78
1 M* c- p3 R% E: I  A5 O" J. t79
% I: d4 A, z0 D2 A+ w3 i2 P8 H80) @+ {) y1 _: O; W
81
5 g  |- p, S: h9 ]! O82
( T7 V" ?3 p, t1 k3 P9 Q83: W: @( p5 k& ]  u' b5 _
846 q2 v/ j/ n0 y! r; h
858 v# q* Y/ \. o- q7 l9 Z5 y
86
+ [! w; D4 k0 ~87
$ _# u/ i8 c0 w2 C7 K, U* `88+ y6 ]- h8 B" H6 H$ K7 Y
89
& R+ n7 {- j+ u& `8 J  ^& d" \, l, ^90
$ ]+ e' l3 `7 p* l5 a7 n3 F+ y91
4 X4 D* `' [; \  ~92
) U; u/ \5 Q" o! M: s8 }( i+ t93
! @( K: j! {, P3 \  \7 n4 I94
2 p: ?  e& ~# P% V95
$ t) e; k8 h& B, k96" V, ^; @( u+ S: }6 T
97
- c, K+ d* w+ n; }! b! H$ z8 z# D98
/ Z3 l5 m1 i# A0 d: G996 H8 F# A" g" O- W: @
100
8 J' p* J0 ]9 k, g) [7 K101
6 x# Y& a7 ]) [# v% R1027 x1 S% J# U! u) ]% H2 z; o. g
103
# h# W3 v0 Y4 [* w+ q2 T5 F（高斯核函数）
/ c/ P# r7 F; y7 w; }" n/ V, F+ i; k+ D4 N: I2 P: E1 x

（K邻近法）8 @6 y- U# N( N+ k$ {) a: Q
& _4 b2 g+ t) V& m
! W+ R8 W+ l, }* u
四：谱聚类算法优缺点
/ W: G6 W, b$ G. J0 l（1）优点5 s  ~9 E, w8 K+ r7 A6 K
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效7 [) V" L/ d/ |0 A
使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法
/ f8 ~3 O7 K1 P4 r* E  C, F谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解
; q: @, S. H4 ^( v（2）缺点
0 ^/ {7 W: v! C, P- {! q4 `如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
9 Y. U7 o& O9 p& @1 [  s聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同' H" ~# R9 K; `+ f) B
————————————————
( N# i3 S) B- ]( Z版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
- k# [, ^5 Y  u" E0 a& z8 q, K! ?原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494% ~, Q7 m  h: j: t4 A$ P

( Z/ t/ b% r5 y1 Q5 S0 Z! Z6 c: I. @1 u1 G* M2 g( F0 L