标签：机器 结果 样本 矩阵 距离 学习 簇内 聚类

聚类的定义

聚类是一种非监督学习任务，其目的是发现数据中隐含的结构。

 

相似度度量

样本之间的相似性对聚类的结果很关键，在聚类的时候，是根据相似度来聚类的。

定义距离参数

非负性：两个样本之间的距离只能大于等于0；

可辨识性：样本只与自己的距离为0，与其他样本不会重叠；

对称性：样本a到样本b的距离等于样本b到样本a的距离。

三角不等式：两点之间，直线最短。

距离度量

欧式距离

空间中两点之间的直线距离

曼哈顿距离（两个样本中，对应分量差值的总和。）

曼哈顿是一个形象的命名，假设在曼哈顿，从一个路口到另一个路口，不可能是直线距离，因为不能穿越房屋。

切比雪夫距离（两个样本中对应分量的最大差值）

在二维棋盘上，假设一步只能移动到相邻的8个方格中，那么从(x₁,y₁)走到格子(x₂,y₂)最少需要的步数是max( | x₂-x₁ |,| y₂-y₁ |)步。

 

闵可夫斯基距离（前三种距离的总结）

是一组距离的定义，参数不同，变为不同的距离

当p=1时，为曼哈顿距离；当p=2时，为欧式距离；当p->∞时，是切比雪夫距离

 

马氏距离（利用样本的协方差矩阵）

S为所有样本的协方差矩阵。

与欧式距离的关系：如果协方差矩阵是单位矩阵，马氏距离就退化成欧式距离，欧式距离是马氏距离的特例。

 

汉明距离（Hamming Distance）(对应分量疑惑操作)

两个样本对应分量之间进行异或，最后求总和。

夹角余弦（空间上夹角表示相似度）

将两个样本看做是D为空间上的两个向量，求两个向量之间的夹角余弦，作为相似度。

相关系数（夹角余弦样本去中心化）

当μ_i=0，μ_j=0，此时相关系数为夹角余弦。

 

杰卡德相似系数（Jaccard similarity coefficient）（上交下并）

交集元素占并集元素的比例。

 

---

聚类算法

K均值（KMeans）聚类

算法流程

1. 选择K个点作为质心，形成K个簇；
2. 计算每个点与K个质心的相似度，将每个点指派到K个簇；（K均值相似度使用欧氏距离表示，将样本归为最近的一个簇）；
3. 重新计算每个簇的质心。
4. 重复第2步开始。直到簇不发生变化或达到最大迭代次数

优化目标

优化目标就是使得每个样本到其所属簇中心的距离最小。

λi表示样本i所属的簇的索引，μ_λi表示索引为λi的簇的中心，r_i,k=1表示第i个样本属于第k个簇，否则r_i,k=0。

得到：

 

K值的选择

方法1

肘部法，画出训练集上目标函数值随着K的变化曲线，“肘部”位置的K为最佳的K（随着K值的增加，目标函数的值不再显著下降）

如下图所示，最佳的K为4

方法2

使用评价指标选取最佳的K值

优点

计算简单

局限性（每个样本只能属于同一个簇，每个簇为一个球形高斯分布。）

K均值聚类需要指定簇的数目K。

K均值使用的是欧式距离指派样本，相当于假设簇的形状为球形。

K均值聚类直接使用欧氏距离作为指标，相当于假设各个簇的方差/散布程度相同。

K均值中，假设了每个簇的概率相等，不能处理每个簇样本数差异很大的情况。

 

高斯混合模型（Gaussian Mixed Models，GMM）

GMM的假设

每个簇的样本服从高斯分布N(x,μ_k,Σ_k)，均值向量μ_k和协方差矩阵Σ_k（因为有协方差矩阵作为参数，簇可以为椭球形状）。

不再要求每一个样本只能属于一个簇，每个样本以一定概率属于每个簇。从属度r_i,k∈[0,1]。

簇k被选中的概率为π_k。用独热编码向量z表示簇是否被选中，z_k=1表示选择第k个簇。

 

两种角度的高斯混合模型

 

MLE 极大似然估计求解GMM（无法求出解析解）

EM求解高斯混合模型

E步

 

M步，以求解p_k为例

层次聚类

分裂式层次聚类

分裂式从一个包含所有样本的簇开始，然后不断分裂已有簇，直到每个簇只包含一个样本

凝聚式层次聚类

凝聚式层次聚类最开始每个样本视为一个簇，而后计算各簇之间的距离，将两个最相近的簇合并成一个新的簇。如此往复，最后就只剩下一个簇。

1. 初始化：每一个样本为一个簇
2. 计算簇与簇之间的相似度，可存为相似度矩阵；
3. 重复：
   1. 合并最相似的两个簇
   2. 更新簇之间的相似度矩阵
4. 直到只剩下一个簇

簇之间的距离度量

最小距离

最大距离

平均距离

中心点距离

μ_k，μ_{l分别为两个簇的质心。}

_沃德距离

_{误差平方和SSE}

既考虑了簇间的距离，也考虑了每个簇中样本的数目。

 

缺点

效率低，时间复杂度O(N³)

 

基于密度的噪声鲁棒的聚类（DBSCAN）

特点

基于密度

样本类别

核心点：指定半径（ε）内多于指定数量（MinPts）个点；

边界点：半径（ε）内有少于MinPts个点，但在某个核心点的邻域内；

噪声点：核心点和边界点之外的点。

密度可达：如果连接两个点q和点p的路径上所有的点都是核心点，则称点q到点p密度可达。若p是核心点，则由它密度可达的点形成一个簇。

密度相连：如果存在点o，从其密度可达点q和点p，则点q到点p密度相连。

簇的性质

连接性：簇内任意两点是密度相连的。

最大性：如果一个点从一个簇的任意一点密度可达，则点属于该簇。

算法流程

初始化核心点集合：Ω=∅；（遍历每个点，判断半径ε内点是否大于等于MinPts个）
初始化簇的数目K=0，未访问过的点集合Γ=D；
while Ω≠∅:
    记录当前未访问过的点的集合Γold=Γ
    随机选择一个核心点o∈Ω，初始化队列Q=<o>;
    Γ=Γ\{o}; //将o从Γ中去除
    while Q≠∅ do:
      取出队列Q中的首个样本点q
        如果q半径ε内点的个数大于等于MinPts，将半径ε内所有未被访问过的点加入到队列Q中，访问队列Γ中去除这些点。
    K=K+1，CK=Γold \ Γ

大致思路：

判断某个核心点的邻域内未访问点的个数是否大于指定个数，大于则将这些点全部加入到队列中。

从队列中出队一个继续判断。

 

优点

对噪声不敏感

可以找到任意大小和任意形状的簇。

无需指定簇的数目K，只要设置两个参数：一个是半径，一个是最小的点数MinPts。

 

谱聚类

基本思想

将每个样本看成一个无向图中的节点，节点之间的边的权重为相似度，将聚类问题转换为图的切分问题。

相似性图

边的权重为两个节点的相似度。

一般相似度为：

 

相似性图的构造

ε-邻近法

若样本之间的相似度大于ε，则用权重ε连接两个样本，相似度小于ε，权重等于0；

 

K近邻

只考虑样本点的K个邻居，不在K近邻范围内的样本，权重为0。

为了对称性，xi必须是xj的K近邻，xj也必须是xi的K近邻，否则权重为0

全连接法

直接用相似度衡量所有样本之间的权重，w_i,j=s_i,j。

 

邻接矩阵W

所有节点之间的权重值w_i,j构成图的邻接矩阵W。

 

度矩阵D

度矩阵描述每个节点的度。是一个对角矩阵。

 

拉普拉斯矩阵L

L=D-W

 

拉普拉斯矩阵的性质

1.拉普拉斯矩阵是对称矩阵

2.对于任意向量f有：

3.拉普拉斯矩阵是半正定矩阵。

4.拉普拉斯矩阵最小特征值是0，且对应的特征向量为全1向量。

 

图的切分

切图

将无向图G(V,E)切成互不相连的K个子图，每个子图点的集合为A₁,A₂,...,A_k，满足A_i∩A_j≠∅，且A₁∪A₂∪...∪A_k=V。

子图A和B之间的切分权重：

切图为：

 

子集的体积vol(A)为A内所有边的权重

规范化切图（考虑了簇内的相似度）

 

在scikit-learn中，sklearn.cluster.SpectralClustering实现了基于NCut的谱聚类。

需要条件的参数主要是相似矩阵建立相关的参数和聚类类别数目。

 

---

聚类算法的评价指标

评价一个算法的聚类效果是否好。

外部评价指标（有参考结果）

划分结果参数定义

对数据集D={x₁,x₂,...,x_n}，通过聚类算法将样本聚为K类：C={C₁,C₂,...,C_K}，参考结果给出的聚类划分为C^*={C₁^*,C₂^*,...,C_K^*}。

令λ和λ^*分别表示C与C^*对应的簇标记向量。有如下定义：

S1中包含了经过算法划分后属于同一个簇，并且在参考划分结果中也属于同一个簇的样本对。

S2中包含了经过算法划分后属于同一个簇，但是在参考划分结果属于不同簇的样本对。

S3中包含了经过算法划分后不属于同一个簇，但是在参考划分结果中属于同一个簇的样本对。

S4中包含了经过算法划分后不属于同一个簇，并且在参考结果中也不属于同一个簇的样本对。

每个样本只能出现在一个集合中，故a+b+c+d=N(N-1)/2。(注意a=|S1|，a是S1中样本个数，b,c,d均是表示集合中样本个数)

性能度量指标

Jaccard系数（JC）

描述了正确结果样本，占聚类结果正确样本和参考结果正确样本的比例。（要么在聚类结果中属于同一个簇，要么在参考结果中属于同一个簇，总有一个正确）JC∈[0,1]。

JC越大，聚类结果与参考结果一致性越高。

 

FM指数

FMI∈[0,1]，FMI越大，聚类效果与参考结果的一致性越高。（将JC指数拆开，取根号）

 

兰德指数（RI）

a+d表示聚类结果与参考结果完全吻合的样本对个数。将所有样本个数考虑了进去。

RI∈[0,1]，RI越大，聚类结果与参考结果的一致性越高。

 

调整兰德指数（ADI）

ARI∈[-1,1]，ARI越大，聚类结果与参考结果一致性越高。

总结

外部评价指标主要是通过判断 聚类结果中样本对是否相同，参考结果中样本对是否相同这样一个参数来做评判。

根据组成的四个参数a，b，c，d，代入到各个公式判断。

内部评价指标（没有参考结果）

参数定义

avg(C_k)：表示簇C_k中样本对平均距离。

diam(C_k)：表示簇C_k中样本对最大距离。

d_min(C_k,C_l)：表示簇C_k和簇C_l最短距离。

d_cen(C_k,C_l)：表示簇C_k和C_l两个簇的中心距离。

 

戴维斯-堡丁指数（Davies-Bouldin Index，DBI）

簇内距离与簇间距离的比例，所以DBI越小，表示簇内距离越小，簇间距离越大，聚类效果越好。

 

邓恩指数（Dunn Validity Index，DVI）

任意两个簇之间最小距离，占任意簇内最大距离的比例，当任意两个簇之间最小距离越大，任意簇内最大距离越小，这样就分的越开，聚类效果越好，所以DVI越大越好。

 

Calinski-Harabaz指数（Calinski-Harabaz Index，CHI）

B为簇间散度矩阵。μ为所有样本的中心，μ_k表示簇C_k的中心。簇间散度矩阵就是每个簇的中心与所有样本中心的差值，组成的协方差矩阵

W为簇内散度矩阵。x_i为簇C_k中的样本x_i。簇内散度矩阵就是簇内样本与簇的中心的差值，组成的协方差矩阵。

CHI越大，簇自身越紧密，簇间越分开，聚类效果越好。

 

轮廓系数（Silhouette cofficient，SC）

样本i的轮廓系数

样本的总轮廓系数

a(i)：样本点i到其所属簇中其他点的平均距离，a(i)与簇内散度有关。

b(i)：样本点i到其他类内所有点的平均距离，b(i)与簇间有关。

s(i)∈[-1,1]。

s(i)趋向于1，样本点距离相邻的簇很远。所以s(i)越大越好

s(i)≈0，表示样本非常靠近相邻的簇，样本在两个簇的边界上。

s(i)趋向于-1，表示样本分配给错误的簇。

 

 

 

标签：机器,结果,样本,矩阵,距离,学习,簇内,聚类
From： https://www.cnblogs.com/RedNoseBo/p/17088469.html