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

and reliable statistically supported technique was proposed
in [64], in which Pakhira and Dutta provided a quick solution for extracting k from the VAT RDI.
Extensions of VAT/iVAT in Big Data
Applications
Big data is a term coined to describe the exponential growth
of structured and unstructured data, which is difficult to
capture, store, manage, and process with conventional datamanagement and -analysis techniques. With the rapid
advances in information sensing, IoT devices, remote sensing, software logs, cameras, microphones, radio-frequency
identification readers, wireless sensor networks (WSNs), and
so on, the world's technological per capita capacity to store
information has roughly doubled every 40 months since the
1980s. In 2001, Laney [65] defined the data growth challenge
as having three dimensions-volume, velocity, and variety,
also called the three Vs of big data. (Many more Vs describing various attributes of big data and the associated processing challenges have been added over the years. In 2017, there
were 42 documented Vs of big data [66]).
The heterogeneity, ubiquity, and dynamic nature of the
resources and devices as well as the wide variety of data
make discovering, accessing, processing, integrating, and
interpreting big data a challenging task [67]. Much VATinspired research has been performed to tackle different
aspects of big data analytics to understand a variety of
novel data sources and extract actionable knowledge from
them. This research can be broadly classified into three
categories, which cater to the high-volume, high-velocity
(streaming data) and high-dimensionality aspects of big
data and are discussed next. In the following sections, we
use N and n to denote the sample size of "big data" and
"small data," respectively.
Clustering High-Volume Data Sets
Assessing Clustering Tendency Visually
Huband et al. [68] were the first to realize the limitations of
VAT to handle even moderately sized data sets (with a few
tens of thousands of data points) due to its O (n 2) computational complexity (n being the number of points in the
data set). To address this problem, they developed an alternative way to compute the most critical information in the
ordered image matrix, that is, the boundary between clusters shown by the dark blocks along the diagonal. They
developed the revised VAT (reVAT) algorithm, which
achieves results similar to VAT with less computation.
The reVAT algorithm builds and displays a set of profile graphs of specific rows of a pseudo-ordered dissimilarity matrix, rather than displaying an entire ordered
image matrix. When presented as an ensemble, the suite
of profile graphs visually suggests distinct clusters when
they are present. In this case, each profile graph will have
a unique peak (i.e., the peaks from one profile to the next
do not overlap). However, interpreting a series of profile
28

IEEE SYSTEMS, MAN, & CYBERNETICS MAGAZINE Apri l 2020

graphs is more difficult than the visual assessment of a
VAT image, especially when the number of clusters in the
data set is large-that is, reVAT does not produce a composite picture of possible substructure in the data. Also,
the computational complexity of reVAT is still O (n 2) due
to the computation of the n # n input-distance matrix.
To solve the interpretation problem of reVAT, a new
algorithm called bigVAT [69] was introduced, which combined the quasi-ordering technique used by reVAT with an
image display of the set of profile graphs displaying the
clustering tendency information with a VAT-like image. bigVAT uses random samples from reVAT-generated quasiordered profile graphs to create a VAT-like image to
simplify the interpretation of cluster structure in big data.
Although reVAT and bigVAT address the visualization
challenge of the VAT RDI for moderately sized data sets,
they still suffer from the high memory requirements of
storing an n # n (unordered) distance matrix. To address
this challenge, Hathaway et al. [13] developed a new scalable, sample-based version of VAT called scalable VAT
(sVAT) and its iVAT extension, scalable iVAT (siVAT) (algorithm S6 in "Pseudocode for Various Algorithms Belonging
to the Visual Assessment of Tendency Family"), which is
feasible for arbitrarily large data sets.
In a nutshell, sVAT/siVAT selects a sample of (approximately) size n from the full set of objects O = " o 1, o 2, f, o N ,
and performs VAT on the distance matrix of the n samples.
The sample is chosen so that it (hopefully) contains a cluster
structure similar to the full set. One of the most important
results in [13] is a (weak) theorem that guarantees that each
cluster in the big data is sampled at least once if it is compact
and well separated in the sense of Dunn's index. This is done
by first picking a set of kl distinguished objects using maximin sampling [70], selected to provide a representation of
each of the clusters. Then, the remainder of the sample is
built by choosing additional data near each of the distinguished objects. This sampling scheme is called maximin
random sampling (MMRS). The VAT/iVAT algorithm is then
applied to the MMRS samples. This yields a sample-based
approximation to the cluster heat map of the big data set that
cannot be made with VAT or iVAT.
To illustrate this, Figure 9(a) is a scatterplot of N =
1,000,000 2D points drawn from a four-component Gaussian, with 250,000 points per cluster. In this case, we cannot
generate a VAT image, indicated by the question mark in
Figure 9(b). However, we can generate sVAT and siVAT
images for this big data set by sampling n = 500 points
(0.05% of the total data set) from O. The sVAT image [Figure 9(c)] weakly suggests four clusters, which are seen with
much better visual acuity in the siVAT image [Figure 9(d)].
Wang et al. [19] proposed a random-sampling-based
extension to their SpecVAT algorithm to enable VCA for
large data sets. Prasad and Reddy [71] proposed a samplebased VAT (PSVAT), which uses several distinguished features (DFs) [72] to select the best random samples in a
progressive sampling scheme. DFs are selected from the

IEEE Systems, Man and Cybernetics Magazine - April 2020

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