r - 在 R 中自动化成对重要性分组标签的算法

Question

在为这个问题苦苦挣扎了一段时间之后，我希望能在这里得到一些建议。我想知道是否有人知道根据重要性确定成对分组标签的自动化方法。该问题独立于显着性检验(例如，Tukey 用于参数，Mann-Whitney 用于非参数)- 考虑到这些成对比较，一些箱形图类型的图形通常用下标表示这些分组:

我已经手工完成了这个例子，这可能非常乏味。我认为算法中的标记顺序应该基于每个组中的级别数 - 例如那些包含与所有其他级别显着不同的级别的组应该首先命名，然后是包含 2 个级别的组，然后是 3 个级别，等等，同时检查新分组是否添加了新的需要的分组并且不违反和差异。

在下面的示例中，棘手的部分是让算法识别级别 1 应与 3 和 5 分组，但不应将 3 和 5 分组(即共享标签)。

示例代码:

set.seed(1)
n <- 7
n2 <- 100
mu <- cumsum(runif(n, min=-3, max=3))
sigma <- runif(n, min=1, max=3)

dat <- vector(mode="list", n)
for(i in seq(dat)){
    dat[[i]] <- rnorm(n2, mean=mu[i], sd=sigma[i])
}

df <- data.frame(group=as.factor(rep(seq(n), each=n2)), y=unlist(dat))

bp <- boxplot(y ~ group, df, notch=TRUE)
kr <- kruskal.test(y ~ group, df)
kr
mw <- pairwise.wilcox.test(df$y, df$g)
mw
mw$p.value > 0.05 # TRUE means that the levels are not significantly different at the p=0.05 level

#      1     2     3     4     5     6
#2 FALSE    NA    NA    NA    NA    NA
#3  TRUE FALSE    NA    NA    NA    NA
#4 FALSE FALSE FALSE    NA    NA    NA
#5  TRUE FALSE FALSE FALSE    NA    NA
#6 FALSE FALSE FALSE  TRUE FALSE    NA
#7 FALSE FALSE FALSE FALSE FALSE FALSE

text(x=1:n, y=bp$stats[4,], labels=c("AB", "C", "A", "D", "B", "D", "E"), col=1, cex=1.5, pos=3, font=2)

Answer 1

首先让我用图论的语言重述这个问题。定义一个图如下。每个样本都会产生一个代表它的顶点。在两个顶点之间，当且仅当某些测试表明无法在统计上区分这些顶点所代表的样本时，才存在边。在图论中，clique 是一组顶点，在该集合中的每两个顶点之间，都有一条边。我们正在寻找一组派系，使得图中的每条边都属于(至少？确切地？)其中一个派系。我们希望使用尽可能少的派系。 (此问题称为 clique edge cover，而不是 clique cover。)然后我们为每个 clique 分配自己的字母，并用该字母标记其成员。与所有其他样本不同的每个样本也都有自己的字母。

比如你输入的样本对应的图可以这样画。

3---1---5       4--6

我提出的算法如下。构建图形并使用 Bron--Kerbosch algorithm找到所有最大派系。对于上图，它们是 {1, 3}、{1, 5} 和 {4, 6}。例如，集合 {1} 是一个团，但它不是最大的，因为它是团 {1, 3} 的子集。集合 {1, 3, 5} 不是团，因为 3 和 5 之间没有边。在图中

  1
 / \
3---5       4--6,

最大的派系是 {1, 3, 5} 和 {4, 6}。

现在递归地搜索一个小的 clique 边缘覆盖。我们的递归函数的输入是一组剩余要覆盖的边和最大团的列表。在剩余的集合中找到最少的边缘，例如，边缘 (1,2) < (1,5) < (2,3) < (2,5) < (3,4)。对于包含此边的每个最大派系，构造一个候选解决方案，该解由该派系和递归调用的输出组成，其中派系边从剩余的边集中移除。输出最佳候选者。

除非边很少，否则这可能太慢了。第一个性能改进是 memoize:维护递归函数从输入到输出的映射，这样我们就可以避免做两次工作。如果这不起作用，那么 R 应该有一个整数规划求解器的接口(interface)，我们可以使用整数规划来确定最佳的集团集合。 (如果其他方法不够充分，我将对此进行更多解释。)