Ranking Vectors Clustering: Theory and Applications

Ali Fattahi, Ali Eshragh, Babak Aslani, Meysam Rabiee · 2025

Read Ranking Vectors Clustering: Theory and Applications by Ali Fattahi, Ali Eshragh, Babak Aslani, Meysam Rabiee (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-12583.txt.

Introduction

Fattahi and three co-authors studied how to cluster rankings in twenty twenty-five. A ranking vector is an ordered list of preferences, like a voter's ballot or a customer's product order. Clustering such vectors means grouping similar preferences and naming each group's centroid, itself a valid ranking, which makes the problem harder than ordinary k-means.

The authors prove the general problem is NP-hard and characterize its feasible set. For a single cluster they derive a closed-form optimal centroid computable in linear time. Their approximation algorithm starts from ordinary k-means solutions and refines them, using a branch-and-bound subroutine that rebuilds clusters through a decision tree with a quality-speed dial. Error bounds accompany both methods. Experiments on synthetic and real data showed consistent improvements over the baseline with fast running times.

Catalog record

CREATORAli Fattahi, Ali Eshragh, Babak Aslani, Meysam Rabiee
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE133 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-12583

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Ranking Vectors Clustering: Theory and Applications Ali Fattahi, Ali Eshragh, Babak Aslani, Meysam Rabiee Abstract We study the problem of clustering ranking vectors, where each vector represents preferences as an ordered list of distinct integers. Specifically, we focus on the k k -centroids ranking vectors clustering problem ( KRC ), which aims to partition a set of ranking vectors into k k clusters and identify the centroid of each cluster. Unlike classical k k -means clustering ( KMC ), KRC constrains both the observations and centroids to be ranking vectors. We establish the NP-hardness of KRC and characterize its feasible set. For the single-cluster case, we derive a closed-form analytical solution for the optimal centroid, which can be computed in linear time. To address the computational challenges of KRC , we develop an efficient approximation algorithm, KRCA , which iteratively refines initial solutions from KMC , referred to as the baseline solution. Additionally, we introduce a branch-and-bound ( BnB ) algorithm for efficient cluster reconstruction within KRCA , leveraging a decision tree framework to reduce computational time while incorporating a controlling parameter to balance solution quality and efficiency. We establish theoretical error bounds for KRCA and BnB . Through extensive numerical experiments on synthetic and real-world datasets, we demonstrate that KRCA consistently outperforms baseline solutions, delivering significant improvements in solution quality with fast computational times. This work highlights the practical significance of KRC for personalization and large-scale decision making, offering methodological advancements and insights that can be built upon in future studies. Key words: ranking vectors clustering, computational complexity, efficient approximation algorithms, personalized recommendations, large-scale group decision making † † runningauthor: Fattahi, Eshragh, Aslani, and Rabiee † † runningtitle: Ranking Vectors Clustering: Theory and Applications † † authors: Carey Business School, Johns Hopkins University, Baltimore, MD USA, [email protected] Carey Business School, Johns Hopkins University, Washington, DC USA, International Computer Science Institute, University of California at Berkeley, CA USA, [email protected] Department of Systems Engineering and Operations Research, George Mason University, USA, [email protected] Business School, University of Colorado Denver, Denver, CO 80202, USA, [email protected] † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: 1 Introduction We study the problem of clustering ranking vectors for large-scale problems by developing theoretical frameworks and applying them to extensive synthetic and real datasets. A ranking vector is an m -dimensional vector that represents a permutation of the set \{1,\dots,m\} . Each entry in the vector is unique, corresponding to exactly one element from the set. In a ranking vector, the value of each entry indicates the position or rank of the corresponding option in an ordered list ( Aledo et al. 2018 , Hou and Triantaphyllou 2019 ) . Note that there are no ties, as each position is assigned to exactly one element. For instance, an individual’s order of preference for movie genres can be represented as a ranking vector, wherein each entry indicates the rank of the corresponding genre. Similarly, in a hiring committee, each member’s preference ranking over applicants captures their individual evaluation of candidates. In a similar vein, students may rank their subject preferences based on interest or perceived difficulty, while in healthcare, patients may rank treatment options according to factors such as effectiveness, side effects, and cost. These examples illustrate how ranking vectors naturally arise in diverse decision making contexts. The k -centroids ranking vectors clustering problem, denoted by KRC , involves partitioning a given set of n ranking vectors into k clusters and determining the centroid of each cluster by minimizing the sum of the squared Euclidean distances between the n ranking vectors and their assigned centroids. While KRC may seem similar to the classical k -means clustering ( KMC ) problem ( Lloyd 1982 , Arthur and Vassilvitskii 2006 ) , where both data points and centroids can take any real values, KRC imposes a stricter constraint: both the data points and the centroids must be ranking vectors. This structured discretization of the decision variables introduces new challenges to the problem. The KRC problem enables the personalization of offers, promotions, and recommendations by clustering ranking vectors, making it applicable across various domains such as enhancing user experiences on digital platforms. Beyond personalization, it also plays a crucial role in decision making contexts where diverse perspectives must be aggregated, such as in group decision making. Given its ability to structure ranking data efficiently, KRC is particularly valuable for large-scale applications, where n can scale to millions, requiring scalable and efficient computational methods. In Section 1.1 , we propose several applications for KRC to emphasize its broad applicability and discuss how our proposed methodology can potentially lead to significant improvements in these applications. We proceed by presenting our motivating examples in Section 1.1 and outlining our main results and insights in Section 1.2 . 1.1 Motivating Examples We propose several applications for KRC across diverse domains, ranging from online review platforms—illustrated by examples including streaming platforms such as Netflix, Amazon Prime, and HBO Max, hospitality review systems, and dining reservation platforms like OpenTable and Resy—to large-scale group decision making. To the best of our knowledge, the application of ranking vector clustering in these contexts is novel and has not been explored in the existing literature, as detailed in Section 2 . 1.1.1 Online Review Platforms. On streaming platforms such as Netflix, Amazon Prime, and HBO Max, viewers often rely on the average of individual ratings to decide what to watch. However, differences in genre preferences can result in significant variation in ratings, leading to high volatility. To address this, we propose a personalized approach to presenting average ratings that incorporates viewers’ genre preference rankings. While prior work has explored personalization based on viewer characteristics (Section 2 ), to the best of our knowledge, we are the first to personalize ratings using genre preference rankings. This approach is motivated by our hypothesis that differences in genre preferences drive variation in movie ratings. For instance, consider two types of viewers: A and B. Viewer A prefers comedy over thriller, while viewer B favors thriller over comedy. Suppose type A viewers consistently assign higher ratings to comedies, and type B viewers do the same for thrillers, reflecting the greater enjoyment they derive from their preferred genres. We explore such systematic rating behaviors using the MovieLens dataset ( grouplens.org/datasets/movielens ) in Section 6 . If a type A viewer relies on average ratings to choose between a comedy and a thriller, they might end up selecting a less desirable option. This misalignment is particularly likely when type A viewers are a minority — that is, when the number of type B viewers significantly outweighs that of type A. Research suggests a positive relationship between customer satisfaction and profitability ( Pooser and Browne 2018 , Williams and Naumann 2011 ) . Building on this insight, personalization based on genre preference rankings has the potential to significantly enhance viewer utility, particularly for minority groups. This personalization can be implemented using KRC to identify clusters of viewers with similar genre preference rankings. Based on these clusters, we propose that the platform personalize the presentation of average ratings. Specifically, a viewer would see the

Read the complete text