聚类算法

机器学习数据集可能包含数百万个示例,但并非所有聚类算法都能高效扩展。许多聚类算法会计算所有示例对之间的相似性,这意味着它们的运行时间会随着示例数量的平方(在复杂性表示法中用 \(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,并且适用于大致等大小的集群。

使用基于质心的聚类方法将示例划分到各个集群。
           线条表示集群之间的边界。
图 1:基于中心点的聚类示例。

基于密度的聚类

基于密度的聚类会将示例密度较高的连续区域连接到集群中。这样,便可发现任意数量的任意形状的集群。系统不会将离群值分配到任何簇。这些算法难以处理不同密度的集群和高维数据。

使用基于密度的聚类方法将示例划分为两个集群。
      这些集群无法线性分离。
图 2:基于密度的聚类示例。

基于分布的聚类

这种聚类方法假定数据由概率分布(例如高斯分布)组成。在图 3 中,基于分布的算法会将数据聚类为三个高斯分布。随着与分布中心的距离增加,点属于该分布的概率会降低。这些条带显示了概率的降低。如果您不确定数据的特定底层分布,则应使用其他算法。

使用基于分布的聚类方法对示例进行分组。每个集群中示例密度的阴影显示了这些集群如何映射到分布。
图 3:基于分布的重合示例。

层次聚类

层次聚类会创建一个聚类树。毫不奇怪,层次聚类非常适合分层数据,例如分类。如需查看示例,请参阅 Oksana Lukjancenko、Trudy Wassenaar 和 Dave Ussery 撰写的Comparison of 61 Sequenced Escherichia coli Genomes。通过在正确的层级截断树,可以选择任意数量的集群。

使用分层树对动物进行分组。
图 4:按层次树状结构对动物进行聚类的示例。