Visual estimation of structure in ranked data

Abstract

Ranked data arise when some group of judges is asked to rank order a set of n items according to some preference function. A judge's ranking is denoted by a vector x = $(x\sb1,...,x\sb{n}),$ where $x\sb{i}$ is the rank assigned to item i. If we treat these vectors as points in $\Re\sp{n}$, we are led to consider the geometric structure encompassing the collection of all such vectors: the convex hull of the n! points in $\Re\sp{n}$ whose coordinates are permutations of the first n integers. These structures are known as permutation polytopes. The use of such structures for the analysis of ranked data was first proposed by Schulman $\lbrack65\rbrack$. Geometric constraints on the shapes of the permutation polytopes were later noted by McCullagh $\lbrack56\rbrack.$ Thompson $\lbrack77\rbrack$ advocated using the permutation polytopes as outlines for high-dimensional "histograms", and generalized the class of polytopes to deal with partial rankings (ties allowed). Graphical representation of ranked data can be achieved by putting varying masses at the vertices of the generalized permutation polytopes. Each face of the permutation polytope has a specific interpretation; for example, item i being ranked first. The estimation of structure in ranked data can thus be transformed into geometric (visual) problems, such as the location of faces with the highest concentrations of mass. This thesis addresses various problems in the context of such a geometric framework: the automation of graphical displays of the permutation polytopes; illustration and estimation of parametric models; and smoothing methods using duality--where every face is replaced with a point. A new way of viewing the permutation polytopes as projections of high-dimensional hypercubes is also given. The hypercubes are built as cartesian products of the $(\sbsp{2}{n})$ possible paired comparisons, and as such lead to methods for building rankings from collections of paired comparisons.