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

only. To address this problem, Kumar et al. [85] proposed
Fast-clusiVAT, an adaptation of clusiVAT for time-consuming distance measures. Essentially, they proposed modifications for the two most time-consuming steps of clusiVAT:
MMRS sampling and the NPR extension for faster runtime
without significantly compromising accuracy.
Clustering Streaming Data
The growth in network infrastructure, such as the IoT,
closed-circuit television recordings, and online activities,
has enabled a wide range of human activities, physical
objects, and environments to be monitored in fine spatial
and temporal detail. Automatic interpretation of these
evolving data streams is required for the timely detection
of interesting events. Conventional clustering techniques,
which provide a static snapshot of each data point's commitment to every group, may not be sufficient for adapting
to the presence of new clusters or even the merging of
existing data-dense regions for streaming data sets.
To overcome this deficit, Sledge and Keller [82]
explored the use of growing neural gas (GNG) for temporal
clustering and developed a novel clustering scheme called
GNG clustering (GNGC) for streaming data sets, which
helps increase the stability of previously learned clusters
but also promotes plasticity for exploring forming structures. Although GNGC is helpful in online clustering, the
visualization of clustering results is equally important.
When working with low-dimensional data, say, X 1 R 3, it
is easy to display intermittent GNGC results. If the dimensionality of the data set is greater than 3, however, capturing the same spatial information and visualizing the
learned distributions is problematic.
The VAT algorithm was modified in [82] to instead
use the information obtained from GNGC to create VATlike images called neuronal dissimilarity images
(NerDI) by applying the VAT algorithm to the dissimilarity matrix of the neurons in each isolated graph to better understand the evolving cluster structure of the
streaming data. Figure 10 illustrates a few snapshots of
a temporal data set (top row) and corresponding NerDI
images of the GNGC clustering results at those timestamps. As more data are added with time, the corresponding NerDI plots highlight the changing cluster
structure of the data set by the changing structure of
the dark blocks along the diagonal.
Although the approach presented by Sledge and Keller [82]
is useful, it requires the computation of a VAT image every
time a new data point arrives, which, owing to the O (n 2)
time complexity of VAT, can become computationally prohibitive. To solve this problem, Kumar et al. [86] proposed
a novel MST-based incremental update mechanism to
achieve computationally efficient visual assessment. The
new algorithms, incremental VAT (inc-VAT), incremental
iVAT (inc-iVAT), decremental VAT (dec-VAT), and decremental iVAT (dec-iVAT), provide efficient mechanisms to
update the VAT or iVAT RDIs if a new point is added to or
30

IEEE SYSTEMS, MAN, & CYBERNETICS MAGAZINE Apri l 2020

an existing point is removed from the current data set.
The pseudocodes for these algorithms are given in algorithms S8-S20 in "Pseudocode for Various Algorithms
Belonging to the Visual Assessment of Tendency Family."
The time complexities of inc-VAT/dec-VAT and inc-iVAT/
dec-iVAT compares favorably to those of VAT and iVAT
and are useful for applications of anomaly detection and
sliding-window-based online visual assessment of evolving cluster structure in streaming data.
To illustrate the effectiveness of capturing the evolving
cluster structure and the computational efficiency of incVAT/inc-iVAT/dec-VAT/dec-iVAT compared with VAT/iVAT,
an experiment performed on a 2D Gaussian mixture of
five clusters, called X, that has a total of 5,000 data points
is shown in Figures 11 and 12. The numbers of data points
in each of the five clusters are 1,300; 1,000; 400; 1,600; and
700, respectively. The data points in X are arranged
according to the cluster they belong to. Hence, the first
1,300 rows of X are x and y coordinates of the data
points belonging to the first cluster, the next 1,000 rows
represent the data points belonging to the second cluster,
and so on. We start with the first two data points and add
one data point at a time.
The first column in all of the rows of Figure 11 includes
subsets of X consisting of the points belonging to the first
cluster, first two clusters, and so on. Their respective incVAT and inc-iVAT images in the second and third columns
of Figure 11 show that the incrementally built iVAT images
correctly track the changing cluster structure of the points
in the data set. Although the inc-VAT and inc-iVAT images
in Figure 11(k) and (l) seem to show three dark blocks, a
closer look at the images shows two subblocks within the
top-left dark block along the diagonal, owing to the proximity of the two clusters, X 1 - 1,300 and X 2,301 - 2,700, as compared to others. To illustrate the difference in time
complexities of VAT/iVAT and inc-VAT/inc-iVAT, we perform an experiment on the same 2D Gaussian mixture X,
but we randomize the rows of X so that the data points
belonging to the same cluster are not indexed sequentially.
We start with the first two data points and add one data
point at a time. At each step, the VAT, iVAT, inc-VAT, and
inc-iVAT algorithms are executed, and the time taken to
compute the respective reordered dissimilarity matrices is
recorded. Figure 12(a) shows that the time taken to update
the inc-iVAT image is much less than that needed to generate a new iVAT image as n increases. Similarly, to illustrate the time complexity difference between dec-VAT/
dec-iVAT and VAT/iVAT, we perform an experiment on the
same 2D Gaussian mixture X, but this time, we start with
n = 5,000 data points and remove one randomly chosen
data point at a time. Figure 12(b) reveals that the time taken
to generate the iVAT image from the distance matrix (black
curve showing VAT + iVAT) is of the order of o(n 2) and is
much higher than the time taken to update the dec-iVAT
image (green curve showing dec-VAT + dec-iVAT) for large
values of n.

IEEE Systems, Man and Cybernetics Magazine - April 2020

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