Allen

In this work, we consider the problem of clustering partial lexicographic preference trees, intuitive and often compact representations of user preferences over multi-valued attributes. Due to the preordering nature of PLP-trees, we define a variant of Kendall's τ distance metric to be used to compute distances between PLP-trees for clustering. To this end, extending the previous work by Li and Kazimipour (Li and Kazimipour 2018), we propose a polynomial time algorithm PlpDis to compute such distances, and present empirical results comparing it against the brute-force baseline. Based on PlpDis, we use various distance-based clustering methods to cluster PLP-trees learned from a car evaluation dataset. Our experiments show that hierarchical agglomerative nesting (AGNES) is the best choice for clustering PLP-trees, and that the single linkage variant of AGNES is the best fit for clustering large numbers of trees.