最小生成树算法-spdep | 最小生成树

“树”（tree）是一种数据结构，它最大的特点就是不含环状结构。假设对节点两两之间的距离赋予一定的权重值，使用连线将节点连成树结构，其中连线的权重值之和最小的树称为“最小生成树”（minimal spanning tree）。

小编在知乎上看到有博主使用图示的方法介绍了最小生成树的两种算法：Kruskal算法和Prim算法算法，链接如下：

在R语言中，可以通过spdep工具包中的函数实现最小生成树算法，此前我们已经用该包中的函数计算了莫兰指数：

mstree()函数

mstree()函数可以寻找最小生成树最小生成树算法，它使用的是Prim算法：

mstree(nbw, ini = NULL)

该函数共有两个参数。nbw为空间权重矩阵，它的生成方法参见本号另外一篇推文以及本文的下文。

ini为树的根节点。树是一种层次结构，上一层次的节点称为下一层次的父节点，下一层次的节点称为上一层次节点的子节点最小生成树算法，一个父节点可对应多个子节点，而除根节点外每个节点都有且仅有一个父节点，根节点没有父节点。

空间权重矩阵

前面提及的推文已经介绍几个与空间权重矩阵相关的函数。

首先，需先生成空间邻接矩阵（只含邻接关系，不含权重）。例如，对于面要素而言：

library(spdep)
bhicv <- st_read(system.file("etc/shapes/bhicv.shp",
                             package="spdep")[1], quiet=TRUE)
nb <- poly2nb(bhicv)
par(mar=c(0,0,0,0))
plot(st_geometry(bhicv))
plot(nb, st_geometry(bhicv), add = T,
     col = "red", lty = 2)

最小生成树算法_百度绿萝算法和石榴算法精髓是什么_carma算法 apriori算法

然后在空间邻接矩阵的基础上，生成空间权重矩阵。权重确定方法有B型、W型等类型，详见推文。

nbw <- nb2listw(nb)

百度绿萝算法和石榴算法精髓是什么_carma算法 apriori算法_最小生成树算法

但是，以上空间权重矩阵的计算仅考虑空间连接性，而没有考虑其他更一般的属性权重特征，这一特征可以由nb2listw()函数的参数glist进行描述，该参数默认值为NULL。

nbcosts()函数可以根据属性数据计算节点之间更一般的连通权重，再向glist参数赋值，它的语法结构如下：

nbcosts(nb, data,
        method = c("euclidean", "maximum", 
                   "manhattan", "canberra",
                   "binary", "minkowski", "mahalanobis"),
        p = 2, cov, inverted = FALSE)

data = data.frame(st_drop_geometry(bhicv[,5:8]))
nb.cost = nbcosts(nb, data)
nbw.2 <- nb2listw(nb, glist = nb.cost)

百度绿萝算法和石榴算法精髓是什么_最小生成树算法_carma算法 apriori算法

示例

由于mstree()函数仅有两个参数，因此得到空间权重矩阵后，再指定一个根节点，即可运行函数。

tree <- mstree(nbw.2, 2)

par(mar=c(0,0,0,0))
plot(st_geometry(bhicv), border = grey(0.5))
plot(tree, coordinates(as(bhicv, "Spatial")),
     add = T, cex.circles = 0.005,
     cex.lab = 0.5, col = "red", lty = 2)