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

Algorithm S24. coVAT2 [95], [96].
Input : D - m # n rectangular dissimilarity matrix
Output: D )), Dt r ,  and Dt c -  Reordered dissimilarity
  matrices
1	Build estimates of D r  and  D c  by interpreting the
 m rows and n columns of D  as the feature vector
representing m row objects and n column objects
respectively
2	Apply VAT to  D r  generating permutation array
  RP = " RP ^1h, P ^2h f, P ^m h,
3	Apply VAT to  D c  generating permutation array
  CP = " CP ^1h, C ^2h f, C ^nh,
4	for p ! 1 to m do
5		 for q ! 1 to n do
6			 D ))p,q = D RP ,CP
7		 end
8	end
9	 Create I ^D )) h
p

q

Visual Assessment of Clustering Tendency
The VAT algorithm, introduced in [11], is a method for visually assessing the clustering tendency in a set of objects
O = " o 1, o 2, f, o n ,, whether they are represented by object
feature vectors or numerical pairwise dissimilarity values.
The input matrix D, generally any dissimilarity matrix,
but usually a pairwise distance matrix built from vector
data inputs, is reordered to obtain D) using a modified
Prim's algorithm. The image I (D) ), when displayed as a
grayscale image, shows possible clusters as dark blocks
along the diagonal. The pseudocode for VAT is given in
algorithm S1 in "Pseudocode for Various Algorithms Belonging to the Visual Assessment of Tendency Family."
Our first example replicates part of [13, Fig. 2]. Figure 1(a) is a scatterplot of three subsets, X 1, X 2, and X 3,
drawn from Gaussian distributions centered at (0, 0), (3, 4),
and (6, 0), with cardinalities of ; X 1 ; = 750, ; X 2 ; = 1,750,
; X 3 ; = 2,500, respectively. All three distributions had the
same covariance matrix:
0.1 0
E.
Ri = ;
0 0.1

Algorithm S25. Scalable coVAT
(scoVAT) [98].
Input : D - m # n rectangular dissimilarity matrix, M and
  N are large
				c l - An overestimate of the true but unknown
  number of clusters c
				 m - Row sample size
				 n - column sample size
Output: D )m # n - scoVAT reordered dissimilarity matrix
1	Build estimates of [D r ]M # M  and  [D c]N # N  by interpreting
 the M rows and N columns of  D  as the feature vector
representing M row objects and N column objects
respectively
2	 Apply siVAT on [D r ]M # M  returning m sampled rows
3	 Apply siVAT on [D c]N # N  returning n sampled rows
4	Build D m # n  by extracting m sampled rows and n sampled
  columns from D M # N
5	 Apply coVAT on D m # n

image in Figure 1(b). However, we will usually use Euclidean
distance, so we suppress the set X and subscript E unless
clarity demands it.
Improvements in the VAT RDI for Complex
Cluster Structure and Noisy Data
Although VAT can often provide a useful estimate of the
number of clusters in a data set that have globular compact
separated clusters, the VAT image can often be inconclusive,
especially if the cluster structure in the data set is complex.
To illustrate this point, Figure 2(a) and (b) shows two data

1

1

0.5

0.5

0

0

-0.5

-0.5

-1
-1 -0.5

Figure 1(b) is the VAT image of the Euclidean distance matrix
D E, whose ijth entry is the Euclidean distance
d E,ij = < x i - x j <. The structure of the data in Figure 1(a) is
represented in Figure 1(b) by the three dark diagonal blocks.
For the three compact, well-separated clusters in X, the
sizes of the three blocks in the VAT image correspond exactly
to the cardinalities of the three subsets, beginning with the
largest block for X 3 at the top, X 2 in the middle, and X 1 at
the bottom. This shows how the VAT image can suggest both
the number and sizes of clusters in the data. In addition, the
VAT image in Figure 1(b) depends on the choice of distance
used to build the input dissimilarity matrix. A change in the
metric might result in a different VAT image for the same data
set, which explains the explicit notation I (D)E (X )) for the
	

0
(a)

(c)

0.5

1

-1
-1 -0.5

0
(b)

0.5

1

(d)

Figure 2. The data scatterplots and VAT images for

the two data sets: (a) a three-line data set, (b) a
three-ring data set, (c) I (D *) for the three-line data
set, and (d) I (D *) for the three-ring data set.

Ap ri l 2020

IEEE SYSTEMS, MAN, & CYBERNETICS MAGAZINE	

19
IEEE Systems, Man and Cybernetics Magazine - April 2020

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