# CUDA and OpenMp Implementation of Boolean Matrix Product with Applications in Visual SLAM
## 5 Ultrametric-PAM and Ultrametric-FABMAP
Runs FABMAP with the transformed distance matrices

Input: Euclidean distance matrix A, Training, Testing Dataset

Output: confusion matrix
```
1:procedureUltrametric-FABMAP( Training, Testing Images)
2: Extract 128-d surf features from all collected images
3: Both for training and testing dataset
4: Apply PCA on the training and testing images matrix
5:
6:Centroids \(\leftarrow\)Call Ultrametric-PAM for the feature matrix
7:
8:for\(\mathcal{X}\in\) [Train/Test] do
9:for All images \(\in\)\(\mathcal{X}\)do
10: Vector quantize image descriptors
11: set on the obtained centroid
12: Perform TF-IDF Vector Quantization
13: Obtain BoW representation of of image set \(\mathcal{X}\)
14:endfor
15: Normalize BoW representation, Obtained
16: Start FABMAP procedure using Clustering centroids and BoW representaion
17:endfor
18: Return confusion matrix
19:endprocedure
```

**Algorithm 5** (Ultrametric-FABMAP). Runs FABMAP with the transformed distance matrices

## 6 Experiments

### Metrics

For clusterings \(\mathcal{C}=\{\mathcal{C}_{1},\mathcal{C}_{2},\mathcal{C}_{3},\ldots,\mathcal{ C}_{n}\}\) where \(\mathcal{C}_{i}\) is the \(i\)th cluster:

The Dunn Index is calculated as the ratio of the smallest distance between observations that are not in the same cluster to the greatest intra-cluster distance. Donn index is defined as follows:

\[DonnIndex(\mathcal{C})=\frac{\min\limits_{ \begin{subarray}{c}\mathcal{C}_{i} \in\mathcal{C}_{i}\in\mathcal{C}_{i}\
eq\mathcal{C}_{i}\end{subarray} }(dist(i,j))}{\max\limits_{ \begin{subarray}{c}\mathcal{C}_{n}\in\mathcal{C}\end{subarray} }( C_{m})} \tag{9}\]

A higher Dunn Index will indicate compact, well-separated clusters, while a lower index will indicate less compact or less well-separated clusters. We can now try to calculate the metric for the dataset we've created previously. Another clustering evaluation technique that we have used is compactness which can be defined as:

\[Compactness=\sum\limits_{ \begin{subarray}{c}\mathcal{C}_{i}\in\mathcal{C}\end{subarray} } \frac{1}{|\mathcal{C}_{i}|-\frac{1}{x}\sum\limits_{ \begin{subarray}{c} \mathcal{C}_{i}=\{m_{i}\}\end{subarray} }}d(x,m_{i})\Big{/}|\mathcal{C}| \tag{10}\]

Compactness determines how close the data points within a cluster are, to the cluster's Medoid. Formula adds the distances between data points of a clusters and each cluster'sMedoid, \(m_{i}\). A lower within-cluster variation indicates a good compactness (i.e., good clustering). ### Definition and Examples:

A dissimilarity space (\(\mathcal{X}\),\(\mathcal{F}\)), is a pair where \(\mathcal{X}\), is a set of points and \(\mathcal{F}\):\(\mathcal{X}\times\mathcal{X}\longrightarrow\mathcal{R}\) is a single-valued distance function defined on them with the following three properties:

\[ \begin{cases}\mathcal{F}(x,x)=0\\ \mathcal{F}(x_{1},x_{2})\geqslant 0\ (\text{positiveness})\\ \mathcal{F}(x_{1},x_{2})=\mathcal{F}(x_{2},x_{1})\ (\text{symmetry})\ \text{for all}\ x_{1},x_{2}\in\mathcal{X}.\end{cases}  \tag{11}\]

An ultrametric space is a dissimilarity space with additional conditions \(F(x_{1},x_{2})=0\), if and only if \(x_{1}=x_{2}\), and \(F(x_{1},x_{3})\leq maxF(x_{2},x_{3}),F(x_{1},x_{2})\). This inequality is called the strong triangular or ultrametric inequality. In this case, every triple of points in an ultrametric space forms an isosceles triangle. ### Datasets

We applied Algorithm 1 on data sets Jain, Spiral, Iris, and Seeds. These datasets are available online ([[https://archive.ics.uciedu/ml/index.php](https://archive.ics.uciedu/ml/index.php)]([https://archive.ics.uciedu/ml/index.php](https://archive.ics.uciedu/ml/index.php)), accessed on 20 December 2017). Jain is a dataset including 373 two-dimensional points divided into two clusters. The Spiral dataset contains 300 data points and is made up of three spiral shape clusters in two-dimensional space. The Iris dataset contains three classes of 50 instances each, and each class represents a different type of plant.