Cluster Analysis of Heterogeneous Rank Data.pdf

Cluster Analysis of Heterogeneous Rank Data Ludwig M. Busse bussel@student.ethz.ch Peter Orbanz porbanz@inf.ethz.ch Joachim M. Buhmann jbuhmann@inf.ethz.ch Institute of Computational Science, ETH Zurich, 8092 Zurich, Switzerland This revision of the ICML 2007 proceedings article corrects an error in Sec. 3. Abstract Cluster analysis of ranking data, which occurs in consumer questionnaires, voting forms or other inquiries of preferences, at- tempts to identify typical groups of rank choices. Empirically measured rankings are often incomplete, i.e. different numbers of filled rank positions cause heterogeneity in the data. We propose a mixture approach for clustering of heterogeneous rank data. Rank- ings of different lengths can be described and compared by means of a single probabilistic model. A maximum entropy approach avoids hidden assumptions about missing rank po- sitions. Parameter estimators and an ef- ficient EM algorithm for unsupervised in- ference are derived for the ranking mixture model. Experiments on both synthetic data and real-world data demonstrate significantly improved parameter estimates on heteroge- neous data when the incomplete rankings are included in the inference process. 1. Introduction Ranking data commonly occurs in preference surveys: A number of subjects are asked to rank a list of items or concepts according to their personal order of prefer- ence. Two types of ranking data are usually discussed in the literature: Complete and partial (or incom- plete) rankings. A wide range of probabilistic mod- els is available for both (Diaconis, 1988; Critchlow, 1985). A complete ranking of r items is a permutation of these items, listed in order of preference. Mathemat- ical models of rankings are based on the corresponding permutation group. A partial ranking is a preference Appearing in Proceedings of the 24 th International Confer- ence on Machine Learning, Corvallis, OR, 2007. Copyright 2007 by the author(s)/owner(s). list of t out of r item