slides

Past, Present, and Future of MDS. – 3 – dissimilarity matrix Δ. O1. O2. O3. L. On-1 On. O1. 0. O2 δ12. 0. O3 δ13 ... network analysis. – biology,. – economists, etc.
3MB Sizes 2 Downloads 323 Views
Past, Present, and Future of Multidimensional Scaling Patrick J. F. Groenen *Econometric Institute, Erasmus University Rotterdam, The Netherlands, [email protected], http://people.few.eur.nl/groenen/

Summary: 1 2 3 4 5

What is MDS? Some Historical Milestones Present Future Summary of highlights in MDS

1 What is MDS? • Table of travel times by train between 10 French cities:

Bordeaux Brest Lille Lyon Marseille Nice Parijs Strassbourg Toulouse Tours

Bordeaux Brest 0 9h58 0 6h39 7h11 8h05 7h11 5h47 8h49 8h30 13h36 2h59 4h17 8h08 10h16 2h02 13h52 2h36 5h38

Lille

0 4h52 6h12 8h20 1h04 6h54 9h42 4h17

Lyon

0 1h35 4h33 2h01 4h36 4h25 4h21

Marseille

Nice

0 2h26 3h00 7h04 3h26 5h13

Parijs

0 5h52 11h15 6h29 9h04

Strassb ourg

0 4h01 5h14 1h13

Toulouse

0 10h56 6h03

Tours

0 6h06

0

Lille

Brest

Paris

Strassbourg

Brest Strassbourg Tours

Tours

Lille Paris Lyon

Lyon

Bordeaux Marseille

Bordeaux Toulouse

Toulouse Nice Marseille

Geographic map of France.

Nice

MDS map of travel time by train. Past, Present, and Future of MDS

–2–

dissimilarity matrix ∆ O1

O2

O3

O1

0

O2 O3 M

δ12 δ13

0

M

M

On-1 On

δ1,n-1 δ2,n-1 δ3,n-1 δ1n δ2n δ3n

δ23

0 M

L

On-1

O L L

0

δ2n

On

0

⇓ O • 1

coordinates matrix X

O1

dim 1 x11

dim 2 x12

O2 O3

x21 x31

x22 x32

M On-1

M xn-1,1

M xn-1,2

On

xn1

xn1





Past, Present, and Future of MDS

On



On-1 •O2

O • 3

–3–

• First sentence in Borg and Groenen (2005): Multidimensional scaling (MDS) is a method that represents measurements of similarity (or dissimilarity) among pairs of objects as distances between points of a lowdimensional space. • Who uses MDS? – – – –

psychology, sociology, archaeology, biology,

– – – –

medicine, chemistry, network analysis economists, etc.

• Similarities and dissimilarities: – Large similarity approximated by small distance in MDS. – Large dissimilarity (δij) approximated by large distance in MDS. – General term: proximity.

Past, Present, and Future of MDS

–4–

2 Some Historical Milestones • 1635: van Langren: Provides a distance matrix and a map.

Newcastle Durham Map of Durham county – Cartographer: Jacob van Langren – Date 1635

Past, Present, and Future of MDS

–5–

• 1635: van Langren: Provides a distance matrix and a map. • 1958: Torgerson:

Provides a solution for classical MDS based on eigendecomposition

• 1966: Gower:

Provides independently the same solution for classical MDS and gives connection to principal components analysis.

Classical MDS:

minimize Strain(X) = 1/4||J(∆ ∆(2)–D(2)(X))J||2 with J centering matrix by eigendecomposition of –½ J∆ ∆(2)J

Past, Present, and Future of MDS

–6–

• 1635: van Langren: Provides a distance matrix and a map. • 1958: Torgerson:

Provides a solution for classical MDS based on eigendecomposition

• 1966: Gower:

Provides independently the same solution for classical MD