用于在R中自动化成对有效分组标签的算法
Mar*_*box 5 algorithm r clique-problem
在努力解决这个问题一段时间后,我希望在这里得到一些建议.我想知道是否有人知道一种基于显着性确定成对分组标签的自动方法.这个问题与重要性测试无关(例如Tukey用于参数化或Mann-Whitney用于非参数) - 给定这些成对比较,一些boxplot类型的数字通常用子脚本表示这些分组:
我手工完成了这个例子,这可能很乏味.我认为算法中的标记顺序应该基于每个组中的级别数 - 例如,那些包含与所有其他级别显着不同的单个级别的组应该首先命名,然后是包含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)
小智 6
很酷的代码.
我认为你需要在调用时引用函数order()do.call:
reord<-do.call("order", data.frame(
do.call(rbind,
lapply(res, function(x) c(sort(x), rep.int(0, ml-length(x))))
)
))
首先让我用图论的语言重述这个问题。定义一个图如下。每个样本都会产生一个代表它的顶点。当且仅当某些测试表明这些顶点所代表的样本无法在统计上区分时，两个顶点之间才存在边缘。在图论中，派系是一组顶点，该组中的每两个顶点之间都有一条边。我们正在寻找一组派系，使得图中的每条边都属于（至少？完全？）其中一个派系。我们希望使用尽可能少的派系。（这个问题称为派边缘覆盖，而不是派覆盖。）然后，我们为每个派分配自己的字母，并用该字母标记其成员。每个样本都可以与其他样本区分开来，并且都有自己的字母。
例如，与示例输入相对应的图表可以这样绘制。
3---1---5 4--6
我提出的算法如下。构建该图并使用Bron--Kerbosch 算法来查找所有最大派系。对于上图，它们是 {1, 3}、{1, 5} 和 {4, 6}。例如，集合 {1} 是一个派系，但它不是最大的，因为它是派系 {1, 3} 的子集。集合 {1, 3, 5} 不是一个派系，因为 3 和 5 之间没有边。在图中
1
/ \
3---5 4--6,
最大派系为 {1, 3, 5} 和 {4, 6}。
现在递归搜索一个小团边缘覆盖。递归函数的输入是一组剩余要覆盖的边和最大团列表。找到剩余集合中的最小边，其中，例如，边 (1,2) < (1,5) < (2,3) < (2,5) < (3,4)。对于包含此边的每个最大团，构造一个由该团和递归调用的输出组成的候选解决方案，其中从剩余的边集中删除团边。输出最佳候选。
除非边缘非常少，否则这可能会太慢。第一个性能改进是记忆：维护递归函数从输入到输出的映射，这样我们就可以避免重复工作。如果这不起作用，那么 R 应该有一个整数规划求解器的接口，我们可以使用整数规划来确定派系的最佳集合。（如果其他方法还不够，我会对此进行更多解释。）