Abstract
This paper describes our ensemble of three classifiers for the KDD Cup 2009 challenge. We transform the three binary classification tasks into a joint multi-class classification problem and utilize an ensemble of an L1-regularized maximum entropy model, heterogeneous AdaBoost, and Selective Naïve Bayes. Our approach secured 3rd place in the slow track with an average AUC of 0.8461.
Introduction
The KDD Cup 2009, sponsored by the French telecom company Orange, focused on customer relationship management (CRM) through three predictive tasks: churn (leaving the company), appetency (buying a new service), and up-selling (buying upgrades). The dataset was characterized by extreme heterogeneity, high dimensionality (up to 15,000 features), and significant amounts of missing data. Success required robust handling of sparse categorical features and a strategy to prevent overfitting on a noisy public leaderboard.
Methodology
Our solution relies on an ensemble of three diverse classifiers, each designed to address specific data challenges:
- L1-Regularized Maximum Entropy Model: This linear model handles high-dimensional categorical data by expanding categories into binary indicators. Numerical features were scaled, and missing values were handled by adding explicit "is_missing" indicator features.
- Heterogeneous AdaBoost: This model utilizes a custom base learner that combines numerical and categorical decision trees. These trees handle missing values natively by treating "missing" as a distinct category, as shown in the tree structures below.
- Selective Naïve Bayes (SNB): This model provides a probabilistic baseline by automatically grouping categorical features and discretizing numerical ones using the Minimum Optimized Description Length (MODL) criterion.
To refine the ensemble, we applied a post-processing step using a linear Support Vector Machine (SVM) to adjust final scores based on the mutual exclusivity of the target labels.
Key Insights and Ideas
Exploiting Label Exclusivity
Analysis of the training data revealed that customers rarely exhibited more than one of the three target behaviors simultaneously. We exploited this by treating the problem as a 4-class classification task (Churn, Appetency, Up-selling, or None) and using the SVM post-processor to penalize conflicting high-probability predictions across tasks.
Missingness as a Feature
Rather than simple imputation, we treated the absence of data as informative. Adding binary indicators for missing values allowed the linear models to capture the predictive power inherent in data sparsity, which proved highly effective given the messy nature of the Orange dataset.
Validation Strategy
A critical observation was the discrepancy between local cross-validation (CV) results and the public leaderboard. As shown in the distribution for the Churn task, the public leaderboard score (dashed line) was significantly lower than the CV mean, suggesting the 10% public test sample was unrepresentative. By prioritizing local CV over leaderboard chasing, we avoided overfitting.
Key Results
The final ensemble achieved an average AUC of 0.8461 on the private test set, securing 3rd place. Post-processing significantly improved performance; for instance, the appetency task AUC rose from 0.8671 to 0.8789. The diversity of the ensemble was key, as different models excelled at different tasks: the Maximum Entropy model was strongest for appetency, while AdaBoost performed best for up-selling.
Conclusion
Our solution demonstrates that handling heterogeneous CRM data requires a multi-faceted approach. By combining linear models, boosting, and probabilistic classifiers, and by leveraging domain-specific insights like label exclusivity and missingness patterns, we built a robust system capable of generalizing well to unseen data.
Summary updated