什么是聚类
- 聚类是针对给定的样本,依据它们特征的相似度或者距离,将其归到若干个类或者簇的数据分析问题。
- 聚类的目的是通过得到的类或者簇来发现数据的特点或者数据进行处理
- 聚类是无监督学习,常用的聚类算法
- 层次聚类
- 分为聚合和分裂两种方法
- 聚合:将相近的两类合并,重复;分裂:将相距最远的样本分到两个不同的类中
- k-均值聚类
- 基于中心的聚类
- 找到每个样本与其所属的中心或者均值最近
基本概念
相似度或距离
聚类的对象是观测数据或者样本集合,用相似度或者距离来表示样本之间的相似度。常用的距离:
-
闵可夫斯基距离
闵可夫斯基距离越小相似度越大
$$
d_{ij}=(\sum_{k=1}{m}|x_{ki}-x_{kj}|p)^{\frac{1}{p}}
$$
这里$p\geq1$,p=2
表示欧式距离
,常用;p=1
表示曼哈顿距离
;$p=\infty$表示切比雪夫距离
,取各个坐标值的绝对值的最大值 -
马哈拉洛比斯距离(马氏距离)
马氏距离越小相似度越大。
给定的样本集合$X=(x_{ij}){m \times n}$,协方差矩阵为$S$,两个样本之间的马氏距离为
$$
d_j=[(x_i-x_j)TS{-1}(x_i-s_j)]^{\frac{1}{2}}
$$
其中$x{i}=(x_{1i},…,x_{mi})^T$,$x_{j}$类比。当$S$为单位矩阵时,方差为1,马氏距离就是欧式距离。马氏距离是欧式距离的推广。 -
相关系数
相关系数的绝对值越接近1,样本越相似;越接近0,越不相似
-
夹角余弦
夹角余弦cosine
越接近1表示越相似,接近0表示越不相似
用距离度量:距离越小,越靠近越相似;用相关系数:相关系数越大越相似
类或簇
通过聚类得到的类或者簇,本质是样本的子集。
- 硬聚类:一个样本只能属于一个类或者簇
- 软聚类:一个样本属于多个类或者簇
类的特征
类的特征可以通过不同的角度进行刻画,常用三种:
-
类的均值$\hat x_G$,或者类的中心
$$
\hat x_G=\frac{1}{n_G}\sum_{i=1}^{n_G}x_i
$$ -
类的直径
任意两个样本之间的最大距离
$$
D_G=\mathop {\max}\limits_{x_i,x_j \in G}d_{ij}
$$ -
类的样本散布矩阵$A_G$与协方差矩阵$S_G$
$$
A_G=\sum_{i=1}^{n_G}(x_i-\hat x_G)(x_j-\hat x_G)^T
$$$$
S_G=\frac{1}{m-1}A_{G}
$$关于符号:
- $G$:类或者簇
- $x_i,x_j$:样本
- $n_G$:样本个数
- $d_{ij}$:两个样本之间的距离
- $m$:样本的维度
类和类之间的距离
两个不同类$G_p,G_q$之间的距离$D$,称之为 连接linkage
,假设两个样本、个数和均值:
$G_p—>n_p—>\hat x_p$;$G_q—>n_q—>\hat x_q$
-
最短距离(单连接)
两个类中样本之间的最短距离
-
最长距离(完全连接)
两个类中样本之间的最长距离
- 中心距离
两个中心之间的距离
$$
D_{pq}=d_{\overline x_p \overline x_q}
$$
- 平均距离
两个类中的任意两个样本之间距离的平均值
$$
D_{pq}=\frac{1}{n_qn_p}\sum_{x_i\in G_p}\sum_{x_i\in G_q}d_{ij}
$$
层次聚类
- 聚合:自下而上的聚类,
bottom-up
- 分裂:自上而下的聚类,
divisive