欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

在Matlab中构建最大带权生成树

程序员文章站 2022-05-21 09:31:19
...

题目:在Matlab中构建最大带权生成树

学过数据结构的都知道“最小生成树” (Minimum Spanning Tree),可以使用Prim和Kruskal算法找到完全图的最小生成树。但在有些时候还需要找最大带权生成树 (Maximum Weighted Spanning Tree),例如在西瓜书(即 周志华. 机器学习. 北京:清华大学出版社, 2016.)中的第7.4节半朴素贝叶斯分类器提到的TAN(Tree Augmented naive Bayes)算法则基于最大带权生成树算法:

在Matlab中构建最大带权生成树

提到最大带权生成树时,一般引用[Chow and Liu, 1968]:

C. Chow and C. Liu. Approximating discrete probability distributions with dependence trees. IEEE Transactions on Information Theory, 14:462–467, 1968.

其实如果知道怎么构建最小生成树,那么只需要把原来的权重添加一个负号,重新构建最小生成树,所得结果就是最大生成树了,根本没必要那么麻烦。

在Matlab中有内置函数graphminspantree(中文解释参考:百度经验),可以构建最小生成树,帮助文件提供了一个例子:

W = [.41 .29 .51 .32 .50 .45 .38 .32 .36 .29 .21];
DG = sparse([1 1 2 2 3 4 4 5 5 6 6],[2 6 3 5 4 1 6 3 4 2 5],W);
UG = tril(DG + DG');%函数graphminspantree权重输入为下三角矩阵
view(biograph(UG,[],'ShowArrows','off','ShowWeights','on'));
[ST,pred] = graphminspantree(UG);
view(biograph(ST,[],'ShowArrows','off','ShowWeights','on'));

参见:https://ww2.mathworks.cn/help/bioinfo/ref/graphminspantree.html

但是,这个例子中如果直接对完全图权重矩阵UG添加负号运行,则会报错:

在Matlab中构建最大带权生成树

这是由于函数graphminspantree默认调用Prim算法,而该算法(好像)不支持负值权重。可以将graphminspantree调用的最小生成树算法改为Kruskal算法:

W = [.41 .29 .51 .32 .50 .45 .38 .32 .36 .29 .21];
DG = sparse([1 1 2 2 3 4 4 5 5 6 6],[2 6 3 5 4 1 6 3 4 2 5],W);
UG = tril(DG + DG');%函数graphminspantree权重输入为下三角矩阵
view(biograph(UG,[],'ShowArrows','off','ShowWeights','on'));
[ST,pred] = graphminspantree(-UG,'Method', 'Kruskal');
view(biograph(ST,[],'ShowArrows','off','ShowWeights','on'));

再次运行程序,则会发现可以正常运行了,而此时得到的结果就是最大带权生成树了。

另外,在高版本Matlab中(R2015b及以上)还有一个minspantree函数,具体没细琢磨,这里就不具体展开了。

相关标签: matlab使用