无监督聚类

定义

无监督聚类也常称为聚类分析或集群分析，指对一组数据对象进行分组，使同一组（簇）内的对象具有较高的相似性，而不同组的对象差异较大^[1][2]。它与分类的主要差别在于，聚类要划分的类别事先未知，也没有带类别标记的训练实例，标记由算法自行确定^[2]。相似性通常用坐标系中的距离等度量来刻画^[1]。

聚类的概念本身难以精确界定，不同研究者采用不同的聚类模型，同一模型下还可派生出多种算法，因此不同算法得到的簇在性质上往往差别很大^[1]。按模型划分，常见的有以距离连通性为基础的层次聚类、用均值向量表示每个簇的K-均值聚类、借助统计分布建模的期望最大化算法，以及把簇定义为相连密集区域的DBSCAN 和 OPTICS 等^[1]。按隶属方式划分，可分为每个对象只归入一个簇的硬聚类，以及对象以一定隶属程度分属各簇的软聚类，后者也称模糊聚类^[1]。

原理

聚类算法没有统一形式，共同点在于先规定对象之间的相似性或距离，再据此把对象划入簇^[1]。以 K-均值（k-means）为例，算法在分配与更新两个步骤之间反复迭代：先把每个观测指派到均值距离最近的簇，再把各簇均值更新为该簇所有点的质心^[3]。该过程等价于最小化簇内平方和，即 $J=\sum_{i=1}^{k}\sum_{x\in S_i}\lVert x-\mu_i\rVert_2^2$^[3]。由于两步都在降低同一目标函数，算法必定收敛，但只能保证达到局部最优，结果还取决于初始质心的选取^[3][4]。

flowchart TD

A[确定簇数 K 并初始化质心] --> B[把每个点分配给最近的质心]

B --> C[重新计算各簇质心]

C --> D{质心是否改变}

D -- 是 --> B

D -- 否 --> E[输出簇划分]

层次聚类借助距离连通性构造嵌套的簇层次：自下而上的凝聚方法先让每个对象各自成簇，再逐步合并，自上而下的分裂方法则从整体出发不断拆分，结果常用树状图呈现^[5]。衡量两个簇之间距离的准则包括最小距离（单链）、最大距离（全链）和平均距离等，采用不同准则会在同一数据上得到不同的簇^[5][6]。密度聚类则是在数据空间中寻找被低密度区域分隔开的稠密区域^[1]。

许多划分式算法需要事先给出簇的数目，实践中常用肘部法观察簇内平方和随簇数增加的变化，取曲线转折处对应的取值^[7][8]。轮廓系数由样本的平均簇内距离与平均最近簇间距离算出，取值范围为 -1 到 1，数值越大表示划分越合理^[8]。Davies-Bouldin 指数越小表示聚类效果越好，Calinski-Harabasz 指数则越大越好^[7][8]。

发展历程

K-均值算法有多个彼此独立的提出者。1957 年 Steinhaus 提出相关思想，同年 Lloyd 在贝尔实验室为脉冲编码调制设计了标准算法，但该算法直到 1982 年才在贝尔实验室之外公开发表^[3][9]。1965 年 Forgy 发表了实质相同的方法，因此这一算法有时被称为 Lloyd-Forgy 算法；1967 年 MacQueen 首次使用 k-means 这一名称，并给出完整步骤^[3][10]。此外，Cox 在 1957 年、Ball 与 Hall 在 1967 年也分别独立提出了类似算法^[11]。

1996 年，Ester、Kriegel、Sander 与 Xu 在知识发现与数据挖掘会议（KDD）上发表 DBSCAN，把基于密度的聚类引入数据挖掘领域，该方法能够发现任意形状的簇，并对噪声具有较好的稳健性^[12]。这篇论文在 2014 年获得 SIGKDD 时间检验奖，基于密度的聚类此后成为主要的聚类范式之一^[12]。

2007 年，Arthur 与 Vassilvitskii 提出 k-means++ 初始化方法，通过选择在数据空间中彼此分散的初始质心来改善收敛表现^[4]。层次聚类方面，凝聚式的 AGNES 与分裂式的 DIANA 是两类经典算法^[6]。聚类方法的来源跨越多个学科，与数学、计算机科学、统计学、生物学和经济学都有渊源^[2]。

应用

聚类是数据挖掘的主要任务之一。它既可作为独立工具考察数据分布、观察各簇的特征，也可作为分类、定性归纳等算法的预处理步骤^[2]。在机器学习、数据挖掘、模式识别、图像分析和生物信息等领域，聚类被用来描述数据、衡量不同数据源之间的相似性，并把数据归入不同的簇^[1]。

在商业分析中，聚类可用于市场细分。有研究以 592 名啤酒饮用者的调查数据为样本，先用因子分析提取潜在维度，再用 Ward 法的层次聚类判断簇数，最后以欧氏距离的 K-均值得到 5 类消费者，并比较各群体在品牌忠诚度和购买意愿上的差异^[4]。层次聚类还被用于临床研究中的人群分组、客户细分，以及网络模型中节点社区的发现^[5]。

在空间数据库领域，DBSCAN 用于从带有噪声的大型空间数据中识别类别，并可借助空间索引结构支持范围查询以提升处理效率；原论文用合成数据和 SEQUOIA 2000 基准的真实数据进行了验证^[13][12]。

局限

聚类没有唯一正确的答案，同一组数据由不同研究者分析，得到的簇数未必一致^[2]。理论上也不存在对所有情形都适用的算法：Kleinberg 在 2003 年证明，没有哪一种聚类算法能同时满足若干基本公理^[14]。此外，参数化方法需要事先掌握数据分布、簇结构或簇数等信息，离群点的处理也是其主要困难之一^[14]。

K-均值要求用户预先指定簇数，结果对初始质心敏感，不同初始化可能得到不同解，其有效性建立在簇近似球形、各维方差相近等假设之上^[4][3]。层次聚类对噪声较敏感，倾向于形成球形簇，计算开销偏大，难以适用于大规模和高维数据，而且合并或分裂一旦执行便无法撤销^[14][5]。

密度聚类虽然能识别任意形状的簇，但在维数很高、例如超过 10000 维的数据上通常难以扩展^[15]。聚类质量的判断本身也存在困难：轮廓系数一类内部指标不需要外部信息，而兰德指标、调整互信息等外部指标的计算必须借助真实标签^[7]。

参见

• 无监督学习 —— 聚类通常被归入这一类不需要标签的学习方法。

• K-均值聚类 —— 最常用的划分式聚类算法之一，通过迭代降低簇内平方和。

• DBSCAN —— 基于密度的聚类算法，可发现任意形状的簇并识别噪声点。

• 层次聚类 —— 通过反复合并或分裂构建嵌套簇结构的方法。

• 期望最大化算法 —— 常用于求解分布模型聚类的迭代算法。

• 数据挖掘 —— 聚类是其主要任务之一，也常作为其他任务的预处理步骤。