R:K 均值聚类与社区检测算法(加权相关网络)——我是否把这个问题复杂化了?
R: K Means Clustering vs Community Detection Algorithms (Weighted Correlation Network) - Have I overcomplicated this question?
我有这样的数据:https://imgur.com/a/1hOsFpF
第一个数据集是一个标准格式的数据集,其中包含人员及其财务属性的列表。
第二个数据集包含这些人之间的“关系”——他们彼此付出了多少,彼此欠了多少。
我有兴趣了解更多关于基于网络和图的聚类的知识 - 但我试图更好地了解什么类型的情况需要基于网络的聚类,即我不想在不需要的地方使用图聚类(避免“方钉圆孔”类型情况)。
使用 R,首先我创建了一些假数据:
library(corrr)
library(dplyr)
library(igraph)
library(visNetwork)
library(stats)
# create first data set
Personal_Information <- data.frame(
"name" = c("John", "Jack", "Jason", "Jim", "Julian", "Jack", "Jake", "Joseph"),
"age" = c("41","33","24","66","21","66","29", "50"),
"salary" = c("50000","20000","18000","66000","77000","0","55000","40000"),
"debt" = c("10000","5000","4000","0","20000","5000","0","1000"
)
Personal_Information$age = as.numeric(Personal_Information$age)
Personal_Information$salary = as.numeric(Personal_Information$salary)
Personal_Information$debt = as.numeric(Personal_Information$debt)
create second data set
Relationship_Information <-data.frame(
"name_a" = c("John","John","John","Jack","Jack","Jack","Jason","Jason","Jim","Jim","Jim","Julian","Jake","Joseph","Joseph"),
"name_b" = c("Jack", "Jason", "Joseph", "John", "Julian","Jim","Jim", "Joseph", "Jack", "Julian", "John", "Joseph", "John", "Jim", "John"),
"how_much_they_owe_each_other" = c("10000","20000","60000","10000","40000","8000","0","50000","6000","2000","10000","10000","50000","12000","0"),
"how_much_they_paid_each_other" = c("5000","40000","120000","20000","20000","8000","0","20000","12000","0","0","0","50000","0","0")
)
Relationship_Information$how_much_they_owe_each_other = as.numeric(Relationship_Information$how_much_they_owe_each_other)
Relationship_Information$how_much_they_paid_each_other = as.numeric(Relationship_Information$how_much_they_paid_each_other)
然后,我 运行 一个标准的 K 均值聚类算法(在第一个数据集上)并绘制了结果:
# Method 1 : simple k means analysis with 2 clusters on Personal Information dataset
cl <- kmeans(Personal_Information[,c(2:4)], 2)
plot(Personal_Information, col = cl$cluster)
points(cl$centers, col = 1:2, pch = 8, cex = 2)
这就是我通常处理这个问题的方式。现在,我想看看我是否可以使用图聚类来解决这类问题。
首先,我创建了一个加权相关网络(http://www.sthda.com/english/articles/33-social-network-analysis/136-network-analysis-and-manipulation-using-r/)
首先,我创建了加权相关网络(使用第一个数据集):
res.cor <- Personal_Information[, c(2:4)] %>%
t() %>% correlate() %>%
shave(upper = TRUE) %>%
stretch(na.rm = TRUE) %>%
filter(r >= 0.8)
graph <- graph.data.frame(res.cor, directed=F)
graph <- simplify(graph)
plot(graph)
然后,我运行图聚类算法:
#run graph clustering (also called communiy dectection) on the correlation network
fc <- fastgreedy.community(graph)
V(graph)$community <- fc$membership
nodes <- data.frame(id = V(graph)$name, title = V(graph)$name, group = V(graph)$community)
nodes <- nodes[order(nodes$id, decreasing = F),]
edges <- get.data.frame(graph, what="edges")[1:2]
visNetwork(nodes, edges) %>%
visOptions(highlightNearest = TRUE, nodesIdSelection = TRUE)
这似乎可行 - 但我不确定这是否是解决此问题的最佳方法。
有人可以提供一些建议吗?我是不是把这个问题复杂化了?
谢谢
I am trying to better understand what type of situations require
network based clustering
这完全取决于您的问题领域和您提出的问题。您确实需要针对要尝试回答的数据提出有针对性的问题。话虽如此,您可以应用一组可以同时使用边权重和节点属性的聚类技术:Hierarchical Clustering.
边缘和节点属性在您如何确定驱动聚类的 similarity/dissimilarity 矩阵时发挥作用。请注意,有很多很多这样的实现,花点时间找到一个可以应用于您的数据和问题集的实现。
也许您可能有兴趣阅读“基于融合的社区检测方法”(https://link.springer.com/chapter/10.1007/978-3-030-44584-3_24)。这些基于融合的方法显然是专门为考虑节点属性而设计的。
(首先了解一些背景知识,从您的描述中了解问题的性质)您有 2 个数据集,因此产生 2 个数据结构:Personal_Information
和 Relationship_Information
.您有一组实体,由于在 Personal_Information
中没有名称重复,因此它们看起来是唯一的,因此如果您知道这些实体之间有连接信息,我们可以参考它们作为网络中的节点,它们的互连性可以产生一个网络,其中有社区,社区检测算法可以uncover/allocate/detect。所以,
- Personal_Information,描述每个人(节点)
- Relationship_Information,描述了它们的connectivity/relationship(边)
在您在代码中提供的此信息的示例用法中,您似乎只使用了仅从 Personal_Information[=61= 构建的 graph
数据] res.cor <- Personal_Information[, c(2:4)] %>% ...
而不是 Relationship_Information
。这意味着您正在建立每个人作为网络节点固有的变量之间的关系,而不是他们因相互关联的交互而产生的数据。要明白你在这里做什么,你的方向就像在说; 我将在人们的性格特征之间建立一个网络,并忽略他们之间的关联,即使我有数据。我将看看这些个性特征如何相互关联,然后看看哪些特征值组具有相互跟随的值(分组关联)
所以找到多个人的节点(人)的特征之间的相关性是可以的,然后生成该信息的矩阵也可以,然后从中生成 graph/network 也可以。您通过 fc <- fastgreedy.community(graph)
生成的图表(您称为 graph
)的结果是您获得的是;每个人的哪些变量组是相关的。例如,var1 和 var2 之间有很强的相关性,但是 var2 和 var3 之间有很强的负相关性,所以 var2 和 var3 之间的边缘将推动它们处于 单独的社区 并且还推动 var1 与 var3 在一个单独的社区中,因为它与 var2(密友)密切相关。这些信息有什么用?它可以帮助您了解变量如何作为组存在,这样如果您有一个新人,他的 var2 值很低,而您不知道 var1 或 var3 的值;您会期望 var1 也会很低,而 var3 也会很高。如果你采用了人员数据的协方差,你可以采用特征向量并有效地进行 PCA,从而为你提供具有这种性质信息的向量。
但是,这不会在您的 Relationship_Information
数据中生成有关您 observed/measured 的网络边缘的信息,这些信息描述的是社区数据信息而不是节点数据。这个数据集看起来像一个 邻接列表 ,它是一个数据结构,它列出了前两列作为 col1 中的节点源,col2 中的节点目标和 col3 中的边权重,如果你在 col2 和 col1(交换)中具有相同的节点名称,具有相同的边权重网络具有对称边(无向),否则它是有向的。由于您的数据有 2 个边缘列(col3 和 col4),您可以使用 col1、col2、col3 生成一个网络,使用 col1、col2、col4 生成另一个网络,或者...您可以使用
生成一个网络
- adj_list1 = col1,col2,(col3-col4), 在该电子表格中使用 var 名称 $adj_list1 = name1,name2,(how_much_they_paid_each_other-how_much_they_owe_each_other)$
- 或adj_list1 = col1,col2,(col3/col4) $adj_list1 = name1,name2,(how_much_they_paid_each_other / how_much_they_owe_each_other)$
这取决于您如何使用这些值定义边缘。您想要从 adj1 或 adj2 生成一个网络,然后从该网络应用社区检测。将其视为该数据集中的那些付款,就像社交媒体上的那些交互一样,就像喜欢和提及将人们联系在一起一样。此处的社区结果显示了根据您使用的边在经济上相关的社区的标签,您可以应用 Louvain algorithm
等算法来执行此操作。
但这并没有同时使用节点数据和边缘数据(人员数据和交换数据)。他们在回答不同的问题。
将 K-Means 应用于节点特征数据正在回答与社区检测算法不同的问题。
- K-Means,每个人的这些变量值分布不均,它们集中在 K 个密集区域,中间区域的样本稀疏。所以我们有类型
- 社区检测,忽略这些人的特征,让人们根据他们的互动将人们聚集在一起,看看有多少组,所以如果人们在他们之间交换金钱,他们会专注于一个子组。
所以这些问题是独立使用聚类和社区检测的,因为它们使用独立收集的数据集。电子表格不相互依赖,也不依赖数据。这并不意味着他们的数据没有交叉信息。您可以让这些特征影响边缘。所以在展示它的时候,你有两个独立的调查。
(上面的另一个答案提到了基于融合的方法将节点数据和边缘数据一起分析数据,但这似乎不是您的问题。您是否尝试同时使用这两个数据集?如果是这样,最简单的方法是使用具有良好实现的方法,'graph neural networks' 像 SGC,简单的图卷积神经网络,是一个很好的建议,虽然它听起来很吓人,但你可以为它提供邻接矩阵你创建的支付网络,然后是节点 attributes/features。Python 的 DGL 库非常适合这个。如果你愿意,你可以在无监督的情况下使用缩放数据。)
我有这样的数据:https://imgur.com/a/1hOsFpF
第一个数据集是一个标准格式的数据集,其中包含人员及其财务属性的列表。
第二个数据集包含这些人之间的“关系”——他们彼此付出了多少,彼此欠了多少。
我有兴趣了解更多关于基于网络和图的聚类的知识 - 但我试图更好地了解什么类型的情况需要基于网络的聚类,即我不想在不需要的地方使用图聚类(避免“方钉圆孔”类型情况)。
使用 R,首先我创建了一些假数据:
library(corrr)
library(dplyr)
library(igraph)
library(visNetwork)
library(stats)
# create first data set
Personal_Information <- data.frame(
"name" = c("John", "Jack", "Jason", "Jim", "Julian", "Jack", "Jake", "Joseph"),
"age" = c("41","33","24","66","21","66","29", "50"),
"salary" = c("50000","20000","18000","66000","77000","0","55000","40000"),
"debt" = c("10000","5000","4000","0","20000","5000","0","1000"
)
Personal_Information$age = as.numeric(Personal_Information$age)
Personal_Information$salary = as.numeric(Personal_Information$salary)
Personal_Information$debt = as.numeric(Personal_Information$debt)
create second data set
Relationship_Information <-data.frame(
"name_a" = c("John","John","John","Jack","Jack","Jack","Jason","Jason","Jim","Jim","Jim","Julian","Jake","Joseph","Joseph"),
"name_b" = c("Jack", "Jason", "Joseph", "John", "Julian","Jim","Jim", "Joseph", "Jack", "Julian", "John", "Joseph", "John", "Jim", "John"),
"how_much_they_owe_each_other" = c("10000","20000","60000","10000","40000","8000","0","50000","6000","2000","10000","10000","50000","12000","0"),
"how_much_they_paid_each_other" = c("5000","40000","120000","20000","20000","8000","0","20000","12000","0","0","0","50000","0","0")
)
Relationship_Information$how_much_they_owe_each_other = as.numeric(Relationship_Information$how_much_they_owe_each_other)
Relationship_Information$how_much_they_paid_each_other = as.numeric(Relationship_Information$how_much_they_paid_each_other)
然后,我 运行 一个标准的 K 均值聚类算法(在第一个数据集上)并绘制了结果:
# Method 1 : simple k means analysis with 2 clusters on Personal Information dataset
cl <- kmeans(Personal_Information[,c(2:4)], 2)
plot(Personal_Information, col = cl$cluster)
points(cl$centers, col = 1:2, pch = 8, cex = 2)
这就是我通常处理这个问题的方式。现在,我想看看我是否可以使用图聚类来解决这类问题。
首先,我创建了一个加权相关网络(http://www.sthda.com/english/articles/33-social-network-analysis/136-network-analysis-and-manipulation-using-r/)
首先,我创建了加权相关网络(使用第一个数据集):
res.cor <- Personal_Information[, c(2:4)] %>%
t() %>% correlate() %>%
shave(upper = TRUE) %>%
stretch(na.rm = TRUE) %>%
filter(r >= 0.8)
graph <- graph.data.frame(res.cor, directed=F)
graph <- simplify(graph)
plot(graph)
然后,我运行图聚类算法:
#run graph clustering (also called communiy dectection) on the correlation network
fc <- fastgreedy.community(graph)
V(graph)$community <- fc$membership
nodes <- data.frame(id = V(graph)$name, title = V(graph)$name, group = V(graph)$community)
nodes <- nodes[order(nodes$id, decreasing = F),]
edges <- get.data.frame(graph, what="edges")[1:2]
visNetwork(nodes, edges) %>%
visOptions(highlightNearest = TRUE, nodesIdSelection = TRUE)
这似乎可行 - 但我不确定这是否是解决此问题的最佳方法。
有人可以提供一些建议吗?我是不是把这个问题复杂化了?
谢谢
I am trying to better understand what type of situations require network based clustering
这完全取决于您的问题领域和您提出的问题。您确实需要针对要尝试回答的数据提出有针对性的问题。话虽如此,您可以应用一组可以同时使用边权重和节点属性的聚类技术:Hierarchical Clustering.
边缘和节点属性在您如何确定驱动聚类的 similarity/dissimilarity 矩阵时发挥作用。请注意,有很多很多这样的实现,花点时间找到一个可以应用于您的数据和问题集的实现。
也许您可能有兴趣阅读“基于融合的社区检测方法”(https://link.springer.com/chapter/10.1007/978-3-030-44584-3_24)。这些基于融合的方法显然是专门为考虑节点属性而设计的。
(首先了解一些背景知识,从您的描述中了解问题的性质)您有 2 个数据集,因此产生 2 个数据结构:Personal_Information
和 Relationship_Information
.您有一组实体,由于在 Personal_Information
中没有名称重复,因此它们看起来是唯一的,因此如果您知道这些实体之间有连接信息,我们可以参考它们作为网络中的节点,它们的互连性可以产生一个网络,其中有社区,社区检测算法可以uncover/allocate/detect。所以,
- Personal_Information,描述每个人(节点)
- Relationship_Information,描述了它们的connectivity/relationship(边)
在您在代码中提供的此信息的示例用法中,您似乎只使用了仅从 Personal_Information[=61= 构建的 graph
数据] res.cor <- Personal_Information[, c(2:4)] %>% ...
而不是 Relationship_Information
。这意味着您正在建立每个人作为网络节点固有的变量之间的关系,而不是他们因相互关联的交互而产生的数据。要明白你在这里做什么,你的方向就像在说; 我将在人们的性格特征之间建立一个网络,并忽略他们之间的关联,即使我有数据。我将看看这些个性特征如何相互关联,然后看看哪些特征值组具有相互跟随的值(分组关联)
所以找到多个人的节点(人)的特征之间的相关性是可以的,然后生成该信息的矩阵也可以,然后从中生成 graph/network 也可以。您通过 fc <- fastgreedy.community(graph)
生成的图表(您称为 graph
)的结果是您获得的是;每个人的哪些变量组是相关的。例如,var1 和 var2 之间有很强的相关性,但是 var2 和 var3 之间有很强的负相关性,所以 var2 和 var3 之间的边缘将推动它们处于 单独的社区 并且还推动 var1 与 var3 在一个单独的社区中,因为它与 var2(密友)密切相关。这些信息有什么用?它可以帮助您了解变量如何作为组存在,这样如果您有一个新人,他的 var2 值很低,而您不知道 var1 或 var3 的值;您会期望 var1 也会很低,而 var3 也会很高。如果你采用了人员数据的协方差,你可以采用特征向量并有效地进行 PCA,从而为你提供具有这种性质信息的向量。
但是,这不会在您的 Relationship_Information
数据中生成有关您 observed/measured 的网络边缘的信息,这些信息描述的是社区数据信息而不是节点数据。这个数据集看起来像一个 邻接列表 ,它是一个数据结构,它列出了前两列作为 col1 中的节点源,col2 中的节点目标和 col3 中的边权重,如果你在 col2 和 col1(交换)中具有相同的节点名称,具有相同的边权重网络具有对称边(无向),否则它是有向的。由于您的数据有 2 个边缘列(col3 和 col4),您可以使用 col1、col2、col3 生成一个网络,使用 col1、col2、col4 生成另一个网络,或者...您可以使用
- adj_list1 = col1,col2,(col3-col4), 在该电子表格中使用 var 名称 $adj_list1 = name1,name2,(how_much_they_paid_each_other-how_much_they_owe_each_other)$
- 或adj_list1 = col1,col2,(col3/col4) $adj_list1 = name1,name2,(how_much_they_paid_each_other / how_much_they_owe_each_other)$
这取决于您如何使用这些值定义边缘。您想要从 adj1 或 adj2 生成一个网络,然后从该网络应用社区检测。将其视为该数据集中的那些付款,就像社交媒体上的那些交互一样,就像喜欢和提及将人们联系在一起一样。此处的社区结果显示了根据您使用的边在经济上相关的社区的标签,您可以应用 Louvain algorithm
等算法来执行此操作。
但这并没有同时使用节点数据和边缘数据(人员数据和交换数据)。他们在回答不同的问题。
将 K-Means 应用于节点特征数据正在回答与社区检测算法不同的问题。
- K-Means,每个人的这些变量值分布不均,它们集中在 K 个密集区域,中间区域的样本稀疏。所以我们有类型
- 社区检测,忽略这些人的特征,让人们根据他们的互动将人们聚集在一起,看看有多少组,所以如果人们在他们之间交换金钱,他们会专注于一个子组。
所以这些问题是独立使用聚类和社区检测的,因为它们使用独立收集的数据集。电子表格不相互依赖,也不依赖数据。这并不意味着他们的数据没有交叉信息。您可以让这些特征影响边缘。所以在展示它的时候,你有两个独立的调查。
(上面的另一个答案提到了基于融合的方法将节点数据和边缘数据一起分析数据,但这似乎不是您的问题。您是否尝试同时使用这两个数据集?如果是这样,最简单的方法是使用具有良好实现的方法,'graph neural networks' 像 SGC,简单的图卷积神经网络,是一个很好的建议,虽然它听起来很吓人,但你可以为它提供邻接矩阵你创建的支付网络,然后是节点 attributes/features。Python 的 DGL 库非常适合这个。如果你愿意,你可以在无监督的情况下使用缩放数据。)