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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2018

Author dc:creator

• Satpathi, Siddhartha

Contributors dc:contributor

• Srikant, Rayadurgam

• Pairwise comparison
• Spectral clustering
• Inference
• Ranking

Statement dc:rights

• Copyright 2017 Siddhartha Satpathi

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/99229

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/99229