# A Visual Mining Approach to Improved Multiple-Instance Learning
## 4 Visual Multiple-Instance Learning
### Creating a Multiple-Instance Tree (MILTree)  
The improved NJ algorithm [33] begins with a star tree formed by all \(m\) objects on the distance matrix, represented by leaf nodes arranged in a circular configuration and connected by branches to a single central node. Then, it iteratively finds the closest neighboring pair among all possible pairs of nodes by the criterion of minimum evolution, which attempts to minimize the sum of all edge lengths for all nodes of the tree. Afterwards, the closest pair is clustered into a new internal node, and the distances from this node to the remaining ones are computed to be used in subsequent iterations. The algorithm stops when \(m-2\) virtual nodes have been inserted into the tree, i.e., when the star tree is completely resolved into a binary tree. Algorithm 2 illustrates the NJ tree procedure, which starts by computing the depth of the divergence for each node, i.e., the sum of the distances from instance \(i\) to all other nodes:  
\[r_{i}=\sum_{j\
eq i}D_{i,j}. \tag{4}\]  
Then, it computes a new distance matrix based on the divergence \(r_{i}\) in order to find the closest pair of nodes \(i,j\):  
\[c_{i,j}=D_{i,j}-\frac{r_{i}+r_{j}}{-2}, \tag{5}\]  
After finding the pair of nodes \(i,j\), a virtual node \(u\) is created as a parent of both \(i\) and \(j\). The length of the edge connecting \(u\) to \(i\) is:  
\[s_{i,u}=\frac{D_{i,j}}{2}+\frac{r_{i}+r_{j}}{2(m-2)}, \tag{6}\]  
and the length of the edge connecting \(u\) to \(j\) is:  
\[s_{j,u}=D_{i,j}-s_{i,u}. \tag{7}\]  
Finally, the pair of nodes \(i,j\) is replaced by \(u\) in the matrix \(D\), and the distances between \(u\) and all others nodes are computed by Equation (8), where \(k\
eq i\), \(k\
eq j\) and \(k=1..m\):  
\[D_{k,u}=\frac{D_{i,k}+D_{j,k}-D_{i,j}}{2} \tag{8}\]  
The algorithm then iterates, finding and joining pairs of nodes until \(m-2\) virtual nodes are inserted into the tree. ```
Input: Similarity matrix \(D\). Output: Phylogenetic Neighbor-Joining Tree. \(v^{\prime}=m\) ;// Where\(m=D.size\) while\(v^{\prime}>2\)do  Compute \(r_{i}\) for \(i=1..m\), and find \(c_{i,j}\) which is the closest pair of instances \(i,j\) ; // (see Equations (4) and (5)). Create a new virtual node \(u\);  Compute the lengths of edges \((u,i)\) and \((u,j)\) ;// (see Equations (6) and (7)). Replace \(i,j\) by \(u\) and update the distance matrix \(D\) with the new node \(u\) ; // (see Equation (8)). Define \(u\) as parent of both \(i\) and \(j\); \(v^{\prime}=v^{\prime}-1\);  end while
```  
**Algorithm 2**NJ tree Algorithm. ```
Input: Similarity matrix \(D\). Output: Phylogenetic Neighbor-Joining Tree. \(v^{\prime}=m\) ;// Where\(m=D.size\) while\(v^{\prime}>2\)do  Compute \(r_{i}\) for \(i=1..m\), and find \(c_{i,j}\) which is the closest pair of instances \(i,j\) ; // (see Equations (4) and (5)). Create a new virtual node \(u\);  Compute the lengths of edges \((u,i)\) and \((u,j)\) ;// (see Equations (6) and (7)). Replace \(i,j\) by \(u\) and update the



To map multiple-instance data to a visual tree structure, the MILTree was developed as a two-level NJ tree, with bags and instances projected in different levels. We group the instance matrix data by the previously known bags using the instance prototypes as nodes of the second level of the NJ. The layout of the tree projects the data into visual space. A subset of the Corel-1000 dataset is used to illustrate the bag and instance projection levels in Figure 1. In this dataset, each image is a bag, composed of feature vectors (instances) that are extracted from disjoint regions of the image, with an average of 4.5 instances per bag. In the first-level (bag space projection) the red points represent positive bags--100 images of the flower category--and the blue points represent negative bags--100 images selected uniformly from the remaining categories of the dataset. When a bag is selected, its instances are projected in the second level of the multiple-instance tree (instance space projection).