在Matlab中构建最大带权生成树
题目:在Matlab中构建最大带权生成树
学过数据结构的都知道“最小生成树” (Minimum Spanning Tree),可以使用Prim和Kruskal算法找到完全图的最小生成树。但在有些时候还需要找最大带权生成树 (Maximum Weighted Spanning Tree),例如在西瓜书(即 周志华. 机器学习. 北京:清华大学出版社, 2016.)中的第7.4节半朴素贝叶斯分类器提到的TAN(Tree Augmented naive Bayes)算法则基于最大带权生成树算法:
提到最大带权生成树时,一般引用[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添加负号运行,则会报错:
这是由于函数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函数,具体没细琢磨,这里就不具体展开了。
上一篇: WebSocket之GatewayWorker使用说明
下一篇: Clojure 1.2 发布了
推荐阅读