TL; DR The Criteo team won the PEReN Hackathon by using clustering approaches to distinguish pricing options from meal delivery data. We launched several exploratory data analysis to learn the data characteristics and extract many good features. The final solution combines a hand-made manual pricing cluster using a distance-fee correlation threshold and the Gaussian Mixture model handling the rest dataset.
How the journey started
On 30th Nov, our Criteo team “Critemon” won the 1st prize in the Hackathon “Segmente-moi si tu peux !” organized by PEReN (the Center of Expertise for Digital Regulation).
PEReN is an office placed under the joint authority of the French Ministers of Economy, Culture, and Digital Technology. It was created to help state administrations set or adapt digital platform regulations. Before adopting regulations or questioning the responsibilities, we must be able to identify the source of a decision made by digital platforms — This is the goal of the Hackathon.
More precisely, the Hackathon offers a simplified but realistic case of a meal delivery digital platform (e.g. Deliveroo or Uber eats). The platform displays to the user a single fee for each delivery order from the restaurant to the delivery place. Different options are possible for establishing this fee: the restaurant decides to apply one of the pricing algorithms offered by the platform, or the restaurant sets the fee manually.
The task is to detect from the provided dataset which fee is set by which option: e.g. by some pricing algorithm or manual pricing.
The first step is always the hardest
First, we started looking at the dataset to figure out what kind of information we would need and what we were missing. Starting with Data cleaning and Data Preparation is always preferable for a Hackathon.
Data cleaning is the process of preparing data for analysis. We skipped the step of correcting errors and inconsistencies as the dataset was clean. Still, the interesting part was formatting the data in a way that made it suitable for prediction. This is important in machine learning because the quality of the data has a direct impact on the accuracy and performance of the model.
Let’s take a look at the dataset. The provided dataset is composed of the following:
- order id
- latitude/ longitude and code postal of the restaurant
- latitude/longitude and code postal of delivery place
- weekday, hour and minute of order
- classified rainfall intensity
- temperature classification
- the fee for the order
Each row in the dataset represents one order. The pricing strategy used by the order is not provided in the dataset, so obviously, this is an unsupervised learning problem.
These data points are not usable as they are. We know theoretically that fees should depend on the distance between the restaurant and the delivery place. Therefore we compute the distance in meters using what we call the haversine formula.
The haversine formula is a mathematical formula that is used to calculate the distance between two points on a sphere based on their longitudes and latitudes. It is best suited for long distances and is often used in navigation and other applications that involve spherical trigonometry, but it also works for short distances. The distance distribution we had in the dataset looks like a Gaussian distribution, ranging from 0 to 10 km, centered on 5km. Using more precise ways, we can calculate the precise distance through roads, but they weren’t necessary.
After calculating the distance, we could remove the coordinate columns from the dataset.
We then added some features that might affect the pricing, for example :
- Extracting with a simple algorithm when the delivery has been made during the weekend, as this may be a factor that changes the fees (for both manual pricing and pricing algorithm).
- Extracting if the delivery place is in the same district as the restaurant (with the postal code).
At this point, our primary goal was to try some clustering algorithms and get our first result. We started by using the basic clustering algorithms of Kmeans and DBSCAN. We wanted to try them without any further data processing.
K-Means is used to segment data points into a specific number of clusters. The idea is to minimize the distance between a data point and a cluster centroid. It iterates through every point by assigning it to the nearest cluster centroid until the clustering does not change anymore.
DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is another clustering algorithm that looks like the K-Means but uses density-based centroids. It results in aggregating points that are close and separating points that are isolated or in low-density regions.
The result of launching Kmeans and DBSCAN with numbers of clusters ranging from 1 to 12 gave a negative score (the full score is 1 000 000). The clustering result has been projected on a 2-D space for visualization purposes. Looking at the visualization, we know that our methods were far from perfect — clusters are overlapped, and it is difficult to separate the pricing strategies from the initial dataset.
To make a good prediction, an engineer needs the best features
After the first unsuccessful attempt, we realized we needed to launch exploratory data analysis to understand the data in depth and learn the data characteristics. We launched several analyses, which eventually enabled us to target some very interesting patterns in the data.
The first analysis we performed was to check the distribution of each column, and we quickly found out:
- After dropping duplicated latitude/ longitude and code postal of restaurants, there are only 600 restaurants.
- All restaurants and delivery places are located in Paris
- The delivery hour ranges from 12 to 14, meaning only lunch orders in the dataset
The first finding seemed very interesting and inspired us to think about a question “is it likely that a restaurant uses pricing algorithm and manual pricing at the same time?” Intuitively the answer is no. If a restaurant chose a pricing algorithm offered by the platform, it is very unlikely it would still set the fee of some orders manually. Based on this assumption, we decided to predict per restaurant instead of per order, allowing us to reshape the dataset from 4800 samples (each sample is a transaction) to 600 samples (each sample is a restaurant).
However, it was still unclear how to aggregate the data at this stage. The first trivial step we made was to compute the mean value and the standard deviation of each column for each restaurant, and magic happened.
For some restaurants, the standard deviation of fees is 0, meaning they only have one fee for all their orders. Apparently, they are using manual pricing, and the owner is unwilling to set a second fee. We suddenly realized the number of unique fees per restaurant is a good predictive feature because the more unique fees a restaurant has, the more likely the fee is set by a pricing algorithm instead of a human being.
With the new aggregated features, we applied many other different clustering algorithms besides Kmeans and DBSCAN, for instance, Gaussian Mixture model and Kprototypes. The challenge was to consider at the same time numerical and categorical features as well as find the correct number of clusters.
The grid search helped us to find the best algorithm KPrototypes with the best hyperparameters and gave us first place on the leaderboard with a score of 55k.
KPrototypes is an algorithm-based KMeans and KModes, it can manage both numerical and categorical features. It measures the distance between numerical features using Euclidean distance (like K-means) but also measures the distance between categorical features using the number of matching categories.
We Are the Champions
After getting first place on the leaderboard, we made a great effort to reach a better score but failed.
The fact is, the dataset did not only contain fees determined by pricing algorithms but also by manual pricing from restaurants. The manual pricing added noise to the dataset and made clustering even harder. If we can separate manual pricing from the dataset, the score would be improved a lot.
We started to establish some hypotheses about manual pricing by checking the correlation matrix between fees and features. We quickly discovered that distance was the most correlated feature with fee. There were some low correlations between fee and distance, but most were very close to 1.
With the correlation between distance and fee as a threshold, we could identify the restaurants using manual pricing — they have a low correlation between distance and fee. We did some fine-tuning to extract as many as possible manual pricing restaurants, to get a clean dataset with only restaurants using pricing algorithms inside.
We then tried with other features correlation to find other groups, but the results were less conclusive.
After many tries, we started another grid search with the new features and the new dataset without the manual pricing. This time, the best clustering algorithm was the Gaussian Mixture model, with one hot encoding to manage categorical features.
The Gaussian mixture model is a probabilistic model that is based on the assumption that points are generated from a mixture of a finite number of Gaussian distributions.
The Gaussian mixture model can be used with a ‘tied’ or ‘diag’ covariance matrix. We first tested ‘diag’ as we wanted to achieve a better score with one diagonal covariance by cluster; however, the execution took a very long time. To reduce the execution time, we used the parameters ‘tied’ to have only a full covariance matrix for all the clusters. We didn’t notice much difference in terms of performance.
With the hand-made manual pricing cluster using distance-fee correlation threshold and the Gaussian Mixture model handling the dataset containing only pricing algorithms, we obtain a score of 157k.
Our journey continues
Our team was able to achieve victory at the hackathon by using a combination of technical skills, collaboration, and persistence. At first, we struggled to get started. Yet, after carefully analyzing the problem and brainstorming potential solutions, we divided the work among team members and began working on implementing our ideas. Throughout the process, we communicated regularly and provided support and feedback to each other. Despite facing some challenges and obstacles along the way, we remained focused and determined to succeed.
We are proud of our achievement, and we would like to thank PEReN for hosting and organizing this event. We are most of all grateful to Criteo for allowing us to participate in such a rewarding event under Criteo’s color! (We are hiring!)
