Abstract
Recently, ranked data has become prevalent in the era of the Internet and e-commerce, where consumers express their opinions through ranks of a set of items. Applications of clustering ranked data include target marketing, campaign selection, and top-k item identification. This paper implements a campaign selection process using clustering on rank-ordered feedback data. We propose a method that groups ranked data using various distance metrics—Kendall’s tau, Spearman’s rho square, Spearman’s footrule, and Cayley’s distance—and applies the resulting knowledge to the campaign selection process. Experimental results on real datasets demonstrate the effectiveness of our proposed clustering algorithm compared to existing methods.
Introduction
In the modern digital economy, consumer feedback is frequently captured as ranked lists of preferences. For example, a user might rank a set of products from most to least preferred. Traditional clustering algorithms, such as K-Means, are designed for continuous numerical data and rely on Euclidean distance and mean calculations. These concepts do not translate directly to ordinal rankings, where the "average" of two permutations may not be a valid permutation itself. Furthermore, standard clustering often suffers from initialization sensitivity, leading to suboptimal local minima. This paper addresses these challenges by introducing the KRanks framework, specifically designed for clustering ranked data to enhance marketing campaign selection.
Methodology
The proposed KRanks framework consists of three algorithmic variants: KR1 (random initialization), KR2 (strategic initialization), and KR3 (strategic initialization with greedy refinement).
Distance Metrics for Ranked Data
To quantify the similarity between ranked lists, we employ specialized metrics instead of standard Euclidean distance. These include:
- Kendall’s Tau: Measures the number of pairwise inversions.
- Spearman’s Rho Square: Based on the squared differences in ranks.
- Spearman’s Footrule: Based on the absolute differences in ranks.
- Cayley’s Distance: Measures the minimum number of transpositions required to transform one ranking into another.
Strategic Initialization (KR2/KR3)
To overcome the initialization problem, we move beyond random selection. We identify initial cluster centers by calculating distances from "pivot" permutations (e.g., identity or reverse identity rankings) to ensure that starting points are mathematically distant and representative of the preference space.
Greedy Mode Refinement (KR3)
A significant challenge in ranked clustering is that the aggregate "mode" of a cluster might contain non-distinct ranks (ties). KR3 introduces a frequency-table-based greedy approach to ensure that every cluster center is a valid, distinct permutation, which is essential for defining clear target preferences for marketing.
Campaign Selection Logic
We utilize the derived cluster centers to identify the most preferred items for specific consumer segments. By matching campaigns to these "least rank" items, we optimize the relevance of marketing efforts.
Experimental Evaluation
The algorithms were evaluated using two real-world datasets:
- Sushi Dataset: 5,000 instances where consumers ranked 10 different types of sushi.
- American Psychological Association (APA) Dataset: 5,738 instances of voters ranking 5 candidates.
- Synthetic Data: Used to assess scalability across varying dimensions and data sizes.
Performance was measured using the Overall Average Silhouette Width (OASW) and the Validity Index (VI). Results indicated that KR3 and KR2 consistently outperformed traditional K-Means, K-Medoids, and K-Modes.
Key Insights and Results
- Initialization Impact: Strategic initialization (KR2) significantly improves cluster stability and quality over random initialization (KR1).
- The Distinctness Requirement: The KR3 variant's ability to maintain distinct ranks in cluster centers proved vital for practical campaign design, ensuring that each segment has a clear, actionable preference profile.
- Metric Performance: Kendall’s tau emerged as the most robust distance metric for producing high-quality clusters across the tested datasets.
- Targeted Marketing: Using the Grand Attention Factor (GAF) and Local Attention Factor (LAF), the study demonstrated that segmented marketing campaigns tailored to specific clusters significantly outperform generic, mass-market approaches.
- Efficiency: Scalability tests confirmed that the KRanks algorithms scale linearly with data size and dimensionality, making them suitable for large-scale e-commerce applications.
Conclusion
This research provides a robust framework for clustering ranked data, offering a significant improvement over traditional numerical methods for market segmentation. While the current model focuses on complete rankings, future work will explore handling partial rankings and temporal shifts in consumer preferences. Additionally, optimizing the greedy refinement step for extremely high-dimensional item sets remains an area for further investigation.
Summary updated