TL;DR
This paper introduces the novel task of mining "rank data," which consists of ordered lists of items, and proposes algorithms for discovering frequent subrankings and association rules within this data. This work opens up a new avenue for data mining by extending established techniques to handle preference and ranking information, which is increasingly prevalent in areas like preference learning.
What Problem Does This Paper Address?
Traditional data mining often deals with transactional data (itemsets) or sequential data. However, many real-world scenarios involve data where the order of items is crucial, such as user preferences, survey responses, or competitive rankings. This paper identifies a gap in existing data mining literature by focusing on "rank data" – data that represents total orders of a set of items. The authors aim to develop methods for discovering interesting patterns within these rankings, analogous to how frequent itemsets or association rules are found in transactional data. This is particularly relevant given the rise of preference learning, where understanding user rankings is paramount.
Methods
The paper proposes two main types of rank patterns:
- Subrankings: These are rankings of a subset of items. For example, if a user ranks sushi, a subranking might only consider their top 3 favorite sushi. The paper defines the "support" of a subranking as its relative frequency in the dataset and introduces the concept of "frequent subrankings" based on a user-defined minimum support threshold.
- Association Rules: These are rules of the form $\pi_A \rightarrow \pi_B$, where $\pi_A$ and $\pi_B$ are subrankings. The rule suggests that if items are ranked according to $\pi_A$, then items are likely to be ranked according to $\pi_B$. A key constraint is that the sets of items in $\pi_A$ and $\pi_B$ should have at most one item in common to avoid trivial dependencies. The paper defines measures like "confidence" and "significance" for these rules, adapting concepts from itemset mining.
The core algorithm for mining frequent subrankings is a generalization of the Apriori algorithm. It works in a level-wise manner, starting with frequent 2-rankings (pairwise preferences) and iteratively constructing candidate k-rankings from frequent (k-1)-rankings. A crucial aspect is the "CONSTRUCT" procedure, which efficiently generates potential k-rankings by aligning and comparing (k-1)-rankings. The filtering step then verifies the frequency of these candidates against the dataset.
Datasets
The paper evaluates its methods on three real-world datasets:
- SUSHI data: 5000 rankings of 10 types of sushi.
- STUDENTS data: 404 rankings of 16 goals from a psychological study.
- ESC14 data: Rankings from the European Song Contest 2014, consisting of 180 rankings of 26 countries (with a slight adjustment for self-ranking).
The authors also use synthetic data generated uniformly at random for comparison in their experiments.
Key Insights and Ideas
- Rank data is a distinct mining challenge: The paper highlights that rank data has unique properties (like transitivity) that require specialized algorithms, rather than simply reducing it to itemset mining.
- Apriori generalization is effective: The adaptation of the Apriori algorithm proves to be a viable approach for mining frequent subrankings, leveraging the monotonicity property of subrankings.
- Subrankings and association rules offer interpretable patterns: The discovered patterns, such as "sushi 8 > sushi 3 > sushi 9" or association rules like "goal 10 > goal 3 → goal 10 > goal 5," provide semantically meaningful insights into user preferences.
- The CONSTRUCT procedure is key: The novel algorithm for generating candidate k-rankings from (k-1)-rankings is central to the efficiency of the mining process.
Key Results
The paper demonstrates the effectiveness of its algorithms on the described datasets. Figure 3 shows that the number of frequent subrankings found in the real datasets is significantly lower than in synthetic data, suggesting that real-world preferences exhibit structure beyond random chance. The authors also report finding association rules with high confidence and interest, such as a rule in the STUDENTS data with confidence 0.9038 and interest 0.6544. The analysis of representative subrankings (Figure 4) indicates that for the STUDENTS and SUSHI datasets, a large majority of rankings are close to a central pattern, while the ESC14 data shows more diversity.
Limitations and Future Work
The authors acknowledge that their Apriori-based approach, while effective, might not be scalable to extremely large datasets. They suggest exploring ideas from faster itemset mining algorithms like Eclat or FP-growth, though noting that their data structures may not be directly applicable.
Future work directions include:
- Generalizing rank data: Extending the methods to handle incomplete rankings, partial orders, or "bags" of order relations.
- Combining rank and itemset mining: Integrating preference information with transactional data.
- Approximate pattern mining: Allowing for patterns that are supported by similar, rather than identical, rankings.
- Incorporating quantitative rank information: Considering the magnitude of preference (e.g., adjacent ranks vs. top/bottom ranks).
Summary updated