查看: 3032|回复: 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])
$ r* ]% W8 u1 Z' Q return dist_matrix0 e: P; b( o  j8 ?% z
: K3 W0 ^2 p; g  T) z/ c
def get_W(data, k):
5 F; |8 I( u( y; d$ y # 获取邻接矩阵（K邻近法）
, U  j/ C6 w) I5 b  }- p n = len(data)
1 y5 a0 _4 u/ j) L) s) L dist_matrix = get_dist_matrix(data)5 F/ \+ v3 q  _: F( R
W = np.zeros((n, n))
7 N  U/ Y* I# l% j3 `! t for idx, item in enumerate(dist_matrix):2 ?" |: V& K/ y8 Z! j# E
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表
3 j" e+ [8 s8 E" B' l: i1 L       W[idx][idx_array[1:k+1]] = 1( E% l2 T6 }( ]7 v  C+ M8 |
transpW =np.transpose(W)6 |& U* s3 z6 k9 m4 G
return (W+transpW)/2
; @, f7 z8 Z/ @) u: c7 F5 K/ |0 B8 V/ `
def spectral_clustering(data_set, k):: W5 x% B" d* A, U' C1 l, w2 p
# 利用相似矩阵S得到邻接矩阵W
  o3 Y! z4 l: Z" e8 n4 k% F/ V0 ^ W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
9 r. v% N  T- }9 r3 {  l& j; e #  W = get_W(data_set, k)  # K邻近法/ o# n8 S9 o  k8 i* C. W* K, F1 _
0 _, @) y. E' d: [/ f
# 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）8 q% f7 G& h2 B" L) F
D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))
. H0 n$ p. W6 d8 u* h2 c- y. E- d* J
# E9 @" u- L! ^6 ]4 v # 计算拉普拉斯矩阵L=D-W' @) X) j) j6 }4 }: l
# 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
0 v5 h, S. V, ~" B; `) M& k L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)  A+ q! Q6 G2 ^) _8 S& I  c
6 G% m  D6 F( s) N$ n
# 得到特征值和特征向量
: A  R( C7 a# x8 ?4 A$ m eigvals, eigvecs = np.linalg.eig(L)( Z2 X  d( p& z

) a7 v! A% E9 C  u" h # 找到前k个最小的特征值（索引）
7 N/ G3 z/ r. l$ K5 [4 n k_smallest_eigvals_index = np.argsort(eigvals)[:k]
4 r) |  v% Y! T/ j6 C/ L+ I5 P7 g; b! C) ~+ l; ?1 @* y6 ^
# 取出这k小特征值对应的特征向量，并正则化
. F. O5 |8 ^, M$ s k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])& n  k# B! V% C/ g$ ?, X
3 j- Y( Z4 F/ P' C
# 使用K_Means聚类* W# o- @+ i; ]* k, i8 x9 `  X; r
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)
* }2 D1 u! f+ J6 ]; {. g6 i  S
4 _; X5 ?8 f9 p- I+ n; m' F. D: h5 N+ X
raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)& Z$ f# _  f" }4 I
raw_data.columns = ['X', 'Y']" G* R  B2 n8 q( L  q8 h# t
x_axis = 'X'# z1 d2 `8 z; i
y_axis = 'Y'. T# x& R9 ?8 w2 T

examples_num = raw_data.shape[0]' X6 d* \% b3 {6 O7 B; L. t
train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)
' {$ G" ^% u* Y! p8 k
( t* l, p4 _5 i" o3 W2 t1 P0 T4 e1 p) ?
min_vals = train_data.min(0)
0 ]2 ~0 _5 l* r/ [* _/ Tmax_vals = train_data.max(0)
- i2 r: r, m- `. `ranges = max_vals - min_vals
4 ]9 k4 D. h# ~# }( x/ qnormal_data = np.zeros(np.shape(train_data))
' M9 P1 Y# @9 H  ~! Lnums = train_data.shape[0]
( B* L( t$ T. w$ `; r& a+ q& xnormal_data = train_data - np.tile(min_vals, (nums, 1))7 m3 t% T8 _  W3 Z6 c
normal_data = normal_data / np.tile(ranges, (nums, 1))
* E; \4 ]! n) b) M$ R9 N9 R! B# {7 x+ Q8 A6 y- l9 ]0 |
labels = spectral_clustering(normal_data, 2)8 |  F: o$ l+ @0 P. D0 H

0 @9 \; B- E* y1 \$ D3 R# 原数据5 f8 j& ~( A$ t6 `; N2 ]2 i
fig, (ax0, ax1) = plt.subplots(ncols=2)
9 t; s% f5 w4 C5 W) M( nax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')+ j4 f* |* i  a& p( z, `( H: ~
ax0.set_title('raw data')$ N( a9 V, H9 r# ^  [2 G5 Y- K
# 谱聚类结果
5 b) ~) @  O* A$ u$ h9 H  lax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)1 |! }6 k9 G0 c. `8 }3 i
ax1.set_title('Spectral Clustering')
! {9 r; t/ N4 G4 c8 Z
! l4 l9 Q: y# [+ J. mplt.show()
( r2 `% C* e* ?8 R# O
# m. g: A5 k! L7 i1
# |' E% Y+ Y2 R2
  J' o8 R9 {- R7 @/ Z3
9 ~7 U6 O! L7 z% _& U# P- B3 r43 I/ g9 L" {5 l+ U! p( e; \6 \
5
) {2 k0 j, S0 @& f  j6
  \/ N3 L7 t0 a0 c+ K, C7( k. H# m' J2 _/ G
8
5 z0 H( e5 @# ~+ D9
9 {; r: d1 C+ i; O  k3 T3 f10
0 \% W# ~1 s7 n2 J11$ y1 \4 ~1 Q! j, n5 ~
12
" b2 m5 w" G' c1 o139 V$ j9 k5 R9 N% _6 b0 a& ?, H4 |
14
' u( P% f% y. R/ F/ ?: a& l- t  X151 e5 M2 [8 C& P$ S4 o' ?- b
16
! A+ ~- T; I0 U. x! z+ o! e, k173 J8 ^( H2 \7 h" N1 \
18
) V1 x# s' G; c& ?2 W; N' b9 Z1 i: i19$ F& N9 h+ x% D9 V2 p* j& h  W
20" T6 S7 R8 s$ H6 O  [% {- r
21
% M' T2 V  d' M6 n, Z22
# ^, j+ A8 `2 {. P( W4 W  Z23
, x6 V9 Z$ Q1 R' G8 r! I24
" c3 ]% [' ?" j, V; P25
9 y7 d- y- l7 Y; F9 D- s2 A26, J! {. K( q: M) X
27
( H# N0 A; q* w+ A7 @) `6 X283 m( Y# h) k2 G# f
291 W. q7 S0 s. V% N6 U3 N3 X
30" _/ P; ?( X: E, W
31# x/ Q# E- {" J9 J! y
32- ]/ s' ]6 D0 B
33# Q0 x* u. E/ a& c9 p) l
34* O9 p  C/ h: \# I0 z2 X; R3 q
35
: p- w( z" q9 K4 b36- a% d% U* W& q, M
37
5 Y7 U7 z$ n1 {383 Z* s6 t& i8 |, v0 y* U
39) R9 Q9 T4 i1 X; k4 J' }
40  W1 m0 }5 C, l" `- \
41
. Y% o( ^. ]/ s5 A* y42- D" s7 f$ ?- G. M
43) D: M' H; F% L
445 ^% p! e8 H, y' ~5 m: T4 J; z
45
; @: h6 q: g* Y6 ^9 g$ a, k* H8 k46
# h# H$ `1 X- k. e47' ^/ h/ U" z' _. U
48
# [* Y, }% Y7 a1 P; l49
  y. t/ R/ x1 ], Y3 w% m# z  S50
3 P) |4 t3 I! d. e513 M/ G( _9 h* _( i
52* U5 c* I( O' J  m0 w+ V
532 q! e0 }: F4 C9 t
54
0 g* ]+ A% G6 h2 g* R% H55: z1 c) K# ?- e( |0 Y; ]8 v$ x  }
56
' Q& b1 s; q" L3 ?  A  o8 ?57
0 p0 ]9 c: C' S" d- e58
6 E. N1 U3 k- i59
9 M0 J% `  z5 {9 d! R60
, L8 f, c0 ~+ ~1 C5 t61
, V6 O0 c2 {& B623 R" I; ]: z, H, b3 u6 m0 T
63
" e$ V/ [. K$ K+ u, L4 M64
' f8 _+ g, J; q6 I8 _! D653 E9 I- s1 x" }* G/ Z+ T8 H
66$ w8 J: b5 |- S8 E  g. `6 K
67
2 P! r* Q. s- |2 W: k: w68
8 N" [$ X  [- d3 `$ p% r7 a8 W69! q0 l" ]. B5 @5 |5 u8 A8 W% X
70$ {. O' J1 u( \9 l) _0 j
712 X. E! y& G+ |0 r1 f; o
72
2 r$ Y) L' ~- P73  L7 _6 I+ |) ~# ?
74+ F/ }$ [7 G- ~! q) l
75
/ v, G1 x8 z$ D& g" g: G76
) t2 X9 v% D3 i; \1 J+ _77
0 w( X) o0 H+ f0 u781 }, x9 [' [9 x  d! w/ k
79
1 {3 u& v) A3 l( d80& s/ B8 D/ L- w6 W% B
81
; G- ^0 ^, V' k" B. K2 L82+ y' z! H. I. _
83
$ W/ o* O/ F4 `84
/ }2 U) _  J1 {- ~85. s2 R# l, @5 U5 J# o2 Y
86' a1 o" ?* v7 u" K3 ?
87
3 x! T( }+ }4 ~$ U* R% N4 \! }88
5 @% a# ]. x7 l  a1 t: V8 Y# C893 X9 u4 \( e% h0 s. C6 @
902 P; C. s% X% p/ C- ~
91
- i2 C- x" {# t, W$ X92
& c7 b5 {) O5 ?93  F5 f6 x; y4 s
945 P- B/ ?; z! ~: d8 h( m1 E. o* {
95( q6 r; c$ g' o" F
96& v5 u# g3 a& {* v& v0 Y  S
97
: Z3 ]' p0 H" n0 K4 W, Y& Y989 O9 `6 Q7 s# W7 g* ?1 y
99
- V( N. B, v% P9 p$ m0 t- q100
) `. }6 `( `: Z) X9 I0 x101" ]/ I& J! t: W( k+ D# c" b1 T" H' j6 Y
102) [- _( \& A0 m* k$ U
103- s, i8 s* I7 z; ]" l
（高斯核函数）/ s+ W7 r& u: R5 y: p/ O! q
- K  {- I+ S: P* y# w+ M$ |# z
& N# F+ e9 _. a: u
（K邻近法）
. I9 W3 Z6 _/ o% Z! L# e
1 v9 j( q; P" m8 Q; C& O0 A- c
6 ^; D/ T2 I: _& u2 J7 A9 d" w四：谱聚类算法优缺点; P' N8 ?$ B( C4 X
（1）优点
/ y% T! E$ x! x谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效6 I* R! c7 v( X1 G5 c6 X$ L
使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法% t+ |& k6 @8 n( v( O7 T( l8 z, {
谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解' L" c7 J6 E* }" j+ H  h
（2）缺点, }6 b8 P* z8 e$ [7 M4 U
如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
$ ~1 `7 |, K2 p+ G$ D7 ~2 ~  _8 W聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同
* m2 P/ D+ C. N  b. U6 P! l( h8 u————————————————) O7 f3 ?% |) X
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
+ o7 E8 Y0 S5 G5 j9 b9 m原文链接：https://blog.csdn.net/qq_39183034/article/details/1267474947 i( g; W2 m+ c3 _
% ?( c. V# ?6 a4 b( O) q0 W  g
% f' S7 N3 L( R  u9 _- n! e! u