查看: 3043|回复: 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 @5 ?# R2 D" y$ x' ^ return dist_matrix/ R, |* j% h, Z- G" d9 y+ [6 E( Q: u! V

8 U8 E9 U% l9 b; }' G/ y' D6 Gdef get_W(data, k):: @& Q/ o% ?( k- n2 P; p+ |
# 获取邻接矩阵（K邻近法）1 e/ v; r3 e& m" b( f) j
n = len(data)7 `4 A7 s( ^# M. k) G* G: q
dist_matrix = get_dist_matrix(data)" D2 q4 P3 a* V/ X, H
W = np.zeros((n, n))
& b3 p0 v- U$ J) {2 y for idx, item in enumerate(dist_matrix):4 v4 u- t4 S8 x6 H: {# N9 M
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表
8 Q* P( `7 \3 a  s       W[idx][idx_array[1:k+1]] = 1
( h+ p. i8 j  j# n. |+ N transpW =np.transpose(W)$ j. \( j/ q0 i8 P* i( l; I
return (W+transpW)/2& N% T, h6 O, @$ `5 S" l

" |- w8 ^/ R3 D4 Y$ wdef spectral_clustering(data_set, k):
+ Y6 D1 b; u) `0 }" w1 ^ # 利用相似矩阵S得到邻接矩阵W
& k; x* t  L: Y" y* g W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
. @! o; Y) `% x' w1 A- R$ ?, j #  W = get_W(data_set, k)  # K邻近法
. H$ O+ X$ T& U, p( _( ?9 G5 D
5 k5 x4 T4 e; d- p+ j% H7 C # 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）3 o! r3 `& T* T" D, K
D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))
9 m/ G; B* y- U  ~1 t$ b
# M/ s/ b4 @0 F1 E4 F& T0 @ # 计算拉普拉斯矩阵L=D-W
+ v/ ]5 r! E6 C # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv0 ]% D, U! C: n# c, g. e! v
L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)
+ c. l  s7 d. T& t! e0 v
0 W, K- @5 G# z # 得到特征值和特征向量
1 P5 f  G9 [' [1 |! P+ j eigvals, eigvecs = np.linalg.eig(L)
0 V* n6 c4 v& y, N9 X; i3 m2 q6 i: @/ v. V; C9 ~, |* V
# 找到前k个最小的特征值（索引）: T6 F' n% R! T) ]# |0 J) i
k_smallest_eigvals_index = np.argsort(eigvals)[:k]% {4 Y( U) k, m) K1 h

  w; Y, R! \3 k1 p. k, @6 c # 取出这k小特征值对应的特征向量，并正则化
: C* R8 i% w7 A k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])
6 P6 n/ T" v+ j6 P- T
6 V5 x$ M7 |% X3 [" P& g; u" ^2 d # 使用K_Means聚类
9 J0 _" Y, f5 p; O+ R1 P" | return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)
! X& t. q+ S) V. `& T" B
6 m2 E  E! ~# r, g, T2 M" d
+ I! b/ d. v9 A5 M4 G6 {6 Oraw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)
1 a9 `, U# p, _' ~* R0 d+ wraw_data.columns = ['X', 'Y']
3 _# U0 t$ Z1 O* Wx_axis = 'X'/ m! D, Y: }; W1 n0 x) u; {
y_axis = 'Y'
2 A/ H' n4 o  Y  i9 o, d9 K! g" K* m6 `' `& R
examples_num = raw_data.shape[0]* ^9 h8 y* p2 [% ]+ |
train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)
. P+ D2 k! J) Q" v$ {; v8 ]- G! ~, C/ e) c6 k2 K* D& q
" v$ k& f! W% ]# e5 T
min_vals = train_data.min(0)
: D$ x4 P( h9 G- ?7 Cmax_vals = train_data.max(0)5 E% U* B8 W6 ]- [: _
ranges = max_vals - min_vals
& I* [  [5 E) O7 ~, c  Bnormal_data = np.zeros(np.shape(train_data))
0 a/ I  V' T; O6 z6 _# Znums = train_data.shape[0]( l# p4 E  U6 ]. X+ p
normal_data = train_data - np.tile(min_vals, (nums, 1))# C" l7 ]" y8 q% j- M
normal_data = normal_data / np.tile(ranges, (nums, 1))
" U4 k% E$ g7 ^# v7 A9 T6 w3 q4 H9 e% d
labels = spectral_clustering(normal_data, 2)
/ \) Y& _; L5 u; y0 x: ]+ O
# l& e9 d/ D: `: ?" H# 原数据
% ~- U# g. a( X" cfig, (ax0, ax1) = plt.subplots(ncols=2)
  J! d( }5 C: ~" Dax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')3 P! q/ H# A) j0 z2 ]) k
ax0.set_title('raw data')! V# Z" G; S* ^- K5 ^8 a4 Q
# 谱聚类结果
% M" M1 Z5 F3 w$ k  @6 Bax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)
6 V% Z) B% o- Dax1.set_title('Spectral Clustering')
3 G' x; D4 B; I& x# E$ W6 @- b* I; B- C* f& _- D
plt.show()
0 I) m5 b4 Z0 k4 y7 I* K% \& O
9 |9 {0 L  P5 U( v7 d1
4 }; E0 w, w+ @23 M9 X- ?. M1 o" U# W0 e/ e
3
' w, s& Q$ |6 v; F  S4
  Z+ l" I7 p- D- O/ V( |0 B5+ e  L, ?" @6 w) `5 y4 }/ }
6. Y) y0 P$ P9 z
7
1 A0 A3 P4 K% G# _9 Q0 s% w8
# m3 G, N+ f" c94 M" H- d) I3 M. L/ K  ?" r
10
" U1 b% Q/ K) |) B8 o11) I# U& G0 e3 C+ B9 `' o! I& Z. k
129 |) Y5 a. j+ x: |7 l& M
13
& l2 m2 }8 ^7 t* U14
% N7 V( z% o9 y6 z$ D0 w1 g15
0 x; j$ V& F/ h4 g8 R0 O( K16, F3 B) W' E" F  r1 \
17
- p( \* m1 l: r7 b. c" T: M# b18
' j. K6 m# _# I& I, H! _( P19) g# B+ ?' @6 R5 s7 C% k: m
20( z2 n( d, O# M6 o6 F9 v1 d
21
  A4 R. ?- b6 g" O9 j2 w, \3 g22
+ _8 x( O7 u9 B6 j233 k9 A. a& J, {# E7 v
24
9 a+ B3 k( w+ P) }* c4 E251 D  Q6 H1 x8 w
26
5 ~9 T+ t. P* S6 ^/ R275 P; U* I& s0 u1 T# q" s
288 ~$ I3 h5 O5 d4 K. |0 @
298 Q  b2 A* N2 w$ e: A: X3 V8 w
306 h7 k2 X9 a( q1 A! \
31
2 i. |; v0 @2 \# x32
8 b1 n/ u" W0 t; J8 m9 k; X33  U9 s8 w& Q5 U. @
34$ P8 l" Y" M5 N
35
; q0 N7 [- `3 W! Z: P" ~+ f5 E367 p1 k) @1 u+ X' X  u: [
378 y! L4 v& j* n5 I" V$ D- A* q* b
38
" j9 b2 W! z9 e3 E! a392 t8 F9 C9 {' S# S( R7 }
40& t1 M8 f: O; [
41* g1 F6 ?2 X" J9 k( [
42. ?. _% U9 y$ H
43
- Z2 v5 @6 j# f8 m, w  V. Q: \44
" C( W1 y1 `- l4 D6 T45
& s' g$ T: N0 o46
, K2 G& r0 _8 Z47
. O& }/ s/ s9 ?. }$ I0 l, t* w, Z486 N9 z2 K# J# t, e
49
0 K- n% |* E/ W* E. S/ L501 w$ F3 i1 j1 }* q* C0 D  O, @; S
51
' \& |# J, ], Z+ A7 s! y52% J0 U- h- ^! S
53( L. [  R) w( a9 P: d  ^
54
+ M* ^/ D& r: R! K5 V2 o55
9 J" P7 S8 U. {8 ~# R0 x56* V! X5 l* S6 n& q% {" o9 b
57
+ [9 Q1 z9 m# D( w) ]6 _' a58
; [# G3 K0 w% S; f8 b59% |# U" i  b5 Q/ J7 p+ l) j1 O
60' N$ W; m0 y2 H
61
% Y4 f& r# F3 u# Y62
  `- l! L* f! E! W& u9 c! \) G& D63
4 z' k/ b. M0 \0 a7 i6 o64
1 Y/ m. E6 d7 Z1 b+ U9 J65
7 Y7 G* k! I+ ]- U* p+ I4 J8 \; {66/ w  n; z& I2 }* o9 j$ v% F' k' P) r
677 e4 Z- f1 f1 T  H' b; ?" H, g
68( K) ?- A4 S9 F1 t7 \
69, u1 U" ~# p& K: e2 l) O
70
4 S: t& t  I+ z/ t2 g: w. F71
( Y# w6 S6 {. x$ L. G8 O72
) l& c' m) _/ F% R9 \73
) a) x# _) |8 ~. Q" i1 {1 R/ f74
  z7 ?8 ]1 s) K0 {9 e+ q, H75
+ e  K4 o8 J. i  B' W760 u2 {8 m) t0 f* D
77
1 v5 K, i. E! }# x, P78
/ F- n8 X% R( P9 J0 w; e$ e7 J. a791 l; {3 s  y( N: Q0 R2 c7 D
80/ d7 C5 S) {+ C8 I
810 [4 s1 m$ V, S
82: H+ k) a5 [' T3 W$ I4 h
83' K' p  q* D* ~4 T5 c5 i' j
84
: ?. I( o2 M4 g. p4 z% r9 z( z85
2 b" a6 b7 u1 x86/ W4 B' v$ s3 a  W6 G" H
87: m% n$ u0 a  ?4 m& I$ U
88
* T8 l  I5 e& ~; p  U- p894 C6 j: S" L, v/ G! d7 t- l6 t, e
900 F( k  Q- w) k
91! C( v0 i/ ~1 K1 }
921 k5 w" r6 _4 T" k; y7 y& V* Y" g- z
93
4 f; X8 m* i  U" ^/ E94/ H5 Y- C3 a( l: f& w5 K: k# E: [
95
5 G( f! d: g( \$ u/ v% M4 J96
$ x  ?: X2 {# O+ s97
% U4 i' `6 Q% w( Q0 N4 m98
4 P& T5 P! j( L7 w99
! W+ f) @( H5 ~- N100' s# A. A, Q/ u9 \/ ]$ T
101
8 J$ ]8 x; S* Z$ Q( J! o2 c' h102
2 Y/ ]. q! V1 X: K" A! b103% e  T3 a8 D! q. S+ B0 x
（高斯核函数）0 y: q- [# d' b+ {$ P0 u
' d. V) l6 o% D* D: ~8 Y: s' R+ n

! L% \% v1 r9 o( K* j3 _; G（K邻近法）
7 U! m4 X8 o3 y* K) R- P  _) ^! n% Q# C

$ ~2 e' d! z  \+ k* h, K0 i四：谱聚类算法优缺点/ E' o" F5 g; a' g  j0 a
（1）优点
9 E  c# k, Q6 M6 I# k& G! G谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效
0 |. O" U+ ?7 G5 o5 `( ~0 [0 L使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法9 o; J, P% K. H  L
谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解
& D# v0 v1 K( P8 ?1 c, d. c1 e（2）缺点6 m  l  n% ]& g2 o. e: M' u) m& j6 ]6 z
如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
  S0 M# D1 n2 O5 h+ e/ P% C聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同7 E) V4 @3 O0 t3 u
————————————————
, [6 }  W9 {  W8 a9 I% L版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。# k& h' F7 ~# o$ d
原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494
1 R& W% S) M* S1 K0 L# o# T- {% q0 Y$ _  q8 y; p

0 h* i) g$ I2 s' V% Y( i