0:45

And so we've looked at this in terms of visualizing graphs.

Â Graphs encode relationships between data points where the length of the edge is

Â irrelevant.

Â But if we want to look at a graph where the length is relevant,

Â we might want to look at ways of plotting the nodes of a graph or data,

Â based on the relationship between data points, based on distance.

Â So that we can try to preserve the distance in, for example,

Â a low dimensional, a two dimensional visualization of high dimensional data.

Â We may want the distance between data points in two dimensions to somehow

Â indicate the distance between the data points in higher dimensions.

Â And so that sets up a metric MDS,

Â metric multidimensional scaling where you try to preserve the distance between

Â data points even though you're displaying them at a lower dimensional space.

Â So here's a nice example.

Â We're not doing dimensionality reduction because we'll go from a two dimensional

Â space to a two dimensional space.

Â But it illustrates how we would compute a multidimensional scaling to try to

Â preserve the distance between points.

Â So here's distances between cities in the US, for example.

Â So we've got Boston, NYC, DC, Miami, Chicago, Seattle, SF, LA, and Denver.

Â And so the distance between, for example, Chicago and

Â NYC would be 803 miles in this example.

Â So the lower triangle of this data is showing the distance between

Â the city on the left and the city in the row, and the city in the column.

Â And so there'd be 0 distance between a city and itself.

Â And this will be symmetric, so

Â I haven't bothered to fill in the upper triangle of this matrix.

Â 2:36

So given those distances, dij, between data points i and j,

Â between city i and city j, can we recover the positions of those cities?

Â So I'm not taking the coordinates of those cities,

Â I'm just taking the distances between those cities.

Â Basically taking a graph where I'm specifying the length of the edges between

Â the nodes.

Â And then I want to find the positions of the nodes that satisfies

Â those edge lengths.

Â So we can do that by minimizing this function.

Â We basically take the distance between the two data points,

Â and then we want to subtract their actual distance, and we want to minimize that.

Â So if the distance between two data points equals the desired distance

Â between those two data points, then this should be close to zero.

Â And we square things here so that we keep everything positive so

Â that negative values aren't messing up our minimization.

Â So we can solve this with any number of non-linear optimization methods.

Â In the example I'm going to describe, I solved it just using

Â the Excel spreadsheet program with an optimizer plug-in.

Â So here's the results that I got,

Â I minimized that distance relationship between the actual

Â distance from my optimized variables and the desired distance.

Â And as you can see, things are obviously in the wrong place.

Â I've got the East Coast on the left and West Coast on the east, but

Â that should still preserve distance.

Â And there's a few other differences,

Â but basically I've got this general east to west trend.

Â Seattle is above SF and LA, Denver is here, Chicago is where it's at.

Â So I've preserved the distance of my

Â points even though I haven't preserved the exact geometry of the points.

Â And so this can be a useful layout method, especially for high dimensional data when

Â you're trying to preserve the distances between the points without necessarily

Â representing accurately their spatial configuration, their original coordinates.

Â So we've thrown away the original coordinates of these points.

Â And just using their distance relationship,

Â tried to preserve that in a reprojection, in this case in two dimensions.

Â So there's all sorts of ways you can use MDS, multidimensional scaling.

Â You can visualize affinities between data points,

Â areas of collaboration based on co-authorship of papers.

Â If you're visualizing papers or the number of any other attributes two data

Â points might have in common, anything you can describe as a distance.

Â It doesn't have to be coordinate distance, it can be other similarities.

Â It's used in human-computer interaction for

Â user interface design to basically lay out buttons.

Â If you have a dashboard with a lot of buttons, you can lay out the buttons by

Â organizing them based on how similar the buttons are to a given task.

Â And then,

Â let multidimensional scaling compute the coordinates of where the buttons should be

Â located so that buttons that are used together are close to each other.

Â And it's also used in marketing to create what are called perceptual maps

Â that are based on survey data of what people think of different products,

Â what attributes people assign to different products.

Â And then you can figure out what products are similar to other products and

Â create a map of products that way.

Â So, multidimensional scaling is enabled by optimization.

Â You don't have to write your own optimization program,

Â you can use pre-existing optimization packages.

Â You just need something that's going to minimize a function, and so

Â you need some form of non-linear minimization in an optimization package.

Â I found one that was enabled in Excel in order to do

Â the example I described in the slides.

Â [MUSIC]

Â