Page 232 - Classification Parameter Estimation & State Estimation An Engg Approach Using MATLAB

FEATURE REDUCTION 221

information. For example, it can project two distinct groups in the data on
top of each other; or it might not show whether data is distributed non-
linearly in the original high dimensional measurement space.
To retain such information, a nonlinear mapping method is needed.
As there are many possible criteria to fit a mapping, there are many
different methods available. Here we will discuss just one: multi-
dimensional scaling (MDS) (Kruskal and Wish, 1977) or Sammon map-
ping (Sammon Jr, 1969). The self-organizing map, discussed in Section
7.2.5, can be considered as another nonlinear projection method.
MDS is based on the idea that the projection should preserve the
distances between objects as well as possible. Given a data set containing
N dimensional measurement vectors (or feature vectors) z i i ¼ 1, ... ,N S ,
we try to find new D dimensional vectors y i ¼ 1, .. . N S according to this
i
criterion. Usually, D N; if the goal is to visualize the data, we choose
D ¼ 2or D ¼ 3. If ij denotes the known distance between objects z i and
z j ,and d ij denotes the distance between projected objects y and y ,then
j
i
distances can be preserved as well as possible by placing the y such that the
i
stress measure
1 X X 2
N S
N S
E S ¼ ij d ij ð7:5Þ
N
N
P S P S
2 i¼1 j¼iþ1
ij
i¼1 j¼iþ1
is minimized. To do so, we take the derivative of (7.5) with respect to
the objects y. It is not hard to derive that, when Euclidean distances are
used, then
N S
qE S 2 X ij d ij
¼ ðy y Þ ð7:6Þ
N
qy i P S P S d ij i j
N
2
jk j¼1
j6¼i
j¼1 k¼jþ1
There is no closed-form solution setting this derivative to zero, but a
gradient descent algorithm can be applied to minimize (7.5). The MDS
algorithm then becomes:
Algorithm 7.1: Multi-dimensional scaling

1. Initialization: Randomly choose an initial configuration of the
(0)
projected objects y . Alternatively, initialize y (0) by projecting the
original data set on its first D principal components. Set t ¼ 0.