聚类算法详解：从K-means到谱聚类

"相似度图G的建立方法-聚类算法基础" 在机器学习领域，聚类是一种无监督学习方法，用于发现数据集中的自然结构，将相似的数据分组到一起，形成所谓的“簇”。相似度图G的建立是聚类算法的基础，它描述了数据点之间的相互关系。本文将详细介绍几种常见的相似度图构建方法以及聚类算法的相关概念。 1. ε近邻图：ε近邻图是一种基于固定半径ε的图构建方法，如果两个数据点之间的距离小于ε，则它们之间建立边。这种方法简单直观，但可能产生许多孤立的节点或小簇。 2. k最近邻图(kNN图)：kNN图是每个数据点与其最近的k个邻居相连的图。可以是有向或无向，有向图表示单向的最近邻关系，无向图则表示双向的最近邻关系。互k最近邻图（mutual kNN）则更进一步，只有当双方都是彼此的k个最近邻时，两点之间才连边。 3. 全连接图：在全连接图中，所有数据点之间都有边相连，这在数据点数量较少时是可行的，但在大数据集上会变得过于复杂。 4. 高斯相似度函数：这是一种基于距离的相似度度量，通常采用高斯函数（也称为正态分布）来计算。随着两点之间距离的增加，相似度降低。 聚类的目标是将数据集分为多个类别，使得同一类别内的数据点相互相似，而不同类别的数据点相异。这里提到了几种聚类方法： 1. K-means算法：K-means是最常用的聚类算法之一，它基于距离度量（通常为欧氏距离）。算法的核心是迭代过程，通过不断调整簇中心和分配对象来最小化簇内的平方误差总和。然而，K-means对初始中心点的选择敏感，可能陷入局部最优。 2. 层次聚类：这种聚类方法通过逐步合并或分裂簇来构建层次结构，可以生成树形图（Dendrogram），提供对簇结构的不同级别的洞察。 3. 密度聚类：包括DBSCAN（Density-Based Spatial Clustering of Applications with Noise）和密度最大值聚类。这些方法不依赖于预设的簇数量，而是基于数据点的密度来发现簇。DBSCAN能处理不规则形状的簇，并且可以识别噪声点。 4. 谱聚类：谱聚类利用数据的拉普拉斯矩阵进行聚类，通过最小化数据点之间的切割损失或最大化类间边的差异来找到簇。这种方法对簇的大小和形状适应性较好。 此外，最大熵模型和决策树虽然在此处未详细展开，但它们也是机器学习的重要组成部分。最大熵模型常用于建模不确定性，例如在决策树的特征选择过程中；而逻辑回归，作为最大熵模型的一种，其对数似然函数是凸函数，确保了梯度上升法能找到全局最优解。 相似度图的构建是聚类算法的关键步骤，不同的图构建方法会引导出不同的聚类结果。理解和选择合适的图构建方法以及聚类算法，对于解决实际问题至关重要。