查看: 2282|回复: 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 n. w. @9 L+ ^# Z/ w- m return dist_matrix
. x5 B5 }/ Y; q' M4 c3 I- P1 M5 K7 o! `: I$ V
def get_W(data, k):. M, `+ a* U, F) A+ Q
# 获取邻接矩阵（K邻近法）
/ `7 w9 H; C) y n = len(data)' G1 z' y% a( y
dist_matrix = get_dist_matrix(data)
% z1 \+ E* i' C  ^1 B. x! k5 \. J W = np.zeros((n, n))/ g" Z* |. E9 a  z4 P9 X7 L7 b
for idx, item in enumerate(dist_matrix):+ g! k+ X: m( g0 z8 v8 _
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表
$ F& j. s1 d# }7 j! J" G& e       W[idx][idx_array[1:k+1]] = 1
( R3 R: k. M# M: x transpW =np.transpose(W)
0 E  g  K9 e# f5 E8 i' j return (W+transpW)/27 R! C0 t2 ?# _

6 k: t2 W/ D2 |  K1 `4 ndef spectral_clustering(data_set, k):! e/ z# P: w4 f& ?
# 利用相似矩阵S得到邻接矩阵W+ a! A' x4 Z$ c2 ~
W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
1 B" [; g# g4 I- D& Q* e #  W = get_W(data_set, k)  # K邻近法
$ H- n/ x& ^' \. J; H6 \5 _
& G1 h0 {6 j9 i  W7 {* u # 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）. U% ^9 V) |4 l% S, e7 V0 a8 z
D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))
8 i" I- W0 \' z$ y* y3 S* \* M# v3 n1 Q; _
# 计算拉普拉斯矩阵L=D-W0 I2 w9 B- R( u. g+ \. b/ k4 [
# 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
6 X. G: E( V# b) ]7 f0 Z2 w L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)# f; L9 n% W1 m4 R) H; V

) I; e6 @) F9 H. F # 得到特征值和特征向量
- X; i- g. j' q: {, ]1 Y eigvals, eigvecs = np.linalg.eig(L)
: S  A( u4 }- v) o( P
* H0 R3 T" }8 v4 u* Q # 找到前k个最小的特征值（索引）
3 S( v/ W3 H3 ~. n. K4 k9 K" S0 m k_smallest_eigvals_index = np.argsort(eigvals)[:k]2 H) N; F' q# }( w7 ~

  j( q( v2 v' [! V' y7 g; |# X # 取出这k小特征值对应的特征向量，并正则化
$ X, E& P# c  ] k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])' e: o% A. j% ]  T: e

0 [3 X9 W0 N0 s6 j # 使用K_Means聚类
6 H+ v/ s; `5 d: P( k8 v; u4 i5 F return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)
, p7 m5 @5 j( P$ ]& Z- f* @8 @0 z$ d6 s  f
$ ?/ W/ f" ~  ~* i0 f( T
raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)
0 j8 n1 W( A7 Y* a8 Kraw_data.columns = ['X', 'Y']
% }; d1 [" m) r! g8 Dx_axis = 'X'
5 a1 z' w( q0 w7 M% Oy_axis = 'Y'
8 r- v  i( C7 e' U9 f, f0 ~% ^8 h5 e
examples_num = raw_data.shape[0]" Q0 \' S. A; G" P3 ^3 f2 W
train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)' x. ~9 }9 `! v- g1 |3 b

5 c# ]& i) \/ T9 l' W
! U5 P6 H8 u/ s& Umin_vals = train_data.min(0)2 X% Q: a* a; n8 m/ G
max_vals = train_data.max(0)
& E$ W* e( A1 B6 u5 mranges = max_vals - min_vals
* W1 w& [) F1 I; J) P4 n4 ~normal_data = np.zeros(np.shape(train_data))# G; @3 A6 n6 U- T8 R
nums = train_data.shape[0]7 p0 n( G- E" y& g# M/ I
normal_data = train_data - np.tile(min_vals, (nums, 1))
# u3 {3 t" c, ~' W0 ~normal_data = normal_data / np.tile(ranges, (nums, 1))3 V6 P2 M  v) ^, q7 I
0 ]. {$ t# Y* i( U9 v, W+ A* [
labels = spectral_clustering(normal_data, 2)  Y- z! N+ a  R. M
7 g$ a6 G0 v& T7 U# E& A
# 原数据
0 i' V" o2 V- }/ wfig, (ax0, ax1) = plt.subplots(ncols=2)
: M3 `' [: d! d0 pax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')
/ s- |4 b6 H2 B; Z" P' I: vax0.set_title('raw data')) E! [+ l& W1 c4 l. H2 `$ a
# 谱聚类结果1 Z  |- t# q9 ~" g+ A5 h. ~! y
ax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)
2 P3 X  J- N0 c- B; b6 S: @ax1.set_title('Spectral Clustering')8 p# l, ~( b- G

, J. M0 L% ]8 w2 gplt.show()
' i+ V/ R4 [4 x( C$ J$ A+ A8 o7 z
" x* |0 P8 K% j/ ^3 r% A, f1
& I4 t( ]1 V, S2  a3 ?, y$ {! Z( ^9 e2 \$ C- Z$ {7 v1 `
3
& A+ h5 y& V# P2 w" r) F8 r, t4$ {8 E2 D4 d; a, L/ m5 {' r4 G( g
5
3 |$ b. {8 b8 b' r1 g  p6
" e0 `% e2 F2 E# C6 L7! ~; L1 C3 d+ M% V; e0 a( q
8
) s, n+ J. Q3 P4 [" N96 N  G- A( ^0 l+ S5 v9 S/ w! q( W& x
10
6 V- `. |% j) Q6 z3 A' ~111 a4 ]3 n" w: ^5 q) n9 ]& O6 g3 t
12
5 H7 R8 m6 \/ z# H) T13
5 Y1 T( X# \! X9 n5 ^6 Z- R141 v! y9 _* }5 j2 u
15
* {6 l; e& @5 A' \8 U) b( V$ x0 i6 r16
" @/ t. Z& B, x7 p5 L17. H: t& Y' R' ]# t( j  O" ]- b) c5 \
18' T& F5 F/ d* r8 V9 e+ |0 w" a) W
19- @+ Q7 y% @+ p
20' \" u1 M/ v8 `
21
- L1 r7 a6 w) t. d9 q3 n8 x- t22
3 |" K7 M# E, _5 o+ u( l+ b231 C, d$ F9 Q" K+ h" i
24' r# J: x2 `, G- w
259 y& L+ B! W% Y" {7 {
26/ f2 e8 G% J5 A: Q$ Y( \
27
4 U( y* ~( _( l, y) e28
" Z3 Z0 ^+ b9 V# K9 ^29
# V& @9 P, V. u3 H$ ~# t30
" I' A7 V, O! `; Q5 b# M  X318 X' K6 O9 E$ r! v7 |: C
32
/ J) d+ H" ]1 N33
/ Y7 F1 [2 `( i# j# _; G34+ ^: r( Z' u  i* M  c' k0 s% u
35
; D6 e. K* A* T0 q) A36
/ l/ ]5 p) F% X5 C- J37. W+ c% r: d+ u! V) |  Y
385 U" p7 P& L6 _$ i4 ]0 C3 }
39
2 v  U4 l% M+ H  x! I# p# q40
7 {! a) d3 g! l. h- P$ _7 h417 G/ J7 T' y9 B- \' m
42! ]. c8 z7 _% j# c8 t& E
43: I3 y: a7 d$ Z8 w
44, n( D$ s5 F$ A( k
457 I% u) C. i7 P3 y
46
! Z3 X/ I. {& k: v! Z" ]47; J* P9 g& X( Y; N2 I1 `  \
48
( R1 C. d3 i2 @& _$ Y; I49
502 D* Z+ F2 [$ c2 H* }! M2 Y, p$ O5 V( p
51$ \2 P# D6 ?9 T+ B: x; b4 V, ?
52/ J& s8 [# Y& _) _+ i
53
, }+ \* H3 f; x5 E" O547 ]8 @+ r  \' f2 N& R  s
554 Y  z+ E) U* Z% s: z, f7 J
56
1 v3 F: i5 |' D* u% T# v57
4 {; u2 B, x. }2 @$ M0 B  B7 i# Z58
0 X( X  C6 N, k2 X595 p% C  j& M/ S2 e
60+ \2 I( L8 k$ C8 L
61
9 K+ V1 q* _& N8 I, t627 T' ^5 Z0 p6 o* J  \" X
63" o* ]' N$ F* s9 }) ^6 R0 |2 ?/ y
645 n4 ^& ]6 I, y) ^) s
65
: u& z: W8 P0 M% n4 j66
# i/ d# ]& a3 O( I) u$ l/ i( {, P67
9 u, {/ C/ D) N2 G9 [9 |68+ \: p& ]# F" I. x
694 k$ J8 n9 E; K
701 J, J* _2 Z' t% v7 K9 b
715 z2 z6 X$ v1 N( p( S( A4 N: a
72
7 z& I, }' C- ^( [+ g  k& x73
" n3 K: |) k6 B74
: w! \* s0 H  Y  I2 k5 l9 n0 t9 Z75
, N: x0 x" t/ w: }" ?" U) V76: J' r. O. o' i9 @, m0 q( q
77
- E, c& n1 b. `78
% i+ d9 c# h( `797 i, b+ b  \8 R- c0 t1 ~! _5 h
801 T% y+ K% Z, |  p5 V; L8 a
81' |5 O% ]8 G2 R! ?% Q
82
; ]* a' N, y+ M5 a9 o8 n3 G, y: F83
9 v4 Q5 w- X; w2 U; _84  U( R# y7 C6 @& V0 I0 `0 y
85
6 d% D! u1 T; ^86! r7 m5 Z2 F" `& M0 \; b
87  y  U" }9 a2 c7 V5 o4 b
883 [3 q0 k. v. J: ^! d( U- J
89' r: L/ k! i2 i8 k) H* X
90
- z! y" ]. F2 j9 K1 r914 a5 d; b$ J: m  O
92# P/ Y  u7 R( r7 `3 v
93
) X$ i/ b: H) ?+ }2 b4 {94
2 Z; I4 g+ r3 `2 V; E95
. }& u, \7 P$ d2 ?: \' A" }969 Q9 z2 w  K% ?5 W( r
977 @4 M) v1 V/ X
98- S( ?7 U4 D# z( I
99/ g6 K. H( K" t2 S1 T  }) p4 y
100
! q/ g, o$ `, J4 s+ c0 e5 d101
" B9 m4 W# E# }  J102; P3 w+ u# D- }/ r, m3 d5 K1 o
103$ z, A- v1 \6 i- s5 G
（高斯核函数）
' T! {3 N, ^5 D$ ?- e
0 X' p- @  ?$ G' ^% _
6 y! ^  x2 L8 B( V（K邻近法）
' I" Z2 N7 p+ N7 N
0 w& D* _. ]2 ~" ~& u* h* o  q
/ Y! l& `3 l+ {# ^* L- I. Y四：谱聚类算法优缺点
- \: E" }" ?4 Z（1）优点
( R3 d$ G9 t+ T$ e3 E3 S谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效. O0 E$ e2 W7 i+ C4 l
使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法
* a5 Z. a' o2 u3 M" K谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解
' \3 x" S' f( n' D) t（2）缺点
9 Y- O$ y$ X/ n) O" U如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好4 G( o% z( y1 K. E) E7 x( q. v
聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同! G2 \+ `$ V  e7 U: H
————————————————
& x; Q8 _. z# f: {$ Z) R0 U, r版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。8 b/ A/ J! X* J" J8 E+ {; X+ G* |$ `
原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494% n0 O: j5 E7 ~$ A0 M: i# i
3 j/ h" x: E. `

0 Y% c% M5 H1 V" r; o% r