北大公开课-人工智能基础 57 机器学习的任务之聚类
简单来说，聚类就是将数据分成不确定的组（怎么分组，分成几组，用什么标准分组，都是基于具体的数据来确定的。）
聚类没有训练数据。——无监督学习
而分类是事先就想好分成特定的组，事先已经确定好分组的规则和目的。
分类有训练数据。——有监督学习
这样看，聚类比分类更难。
聚类是机器学习中的一类无监督学习方法，其目标是将数据对象按照相似性分组的任务。聚类的形式化描述是：对于给定的数据集，将其划分为k个不相交的簇，使得每个簇内部的对象相似度较高，而不同簇之间的对象相似度较低123。例如，将一组人根据他们的年龄、性别、收入等特征分成不同的群体，以便更好地了解他们的行为和需求2。
选择合适的聚类算法需要根据具体的应用场景、数据特点、数据可视化或者聚类效果来综合考虑，从而达到最佳的效果。常见的聚类算法包括基于距离的聚类算法（例如K-Means、PAM、CLARANS等）和基于密度的聚类算法（例如DBSCAN、OPTICS等）1。
在选择聚类算法时，需要考虑以下几个因素2：
数据量：对于大规模数据集，可以使用基于采样的聚类算法。
数据类型：对于不同类型的数据，可以使用不同的距离度量方法。
聚类数量：对于已知聚类数量的情况，可以使用划分聚类算法；对于未知聚类数量的情况，可以使用层次聚类算法。
聚类形状：对于球形簇，可以使用K-Means等基于距离的聚类算法；对于任意形状簇，可以使用基于密度的聚类算法。
噪声：对于存在噪声的数据集，可以使用基于密度的聚类算法。
总之，在选择合适的聚类算法时需要根据具体情况进行综合考虑。1
基于连接性的聚类算法是一种基于距离的聚类方法，也称为分层聚类。该算法根据距离将对象连接起来形成簇（cluster），并且与附近的对象而不是较远的对象更为相关。例如，对于一组人，可以根据他们的年龄、性别、收入等特征计算出他们之间的距离，然后将距离较近的人连接起来形成簇12。
一个具体的例子是：假设有一组人，他们的年龄、性别、收入如下表所示。我们可以使用基于连接性的聚类算法将这些人分成不同的群体。
首先，我们可以计算出每个人之间的距离，例如使用欧氏距离2。然后，我们可以将距离较近的人连接起来形成簇。例如，如果我们将阈值设置为2000，则A和B会被连接起来形成一个簇；C和E会被连接起来形成另一个簇；D会单独形成一个簇2。
基于中心点的聚类算法是一种Partition-based methods一类的聚类算法，核心思想就是：初始化中心点，然后通过启发式算法，达到”类内的点都足够近，类间的点都足够远“的目标。常见的基于中心点的聚类算法有K-Means、K-Medoids等1。
以K-Means为例，其具体步骤如下：
随机选择k个数据点作为初始聚类中心。
对于每个数据点，计算其到k个聚类中心的距离，并将其归入距离最近的聚类中心所在的簇。
对于每个簇，重新计算其聚类中心。
重复步骤2和3，直到聚类中心不再发生变化或达到预定迭代次数。
基于多元正态分布的聚类算法是一种基于概率分布的聚类算法，也称为高斯混合聚类（Gaussian Mixture Model，GMM）1。它假设每个簇符合不同的高斯分布，也就是多元正态分布，每个簇内的数据会符合一定的数据分布12。
以GMM为例，其具体步骤如下：
随机初始化k个高斯分布的参数。
E步：计算每个样本属于每个高斯分布的概率。
M步：根据E步计算出的概率重新估计高斯分布的参数。
重复步骤2和3，直到收敛1。
基于密度的聚类算法是一种基于概率分布的聚类算法，它假设簇是由数据密度相对较高的区域组成的，可以在有噪音的数据中发现各种形状和各种大小的簇。其中，DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是该类方法中最典型的代表算法之一。
以DBSCAN为例，其具体步骤如下：
随机选择一个未被访问过的点p。
找到以p为中心，半径为ε内的所有点。
如果p周围的点数大于等于MinPts，则将p标记为核心点，并将其周围的所有点加入同一个簇中。
如果p周围的点数小于MinPts，则将p标记为噪声点。
重复步骤2-4，直到所有点都被访问过1。
基于密度峰值的聚类算法（DPC）是一种基于快速搜索和发现密度峰值的聚类算法，它能够自动地发现簇中心，实现任意形状数据的高效聚类。该算法基于两个基本假设：1）簇中心是密度峰值，2）簇中心周围的点密度相对较高。
以DPC为例，其具体步骤如下：
计算每个点的局部密度。
找到所有局部密度比该点大的点，并计算它们的距离。
找到所有距离比该点小的点，并计算它们的局部密度。
将局部密度和距离作为坐标系中的坐标，找到所有局部密度和距离都比该点大的点，该点即为簇中心。
将所有簇中心相互连接，形成聚类结果。
根据密度峰值聚类的具体应用，人脸识别
常见的聚类算法有很多种，这里列举一些比较常用的：
K均值聚类（K-means clustering）：将数据集分成K个簇，每个簇的中心是该簇所有数据点的平均值。
基于密度的聚类（Density-based clustering）：将高密度区域划分为簇，并在低密度区域之间划分边界。
层次聚类（Hierarchical clustering）：将数据集分成一系列嵌套的簇，可以是自顶向下或自底向上。
均值漂移聚类（Mean shift clustering）：通过寻找密度函数的最大值来确定簇中心。
谱聚类（Spectral clustering）：将数据集投影到低维空间，然后使用K-means等算法进行聚类。
PAM（Partitioning Around Medoids）算法是K-medoid（K中心点划分）的一种流行的实现1。它是一种基于贪心策略的聚类算法，通过不断地交换簇中的对象，来寻找最优的簇中心点（medoids）。
【PAM】
PAM 算法的具体步骤如下：
随机选择k个对象作为初始medoids。
对于每个非medoid对象，计算它与所有medoids之间的距离，并将其分配到距离最近的medoid所在的簇中。
对于每个簇，选择一个非medoid对象替换当前medoid，并计算新的代价函数（所有对象到其所属簇中心点的距离之和）。
如果新的代价函数比当前代价函数更小，则接受这个替换，否则保留原来的medoid。
PAM算法适用于小数据集，但对于大数据集而言，计算量较大，效率较低。
