R 中的数据挖掘算法/聚类/CLARA
对大型数据集进行聚类的一个显而易见的方法是尝试扩展现有方法，使其能够处理更多对象。重点在于对大量对象而不是高维空间中的少量对象进行聚类。Kaufman 和 Rousseeuw (1990) 提出了 CLARA (用于大型应用程序的聚类) 算法来处理大型应用程序。CLARA 扩展了他们的 k-medoids 方法，适用于大量对象。它通过对数据集中的样本进行聚类，然后将数据集中的所有对象分配到这些聚类中。
- 将要讨论的技术
这项工作重点介绍 CLARA，这是一种用于对大型数据集进行聚类的方法。
| 符号 | 定义 |
|---|---|
| D | 要聚类的数据集 |
| n | D 中的对象数量 |
| O_i | D 中的对象 i |
| k | 聚类数量 |
| S | D 的样本 |
| s | S 的大小 |
表 1: 符号和定义的摘要
CLARA (Clustering LARge Applications) 依赖于采样方法来处理大型数据集。CLARA 并没有为整个数据集寻找 medoids，而是从数据集中抽取一个小的样本，并应用 PAM 算法为样本生成一个最佳的 medoids 集。结果 medoids 的质量通过整个数据集 D 中每个对象与其聚类 medoid 之间的平均差异来衡量，定义为以下成本函数
其中 M 是选定的 medoids 集，dissimilarity(Oi, Oj) 是对象 Oi 和 Oj 之间的差异，rep(M, Oi) 返回 M 中最接近 Oi 的 medoid。
为了减轻采样偏差，CLARA 重复采样和聚类过程预先定义的次数，然后选择成本最小的 medoids 集作为最终的聚类结果。假设 q 是采样次数。CLARA 算法在图 1 中详细说明。
文件:Algorithm CLARA.png
图 1: CLARA 算法
由于 CLARA 采用了采样方法，因此其聚类结果的质量在很大程度上取决于样本的大小。当样本量较小时，CLARA 在对大型数据集进行聚类方面的效率是以聚类质量为代价的。
为了在 R 中使用 CLARA 算法，必须安装 cluster 包。此包包含一个执行 CLARA 过程的函数。
安装 cluster 包
install.packages("cluster")
导入内容
library("cluster")
cluster 包提供的 CLARA 函数可以按如下方式使用
clara(x, k, metric = "euclidean", stand = FALSE, samples = 5, sampsize = min(n, 40 + 2 * k), trace = 0, medoids.x = TRUE, keep.data = medoids.x, rngR = FALSE)
其中参数为
- x: 数据矩阵或数据框，每行对应一个观测值，每列对应一个变量。所有变量都必须是数值型的。允许出现缺失值 (NA)。
- k: 整数，聚类数量。要求 0 < k < n，其中 n 是观测值数量（即 n = nrow(x)）。
- metric: 字符串，指定用于计算观测值之间差异的度量。目前可用的选项为 "euclidean" 和 "manhattan"。欧几里得距离是差异的平方根和，曼哈顿距离是绝对差异的总和。
- stand: 逻辑值，指示在计算差异之前是否对 x 中的测量值进行标准化。测量值对于每个变量（列）进行标准化，方法是减去变量的平均值并除以变量的平均绝对偏差。
- samples: 整数，从数据集中抽取的样本数量。
- sampsize: 整数，每个样本中的观测值数量。sampsize 应该大于聚类数量 (k)，最多等于观测值数量 (n = nrow(x))。
- trace: 整数，指示算法过程中诊断输出的跟踪级别。
- medoids.x: 逻辑值，指示是否应返回 medoids，与输入数据 x 的某些行相同。如果为 FALSE，则 keep.data 也必须为 false，并且将仍然返回 medoid 索引（即 medoids 的行号，即 i.med 组件），算法通过少复制 x 来节省空间。
- keep.data: 逻辑值，指示是否应将 (如果 stand 为 true 则为缩放的) 数据保存在结果中。将其设置为 FALSE 可以节省内存（从而节省时间），但会禁用 clusplot()ing 结果。使用 medoids.x = FALSE 可以节省更多内存。
- rngR: 逻辑值，指示是否应使用 R 的随机数生成器而不是 clara()-内置的随机数生成器。如果为 true，这也意味着对 clara() 的每次调用都会返回不同的结果 - 尽管在良好的情况下只有细微的差异。
实际上有两种方法可以查看 CLARA 使用的结果。它们都使用函数应用程序返回的 class 为 clara 的对象。
第一种方法是绘制该对象，创建一个表示数据的图表。因此，如果有 N 个对象被分成 K 个聚类，图表必须包含 N 个点来表示这些对象，并且这些点必须用 K 种不同的颜色着色，每种颜色代表一个聚类集。例如，给定对象 clarax，它是函数 clara 应用程序的结果，要绘制该对象，只需
plot(clarax)
查看 CLARA 应用程序结果的第二种方法是简单地打印 class 为 clara 的对象的组件。例如，给定与上一个示例相同的对象 clarax，可以使用以下方法打印其组件
print(clarax)
示例
假设我们有 500 个对象，每个对象有两个属性（或特征）。我们的目标是根据它们的两个特征将这些对象分成 K=2 个组。CLARA 函数可用于定义这些组，如下所示
## generate 500 objects, divided into 2 clusters. x <- rbind(cbind(rnorm(200,0,8), rnorm(200,0,8)), cbind(rnorm(300,50,8), rnorm(300,50,8))) ## run clara clarax <- clara(x, 2) clarax clarax$clusinfo ## print components of clarax print(clarax) ## plot clusters plot(x, col = clarax$cluster) ## plot centers points(clarax$centers, col = 1:2, pch = 8)
打印 clarax 组件的结果
Call: clara(x = x, k = 2)
Medoids:
[,1] [,2]
[1,] 1.091033 -0.5367556
[2,] 51.044099 51.0638017
Objective function: 9.946085
Clustering vector: int [1:500] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
Cluster sizes: 200 300
Best sample:
[1] 6 45 51 56 67 75 85 90 94 97 110 111 160 170 176 181 201 219 249
[20] 260 264 275 296 304 317 319 337 340 361 362 369 370 374 379 397 398 411 420
[39] 422 424 436 448 465 489
Available components:
[1] "sample" "medoids" "i.med" "clustering" "objective"
[6] "clusinfo" "diss" "call" "silinfo" "data"
绘制 "clarax" 的结果
图 2: 绘制 clarax 的结果
在本节中，我们将说明使用 CLARA 的案例研究。
此数据集包含 1973 年美国 50 个州的攻击、谋杀和强奸每 10 万居民的逮捕统计数据。还给出了城市人口的百分比。
具有 50 个观测值和 4 个变量的数据框。
- [,1] 谋杀 数值型 谋杀逮捕（每 10 万人）
- [,2] 攻击 数值型 攻击逮捕（每 10 万人）
- [,3] 城市人口 数值型 城市人口百分比
- [,4] 强奸 数值型 强奸逮捕（每 10 万人）
| 州 | 谋杀 | 攻击 | 城市人口 | 强奸 |
|---|---|---|---|---|
| 阿拉巴马州 | 13.2 | 236 | 58 | 21.2 |
| 阿拉斯加州 | 10.0 | 263 | 48 | 44.5 |
| 亚利桑那州 | 8.1 | 294 | 80 | 31.0 |
| 阿肯色州 | 8.8 | 190 | 50 | 19.5 |
| 加利福尼亚州 | 9.0 | 276 | 91 | 40.6 |
| 科罗拉多州 | 7.9 | 204 | 78 | 38.7 |
| 康涅狄格州 | 3.3 | 110 | 77 | 11.1 |
| 特拉华州 | 5.9 | 238 | 72 | 15.8 |
| 佛罗里达州 | 15.4 | 335 | 80 | 31.9 |
| 佐治亚州 | 17.4 | 211 | 60 | 25.8 |
| 夏威夷州 | 5.3 | 46 | 83 | 20.2 |
| 爱达荷州 | 2.6 | 120 | 54 | 14.2 |
| 伊利诺伊州 | 10.4 | 249 | 83 | 24.0 |
| 印第安纳州 | 7.2 | 113 | 65 | 21.0 |
| 爱荷华州 | 2.2 | 56 | 57 | 11.3 |
| 堪萨斯州 | 6.0 | 115 | 66 | 18.0 |
| 肯塔基州 | 9.7 | 109 | 52 | 16.3 |
| 路易斯安那州 | 15.4 | 249 | 66 | 22.2 |
| 缅因州 | 2.1 | 83 | 51 | 7.8 |
| 马里兰州 | 11.3 | 300 | 67 | 27.8 |
| 马萨诸塞州 | 4.4 | 149 | 85 | 16.3 |
| 密歇根州 | 12.1 | 255 | 74 | 35.1 |
| 明尼苏达州 | 2.7 | 72 | 66 | 14.9 |
| 密西西比州 | 16.1 | 259 | 44 | 17.1 |
| 密苏里州 | 9.0 | 178 | 70 | 28.2 |
| 蒙大拿州 | 6.0 | 109 | 53 | 16.4 |
| 内布拉斯加州 | 4.3 | 102 | 62 | 16.5 |
| 内华达州 | 12.2 | 252 | 81 | 46.0 |
| 新罕布什尔州 | 2.1 | 57 | 56 | 9.5 |
| 新泽西州 | 7.4 | 159 | 89 | 18.8 |
| 新墨西哥州 | 11.4 | 285 | 70 | 32.1 |
| 纽约州 | 11.1 | 254 | 86 | 26.1 |
| 北卡罗来纳州 | 13.0 | 337 | 45 | 16.1 |
| 北达科他州 | 0.8 | 45 | 44 | 7.3 |
| 俄亥俄州 | 7.3 | 120 | 75 | 21.4 |
| 俄克拉荷马州 | 6.6 | 151 | 68 | 20.0 |
| 俄勒冈州 | 4.9 | 159 | 67 | 29.3 |
| 宾夕法尼亚州 | 6.3 | 106 | 72 | 14.9 |
| 罗德岛州 | 3.4 | 174 | 87 | 8.3 |
| 南卡罗来纳州 | 14.4 | 279 | 48 | 22.5 |
| 南达科他州 | 3.8 | 86 | 45 | 12.8 |
| 田纳西州 | 13.2 | 188 | 59 | 26.9 |
| 德克萨斯州 | 12.7 | 201 | 80 | 25.5 |
| 犹他州 | 3.2 | 120 | 80 | 22.9 |
| 佛蒙特州 | 2.2 | 48 | 32 | 11.2 |
| 弗吉尼亚州 | 8.5 | 156 | 63 | 20.7 |
| 华盛顿州 | 4.0 | 145 | 73 | 26.2 |
| 西弗吉尼亚州 | 5.7 | 81 | 39 | 9.3 |
| 威斯康星州 | 2.6 | 53 | 66 | 10.8 |
| 怀俄明州 | 6.8 | 161 | 60 | 15.6 |
表 2: USArrests 数据库
"clara" 函数的使用方式如下
## import data x <- USArrests ## run CLARA clarax <- clara(x[1:4], 3) ## print components of clarax print(clarax) ## plot clusters plot(x, col = clarax$cluster) ## plot centers points(clarax$centers, col = 1:2, pch = 8)
- plot(Assault, Murder)
(USArrests) points(254,11.1, pch=16) text(254,11.11, labels ='纽约') lines(Assault, (.63168 + (.04191 * Assault)))
下面显示了打印函数应用返回的类组件的结果。
Call: clara(x = x[1:4], k = 3)
Medoids:
Murder Assault UrbanPop Rape
Michigan 12.1 255 74 35.1
Missouri 9.0 178 70 28.2
Nebraska 4.3 102 62 16.5
Objective function: 29.31019
Clustering vector: Named int [1:50] 1 1 1 2 1 2 3 1 1 2 3 3 1 3 3 3 3 1 ...
- attr(*, "names")= chr [1:50] "Alabama" "Alaska" "Arizona" "Arkansas" "California" "Colorado" "Connecticut" ...
Cluster sizes: 16 14 20
Best sample:
[1] Alabama Alaska Arizona Arkansas California
[6] Colorado Delaware Florida Georgia Idaho
[11] Illinois Indiana Iowa Kansas Kentucky
[16] Louisiana Maine Maryland Massachusetts Michigan
[21] Minnesota Mississippi Missouri Montana Nebraska
[26] Nevada New Hampshire New York North Carolina North Dakota
[31] Ohio Oklahoma Oregon Pennsylvania Rhode Island
[36] South Carolina South Dakota Tennessee Texas Utah
[41] Vermont Virginia Washington West Virginia Wisconsin
[46] Wyoming
Available components:
[1] "sample" "medoids" "i.med" "clustering" "objective"
[6] "clusinfo" "diss" "call" "silinfo" "data"
下面显示了绘制函数应用返回的类的结果。
图 3：示例结果
CLARA 的实现生成了三个相对同质的集群，分别包含 16 个、14 个和 20 个国家。分析集群均值，我们可以将每个组与三种州类别中的每一种相关联。
- 由阿拉巴马州、阿拉斯加州、亚利桑那州、加利福尼亚州、特拉华州、佛罗里达州、伊利诺伊州、路易斯安那州、马里兰州、密歇根州、密西西比州、内华达州、新墨西哥州、纽约州、北卡罗来纳州、南卡罗来纳州组成的集群的谋杀、袭击和强奸逮捕率最高（每 100,000 人），而且人口最多。
- 由阿肯色州、科罗拉多州、佐治亚州、马萨诸塞州、密苏里州、新泽西州、俄克拉荷马州、俄勒冈州、罗德岛州、田纳西州、德克萨斯州、弗吉尼亚州、华盛顿州、怀俄明州组成的集群的谋杀、袭击和强奸逮捕率中等（每 100,000 人），而且人口最多。
- 由康涅狄格州、夏威夷州、爱达荷州、印第安纳州、爱荷华州、堪萨斯州、肯塔基州、缅因州、明尼苏达州、蒙大拿州、内布拉斯加州、新罕布什尔州、北达科他州、俄亥俄州、宾夕法尼亚州、南达科他州、犹他州、佛蒙特州、西弗吉尼亚州、威斯康星州组成的集群的谋杀、袭击和强奸逮捕率最低（每 100,000 人），而且人口最多。
根据 [3] 分析这两个极端集群（1、3）中的州，可以验证每个国家位于这些组中的原因。加利福尼亚州虽然拥有良好的人类发展指数和个人收入中位数，但其失业率在美国排名第三，密歇根州排名第二，内华达州排名第一，这两个州也位于集群 1 中。康涅狄格州拥有最高的人类发展指数，位于集群 3 中。怀俄明州拥有最高的高中毕业率，位于集群 2 中。其他原因可以通过结合 [3] 对这项工作进行检查来验证。