有效地计算 R 中的共识成员集
Efficiently calculate a consensus set of members in R
我有一个非常大的（数百万个点）连接图和许多潜在的分割算法来确定组成员资格。是否存在集合中的现有实现或类似的 R 包来计算可能的集合之间的共识集。
一个例子：
假设我有 10 个总分和三个选择组和成员的算法。
> algorithm1<-list(c(1,2,3),c(4,5,6),c(7,8,9,10))
> algorithm2<-list(c(1,2,3),c(4,6),c(5,7,8,9,10))
> algorithm3<-list(c(1,2,3),c(4,6),c(5,7,8),c(9,10))
> algorithm1
[[1]]
[1] 1 2 3
[[2]]
[1] 4 5 6
[[3]]
[1] 7 8 9 10
> algorithm2
[[1]]
[1] 1 2 3
[[2]]
[1] 4 6
[[3]]
[1] 5 7 8 9 10
> algorithm3
[[1]]
[1] 1 2 3
[[2]]
[1] 4 6
[[3]]
[1] 5 7 8
[[4]]
[1] 9 10
三种算法都同意1,2,3之间存在隶属关系，但其余组需要多数规则算法来决定与输入组相比损失最小的最小组数。这感觉像是 permutation/combinatorics 的一个区域，可能已经解决了。这不是我的领域，我需要朝着正确的方向前进。
一个，不完整，我考虑过的是在成员中生成成对的 links，link 强度等于一对点被包含在一个集合中的次数。
> library(reshape2)
>
> pairwise_count<-function(x){
+
+ #For each group, get all pairwise combination of members
+ m<-lapply(x,function(y){
+ as.data.frame(t(combn(y,2)))
+ })
+
+ #Bind groups into a dataframe and give it a count column
+ df<-bind_rows(m)
+ colnames(df)<-c("Point1","Point2")
+ return(df)
+ }
>
> #Example
> pairwise_count(algorithm1)
Point1 Point2
1 1 2
2 1 3
3 2 3
4 4 5
5 4 6
6 5 6
7 7 8
8 7 9
9 7 10
10 8 9
11 8 10
12 9 10
> #Compute for all algorithms
> alldf<-list(algorithm1=pairwise_count(algorithm1),algorithm2=pairwise_count(algorithm2),algorithm3=pairwise_count(algorithm3))
> alldf<-melt(alldf,id.vars=c("Point1","Point2"))
>
> #Get consensus probability that a pair are in the same set.
> library(dplyr)
> alldf %>% group_by(Point1,Point2) %>% summarize(n=n()/3)
# A tibble: 16 x 3
# Groups: Point1 [?]
Point1 Point2 n
<dbl> <dbl> <dbl>
1 1. 2. 1.00
2 1. 3. 1.00
3 2. 3. 1.00
4 4. 5. 0.333
5 4. 6. 1.00
6 5. 6. 0.333
7 5. 7. 0.667
8 5. 8. 0.667
9 5. 9. 0.333
10 5. 10. 0.333
11 7. 8. 1.00
12 7. 9. 0.667
13 7. 10. 0.667
14 8. 9. 0.667
15 8. 10. 0.667
16 9. 10. 1.00
>
> # How to choose final sets?
编辑 #1 下面的代码重现了上面的函数。
library(reshape2)
library(dplyr)
algorithm1<-list(c(1,2,3),c(4,5,6),c(7,8,9,10))
algorithm2<-list(c(1,2,3),c(4,6),c(5,7,8,9,10))
algorithm3<-list(c(1,2,3),c(4,6),c(5,7,8),c(9,10))
pairwise_count<-function(x){
#For each group, get all pairwise combination of members
m<-lapply(x,function(y){
as.data.frame(t(combn(y,2)))
})
#Bind groups into a dataframe and give it a count column
df<-bind_rows(m)
colnames(df)<-c("Point1","Point2")
return(df)
}
#Example
pairwise_count(algorithm1)
#Compute for all algorithms
alldf<-list(algorithm1=pairwise_count(algorithm1),algorithm2=pairwise_count(algorithm2),algorithm3=pairwise_count(algorithm3))
alldf<-melt(alldf,id.vars=c("Point1","Point2"))
#Get consensus probability that a pair are in the same set.
alldf %>% group_by(Point1,Point2) %>% summarize(n=n()/3)
# How to choose final sets?
所以这里有一些东西可能会让你更接近你的目标.. diceR 包实现 "consensus clustering"。以下是它如何对您的样本起作用。这表示“对我的三组聚类进行共识聚类，不要对数据子集重新采样，否则会出现很多 NA，reps 以确定要迭代多少次，然后你还可以选择一种或多种聚类算法（例如hc、pam、diana、km）和一种或多种距离度量（distance=c("euclidean","minkowski")）。
这是一个关于您的数据的非常简短的示例，在最终解决方案中要求 "three or four clusters"，并且仅使用欧氏距离（默认）的层次聚类：
> library(diceR)
> df <- cbind(unlist(algorithm1),unlist(algorithm2),unlist(algorithm3))
> consensus_cluster(df, nk=3:4, p.item=1, reps=10, algorithms=c("hc"))
, , HC_Euclidean, 3
R1 R2 R3 R4 R5 R6 R7 R8 R9 R10
1 1 1 2 2 3 3 2 1 3 1
2 1 1 2 2 3 3 2 1 3 1
3 1 1 2 2 3 3 2 1 3 1
4 1 1 2 2 3 3 2 1 3 1
5 2 2 3 1 2 1 3 3 1 2
6 2 2 3 1 2 1 3 3 1 2
7 3 3 1 3 1 2 1 2 2 3
8 3 3 1 3 1 2 1 2 2 3
9 3 3 1 3 1 2 1 2 2 3
10 3 3 1 3 1 2 1 2 2 3
, , HC_Euclidean, 4
R1 R2 R3 R4 R5 R6 R7 R8 R9 R10
1 1 4 2 2 3 4 3 1 4 1
2 1 1 2 2 3 4 3 1 4 1
3 1 1 4 2 3 3 2 1 3 1
4 1 1 4 2 3 3 2 1 3 1
5 2 2 3 1 2 1 4 3 1 2
6 2 2 3 1 2 1 4 3 1 2
7 3 3 1 4 1 2 1 2 2 3
8 3 3 1 4 1 2 1 2 2 3
9 4 3 1 3 1 2 1 2 2 4
10 4 3 1 3 4 2 1 4 2 4
最后一列显示了最后一次迭代的集群分配。您将不得不尝试使用聚类方法、距离度量和重复次数来找到适合您的方法，但这里有一个小插图可以帮助您做到这一点：https://cran.r-project.org/web/packages/diceR/vignettes/overview.html
这里还有一篇学术论文：https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5769335/
希望对您有所帮助:)
我有一个非常大的（数百万个点）连接图和许多潜在的分割算法来确定组成员资格。是否存在集合中的现有实现或类似的 R 包来计算可能的集合之间的共识集。
一个例子：
假设我有 10 个总分和三个选择组和成员的算法。
> algorithm1<-list(c(1,2,3),c(4,5,6),c(7,8,9,10))
> algorithm2<-list(c(1,2,3),c(4,6),c(5,7,8,9,10))
> algorithm3<-list(c(1,2,3),c(4,6),c(5,7,8),c(9,10))
> algorithm1
[[1]]
[1] 1 2 3
[[2]]
[1] 4 5 6
[[3]]
[1] 7 8 9 10
> algorithm2
[[1]]
[1] 1 2 3
[[2]]
[1] 4 6
[[3]]
[1] 5 7 8 9 10
> algorithm3
[[1]]
[1] 1 2 3
[[2]]
[1] 4 6
[[3]]
[1] 5 7 8
[[4]]
[1] 9 10
三种算法都同意1,2,3之间存在隶属关系，但其余组需要多数规则算法来决定与输入组相比损失最小的最小组数。这感觉像是 permutation/combinatorics 的一个区域，可能已经解决了。这不是我的领域，我需要朝着正确的方向前进。
一个，不完整，我考虑过的是在成员中生成成对的 links，link 强度等于一对点被包含在一个集合中的次数。
> library(reshape2)
>
> pairwise_count<-function(x){
+
+ #For each group, get all pairwise combination of members
+ m<-lapply(x,function(y){
+ as.data.frame(t(combn(y,2)))
+ })
+
+ #Bind groups into a dataframe and give it a count column
+ df<-bind_rows(m)
+ colnames(df)<-c("Point1","Point2")
+ return(df)
+ }
>
> #Example
> pairwise_count(algorithm1)
Point1 Point2
1 1 2
2 1 3
3 2 3
4 4 5
5 4 6
6 5 6
7 7 8
8 7 9
9 7 10
10 8 9
11 8 10
12 9 10
> #Compute for all algorithms
> alldf<-list(algorithm1=pairwise_count(algorithm1),algorithm2=pairwise_count(algorithm2),algorithm3=pairwise_count(algorithm3))
> alldf<-melt(alldf,id.vars=c("Point1","Point2"))
>
> #Get consensus probability that a pair are in the same set.
> library(dplyr)
> alldf %>% group_by(Point1,Point2) %>% summarize(n=n()/3)
# A tibble: 16 x 3
# Groups: Point1 [?]
Point1 Point2 n
<dbl> <dbl> <dbl>
1 1. 2. 1.00
2 1. 3. 1.00
3 2. 3. 1.00
4 4. 5. 0.333
5 4. 6. 1.00
6 5. 6. 0.333
7 5. 7. 0.667
8 5. 8. 0.667
9 5. 9. 0.333
10 5. 10. 0.333
11 7. 8. 1.00
12 7. 9. 0.667
13 7. 10. 0.667
14 8. 9. 0.667
15 8. 10. 0.667
16 9. 10. 1.00
>
> # How to choose final sets?
编辑 #1 下面的代码重现了上面的函数。
library(reshape2)
library(dplyr)
algorithm1<-list(c(1,2,3),c(4,5,6),c(7,8,9,10))
algorithm2<-list(c(1,2,3),c(4,6),c(5,7,8,9,10))
algorithm3<-list(c(1,2,3),c(4,6),c(5,7,8),c(9,10))
pairwise_count<-function(x){
#For each group, get all pairwise combination of members
m<-lapply(x,function(y){
as.data.frame(t(combn(y,2)))
})
#Bind groups into a dataframe and give it a count column
df<-bind_rows(m)
colnames(df)<-c("Point1","Point2")
return(df)
}
#Example
pairwise_count(algorithm1)
#Compute for all algorithms
alldf<-list(algorithm1=pairwise_count(algorithm1),algorithm2=pairwise_count(algorithm2),algorithm3=pairwise_count(algorithm3))
alldf<-melt(alldf,id.vars=c("Point1","Point2"))
#Get consensus probability that a pair are in the same set.
alldf %>% group_by(Point1,Point2) %>% summarize(n=n()/3)
# How to choose final sets?
所以这里有一些东西可能会让你更接近你的目标.. diceR 包实现 "consensus clustering"。以下是它如何对您的样本起作用。这表示“对我的三组聚类进行共识聚类，不要对数据子集重新采样，否则会出现很多 NA，reps 以确定要迭代多少次，然后你还可以选择一种或多种聚类算法（例如hc、pam、diana、km）和一种或多种距离度量（distance=c("euclidean","minkowski")）。
这是一个关于您的数据的非常简短的示例，在最终解决方案中要求 "three or four clusters"，并且仅使用欧氏距离（默认）的层次聚类：
> library(diceR)
> df <- cbind(unlist(algorithm1),unlist(algorithm2),unlist(algorithm3))
> consensus_cluster(df, nk=3:4, p.item=1, reps=10, algorithms=c("hc"))
, , HC_Euclidean, 3
R1 R2 R3 R4 R5 R6 R7 R8 R9 R10
1 1 1 2 2 3 3 2 1 3 1
2 1 1 2 2 3 3 2 1 3 1
3 1 1 2 2 3 3 2 1 3 1
4 1 1 2 2 3 3 2 1 3 1
5 2 2 3 1 2 1 3 3 1 2
6 2 2 3 1 2 1 3 3 1 2
7 3 3 1 3 1 2 1 2 2 3
8 3 3 1 3 1 2 1 2 2 3
9 3 3 1 3 1 2 1 2 2 3
10 3 3 1 3 1 2 1 2 2 3
, , HC_Euclidean, 4
R1 R2 R3 R4 R5 R6 R7 R8 R9 R10
1 1 4 2 2 3 4 3 1 4 1
2 1 1 2 2 3 4 3 1 4 1
3 1 1 4 2 3 3 2 1 3 1
4 1 1 4 2 3 3 2 1 3 1
5 2 2 3 1 2 1 4 3 1 2
6 2 2 3 1 2 1 4 3 1 2
7 3 3 1 4 1 2 1 2 2 3
8 3 3 1 4 1 2 1 2 2 3
9 4 3 1 3 1 2 1 2 2 4
10 4 3 1 3 4 2 1 4 2 4
最后一列显示了最后一次迭代的集群分配。您将不得不尝试使用聚类方法、距离度量和重复次数来找到适合您的方法，但这里有一个小插图可以帮助您做到这一点：https://cran.r-project.org/web/packages/diceR/vignettes/overview.html
这里还有一篇学术论文：https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5769335/
希望对您有所帮助:)