本文来自之前在Udacity上自学机器学习的系列笔记。这是第16篇，介绍了什么是聚类（1），介绍K-均值、单链路聚类和基于密度的聚类三种。
K-均值（K-Means）
K-均值可以分为两个步骤，第一步是分配，第二步是优化。对于M个数据点划分为k类的问题，首先假设K个初始聚类中心；然后，计算各个数据点到这k个中心的距离，按照最近原则分配到各个中心；接着，计算每个聚类的均值点，作为新的聚类中心；最后，重复地按照最近原则进行分配和优化，直至每个聚类的数据点距离其中心足够小，而每个聚类中心距离足够大为止。
上面提到的距离常用的有欧氏距离，假设数据点都是N维的向量，那么数据点的距离为：
上面提到的距离足够小，可以使用损失函数来定义，也就是判断各个聚类的数据点到聚类均值点的均方误差。即
其中
为
簇内的数据点个数。
通过最小化E，可以得到稳定的最小化的结果。
K-均值聚类的优点是原理简单，容易解释，但是缺点是当数据量较大时，计算量也较大，需要通过反复地尝试来寻找适合的K值。
单链路聚类
单链路聚类（Single Linkage Clustering）是一种层次凝聚聚类算法（Hierarchical Agglomerative Clustering）。它的过程是：首先将M个数据点都看成M个聚类，将两个聚类之间的距离定义为两个聚类之中最接近的点之间的距离；然后，合并两个最接近的聚类；接着，按照这种合并规则，继续重复（n-k）次，其中k是我们希望划分为的聚类的个数。
比如说下面的a到g，七个点，按照上面的流程可以得到两个聚类。
这种方法从下到上进行聚类，就像化学当中的凝聚的概念一样。上面提到的距离除了可以是最小距离，还可以使用平均距离。
单链路聚类的优点是，它具备确定的唯一答案，而且是最小生成树。另外，这个算法的运行时间是，考虑到最差的情况下，n个点需要分为k个聚类，我们需要运行
次，而在每次运行时，需要考虑任意两点之间的距离，也就是
次。它存在的缺点也是当数据量比较大时，计算量也比较大。
基于密度的聚类
这种聚类方法称为DBSCAN，即Density-based Saptial Clustering of Applications with Noise。
聚类看成是数据空间中的密集区域，聚类由数据点的密度比较低的区域分隔开来。 DBSCAN算法基于“密集区域”和“噪声”的概念，对于密集区域的每个点，在给定半径的邻域内必须至少包含多少数量的点来得到聚类的结果。
对于K-均值和层次聚类的方法，它们适用于数据分布呈球状或者凸簇的数据，且容易受到噪声的影响。在现实生活中，数据分布往往是不规则的，而且包含噪声。
eps定义为围绕一个数据点的半径。MinPts定义为在这个半径内至少包含多少个点的数量。
如果一个数据点在既定的半径内包含多于MinPts个数的邻近点，那么这个点就是核心点。
如果一个数据点在既定的半径内包含少于MinPts个数的邻近点，但它是某个核心点的邻近点，那么这个点就是边界点。
如果一个点既不是核心点，也不是边界点，那么这个点就是噪声或者异常点。
DBSCAN的流程是：
- 根据每个点在既定的eps内的邻近点个数，确定核心点；
- 对于每个核心点（如果尚未分配到一个聚类），那么创建一个新的聚类；
- 递归查找核心点的eps内的相邻点，并将其分配给与核心点相同的聚类。如果存在一个点c有足够的相邻点，同时a和b点也在其中，那么a和b就称为是密度相连的。
- 遍历数据集中其余未查看的点，不属于任何聚类的点就是噪声。
具体可以参考：
https://www.geeksforgeeks.org/dbscan-clustering-in-ml-density-based-clustering/
