1. 聚类概述
Everitt 在 1974 年对聚类分析做出如下定义：同一簇内的对象之间相似性高，不同簇内的对象之间相似性低，同一簇内的任意两个对象间的距离小于不同簇内的任意两个对象间的距离[2]。簇可以这样描述：“它是一个密度相对较高的数据对象集”。
(1) 基于划分的聚类方法，如K-means、K-medoids
(2) 基于层次的聚类方法，如CURE
(3) 基于网格的聚类方法，如STING
(4) 基于密度的聚类方法，如DBSCAN
(5) 基于神经网络的聚类方法，如SOM
(6) 基于图的聚类方法，如Normalized cut
2. 相似度量
一般地，每个数据点都可以用一个向量表示，因此可以使用距离d或者相似性s来衡量两个用向量表示的数据间的相似程度。
由于表示数据点的向量元素具有不同的类型，可能是连续的，也可能是离散的，也可能有二者皆有的形式。因此距离函数d和相似系数s的定义也相应存在不同的形式。
2.1 相似度量矩阵：
假设有n个点的数据集合 x 1 , x 2 , x 3 , . . . x n {x_1,x_2, x_3,...x_n} x1,x2,x3,...xn, d i j d_{ij} dij表示数据点 x i , x j x_i,x_j xi,xj之间的距离，可以将n个数据点 x i , x j x_i,x_j xi,xj间的距离写成矩阵形式。
d = [ d 11 d 12 ⋯ d 1 n d 21 d 22 ⋯ d 2 n ⋮ ⋮ ⋱ ⋮ d n 1 d n 2 ⋯ d n n ] d=\left[\begin{array}{cccc}{d_{11}} & {d_{12}} & {\cdots} & {d_{1 n}} \\ {d_{21}} & {d_{22}} & {\cdots} & {d_{2 n}} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ {d_{n 1}} & {d_{n 2}} & {\cdots} & {d_{n n}}\end{array}\right] d=⎣⎢⎢⎢⎡d11d21⋮dn1d12d22⋮dn2⋯⋯⋱⋯d1nd2n⋮dnn⎦⎥⎥⎥⎤
对于上述的数据集， s i j s_{ij} sij表示数据点 x i x_i xi与 x j x_j xj间的相似度系数，也可以将n个数据对象的相似度系数写成矩阵形式。
s = [ s 11 s 12 ⋯ s 1 n s 21 s 22 ⋯ s 2 n ⋮ ⋮ ⋱ ⋮ s n 1 s n 2 ⋯ s n n ] \boldsymbol{s}=\left[\begin{array}{cccc}{\boldsymbol{s}_{11}} & {\boldsymbol{s}_{12}} & {\cdots} & {\boldsymbol{s}_{1 n}} \\ {\boldsymbol{s}_{21}} & {\boldsymbol{s}_{22}} & {\cdots} & {\boldsymbol{s}_{2 n}} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ {\boldsymbol{s}_{n 1}} & {\boldsymbol{s}_{n 2}} & {\cdots} & {\boldsymbol{s}_{n n}}\end{array}\right] s=⎣⎢⎢⎢⎡s11s21⋮sn1s12s22⋮sn2⋯⋯⋱⋯s1ns2n⋮snn⎦⎥⎥⎥⎤
其中，距离矩阵的性质：在聚类分析中，距离矩阵一般满足自反性，对称性，非负性以及三角不等式等性质。
- 自反性，即 d ( x i , x i ) = 0 d\left(x_{i}, x_{i}\right)=0 d(xi,xi)=0
- 对称性，即 d ( x i , x j ) = d ( x j , x i ) d\left(x_{i}, x_{j}\right)=d\left(x_{j}, x_{i}\right) d(xi,xj)=d(xj,xi)
- 非负性，即 d ( x i , x j ) ≥ 0 d\left(x_{i}, x_{j}\right) \geq 0 d(xi,xj)≥0
- 三角不等式，即 d ( x i , x j ) + d ( x j , x k ) ≥ d ( x j , x k ) d\left(x_{i}, x_{j}\right)+d\left(x_{j}, x_{k}\right) \geq d\left(x_{j}, x_{k}\right) d(xi,xj)+d(xj,xk)≥d(xj,xk)
2.2 相似度量定义
高斯核函数（RBF）
3. 常见的聚类算法
3.1 基于划分的方法
假定一个具有n个点的数据的集合，我们需要把数据集划分位k个子集，每个子集代表一个类别。一般地，k的取值范围 2 ≤ k ≤ n 2\leq k \leq \sqrt{n} 2≤k≤n 。
基于划分的方法其实本质是对聚类中心逐步进行优化，不断将各个聚类中心进行重新分配，直到聚类中心位置不变，即获得最优解。
常见的代表算法有kmeans，k-modes。
k-means
K-means的具体思想：给定聚类个数k并随机选定k个聚类中心 c k c_k ck，计算所有数据点与k个聚类中心的欧式距离，再对k个距离值进行排序，找到每个数据点最近的聚类中心。遍历完所有的数据点后，将每个聚类中心里的所有数据求平均值，将其更新为新的聚类中心。再重新遍历所有的数据点，再依次计算每个数据点与k个聚类中心的距离，找到它们与之对应的最近的聚类中心。遍历完后更新聚类中心，以此类推，直至误差值也就是每个簇内部数据点与中心的距离之和小于一个给定值并且聚类中心无变化时，就得到了最终的聚类结果。
- 指定k个聚类中心 ( c 1 , c 2 , c 3 ⋯ c k ) \left(c_{1}, c_{2}, c_{3} \cdots c_{k}\right) (c1,c2,c3⋯ck)
- d ( c j , x i ) d\left(c_{j}, x_{i}\right) d(cj,xi)（计算数据点与初始聚类中心的距离）
- x i ∈ c j x_{i} \in c_{j} xi∈cj（对于数据点 x i \mathcal{x}_{i} xi，找到最近的 c i \mathcal{c}_{i} ci(聚类中心)，将 x i \mathcal{x}_{i} xi分配到 c i \mathcal{c}_{i} ci中）
- c j o l d → c j n e w c_{j}^{old} \rightarrow c_{j}^{new} cjold→cjnew(更新聚类中心点， c j n e w c_{j}^{new} cjnew是新类别数值的均值点)
- D = ∑ i = 1 n [ min j = 1 ⋯ K d ( x i , c j ) 2 ] D=\sum_{i=1}^{n}\left[\underset{{j=1 \cdots K}}{\min}d\left(x_{i}, c_{j}\right)^{2}\right] D=∑i=1n[j=1⋯Kmind(xi,cj)2]（计算每一类的偏差）
-
D
r
−
D
r
+
1
<
ε
0
D_{r}-D_{r+1}<\varepsilon_{0}
Dr−Dr+1<ε0返回
(
c
1
,
c
2
,
⋯
c
k
)
\left(c_{1}, c_{2}, \cdots c_{k}\right)
(c1,c2,⋯ck)
D r − D r + 1 ≥ ε 0 D_{r}-D_{r+1} \geq \varepsilon_{0} Dr−Dr+1≥ε0返回第二步
优点：
- 当类与类容易分开时，k-means算法的效果相对较好；
- 假设n为所有数据对象的数目，k为聚类个数，t为算法迭代的次数，则k-means时间复杂度为 o ( n K t ) o(nKt) o(nKt)，故算法可以处理样本量较大的数据。
缺点：
- 初始聚类中心选择的优劣，对聚类结果有很大的影响；
- 只适用于凸状数据；
- 需要人为设置聚类数目K，这对于调优超参数K带来一定的困扰。
3.2 基于层次的方法
基于层次的聚类算法是对给定数据对象集合作类似于层次状的分解。
基于层次的聚类算法通常可以分为2种：自底而上的合并聚类和自顶向下的分裂聚类。
- 合并聚类开始会将每个数据对象看作一个子集，也就是有n个子集，然后对这些子集逐层依次进行聚类，直到满足无法合并的条件。
- 分裂聚类是在一开始将所有的数据对象看成是一个集合，然后将其不断分解成子集直至满足不能再分解的条件为止。
基于层次的聚类算法通常会用平均距离，最大距离，最小距离作为衡量距离的方法。
- 算法如果使用最大距离来度量类与类的距离时，称为最远邻聚类算法；
- 当使用最小距离作为衡量类与类之间的距离时，称为邻聚类算法。
代表算法有：CURE、CHAMELEON、ROCK等。
这里写的太简略可参考其他文章
3.2.1 CURE
CURE是凝聚层次聚类
- 每个样本作为单独的一个类别 ( c 1 , c 2 , c 3 ⋯ c k ) \left(c_{1}, c_{2}, c_{3} \cdots c_{k}\right) (c1,c2,c3⋯ck)
- d ( c v , c k ) = min ∀ c i , c j ∈ s { d ( c i , c j ) , ∀ i , j ∈ { 1 , 2 , ⋯ n } } d\left(c_{v}, c_{k}\right)= \underset{_{\forall c_i, c_{j} \in s}}{\min}\left\{d\left(c_{i}, c_{j}\right), \forall i, j \in\{1,2, \cdots n\}\right\} d(cv,ck)=∀ci,cj∈smin{d(ci,cj),∀i,j∈{1,2,⋯n}}
- 合并 c v , c k c_{v},c_{k} cv,ck为 c v k c_{vk} cvk
- 遍历完本次样本，合并成新的类别后，若存在多个类别，则返回第二步
- 遍历完本次样本，合并成新的类别后，若所有样本为同一类别，跳出循环，输出每层类别。
优点：
- 不需要预先设定聚类个数；
- 可以发现类的层次关系;
缺点：
- 计算时间复杂度高；
- 算法有可能导致聚类成链状，而无法形成层次结构。
3.3 基于网格的方法
基于网格的聚类算法的目标是将数据按维数划分为多层类似网格的结构。
常见的基于网格聚类的算法如 ： STING、 WAVECLUSTER等 。
3.3.1 STING 算法
STING(Statistical Information Grid-based method)聚类算法按照维数将数据空间划分为多个单元，子单元与原始数据的父单元构成一个层次结构。每个子单元存储子单元的相关信息（均值，极值等）。基于网格方法的时间复杂度为o(K)。其中K为最底层网格单元的数量。
- 将数据集合X划分多层网格结构，从某一层开始计算
- 查询该层网格间的属性值，计算属性值与阈值的关系，判定网格间的相关情况，不相关的网格不作考虑
- 如果网格相关，则进入下一层的相关区域继续第二步，直到下一层为最底层
- 返回相关网格结果
优点：
- 基于网格计算是相互独立的且互不干扰；
- 时间复杂度低
缺点：
- 聚类的效果依赖于矩阵单元格划分的大小，单元格划分的细，聚类效果好，时间复杂度高；
- 单元格划分的粗，聚类效果差。时间复杂度小。
3.4 基于密度的方法
基于密度的聚类方法是将数据密度较大的区域连接，主要对有空间性的数据进行聚类。该聚类方法将簇看作数据点密度相对较高的数据对象集。该方法具有较大的灵活性，能有效克服孤立点的干扰。
常见的基于密度的聚类算法有：DBSCAN，DENCLUE, OPTICS等。
3.4.1 DBSCAN
DBSCAN（Density-Based Spatial Clustering of Application with Noise）DBSCAN通过计算每个数据点的 ε − \varepsilon- ε−邻域来探寻密度可达对象集。如果一个点p的 ε − \varepsilon- ε−邻域内所包含密度可达对象点数目大于指定个数，则需要创建一个以点p为核心的新类。在此之后，DBSCAN算法反复从p的 ε − \varepsilon- ε−邻域中找寻密度可达对象集中元素，继续查找子集的密度可达对象集，当没有新的点构成聚类中心点时，聚类过程结束。
- 输入数据集合X，随机选取一点，并找出这个点的所有高密度可达点
- 遍历此点的所有 ε − \varepsilon- ε−邻域内的点，并寻找这些密度可达点，判定某点 ε − \varepsilon- ε−邻域内的点，并寻找这些点密度可达点，判定某点的 ε − \varepsilon- ε−邻域内的点数是否超过阈值点数，超过则构成核心点
- 扫描数据集，寻找没有被聚类的数据点，重复第二步
- 输出划分的类，并输出异常值点（不和其他密度相连）
优点：
- 应用比较广泛，收敛速度快
缺点：
- 不适合高维数据
3.5 神经网络的方法
SMO
自组织映射(Self-Organizing Maps， SOM)神经网络, 实质上是一种浅层神经网络，只有输入层和隐藏层两层结构。
隐藏层中的节点代表其需要聚集的类。每个输入的样本在隐藏层中找到一个和它匹配度最高的节点，称之为激活节点。
- 数据集合 [ x 1 , x 2 , ⋯ x n ] \left[x_{1}, x_{2}, \cdots x_{n}\right] [x1,x2,⋯xn]，权重向量为 [ w 1 , w 2 , ⋯ w n ] \left[w_{1}, w_{2}, \cdots w_{n}\right] [w1,w2,⋯wn]， ∥ x i ∥ = ( ∑ i = 1 d x n 2 ) 1 / 2 \left\|x_{i}\right\|=\left(\sum_{i=1}^{d} x_{n}^{2}\right)^{1 / 2} ∥xi∥=(∑i=1dxn2)1/2，归一化处理 w ^ j = w j ∥ w j ∥ \hat{w}_{j}=\frac{w_{j}}{\left\|w_{j}\right\|} w^j=∥wj∥wj, x ^ i = x i ∥ x i ∥ \quad \hat{x}_{i}=\frac{x_{i}}{\left\|x_{i}\right\|} x^i=∥xi∥xi
- 寻找获胜的神经元，找到最小距离，对于每一个输入数据，找到与之最相匹配的节点
- 更新临近节点，令 S j , I ( x ) 为 I ( x ) S_{j, I(x)}为\mathrm{I}(x) Sj,I(x)为I(x)为 j j j的距离，更新权重： T j , I ( x ) = exp ( − S j , l ( x ) / 2 σ 2 ) T_{j, I(x)}=\exp \left(-S_{j, l(x)} / 2 \sigma^{2}\right) Tj,I(x)=exp(−Sj,l(x)/2σ2)
- 更新节点参数 ，
w
(
t
+
1
)
=
w
(
t
)
+
η
(
t
)
T
j
,
l
(
x
)
(
t
)
(
x
i
−
w
j
i
)
w(t+1)=w(t)+\eta(t) T_{j, l(x)}(t)\left(x_{i}-w_{j i}\right)
w(t+1)=w(t)+η(t)Tj,l(x)(t)(xi−wji)，其中
η
(
t
)
\eta(t)
η(t)代表学习率
5。 重新归一化处理：对调整后的权向量重新归一化，多次迭代运算，直到
η ( t ) < ε \eta(t)<\varepsilon η(t)<ε或者迭代次数大于规定次数；
优点：
- 不需要定义聚类个数，SOM有很好的拓扑结构，可视性较好
缺点：
- 需要选择参数很多，调参数需要经验
3.6 基于图的聚类方法（谱聚类）
基于图的聚类方法根据给定的数据集，计算样本间的相似度矩阵，度矩阵以及拉普拉斯矩阵，并计算拉普拉斯的特征值和特征向量。然后选择合适数目的特征向量b并使用传统kmeans聚类，图聚类可以在非凸样本空间中聚类。
领接矩阵、相似矩阵：
一般来说，领接矩阵W需要通过样本点距离度量的相似矩阵S来获得。
构建邻接矩阵A的方法有三类。ϵ-邻近法，K邻近法和全连接法。
拉普拉斯矩阵：
是对称半正定矩阵、最小的特征值是 0，所对应的特征向量(1, 1, … ,1)
图划分准则:
图聚类问题的实质是图划分问题，聚类的过程其实就是对图划分过程的优化。优化的目的是使子图间的相似度变小，子图内的相似度变大。
定义图G中，子图a，子图b，之间所有的边的权值和：
A
(
a
,
b
)
=
∑
i
∈
a
,
j
∈
b
w
i
j
，
w
i
j
为
点
i
到
点
j
的
权
重
A(a,b) =\sum_{i\in a,j\in b}w_{ij}，w_{ij}为点i到点j的权重
A(a,b)=i∈a,j∈b∑wij，wij为点i到点j的权重
cut: 子图a与子图b之间公共边的权值之和
c
u
t
(
a
,
b
)
=
∑
u
∈
a
,
v
∈
b
A
(
u
,
v
)
，
cut(a,b)= \sum_{u\in a,v\in b}A(u,v)，
cut(a,b)=u∈a,v∈b∑A(u,v)，
其中，A为连通图的领接矩阵，
a
∩
b
=
∅
a\cap b=\varnothing
a∩b=∅
RatioCut 切图、NCut 切图、
谱聚类算法
- 计算邻接矩阵
A
=
[
w
11
⋯
w
1
n
⋮
⋱
⋮
w
n
1
⋯
w
n
n
]
A=\left[\begin{array}{ccc}{w_{11}} & {\cdots} & {w_{1 n}} \\ {\vdots} & {\ddots} & {\vdots} \\ {w_{n 1}} & {\cdots} & {w_{n n}}\end{array}\right]
A=⎣⎢⎡w11⋮wn1⋯⋱⋯w1n⋮wnn⎦⎥⎤，
度矩阵(对角阵) D i i = ∑ j = 1 n w i j D_{ii}=\sum_{j=1}^{n} w_{ij} Dii=∑j=1nwij， D = [ D 11 ⋯ 0 ⋮ ⋱ ⋮ 0 ⋯ D n n ] D=\left[\begin{array}{ccc}{D_{11}} & {\cdots} & {0} \\ {\vdots} & {\ddots} & {\vdots} \\ {0} & {\cdots} & {D_{n n}}\end{array}\right] D=⎣⎢⎡D11⋮0⋯⋱⋯0⋮Dnn⎦⎥⎤ - 计算拉普拉斯矩阵 L = D − A L=D-A L=D−A
- 计算归一化拉普拉斯矩阵 L = I − D 1 / 2 ⋅ A ⋅ D 1 / 2 L=I-D^{1 / 2} \cdot A \cdot D^{1 / 2} L=I−D1/2⋅A⋅D1/2
- 计算L的特征值和特征向量 Q Q Q
- 对Q矩阵进行K-means聚类，得到聚类结果
优点：
- 比传统的kmeans聚类算法普适性更强，不仅可以用于凸数据，对于任意形状的数据空间也能得到很好的聚类。
缺点：
- 在进行聚类之前需要设置具体应用的尺度参数，通常需要一些经验。
- 选择初始地聚类中心对整个聚类纯度影响很大。
- 很难找到图划分的优化解，聚类个数选择对于整个聚类的结果有很大影响。
4. 聚类结果的评价
。。。。。。
参考：
[1] 张涛. 基于图的聚类分析研究[D].云南师范大学,2018.
[2] https://www.jianshu.com/p/b648072e9e37
[3] https://www.jianshu.com/p/cef979c12245 // 以上三者为同一出处
[4] https://www.cnblogs.com/pinard/p/6221564.html
[5] https://zhuanlan.zhihu.com/p/84834952