如何在R中遍历hclust内部节点并实现节点相关查询

1. 数据准备 #

# 构造聚类数据框
df <- structure(c(1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 
0L, 0L, 0L, 0L, 0L, 1L, 1L, 1L, 1L, 0L, 0L, 0L, 0L, 0L, 1L, 1L, 
1L, 1L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 
0L, 1L, 0L, 1L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 
0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 1L, 1L, 1L, 0L, 0L, 0L, 0L, 0L, 
1L, 1L, 1L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 1L, 1L, 0L, 0L, 0L, 
0L, 0L, 0L, 0L, 1L, 1L), dim = c(9L, 11L), dimnames = list(c("1", 
"2", "3", "4", "5", "6", "7", "8", "9"), c("C", "D", "E", "F", 
"G", "H", "K", "L", "M", "N", "P")))

2. 执行层次聚类 #

# 计算曼哈顿距离
dist_matrix <- dist(df, method = "manhattan")
# 完全链接法聚类
clust <- hclust(dist_matrix, method = "complete")
# 绘制树状图
plot(clust)

3. 需求说明 #

• 获取指定节点的左、右子节点
• 获取指定节点包含的所有叶子元素

4. 实现代码 #

4.1 获取指定节点的左右子节点 #

get_child_nodes <- function(hclust_obj, node_id) {
  n <- length(hclust_obj$labels)
  # 内部节点编号从n+1开始，对应merge矩阵的行号为node_id - n
  if (node_id > n) {
    merge_row <- hclust_obj$merge[node_id - n, ]
    left <- merge_row[1]
    right <- merge_row[2]
    # 负数代表原始样本，转为正整数编号；正数代表内部节点，转为实际节点编号
    left <- ifelse(left < 0, abs(left), left + n)
    right <- ifelse(right < 0, abs(right), right + n)
    return(list(left_node = left, right_node = right))
  } else {
    # 叶子节点无下属子节点
    return(list(left_node = NULL, right_node = NULL))
  }
}

4.2 获取指定节点的所有叶子元素 #

get_leaf_nodes <- function(hclust_obj, node_id) {
  n <- length(hclust_obj$labels)
  if (node_id <= n) {
    # 叶子节点直接返回自身标签
    return(hclust_obj$labels[node_id])
  } else {
    # 递归遍历左右子节点，收集所有叶子
    merge_row <- hclust_obj$merge[node_id - n, ]
    left <- merge_row[1]
    right <- merge_row[2]
    left_leaves <- ifelse(left < 0, hclust_obj$labels[abs(left)], get_leaf_nodes(hclust_obj, left + n))
    right_leaves <- ifelse(right < 0, hclust_obj$labels[abs(right)], get_leaf_nodes(hclust_obj, right + n))
    return(c(left_leaves, right_leaves))
  }
}

5. 使用示例 #

# 获取根节点的左右子节点（根节点编号为n + (n-1) = 9+8=17）
get_child_nodes(clust, 17)

# 获取某个内部节点的叶子元素，例如节点12
get_leaf_nodes(clust, 12)

内容的提问来源于stack exchange，提问作者zhang