Perfect clustering from pairwise comparisons
type: CreativeWork
description: 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.
abstract: 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.
author: Satpathi, Siddhartha
language: en
keywords: Pairwise comparison, Spectral clustering, Inference, Ranking
date published: 2018-03-13T15:25:25Z
date modified: 2026-07-22T22:24:37Z
provider: University of Illinois - Urbana-Champaign
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: University of Illinois at Urbana-Champaign

PropertyValue
property ID: Handle
value: http://hdl.handle.net/2142/99229