\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, 2009} \begin{document} \begin{frame} \titlepage \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 about 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 (Sangaman) 9: Pekin (Tazewell) 10: Metamora (Woodford) 11: Bloomington (McLean) 12: Mt. Pulaski (Logan) 13: Clinton (Dewitt) 14: Monticello (Piatt) \end{columns} \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 Salesman (Salesperson) (TSP) Problem} Given a set of cities that a salesman 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 (for any other city). \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 country road travel), the exact same tour would be optimal and Lincoln's would not (but would still be pretty good). 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{TSP (or Optimal Path) Applications in Psychology} 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 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}$. \bigskip Could lead to prettier heat maps for enormously sized matrices given that we now can solves optimally the TSP for a number of cities into the tens of thousands (can we say, ``data mining''): \bigskip The history of the cluster heat map Leland Wilkinson and Michael Friendly \emph{The American Statistician}, in press. \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 obtaining minimum weight paths within $\mathbf{R}_{row}$ and $\mathbf{C_{column}}$ \end{frame} \begin{frame} \frametitle{} \begin{tabular}{cccccccc} attributes & a1 & a2 & a3 & a4 & a5 & a6 & a7 & a8 \\ 2 & 3 & 5 & 8 & 12 & 14 & 17 & 19 \\ 1 & 2 & 4 & 7 & 11 & 13 & 16 & 18 \\ 2 & 1 & 1 & 4 & 8 & 10 & 13 & 15 \\ 4 & 3 & 1 & 2 & 6 & 8 & 11 & 13 \\ 5 & 4 & 2 & 1 & 5 & 7 & 10 & 12 \\ 7 & 6 & 4 & 1 & 3 & 5 & 8 & 10 \\ 8 & 7 & 5 & 2 & 2 & 4 & 7 & 9 \\ 9 & 8 & 6 & 3 & 1 & 3 & 6 & 8 \\ 11 & 10 & 8 & 5 & 1 & 1 & 4 & 6 \\ 13 & 12 & 10 & 7 & 3 & 1 & 2 & 4 \\ 14 & 13 & 11 & 8 & 4 & 2 & 1 & 3 \\ 16 & 15 & 13 & 10 & 6 & 4 & 1 & 1 \\ \end{tabular} \end{frame} \begin{frame} \frametitle{} F) As a model for Profile Smoothing (or Parallel Coordinate Analyses) 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}$ is a mechanism for minimizing the number of crossing over the set of profiles (a measure of clutter). \end{frame} \begin{frame} \frametitle{} 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 Eighth Judicial Circuit for Data Analysis and Visualization Examples} Using MapQuest times to effect a spatial representation of the county seats, we can compare this scaling to the actual map based on longitude and latitude. The comparison can be done through a Procrustes transformation of the coordinates from the scaling to the actual map (e.g., through a MATLAB M-function). \bigskip Or 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 \end{frame} \end{document}