查看: 3013|回复: 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])
5 t) Z: Z: g7 z: ?" L return dist_matrix& B" S- T& T( m9 l: g
+ e0 U+ f. b- l2 e* b9 e5 Q
def get_W(data, k):
# L9 ~$ @6 L3 Q$ @6 g # 获取邻接矩阵（K邻近法）) e0 [' A$ P3 J# r9 I# o# e
n = len(data)
" K+ w# H! n) \* G; L* ~+ z( r dist_matrix = get_dist_matrix(data)
# K5 h+ W% c3 w W = np.zeros((n, n))
3 b" _$ j, _) L2 F) ^ for idx, item in enumerate(dist_matrix):  L" N# C# F8 _& t& H1 j
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表
8 F* N6 |( R# R# v& A% y       W[idx][idx_array[1:k+1]] = 1
' h$ x) d7 X1 z- ? transpW =np.transpose(W)
, ^; V0 i* X5 [4 c  J+ n: Q return (W+transpW)/2# o" O( ~; T% I" ]# D4 x, {" Q0 ]
0 F5 f1 |3 q9 {% l
def spectral_clustering(data_set, k):
% l3 n  c- D: N0 Q # 利用相似矩阵S得到邻接矩阵W# w, y7 b3 Z' g- h" s- }3 _
W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
- G7 o3 t4 H$ d1 h #  W = get_W(data_set, k)  # K邻近法
. i+ R8 p* ~; r7 |% b2 D7 }6 b8 k, ]( C6 Q5 C" `5 |6 C  V
# 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）
) E) i& ^0 }& _ D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))2 n/ j' ]/ q' ]( `2 ~) Z  T
' v* S2 r$ v4 E. l- U' k! O+ G& A
# 计算拉普拉斯矩阵L=D-W
. f6 X* |* N  G- W, u" K/ l1 Y # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
, n% V3 K+ i! G/ t L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)) K" l$ z6 K- s
0 f& E8 T7 V; B" s8 R% ^3 c5 o
# 得到特征值和特征向量
8 C+ P8 M/ ]4 y# W5 k eigvals, eigvecs = np.linalg.eig(L)" a: B+ ?4 h+ e2 b% _2 r; \
2 G8 U0 v5 a7 F* i' c# C4 j
# 找到前k个最小的特征值（索引）
4 Y, @/ y0 z. r, c k_smallest_eigvals_index = np.argsort(eigvals)[:k]
: s# `+ `. U  o) x
# H3 e9 X" c' a4 q! q9 @ # 取出这k小特征值对应的特征向量，并正则化& e/ q" |, A% U9 d3 w0 n: n
k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])
: |+ m7 j  t  j( `! @. O
; M$ B* c! r$ v+ U5 N # 使用K_Means聚类) f* ~; X* Y5 M9 L$ D8 K
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)
4 W( t( ?- b/ F: ^* l8 h
7 s0 |4 ^$ c& p3 e0 c
4 U9 E7 @5 O2 ~* |7 z: ?5 F+ yraw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)3 k. k' a- E7 F/ j' B5 K7 R) G% D4 S
raw_data.columns = ['X', 'Y']
6 W2 x/ e7 B0 f( W! E; G, bx_axis = 'X') ^: V$ v2 Y% E5 {& A! k( C; J6 }
y_axis = 'Y'
; ^$ u% y6 p: _4 K; B$ Y6 \# N& \+ N& v- e: s9 i
examples_num = raw_data.shape[0]
4 P" U- e! K& }( X# _& w5 B! Btrain_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)1 g. o9 D/ ^) h: u5 }4 h/ m9 m
( G* z& F$ n# P2 ~2 X

9 i+ I+ h3 i7 U; b* @min_vals = train_data.min(0)
9 U3 Y) a) _! i8 c8 S7 `max_vals = train_data.max(0)1 W0 ~  Z* ~, e' ^- Y; l
ranges = max_vals - min_vals
( c" @4 P3 N8 X6 e' Z% snormal_data = np.zeros(np.shape(train_data))( Z6 s: m' j2 J$ T  H
nums = train_data.shape[0]$ `& ?- A9 ~7 v
normal_data = train_data - np.tile(min_vals, (nums, 1))1 c6 V/ z0 r& Q! S, Y2 F
normal_data = normal_data / np.tile(ranges, (nums, 1))+ z/ e( ~* n/ L$ o
% S# p5 P! c1 z/ l3 u* `$ @" z
labels = spectral_clustering(normal_data, 2)8 Y$ j1 M, h, Y$ v
. p$ w$ X# r5 z; P6 H! j
# 原数据# T$ W- ~4 o7 K7 j. |
fig, (ax0, ax1) = plt.subplots(ncols=2)
1 l3 u* O2 X0 M4 }- A7 [4 {ax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')
6 }  _# {6 S1 M2 m. m) [5 S/ Dax0.set_title('raw data'). E8 I1 L, b- t; y/ Q
# 谱聚类结果
) w8 S  `; u  `/ C3 I8 ~ax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)) D& O+ R$ n% q3 E$ r9 e
ax1.set_title('Spectral Clustering')$ U4 r; I* ~  n6 x6 J/ l+ [0 F

" t! X1 y9 f5 ~/ Hplt.show()1 T6 M" P: x# s1 s' v# K& R! ~

+ C; h- I2 u; D+ E& ]- |6 E# \1, J% }# x3 E/ D0 B$ Q
2
9 w4 g, b4 r* B: R! A3
  Y: F/ G% u5 B+ v4' a# g# k7 e* _; L  ^# R. ]
56 c" }* s: j- c$ h' i, V
67 j8 C. S, C# r4 U$ N" u  g+ w+ n
78 g1 h& V+ I8 `& t; k3 v
8
/ o  X2 \' X  o! z' Y7 U$ B94 x* r1 |; ^" J5 J& R9 Y
10
$ l8 D4 \6 Z& W5 Y! D( [7 T110 p( S  L% g2 z
12
  Q, v  j" ?; x9 l' V- Z130 O, B! U. z4 Q
146 T  b3 D, K  x3 `9 T. g8 [
15$ [' m: s" x' q6 Z
164 M4 y6 ?( T, c0 {" @
17
# o" u0 Z9 G0 [& ~6 f$ o! z18
4 [$ \- ?  @$ E$ ?, k19. M- _% r" V7 ?0 F- W
20
" }3 ~; V+ H- i3 j$ N) C& P/ t21( G1 n: }  K. J; ?
22/ l, {  |4 `0 p% F6 v
23' l0 ]0 j' ~  r/ s
24
1 O1 ?: w+ f% ^; V+ e" b3 v! P' V1 y25
* f0 l( z8 V0 k, {, _: @9 \26: E" a1 W% G$ N. K- b; |# r& j
27" ~/ z0 r% q* ~6 G
28( d8 }5 i- @# j1 I6 D
29
4 t( }- ^8 x8 y  t/ w30
. x4 x' y% u/ G0 |8 i31
6 ?4 M$ A" F, a; s32. _: F8 o1 w. q* ^- |+ Z6 {' u' y
33
; k0 E/ A; P# j34
* e& x! Q+ k0 F! |# M' A35
7 `5 t; `# s! N- k# h3 C6 R2 V36
8 q! v9 Z+ H. u% i" ?9 B37/ Y" M: R6 E$ i7 D1 K8 L
386 V4 t( s& R$ _' p, e& _; z
394 H& k$ ]8 x: \- O- i
403 |+ }% ^$ A, X) x; a, X9 @' `
41
" _! ~; U0 Y& e8 A42  _8 l6 P6 A+ T2 a: _
434 S* j! O! l/ c
44% {' q; c$ a  B0 I" \
45
8 o3 ]+ V+ i! c2 _46
, @0 X5 J* y8 }/ u  O( {! x( @47
; q7 c% b1 r* M8 }48
* x& y- c$ T7 l! Z2 m% g+ U* K! c49
. z) q5 a; b# Q/ D# T& D, E50
/ w* }% d4 ^+ i8 }( d& s51- X$ ~3 c% U6 Q
52
( |: l/ O  V4 \0 V3 i# D6 f53
' a8 V  p3 I. R. r. D1 ~54
+ t9 ~$ Q, b' j. X552 A& J( v4 N7 `' }  ^
56$ O6 u, A7 \6 g* R
57
# u) f: Z4 Q+ Y3 c58) t# a4 A+ b$ H7 d/ V# O; ]
59& I8 w* x9 p$ ?
605 @. l, X1 ]! j
619 A% v6 Z' D$ ?1 x4 p
62
1 Z- J' o9 }9 G' K63
2 I, S6 W4 V1 Z$ |5 {64
* K1 ?: f- n% _4 y) C& o65
( `# i/ e! c7 m: D7 E9 v66
; L" `- D7 m; Z1 ~4 C6 ^9 M671 P& Y2 j* V  V2 k
68
8 Q: I. {" o* }( G7 K3 k69
- b, S1 \; P( X3 R1 ~( {( Z70
: A0 S( B  \  [/ w# s71
0 P! L5 D# D" _% O9 Q' U! V72
' e* G0 i" X& O( R9 |. x73
, U2 @( V) K3 v74
8 ?& |' ?# b6 @/ W# x; f" ~753 Y6 z3 o+ W3 U+ M/ a
760 V, R7 W6 Z  E2 y0 h5 C. o: K
77! v/ }7 `1 z3 A- R& A
78
+ X8 G% |2 r( M) d  `* Z/ O. H791 O, w$ H0 p! w0 \9 R; y
80
# h5 D: u' i; B, [811 T& u. f1 Q5 y5 I4 P+ b# L, k
82
4 U. N' f" ?1 F2 e2 w8 y% H9 e83, Z0 s# L) r# ]8 s: [) E( F6 m
84
  f8 O0 v: V0 U$ T* n* ^85
2 y/ s8 t  ?7 x( K2 G& Y86
) v/ D+ T. n' j" l876 t3 N+ {1 L" X5 \) x
88
- ?' R, W3 z* C89) T0 H8 ?2 Z: e- z5 F! e7 ^: G
90) z; N: B  ^" R# b
91. Q: \1 \9 @8 B; B2 [
92
* C) S1 @& f/ x% y0 g  |939 z# O2 J2 }% s$ z, s% K/ k$ \
947 l' P+ e# S1 [: Q, N3 d1 R
95
. A8 K  e9 c: W7 B  e96
& h$ k8 v$ l7 m" j' \97# O) e) b& P4 {/ r' r7 b7 M
98
* X5 _5 j  G- \8 j+ C6 m, M/ g99' \/ z3 s) r; h& T7 ?
1002 N! c( {" n. U6 U1 J: t" U
1016 J: G# u/ u3 {7 i7 d& j8 G& E: c7 F
102- q! z+ Z) U$ |$ u0 q6 p9 B
103
5 m. ~' W  l8 g（高斯核函数）* C% R# L/ @: _' X
# D5 s: n" D6 |  ~5 [6 ]0 a$ ^" Y

" V# j& k. m. `# [（K邻近法）
; b" j  y0 n8 D2 \5 }7 ~. N
7 |; ~$ \7 L4 @% j
6 z+ u: U4 W* A! ^四：谱聚类算法优缺点% g) a5 X/ p: I9 L2 h- D, |7 ~
（1）优点) F1 \; {: z; f9 F
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效6 u+ S/ \8 j2 q) q1 `* [3 F: x
使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法
) q& v- H: S$ x  {* k- M" T% v0 m谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解
0 q% j/ W# z, b8 D2 k7 A5 M（2）缺点
$ P- T* A5 {6 {. W) N! [$ o如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
+ k% w9 A8 u: H聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同# |  k5 i/ C" z+ d
————————————————
$ |8 {# ]7 s* h% q5 l( B版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。$ A% @2 i' n: @+ V, d- m% L; E' E
原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494  O8 X6 M' s: {6 d0 j& C4 d

! r# S" Z. j4 S* D
4 B1 `  C7 I$ w8 p- v* |. L/ a, \