[mlpack] [mlpack/mlpack] EMST non-optimal for d = 2 sets of forests (#823)

[Matt Piekenbrock]

Consider the attached zip archive containing two csv files. I assume you change the path of where the file is downloaded too. The archive contains: 

1. A distance/dissimilarity matrix
2. 100 two-dimensional points from which the dissimilarity matrix was computed from 

I wish to compute the **euclidean minimum spanning tree** of said matrix, built from said points. 

I've attached a reproducible PDF showing several MST implementation results using the traditional MST algorithms from R, printing out the sum of the minimum edge weights for each edge from the resulting MST. 

I also attached a reproducible PDF of the python implementation I'm trying to match, which is actually the only package using the Dual Tree Boruvka approach like MLPACK. 

Finally, if I attempt to do this with MLPACK using the following code, I get a number slightly above the other MST edge weight estimates: 

```
#include <iostream>
using namespace std;

#include <mlpack/core.hpp>
#include <mlpack/methods/emst/dtb.hpp>
using namespace mlpack;
int main()
{
	arma::mat dm;
	data::Load("/Users/mpiekenbrock/Downloads/dissimilarity_matrix.csv", dm, false);

	// Make the dual tree with defaults
	mlpack::emst::DualTreeBoruvka<> dtb(dm);

	// Run the DTB algorithm.
	arma::mat results;
	dtb.ComputeMST(results);

	// Get distances of MST manually, add them up
	double cum_edge_weight = 0;
	for (int i = 0; i < results.n_cols; ++i){
		cum_edge_weight += dm(results(0, i), results(1, i));
	}
	std::cout << cum_edge_weight << std::endl; 
}
```
This outputs 34.1134, slightly above all of the previous MST results of 33.50638. 

[mst_test_case.pdf](https://github.com/mlpack/mlpack/files/623515/mst_test_case.pdf)
[test_data.zip](https://github.com/mlpack/mlpack/files/623342/test_data.zip)
[MST_example.pdf](https://github.com/mlpack/mlpack/files/623522/MST_example.pdf)


-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/mlpack/mlpack/issues/823
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://knife.lugatgt.org/pipermail/mlpack/attachments/20161130/14ec7bc6/attachment.html>