Perfect clustering from pairwise comparisons
We consider a pairwise comparisons model with n users and m items. Each user is shown a few pairs of items, and when a pair of items is shown to a user, he or she expresses a preference for one of the items based on a probabilistic model. The goal is to group users into clusters so that users within each cluster have similar preferences. We present an algorithm which clusters all users correctly with high probability using a number of pairwise comparisons which is within a polylog factor of a lower bound.
Pairwise comparison, Spectral clustering, Inference, Ranking
University of Illinois - Urbana-Champaign
Networked Digital Library of Theses and Dissertations
University of Illinois at Urbana-Champaign