\documentclass[xcolor = pdftex, dvipsnames,table] {beamer} \usetheme{Berkeley} \title[Eighth Circuit]{Abraham Lincoln's Eighth Judicial Circuit (1850) in the Age of MapQuest} \author{Lawrence Hubert} \institute{Department of Psychology \\The University of Illinois} \date{APA Division 5 Presentation \\ Jacob Cohen Award for Distinguished \\ Contributions to Teaching and Mentoring\\ August 8, 2009} \begin{document} \begin{frame} \titlepage \end{frame} \begin{frame} \frametitle{So Why This Talk?} Because the Jacob Cohen Award is for teaching and mentoring, it seems only appropriate to provide an interesting example that we all might use in our graduate methodology classes. \bigskip Secondly, because of where I now live and teach (in Urbana, Illinois), this example for me is very locally salient (and useful for the various multidimensional scaling and clustering classes I regularly teach). \bigskip Maybe most importantly, we can do a little to honor the 200th anniversary of Abraham Lincoln's birth (on February 12, 1809). \bigskip Also, I think I have a cooler title than Howard Wainer. \end{frame} \begin{frame} \frametitle{The Eighth Judicial Circuit} Prior to becoming the $16^{th}$ President of the United States in 1860, Abraham Lincoln worked as a lawyer in the Eighth Judicial Circuit in Illinois. \medskip The Eighth Circuit consisted of fourteen counties (and their county seats), with a total of some one hundred thousand people. \medskip These county seats were visited consecutively in the Spring and Fall of each year, over a period of eleven weeks and with a travel distance of well over four hundred miles. \medskip The counties were visited in the (circular) ordering listed on the next slide, starting from the state capital of Springfield. Because I live in Urbana, however, I will give that locale the number one label. \end{frame} \begin{frame} \frametitle{The County Seats of the Eighth Circuit} \begin{columns}[l] \column{2.0in} 1: Urbana (Champaign) 2: Danville (Vermilion) 3: Paris (Edgar) 4: Shelbyville (Shelby) 5: Sullivan (Moultrie) 6: Decatur (Macon) 7: Taylorville (Christian) \column{2.0in} 8: Springfield (Sangamon) 9: Pekin (Tazewell) 10: Metamora (Woodford) 11: Bloomington (McLean) 12: Mt. Pulaski (Logan) 13: Clinton (Dewitt) 14: Monticello (Piatt) \end{columns} \bigskip For those who have lived in the Midwest, county names and where they are in relation to you, become very familiar from all the tornado warnings we receive. Thus, if a sighting occurs to the west in Piatt county, I'm on my way to the basement. \end{frame} \begin{frame} \frametitle{An Old Map of the Eighth Judicial Circuit} \begin{center} \includegraphics[height=4.0in]{lincoln_eighth_circuit_oldmap.pdf} \end{center} \end{frame} \begin{frame} \frametitle{Lincoln's Mode of Transport on the Circuit} \begin{center} \includegraphics[height=4.0in]{lincolninbuggy.pdf} \end{center} \end{frame} \begin{frame} \frametitle{The Traveling Sales(man)person Problem (TSP)} Given a set of cities that a salesperson must visit, plus measures of effort to travel between cities (e.g., distance, time, cost, and so on), find an ``optimal'' route that starts at some city, visits each of the other cities, and returns to the city of origin. \bigskip ``Optimality"" might be defined as the tour of least total effort, e.g., the minimal sum of travel times. \bigskip The related seriation task of defining an ``optimal'' path that visits each city once (but does not need to return to the starting city), is a special case: just define a ``dummy city'' for which there is no effort in going to or from it (in relation to any other city). \bigskip (And no, the TSP does *not* refer to the jokes told by boys in Junior High.) \end{frame} \begin{frame} \frametitle{The Ubiquity of the TSP} The TSP is the most studied combinatorial optimization problem in Operations Research (or elsewhere, I might add). \smallskip It has spawned an enormous literature on general solution techniques in combinatorial optimization. \smallskip It is the optimization ``engine'' for a huge number of creative applications. \smallskip Two pertinent references: \smallskip The Traveling Salesman Problem: A Computational Study David Applegate; Robert Bixby; Vasek Chvatel; William Cook Princeton University Press, 2007 \bigskip Applications of Combinatorial Programming to Data Analysis: The Traveling Salesman and Related Problems Lawrence Hubert; Frank Baker \emph{Psychometrika}, 1978, \emph{43}, 81--91. \end{frame} \begin{frame} \frametitle{MapQuest Times for Travel on the Eighth Circuit} \begin{flushleft} \begin{tabular}{ccccccccccc} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 00 & {\color{Red} 35} & 76 & 93 & 72 & 62 & 97 & 94 & 103 & 100\\ 2 & 35 & 00 & {\color{Red} 57} & 119 & 98 & 87 & 123 & 119 & 129 & 125\\ 3 & 76 & 57 & 00 & {\color{Red} 87} & 71 & 94 & 136 & 135 & 166 & 162 \\ 4 & 93 & 119 & 87 & 00 & {\color{Red} 30} & 49 & 49 & 86 & 142 & 145 \\ 5 & 72 & 98 & 71 & 30 & 00 & {\color{Red} 41} & 59 & 78 & 135 & 135 \\ 6 & 62 & 87 & 94 & 49 & 41 & 00 & {\color{Red} 42} & 44 & 97 & 98 \\ 7 & 97 & 123 & 136 & 49 & 59 & 42 & 00 & {\color{Red} 41} & 103 & 118 \\ 8 & 94 & 119 & 135 & 86 & 78 & 44 & 41 & 00 & {\color{Red} 76} & 91 \\ 9 & 103 & 129 & 166 & 142 & 135 & 97 & 103 & 76 & 00 & {\color{Red} 38} \\ 10 & 100 & 125 & 162 & 145 & 135 & 98 & 118 & 91 & 38 & 00 \\ 11 & 59 & 85 & 122 & 104 & 94 & 57 & 93 & 72 & 50 & 48 \\ 12 & 76 & 102 & 122 & 76 & 68 & 32 & 48 & 37 & 65 & 81 \\ 13 & 56 & 82 & 114 & 78 & 68 & 31 & 66 & 60 & 71 & 70 \\ 14 & 33 & 59 & 83 & 68 & 46 & 35 & 71 & 67 & 100 & 98 \\ \end{tabular} \end{flushleft} \end{frame} \begin{frame} \frametitle{MapQuest Times for Travel on the Eighth Circuit} \begin{flushleft} \begin{tabular}{ccccc} & 11 & 12 & 13 & 14 \\ 1 & 59 & 76 & 56 & {\color{Red} 33} \\ 2 & 85 & 102 & 82 & 59 \\ 3 & 122 & 122 & 114 & 83 \\ 4 & 104 & 76 & 78 & 68 \\ 5 & 94 & 68 & 68 & 46 \\ 6 & 57 & 32 & 31 & 35 \\ 7 & 93 & 48 & 66 & 71 \\ 8 & 72 & 37 & 60 & 67 \\ 9 & 50 & 65 & 71 & 100 \\ 10 & {\color{Red} 48} & 81 & 70 & 98 \\ 11 & 00 & {\color{Red} 54} & 31 & 60 \\ 12 & 54 & 00 & {\color{Red} 27} & 50 \\ 13 & 31 & 27 & 00 & {\color{Red} 36} \\ 14 & 60 & 50 & 36 & 00 \\ \end{tabular} \end{flushleft} \end{frame} \begin{frame} \frametitle{Placement of the Eighth Circuit County Seats} \begin{center} \scalebox{2}{\includegraphics[height = 2.0in]{map_eighth_circuit_scaled.pdf}} \end{center} \end{frame} \begin{frame} \frametitle{Lincoln's route on the Eighth Circuit} \begin{center} \scalebox{2}{\includegraphics[height = 2.0in]{map_eighth_circuit_scaled_lincoln_route.pdf}} \end{center} \end{frame} \begin{frame} \frametitle{The Optimal Route on the Eighth Circuit} \begin{center} \scalebox{2}{\includegraphics[height = 2.0in]{map_eighth_circuit_scaled_optimal_route.pdf}} \end{center} \end{frame} \begin{frame} \frametitle{The Quality of Lincoln's Tour} The optimal tour based on total time is 601; Lincoln's total tour length was 645, so he could have saved 44 minutes (in today's MapQuest time) using the optimal tour. \bigskip Still, Lincoln's tour is pretty good, and does satisfy two properties that an optimal tour must have for a Euclidean embedded TSP. \bigskip (a) The cities in the convex hull are visited in order (for the idea of a convex hull, think about a rubber band pulled around pegs standing at each city location). \bigskip (b) The paths in Lincoln's tour do not cross. \end{frame} \begin{frame} \frametitle{} The improvements made to Lincoln's tour to get to one that is optimal are suggested by the acute angles at Shelbyville and Mt. Pulaski. \bigskip Even though the MapQuest times of travel and the MapQuest distances are \emph{not} linear (due to the possible use of freeways or slower county road travel), the exact same tour would be optimal and Lincoln's would not (but would still be pretty good). \bigskip The map representations given earlier were generated from the actual longitude and latitude values for the county seats (also, given by MapQuest); in other words, the MapQuest distances or times were not used to generate the maps. \end{frame} \begin{frame} \frametitle{Instructional Uses of the Lincoln MapQuest Example} There are at least four areas in Psychology that might use this example: \bigskip A) Direct application of the TSP (or optimal path) optimization task \medskip cda.psych.uiuc.edu/lincoln\_mapquest\_presentation.pdf \medskip B) Use of the example itself for multidimensional scaling and visualization \medskip C) Comparisons between alternative proximity matrix representations \medskip D) To give illustrations from the field of computational geometry \end{frame} \begin{frame} \frametitle{Six TSP (or Optimal Path) Applications} A) As a canonical experimental task in the problem solving literature: Some tours are more equal than others: The convex-hull model revisited with lessons for testing models of the traveling salesperson problem Susanne Tak, Marco Plaisier, and Iris van Rooij \emph{The Journal of Problem Solving}, 2008, \emph{2}, 4--25 (Online journal) \bigskip B) As a (developmental) task in distinguishing perceptual versus cognitive skills: Perceptual or analytical processing? Evidence from children's and adult's performance on the Euclidean traveling salesperson problem Iris van Rooij, U. Stege, and A. Schactman \emph{The Journal of Problem Solving}, 2006, \emph{1}, 44--73. \end{frame} \begin{frame} \frametitle{} C) As part of the continuing discussion of what constitutes ``figural goodness'': The generally direct relation between the quality of a tour and its perceived goodness-of-figure The discussion of tour aesthetics with high quality geometric tours ``feeling right'' --- particularly to graphic design professionals \bigskip D) As part of various neuropsychological assessment procedures: The Trail Making Test from the Halstead-Reitan Battery \end{frame} \begin{frame} \frametitle{} E) As a model for Data Array Clustering and helping interpret the patterning in an $n$ object by $p$ attribute data matrix: \[ \mathbf{X} = \{x_{ij}\}_{n \times p} \] where $x_{ij}$ is the value for object $i$ on attribute $j$. \bigskip Define two separate proximity matrices between the objects and between the attributes: \[ \mathbf{R}_{row} = \{r_{ii'}\} = \{\sum_{j=1}^{p} x_{ij}x_{i'j}\}_{n \times n} \] \[ \mathbf{C}_{column} = \{c_{jj'}\} = \{ \sum_{i=1}^{n} x_{ij}x_{ij'} \}_{p \times p} \] \end{frame} \begin{frame} \frametitle{} Reorder the rows (and separately the columns) to place the numerically larger elements of the array together by finding maximum weight paths using $\mathbf{R}_{row}$ and $\mathbf{C}_{column}$. \smallskip Could lead to prettier heat maps for enormously-sized matrices given that we now can solve the TSP optimally for tens of thousands of cities (can we all say, ``data mining''): \smallskip A very nice reference for some of the historical background: \smallskip The history of the cluster heat map Leland Wilkinson and Michael Friendly \emph{The American Statistician}, in press. \smallskip Also see: The bond energy algorithm revisted Phipps Arabie; Lawrence Hubert \emph{IEEE Transactions on Systems, Man, and Cybernetics}, \emph{20}, 1990, 268--274. \end{frame} \begin{frame} \frametitle{} \begin{center} \scalebox{1.5}{\includegraphics[height = 2.0in]{Heatmap_illustration.pdf}} \end{center} \end{frame} \begin{frame} \frametitle{} E) As a model for Unidimensional Unfolding, using an $n$ subject by $p$ object preference matrix: \[ \mathbf{P} = \{p_{ij}\}_{n \times p} \] where $p_{ij}$ is a measure of preference (or dissimilarity) that subject $i$ has for object $j$ (i.e., a low value implies preference for the object). \bigskip We look for a reordering of the rows of $\mathbf{P}$ so that within each column the entries generally decrease to a minimum and thereafter increase. \bigskip Similarly, we look for a reordering of the columns to identify the same type of gradient within each row. \end{frame} \begin{frame} \frametitle{} As suggested by D.G. Kendall, define two separate proximity matrices between the objects and between the attributes: \[ \mathbf{R}_{row} = \{r_{ii'}\} = \{\sum_{j=1}^{p} \min(x_{ij}, x_{i'j})\}_{n \times n} \] \[ \mathbf{C}_{column} = \{c_{jj'}\} = \{ \sum_{i=1}^{n}\min( x_{ij}, x_{ij'})\}_{p \times p} \] And obtain the row and column reorderings by finding maximum weight paths within $\mathbf{R}_{row}$ and $\mathbf{C_{column}}$ \bigskip We are, in effect, looking for the Coombsian ``parallelograms'': \end{frame} \begin{frame} \frametitle{} \begin{tabular}{ccccccccc} attributes: & a1 & a2 & a3 & a4 & a5 & a6 & a7 & a8 \\ \hline subjects & & & & & & & & \\ s1 & 2 & 3 & 5 & 8 & 12 & 14 & 17 & 19 \\ s2 & 1 & 2 & 4 & 7 & 11 & 13 & 16 & 18 \\ s3 & 2 & 1 & 1 & 4 & 8 & 10 & 13 & 15 \\ s4 & 4 & 3 & 1 & 2 & 6 & 8 & 11 & 13 \\ s5 & 5 & 4 & 2 & 1 & 5 & 7 & 10 & 12 \\ s6 & 7 & 6 & 4 & 1 & 3 & 5 & 8 & 10 \\ s7 & 8 & 7 & 5 & 2 & 2 & 4 & 7 & 9 \\ s8 & 9 & 8 & 6 & 3 & 1 & 3 & 6 & 8 \\ s9 & 11 & 10 & 8 & 5 & 1 & 1 & 4 & 6 \\ s10 & 13 & 12 & 10 & 7 & 3 & 1 & 2 & 4 \\ s11 & 14 & 13 & 11 & 8 & 4 & 2 & 1 & 3 \\ s12 & 16 & 15 & 13 & 10 & 6 & 4 & 1 & 1 \\ \end{tabular} \end{frame} \begin{frame} \frametitle{} F) As a model for Profile Smoothing (or what is now known as Parallel Coordinate Analysis), and helping unclutter the plots of $n$ subject profiles over a set of $p$ attributes (the latter are listed along a horizontal axes). \medskip Define a proximity matrix among the attributes as \[ \mathbf{C}_{column} = \{c_{jj'}\} = \{ \sum_{i=1}^{n} I( x_{ij} > x_{i'j} \ \mathrm{and} \ x_{ij'} < x_{i'j'}) \] where $I(\cdot)$ is a zero/one indicator of a crossing of two profiles for subjects $i$ and $i'$ \medskip A minimum weight path using $\mathbf{C}_{column}$ is a mechanism for minimizing the number of crossings over the set of profiles (a measure of visual clutter). \end{frame} \begin{frame} \frametitle{} Some particularly relevant sources: \bigskip Hyperdimensional Data Analysis Using Parallel Coordinates Edward Wegman \emph{Journal of the American Statistical Association}, 1990, \emph{85}, 664-675 \medskip Chapter 1: Profiles, in John Hartigan, \emph{Clustering Algorithms}, 1975, Wiley \medskip \emph{Parallel Coordinates: Visual Multidimensional Geometry and Its Applications} Alfred Inselberg, 2009, Springer \end{frame} \begin{frame} \frametitle{Applications of the MapQuest Time Data for Multidimensional Scaling and Visualization} Using MapQuest times to generate a spatial representation of the county seats, we can compare this scaling to the actual map based on longitude and latitude. \bigskip The comparison can be done through a Procrustes transformation of the coordinates from the scaling to the coordinates of the actual map (e.g., through a MATLAB M-function, procrustes.m). \bigskip We carried out the (metric) multidimensional scaling with the M-file, mdscale.m, from the Statistics Toolbox in MATLAB. \end{frame} \begin{frame} \frametitle{Euclidean Scaling Based on the Mapquest Times} \begin{center} \scalebox{2}{\includegraphics[height = 2.0in]{lincoln_time_eu_map.pdf}} \end{center} \end{frame} \begin{frame} \frametitle{Comparison to Longitude and Latitude} \begin{center} \scalebox{2}{\includegraphics[height = 2.0in]{lincoln_time_eu_to_lat_long.pdf}} \end{center} \end{frame} \begin{frame} \frametitle{Property Fitting in a Multidimensional Scaling} Given the spatial representation from a scaling based on time, the two properties of longitude and latitude can be fit as vectors into the representation to indicate east-west and north-south directions. \bigskip These projections (defining two vectors in the scaling) can be seen as an illustration of Tucker's vector model, or alternatively, as one of Doug Carroll's external unfolding options in PREFMAP. \end{frame} \begin{frame} \frametitle{Vector Fitting in a Multidimensional Scaling} \begin{center} \scalebox{2}{\includegraphics[height = 2.0in]{lincoln_time_eu_lat_long_fitted.pdf}} \end{center} \end{frame} \begin{frame} \frametitle{Scaling in the Euclidean or City-Block Metrics} Because times between locations do not always reflect straightline (i.e., Euclidean) distances, possibly better fits could be obtained using city-block metric scaling methods. \bigskip Also, there is a city-block bias of major highways going East/West and North/South, and in how states were platted in the 1800's. \bigskip At one time I lived at the intersection in Champaign County at 1800N and 600E (18 miles north of the county to the south, and 6 miles east of the county to the west). \end{frame} \begin{frame} \frametitle{} The city-block scaling of the MapQuest travel time data was done with the very robust M-file, biscalqa.m, documented in the monograph: \bigskip \emph{Structural representation of proximity matrices with MATLAB} Lawrence Hubert; Jacqueline Meulman; Phipps Arabie SIAM: Philadelphia, 2006 \bigskip As the illustration to follow shows, it really makes little difference in this case, whether a scaling is done with the city-block or the Euclidean metric. \bigskip From my experiences, this latter observation is one that generalizes very widely. \end{frame} \begin{frame} \frametitle{City-Block Scaling of the MapQuest Time Data} \begin{center} \scalebox{2}{\includegraphics[height = 2.0in]{lincoln_time_cb_map.pdf}} \end{center} \end{frame} \begin{frame} \frametitle{Procrustean Transformation of Euclidean To City-Block Coordinates} \begin{center} \scalebox{2}{\includegraphics[height = 2.0in]{lincoln_time_eu_to_cb.pdf}} \end{center} \end{frame} \begin{frame} \frametitle{Comparisons of Alternative Proximity Matrix Representations} We can have meaningful demonstrations of how various alternative methodologies look and compare on the same data set. For example, for the MapQuest time data: \bigskip A (best) least-squares fitted ultrametric has a (not so good) variance-accounted-for (vaf) of 49.32\% (but using about half of the fitted ``parameters'' of the next three) \bigskip A (best) least-squares fitted additive tree has a vaf of 85.25\% \bigskip A (best) least-squares city-block scaling has a vaf of 97.48\% \bigskip A (best) least-squares Euclidean scaling has a vaf of 98.80\% \bigskip A number of ways could be tried for imbedding an ultrametric or additive tree into one of the scalings. \end{frame} \begin{frame} \frametitle{Computational Geometry Illustrations} Various computationally important (and very cool) geometric structures can be shown nicely with the Eighth Circuit Map: \bigskip Voronoi diagram: a subdivision of a Euclidean space that shows the regions of points closest to each of the given points in the space. \bigskip Delaunay triangulation: an undirected graph among the given points where an edge exists between two points if a boundary is present in the Vornoi diagram separating the two points. \bigskip Nearest neighbor graph: an undirected graph among the given points when an edge is present between two points if one is a nearest neighbor of the other. \end{frame} \begin{frame} \frametitle{} Minimum spanning tree: an undirected, connected, acyclic graph among the given points that has minimum weight for the sum of edge lengths. \bigskip Gabriel graph: an undirected graph among the given points where an edge exists between two points if the disk having that edge as a line segment includes no other points from the given point set. \bigskip A Gabriel graph is a subgraph of the Delaunay triangulation and contains the minimum spanning tree and the nearest neighbor as subgraphs. \end{frame} \begin{frame} \frametitle{Voronoi Diagram for the Eighth Circuit} \begin{center} \scalebox{2}{\includegraphics[height = 2.0in]{lincoln_voronoi.pdf}} \end{center} \end{frame} \begin{frame} \frametitle{Delaunay Tesselation for the Eighth Circuit} \begin{center} \scalebox{2}{\includegraphics[height = 2.0in]{lincoln_delaunay.pdf}} \end{center} \end{frame} \begin{frame} \frametitle{Minimum Spanning Tree for the Eighth Circuit} \begin{center} \scalebox{2}{\includegraphics[height = 2.0in]{map_eighth_circuit_minimumspanningtree.pdf}} \end{center} \end{frame} \end{document}