R 中的数据挖掘算法/聚类/混合层次聚类

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

混合层次聚类是一种聚类技术，它试图结合两种层次技术（凝聚的和分裂的）的最佳特征。

介绍

聚类可以被认为是一个重要的无监督学习问题，它试图在一个未标记的数据集合中找到相似的结构（JAIN，MURTY，FLYNN，1999）^[1]。

这些相似的结构是数据组，更广为人知的是聚类。每个聚类中的数据与其聚类内的元素相似（或接近），并且与属于其他聚类的元素不同（或更远）。聚类技术的目标是确定数据集中的内在分组（JAIN，MURTY，FLYNN，1999）^[1]。

聚类技术

有几种聚类技术，但没有一种可以被认为是绝对最好的方法。每种技术都有自己的优点和缺点，这通常会让用户决定哪种聚类方法最能满足他的需求。

层次聚类

层次聚类函数基本上是将最接近的聚类连接起来，直到达到所需的聚类数量。这种层次聚类被称为凝聚的，因为它迭代地连接聚类。还有一种分裂的层次聚类，它执行相反的过程，每个数据项都在同一个聚类中开始，然后它被分成更小的组（JAIN，MURTY，FLYNN，1999）^[1]。

聚类之间的距离测量可以通过多种方式完成，这就是单链接、平均链接和完全链接的层次聚类算法的不同之处。

在单链接聚类中，也称为最小方法，两个聚类之间的距离被认为是所有数据项对之间的最小距离。在完全链接聚类中，也称为最大方法，两个聚类之间的距离被认为是所有数据项对之间的最大距离。完全链接算法找到的聚类通常比单链接算法找到的聚类更紧凑。然而，单链接算法更通用（JAIN，MURTY，FLYNN，1999）^[1]。

在平均链接聚类中，两个聚类之间的距离等于所有数据的平均距离。此方法的一个变体使用中位数距离，它对数据变化比平均距离更不敏感。

许多层次聚类算法具有一个吸引人的属性，即嵌套的聚类序列可以用一棵树图形地表示，称为“树状图”（CHIPMAN，TIBSHIRANI，2006）^[2]。图 1 显示了一个树状图示例。

图 1：使用单链接凝聚聚类算法获得的树状图。来源：Jain，Murty，Flynn（1999）^[1]。

层次聚类的最大缺点是它的高复杂度顺序 O(n^2 log n)（JAIN，MURTY，FLYNN，1999）^[1]。然而，层次方法具有处理不同密度的聚类的优点，这比其他聚类技术好得多。

混合层次聚类

凝聚算法将数据分组为许多小的聚类和几个大的聚类，这通常使它们擅长识别小的聚类而不是大的聚类。然而，分裂算法具有相反的特征；使它们普遍擅长识别大型聚类（CHIPMAN，TIBSHIRANI，2006）^[2]。

混合层次聚类技术试图结合凝聚和分裂技术的最佳优势（LAAN，POLLARD，2002；CHIPMAN，TIBSHIRANI，2006）^[2]^[3]。这种组合的实现方式取决于所选的算法。

在本节中，将介绍一种混合层次算法，该算法使用“互斥聚类”的概念将分裂技术的程序与从初步凝聚聚类中获得的信息相结合。

互斥聚类

互斥聚类可以定义为一组数据，这些数据相互之间比对任何其他数据更接近，并且与所有其他数据相距甚远。互斥聚类中包含的数据绝不应该分离（CHIPMAN，TIBSHIRANI，2006）^[2]。

基本上，这要求在互斥聚类中，S 中的数据元素之间的最大距离小于 S 中的元素到不在 S 中的任何数据的最小距离

$d(x,y)_{x\in S,y\notin S}>diameter(S)\equiv \max _{w\in S,z\in S}d(w,z)$

其中 S 是数据的子集，d 是两个数据项之间的距离函数，x 是属于 S 的元素，y 是不属于 S 的元素。

互斥聚类有一个有趣的属性，它表明互斥聚类不会被任何单链接、平均链接或完全链接方法的凝聚聚类破坏（CHIPMAN，TIBSHIRANI，2006）^[2]。有关单链接、平均链接或完全链接方法的更多信息，请参阅层次聚类部分的凝聚技术。

此属性对互斥聚类有几个影响。最明显的是支持这样的想法，即互斥聚类包含强大的聚类信息，无论使用哪种链接方法。此属性还有助于解释凝聚方法。此附加信息可以帮助解释互斥聚类，或帮助决定要分割哪些聚类。

此属性的另一个影响是互斥聚类不能被凝聚方法破坏，这表明所有互斥聚类都可以通过检查此方法中的嵌套聚类来识别。

算法

使用互斥聚类的混合层次算法可以分为三个步骤

使用凝聚技术计算互斥聚类。
执行约束的分裂技术，其中每个互斥聚类必须保持完整。这是通过暂时用它们的质心替换一组数据元素的互斥聚类来实现的。
一旦分裂聚类完成，通过在每个互斥聚类“内部”执行另一个分裂聚类来分割每个互斥聚类。

前面描述的互聚类属性及其含义表明，如何在步骤 1 中使用凝聚技术轻松找到互聚类。对于步骤 2，可以使用任何自上而下的方法，它甚至不需要是分裂式层次算法。在步骤 3 中，可以使用凝聚方法。由于互聚类通常很小，因此在步骤 3 中使用自上而下或自下而上的方法将产生类似的结果。在步骤 2 和 3 中同时使用自上而下似乎更简单。

R 中的实现

包： hybridHclust
描述： 通过互聚类进行混合层次聚类
版本 1.0-3
依赖： cluster
发布 2008-04-08
作者： Hugh Chipman、Rob Tibshirani，tsvq 代码最初来自 Trevor Hastie
维护者： Hugh Chipman <[email protected]>
许可证： GPL-2
网址： http://ace.acadiau.ca/math/chipmanh/hybridHclust
存储库： CRAN
在视图中： 聚类、多元

要下载此包，请访问 CRAN Mirrors 页面，然后选择离您所在区域最近的镜像。到达那里后，选择“包”，然后搜索“hybridHclust”。

详情

hybridHclust 包使用互聚类概念来构建一个聚类，其中互聚类永远不会被破坏。这是通过暂时将互聚类中的所有点“融合”在一起，使它们具有相同的坐标来实现的。然后将生成的从上到下的聚类“拼接”在一起，形成一个单独的从上到下的聚类（CHIPMAN，TIBSHIRANI，2006；2008）^[2]^[4]。

“只有最大的互聚类被限制为不能被破坏。因此，如果点 A、B、C、D 是一个互聚类，而点 A、B 也是一个互聚类，那么只有这四个点将被禁止被破坏”（CHIPMAN，TIBSHIRANI，2008）^[4]。

此包使用 x 的行之间的平方欧几里得距离作为距离度量。在某些情况下，理想的距离度量是 d(x1,x2)=1-cor(x1,x2)，如果 x1 和 x2 是矩阵 x 的两行。这种基于相关性的距离在行被缩放为具有均值 0 和标准差 1 后等效于平方欧几里得距离。这可以通过在调用混合聚类算法之前预处理数据矩阵来实现（CHIPMAN，TIBSHIRANI，2008）^[4]。

执行混合聚类的主要方法称为 hybridHclust。

用法
hybridHclust(x, themc=NULL, trace=FALSE)

参数
x - 要聚类的行是数据矩阵
themc - 代表 x 中的互聚类的对象，通常由 mutualCluster 函数生成。如果没有提供，它将被计算。
trace – 指示在执行时是否打印内部步骤。

返回值
hclust 格式的树状图

可视化

hybridHClust 函数返回一个树状图，代表算法的聚类。可以使用“plot”函数查看树状图。

可以使用互聚类函数计算互聚类。该函数有一个“plot”参数，它会在图表上自动绘制互聚类树状图。要打印互聚类，需要使用“print.mutualCluster”函数。

请记住在尝试任何示例代码之前加载 hybridHclust R 包。

示例

# Function to show multiple graphs plotting, in this case 3 graphs in one row 
par(mfrow=c(1,3))
# An Example Data 
x <- cbind(c(-1.4806,1.5772,-0.9567,-0.92,-1.9976,-0.2723,-0.3153),c( -0.6283,-0.1065,0.428,-0.7777,-1.2939,-0.7796,0.012))
# Plot the example data
plot(x, pch = as.character(1:nrow(x)), asp = 1)
# Calculate the mutual clusters
mc1 <- mutualCluster(x, plot=TRUE)
print.mutualCluster(mc1) # print the mutual clusters
dist(x) # distance between data so you can verify that mc's are correct
# Calculate the Hybrid Hierarchical Cluster
hyb1 <- hybridHclust(x)
# Plot the Hybrid Clustering Dendogram
plot(hyb1)

案例研究

为了更好地说明聚类技术，将展示一个简单的案例研究。

当代心理学中的“五大”包含五个重要的性格因素。这五个因素被发现包含并涵盖了所有已知的性格特征，并代表了所有性格特征背后的基本结构。

五大因素及其组成特征可概括如下

开放性 - 对艺术、情感、冒险、非凡的想法、好奇心和各种体验的欣赏。
尽责性 - 表现出自律、尽职尽责和追求成就的倾向；计划性而非自发性行为。
外向性 - 活力、积极情绪、紧迫感，以及在与他人交往中寻求刺激的倾向。
宜人性 - 倾向于对他人表现出同情和合作，而不是怀疑和对抗。
神经质 - 容易体验到令人不快的情绪，例如愤怒、焦虑、抑郁或脆弱。

心理学家衡量某人性格中这些因素最常见的方式是应用带有描述性句子的“测试”。这些特征的测试分数通常以百分位数的形式呈现。

场景/情况/发展

假设五大分数被应用于人口。在这种情况下，测试还附带一个社会经济测试，用于研究目的。这些测试可以根据他们在每个因素和社会经济变量中的百分位数得分进行分组，以便心理学家可以更好地分析结果及其对人口的可能影响。

输入数据

输入数据是六维数值数据，包含五个因素百分位数得分和个人家庭收入。输入数据是使用每个维度上的正态分布随机生成的。随机生成的数据节省了时间，并避免了使用个人可能的特权信息（即使是匿名）的法律问题。

列 O、C、E、A、N 分别代表开放性、尽责性、外向性、宜人性和神经质因素。所有这些列的值都以五大测试的百分位数结果的形式呈现。每个因素的百分位数从最低 5 到最高 95，间隔为 5。

列 I 代表个人家庭收入，该值是家庭赚取的最低工资数。

包含输入数据的 csv 文件可以在这里找到：HybridHClust 案例研究 CSV 输入文件

	O	C	E	A	N	I
1.	10	30	40	55	45	12
2.	50	85	25	30	40	6
3.	95	90	80	50	5	10
4.	20	65	20	15	50	5
5.	50	25	65	10	95	13
6.	40	85	25	10	65	10
7.	55	50	90	90	75	9
8.	35	80	5	40	35	10
9.	30	65	85	35	80	13
10.	20	45	30	50	25	13
11.	40	30	65	10	25	14
12.	50	75	85	50	10	6
13.	65	75	50	5	50	9
14.	90	30	50	35	95	10
15.	60	80	10	75	50	6
16.	25	85	25	50	20	4
17.	10	30	90	50	35	13
18.	75	10	85	55	5	10
19.	65	65	20	50	15	16
20.	60	70	60	60	25	9
21.	35	70	30	40	45	6
22.	55	5	90	70	70	13
23.	15	20	60	40	60	10
24.	20	40	75	70	15	9
25.	30	95	25	65	20	7
26.	90	75	30	20	70	2
27.	95	20	65	80	45	15
28.	45	50	85	70	65	4
29.	60	90	70	25	5	14
30.	70	45	65	50	40	9
31.	50	50	65	65	45	7
32.	50	95	15	35	60	5
33.	70	15	90	80	50	9
34.	85	30	20	30	80	2
35.	70	40	45	85	30	2
36.	75	55	80	85	25	4
37.	20	55	25	35	90	4
38.	85	10	5	55	80	15
39.	5	15	75	35	25	10
40.	75	50	45	60	40	16
41.	65	85	35	90	10	3
42.	25	50	20	15	65	12
43.	15	15	50	75	80	3
44.	30	95	30	45	75	14
45.	80	50	85	20	25	5
46.	35	35	60	25	35	8
47.	90	55	50	15	35	5
48.	35	65	95	35	20	7
49.	30	70	60	25	45	15
50.	30	55	50	30	65	9
51.	35	90	70	20	20	6
52.	60	35	95	10	15	9
53.	25	60	35	90	25	10
54.	10	5	10	45	20	6
55.	80	5	15	75	90	14
56.	20	40	80	35	15	5
57.	80	60	95	65	70	4
58.	65	30	75	30	65	15
59.	15	45	55	50	70	6
60.	20	5	55	55	35	1
61.	40	10	75	70	30	3
62.	20	90	65	80	75	10
63.	95	40	40	20	5	4
64.	45	45	75	25	45	11
65.	80	95	50	45	10	14
66.	60	25	50	70	80	6
67.	85	60	45	95	55	9
68.	95	10	70	60	20	12
69.	65	75	25	50	40	15
70.	10	50	35	10	50	10
71.	50	85	85	40	65	8
72.	45	55	10	10	70	1
73.	5	50	95	55	90	3
74.	35	15	35	15	50	15
75.	95	40	75	50	50	4
76.	50	40	95	65	5	4
77.	40	80	50	95	5	14
78.	55	50	70	50	15	9
79.	90	45	55	30	65	1
80.	20	60	95	95	50	15
81.	85	50	95	95	90	11
82.	5	55	55	25	95	10
83.	15	15	40	20	15	9
84.	80	50	50	50	35	2
85.	65	90	65	50	35	3
86.	75	70	85	20	30	7
87.	65	10	85	10	50	1
88.	75	10	85	15	5	10
89.	50	25	15	20	30	6
90.	15	30	60	10	75	7
91.	30	15	45	25	25	11
92.	75	95	5	95	30	10
93.	55	15	70	30	40	12
94.	10	15	50	30	65	5
95.	5	50	50	60	25	7
96.	75	5	75	65	90	15
97.	80	25	90	90	50	6
98.	60	15	10	75	80	9
99.	95	15	95	95	5	7
100.	55	30	70	85	90	5

执行

# Read the data file
x <- read.csv("hybridHclust_case_study_input.csv")
# calculate the mutual clusters
mc <- mutualCluster(x)
# Calculate the Hybrid Hierarchical Cluster
hyb <- hybridHclust(x, mc)
# Plot the Hybrid Clustering Dendogram
plot(hyb)

输出

聚类函数显示了聚类数据的树状图，通过它可以决定要使用多少个聚类。下图中的红线演示了分析的这种选择，在本例中，将考虑红线以下的聚类。

图 2：上述案例研究数据的混合聚类树状图

分析

由于案例研究具有多维数据，因此很难直观地了解聚类有哪些共同之处。但是，当选择了一个合适的聚类数量时，就可以看到它们的相似性，并更好地分析结果。

看看由 50、59、23、94、43、82、90、5、4、42、70、72 和 37 形成的聚类。该聚类具有中等至高的神经质值 [50、95]，中等至低的开放性值 [5、50]，以及低至中等高的尽责性值 [15、65]。

	O	C	E	A	N	I
4.	20	65	20	15	50	5
5.	50	25	65	10	95	13
23.	15	20	60	40	60	10
37.	20	55	25	35	90	4
42.	25	50	20	15	65	12
43.	15	15	50	75	80	3
50.	30	55	50	30	65	9
59.	15	45	55	50	70	6
70.	10	50	35	10	50	10
72.	45	55	10	10	70	1
82.	5	55	55	25	95	10
90.	15	30	60	10	75	7
94.	10	15	50	30	65	5

另一个有趣的聚类是由 74、89、83、91、54、10、95 和 1 形成的。该聚类具有中等至低的开放性值 [5、50]，中等至低的尽责性值 [5、50]，中等至低的外向性值 [10、50]，以及中等至低的神经质值 [15、50]。

	O	C	E	A	N	I
1.	10	30	40	55	45	12
10.	20	45	30	50	25	13
54.	10	5	10	45	20	6
74.	35	15	35	15	50	15
83.	15	15	40	20	15	9
89.	50	25	15	20	30	6
91.	30	15	45	25	25	11
95.	5	50	50	60	25	7

如果聚类中的值范围是风险行为或病理的指标，那么心理学家就可以更关注该组中的任何人，例如。或者，如果更准确的社会经济变量可以用来查看五大因素与其他社会经济因素之间的相关性。

参考文献

↑ ^a ^b ^c ^d ^e ^f Jain, A. K., Murty, M. N., Flynn, P. J. (1999) “数据聚类：综述”。ACM 计算机调查 (CSUR)，31(3)，第 264-323 页，1999 年。
↑ ^a ^b ^c ^d ^e ^f Chipman, H., Tibshirani, R. (2006) “带有微阵列数据应用的混合层次聚类”。生物统计学提前访问，7(2)，第 286-301 页，2006 年 4 月。
↑ Laan, M.，Pollard, K. (2002) "一种新的混合层次聚类算法及其可视化和自举方法"。统计规划与推断杂志，117 (2)，第 275-303 页，2002 年 12 月。
↑ ^a ^b ^c Chipman, H.，Tibshirani, R. (2008) "hybridHClust 包"，2008 年 4 月。

[jain99-1] ↑ ^a ^b ^c ^d ^e ^f Jain, A. K., Murty, M. N., Flynn, P. J. (1999) “数据聚类：综述”。ACM 计算机调查 (CSUR)，31(3)，第 264-323 页，1999 年。

[chipman06-2] ↑ ^a ^b ^c ^d ^e ^f Chipman, H., Tibshirani, R. (2006) “带有微阵列数据应用的混合层次聚类”。生物统计学提前访问，7(2)，第 286-301 页，2006 年 4 月。

[laan02-3] Laan, M.，Pollard, K. (2002) "一种新的混合层次聚类算法及其可视化和自举方法"。统计规划与推断杂志，117 (2)，第 275-303 页，2002 年 12 月。

[chipman08-4] Chipman, H.，Tibshirani, R. (2008) "hybridHClust 包"，2008 年 4 月。

[1]

[2]

[3]

[4]