IEEE Systems, Man and Cybernetics Magazine - April 2020 - 23

8 5 7 9 3 6 10 1 2 4

Z4

Unit 1
Unit 2
Unit 3
Unit 4
Unit 5

8
5
7
9
3
6
10
1
2
4

Unit 6
Unit 7
Unit 8
Unit 9
Unit 10

(a)

2
1.8
1.6
1.4
1.2
1
0.8
0.6

(b)

6 10 3

9

5 7
(c)

8

1

2

4

Figure 6. The iVAT as a visualization of SL clusters and dendrogram: (a) X 10 + 10 waveforms, (b) the iVAT image

of D E (X 10), and (c) the SL dendrogram of X 10 . (Source: Mahallati et al. [35].)

proposed that the input-distance matrix should be completed using various matrix imputation techniques, such as
sampling from a given distribution, prediction from regressing over the known values (kernel regression, bootstrapped
regression, and so on), and a combination of sampling and
regression, before applying VAT/iVAT.
Parallelized VAT Algorithm
The VAT algorithm, although helpful in determining the
cluster structure in the data visually, has an O(n 2 ) computational complexity and becomes computationally prohibitive for even a moderately sized data set (e.g., a data set
with 20,000 points). In recent years, the graphics processing
unit (GPU) has emerged as an inexpensive, energy-conserving, and highly efficient single-instruction, multiple-threads
parallel-computing device, and it can be found in many
mainstream desktop computers and workstations.
Parveen and Sreevalsan-Nair [29] were the first to propose a parallel implementation of VAT (pVAT). The original
implementation of VAT used Prim's algorithm for constructing the minimum spanning tree (MST) to find the
permutation order of elements in the distance matrix.
However, for the parallel implementation in [29], the
authors used Boruvka's algorithm [30] to find the MST, as
implemented in [31], on a GPU. The pVAT algorithm
obtained the same reordered image as VAT while providing
a speed of up to six orders of magnitude faster. The
pseudocode for pVAT is given in algorithm S4 of "Pseudocode for Various Algorithms Belonging to the Visual
Assessment of Tendency Family."
The massively parallel computing capability of CUDAenabled GPUs was exploited by Meng and Yuan [32] to
develop a GPU-accelerated VAT, which improved the computational efficiency of VAT using a parallel implementation. Along similar lines, edge-based VAT (eVAT), an
edge-based algorithm that can replicate the output of iVAT
[14] but is more efficient and more suitable for parallelism,
was proposed by Meng and Yuan in [33]. They also
	

proposed a parallel scheme to accelerate eVAT using the
NVIDIA GPU and CUDA architecture.
Clustering Algorithms Based on VAT
The VAT algorithm and its modifications help determine
whether there is a cluster structure in the data and, if so,
how many clusters to look for. Based on visual information
contained in the VAT RDI, any clustering algorithm can be
used to find the suggested clusters (say k) in the data.
However, since generating a VAT RDI requires finding the
MST of the data points, a natural choice for the clustering
algorithm is SL hierarchical clustering [5], which simply
requires cutting the k - 1 longest edges of the MST to generate k clusters. A paper by Havens et al. [34] explored the
relationship between the VAT algorithm and SL hierarchical clustering and showed that the VAT reordering of dissimilarity data is directly related to the clusters produced
by the SL hierarchical clustering.
To illustrate the relationship between iVAT and SL clustering, the example shown in Figure 6 is excerpted from
[35]. Figure 6(a) is a set of 10 waveforms, X 10, each represented by a sample vector of p = 48 equally spaced values.
The waveform labeled x 4 is visually anomalous to the
other nine graphs. Figure 6(b) is the iVAT image of X 10
made from the 10 # 10 matrix of Euclidean distances
between pairs of waveform vectors. The integers along the
borders of the iVAT image of X 10 show the identity of each
pixel after iVAT reordering. Waveform x 4 is isolated in a
single 1 # 1 dark block in the lower right corner of Figure 6(b). This illustrates the potential of an iVAT image to
suggest anomalies in the input data.
This iVAT image also depicts the other nine waveforms
as members of a second large cluster. Moreover, the image
suggests a hierarchical substructure within the 9 # 9
block. The intensities in the highlighted (6, 10) pair suggests that these two waveforms are most closely related,
followed by the (5, 7) and then (3, 9) pairs. These internal
pairings are a bit hard to see in Figure 6(b), but if you look
Ap ri l 2020

IEEE SYSTEMS, MAN, & CYBERNETICS MAGAZINE	

23
IEEE Systems, Man and Cybernetics Magazine - April 2020

Table of Contents for the Digital Edition of IEEE Systems, Man and Cybernetics Magazine - April 2020
