【数据挖掘 15】聚类算法01：简介
文章目录
1. 聚类算法简介
聚类（Clustering）是一种涉及数据点分组（clusters）的机器学习技术。给定一组数据点，我们可以使用聚类算法将每个数据点分类到特定的组（簇）中。理论上，同一组中的数据点应具有相似的属性或特征，而不同组中的数据点应具有较大差异的属性或特征。聚类是无监督学习的一种方法，也是用于许多领域中统计数据分析的常用技术。
在对相似示例进行分组之前，首先需要查找相似示例。您可以通过将示例的特征数据组合到一个度量（称为相似性度量（ similarity measure））中来度量示例之间的相似性。当每个示例由一个或两个功能定义时，很容易衡量相似度。随着特征数量的增加，创建相似性度量变得更加复杂。
2. 聚类算法应用
聚类算法在很多工业领域都有很广泛的应用。一些常用的例子包括：
- 市场划分（market segmentation）；
- 社交网络分析（social network analysis）；
- 搜索结果分组（search result grouping）；
- 医疗图像（medical imaging）；
- 图像分割（image segmentation）；
- 异常检测（anomaly detection）；
聚类之后，每一个簇都被分配一个簇ID，此时可以将样本的所有特征对应到一个簇ID，通过这样简单的簇ID来压缩样本的特征使得聚类算法非常有用。通过这样的思想，聚类算法可以轻易的简化大型数据集合。
例如，可以通过不同的特征将下例进行分组：
- 将星星按亮度分组；
- 将生物按照遗传信息分为不同的类；
- 将文件按主题分组；
机器学习系统可以使用这些簇编号来简化大型数据集的处理。因此，聚类的输出用作机器学习系统的特征数据。
在Google，聚类算法用于油管视频，谷歌商店App以及音乐曲目等产品中的概括（Generalization），数据压缩（Data Compression）和隐私保护。
2.1 Generalization
当聚类中的某些示例缺少特征数据时，可以从聚类中的其他示例推断出缺失的数据。例如，较不受欢迎的视频可以与较受欢迎的视频聚在一起，以改善视频推荐。
2.2 Data Compression
如讨论的那样，聚类中所有示例的特征数据都可以由相关的簇ID代替。 这种替换简化了特征数据并节省了存储空间。 当扩展到大型数据集时，这非常重要。 此外，机器学习系统可以使用簇ID代替整个特征数据集作为输入。减少输入数据的复杂性使ML模型更简单，更快速地训练。
例如，一个油管视频的特征数据包括：
- 包含位置，时间和人数的观看者数据；
- 包含时间戳，文本和用户ID的评论；
- 视频标签；
聚类油管视频使得可以用单一的簇ID代替复杂的特征数据，从而实现数据压缩。
2.3 Privacy Preservation
通过聚类算法，使用簇ID来代表用户数据而不是用具体的用户数据，可以达到保护用户隐私的目的。
例如，如果你想将用户的油管视频观看历史加入到模型中。不依靠具体的用户ID，而是使用聚类用户后的簇ID。这样模型就可以将视频观看历史数据用过簇ID关联，而并非具体的用户数据。
3. 聚类算法概览
在选择聚类算法时，应该首先考虑算法是否能够缩放数据集。机器学习领域中的数据集通常包含数以百万计的样本，但是并非所有的聚类算法可以高效的缩放数据特征。许多聚类算法通过计算所有成对样本的相似度来实现聚类，这意味着他们的算法时间复杂度为样本数量 n n n 的平方，即 O ( n 2 ) O(n^2) O(n2)。
2015年，Xu, D. & Tian, Y. 等人的论文 《A Comprehensive Survey of Clustering Algorithms》中对聚类算法做了综述。每种聚类算法都对应独特的数据分布。下文多常用算法做了简单的介绍。
3.1 基于中心的聚类
基于中心的聚类（Centroid-based Clustering）将数据组织为无层次的聚类，与层次聚类算法相比。k-means算法是一类应用非常广泛的基于中心的聚类算法。基于中心的聚类算法非常高效，但是对初始化条件和异常值非常敏感。
基于中心的聚类算法的聚类目标是使得类内的点足够近，类间的点足够远。常用的算法有k-means及其衍生算法。
3.2 基于密度的聚类
基于密度的聚类（Density-based Clustering）将样本划分到密度高的区域实现聚类，这使得聚类结果可以为任意形状的分布，只要样本可以连接到密集的区域。但是这些算法难以处理不同密度和高维数据。
其核心思想是：当邻近区域的密度超过某个阈值，则继续聚类。常用算法有DBSCAN，OPTICS等。
3.3 基于分布的聚类
基于分布的聚类（Distribution-based Clustering）算法假设数据具有固定的分布，比如高斯分布（Gaussian distribution）。图3中，基于分布的聚类算法将图中的数据点划分为3个具有高斯分布的簇。随着样本数据与分布中心距离的增加，某个样本属于某一分布的概率逐渐下降，图中不同的圆带显示了概率的下降。当不知道数据的分布时，应该使用不同的算法。
常用的算法有期望最大化（EM）算法。
3.4 基于层次的聚类
层次聚类（Hierarchical clustering）创建了三个聚类树，不出所料，层次聚类适合具有层次的数据，比如物种分类（taxonomies），具体可参考Oksana Lukjancenko, Trudy Wassenaar, Dave Ussery的论文《Comparison of 61 Sequenced Escherichia coli Genomes》。此外，另一个优势是通过在正确的层次上切分树，可以生成任意数量的簇。
基于层次的聚类算法实际上可以看作是二叉树的生成和分裂过程。常用算法有HDBSCAN等。
3.5 基于图的聚类
通过建图来进行聚类，在聚类算法中的占比较大，很多较新的聚类算法都有图聚类的思想。两大具有代表性的图聚类算法为Chinese Whisper和谱聚类。
3.6 基于GCN的聚类
本质上也是基于图的聚类，然而基于图卷积神经网络（GCN）的聚类算法会有深度学习中的训练的概念，而传统的聚类算法则是通过人工设定阈值来决定的。具体可参考《Learning to Cluster Faces on Affinity Graph》（CVPR2019），CDP（ECCV2018）两篇论文的思想。
4. 聚类算法的工作流程
聚类算法简单来说包含四个步骤：
- 准备数据；
- 创建相似性矩阵；
- 运行聚类算法；
- 解释结果并应用。
4.1 准备数据
在处理任何机器学习问题时，第一步必须归一化，缩放和转换特征数据。而对于聚类算法来说，必须额外确保准备的数据可以使得聚类算法准确地计算出样本之间的相似性。关于数据转换的相关内容可以参考：Here。
4.2 创建相似性矩阵
在聚类算法可以对数据进行分组之前，需要知道成对数据之间的相似性。可以通过创建的相似性矩阵来度量样本之间的相似性。
4.3 运行聚类算法
一种基于相似度度量的聚类算法，本课程着重于k-means。
4.4 解释和应用结果
检查集群输出的质量是迭代的和探索性的，因为集群缺乏可以验证输出的真相。可以在集群级和示例级根据预期验证结果。改进结果需要迭代地试验前面的步骤，以了解它们如何影响集群。
参考：
https://zhuanlan.zhihu.com/p/38740660
https://zhuanlan.zhihu.com/p/78382376
https://developers.google.com/machine-learning/clustering/overview
https://developers.google.com/machine-learning/data-prep/transform/introduction