聚类是机器学习中一种重要的 无监督算法，它可以将数据点归结为一系列特定的组合。理论上归为一类的数据点具有相同的特性，而不同类别的数据点则具有各不相同的属性。在数据科学中聚类会从数据中发掘出很多分析和理解的视角，让我们更深入的把握数据资源的价值、并据此指导生产生活。

聚类分析就仅根据在数据中发现的描述对象及其关系的信息，将数据对象分组(簇)。其目标是，组内的对象相互之间是相似的，而不同组中的对象是不同的。组内相似性越大，组间差别越大，聚类就越好。
基于不同的学习策略，聚类算法可分为多种类型：
1.基于划分
给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K<N。
特点：计算量大。很适合发现中小规模的数据库中小规模的数据库中的球状簇。
算法：K-MEANS算法、K-MEDOIDS算法、CLARANS算法
2.基于层次
对给定的数据集进行层次似的分解，直到某种条件满足为止。具体又可分为“自底向上”和“自顶向下”两种方案。
特点：较小的计算开销。然而这种技术不能更正错误的决定。
算法：BIRCH算法、CURE算法、CHAMELEON算法
3.基于密度
只要一个区域中的点的密度大过某个阈值，就把它加到与之相近的聚类中去。
特点：能克服基于距离的算法只能发现“类圆形”的聚类的缺点。
算法：DBSCAN算法、OPTICS算法、DENCLUE算法
4.基于网格
将数据空间划分成为有限个单元（cell）的网格结构,所有的处理都是以单个的单元为对象的。
特点：处理速度很快，通常这是与目标数据库中记录的个数无关的，只与把数据空间分为多少个单元有关。
算法：STING算法、CLIQUE算法、WAVE-CLUSTER算法

聚类算法类型

K均值算法(K-means)

k-means算法是一种简单的迭代型聚类算法，采用距离作为相似性指标，从而发现给定数据集中的K个类，且每个类的中心是根据类中所有值的均值得到，每个类用聚类中心来描述。
K均值聚类的基本思想是，通过迭代方式寻找K个簇的一种划分方案，使得聚类结果对应的代价函数最小。其代价函数可以定义为各个样本距离所属簇中心点的误差平方和：
$$
J(c,\mu) = \sum_{i=1}^M {||x_i- \mu_{c_i}||}^2
$$
其中$x_i$代表第$i$个样本，$c_i$是$x_i$所属于的簇，$\mu_{c_i}$代表簇对应的中心点，$M$是样本总数。

算法流程

K-means是一个反复迭代的过程，算法分为四个步骤：
1） 选取数据空间中的K个对象作为初始中心，每个对象代表一个聚类中心；
2） 对于样本中的数据对象，根据它们与这些聚类中心的欧氏距离，按距离最近的准则将它们分到距离它们最近的聚类中心（最相似）所对应的类；
3） 更新聚类中心：将每个类别中所有对象所对应的均值作为该类别的聚类中心，计算目标函数的值；
4） 判断聚类中心和目标函数的值是否发生改变，若不变，则输出结果，若改变，则返回2）。

K-means算法流程

优缺点

  • K均值算法的优点有：

    • 相对可伸缩和高效，计算复杂度是O(NKt)接近于线性，其中N是数据数目，K是聚类簇数，t是迭代轮数。。
    • 可以灵活地设置约束条件，通过约束条件的多少可以调节模型对未知数据的适应度和对已知数据的拟合程度。

  • K均值算法的缺点有：

    • 容易受初值和离群点的影响，每次结果不稳定，需要人工预先确定初始K值
    • 结果通常不是全局最优而是局部最优
    • 无法很好的解决数据簇分布差别比较大的情况
    • 样本点只能划分到单一的类中

调优

* 数据归一化和离散点处理
* 合理选择K值（手肘法（拐点））
* 采用核函数

高斯混合模型（GMM）

高斯混合模型（GMM）的核心思想是，假设数据可以看作从多个高斯分布中生成出来的。在该假设下，我们需要寻找每个单独的分模型的均值、方差以及权重。采用EM算法框架来求解该优化问题。EM算法是在最大化目标函数时，先固定一个变量使整体函数变成凸优化函数，求导得到最值，然后利用最优参数更新被固定的变量，进入下一循环。具体到高斯混合模型的求解，EM算法的迭代过程如下：
首先，初始随机选择各参数的值。然后，重复下面两步，直到收敛：
（1）E步骤，根据当前参数，计算每个点由分模型生成的概率
（2）M步骤，使用E步骤估计出的概率，来改进每个分模型的均值，方差和权重。

高斯混合模型（GMM）

高斯混合模型与K均值算法相同点：
1.都是可用于聚类的算法
2.都需要指定K值
3.都是使用EM算法来求解
4.都往往只能收敛于局部最优

不同点：
1.混合高斯模型可以给出一个样本属于某类的概率是多少
2.不仅仅可以用于聚类，还可以用于概率密度的估计
3.可以用于生成新的样本点

DBSCAN密度聚类算法

DBSCAN(Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法)是一种很典型的密度聚类算法，和K-Means，BIRCH这些一般只适用于凸样本集的聚类相比，DBSCAN既可以适用于凸样本集，也可以适用于非凸样本集。
DBSCAN是一种基于密度的聚类算法，这类密度聚类算法一般假定类别可以通过样本分布的紧密程度决定。同一类别的样本，他们之间的紧密相连的，也就是说，在该类别任意样本周围不远处一定有同类别的样本存在。
通过将紧密相连的样本划为一类，这样就得到了一个聚类类别。通过将所有各组紧密相连的样本划为各个不同的类别，则我们就得到了最终的所有聚类类别结果。
DBSCAN算法将数据点分为三类：
　　1.核心点：在半径Eps内含有超过MinPts数目的点。
　　2.边界点：在半径Eps内点的数量小于MinPts,但是落在核心点的邻域内的点。
　　3.噪音点：既不是核心点也不是边界点的点。

算法流程

1.将所有点标记为核心点、边界点或噪声点；
2.删除噪声点；
3.为距离在Eps之内的所有核心点之间赋予一条边；
4.每组连通的核心点形成一个簇；
5.将每个边界点指派到一个与之关联的核心点的簇中（哪一个核心点的半径范围之内）。
DBSCAN密度聚类算法