Collaborative partitioning with maximum user satisfaction

Our collaborative partitioning model posits a bicriteria objective in which we seek the best item clustering that satisfies the most users at the highest level of satisfaction. We consider two basic methods for determining user satisfaction. The first method is based on how well each user's preferences match a given partition, and the second method is based on average correlation scores taken over sufficiently large subpopulations of users. We show these problems are NP-Hard and develop a set of heuristic approaches for solving them. We provide lower bounds on the satisfaction level on random data, and error bounds in the planted partition model, which provide confidence levels for our heuristic methods. Finally, we present experiments on several real examples that demonstrate the effectiveness of our framework.