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

sets consisting of data points along three parallel lines and
three concentric circles. Most human observers would
agree that the three lines and rings in Figure 2(a) and (b)
constitute three clusters. Their VAT images are shown in
Figure 2(c) and (d), respectively, and neither image gives
any indication about the presence of three clusters in these
two data sets. The problem for VAT images of these two
data sets is that the clusters are not "clouds" of points; rather, they are "stringy." To alleviate this problem, a variety of
improvements have been proposed in the literature. These
fall into two major categories: one uses graph-based distances, and the other involves spectral graph theory. These
two approaches are discussed next.
Wang et al. [14] proposed an improved VAT (iVAT) method to enhance the RDI generated by the VAT algorithm by
transforming the input dissimilarity matrix with a pathbased distance measure. The path-based dissimilarity
measure is based on the idea that, if two objects oi and o j
are very far from each other (reflected by a large distance
value d i j), but there is a path connecting them through a
sequence of other objects, such that the distances between
any two successive objects are small, then d i j should be
adjusted to a smaller value to reflect this connection. This
adjustment reflects the idea that, no matter how far the
distance between two objects may be, they should be considered as coming from one cluster if they are connected
by a set of successive objects forming dense regions
(reflecting the characteristic of elongated clusters).
An efficient formulation of the iVAT algorithm (based
on recursion), which significantly reduces its computational complexity from O(n 3 ) (for the iVAT implementation
presented in [14]) to O(n 2 ) was proposed by Havens and
Bezdek [15]. Their iVAT implementation begins by first
finding the VAT reordered dissimilarity matrix D) and
then transforming the input distances in the distance
matrix D ) = [d )ij] by path-based minimax distances
Dl ) = [dl ij) ], given by
	

dl)ij = min
max D)p[h]p[h + 1], (1)
p ! P 1 # h #; p ;
ij

(a)

(b)

Figure 3. The iVAT images for the two data sets in

Figure 2(a) and (b): (a) I (D l*) for the three-line data
set and (b) I (D l*) for the three-ring data set.
20	

IEEE SYSTEMS, MAN, & CYBERNETICS MAGAZINE Apri l 2020

where P i j is the set of all paths from object i(oi) to object
j (o j) in the VAT-generated MST of O. This formulation is
not only computationally efficient, but it also retains a
direct relationship between the VAT and iVAT images, thus
making it feasible to directly extract single-linkage (SL)
clusters from the iVAT image. This improved version of VAT
now appears in almost all of the literature based on algorithms in the VAT family. The pseudocode for iVAT is given
in algorithm S2 of "Pseudocode for Various Algorithms
Belonging to the Visual Assessment of Tendency Family."
Figure 3 shows the iVAT images of the two data sets
shown in Figure 2(a) and (b). Both iVAT images give a clear
and accurate portrayal of the structure of the input data
and suggest the presence of three clusters by three dark
blocks along the diagonal. Again, the sizes of the three
dark blocks indicate the relative sizes of the three clusters
in the data.
As opposed to iVAT, which first uses the VAT algorithm
on the raw distance matrix and then uses a graph-based
distance to improve the RDI quality, an alternate approach
was employed in [16] and [17] that first transforms the raw
distance matrix before feeding it to the VAT algorithm. Markov random-field VAT (MrfVAT), proposed in [16], modifies
the input-distance matrix using Markov random fields,
which updates each object with its local information
dynamically and maximizes a global probability measure.
Similarly, the approach presented in [17] takes a refined
co-association matrix, which was originally used in ensemble clustering, as an initial similarity matrix and transforms
it by a path-based measure before applying it to VAT. These
methods can deal with data sets that have complex cluster
structures (where VAT is likely to fail) and can reveal the
relationship of clusters hierarchically. The -MrfVAT images of
the two complex data sets shown in Figure 2(a) and (b) are
similar to the iVAT images shown in Figure 3. Since the differences between the iVAT and M
- rfVAT images for the threeline and three-ring data sets are indistinguishable to the
human eye, they are not included in this article.
Another set of algorithms that improve VAT-generated
RDIs are based on spectral graph theory. The spectral VAT
(SpecVAT) algorithm [18] addresses the limitation of VAT in
highlighting the complex cluster structure present in a data
set by first mapping the raw distance matrix D to a graph
embedding space Dl before reordering it by using the VAT
algorithm. SpecVAT first converts D to a weighted affinity
matrix and then performs spectral decomposition of the
normalized Laplacian of the weighted affinity matrix. It
then transforms the original feature vector representation
of data points using the k largest eigenvectors. The VAT
algorithm applied to the transformed representation of the
data points produces RDIs that have much sharper contrast
between dark blocks along the diagonal and the remaining
pixels in the image. The output of the SpecVAT algorithm is
a set of images (corresponding to different values of k)
from which we can visually choose a "best" SpecVAT image
in terms of clarity and block structure.
IEEE Systems, Man and Cybernetics Magazine - April 2020

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