Georgia Institute of Technology
Visualizing and modeling partial incomplete ranking data
Abstract
dc:description.abstractAnalyzing ranking data is an essential component in a wide range of important applications including web-search and recommendation systems. Rankings are difficult to visualize or model due to the computational difficulties associated with the large number of items. On the other hand, partial or incomplete rankings induce more difficulties since approaches that adapt well to typical types of rankings cannot apply generally to all types. While analyzing ranking data has a long history in statistics, construction of an efficient framework to analyze incomplete ranking data (with or without ties) is currently an open problem. This thesis addresses the problem of scalability for visualizing and modeling partial incomplete rankings. In particular, we propose a distance measure for top-k rankings with the following three properties: (1) metric, (2) emphasis on top ranks, and (3) computational efficiency. Given the distance measure, the data can be projected into a low dimensional continuous vector space via multi-dimensional scaling (MDS) for easy visualization. We further propose a non-parametric model for estimating distributions of partial incomplete rankings. For the non-parametric estimator, we use a triangular kernel that is a direct analogue of the Euclidean triangular kernel. The computational difficulties for large n are simplified using combinatorial properties and generating functions associated with symmetric groups. We show that our estimator is computational efficient for rankings of arbitrary incompleteness and tie structure. Moreover, we propose an efficient learning algorithm to construct a preference elicitation system from partial incomplete rankings, which can be used to solve the cold-start problems in ranking recommendations. The proposed approaches are examined in experiments with real search engine and movie recommendation data.
Degree
thesis:*- Department dc:contributor.department
- Computing
- Grantor dc:publisher
- Georgia Institute of Technology
- Year dc:date.issued
- 2012
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Sun, Mingxuan
- Advisor dc:contributor.advisor
-
- Lebanon, Guy
- Committee members dc:contributor.committeemember
-
- Collins-Thompson, Kevyn
- Gray, Alexander
- Isbell, Charles
- Zha, Hongyuan
Subjects
dc:subject × 7Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1853/45793