R 中的数据挖掘算法/聚类/Proximus
随着用于高保真设计和模拟的大规模计算平台的可用性，以及用于收集科学和商业数据的仪器的可用性，人们越来越重视用于分析大型和极高维数据集的有效技术。这些数据集可能包含离散属性，例如来自商业流程、信息检索和生物信息学的属性，以及来自科学模拟、天体物理测量和工程设计的连续属性。
高维数据的分析通常采用提取数据项之间的相关性、发现数据中的有意义信息、对数据项进行聚类以及找到聚类数据的有效表示、分类和事件关联的形式。由于数据的体积（和维数）通常很大，因此新算法的重点必须是效率和可扩展性，以适应大型数据集。
在本节中，我们将重点介绍 Proximus。预期的应用领域是将高维二进制数据压缩成代表性模式。例如，购买发生率（市场篮子数据）或术语-文档矩阵可以通过 Proximus 进行预处理，以便进行后续的关联规则挖掘。在下一节中，我们将简要说明该算法的工作原理。
Proximus 算法对逻辑矩阵的行进行聚类。算法的压缩率会受到最大聚类半径和最小聚类大小选择的影響。
该算法属于递归划分类型。具体来说，在每一步，使用当前子矩阵（行集）的局部秩一近似来尝试进行二进制划分。这是一种将主成分专门用于二进制数据的方法，它将矩阵表示为两个二进制向量的外部积。当子矩阵是纯的时，节点扩展停止，即列（存在集）向量指示所有行，并且行（主要属性集）模式向量之间的汉明距离或行集的大小小于或等于指定的阈值。如果秩一近似没有导致划分，但半径约束被违反，则使用随机行划分矩阵并使用半径约束。
该图显示了 proximus 的递归结构，其中 A 表示原始数据矩阵。每个矩形内部节点都是秩一近似，而这些节点的两个圆形子节点是根据此近似从父矩阵的划分得到的矩阵。递归树的叶子对应于最终分解。总体分解为 ，其中 和 .
![{\displaystyle X=[x_{1},x_{01},x_{00}]^{T}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/91f13fc69bd10164bc3c260a0728e0b81f327aa7)
![{\displaystyle Y=[y_{1},y_{01},y_{00}]^{T}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7c16038f74d7c1333b3640c36503f19939dff2a)
Proximus 是 cba 包的一部分。在本节中，您将找到有关如何在 R 环境中安装和使用它的更多信息。
在 R 控制台中输入以下命令以安装 cba 包
install.packages("cba")
在 R 控制台中输入以下命令以加载该包
library("cba")
cba 包提供的 Proximus 函数可能按如下方式使用
proximus(x, max.radius = 2, min.size = 1, min.retry = 10, max.iter = 16, debug = FALSE)
其中参数是
x: a logical matrix. max.radius: the maximum number of bits a member in a row set may deviate from its dominant pattern. min.size: the minimum split size of a row set. min.retry: number of retries to split a pure rank-one approximation (translates into a resampling rate). max.iter: the maximum number of iterations for finding a local rank-one approximation. debug: optional debugging output.
具有以下组件的 proximus 类对象
nr: the number of rows of the data matrix. nc: the number of columns of the data matrix. a: a list containing the approximations (patterns). a$x: a vector of row (presence set) indexes. a$y: a vector of column (dominant attribute set) indexes. a$n: the number of ones in the approximated submatrix. a$c: the absolute error reduction by the approximation. max.radius: see arguments. min.size: see arguments. rownames: rownames of the data matrix. colnames: colnames of the data matrix.
有一种方法可以显示此算法的结果。该方法是输入
summary(ProximusObject)
这里我们有一个 proximus 算法处理的示例。该示例非常简单，并提供了一个关于它如何工作的想法。基本上，会生成一个统一的逻辑矩阵。然后，proximus 对原始逻辑矩阵进行秩 4 近似。
x <- rlbmat() pr <- proximus(x, max.radius=8, debug=TRUE) op <- par(mfrow=c(1,2), pty="s") lmplot(x, main="Data") box() lmplot(fitted(pr)$x, main="Approximation") box() par(op)
输出
在本节中，我们将说明一个使用 Proximus 的案例研究。
在本节中，我们将使用 PROXIMUS 对假设数据库中的术语进行聚类，以提取语义信息。这意味着我们想要知道文档的主要主题是什么。
假设有一个包含一些文档的库，我们想要将这些文档分成几类。我们可以将每个文档描述为该文档中出现的单词集。
我们通过将术语映射到行，将列映射到文档，将数据表示为二进制术语-文档矩阵，这样，矩阵中的 TRUE 项就表示该词在相应文档中存在。
下表显示了 14 个术语和 10 个文档。显然，有两个词组：与计算机相关的词和与作者相关的词。词语 love 是孤立的。
R 代码:
x <- matrix(scan("matriz.txt",what=logical(0),n = 14*10), 14, 10, byrow = TRUE)
pr <- proximus(x, max.radius=8, debug = TRUE)
summary(pr)
对术语和文档矩阵进行聚类得到的结果如下所示
如输出所示，表格中显示了聚类结果。很明显，存在三个词语组（每行一个组）。第一组与计算机相关。第二组与作者相关。第三组代表单个词语“love”。名为“size”的列表示属于同一个组的词语数量。Proximus算法将词语聚类如下：组 1（计算机） = {intel, computer, software, linux, windows, Firefox, explorer, programming} 组 2（作者） = {kuth, shakespeare, grisham, asimov, book} 组 3（噪声） = {love}
- Meira Jr., W.; Zaki, M. 数据挖掘算法基础。 [1]
- CBA R 包。 [2]
- Koyuturk; Mehmet 和 Grama; Ananth。PROXIMUS：一个分析超高维离散属性数据集的框架。
第九届 ACM SIGKDD 国际知识发现与数据挖掘大会 (KDD) 论文集，第 147-156 页，2003 年。