查看: 3025|回复: 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])
) K5 e+ q. X% z return dist_matrix
5 ]' g( x# Z; ]
, Y. d/ ]& W8 c; G- ^$ Sdef get_W(data, k):5 m9 @% O, H6 K$ t9 n
# 获取邻接矩阵（K邻近法）
& T) ^/ q, A* v/ n  e) } n = len(data)$ q1 v- u; R4 e) i7 i- |2 G
dist_matrix = get_dist_matrix(data)& J- x1 x! X$ s7 o6 u: u5 \
W = np.zeros((n, n))' q; ?/ p! c/ z3 p8 V0 p2 j
for idx, item in enumerate(dist_matrix):
6 B4 J! _& \: A. P: ]8 |       idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表
7 _  P% |. T, p, p6 k( B       W[idx][idx_array[1:k+1]] = 18 w8 D" d6 U& H& G
transpW =np.transpose(W)
) o$ n9 N% {* E return (W+transpW)/2
: J6 r' S( F: ?7 R( T# m( ?) T5 |) E- z; i% \# T$ H
def spectral_clustering(data_set, k):( }. q9 l3 |6 M' c+ c: e
# 利用相似矩阵S得到邻接矩阵W5 a/ J$ d# y% \8 u7 F$ ~
W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
2 o" x% V8 B0 z) F* W #  W = get_W(data_set, k)  # K邻近法! B" G! k# Z4 N  Q. V  ?: [

, \. w4 _7 P! w! i: y. q3 j # 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）
$ g+ ^7 V3 L5 N9 z D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))
9 z. `9 y8 t# i  @2 \% v# U5 }, M. |7 S
# 计算拉普拉斯矩阵L=D-W$ g5 P7 F/ \; H& {# U( b1 V
# 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
2 v- t# `/ A; K, \ L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)9 @4 m: l- k$ X+ t: M  ~) W

, U6 s0 N& w. j. q1 `) ` # 得到特征值和特征向量
( H4 }6 {& ?$ P) { eigvals, eigvecs = np.linalg.eig(L)
. X+ _6 A+ L& S$ W
- [( t" B6 `% X # 找到前k个最小的特征值（索引）
: N9 r! N& i: T0 J& R: _: t k_smallest_eigvals_index = np.argsort(eigvals)[:k]
4 C- |% ?7 r4 }( `0 J, }
4 i( Y5 y2 H, e6 l # 取出这k小特征值对应的特征向量，并正则化+ R$ ^) W3 u$ s) i; m) V
k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])
5 K; e) b( l8 n* m5 r- B! }; {% G1 R. l& y: G. r9 [& `, T
# 使用K_Means聚类
4 ^, j/ L' [/ K8 n return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)
4 p! W4 u( b* @, K, ^: J% ?4 ~2 I8 e  m" b/ O+ i7 _/ e. s

! S/ d1 B! q' F, b3 Braw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)
. O7 X" B7 _) A' D8 a2 H0 nraw_data.columns = ['X', 'Y']
  X; q1 N3 c, O) L; d6 jx_axis = 'X'
) A1 Z1 M; g$ a' `' h3 v" X; by_axis = 'Y'# W1 s, I% b, r
/ |; t. H* a! F
examples_num = raw_data.shape[0]/ V  j5 W- g0 L+ ~5 N/ \- R6 R" g. X
train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2). X4 E7 z3 S7 C7 |4 {

/ l9 V' {- B/ u" E* b0 a
, z" X* J- j: r( X! q/ E8 Omin_vals = train_data.min(0)0 K6 E- V1 Y$ Y8 d; e5 S& q
max_vals = train_data.max(0)' {0 ]1 k' @2 m2 y/ W7 p
ranges = max_vals - min_vals2 a* k: \: Y/ ], Z8 y2 y4 Y
normal_data = np.zeros(np.shape(train_data)); J* C/ S  _4 I2 C( x
nums = train_data.shape[0]3 h! h; r% X  I
normal_data = train_data - np.tile(min_vals, (nums, 1))
" W% U( q" R1 e% N# C+ ]; X. |normal_data = normal_data / np.tile(ranges, (nums, 1))' ~8 N$ X! A! D

$ @' E% p3 {% u% blabels = spectral_clustering(normal_data, 2)
/ v; [5 a4 g' A6 `) y" X
3 M2 s& `* }; R/ x" `# 原数据
0 O& M5 K; s% Ifig, (ax0, ax1) = plt.subplots(ncols=2)
# F7 ]# V8 o# }$ Rax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')% Z. B; V( n' n0 I' A1 }
ax0.set_title('raw data')
0 ]. E" }0 h. f/ z# 谱聚类结果
3 I0 J8 ]" ^7 F' ^9 Hax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)8 d3 a* b, K- ~. d" M/ V* J
ax1.set_title('Spectral Clustering')! W% m) W5 b4 I3 T/ i; V7 {

1 Q- V, v6 f( Splt.show()4 A4 J$ W6 u9 o- l4 _$ r
* N1 S  q0 X" l: G* W% N- x8 p
1
9 F8 M7 u5 s. @1 ?/ c  ?% v2
. d. o9 Q' o, F, I: \1 ?/ m' g3! h2 J* U/ a7 Q* r
4# d7 j) V* X, _2 n- [( a
5
* X! s- W8 }2 k& P/ f5 v+ T7 q6
8 q  q3 {5 e; C4 P- ~/ U7
9 `1 ^. v% V  Y* c  B- v3 e8' m! o+ J' M- M- p4 x
9) W. k/ {' Z+ [# q0 ^! D1 V* Z
10. B& `( P+ d5 h( \' S& _
11
  K* c6 _4 ^$ D12
. E" E1 X+ p$ d* k4 z+ c0 [13! X5 ~8 h2 X, D2 v8 ^
14  T* T: Y3 y3 R3 T) V" i
15
6 X  i. _6 x" s+ V! g16
! n) L3 f0 g: t) L9 {7 t/ {17
$ U1 Q9 ]& r3 B- W18
$ [3 O& i) C4 C6 C. x19
0 r, H* X) R0 m- R" x20
9 I) ?2 H/ g" K4 F3 d: p21
& t3 P6 w+ r/ |, O7 ~& y- L% T22
: M: c# r& {9 @: A23
5 M. \" n. U  I6 O$ A+ f24. u9 b8 t+ F$ G% C2 Z
257 E, b7 X2 b. @% u7 ]( K
26
- Q* T9 P; w" v* J8 t8 u. N7 ^277 w6 d% _9 A" }. T
28$ v4 f" G! I/ s( h
29
' ^1 M% m! _6 _4 A3 M0 i308 V: U0 |2 c( `) p0 j* _& C. K5 y
312 f- g/ o/ ^3 A+ E1 W+ @# S/ l' ]
323 N, T$ x* l# {! b  Y- o6 `: z
33- W6 O. a7 H' V# w7 |
34' g" |6 h( {7 _2 q/ R
35
+ H! _" ^! w- s36
8 d$ Z, Z1 y1 k5 N# ^. x* e) n6 u37
8 [: I( E0 U+ f1 `38! X, s( X8 Z3 j, p8 q/ |
39/ I% P8 W) x% K2 i6 b
405 `- C- r1 Y" w3 E  V: e; B
41
5 E) J8 `- b5 l' y7 |" s42( M# u" z" g5 \; s6 U% q
439 h. _( K! z: d$ a$ i, a% J0 M: `
44
' D7 O2 X0 b6 K. @45) b+ _( J" [* c( O+ U
46( V, X2 i9 F6 k
47% }5 @3 L8 D0 h4 e4 G- l
48
2 q: O" h/ X& D! C' ?49
( C" j! l7 G3 l! }  G5 ~509 _, S) B& b% z2 ?! J
51
) ~" \9 ]; N4 n% i. q6 @, v8 Y" M4 _52
+ S6 ]) ]$ R1 s* v8 n# h6 b9 H: d536 L1 j3 A5 q8 t; o* c4 Q" {5 y6 l
54
$ w, p) N. }" a) _1 }7 [( Y55% q/ i# O$ ^% K3 G  m& C
56
* J: R! R3 V# h0 [* P57
) z, @  u. T7 n58
% k4 Y5 }9 X* ~1 t* [59
: [9 L$ ^! f/ w  h8 e( T, {60; c# C. O% b- k% [, r
61
' K; y, p3 T2 w0 n62
9 [9 F" o* N3 S63
2 W0 `0 l0 T) N: p641 B" o' _+ [- y1 Q$ V5 L* {% H0 ~
65
: U% [) K/ Q( v% y66
/ r+ O7 z* D2 |; i; H. n67
5 U' U- N: M$ q" V& Z# |) c68
3 Y* K/ y, X' W/ j69
7 C8 I! Y5 L& z, ]; ?2 M70
- M- j+ R3 T/ C: e5 x- E71' [, v9 W# m" P4 L4 A
72
; T; z% {+ L* B% H) o; q2 w+ p73$ x" D) d, G- \0 T% {/ j5 U6 F
74, E. n# S2 _: U) H6 c
75  U' [& c+ d9 Q) M) j
76
9 ~; D* O9 M7 c4 X. q4 P5 K77
; }( Y0 [2 o. X) T' P8 @; M78% ~% }$ F+ u8 E7 M6 j
793 ?0 [( r5 ^. G" z
80
1 o  Q$ X7 Q  ?5 ?+ t/ B81
& j; K8 ?$ b9 P7 S0 u7 v: k+ h82$ @0 A) Z; j: i
83
0 `$ X# L: i& z: U4 q, i- T84$ T$ F5 U9 g+ c
85
+ h$ P1 C( c, T86
, J8 n2 X$ T- B* @; o4 T87
2 J/ D& T; m8 _1 E& g5 `- {3 `8 ^88
% d" Y4 k4 m' c0 J1 E0 X89
4 i; M# ~( X& V0 M2 D90
+ N& g$ u/ K' `+ d$ E, O91  z# S6 r1 A8 _+ K0 o
92
, E- ], O, o1 F9 \% A6 ?93
! p3 {6 h: j& `2 ?0 v$ {8 v: j$ l3 @94* O: [  z6 G/ A! t$ B
95% Y6 q$ P/ _6 R/ V7 d6 z/ f# {
96
; U, R9 o# d& q" Z; H% J3 q  J" H97
* q: T  |. `" V+ O! _3 U98  ]* z  B& f) \, A, W
99% J9 w8 M0 P$ c$ [( |4 L
100
8 P* [5 v% @4 v! \5 q  x6 J: {101' r" l3 Q3 x2 d$ G
1025 M) X9 G3 e+ I$ C
103
1 A- a! y4 b2 B% t3 T( k8 b（高斯核函数）
0 }6 L1 A7 Y6 @
4 l% \# e3 p+ f
% O) m2 F; y' a$ w（K邻近法）
2 V' w9 l- a- t) U% q' r# v- X/ N, r
% Q* w  s4 w2 ?, a, G. O$ [; }: N' h! B- y
四：谱聚类算法优缺点0 A$ i! `& N/ ^/ I0 {
（1）优点8 F0 ?/ r5 L/ x# b2 P  C
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效1 Z' J/ t9 }/ i- \& A/ H6 ?
使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法
* H1 n0 T7 L( y! X4 R谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解
2 O6 s2 h! G+ l2 |! m（2）缺点
' y6 g, a; G3 D2 y/ N8 Z8 z如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好9 p* T; ~+ x1 b8 `9 p
聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同" [9 s0 v5 }+ y0 \
————————————————
' p' B5 y& ]' X& m7 G8 E: k版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
2 A5 Y. l$ D  {- \原文链接：https://blog.csdn.net/qq_39183034/article/details/1267474942 y& ^! v0 }; V
( m- Q9 y3 ?. c1 Z7 Z  ~8 @

/ L) r! m8 G' y9 b) C5 A