机器学习-聚类

聚类是一种主要用于处理分类的无监督任务。给出一组无标记的数据，目标是找到这组数据的模式特征，例如哪些数据是同一类型的，哪些数据是另外的类型。聚类与分类的最大区别就是分类的目标实现已知，例如我们熟知的猫狗大战，在进行分类之前我们就已经知道给定的样本非猫即狗，但是在聚类的时候，对目标是未知的，只能根据给定的数据的特征，按照自己设定的划分标准将样本进行划分

K-means

k均值聚类是最基础最常用的聚类算法，基本思想是：通过迭代的方式寻找K个簇的一种划分方案，是的聚类结果的代价函数最小，一般使用各个样本距离所属簇的中心点的误差平方和。常用的距离计算的方法有欧氏距离，曼哈顿距离和余弦相似性距离。

k-means的工作流程

• 首先对数据进行预处理，数据归一化以及离群点删除；
• 随机选取K个点作为k个簇的中心点；
• 计算样本中各个样本与选取的k个值的距离，把每个数据样本分配到距离其最近的聚类中心所属于的簇，成本函数$J=\frac{1}{m}{\sum }^m\mathrm{\mid }\mathrm{\mid }{x}_i-u\mathrm{\mid }{\mathrm{\mid }}^2$
• 重新计算各自簇的中心，使用属于该簇中所有点的平均值作为新的簇的中心；
• 不断迭代直到聚类中心不再移动。

代码可以参考：

• Python实现：https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/10.kmeans/kMeans.py

• sklearn实现：https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/10.kmeans/kMeansSklearn.py

k均值聚类的优缺点

K-means针对的数据类型为数值型数据

• 优点
  • 无监督学习，无需准备数据集
  • 对于大数据集，K-means是可伸缩和高效的
  • 计算复杂度$NKt$ 其中N为样本规模，K为设置的簇的数量，t为迭代的轮数
  • 原理简单，实现容易，可解释性强
• 缺点
  • 会受到初始值和离群点的影响；
  • 结果通常不是全局最优，一般是局部最优，大规模数据集收敛较慢;
  • 无法解决簇分布比例差别比较大的情况，比如有两个簇，但是两个簇的样本量差别很大(一个簇包含100个样本，另一个簇包含10个样本)，那么数量少的那个簇很容易会无法提取到;
  • 需要人工干预进行$k$设置

调优方法

• 数据归一化和离群点处理，归一化是由于代价函数为距离，要进行归一化处理，离群点或噪声会对均值产生很大影响。

• k值的选择

  • 手肘法：横轴K，纵轴为代价损失，随着k增加，代价损失会降低，选择代价函数降低幅度显著变小的点对应的k值，这种方法不够自动化，并且很依赖经验

  • Gap Statistic方法：$Gap(K)=E(log{E}_k)-log{D}_k$

    其中$E(log{E}_k)$代表$log{D}_k$的期望，在样本空间所在的区域内，按照均匀分布生成和原始样本数量相同的随机样本，并对这个样本进行k均值，得到一个$D_k$,重复多次计算出$E(log{E}_k)$的近似值。

  • 核函数

    类似于svm的方法，对原始数据样本进行非线性映射，将输入空间的数据点映射到高维特征空间，并在新的特征空间中进行聚类。

  • 二分$k-means$

    该算法首先将所有点作为一个簇，然后将该簇一分为二。之后选择其中一个簇继续进行划分，选择哪一个簇进行划分取决于对其划分时候可以最大程度降低 SSE（平方和误差）的值。上述基于 SSE 的划分过程不断重复，直到得到用户指定的簇数目为止。

k-means++

针对k-means中的k个初始值的选择进行了改进。

在k-means中初始k个点选择为全部随机选择。在**k-means++**中，假设已经选取了n个聚类中心，在选择第n+1个聚类中心时，距离当前n个聚类中心更远的点会有更高的概率被选为第n+1个点；第一个点仍然是随机选择，从第二个点开始，按照如上原则进行选择。

ISOdata算法

针对k-means中k大小的选择进行了改进

• 思想：

  当属于某一个簇的数量样本少于一定阈值是，把这个类进行删除(合并操作)；当属于某个簇的样本数量过多、分赛程度较大时，把该簇分为两个簇(分裂操作)。在原来k-means的基础上增加了合并操作和分裂操作。

• 有四个参数需要设置

  • 预期聚类中心数K，最终输出的聚类中心数一般为0.5k~2k
  • 最大方差$\sigma$：控制簇内样本的分散程度
  • 每个类别要求的最少数目$N_{min}$：如果分裂之后导致某个子簇的样本数量小于该阈值，不对这个簇进行分裂操作
  • 两个类之间允许的最小聚类距离$D_{min}$：如果两个簇中心小于最小聚类距离，将两个簇进行合并

EM算法

如果概率模型既包含观测变量，又包含隐变量。如果只包含观测变量，那么可以使用极大似然估计的方法或者贝叶斯估计的方法进行模型参数的计算，但是当包含隐变量时，就要使用EM算法。EM算法包含两部：

• E：求隐变量的期望$Q(z^{(i)})=P(z^{(i)}\mathrm{\mid }{x}^{(i)},\theta )$

• m=M:求极大得到模型参数：
  $$\theta =argma{x}_{\theta }\sum _{i=1}^m\sum _{z^{(i)}}{Q}_i(z^{(i)})log\frac{P(x^{(i)},z^{(i)}\mathrm{\mid }\theta )}{Q_i(z^{(i)})}$$
  K均值聚类是一种EM算法。

先固定一个变量是整体函数为凸优化函数，求导得到最值，然后利用最优化参数更新被固定的变量

高斯混合模型

使用多个高斯分布函数的线性组合来对数据分布进行拟合，理论上能够拟合出任意类型分布。

• 核心思想：

  假设数据可以看做从多个高斯分布中生成出来，每个单独的分模型都是标准高斯分布，均值为${\mu }_i$和方差${\sigma }_i$是待估计的参数，每个分模型还有一个参数${\pi }_i\text{}$认为是权重或者生成数据的概率

• 高斯混合分布公式：
  $$p(x)=\sum _{i=1}^K{\pi }_{i}N(x\mathrm{\mid }{\mu }_i,{\sigma }_i)$$
  每次循环时，首先固定当前高斯分布不变，获得每个数据点由各个高斯分布生成的概率；然后固定生成概率不变，根据数据点和生成概率，获得一个更加的高斯分布，更新高斯分布的参数。

• 高斯分布不仅可以用于聚类，还可以用于概率密度的估计，并且生成新的样本点