机器学习数据集可能包含数百万个示例，但并非所有聚类算法都能高效扩展。许多聚类算法会计算所有示例对之间的相似性，这意味着它们的运行时间会随着示例数量的平方（在复杂性表示法中用 \(n\)表示）而增加。 \(O(n^2)\) 对于包含数百万个示例的数据集，这些算法并不实用。 \(O(n^2)\)
k-means 算法的复杂度为 \(O(n)\)，这意味着该算法会随着 \(n\)线性扩缩。本课程将重点介绍此算法。
聚类类型
如需查看不同聚类方法的详尽列表，请参阅 A Comprehensive Survey of Clustering Algorithms（聚类算法的全面综述），Xu, D. & Tian, Y. Ann。数据。Sci. (2015) 2: 165. 每种方法都最适合特定的数据分布。本课程将简要介绍四种常见方法。
基于质心的聚类
集群的质心是集群中所有点的算术平均值。基于中心点的聚类会将数据整理为非层次结构的聚类。基于质心的聚类算法高效，但对初始条件和离群值敏感。其中，k-means 是最常用的算法。它要求用户定义质心点数量 k，并且适用于大致等大小的集群。
基于密度的聚类
基于密度的聚类会将示例密度较高的连续区域连接到集群中。这样，便可发现任意数量的任意形状的集群。系统不会将离群值分配到任何簇。这些算法难以处理不同密度的集群和高维数据。
基于分布的聚类
这种聚类方法假定数据由概率分布（例如高斯分布）组成。在图 3 中，基于分布的算法会将数据聚类为三个高斯分布。随着与分布中心的距离增加，点属于该分布的概率会降低。这些条带显示了概率的降低。如果您不确定数据的特定底层分布，则应使用其他算法。
层次聚类
层次聚类会创建一个聚类树。毫不奇怪，层次聚类非常适合分层数据，例如分类。如需查看示例，请参阅 Oksana Lukjancenko、Trudy Wassenaar 和 Dave Ussery 撰写的Comparison of 61 Sequenced Escherichia coli Genomes。通过在正确的层级截断树，可以选择任意数量的集群。
