跳转至

统计机器学习08：聚类Clustering

本页统计信息

  • 本页约 1905 个字, 预计阅读时间 6 分钟。

  • 本页总阅读量次

聚类的基本概念

聚类是一种无监督学习，就是在给定的数据集中根据特征的相似度或者距离，将数据集中的对象归并到若干个类中(事先并不知道，即数据集是没有label的)，因此解决聚类问题的关键是要先定义距离的度量方式，因为很多时候数据点并没有物理意义上的"距离"(地图上的不同点拥有的是物理距离)，比如社交网络中人和人之间的关系就是一种广义上的距离，对于不同的场景，我们需要寻找不同的方式来定义数据样本中的"距离"

相似度和距离

用于聚类的样本数据集D或者样本集合，假设有n个样本，每个样本的有n个属性，那么样本的集合就可以用一个大小为\(m\times n\)的矩阵\(X\)来表示，矩阵的每一列表示一个样本的m个特征，常见的距离定义方法有

  • 闵可夫斯基距离：对于两个向量，定义其闵可夫斯基距离为
\[ d_{ij}=\left(\sum_{k=1}^m|x_{ik}-x_{jk}|^p\right)^{\frac 1p} \]

闵可夫斯基距离中，当p=1时就是曼哈顿距离，p=2时就是欧式距离，p=\(\infty\)为时就是切比雪夫距离，等价于各个坐标数值差的绝对值

  • 马哈拉诺比斯距离：假设样本矩阵X的协方差矩阵是S，则马哈拉诺比斯的距离共识可以表示为
\[ d_{ij}=\left[(x_i-x_j)^TS^{-1}(x_i-x_j)\right] \]

马哈拉诺比斯距离考虑了各个特征之间的相关性，通过协方差矩阵传递了这种相关性到两个样本的距离中，马哈拉诺比斯距离越大说明相似度越小

  • 向量夹角的余弦：高中的时候立体几何中学的
\[ s_{ij}=\frac{\left< x_i,x_j \right>}{||x_i||_2\times||x_j||_2}=\frac{\sum\limits_{k=1}^mx_{ki}x_{kj}}{\left(\sum\limits_{k=1}^mx_{ki}^2\sum\limits_{k=1}^mx_{kj}^2\right)^\frac 12} \]
  • 相关系数：可以用相关系数来表示样本之间的相似度，(概率论和数理统计中似乎学过这个只是)其定义是：
\[ r_{ij}=\frac{\sum\limits_{k=1}^m(x_{ki}-\bar x_i)(x_{kj}-\bar x_j)}{\sum\limits_{k=1}^m(x_{ki}-\bar x_i)^2\sum\limits_{k=1}^m(x_{kj}-\bar x_j)^2} \]

类和簇的判定

定义了什么是距离之后，我们遇到的第二个问题就是，对于一个数据集合G，当其中的点距离满足什么条件的时候可以将一系列数据样本定义成一个类(也可以叫簇，cluster)，而常见的定义方式有：

  • 集合G中任意两个点的距离都不超过常数T

  • 对于集合G中的任意一个点，都存在另一个样本使得二者的距离不超过常数T

  • 对于G中的一个样本点，它和任意一个其他点的距离都不超过T

  • 对于集合G中的样本，任意两个点之间的距离不超过V并且所有距离的平均值不超过T

我们可以用一些特征来刻画一个类，比如定义类的均值或者直径： $$ \bar x_G=\frac{1}{N_G}\sum_{i=1}^{N_G}x_i\qquad G_D=\max d_{ij} $$ 同时类和类之间的距离也可以进行定义，这种距离又可以叫做连接(linkage)，可以有多种定义方式，比如最短距离，最长距离，中心局距离和平均距离等等。

层次聚类

层次聚类是假设类别之间存在层次结构，将样本聚合到层次化的类里面去，分为自顶向下的聚类(分割)和自底向上的聚类(聚合)，聚合算法首先要确定三个要素，不同要素进行组合就可以得到一系列聚类算法：

  • 定义距离或者相似度

  • 确定合并的规则

  • 确定算法停止的条件

聚合聚类

聚合聚类会根据输入的n个样本点进行聚类，最后输出一个包含所有样本的类和其中的各个子类，算法步骤如下：

  • 对于n个样本点计算其距离，构成一个\(m\times n\)的矩阵

  • 构造n个不同的类，每个类只包含一个样本

  • 合并类间距离最小的两个类，以最短距离为类间距离，构造一个新类

  • 计算新的类和当前各个类的距离，如果类的个数为1则停止计算，否则返回上一步

K-means算法

基本介绍

K-Means聚类(也叫做K均值聚类)是一种基于样本集合划分的聚类算法，k均值将样本集合划分称为k个子集，每个样本只属于一个类，因此是一种硬聚类的算法(相对的，软聚类算法是结果中每个样本可能属于多个类的算法)

对于给定的样本集合X，每个样本用特征空间中的特征向量来表示，我们希望将样本分成k个不同的类别\(G_k\)并且满足： $$ G_i\cap G_j=\emptyset\quad \bigcup\limits_{i=1}^{k}G_i=X $$ 可以用C来表示这样的一个划分关系，而一个划分关系也就对应着一个K均值分类的结果，划分C是一个函数，可以表示为： $$ C(x_i)=G_k $$ 表示一个样本的最终划分结果，而K均值算法在训练的过程中采用最小化损失函数的方式来选择最优的划分函数C

K-Means的loss函数

K-Means采用欧几里德距离，并且用所有点到其所在的类的中心的距离的平方和作为损失函数： $$ W(C)=\sum_{l=1}^k\sum_{C(i)=l}||x_i-\bar x_l||^2 $$ 因此实际上K-Means算法的求解就是一个优化问题： $$ C^*=\arg\min W(C)=\arg\min\sum_{l=1}^k\sum_{C(i)=l}||x_i-\bar x_l||^2 $$

K-Means算法的训练过程

根据上面所确定的损失函数，K-Means算法的训练过程可以这样描述：

  1. 首先要随机选K个样本作为初始的K个类的中心点，然后进行如下步骤

  2. 对于每个样本点，计算其与K个类的中心点，然后在选择最近的中心点所在的类作为该样本点的类

  3. 第2步的循环完成之后，在每个类中找到使得到该类中的所有样本点距离最小的中心点，使得该类中距离，也就是该类的样本中所有点的均值

  4. 然后回到第2步用新的K个中心点计算出新的分类，重复上述步骤直到划分结果不再改变，就得到了K均值聚类的最终结果

K-Means算法的特点

  1. K均值聚类属于启发式的方法，不能保证收敛到全局的最优，初始中心的选择会直接影响聚类的结果，要注意的时候类中心的移动往往不会有非常大的波动

  2. 不同的类别数K会带来不同的聚类结果，一般来说分类的平均直径会随着K的增大先减小后不变，这个算法中的K是一个超参数，也是需要人为进行设定的

颜色主题调整

评论区~

有用的话请给我个star或者follow我的账号!! 非常感谢!!
快来跟我聊天~