Clustering Partial Lexicographic Preference Trees (Student Abstract)

Joseph Allen, Xudong Liu, Karthikeyan Umapathy, Sandeep ReddivariAAAI 2021 · DOI

Introduction

Understanding user choice is a cornerstone of modern marketing and recommendation systems. Lexicographic Preference Trees (LP-trees) provide a powerful framework for modeling these choices by representing how individuals prioritize attributes—for instance, prioritizing a car's price over its fuel efficiency. However, real-world preferences are often "partial"; users may not consider every attribute in every context. While Partial LP-trees (PLP-trees) are more realistic and compact, they present a significant computational challenge: comparing them. Standard metrics like Kendall’s $\tau$ typically require exponential time to compute for PLP-trees, making large-scale clustering impossible.

The PlpDis Algorithm

To address this, we introduce PlpDis, a polynomial-time algorithm designed to calculate the distance between PLP-trees. PlpDis computes a variant of Kendall’s $\tau$, denoted as $\tau'$, by traversing the tree structures directly rather than enumerating all possible alternative combinations. The algorithm distinguishes between "strict disagreements" (opposite rankings) and "partial disagreements" (where one tree implies equivalence and the other does not). By introducing a weighting coefficient ($c$) for partial disagreements, PlpDis allows for a nuanced comparison of models with varying levels of specificity.

Experimental Evaluation

The approach was evaluated using the Car Evaluation dataset. We generated "forests" of PLP-trees ranging from 100 to 10,000 individual models. We then constructed distance matrices using PlpDis and applied various clustering techniques, including Spectral Clustering, Affinity Propagation, and Agglomerative Nesting (AGNES).

Clustering Performance

The effectiveness of the clustering was measured using the ratio of the Dunn Index (DI) to the Davies-Bouldin Index (DBI), where a higher ratio indicates better-defined clusters.

Clustering performance (DI/DBI ratio) for different algorithms and forest sizes.

As shown in the results, AGNES variants (specifically AGNES-C and AGNES-S) consistently outperformed more complex methods. Notably, while PlpDis enabled the clustering of 10,000 trees, Spectral Clustering failed to finish (DNF) within the allotted time on the largest dataset, highlighting the scalability challenges that PlpDis helps overcome.

Visualizing Preference Clusters

Beyond numerical metrics, visualizing the relationships between preference profiles provides qualitative insight. By treating the distance matrix as a graph, we can identify distinct communities of users with similar decision-making priorities.

A KNN-graph visualization of clustered preference trees.

Conclusion and Future Work

PlpDis provides a scalable foundation for analyzing large-scale preference data. By moving from exponential to polynomial-time distance computation, it opens the door for sophisticated user segmentation in real-time systems. Future work will focus on optimizing the weighting of partial disagreements and scaling the implementation to handle millions of users, as seen in global digital services.

Summary updated

BibTeX
@inproceedings{allen2021clustering,
  author = {Joseph Allen and Xudong Liu and Karthikeyan Umapathy and Sandeep Reddivari},
  title = {{Clustering Partial Lexicographic Preference Trees (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i18.17872},
}
Figure