R 中的数据挖掘算法/聚类/RockCluster
聚类是一种将数据点分组的有用技术，使得同一个组/聚类中的点具有相似的特征（或彼此接近），而不同组中的点则不同。
我们描述了 ROCK（使用链接的稳健聚类）聚类算法，它属于凝聚层次聚类算法类别。
下图描述了使用 ROCK 进行聚类的步骤。从数据库中抽取随机样本后，将采用链接的层次聚类算法应用于采样点。最后，仅包含采样点的聚类用于将磁盘上的剩余数据点分配到相应的聚类中。在以下小节中，我们首先详细描述了 ROCK 执行的步骤。
ROCK 的层次聚类算法在下图中给出。它接受要聚类的 N 个采样点集 S（从原始数据集随机抽取）和所需的聚类数量 k 作为输入。该过程从步骤 1 中计算点对之间的链接数开始。最初，每个点都是一个单独的聚类。对于每个聚类 i，我们构建一个局部堆 q[i]，并在算法执行期间维护该堆。q[i] 包含每个聚类 j，使得 link[i,j] 不为零。q[i] 中的聚类 j 按相对于 i 的优度度量的降序排列，即 g(i,j)。
除了每个聚类 i 的局部堆 q[i] 之外，该算法还维护一个额外的全局堆 Q，其中包含所有聚类。此外，Q 中的聚类按其最佳优度度量的降序排列。因此，g(j,max(q[j])) 用于对 Q 中的各种聚类 j 进行排序，其中 q[j] 中的最大元素 max(q[j]) 是与聚类 j 合并的最佳聚类。在每个步骤中，Q 中的最大聚类 j 和 q[j] 中的最大聚类是最佳合并聚类对。
对于每个点，在计算其邻居列表后，该算法考虑其所有邻居对。对于每对邻居，该点贡献一个链接。如果对每个点重复该过程，并对每个邻居对增加链接计数，那么在结束时，所有点对的链接计数将被累加。如果 Mi 是点 i 的邻居列表的大小，那么对于点 i，我们必须在 M^2i 个条目中增加链接计数。因此，该算法的复杂度是 M^2i 的总和，即 O(N * Mm * Ma)，其中 Ma 和 Mm 分别是点的平均邻居数和最大邻居数。在最坏情况下，Mm 的值为 n，在这种情况下，该算法的复杂度变为 O(Ma * N^2)。在实践中，我们期望 Mm 与 Ma 相当接近，因此，对于这些情况，该算法的复杂度平均而言降低到 O(M^2a * n)。
为了在 R 中使用 ROCK 算法，必须安装“CBA”包。该包包含一个执行 RockCluster 过程的函数。
安装 CBA 包
install.packages("cba")
导入方法和算法
library("cba")
用法
rockCluster(x, n, beta = 1-theta, theta = 0.5, fun = "dist", funArgs = list(method="binary"), debug = FALSE) rockLink(x, beta = 0.5)
参数
X: a data matrix; for rockLink an object of class dist. n: the number of desired clusters. beta: optional distance threshold. theta: neighborhood parameter in the range [0,1). fun: distance function to use. funArgs: a list of named parameter argu
如果一切顺利，将返回一个 rockCluster 对象。该对象具有以下组件
x: the data matrix or a subset of it. cl: a factor of cluster labels. size: a vector of cluster sizes. beta: see above. theta: see above. rockLink: returns an object of class dist.
有一种方法可以显示该算法的结果。这种方法是打印 RockCluster 对象
print(RockObject)
例如，我们将使用“蘑菇”数据集与 CBA 包提供的算法一起使用
data("Mushroom")
x <- as.dummy(Mushroom[-1])
rc <- rockCluster(x[sample(dim(x)[1],1000),], n=10, theta=0.8)
print(rc)
rp <- predict(rc, x)
table(Mushroom$class, rp$cl)
输出 - 蘑菇
在本节中，我们说明了 RockCluster 的案例研究
从历史上看，美国大选的特点是两个主要的政党。一个称为**共和党**，它通常反映了美国政治光谱中的保守主义，另一个称为**民主党**，被称为更“自由”或“进步”。
我们的想法是使用 UCI 机器学习库提供的美国国会投票数据库，并执行 RockCluster 技术以将**民主党**与**共和党**分开。**
国会投票数据集是从 UCI 机器学习库中获取的。它是 1984 年的美国国会投票记录。每个记录对应于一位国会议员对 16 个议题的投票（例如，教育支出、犯罪）。所有属性都是布尔型的，具有“是”（即 1）和“否”（0）值，并且很少有属性包含缺失值。每个数据记录都提供了一个共和党或民主党的分类标签。该数据集包含 168 名共和党人和 267 名民主党人的记录。
R 代码:
data(Votes) x <- as.dummy(Votes[-17]) rc <- rockCluster(x, n=2, theta=0.73, debug=TRUE) print(rc) rf <- fitted(rc) table(Votes$Class, rf$cl)
下面展示了函数应用返回的类的组件打印结果。
如表所示，ROCK 和传统算法都识别出两个集群，一个包含大量共和党人，另一个包含大多数民主党人。然而，在传统算法发现的共和党人集群中，大约 25% 的成员是民主党人，而对于 ROCK，只有 12% 是民主党人。聚类质量的提升可归因于 ROCK 使用链接。
- Meira Jr., W.; Zaki, M. 数据挖掘算法基础。[1]
- CBA R 包。[2]
- UCI 机器学习库 [3]
- Sudipto Guha; Rajeev Rastogi; Kyuseok Shim。ROCK：用于分类属性的稳健聚类算法