R 中的层次聚类

聚类的预处理操作

在开始之前，有几件事需要先处理好。

• 缩放

在开始聚类之前，对特征值的尺度进行归一化至关重要。这是因为每条观测的特征值会被表示为 n 维空间（n 为特征数）中的坐标，随后对这些坐标间的距离进行计算。如果这些坐标未归一化，可能会导致错误的结果。

例如，假设您有三个人的身高与体重数据：A（6 英尺，75 公斤）、B（6 英尺，77 公斤）、C（8 英尺，75 公斤）。如果在二维坐标系中表示身高与体重，并计算它们之间的欧氏距离，那么以下配对的距离为：

A-B：2 个单位

A-C：2 个单位

距离度量显示 A-B 与 A-C 两对“同样相近”，但显然并非如此！A-B 比 A-C 更相似。因此，先对这些值进行缩放，再计算距离非常重要。

有多种方式可对特征值进行归一化。您可以考虑将所有特征值（x(i)）的尺度标准化到 [0,1]（称为最小-最大归一化），应用如下变换：

$ x(s) = x(i) - min(x)/(max(x) - min (x)) $

您可以使用 R 的 normalize() 函数，或自行编写如下函数：

standardize <- function(x){(x-min(x))/(max(x)-min(x))}

另一种缩放方式可通过以下变换实现：

$ x(s) = x(i)-mean(x) / sd(x) $

其中 sd(x) 为特征值的标准差。这样可确保特征值的分布均值为 0、标准差为 1。您可以使用 R 中的 scale() 函数实现。

• 缺失值填补

提前处理数据集中的 missing/null/inf 值同样重要。处理方法很多，可以删除这些值，或用均值、中位数、众数填补，或使用一些高级回归技术。R 中有许多用于缺失值填补的包与函数，如 impute()、Amelia、Mice、Hmisc 等。您可以在这篇教程中了解 Amelia。

层次聚类算法

层次凝聚聚类的关键操作是反复将距离最近的两个簇合并为更大的簇。首先需要回答三个关键问题：

• 如何表示包含多个点的簇？
• 如何确定簇之间的“接近程度”？
• 何时停止合并簇？

希望在本教程结束时，您能够回答以上所有问题。在应用层次聚类之前，先看看其工作流程：

1. 计算每对观测点之间的距离，并将其存入距离矩阵。
2. 将每个点各自放入一个簇。
3. 根据距离矩阵中的距离，开始合并最接近的点对或簇对，从而使簇的数量减少 1。
4. 重新计算新簇与旧簇之间的距离，并存入新的距离矩阵。
5. 最后重复步骤 2 和 3，直到所有簇合并为一个簇。

为了制定聚类规则，有多种测量簇间距离的方法，通常称为连接方法（Linkage Methods）。常见的连接方法包括：

• 完全连接（Complete-linkage）：在合并前计算簇间的最大距离。

• 单一连接（Single-linkage）：在合并前计算簇间的最小距离。该方法可用于检测数据集中的高值离群点，因为它们通常在最后才被合并。

• 平均连接（Average-linkage）：在合并前计算簇间的平均距离。

• 质心连接（Centroid-linkage）：分别找到簇 1 与簇 2 的质心，再在合并前计算二者之间的距离。

连接方法的选择完全取决于您，没有一成不变的最佳方法。不同的连接会得到不同的聚类结果。

树状图（Dendrogram）

在层次聚类中，您会将对象按照层级进行归类，形成类似树状的图示，称为树状图（dendrogram）。下方树状图的 y 轴显示的是拆分或合并的距离（称为高度）。

在上图中，首先将 4 与 6 合并为一簇（记为簇 1），因为它们的距离最近；随后 1 与 2 合并（记为簇 2）。之后 5 并入簇 1，再接着是 3，最终得到两个簇。最后这两个簇合并为一个簇，聚类过程到此结束。

此时您可能会好奇：如何决定何时停止合并簇？这取决于您对数据的领域知识。比如，如果您根据球员在球场上的位置（作为计算距离的坐标）对足球运动员进行聚类，您已知最终应得到 2 个簇，因为一场比赛只有两支球队。

但有时您并没有这些先验信息。在这种情况下，可以利用树状图的结果来近似估计簇的数量。做法是用一条水平线对树状图进行“切割”，选在水平线向上或向下能跨越的距离最长、且不与任何合并点相交的高度处。在上述示例中，高度 1.5 到 2.5 之间如图所示：

按照所示位置切割，您将得到两个簇。

注意：不一定只能在这种位置切割，您可以根据想要的簇数在任意高度切割。例如，在 1.5 以下且 1 以上切割会得到 3 个簇。

注意：这并非确定簇数的硬性规则。您也可以考虑 Silhouette 图、肘部图，或一些数值指标，如 Dunn 指数、Hubert gamma 等，它们显示误差随簇数（k）的变化趋势，您可以选择使误差最小的 k。

评估聚类效果

或许任何无监督学习任务中最重要的部分就是结果分析。使用任一算法与参数完成聚类后，您需要确保方法得当。但该如何判断？

可用的度量很多，其中最常见的是 Dunn's Index。Dunn 指数是最小簇间距离与最大簇内直径的比值。簇的直径指簇内最远两点之间的距离。为了获得分离良好且紧凑的簇，您应追求更高的 Dunn 指数。

层次聚类实战

现在，您将把所学应用到一个真实问题上。

我们将对 seeds 数据集执行层次聚类。该数据集包含三种不同小麦品种（Kama、Rosa 与 Canadian）籽粒的几何特性测量。变量描述了种子的面积、周长、非对称系数等性质。每个小麦品种有 70 条观测。您可以在此处查看数据集详情。

首先使用 read.csv() 函数将数据集导入为数据框。

注意：该文件没有表头，且为制表符分隔。为确保结果可复现，您需要使用 set.seed() 函数。

set.seed(786)
file_loc <- 'seeds.txt'
seeds_df <- read.csv(file_loc,sep = '\t',header = FALSE)技术支持

由于数据集没有列名，您将根据数据说明自行命名列。

feature_name <- c('area','perimeter','compactness','length.of.kernel','width.of.kernal','asymmetry.coefficient','length.of.kernel.groove','type.of.seed')
colnames(seeds_df) <- feature_name技术支持

建议先获取一些关于数据集的基本信息，如维度、数据类型与分布、NA 的数量等。您可以在 R 中使用 str()、summary() 与 is.na() 函数完成这些检查。

str(seeds_df)
summary(seeds_df)
any(is.na(seeds_df))技术支持

请注意，该数据集的所有列都是数值型。在聚类前无需清理缺失值。但各特征的量纲不同，需要进行归一化。此外，数据带有标签，您已知每条观测对应哪种小麦品种。

现在将标签单独存入一个变量，并从数据集中剔除 type.of.seed 列以便进行聚类。稍后您会用真实标签来检验聚类效果如何。

seeds_label <- seeds_df$type.of.seed
seeds_df$type.of.seed <- NULL
str(seeds_df)技术支持

如您所见，已从数据集中删除真实标签列。

接下来使用 R 的 scale() 函数对所有列进行缩放。

seeds_df_sc <- as.data.frame(scale(seeds_df))
summary(seeds_df_sc)技术支持

可以看到所有列的均值为 0、标准差为 1。完成数据预处理后，接下来构建距离矩阵。鉴于此处均为连续数值，将使用 euclidean 距离方法。

dist_mat <- dist(seeds_df_sc, method = 'euclidean')技术支持

此时应决定要使用的连接方法，然后开展层次聚类。您可以尝试各种连接方法，稍后再比较表现。在这里我们使用 average 连接方法。

使用 hclust() 构建层次聚类对象，并通过绘图生成树状图。您可以通过 method 参数指定连接方法。

hclust_avg <- hclust(dist_mat, method = 'average')
plot(hclust_avg)技术支持

请注意树状图的构建方式：最终所有数据点合并为单一簇，y 轴显示高度（距离）。

接下来，您可以切割树状图以创建期望的簇数。在本例中，您已知只有三种小麦品种，因此选择簇数为 k = 3；或者如树状图所示，在 h = 3 处可得到三个簇。您将使用 R 的 cutree() 函数，以 hclust_avg 为一个参数，另一个参数设为 h = 3 或 k = 3。

cut_avg <- cutree(hclust_avg, k = 3)技术支持

如果想在树状图上直观看到簇，可以使用 R 的 abline() 函数绘制切割线，并用 rect.hclust() 在树上为每个簇叠加矩形框，如下所示：

plot(hclust_avg)
rect.hclust(hclust_avg , k = 3, border = 2:6)
abline(h = 3, col = 'red')技术支持

现在您可以看到三个簇分别被三种不同颜色的方框圈出。您还可以使用 dendextend 库中的 color_branches() 函数，以不同颜色的分支来可视化树。

请记住，您可以使用 install.packages('package_name', dependencies = TRUE) 命令在 R 中安装包。

suppressPackageStartupMessages(library(dendextend))
avg_dend_obj <- as.dendrogram(hclust_avg)
avg_col_dend <- color_branches(avg_dend_obj, h = 3)
plot(avg_col_dend)技术支持

现在，您将把获得的聚类结果追加回原始数据框中新列 cluster 中（使用 dplyr 包的 mutate()），并用 count() 统计每个簇中的观测数量。

suppressPackageStartupMessages(library(dplyr))
seeds_df_cl <- mutate(seeds_df, cluster = cut_avg)
count(seeds_df_cl,cluster)技术支持

您将看到每个簇分配了多少条观测。请注意，在带标签的数据中，每种小麦品种原本都有 70 条观测。

基于聚类结果，按簇分析两项特征之间的关系是很常见的做法，可从中获得更有价值的见解。作为练习，您可以借助 ggplot2 包，按簇分析小麦的 perimeter 与 area 之间的关系。

suppressPackageStartupMessages(library(ggplot2))
ggplot(seeds_df_cl, aes(x=area, y = perimeter, color = factor(cluster))) + geom_point()技术支持

注意，对于所有小麦品种，其周长与面积之间似乎呈线性关系。

由于此数据集已有真实标签，您还可以使用 table() 函数交叉检验聚类结果。

table(seeds_df_cl$cluster,seeds_label)技术支持

查看生成的列联表，可以清楚地看到三个包含 55 个或更多元素的组。总体而言，可以认为您的聚类较好地代表了不同类型的种子，因为每种小麦品种最初各有 70 条观测。较大的组表明簇与实际类型之间具有对应关系。

注意：在许多情况下，您并没有真实标签。此时，如前所述，可以采用诸如最大化 Dunn 指数等其他度量。您可以使用 clValid 库中的 dunn() 函数计算 dunn 指数。您也可以像其他机器学习算法一样，将数据划分为训练集与测试集，在拥有真实标签时进行聚类并做交叉验证。

与 K-Means 聚类算法对比

您或许听说过 k-means 聚类算法；如果没有，请查看这篇教程。两种算法在许多方面存在根本差异，且在不同场景下孰优孰劣并不固定。部分差异包括：

• 距离度量：层次聚类几乎可以处理任意距离度量，而 k-means 依赖欧氏距离。
• 结果稳定性：k-means 在初始化时需要随机步骤，重复运行可能得到不同结果；层次聚类通常不存在此问题。
• 簇的数量：在 k-means 中您可以使用肘部图、Silhouette 图等来确定合适的簇数；层次聚类也能使用这些方法，并且还能借助树状图来辅助判断。
• 计算复杂度：k-means 的计算开销小于层次聚类，可在合理时间内运行较大的数据集，这也是 k-means 更为流行的主要原因。

结语

恭喜您读完本教程！您已学会如何预处理数据、层次聚类的基础知识，以及其所用的距离度量与连接方法，并掌握了在 R 中的实现。您还了解了层次聚类与 k-means 的不同之处。做得很好！但总有更多可以探索的内容。建议您进一步学习我们的 Unsupervised Learning in R 课程。