待办事项
本节仍在编写中。但欢迎您添加您的贡献或以任何方式提供帮助

介绍

层次聚类方法包括将数据对象分组到一个簇树中。主要有两种技术类型：自下而上和自上而下方法。第一种方法从由单个对象组成的较小的簇开始，并在每一步中，将当前簇依次合并成更大的簇，直到形成由所有数据对象组成的簇。第二种方法使用相同的逻辑，但方向相反，从包含所有对象的最大的簇开始，并依次将其拆分成更小的簇，直到形成单例组。除了策略之外，另一个重要问题是用于构建（合并或拆分）簇的度量。这些度量可以是不同的距离度量，将在下一节中介绍。

簇间度量

以下是四种广泛使用的用于度量簇间距离的度量。其中 p 和 p' 是两个不同的数据对象点，m_i 是簇 C_i 的均值，n_i 是簇 C_i 中对象的个数，|p - p'| 是 p 和 p' 之间的距离。

最小距离: $d_{min}(C_{i},C_{j})=min_{p\in C_{i},p'\in C_{j}}\mid p-p'\mid$

最大距离: $d_{max}(C_{i},C_{j})=max_{p\in C_{i},p'\in C_{j}}\mid p-p'\mid$

平均距离: $d_{mean}(C_{i},C_{j})=\mid m_{i}-m_{j}\mid$

平均距离: $d_{avg}(C_{i},C_{j})={\frac {1}{n_{i}n_{j}}}\sum _{p\in C_{i}}\sum _{p'\in C_{j}}\mid p-p'\mid$

算法

一种实现自下而上方法的算法是 AGNES (AGglomerative NESting)。AGNES 的主要思想是在第一步中创建由单个数据对象组成的簇，然后使用指定的度量（如上一节提到的那些度量），将这些簇合并成更大的簇。第二步被迭代重复，直到只获得一个簇，该簇包含所有数据对象。实现这种方法的另一个算法示例是 Cure，它在处理所有实体时，将簇缩小到其中心。

DIANA (DIvisive ANAlysis) 是一个实现自上而下方法的算法示例，该算法从包含所有元素的单个大簇开始，并迭代地将当前组拆分成更小的组。与 AGNES 和 Cure 一样，需要定义一些度量来计算簇间距离，以便决定如何（在何处）拆分它们。

实现

为了在 R 中使用层次聚类算法，必须安装 cluster 包。该包包含一个函数，可以根据不同的算法执行 AGNES 过程和 DIANA 过程。

AGNES 函数

cluster 包提供的 AGNES 函数，可以使用如下方法：

agnes(x, diss = inherits(x, "dist"), metric = "euclidean", stand = FALSE, method = "average", par.method, keep.diss = n < 100, keep.data = !diss)

其中参数是

x: 数据矩阵或数据框（所有变量必须为数值型，允许缺失值），或不相似的矩阵（不允许缺失值），具体取决于diss参数的值。
diss: 逻辑标志。如果为 TRUE（对于 dist 或 dissimilarity 对象的默认值），则x被认为是不相似性矩阵。如果为 FALSE，则x被视为观测值与变量的矩阵。
metric: 字符串，指定用于计算观测值之间不相似的度量。当前可用的选项为euclidean和manhattan。欧氏距离是差值的平方根之和，曼哈顿距离是绝对差值的总和。如果x已经是距离矩阵，则此参数将被忽略。
stand: 逻辑标志：如果为 TRUE，则在计算不相似的距离之前，x中的测量值将被标准化。测量值会针对每个变量（列）进行标准化，方法是减去变量的平均值并除以变量的平均绝对偏差。如果x已经是距离矩阵，则此参数将被忽略。
method: 字符串，定义聚类方法。实现的六种方法为average（[未加权配对]组平均方法，UPGMA）、single（单链接）、complete（完全链接）、ward（Ward 方法）、weighted（加权平均链接）及其推广flexible，它使用 Lance-Williams 公式和 par.method 参数的（常数版本）。默认值为average。
par.method: 如果 method = flexible，则为长度为 1、3 或 4 的数值向量。
keep.diss, keep.data: 逻辑值，指示是否应在结果中保留不相似的距离和/或输入数据x。将这些值设置为 FALSE 可以得到更小的结果，从而节省内存分配时间。

AGNES 算法具有以下特点

生成聚类系数，该系数衡量所发现的聚类结构的程度
提供层次树和标语，这是一种新颖的图形显示

AGNES 函数返回一个agnes 对象，代表聚类。此 agnes 对象是一个列表，包含以下组件

order: 向量，提供原始观测值的排列，以便于绘图
order.lab: 与 order 类似的向量，但包含观测值标签，而不是观测值编号。此组件仅在原始观测值被标记的情况下可用。
height: 向量，包含在连续阶段合并聚类之间的距离。
ac: 聚类系数，衡量数据集的聚类结构。
merge: (n-1) x 2 矩阵，其中n是观测值的个数。
diss: dissimilarity 类的对象，表示数据集的总不相似的距离矩阵。
data: 矩阵，包含原始或标准化的测量值。这仅在输入结构与距离矩阵不同时可用。

可视化

可以使用print和plot函数来可视化 AGNES 函数的结果。

第一个函数只打印agnes对象的组件，第二个函数绘制该对象，创建一个代表数据的图表。

以下是用 plot 函数的示例

plot(x, ask = FALSE, which.plots = NULL, main = NULL,sub = paste("Agglomerative Coefficient = ",round(x$ac, digits = 2)),adj = 0, nmax.lab = 35, max.strlen = 5, xax.pretty = TRUE, ...)

使用的参数为

x: agnes 对象
ask: 如果为 TRUE 且 which.plots = NULL，则 plot.agnes 通过菜单进行交互模式操作。
which.plots: 整数向量或 NULL（默认值），后者生成两个图
main, sub: 图的标题和副标题，每个都带有一个方便的默认值。
adj: 用于调整标语图中的标签
nmax.lab: 整数，指示被认为过大而无法在标语图中使用单名称标记的标签数量。
max.strlen: 正整数，指示在标语图标签中字符串被截断的长度。
xax.prety: 正整数，指示在标语图标签中字符串被截断的长度。
...: 图形参数。

以下是用 print 函数的示例

print(x, ...)

参数为

x: agnes 对象
...: 潜在的进一步参数（通用函数 print 需要）

DIANA 函数

cluster 包提供的 DIANA 函数可以用如下方式使用

diana(x, diss = inherits(x, "dist"), metric = "euclidean", stand = FALSE, keep.diss = n < 100, keep.data = !diss)

其中参数是

x: 数据矩阵或数据框（所有变量必须为数值型，允许缺失值），或不相似的矩阵（不允许缺失值），具体取决于diss参数的值。
diss: 逻辑标志。如果为 TRUE（对于 dist 或 dissimilarity 对象的默认值），则x被认为是不相似性矩阵。如果为 FALSE，则x被视为观测值与变量的矩阵。
metric: 字符串，指定用于计算观测值之间不相似的度量。当前可用的选项为euclidean和manhattan。欧氏距离是差值的平方根之和，曼哈顿距离是绝对差值的总和。如果x已经是距离矩阵，则此参数将被忽略。
stand: 逻辑值；如果为 true，则在计算不相似的距离之前，x中的测量值将被标准化。测量值会针对每个变量（列）进行标准化，方法是减去变量的平均值并除以变量的平均绝对偏差。如果 x 已经是距离矩阵，则此参数将被忽略。
keep.diss, keep.data: 逻辑值，指示是否应在

结果中保留不相似的距离和/或输入数据x。将这些值设置为 FALSE 可以得到更小的结果，从而节省内存分配时间。

DIANA 算法在计算分裂层次结构方面可能很独特，而大多数其他用于层次聚类的软件都是聚合的。它与 AGNES 函数具有以下相同的功能

生成聚类系数，该系数衡量所发现的聚类结构的程度
提供层次树和标语，这是一种新颖的图形显示

DIANA 函数返回一个diana 对象，代表聚类。此 agnes 对象是一个列表，包含以下组件

order: 向量，提供原始观测值的排列，以便于绘图
order.lab: 与 order 类似的向量，但包含观测值标签，而不是观测值编号。此组件仅在原始观测值被标记的情况下可用。
heigh: 向量，包含在连续阶段合并聚类之间的距离。
dc: 分裂系数，衡量数据集的聚类结构。
merge: (n-1) x 2 矩阵，其中n是观测值的个数。
diss: dissimilarity 类的对象，表示数据集的总不相似的距离矩阵。
data: 矩阵，包含原始或标准化的测量值。这仅在输入结构与距离矩阵不同时可用。

可视化

可以使用print和plot函数来可视化 DIANA 函数的结果。

第一个函数只打印agnes对象的组件，第二个函数绘制该对象，创建一个代表数据的图表。

以下是用plot函数的示例

plot(x, ask = FALSE, which.plots = NULL, main = NULL, sub = paste("Divisive Coefficient = ", round(x$dc, digits = 2)), adj = 0, nmax.lab = 35, max.strlen = 5, xax.pretty = TRUE, ...)

使用的参数为

x: diana 对象
ask: 如果为 TRUE 且 which.plots = NULL，则 plot.diana 通过菜单进行交互模式操作。
which.plots: 整数向量或 NULL（默认值），后者生成两个图
main, sub: 图的标题和副标题，每个都带有一个方便的默认值。
adj: 用于调整标语图中的标签
nmax.lab: 整数，指示被认为过大而无法在标语图中使用单名称标记的标签数量。
max.strlen: 正整数，指示在标语图标签中字符串被截断的长度。
xax.prety: 正整数，指示在标语图标签中字符串被截断的长度。
...: 图形参数。

以下是用print函数的示例

print(x, ...)

参数为

x: diana 对象
...: 潜在的进一步参数（通用函数 print 需要）

用例

在本节中，将说明在一些意大利城市中使用层次聚类的示例。在以下示例中，将使用平均距离或单链接方法。

场景

给定意大利城市之间的公里距离，目标是将它们聚合到集群中。例如，在 R 中使用agnes函数。

输入数据

输入数据是一个表格，包含意大利城市之间距离的数值。该表格包含六列（和行），代表意大利城市。每个单元格都有一个数值，代表它们之间的公里距离。该表格可以从电子表格或文本文件中加载。

图 1 说明了本示例中使用的城市。

图 1

输入距离矩阵

	BA	FI	MI	VO	RM	TO
BA	0	662	877	255	412	996
FI	662	0	295	468	268	400
MI	877	295	0	754	564	138
VO	255	468	754	0	219	869
RM	412	268	564	219	0	669
TO	996	400	138	869	669	0

执行

agnes 函数可以用如下方式用于定义国家组

# import data
x <- read.table("data.txt")

# run AGNES
ag <- agnes (x, false, metric="euclidean", false, method ="single")
 
# print components of ag
print(ag)

# plot clusters
plot(ag, ask = FALSE, which.plots = NULL)

agnes 的第二个参数的值为 FALSE，因为x被视为观测值与变量的矩阵。第四个参数也为 FALSE，因为不需要对每列进行标准化。

输出

以下是打印函数应用返回的agnes类组件的结果

Call:    agnes(x = x, diss = FALSE, metric = "euclidean", stand = FALSE,      method = "single") 
Agglomerative coefficient:  0.3370960 
Order of objects:
[1] BA VO RM FI MI TO
Height (summary):
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  295.8   486.0   486.5   517.6   642.6   677.0 

Available components:
[1] "order"     "height"    "ac"        "merge"     "diss"      "call"     
[7] "method"    "order.lab" "data"

以下是绘制函数应用返回的类结果

树状图

分析

该算法总是将最近的城市对进行聚类，因此，在这种情况下，“邻里”城市首先被聚类。在单链接聚类中，规则是复合对象到另一个对象的距离等于集群中任何成员到外部对象的最小距离。

然而，凝聚式聚类方法有一些缺点

它们不能很好地扩展：时间复杂度至少为O( $n^{2}$ )，其中n是总对象数；
它们永远无法撤销之前所做的事情。

参考文献

J. Han and M. Kamber. Data Mining: Concepts and Techniuqes. Morgan Kaufmann Publishers, San Francisco, CA, 2006.

Maechler, M. Package 'cluster'. Disponível em <https://cran.r-project.org.cn/web/packages/cluster/cluster.pdf> Acesso em 12 dez 2009.

Meira Jr., W.; Zaki, M. Fundamentals of Data Mining Algorithms. Disponível em <http://www.dcc.ufmg.br/miningalgorithms/DokuWiki/doku.php> Acesso em 12 dez 2009.

A Tutorial on Clustering Algorithms. Disponível em <http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/hierarchical.html>. Acesso em 12 dez 2009.