K-means（K-均值）

K-means算法是一种广泛使用的聚类算法，是无监督学习，用于将数据分成 K 个簇，以便于数据分析。其步骤简要如下：

选择K个随机点作为初始的簇中心。
对于每一个数据点，计算它与每个簇中心的欧几里得距离，并将其分配给最近的簇中心所代表的簇。
对于每一个簇，重新计算簇中所有点的平均值，并将该平均值作为新的簇中心。
重复步骤2和3，直到簇中心不再发生变化，或者变化非常小，或者达到预定的迭代次数。
算法结束，输出最终的簇划分和簇中心。

K-means算法简单而有效，但其结果可能受到初始簇中心选择的影响，可能需要多次运行以获取最佳结果。此外，K-means假设簇是凸形和相似大小，因此对某些类型的数据分布可能不是最佳选择。

欧几里得距离：两点之间距离公式的扩展

KNN 和 k-means 辨析
相似点：
K-means和KNN都是基于距离度量的算法。它们使用距离来衡量数据点之间的相似性或距离。
K-means和KNN都使用K值来控制算法的行为。K-means中的K代表聚类的数量，KNN中的K代表邻居的数量。

不同点：
目标：K-means旨在将数据点划分为不同的聚类，使同一聚类内的数据点相似度较高，不同聚类之间的相似度较低。而KNN旨在通过找到最近的K个邻居来进行分类或回归预测。
学习方式：K-means是一种迭代的聚类算法，通过最小化聚类内部的方差来更新聚类中心，直到达到收敛条件。KNN是一种基于实例的学习方法，通过存储和比较训练集中的实例来进行预测。
数据需求：K-means通常要求数据点能够表示为数值向量，且距离度量可定义。KNN对数据的要求较少，可以处理不同类型的特征和度量方法。
算法复杂度：K-means的计算复杂度较低，但对初始聚类中心的选择敏感，可能会收敛到局部最优解。KNN的计算复杂度较高，因为需要计算每个测试样本与所有训练样本之间的距离。

总结而言，K-means和KNN是不同类型的机器学习算法，K-means用于聚类，而KNN用于分类和回归预测。它们在目标、学习方式、数据需求和算法复杂度等方面有显著的区别。

Mean-shift

Mean Shift算法是一种基于特征空间中的梯度上升方法的聚类技术，它不需要事先指定簇的数量，与K-means等需要预先指定簇个数的算法不同。Mean Shift的核心思想是对于给定的样本点，通过迭代移动到密度更高的区域，直至收敛到密度最大处的局部峰值。这个过程类似于“爬山”，每个样本点都朝着最陡的方向上山，直到达到山顶。这里的“山”是由特征空间中的数据点分布决定的多维概率密度函数。

Mean Shift算法的基本步骤如下：

选择核函数和带宽：Mean Shift算法需要一个核函数（如高斯核）和一个带宽参数，这个参数决定了搜索窗口的大小，影响着局部密度估计的范围。
对每个数据点执行Mean Shift向量计算：对于每一个数据点，Mean Shift 算法计算以该点为中心，带宽为半径的超球体内所有点的质心（即均值）。这个质心是当前点和其邻域内其他点位置的加权平均，权重由核函数决定。
更新数据点位置：将每个数据点移动到计算得到的质心位置。
重复迭代：重复步骤2和步骤3，直到所有点的移动距离小于某个阈值，或者达到预设的迭代次数。
识别并合并簇：由于多个数据点可能会收敛到相同的局部最大值点，因此最后需要根据一定的准则（如距离阈值）来识别和合并这些收敛点，形成最终的簇。

Mean Shift算法的优点包括不需要指定簇的数量，以及对簇的形状和大小没有严格的假设。然而，它的性能很大程度上依赖于带宽参数的选择，而且计算复杂度较高，特别是在处理大数据集时。

高斯混合模型

高斯混合模型（Gaussian Mixture Model, GMM）是一种软聚类方法，相对于硬聚类（如K-means，每个点只能属于一个类），GMM允许数据点以概率形式属于多个聚类。

GMM假设数据是由多个高斯分布混合而成的，每个高斯分布代表一个聚类。每个高斯分布由三个参数定义：均值（mean）决定了其在特征空间中的位置，协方差矩阵（covariance matrix）决定了其形状，混合系数（mixture coefficient）表示该高斯分布在所有数据点中的占比。

GMM聚类的步骤大致如下：

初始化：随机选择K个高斯分布的参数（均值、协方差矩阵和混合系数）或通过其他方法（如K-means聚类结果）进行初始化。
期望步骤（E-step）：基于当前的参数，计算每个数据点属于每个高斯分布的概率，这一步骤通过贝叶斯定理来完成。
最大化步骤（M-step）：利用E-step得到的概率，重新估计每个高斯分布的参数（均值、协方差矩阵和混合系数），使得数据的似然概率最大化。
迭代：重复E-step和M-step直到收敛（即参数的变化小于某个阈值或达到最大迭代次数）。

GMM聚类的优点包括：

能够适应聚类的不同形状，因为每个聚类可以具有不同的协方差结构。
每个数据点不是被硬性分配到一个聚类中，而是以概率形式表达其属于各个聚类的程度，提供了更多的信息。

但GMM也有一些局限性，如对初始值敏感，可能收敛到局部最优解，以及当数据维度高时计算量大、可能出现奇异协方差矩阵等问题。

期望最大化

EM聚类是基于期望最大化（Expectation-Maximization，简称EM）算法的聚类方法。EM算法是一种迭代优化算法，用于含有隐变量（latent variables）的概率模型参数估计问题。在聚类的上下文中，隐变量通常指的是数据点的类别标签。EM聚类特别适合于模型参数不易直接估计的混合模型，如高斯混合模型（GMM）。

EM聚类算法主要包括两个步骤：

期望步骤（E-step）：固定模型参数，计算或更新每个数据点对于各个聚类的“责任度”，即该数据点属于各个聚类的概率。这一步骤涉及到根据当前模型参数，使用贝叶斯定理计算后验概率。
最大化步骤（M-step）：固定E-step中计算得到的责任度，优化模型参数（如均值、协方差等），使得给定这些责任度下数据的似然概率最大化。这一步通常涉及到对似然函数的求导和优化。

EM算法通过迭代执行这两个步骤直至收敛，即模型参数的变化小于某个阈值或达到最大迭代次数。EM聚类算法的优点在于能够自然地处理混合模型以及软聚类（soft clustering）问题，其中数据点可以以不同的概率属于多个聚类。

然而，EM聚类也有一些局限性：

对初始参数敏感，不同的初始化可能导致不同的聚类结果。
可能收敛到局部最优而非全局最优解。
在处理高维数据时，计算成本可能会非常高，且容易受到“维度的诅咒”的影响。

由于其在统计建模和概率推理方面的基础，EM聚类广泛应用于各种领域，如图像处理、生物信息学和语音识别等。

密度聚类

密度聚类（Density-Based Clustering）是一种根据数据点的紧密程度进行聚类的方法，旨在发现被低密度区域分隔的高密度区域。这种方法的优点是可以发现任意形状的聚类，并且能够处理噪声和异常值。最著名的密度聚类算法是DBSCAN（Density-Based Spatial Clustering of Applications with Noise）。

DBSCAN

DBSCAN算法基于两个主要概念：

核心点：在指定半径（(\epsilon)）内包含足够数量（(MinPts)）的点的点被称为核心点。
边界点和噪声点：在半径(\epsilon)内少于(MinPts)的点被认为是边界点或噪声点，边界点是达到核心点的点，噪声点则是既不是核心点也不是边界点的点。

DBSCAN的步骤包括：

对每个点，计算其(\epsilon)-邻域内的点数。
标记满足(MinPts)条件的点为核心点，不满足的点为边界点或噪声点。
对每个核心点，如果它还没有被分配到任何聚类中，就创建一个新的聚类，并通过核心点的邻域递归扩展这个聚类。
迭代进行，直到所有的点都被访问过。

谱聚类

谱聚类（Spectral Clustering）是一种基于图论的聚类方法，它使用数据的相似性矩阵构建图，然后根据图的特征向量进行聚类。谱聚类特别适合于发现复杂结构的聚类，即使聚类形状非常不规则，也能获得很好的性能。

谱聚类的基本步骤包括：

构建相似性矩阵：首先根据数据点之间的相似度（如高斯核函数计算的距离）构建一个相似性矩阵。
构建图的拉普拉斯矩阵：利用相似性矩阵构建图的拉普拉斯矩阵，拉普拉斯矩阵反映了图的拓扑结构。
计算拉普拉斯矩阵的特征值和特征向量：计算拉普拉斯矩阵的特征值和相应的特征向量。
使用特征向量进行聚类：选择前(k)个特征向量（(k)是预先设定的聚类数目），利用这些特征向量的值将数据点映射到低维空间中，然后在这个低维空间中使用传统的聚类算法（如K-means）进行聚类。

谱聚类的优点是能够识别各种形状的聚类，并且对数据的缩放和旋转具有一定的鲁棒性。然而，它的计算成本较高，特别是在处理大规模数据集时，计算和存储相似性矩阵及其特征向量可能会非常耗时和占用大量内存。

【ML】聚类