查看: 2957|回复: 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])2 m) p* `1 z6 n" M  k0 f. M
return dist_matrix
% ?2 E' q; s, _& P3 P9 a- v2 ?. x: j6 Z  q! I  e
def get_W(data, k):
1 F  x3 W& E  R # 获取邻接矩阵（K邻近法）
1 x# b" j& A9 U5 P7 u! j n = len(data)( v/ {) ?7 T5 c
dist_matrix = get_dist_matrix(data)( f- m' \5 t! T- ]. [8 B
W = np.zeros((n, n))
- I, ^# t. T& y$ j% X  }" ^3 n for idx, item in enumerate(dist_matrix):
, H! i- d0 h2 D' V       idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表
1 Q- B% z/ q7 H& \! |1 \, V% Q       W[idx][idx_array[1:k+1]] = 1
0 p+ @. e" V6 n" S0 i' ]: h8 T. \ transpW =np.transpose(W)
( a; X7 @$ U% a return (W+transpW)/26 y) e& X$ r( q9 e4 ], D

) l" [6 ?9 R7 Hdef spectral_clustering(data_set, k):
. h$ |! ?3 l, h% T6 l9 I # 利用相似矩阵S得到邻接矩阵W% @3 _) Y) Z9 l9 o' {, R* `
W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）  ^9 ^; A; ^8 \
#  W = get_W(data_set, k)  # K邻近法, N# H/ o7 ^+ V! X3 R
' A2 j, @# f. a( E3 {; c/ A
# 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）; |3 W& a( G# t+ w6 F; |, A
D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5)). e. _% ^( ~" e( S2 ?

& G8 g) ^) d1 [+ \( u. P: ]' D # 计算拉普拉斯矩阵L=D-W
0 L1 y! A# ^' D( k+ q; x # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
% f# f6 M9 X* E L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv); \' `! Y4 y$ p- ?9 _0 ?
/ r. f8 q4 X9 i& X6 e/ x
# 得到特征值和特征向量. ~5 b" f; {6 R6 ]8 N! v2 E
eigvals, eigvecs = np.linalg.eig(L)
/ r5 h: q2 C5 u1 I
8 V, T! j: J. Z. K* c7 n # 找到前k个最小的特征值（索引）
9 m- j& [4 w3 y( d4 Q/ ^8 \ k_smallest_eigvals_index = np.argsort(eigvals)[:k]' k3 Y; @, a+ i4 O2 v" h

( x9 |/ |0 F: N, ]3 s) E  Z; c5 a. q # 取出这k小特征值对应的特征向量，并正则化
9 H2 ]4 f3 W% { k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])2 {; G3 e3 f* x5 f  B2 N

, E& i5 ~0 \' d" i' w% \' \ # 使用K_Means聚类, O* K) d7 x9 u- p
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)
& s) k- j6 T1 C0 `; V; i4 M7 @6 H7 U
5 m; ]& H& ^, N
raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)
/ M4 D$ e) G: M0 X5 ?, R3 p9 e. traw_data.columns = ['X', 'Y']7 @0 g) ]+ c" V! m
x_axis = 'X'! ]; d) W* n1 T
y_axis = 'Y'
* K( n# U! [! ]! `
& e1 C5 t5 r; i" u9 i' v% Fexamples_num = raw_data.shape[0]
: Z. K3 N8 d3 y, k4 o& V3 T8 _. Ntrain_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)) u5 z* G# C3 m! q
' o- j7 d% i. t; \
; w9 {$ F3 w1 b  N
min_vals = train_data.min(0)2 q+ t. l, i4 H
max_vals = train_data.max(0)  k9 E" C. _  F, q- K" }' i" o
ranges = max_vals - min_vals
3 ?  y, n) g+ p) T4 |- l9 e( Unormal_data = np.zeros(np.shape(train_data))( D9 ^- l9 P% y( b  h. n+ q
nums = train_data.shape[0]
9 p, J% T) P( o0 x2 T# ?  M+ qnormal_data = train_data - np.tile(min_vals, (nums, 1))
/ K7 W& ]: o6 Q" t- Cnormal_data = normal_data / np.tile(ranges, (nums, 1))7 n% w! V; X* Q. p: N

9 E1 w, r) g5 D3 g- a, slabels = spectral_clustering(normal_data, 2)' }7 u5 R) q* }( L" C7 J# O

% g# {/ @  j3 S8 e( E" ^( h# 原数据# h6 w9 D' q# ^( w3 n8 R; z; C
fig, (ax0, ax1) = plt.subplots(ncols=2)3 O4 O. p# B6 U: h; p
ax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')  _; ]6 E, l; \3 j
ax0.set_title('raw data')4 N& }+ J$ @0 u# n3 w
# 谱聚类结果- {3 L8 l2 _) |8 N2 v
ax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)
( N$ r- U8 d6 l- h3 _ax1.set_title('Spectral Clustering')4 A/ Y6 J* ~' b/ W  f
6 O- q) x0 \- l* ?- g
plt.show()
( t- U6 s$ G3 z2 z& a) h& F! T, U/ {2 o
11 f  n- V# _& r+ q5 [- i
2; h/ H; E' ^& ]" t8 I  X0 M( r
3
, ^8 z# p$ F" j# l41 p% k+ C& a% d
5$ D5 e3 U3 Y8 k6 A) b1 f
6. H4 ~" X$ ?$ M1 Y. S
7, r+ Y% s! Y: F, |' b
8
- V! G/ e9 F/ y* {/ c  f4 g, K" ^* `9; L! o; `$ v  }, @
10& N/ ~0 t2 ?& ?8 [& w
11
  U) ^: V) x4 n4 D12
9 }8 J! P' C) t/ x9 Z13
; W; T9 Y2 _1 Y) x8 M2 A- F14* h5 @7 x9 f0 v, y
15( _( c. l: `5 L, M
16* \5 H( R5 Y7 F9 o5 W& x2 }
17! G0 T: c& i: k4 z
18
  f7 ~: i# M5 U: ^191 l) [! E1 z6 v3 M% u, X
206 d9 Y1 Q: M! v! c  X7 W& W
21" G! e6 i9 r: x% M3 `5 D
228 u% m: \' G: {) Q& R' t
23/ e# x8 E8 R+ n% j" k. H
24
+ Q4 Y- W, h  O/ ]7 o25: _, k! r( w3 g# o) ?8 b0 Y' L
26
7 X% Z! {$ ~6 l. G& b/ J3 i$ i27
9 x& I% R0 n7 q$ B28
+ _. s" d! l% m. v7 m29
" `5 [( \7 i) T2 r% R* R' A& U5 X1 G30* v; L, _- a" N' w' H# o
31
* V% l- o+ i4 J' t, ~" `. l32
4 R) l5 f$ z  Z! z$ s3 C33$ i+ `  T* J7 z( s( ]- c
34
" e: I0 v* h+ `* I% g9 q35
0 @3 g& a/ e/ i4 Z: D36
+ i+ ~3 m3 u# V& }6 l37
' N- \" y; r! U1 C38$ T" E3 X! \0 J2 C' l
39# G& m; {3 |9 W# p
40+ L. I) _  U3 g
41
9 j; H3 p, `; I" }# h, c' g428 @8 s/ c* A0 i% n" F- p8 L
43' M; {, `; X! I5 n* h3 c1 Z) |
441 S! U  G1 q( [- t
45
( D, N) B. V. Z7 w, W( S3 t! T- x9 o46
& {- ?% g4 A5 `# J0 E3 E2 r47
$ g4 f; I* t, J, g48
1 S* x. L$ ~9 X' ^491 v! s# [8 X' C3 @: z3 L$ [6 Y- _
50( `; W& s" d! q; m4 j# P' u4 H
51
, N% H# G* c: _& Y3 Y* \52* E% N. [  h# i( _2 [
53
, @: Z% d7 d) e3 N! d545 O9 E* t3 o% s1 a6 s6 {
55
4 N0 \$ t8 Z& ^# _56
+ U0 U: t; }; L* Q57' V+ y4 C# X* R: H
58" H" T: d) `6 r$ [4 y3 }2 S) c; t
59
/ P1 G+ G6 }" m' W% l" d0 h! h4 Q60
1 I/ f3 y( a; F( m$ G61# k4 M7 V$ V$ |# r
62
/ ?0 X3 e- }8 y1 H% P8 f8 h63
8 L/ K4 x' B# i1 D64
. P4 V2 u! F( F* j' H; m2 J" Q65
, l4 q$ l: S8 o) ~0 e66
2 y, `! w9 e5 V: L# V67
' m" l. \0 s: f  _" B68
6 D4 T7 b  B) w& b69
1 H' g' r( D0 m" ^5 |70
" _$ h3 n% v8 Y! [8 p( h0 f71
2 U; a6 i9 W2 R. F1 l728 f4 ]% ?; C' X' ?6 [# s! T
737 |, S. P- q6 D8 o$ B$ R
74  {+ [8 f. U' L2 ~7 |! H4 \0 }* U" f
75
/ x0 N& e# j4 u- k* J76
3 e0 Z, T7 o1 |9 _/ C; d77$ J& Q1 |% `! d5 W; q1 w4 A! ~
78  {( E; _9 K7 C) V. k# Q
79
1 L) w0 w5 i& b4 i3 ~0 h80
/ t' R3 Z. f& C3 b. n- A0 Z81
2 Y: c  R$ w6 t: R82
' K* ?! J2 R' F, C% Y83! c. E' t. Y9 w/ {
84
3 u& s+ S$ ?  F85
! S+ ?, H% u8 u, e86& q$ n6 d& I% W- ~& ]3 F
87
+ v. u( \% |3 Z* N5 ]885 k+ m5 Y" V8 o, _# f
89' a+ H* o. x% m4 ~# W& k4 {
90. H7 C5 B4 V( _0 B7 e5 H' }
91
$ u+ M" h2 e% h: U: _& U92
/ M" |" I# M# {6 S93
- r  M0 T9 x( s- T# x/ h94. m& H6 g! |4 p, ?0 ?+ \& o8 `; E0 t
954 y1 i/ F$ [& e3 e- L8 c, ^
96
, T* ?, B% r6 ?) [- J97
4 K- R% q# ]+ {+ \/ i98
2 _8 F. y2 m4 D" l+ l8 d, R. b% J99
* `# W% p' f' u' X- g6 d100
# N4 Z3 F/ y$ p2 @6 Y; r101
  F( r9 s: [: H- f( c6 u$ f102: k+ B5 `" f' ^( c3 A
103
& O) b* g+ W% G9 X（高斯核函数）' f: q3 k2 p, Y! }. w* f- s/ g

" M1 v' `$ D1 C* k' w" |. F4 Z; @9 I" r; s* l4 B0 k
（K邻近法）8 T2 N3 r; r. a7 A3 N; ^

- z& a! }3 Y! ^
$ S, t. M8 \# }9 ], ?& n1 E; k4 _( P四：谱聚类算法优缺点6 a, K; I( e- e0 T4 `
（1）优点
6 `  N( k3 t# `" r2 d& p谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效( Q4 g% H8 k. m. A; q" ]
使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法
% j! v. {: p% t+ c谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解+ c: n" h( ]) j$ o
（2）缺点
6 p5 t, \6 q# t! o如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
: W) e1 j) L+ {( H+ G6 M: Q聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同
1 Q, x1 d' S# ^/ ?6 A————————————————
  v. ]3 ~' O* b6 _) I1 {/ Y版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。4 q8 A7 k6 i6 ?$ c  n
原文链接：https://blog.csdn.net/qq_39183034/article/details/1267474943 A( E" j% T  G& v3 d! [, I* o! I
# y" h7 p* h: r/ [- d4 k3 R
8 U, ^/ _" X/ Z4 k% Z: c/ P