# Visual Assessment of Cluster Tendency with Variations of Distance Measures
## 2 Materials and Methods
The correlation distance is defined by:  
\[d(x,y)=1-\frac{(x-\overline{x})\cdot(y-\overline{y})}{\left\|(x-\overline{x}) \right\|_{2}\left(\left\|y-\overline{y}\right\|_{2}\right)}, \tag{10}\]  
where \(\overline{x}\) and \(\overline{y}\) are the means of the elements of \(x\) and \(y\), respectively, and \(\left\|(x-\overline{x})\right\|_{2}\), \(\left\|(y-\overline{y})\right\|_{2}\) means norm, which is, by default, a second-order (Euclidean) norm. The measure of similarity can be estimated through the cosine of the angle between two vectors:  
\[d(x,y)=1-\frac{x\cdot y}{\left\|x\right\|_{2}\left\|y\right\|_{2}}, \tag{11}\]  
where \(\left\|x\right\|_{2}\), \(\left\|y\right\|_{2}\) means norm, which is, by default, a second order (Euclidean) norm. Bray-Curtis dissimilarity [46] is defined by:\[d(x,y)=\sqrt{\sum_{i=1}^{M}(x_{i}-y_{i})^{2}}. \tag{3}\]0  
Canberra distance [42] is given as follows:  
\[d(x,y)=\sqrt{\sum_{i=1}^{M}(x_{i}-y_{i})^{2}}. \tag{3}\]1  
VAT [6; 16] and iVAT algorithms [47] are tools for visual assessment of the tendency to clustering of a set of points by reordering the dissimilarity matrix such that possible clusters appear as dark boxes diagonally in the cluster heat map. This cluster heat map can be used to visually estimate the number of clusters in a dataset [33]. VAT reordering is related with clusters created using single linker hierarchical clustering (SL), which makes it possible to extract SL-aligned groups from images of VAT (iVAT) [48]. The VAT algorithm is presented below (Algorithm 1) [6; 15]. ```
1. Required: A square \(n\times n\) dissimilarity matrix \(D=[d_{ij}]\) satisfying: \(d_{ij}\geq 0\), \(d_{ij}=d_{ji}\forall\,i,d_{ii}=0\,\forall\,i\). 2. Set \(K=\{1,\ldots,\,n\}\), \(I=J=\emptyset\)
3. Select \((i,j)\in arg\max\limits_{k\in K,\,i\in K}d_{kl}\)
4. Set \(P_{i}=i,I=\{i\},J=K-\{i\}\)
5. for \(r=2\) to \(n\)do
6. Select \((i,j)\in arg\min\limits_{k\in I,\,q\in J}d_{kl}\)
7. Set \(P_{t}=j\), Replace \(I=I\bigcup\{j\},J=J-\{j\}\), \(d_{t-1}=d_{ij}\)
8. endfor
9. for \(p=1\) to \(n\)do
10. for \(q=1\) to \(n\)do
11. \(d^{*}_{p,q}=d_{P_{p},P_{q}}\)
12. endfor
13. endfor
14. Generate VAT image of \(D^{*}\): \(I\) (\(D^{*}\))
```  
**Output:** A square \(n\times n\) reordered dissimilarity matrix \(D^{*}=\left[d^{*}_{ij}\right]\), \(I\) (\(A^{*}\)), \(P\) is reordered indices of matrix \(A\). ```
**Algorithm 1** Visual assessment of the clustering tendency (iVAT). In [16], the authors proposed an improved VAT (iVAT). This algorithm transforms the dissimilarity matrix with the idea, which is the following: when two distant objects are connected by a chain of other objects closely located, to reflect this connection, the distance \(d_{ij}\) between them has to be reduced. According to this correction, two objects, if connected by a set of successive objects forming dense regions, should be considered coming from one cluster [15]. The iVAT algorithm is presented in Algorithm 2[15; 16]. ```
1. Required: A square \(n\times n\) reordered dissimilarity matrix \(D^{*}=\left[d^{*}_{ij}\right]\)
2. for \(r=2\) to \(n\)do
3. \(j=arg\min\limits_{1\leq k\leq r-1}d^{*}rk\)
4. \(A^{*}_{rj}=A^{*}_{rj}\)
5. \(c=\{1,\ldots,r-1\}-\{j\}\)
6. \(d^{*}_{rc}=\max\left\{d^{*}_{rj},d^{*}_{rc}\right\}\)
7. endfor
8. \(d^{*}_{rc}=d^{*}_{cr}\) ```
**Algorithm 2** Improved visual assessment of the clustering tendency (iVAT). In this research, we modified the VAT and iVAT algorithms in such a way to be able to calculate many possible distance measures besides the Euclidean (DVAT or DiVAT, see Algorithm 3). ```
1. Required: Set of initial data vectors \(X_{1}\),..., \(X_{n}\), where \(n\) is the number of points. 2. Select distance measure. 3. Calculate dissimilarity matrix \(D=[d_{ij}]\). 4. Run VAT (iVAT) algorithms. ```

**Algorithm 3** DVAT (DiVAT) algorithm. ## 3 Results of Computational Experiment

Computational experiment results of the visual assessment of the clustering tendency based on the VAT and iVAT algorithms with variations of distance measures are presented.