Characterization of Scoring Rules with Distances: Application to the Clustering of Rankings

Paolo ViappianiIJCAI 2015

In modern data-driven environments—from e-commerce platforms to recommendation engines—user preferences are frequently captured as rankings. Analyzing these rankings often requires clustering them into groups of similar users. However, clustering rankings presents a unique challenge: the "distance" between two ordered lists is not as intuitive as the Euclidean distance between points in a vector space.

This research establishes a theoretical bridge between social choice theory (the study of collective decision-making) and distance-based clustering. By demonstrating that common voting rules are equivalent to minimizing specific distance measures, the paper introduces a framework for ranking clustering that is both mathematically rigorous and computationally efficient.

Theoretical Framework: Scoring Rules as Distances

The core contribution of this work is the characterization of scoring rules through the lens of distance metrics. In a standard k-means clustering approach, one needs a distance measure to assign points to clusters and an aggregation method to update cluster centroids. For the algorithm to be consistent, the aggregation method must minimize the chosen distance.

The author proves that many popular aggregation rules, such as the Borda count and Plurality, implicitly minimize generalizations of the Spearman distance.

Summary of aggregation methods, their corresponding distance measures, and mathematical properties.

Key Mathematical Insights

  • The Borda-Spearman Link: The Borda count, which assigns points based on an item's position, is shown to minimize the sum of squared rank differences (Spearman distance).
  • Positional and Biased Rules: The framework extends to "Positional Spearman" distances, allowing for different weights at different ranks (e.g., prioritizing the top-k items), and "Biased Scoring Rules" that account for item-specific importance.
  • Metric Properties: A significant finding is that these distances often fail to meet the strict criteria of a true metric (like the triangle inequality). Instead, they are characterized as semimetrics or premetrics. The paper proves that no true metric can characterize the Borda or Plurality rules.

The Clustering Algorithm

Leveraging these characterizations, the author proposes an iterative clustering algorithm similar to Lloyd’s algorithm for k-means. The efficiency of this approach stems from the "update" step: because the aggregation method is a scoring rule, finding the new cluster centroid simply requires sorting items by their accumulated scores—a fast $O(n \log n)$ operation.

Empirical Results and Robustness

The methods were evaluated using the Sushi dataset, a benchmark containing 5,000 user rankings.

Computational Efficiency

The algorithm proved highly scalable. Clustering using the Plurality rule converged in under one second, while more complex biased rules took between 3 and 8 seconds. This speed makes the approach suitable for large-scale preference datasets.

Handling Incomplete Data

Real-world rankings are often incomplete. The author proposed a "reduced Spearman" heuristic to handle partial lists. Experimental results show that this heuristic performs comparably to more computationally intensive probabilistic sampling methods while remaining much faster.

Comparison of the reduced Spearman heuristic against sampling-based methods as the fraction of unobserved items increases.

Clustering Sensitivity

The choice of scoring rule significantly impacts the resulting clusters. "Steeper" rules (like Plurality), which place heavy weight on the top-ranked item, tend to produce fewer, larger clusters. In contrast, "flatter" rules like Borda distribute the population more evenly across clusters.

Conclusion and Future Directions

By unifying social choice and machine learning, this work provides a principled way to cluster rankings. While the focus on Spearman-style distances offers computational advantages, future work could explore other distance measures like Kendall-tau, though these often lead to NP-hard aggregation problems. Additionally, further research into non-uniform distributions for missing data could enhance the model's applicability to biased real-world datasets.

Summary updated

BibTeX
@inproceedings{viappiani2015characterization,
  author = {Paolo Viappiani},
  title = {{Characterization of Scoring Rules with Distances: Application to the Clustering of Rankings}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure