Graphics Reference
In-Depth Information
points, their dimensionality or the way the distances between them were computed.
Multidimensional scaling
(MDS) is the method for situating these points in a low
space such that a classical distance measure (like Euclidean) between them is as close
as possible to each
d
ij
. There must be a projection from some unknown dimensional
space to another space whose number of dimensions is known.
One of the most typical examples of MDS is to draw an approximation of the map
that represents the travel distances between cities, knowing only the distance matrix.
Obviously, the outcome is distorted due to the differences between the distances
measured taking into account the geographical obstacles and the actual distance
in a straight line between the cities. It common for the map to be stretched out
to accommodate longer distances and that the map also is centered on the origin.
However, the solution is not unique, we can get any rotating view of it.
MDS is within the DR techniques because we can compute the distances in a
d
-dimensional space of the actual data points and then to give as input this distance
matrix to MDS, which then projects it in to a lower-dimensional space so as to
preserve these distances.
Formally, let us say we have a sample
X
x
t
N
t
1
as usual, where
x
t
d
.For
={
}
∈ R
=
the two points
r
and
s
, the squared Euclidean distance between them is
d
d
d
d
d
rs
=||
x
r
x
s
2
x
j
−
x
j
)
2
x
j
)
2
x
j
x
j
+
x
j
)
2
−
||
=
1
(
=
1
(
−
2
1
(
j
=
j
=
j
=
1
j
=
=
b
rr
+
b
ss
−
2
b
rd
where
b
rs
is defined as
d
x
j
x
j
b
rs
=
j
=
1
To constrain the solution, we center the data at the origin and assume
N
x
j
=
0
,
∀
j
=
1
,...,
d
t
=
1
Then, summing up the previous equation on
r
,
s
, and defining
n
x
j
)
2
T
=
b
tt
=
(
t
t
=
1
j
we get
d
rs
=
T
+
Nb
ss
r
